Robust/src/Analysis/MLP/MLPAnalysis.java

   1 package Analysis.MLP;
   2
   3 import Analysis.CallGraph.*;
   4 import Analysis.OwnershipAnalysis.*;
   5 import IR.*;
   6 import IR.Flat.*;
   7 import IR.Tree.*;
   8 import java.util.*;
   9 import java.io.*;
  10
  11
  12 public class MLPAnalysis {
  13
  14   // data from the compiler
  15   private State             state;
  16   private TypeUtil          typeUtil;
  17   private CallGraph         callGraph;
  18   private OwnershipAnalysis ownAnalysis;
  19
  20
  21   // an implicit SESE is automatically spliced into
  22   // the IR graph around the C main before this analysis--it
  23   // is nothing special except that we can make assumptions
  24   // about it, such as the whole program ends when it ends
  25   private FlatSESEEnterNode mainSESE;
  26
  27   // SESEs that are the root of an SESE tree belong to this
  28   // set--the main SESE is always a root, statically SESEs
  29   // inside methods are a root because we don't know how they
  30   // will fit into the runtime tree of SESEs
  31   private Set<FlatSESEEnterNode> rootSESEs;
  32
  33   // simply a set of every reachable SESE in the program, not
  34   // including caller placeholder SESEs
  35   private Set<FlatSESEEnterNode> allSESEs;
  36
  37
  38   // A mapping of flat nodes to the stack of SESEs for that node, where
  39   // an SESE is the child of the SESE directly below it on the stack.
  40   // These stacks do not reflect the heirarchy over methods calls--whenever
  41   // there is an empty stack it means all variables are available.
  42   private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
  43
  44   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessRootView;
  45   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessVirtualReads;
  46   private Hashtable< FlatNode, VarSrcTokTable           > variableResults;
  47   private Hashtable< FlatNode, Set<TempDescriptor>      > notAvailableResults;
  48   private Hashtable< FlatNode, CodePlan                 > codePlans;
  49
  50   private Hashtable< FlatEdge, FlatWriteDynamicVarNode  > wdvNodesToSpliceIn;
  51
  52   private Hashtable< MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet;
  53
  54   public static int maxSESEage = -1;
  55
  56
  57   // use these methods in BuildCode to have access to analysis results
  58   public FlatSESEEnterNode getMainSESE() {
  59     return mainSESE;
  60   }
  61
  62   public Set<FlatSESEEnterNode> getRootSESEs() {
  63     return rootSESEs;
  64   }
  65
  66   public Set<FlatSESEEnterNode> getAllSESEs() {
  67     return allSESEs;
  68   }
  69
  70   public int getMaxSESEage() {
  71     return maxSESEage;
  72   }
  73
  74   // may be null
  75   public CodePlan getCodePlan( FlatNode fn ) {
  76     CodePlan cp = codePlans.get( fn );
  77     return cp;
  78   }
  79
  80
  81   public MLPAnalysis( State             state,
  82                       TypeUtil          tu,
  83                       CallGraph         callGraph,
  84                       OwnershipAnalysis ownAnalysis
  85                       ) {
  86
  87     double timeStartAnalysis = (double) System.nanoTime();
  88
  89     this.state       = state;
  90     this.typeUtil    = tu;
  91     this.callGraph   = callGraph;
  92     this.ownAnalysis = ownAnalysis;
  93     this.maxSESEage  = state.MLP_MAXSESEAGE;
  94
  95     rootSESEs = new HashSet<FlatSESEEnterNode>();
  96     allSESEs  = new HashSet<FlatSESEEnterNode>();
  97
  98     seseStacks           = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
  99     livenessRootView     = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 100     livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 101     variableResults      = new Hashtable< FlatNode, VarSrcTokTable           >();
 102     notAvailableResults  = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 103     codePlans            = new Hashtable< FlatNode, CodePlan                 >();
 104     wdvNodesToSpliceIn   = new Hashtable< FlatEdge, FlatWriteDynamicVarNode  >();
 105
 106     mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet<AllocationSite>>();
 107
 108
 109     FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
 110
 111     mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
 112     mainSESE.setfmEnclosing( fmMain );
 113     mainSESE.setmdEnclosing( fmMain.getMethod() );
 114     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
 115
 116
 117     // 1st pass
 118     // run analysis on each method that is actually called
 119     // reachability analysis already computed this so reuse
 120     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 121     while( methItr.hasNext() ) {
 122       Descriptor d  = methItr.next();
 123       FlatMethod fm = state.getMethodFlat( d );
 124
 125       // find every SESE from methods that may be called
 126       // and organize them into roots and children
 127       buildForestForward( fm );
 128     }
 129
 130
 131     // 2nd pass, results are saved in FlatSESEEnterNode, so
 132     // intermediate results, for safety, are discarded
 133     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
 134     while( rootItr.hasNext() ) {
 135       FlatSESEEnterNode root = rootItr.next();
 136       livenessAnalysisBackward( root,
 137                                 true,
 138                                 null );
 139     }
 140
 141
 142     // 3rd pass
 143     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 144     while( methItr.hasNext() ) {
 145       Descriptor d  = methItr.next();
 146       FlatMethod fm = state.getMethodFlat( d );
 147
 148       // starting from roots do a forward, fixed-point
 149       // variable analysis for refinement and stalls
 150       variableAnalysisForward( fm );
 151     }
 152
 153     // 4th pass, compute liveness contribution from
 154     // virtual reads discovered in variable pass
 155     rootItr = rootSESEs.iterator();
 156     while( rootItr.hasNext() ) {
 157       FlatSESEEnterNode root = rootItr.next();
 158       livenessAnalysisBackward( root,
 159                                 true,
 160                                 null );
 161     }
 162
 163
 164     /*
 165       SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
 166
 167     // 5th pass
 168     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 169     while( methItr.hasNext() ) {
 170       Descriptor d  = methItr.next();
 171       FlatMethod fm = state.getMethodFlat( d );
 172
 173       // prune variable results in one traversal
 174       // by removing reference variables that are not live
 175       pruneVariableResultsWithLiveness( fm );
 176     }
 177     */
 178
 179
 180     // 6th pass
 181     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 182     while( methItr.hasNext() ) {
 183       Descriptor d  = methItr.next();
 184       FlatMethod fm = state.getMethodFlat( d );
 185
 186       // compute what is not available at every program
 187       // point, in a forward fixed-point pass
 188       notAvailableForward( fm );
 189     }
 190
 191     // new pass
 192     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 193         JavaCallGraph javaCallGraph = new JavaCallGraph(state,tu);
 194     while( methItr.hasNext() ) {
 195       Descriptor d  = methItr.next();
 196       FlatMethod fm = state.getMethodFlat( d );
 197       methodEffects(fm,javaCallGraph);
 198     }
 199
 200     // disjoint analysis with a set of flagged allocation sites of live-in variable
 201         try {
 202                 OwnershipAnalysis oa2 = new OwnershipAnalysis(state, tu, callGraph,
 203                                 state.OWNERSHIPALLOCDEPTH, false,
 204                                 false, state.OWNERSHIPALIASFILE,
 205                                 state.METHODEFFECTS,
 206                                 mapMethodContextToLiveInAllocationSiteSet);
 207                 // debug
 208                 methItr = oa2.descriptorsToAnalyze.iterator();
 209                 while (methItr.hasNext()) {
 210                         Descriptor d = methItr.next();
 211                         FlatMethod fm = state.getMethodFlat(d);
 212                         debugFunction(oa2, fm);
 213                 }
 214                 //
 215         } catch (IOException e) {
 216                 System.err.println(e);
 217         }
 218
 219
 220
 221     // 7th pass
 222     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 223     while( methItr.hasNext() ) {
 224       Descriptor d  = methItr.next();
 225       FlatMethod fm = state.getMethodFlat( d );
 226
 227       // compute a plan for code injections
 228       codePlansForward( fm );
 229     }
 230
 231
 232     // splice new IR nodes into graph after all
 233     // analysis passes are complete
 234     Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
 235     while( spliceItr.hasNext() ) {
 236       Map.Entry               me    = (Map.Entry)               spliceItr.next();
 237       FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
 238       fwdvn.spliceIntoIR();
 239     }
 240
 241
 242     double timeEndAnalysis = (double) System.nanoTime();
 243     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 244     String treport = String.format( "The mlp analysis took %.3f sec.", dt );
 245     System.out.println( treport );
 246
 247     if( state.MLPDEBUG ) {
 248       try {
 249         writeReports( treport );
 250       } catch( IOException e ) {}
 251     }
 252   }
 253
 254
 255   private void buildForestForward( FlatMethod fm ) {
 256
 257     // start from flat method top, visit every node in
 258     // method exactly once, find SESEs and remember
 259     // roots and child relationships
 260     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 261     flatNodesToVisit.add( fm );
 262
 263     Set<FlatNode> visited = new HashSet<FlatNode>();
 264
 265     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 266     seseStacks.put( fm, seseStackFirst );
 267
 268     while( !flatNodesToVisit.isEmpty() ) {
 269       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 270       FlatNode fn = fnItr.next();
 271
 272       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 273       assert seseStack != null;
 274
 275       flatNodesToVisit.remove( fn );
 276       visited.add( fn );
 277
 278       buildForest_nodeActions( fn, seseStack, fm );
 279
 280       for( int i = 0; i < fn.numNext(); i++ ) {
 281         FlatNode nn = fn.getNext( i );
 282
 283         if( !visited.contains( nn ) ) {
 284           flatNodesToVisit.add( nn );
 285
 286           // clone stack and send along each analysis path
 287           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 288         }
 289       }
 290     }
 291   }
 292
 293   private void buildForest_nodeActions( FlatNode fn,
 294                                         Stack<FlatSESEEnterNode> seseStack,
 295                                         FlatMethod fm ) {
 296     switch( fn.kind() ) {
 297
 298     case FKind.FlatSESEEnterNode: {
 299       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 300
 301       if( !fsen.getIsCallerSESEplaceholder() ) {
 302         allSESEs.add( fsen );
 303       }
 304
 305       fsen.setfmEnclosing( fm );
 306       fsen.setmdEnclosing( fm.getMethod() );
 307       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 308
 309       if( seseStack.empty() ) {
 310         rootSESEs.add( fsen );
 311         fsen.setParent( null );
 312       } else {
 313         seseStack.peek().addChild( fsen );
 314         fsen.setParent( seseStack.peek() );
 315       }
 316
 317       seseStack.push( fsen );
 318     } break;
 319
 320     case FKind.FlatSESEExitNode: {
 321       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 322       assert !seseStack.empty();
 323       FlatSESEEnterNode fsen = seseStack.pop();
 324     } break;
 325
 326     case FKind.FlatReturnNode: {
 327       FlatReturnNode frn = (FlatReturnNode) fn;
 328       if( !seseStack.empty() &&
 329           !seseStack.peek().getIsCallerSESEplaceholder()
 330         ) {
 331         throw new Error( "Error: return statement enclosed within SESE "+
 332                          seseStack.peek().getPrettyIdentifier() );
 333       }
 334     } break;
 335
 336     }
 337   }
 338
 339
 340   private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
 341                                          boolean toplevel,
 342                                          Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
 343
 344     // start from an SESE exit, visit nodes in reverse up to
 345     // SESE enter in a fixed-point scheme, where children SESEs
 346     // should already be analyzed and therefore can be skipped
 347     // because child SESE enter node has all necessary info
 348     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 349
 350     if( toplevel ) {
 351       flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
 352     } else {
 353       flatNodesToVisit.add( fsen.getFlatExit() );
 354     }
 355
 356     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
 357       new Hashtable< FlatNode, Set<TempDescriptor> >();
 358
 359     if( toplevel ) {
 360       liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
 361     }
 362
 363     while( !flatNodesToVisit.isEmpty() ) {
 364       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 365       flatNodesToVisit.remove( fn );
 366
 367       Set<TempDescriptor> prev = livenessResults.get( fn );
 368
 369       // merge sets from control flow joins
 370       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 371       for( int i = 0; i < fn.numNext(); i++ ) {
 372         FlatNode nn = fn.getNext( i );
 373         Set<TempDescriptor> s = livenessResults.get( nn );
 374         if( s != null ) {
 375           u.addAll( s );
 376         }
 377       }
 378
 379       Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
 380
 381       // if a new result, schedule backward nodes for analysis
 382       if( !curr.equals( prev ) ) {
 383         livenessResults.put( fn, curr );
 384
 385         // don't flow backwards past current SESE enter
 386         if( !fn.equals( fsen ) ) {
 387           for( int i = 0; i < fn.numPrev(); i++ ) {
 388             FlatNode nn = fn.getPrev( i );
 389             flatNodesToVisit.add( nn );
 390           }
 391         }
 392       }
 393     }
 394
 395     Set<TempDescriptor> s = livenessResults.get( fsen );
 396     if( s != null ) {
 397       fsen.addInVarSet( s );
 398     }
 399
 400     // remember liveness per node from the root view as the
 401     // global liveness of variables for later passes to use
 402     if( toplevel ) {
 403       livenessRootView.putAll( livenessResults );
 404     }
 405
 406     // post-order traversal, so do children first
 407     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 408     while( childItr.hasNext() ) {
 409       FlatSESEEnterNode fsenChild = childItr.next();
 410       livenessAnalysisBackward( fsenChild, false, liveout );
 411     }
 412   }
 413
 414   private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
 415                                                     Set<TempDescriptor> liveIn,
 416                                                     FlatSESEEnterNode currentSESE,
 417                                                     boolean toplevel,
 418                                                     Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
 419                                                   ) {
 420     switch( fn.kind() ) {
 421
 422     case FKind.FlatSESEExitNode:
 423       if( toplevel ) {
 424         FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 425         if( !liveout.containsKey( fsexn ) ) {
 426           liveout.put( fsexn, new HashSet<TempDescriptor>() );
 427         }
 428         liveout.get( fsexn ).addAll( liveIn );
 429       }
 430       // no break, sese exits should also execute default actions
 431
 432     default: {
 433       // handle effects of statement in reverse, writes then reads
 434       TempDescriptor [] writeTemps = fn.writesTemps();
 435       for( int i = 0; i < writeTemps.length; ++i ) {
 436         liveIn.remove( writeTemps[i] );
 437
 438         if( !toplevel ) {
 439           FlatSESEExitNode fsexn = currentSESE.getFlatExit();
 440           Set<TempDescriptor> livetemps = liveout.get( fsexn );
 441           if( livetemps != null &&
 442               livetemps.contains( writeTemps[i] ) ) {
 443             // write to a live out temp...
 444             // need to put in SESE liveout set
 445             currentSESE.addOutVar( writeTemps[i] );
 446           }
 447         }
 448       }
 449
 450       TempDescriptor [] readTemps = fn.readsTemps();
 451       for( int i = 0; i < readTemps.length; ++i ) {
 452         liveIn.add( readTemps[i] );
 453       }
 454
 455       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
 456       if( virtualReadTemps != null ) {
 457         liveIn.addAll( virtualReadTemps );
 458       }
 459
 460     } break;
 461
 462     } // end switch
 463
 464     return liveIn;
 465   }
 466
 467
 468   private void variableAnalysisForward( FlatMethod fm ) {
 469
 470     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 471     flatNodesToVisit.add( fm );
 472
 473     while( !flatNodesToVisit.isEmpty() ) {
 474       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 475       flatNodesToVisit.remove( fn );
 476
 477       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 478       assert seseStack != null;
 479
 480       VarSrcTokTable prev = variableResults.get( fn );
 481
 482       // merge sets from control flow joins
 483       VarSrcTokTable curr = new VarSrcTokTable();
 484       for( int i = 0; i < fn.numPrev(); i++ ) {
 485         FlatNode nn = fn.getPrev( i );
 486         VarSrcTokTable incoming = variableResults.get( nn );
 487         curr.merge( incoming );
 488       }
 489
 490       if( !seseStack.empty() ) {
 491         variable_nodeActions( fn, curr, seseStack.peek() );
 492       }
 493
 494       // if a new result, schedule forward nodes for analysis
 495       if( !curr.equals( prev ) ) {
 496         variableResults.put( fn, curr );
 497
 498         for( int i = 0; i < fn.numNext(); i++ ) {
 499           FlatNode nn = fn.getNext( i );
 500           flatNodesToVisit.add( nn );
 501         }
 502       }
 503     }
 504   }
 505
 506   private void variable_nodeActions( FlatNode fn,
 507                                      VarSrcTokTable vstTable,
 508                                      FlatSESEEnterNode currentSESE ) {
 509     switch( fn.kind() ) {
 510
 511     case FKind.FlatSESEEnterNode: {
 512       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 513       assert fsen.equals( currentSESE );
 514
 515       vstTable.age( currentSESE );
 516       vstTable.assertConsistency();
 517     } break;
 518
 519     case FKind.FlatSESEExitNode: {
 520       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 521       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 522       assert currentSESE.getChildren().contains( fsen );
 523
 524       vstTable.remapChildTokens( fsen );
 525
 526       // liveness virtual reads are things that might be
 527       // written by an SESE and should be added to the in-set
 528       // anything virtually read by this SESE should be pruned
 529       // of parent or sibling sources
 530       Set<TempDescriptor> liveVars         = livenessRootView.get( fn );
 531       Set<TempDescriptor> fsenVirtReads    = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
 532       Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
 533       if( fsenVirtReadsOld != null ) {
 534         fsenVirtReads.addAll( fsenVirtReadsOld );
 535       }
 536       livenessVirtualReads.put( fn, fsenVirtReads );
 537
 538
 539       // then all child out-set tokens are guaranteed
 540       // to be filled in, so clobber those entries with
 541       // the latest, clean sources
 542       Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
 543       while( outVarItr.hasNext() ) {
 544         TempDescriptor outVar = outVarItr.next();
 545         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 546         ts.add( outVar );
 547         VariableSourceToken vst =
 548           new VariableSourceToken( ts,
 549                                    fsen,
 550                                    new Integer( 0 ),
 551                                    outVar
 552                                    );
 553         vstTable.remove( outVar );
 554         vstTable.add( vst );
 555       }
 556       vstTable.assertConsistency();
 557
 558     } break;
 559
 560     case FKind.FlatOpNode: {
 561       FlatOpNode fon = (FlatOpNode) fn;
 562
 563       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 564         TempDescriptor lhs = fon.getDest();
 565         TempDescriptor rhs = fon.getLeft();
 566
 567         vstTable.remove( lhs );
 568
 569         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 570
 571         Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
 572         while( itr.hasNext() ) {
 573           VariableSourceToken vst = itr.next();
 574
 575           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 576           ts.add( lhs );
 577
 578           if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
 579             // if the source comes from a child, copy it over
 580             forAddition.add( new VariableSourceToken( ts,
 581                                                       vst.getSESE(),
 582                                                       vst.getAge(),
 583                                                       vst.getAddrVar()
 584                                                       )
 585                              );
 586           } else {
 587             // otherwise, stamp it as us as the source
 588             forAddition.add( new VariableSourceToken( ts,
 589                                                       currentSESE,
 590                                                       new Integer( 0 ),
 591                                                       lhs
 592                                                       )
 593                              );
 594           }
 595         }
 596
 597         vstTable.addAll( forAddition );
 598
 599         // only break if this is an ASSIGN op node,
 600         // otherwise fall through to default case
 601         vstTable.assertConsistency();
 602         break;
 603       }
 604     }
 605
 606     // note that FlatOpNode's that aren't ASSIGN
 607     // fall through to this default case
 608     default: {
 609       TempDescriptor [] writeTemps = fn.writesTemps();
 610       if( writeTemps.length > 0 ) {
 611
 612
 613         // for now, when writeTemps > 1, make sure
 614         // its a call node, programmer enforce only
 615         // doing stuff like calling a print routine
 616         //assert writeTemps.length == 1;
 617         if( writeTemps.length > 1 ) {
 618           assert fn.kind() == FKind.FlatCall ||
 619                  fn.kind() == FKind.FlatMethod;
 620           break;
 621         }
 622
 623         vstTable.remove( writeTemps[0] );
 624
 625         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 626         ts.add( writeTemps[0] );
 627
 628         vstTable.add( new VariableSourceToken( ts,
 629                                                currentSESE,
 630                                                new Integer( 0 ),
 631                                                writeTemps[0]
 632                                              )
 633                       );
 634       }
 635
 636       vstTable.assertConsistency();
 637     } break;
 638
 639     } // end switch
 640   }
 641
 642
 643   private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
 644
 645     // start from flat method top, visit every node in
 646     // method exactly once
 647     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 648     flatNodesToVisit.add( fm );
 649
 650     Set<FlatNode> visited = new HashSet<FlatNode>();
 651
 652     while( !flatNodesToVisit.isEmpty() ) {
 653       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 654       FlatNode fn = fnItr.next();
 655
 656       flatNodesToVisit.remove( fn );
 657       visited.add( fn );
 658
 659       Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
 660       VarSrcTokTable      vstTable    = variableResults.get( fn );
 661
 662       vstTable.pruneByLiveness( rootLiveSet );
 663
 664       for( int i = 0; i < fn.numNext(); i++ ) {
 665         FlatNode nn = fn.getNext( i );
 666
 667         if( !visited.contains( nn ) ) {
 668           flatNodesToVisit.add( nn );
 669         }
 670       }
 671     }
 672   }
 673
 674
 675   private void notAvailableForward( FlatMethod fm ) {
 676
 677     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 678     flatNodesToVisit.add( fm );
 679
 680     while( !flatNodesToVisit.isEmpty() ) {
 681       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 682       flatNodesToVisit.remove( fn );
 683
 684       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 685       assert seseStack != null;
 686
 687       Set<TempDescriptor> prev = notAvailableResults.get( fn );
 688
 689       Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
 690       for( int i = 0; i < fn.numPrev(); i++ ) {
 691         FlatNode nn = fn.getPrev( i );
 692         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
 693         if( notAvailIn != null ) {
 694           curr.addAll( notAvailIn );
 695         }
 696       }
 697
 698       if( !seseStack.empty() ) {
 699         notAvailable_nodeActions( fn, curr, seseStack.peek() );
 700       }
 701
 702       // if a new result, schedule forward nodes for analysis
 703       if( !curr.equals( prev ) ) {
 704         notAvailableResults.put( fn, curr );
 705
 706         for( int i = 0; i < fn.numNext(); i++ ) {
 707           FlatNode nn = fn.getNext( i );
 708           flatNodesToVisit.add( nn );
 709         }
 710       }
 711     }
 712   }
 713
 714   private void notAvailable_nodeActions( FlatNode fn,
 715                                          Set<TempDescriptor> notAvailSet,
 716                                          FlatSESEEnterNode currentSESE ) {
 717
 718     // any temps that are removed from the not available set
 719     // at this node should be marked in this node's code plan
 720     // as temps to be grabbed at runtime!
 721
 722     switch( fn.kind() ) {
 723
 724     case FKind.FlatSESEEnterNode: {
 725       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 726       assert fsen.equals( currentSESE );
 727       notAvailSet.clear();
 728     } break;
 729
 730     case FKind.FlatSESEExitNode: {
 731       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 732       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 733       assert currentSESE.getChildren().contains( fsen );
 734       notAvailSet.addAll( fsen.getOutVarSet() );
 735     } break;
 736
 737     case FKind.FlatMethod: {
 738       notAvailSet.clear();
 739     }
 740
 741     case FKind.FlatOpNode: {
 742       FlatOpNode fon = (FlatOpNode) fn;
 743
 744       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 745         TempDescriptor lhs = fon.getDest();
 746         TempDescriptor rhs = fon.getLeft();
 747
 748         // copy makes lhs same availability as rhs
 749         if( notAvailSet.contains( rhs ) ) {
 750           notAvailSet.add( lhs );
 751         } else {
 752           notAvailSet.remove( lhs );
 753         }
 754
 755         // only break if this is an ASSIGN op node,
 756         // otherwise fall through to default case
 757         break;
 758       }
 759     }
 760
 761     // note that FlatOpNode's that aren't ASSIGN
 762     // fall through to this default case
 763     default: {
 764       TempDescriptor [] writeTemps = fn.writesTemps();
 765       for( int i = 0; i < writeTemps.length; i++ ) {
 766         TempDescriptor wTemp = writeTemps[i];
 767         notAvailSet.remove( wTemp );
 768       }
 769       TempDescriptor [] readTemps = fn.readsTemps();
 770       for( int i = 0; i < readTemps.length; i++ ) {
 771         TempDescriptor rTemp = readTemps[i];
 772         notAvailSet.remove( rTemp );
 773
 774         // if this variable has exactly one source, potentially
 775         // get other things from this source as well
 776         VarSrcTokTable vstTable = variableResults.get( fn );
 777
 778         Integer srcType =
 779           vstTable.getRefVarSrcType( rTemp,
 780                                      currentSESE,
 781                                      currentSESE.getParent() );
 782
 783         if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
 784
 785           VariableSourceToken vst = vstTable.get( rTemp ).iterator().next();
 786
 787           Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
 788                                                                  vst.getAge()
 789                                                                  ).iterator();
 790
 791           // look through things that are also available from same source
 792           while( availItr.hasNext() ) {
 793             VariableSourceToken vstAlsoAvail = availItr.next();
 794
 795             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
 796             while( refVarItr.hasNext() ) {
 797               TempDescriptor refVarAlso = refVarItr.next();
 798
 799               // if a variable is available from the same source, AND it ALSO
 800               // only comes from one statically known source, mark it available
 801               Integer srcTypeAlso =
 802                 vstTable.getRefVarSrcType( refVarAlso,
 803                                            currentSESE,
 804                                            currentSESE.getParent() );
 805               if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
 806                 notAvailSet.remove( refVarAlso );
 807               }
 808             }
 809           }
 810         }
 811       }
 812     } break;
 813
 814     } // end switch
 815   }
 816
 817   private void debugFunction(OwnershipAnalysis oa2, FlatMethod fm) {
 818
 819           String methodName="SomeWork";
 820
 821           MethodDescriptor md=fm.getMethod();
 822                 HashSet<MethodContext> mcSet=oa2.getAllMethodContextSetByDescriptor(md);
 823                 Iterator<MethodContext> mcIter=mcSet.iterator();
 824
 825                 while(mcIter.hasNext()){
 826                         MethodContext mc=mcIter.next();
 827
 828                         OwnershipGraph og=oa2.getOwnvershipGraphByMethodContext(mc);
 829
 830                         if(fm.toString().indexOf(methodName)>0){
 831                                  try {
 832                                    og.writeGraph(fm.toString() + "SECONDGRAPH",
 833                                                  true,  // write labels (variables)
 834                                                  true,  // selectively hide intermediate temp vars
 835                                                  true,  // prune unreachable heap regions
 836                                                  false, // show back edges to confirm graph validity
 837                                                  false, // show parameter indices (unmaintained!)
 838                                                  true,  // hide subset reachability states
 839                                                  false);// hide edge taints
 840                                  } catch (IOException e) {
 841                                  System.out.println("Error writing debug capture.");
 842                                  System.exit(0);
 843                                  }
 844                         }
 845
 846
 847
 848                 }
 849
 850   }
 851
 852         private void methodEffects(FlatMethod fm, CallGraph callGraph) {
 853
 854                 MethodDescriptor md=fm.getMethod();
 855                 HashSet<MethodContext> mcSet=ownAnalysis.getAllMethodContextSetByDescriptor(md);
 856                 Iterator<MethodContext> mcIter=mcSet.iterator();
 857
 858                 while(mcIter.hasNext()){
 859                         MethodContext mc=mcIter.next();
 860
 861                         Set<FlatNode> visited = new HashSet<FlatNode>();
 862
 863                         Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 864                         flatNodesToVisit.add(fm);
 865
 866                         while (!flatNodesToVisit.isEmpty()) {
 867                                 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 868                                 flatNodesToVisit.remove(fn);
 869
 870                                 Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
 871                                 assert seseStack != null;
 872
 873                                 if (!seseStack.empty()) {
 874                                         effects_nodeActions(mc, fn, seseStack.peek(), callGraph);
 875                                 }
 876
 877                                 flatNodesToVisit.remove(fn);
 878                                 visited.add(fn);
 879
 880                                 for (int i = 0; i < fn.numNext(); i++) {
 881                                         FlatNode nn = fn.getNext(i);
 882                                         if (!visited.contains(nn)) {
 883                                                 flatNodesToVisit.add(nn);
 884                                         }
 885                                 }
 886
 887                         }
 888
 889
 890                 }
 891
 892         }
 893
 894         private void analyzeRelatedAllocationSite(MethodDescriptor callerMD,
 895                         MethodContext calleeMC, HashSet<Integer> paramIndexSet,
 896                         HashSet<HeapRegionNode> visitedHRN) {
 897
 898                 HashSet<MethodContext> mcSet = ownAnalysis
 899                                 .getAllMethodContextSetByDescriptor(callerMD);
 900
 901                 if (mcSet != null) {
 902
 903                         Iterator<MethodContext> mcIter = mcSet.iterator();
 904
 905                         FlatMethod callerFM = state.getMethodFlat(callerMD);
 906
 907                         while (mcIter.hasNext()) {
 908                                 MethodContext mc = mcIter.next();
 909
 910                                 Set<FlatNode> visited = new HashSet<FlatNode>();
 911                                 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 912                                 flatNodesToVisit.add(callerFM);
 913
 914                                 while (!flatNodesToVisit.isEmpty()) {
 915                                         FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 916                                         flatNodesToVisit.remove(fn);
 917
 918                                         analyzeRelatedAllocationSite_NodeAction(fn, mc, calleeMC,
 919                                                         paramIndexSet,visitedHRN);
 920
 921                                         flatNodesToVisit.remove(fn);
 922                                         visited.add(fn);
 923
 924                                         for (int i = 0; i < fn.numNext(); i++) {
 925                                                 FlatNode nn = fn.getNext(i);
 926                                                 if (!visited.contains(nn)) {
 927                                                         flatNodesToVisit.add(nn);
 928                                                 }
 929                                         }
 930                                 }
 931                         }
 932                 }
 933
 934         }
 935
 936         private void analyzeRelatedAllocationSite_NodeAction(FlatNode fn, MethodContext callerMC,
 937  MethodContext calleeMC,
 938                         HashSet<Integer> paramIndexSet, HashSet<HeapRegionNode> visitedHRN) {
 939
 940                 OwnershipGraph og = ownAnalysis
 941                                 .getOwnvershipGraphByMethodContext(callerMC);
 942
 943                 switch (fn.kind()) {
 944
 945                 case FKind.FlatCall: {
 946
 947                         FlatCall fc = (FlatCall) fn;
 948
 949                         if(fc.numArgs()>0){
 950                                 MethodContext calleeMCfromOG = ownAnalysis.getCalleeMethodContext(
 951                                                 callerMC, fc);
 952
 953                                 // disable below condition. currently collect all possible
 954                                 // allocation sites without regarding method context
 955
 956                                 // if (calleeMC.equals(calleeMCfromOG)) { // in this case, this
 957                                 // method context calls corresponding callee.
 958
 959                                 int base;
 960                                 if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
 961                                         base = 0;
 962                                 } else {
 963                                         base = 1;
 964                                 }
 965
 966                                 for (Iterator iterator = paramIndexSet.iterator(); iterator
 967                                                 .hasNext();) {
 968                                         Integer integer = (Integer) iterator.next();
 969
 970                                         int paramIdx = integer - base;
 971                                         if (paramIdx >= 0) {
 972                                                 // if paramIdx is less than 0, assumes that it is
 973                                                 // related with wrong method contexts.
 974                                                 TempDescriptor arg = fc.getArg(paramIdx);
 975                                                 LabelNode argLN = og.td2ln.get(arg);
 976                                                 if (argLN != null) {
 977                                                         Iterator<ReferenceEdge> iterEdge = argLN
 978                                                                         .iteratorToReferencees();
 979                                                         while (iterEdge.hasNext()) {
 980                                                                 ReferenceEdge referenceEdge = (ReferenceEdge) iterEdge
 981                                                                                 .next();
 982
 983                                                                 HeapRegionNode dstHRN = referenceEdge.getDst();
 984                                                                 if (dstHRN.isParameter()) {
 985                                                                         if (!visitedHRN.contains(dstHRN)) {
 986                                                                                 setupRelatedAllocSiteAnalysis(og, callerMC,
 987                                                                                                 dstHRN, visitedHRN);
 988                                                                         }
 989                                                                 } else {
 990                                                                         addLiveInAllocationSite(callerMC, dstHRN
 991                                                                                         .getAllocationSite());
 992                                                                 }
 993                                                         }
 994                                                 }
 995                                         }
 996                                 }
 997                         }
 998
 999
1000                         // }
1001
1002                 }
1003                         break;
1004
1005                 }
1006         }
1007
1008         private void setupRelatedAllocSiteAnalysis(OwnershipGraph og,
1009                         MethodContext mc, HeapRegionNode dstHRN,
1010                         HashSet<HeapRegionNode> visitedHRN) {
1011
1012                 HashSet<Integer> paramIndexSet = new HashSet<Integer>();
1013
1014                 // collect corresponding param index
1015                 Set<Integer> pIndexSet = og.idPrimary2paramIndexSet.get(dstHRN.getID());
1016                 if (pIndexSet != null) {
1017                         for (Iterator iterator = pIndexSet.iterator(); iterator.hasNext();) {
1018                                 Integer integer = (Integer) iterator.next();
1019                                 paramIndexSet.add(integer);
1020                         }
1021                 }
1022
1023                 Set<Integer> sIndexSet = og.idSecondary2paramIndexSet.get(dstHRN
1024                                 .getID());
1025                 if (sIndexSet != null) {
1026                         for (Iterator iterator = sIndexSet.iterator(); iterator.hasNext();) {
1027                                 Integer integer = (Integer) iterator.next();
1028                                 paramIndexSet.add(integer);
1029                         }
1030                 }
1031
1032                 if (mc.getDescriptor() instanceof MethodDescriptor) {
1033                         Set callerSet = callGraph.getCallerSet((MethodDescriptor) mc
1034                                         .getDescriptor());
1035                         for (Iterator iterator = callerSet.iterator(); iterator.hasNext();) {
1036                                 Object obj = (Object) iterator.next();
1037                                 if (obj instanceof MethodDescriptor) {
1038                                         MethodDescriptor callerMD = (MethodDescriptor) obj;
1039
1040                                         analyzeRelatedAllocationSite(callerMD, mc, paramIndexSet,visitedHRN);
1041
1042                                 }
1043                         }
1044                 }
1045         }
1046
1047         private void effects_nodeActions(MethodContext mc, FlatNode fn,
1048                         FlatSESEEnterNode currentSESE, CallGraph callGraph) {
1049
1050                 OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc);
1051
1052                 switch (fn.kind()) {
1053
1054                 case FKind.FlatSESEEnterNode: {
1055
1056                         FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
1057                         assert fsen.equals(currentSESE);
1058
1059                         // uniquely taint each live-in variable
1060                         Set<TempDescriptor> set = fsen.getInVarSet();
1061                         Iterator<TempDescriptor> iter = set.iterator();
1062                         int idx = 0;
1063                         while (iter.hasNext()) {
1064                                 TempDescriptor td = iter.next();
1065                                 LabelNode ln = og.td2ln.get(td);
1066                                 if (ln != null) {
1067                                         int taint = (int) Math.pow(2, idx);
1068                                         taintLabelNode(ln, taint);
1069
1070                                         // collects related allocation sites
1071                                         Iterator<ReferenceEdge> referenceeIter = ln
1072                                                         .iteratorToReferencees();
1073                                         while (referenceeIter.hasNext()) {
1074                                                 ReferenceEdge referenceEdge = (ReferenceEdge) referenceeIter
1075                                                                 .next();
1076                                                 HeapRegionNode dstHRN = referenceEdge.getDst();
1077                                                 if (dstHRN.isParameter()) {
1078
1079                                                         HashSet<HeapRegionNode> visitedHRN=new HashSet<HeapRegionNode>();
1080                                                         visitedHRN.add(dstHRN);
1081                                                         setupRelatedAllocSiteAnalysis(og,mc,dstHRN,visitedHRN);
1082
1083                                                 } else {
1084                                                         addLiveInAllocationSite(mc, dstHRN
1085                                                                         .getAllocationSite());
1086                                                 }
1087                                         }
1088
1089                                 }
1090
1091                                 idx++;
1092                         }
1093
1094                 }
1095                         break;
1096
1097                 case FKind.FlatSESEExitNode: {
1098                         FlatSESEExitNode fsexit = (FlatSESEExitNode) fn;
1099
1100                         FlatSESEEnterNode enterNode = fsexit.getFlatEnter();
1101                         FlatSESEEnterNode parent = enterNode.getParent();
1102                         if (parent != null) {
1103
1104                                 SESEEffectsSet set = enterNode.getSeseEffectsSet();
1105                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> readTable = set
1106                                                 .getReadTable();
1107                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentReadTable = parent
1108                                                 .getSeseEffectsSet().getReadTable();
1109                                 Set<TempDescriptor> keys = readTable.keySet();
1110                                 Iterator<TempDescriptor> keyIter = keys.iterator();
1111                                 while (keyIter.hasNext()) {
1112                                         TempDescriptor td = (TempDescriptor) keyIter.next();
1113                                         HashSet<SESEEffectsKey> effectsSet = readTable.get(td);
1114                                         HashSet<SESEEffectsKey> parentEffectsSet = parentReadTable
1115                                                         .get(td);
1116                                         if (parentEffectsSet == null) {
1117                                                 parentEffectsSet = new HashSet<SESEEffectsKey>();
1118                                         }
1119
1120                                         for (Iterator iterator = effectsSet.iterator(); iterator
1121                                                         .hasNext();) {
1122                                                 SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1123                                                                 .next();
1124                                                 parentEffectsSet.add(new SESEEffectsKey(seseKey
1125                                                                 .getFieldDescriptor(), seseKey
1126                                                                 .getTypeDescriptor(), seseKey.getHRNId()));
1127                                         }
1128
1129                                         parentReadTable.put(td, parentEffectsSet);
1130                                 }
1131
1132                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> writeTable = set
1133                                                 .getWriteTable();
1134                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentWriteTable = parent
1135                                                 .getSeseEffectsSet().getWriteTable();
1136                                 keys = writeTable.keySet();
1137                                 keyIter = keys.iterator();
1138                                 while (keyIter.hasNext()) {
1139                                         TempDescriptor td = (TempDescriptor) keyIter.next();
1140                                         HashSet<SESEEffectsKey> effectsSet = writeTable.get(td);
1141                                         HashSet<SESEEffectsKey> parentEffectsSet = parentWriteTable
1142                                                         .get(td);
1143                                         if (parentEffectsSet == null) {
1144                                                 parentEffectsSet = new HashSet<SESEEffectsKey>();
1145                                         }
1146
1147                                         for (Iterator iterator = effectsSet.iterator(); iterator
1148                                                         .hasNext();) {
1149                                                 SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1150                                                                 .next();
1151                                                 parentEffectsSet.add(new SESEEffectsKey(seseKey
1152                                                                 .getFieldDescriptor(), seseKey
1153                                                                 .getTypeDescriptor(), seseKey.getHRNId()));
1154                                         }
1155
1156                                         parentWriteTable.put(td, parentEffectsSet);
1157                                 }
1158
1159                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> strongUpdateTable = set
1160                                                 .getStrongUpdateTable();
1161                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentstrongUpdateTable = parent
1162                                                 .getSeseEffectsSet().getStrongUpdateTable();
1163                                 keys = strongUpdateTable.keySet();
1164                                 keyIter = keys.iterator();
1165                                 while (keyIter.hasNext()) {
1166                                         TempDescriptor td = (TempDescriptor) keyIter.next();
1167                                         HashSet<SESEEffectsKey> effectsSet = strongUpdateTable
1168                                                         .get(td);
1169                                         HashSet<SESEEffectsKey> parentEffectsSet = parentstrongUpdateTable
1170                                                         .get(td);
1171                                         if (parentEffectsSet == null) {
1172                                                 parentEffectsSet = new HashSet<SESEEffectsKey>();
1173                                         }
1174
1175                                         for (Iterator iterator = effectsSet.iterator(); iterator
1176                                                         .hasNext();) {
1177                                                 SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1178                                                                 .next();
1179                                                 parentEffectsSet.add(new SESEEffectsKey(seseKey
1180                                                                 .getFieldDescriptor(), seseKey
1181                                                                 .getTypeDescriptor(), seseKey.getHRNId()));
1182                                         }
1183
1184                                         parentstrongUpdateTable.put(td, parentEffectsSet);
1185                                 }
1186
1187                         }
1188
1189                 }
1190                         break;
1191
1192                 case FKind.FlatFieldNode: {
1193
1194                         FlatFieldNode ffn = (FlatFieldNode) fn;
1195                         TempDescriptor src = ffn.getSrc();
1196                         FieldDescriptor field = ffn.getField();
1197
1198                         LabelNode srcLN = og.td2ln.get(src);
1199                         if (srcLN != null) {
1200                                 HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(srcLN);
1201                                 Iterator<TempDescriptor> affectedIter = affectedTDSet
1202                                                 .iterator();
1203                                 while (affectedIter.hasNext()) {
1204                                         TempDescriptor affectedTD = affectedIter.next();
1205
1206                                         if (currentSESE.getInVarSet().contains(affectedTD)) {
1207
1208                                                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
1209                                                                 og, affectedTD);
1210                                                 Iterator<HeapRegionNode> hrnIter = hrnSet.iterator();
1211                                                 while (hrnIter.hasNext()) {
1212                                                         HeapRegionNode hrn = hrnIter.next();
1213
1214                                                         Iterator<ReferenceEdge> referencers = hrn
1215                                                                         .iteratorToReferencers();
1216                                                         while (referencers.hasNext()) {
1217                                                                 ReferenceEdge referenceEdge = (ReferenceEdge) referencers
1218                                                                                 .next();
1219                                                                 if (field.getSymbol().equals(
1220                                                                                 referenceEdge.getField())) {
1221                                                                         currentSESE.readEffects(affectedTD, field
1222                                                                                         .getSymbol(), src.getType(),
1223                                                                                         referenceEdge.getDst().getID());
1224                                                                 }
1225                                                         }
1226
1227                                                 }
1228                                         }
1229                                 }
1230
1231                                 // handle tainted case
1232
1233                                 Iterator<ReferenceEdge> edgeIter = srcLN
1234                                                 .iteratorToReferencees();
1235                                 while (edgeIter.hasNext()) {
1236                                         ReferenceEdge edge = edgeIter.next();
1237                                         HeapRegionNode accessHRN = edge.getDst();
1238                                         // / follow the chain of reference to identify possible
1239                                         // accesses
1240                                         Iterator<ReferenceEdge> referIter = accessHRN
1241                                                         .iteratorToReferencers();
1242                                         while (referIter.hasNext()) {
1243                                                 ReferenceEdge referEdge = (ReferenceEdge) referIter
1244                                                                 .next();
1245
1246                                                 // if (referEdge.getTaintIdentifier() >0 ||
1247                                                 // referEdge.getSESETaintIdentifier()>0 ) {
1248                                                 HashSet<TempDescriptor> referSet = new HashSet<TempDescriptor>();
1249                                                 followReference(accessHRN, referSet,
1250                                                                 new HashSet<HeapRegionNode>(), currentSESE);
1251
1252                                                 Iterator<TempDescriptor> referSetIter = referSet
1253                                                                 .iterator();
1254                                                 while (referSetIter.hasNext()) {
1255                                                         TempDescriptor tempDescriptor = (TempDescriptor) referSetIter
1256                                                                         .next();
1257                                                         currentSESE.readEffects(tempDescriptor, field
1258                                                                         .getSymbol(), src.getType(), accessHRN
1259                                                                         .getID());
1260                                                 }
1261                                                 // }
1262                                         }
1263                                         // /
1264                                         if (edge.getTaintIdentifier() > 0
1265                                                         || edge.getSESETaintIdentifier() > 0) {
1266
1267                                                 affectedTDSet = getReferenceNodeSet(accessHRN);
1268                                                 affectedIter = affectedTDSet.iterator();
1269                                                 while (affectedIter.hasNext()) {
1270                                                         TempDescriptor affectedTD = affectedIter.next();
1271
1272                                                         if (currentSESE.getInVarSet().contains(affectedTD)) {
1273
1274                                                                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
1275                                                                                 og, affectedTD);
1276                                                                 Iterator<HeapRegionNode> hrnIter = hrnSet
1277                                                                                 .iterator();
1278                                                                 while (hrnIter.hasNext()) {
1279                                                                         HeapRegionNode hrn = hrnIter.next();
1280                                                                         currentSESE.readEffects(affectedTD, field
1281                                                                                         .getSymbol(), src.getType(), hrn
1282                                                                                         .getID());
1283                                                                 }
1284
1285                                                         }
1286
1287                                                 }
1288                                         }
1289                                 }
1290                         }
1291
1292                 }
1293                         break;
1294
1295                 case FKind.FlatSetFieldNode: {
1296
1297                         FlatSetFieldNode fsen = (FlatSetFieldNode) fn;
1298                         TempDescriptor dst = fsen.getDst();
1299                         FieldDescriptor field = fsen.getField();
1300
1301                         LabelNode dstLN = og.td2ln.get(dst);
1302                         if (dstLN != null) {
1303                                 // check possible strong updates
1304                                 boolean strongUpdate = false;
1305
1306                                 if (!field.getType().isImmutable() || field.getType().isArray()) {
1307                                         Iterator<ReferenceEdge> itrXhrn = dstLN
1308                                                         .iteratorToReferencees();
1309                                         while (itrXhrn.hasNext()) {
1310                                                 ReferenceEdge edgeX = itrXhrn.next();
1311                                                 HeapRegionNode hrnX = edgeX.getDst();
1312
1313                                                 // we can do a strong update here if one of two cases
1314                                                 // holds
1315                                                 if (field != null
1316                                                                 && field != OwnershipAnalysis
1317                                                                                 .getArrayField(field.getType())
1318                                                                 && ((hrnX.getNumReferencers() == 1) || // case 1
1319                                                                 (hrnX.isSingleObject() && dstLN
1320                                                                                 .getNumReferencees() == 1) // case 2
1321                                                                 )) {
1322                                                         strongUpdate = true;
1323                                                 }
1324                                         }
1325                                 }
1326
1327                                 HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(dstLN);
1328
1329                                 Iterator<TempDescriptor> affectedIter = affectedTDSet
1330                                                 .iterator();
1331
1332                                 while (affectedIter.hasNext()) {
1333                                         TempDescriptor affectedTD = affectedIter.next();
1334                                         if (currentSESE.getInVarSet().contains(affectedTD)) {
1335
1336                                                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
1337                                                                 og, affectedTD);
1338                                                 Iterator<HeapRegionNode> hrnIter = hrnSet.iterator();
1339                                                 while (hrnIter.hasNext()) {
1340                                                         HeapRegionNode hrn = hrnIter.next();
1341
1342                                                         Iterator<ReferenceEdge> referencers = hrn
1343                                                                         .iteratorToReferencers();
1344                                                         while (referencers.hasNext()) {
1345                                                                 ReferenceEdge referenceEdge = (ReferenceEdge) referencers
1346                                                                                 .next();
1347                                                                 if (field.getSymbol().equals(
1348                                                                                 referenceEdge.getField())) {
1349                                                                         currentSESE.writeEffects(affectedTD, field
1350                                                                                         .getSymbol(), dst.getType(),
1351                                                                                         referenceEdge.getDst().getID(),
1352                                                                                         strongUpdate);
1353                                                                 }
1354                                                         }
1355
1356                                                 }
1357                                         }
1358                                 }
1359
1360                                 // handle tainted case
1361                                 Iterator<ReferenceEdge> edgeIter = dstLN
1362                                                 .iteratorToReferencees();
1363                                 while (edgeIter.hasNext()) {
1364                                         ReferenceEdge edge = edgeIter.next();
1365
1366                                         HeapRegionNode accessHRN = edge.getDst();
1367                                         // / follow the chain of reference to identify possible
1368                                         // accesses
1369                                         Iterator<ReferenceEdge> referIter = accessHRN
1370                                                         .iteratorToReferencers();
1371                                         while (referIter.hasNext()) {
1372                                                 ReferenceEdge referEdge = (ReferenceEdge) referIter
1373                                                                 .next();
1374
1375                                                 // if (referEdge.getTaintIdentifier() > 0 ||
1376                                                 // referEdge.getSESETaintIdentifier() > 0 ) {
1377                                                 HashSet<TempDescriptor> referSet = new HashSet<TempDescriptor>();
1378                                                 followReference(accessHRN, referSet,
1379                                                                 new HashSet<HeapRegionNode>(), currentSESE);
1380                                                 Iterator<TempDescriptor> referSetIter = referSet
1381                                                                 .iterator();
1382                                                 while (referSetIter.hasNext()) {
1383                                                         TempDescriptor tempDescriptor = (TempDescriptor) referSetIter
1384                                                                         .next();
1385                                                         currentSESE.writeEffects(tempDescriptor, field
1386                                                                         .getSymbol(), dst.getType(), accessHRN
1387                                                                         .getID(), strongUpdate);
1388                                                 }
1389                                                 // }
1390                                         }
1391                                         // /
1392                                         if (edge.getTaintIdentifier() > 0
1393                                                         || edge.getSESETaintIdentifier() > 0) {
1394                                                 affectedTDSet = getReferenceNodeSet(accessHRN);
1395                                                 affectedIter = affectedTDSet.iterator();
1396                                                 while (affectedIter.hasNext()) {
1397                                                         TempDescriptor affectedTD = affectedIter.next();
1398                                                         if (currentSESE.getInVarSet().contains(affectedTD)) {
1399
1400                                                                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
1401                                                                                 og, affectedTD);
1402                                                                 Iterator<HeapRegionNode> hrnIter = hrnSet
1403                                                                                 .iterator();
1404                                                                 while (hrnIter.hasNext()) {
1405                                                                         HeapRegionNode hrn = hrnIter.next();
1406                                                                         currentSESE.writeEffects(affectedTD, field
1407                                                                                         .getSymbol(), dst.getType(), hrn
1408                                                                                         .getID(), strongUpdate);
1409
1410                                                                 }
1411
1412                                                         }
1413
1414                                                 }
1415                                         }
1416                                 }
1417
1418                         }
1419
1420                 }
1421                         break;
1422
1423                 case FKind.FlatCall: {
1424                         FlatCall fc = (FlatCall) fn;
1425
1426                         MethodContext calleeMC = ownAnalysis.getCalleeMethodContext(mc, fc);
1427
1428                         MethodEffects me = ownAnalysis.getMethodEffectsAnalysis()
1429                                         .getMethodEffectsByMethodContext(calleeMC);
1430
1431                         OwnershipGraph calleeOG = ownAnalysis
1432                                         .getOwnvershipGraphByMethodContext(calleeMC);
1433
1434                         FlatMethod fm = state.getMethodFlat(fc.getMethod());
1435                         ParameterDecomposition decomp = new ParameterDecomposition(
1436                                         ownAnalysis, fc, fm, calleeMC, calleeOG, og);
1437
1438                         int base;
1439                         if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
1440                                 base = 0;
1441                         } else {
1442                                 base = 1;
1443                         }
1444
1445                         for (int i = 0; i < fc.numArgs(); i++) {
1446
1447                                 TempDescriptor arg = fc.getArg(i);
1448                                 Set<EffectsKey> readSet = me.getEffects().getReadingSet(
1449                                                 i + base);
1450                                 Set<EffectsKey> writeSet = me.getEffects().getWritingSet(
1451                                                 i + base);
1452
1453                                 Set<EffectsKey> strongUpdateSet = me.getEffects()
1454                                                 .getStrongUpdateSet(i + base);
1455
1456                                 LabelNode argLN = og.td2ln.get(arg);
1457                                 if (argLN != null) {
1458                                         HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(argLN);
1459                                         Iterator<TempDescriptor> affectedIter = affectedTDSet
1460                                                         .iterator();
1461
1462                                         while (affectedIter.hasNext()) {
1463
1464                                                 TempDescriptor affectedTD = affectedIter.next();
1465                                                 if (currentSESE.getInVarSet().contains(affectedTD)) {
1466
1467                                                         if (readSet != null) {
1468                                                                 Iterator<EffectsKey> readIter = readSet
1469                                                                                 .iterator();
1470                                                                 while (readIter.hasNext()) {
1471                                                                         EffectsKey key = readIter.next();
1472                                                                         Set<Integer> hrnSet = getCallerHRNId(
1473                                                                                         new Integer(i + base), calleeOG,
1474                                                                                         key.getHRNId(), decomp);
1475                                                                         Iterator<Integer> hrnIter = hrnSet
1476                                                                                         .iterator();
1477                                                                         while (hrnIter.hasNext()) {
1478                                                                                 Integer hrnID = (Integer) hrnIter
1479                                                                                                 .next();
1480                                                                                 currentSESE.readEffects(affectedTD, key
1481                                                                                                 .getFieldDescriptor(), key
1482                                                                                                 .getTypeDescriptor(), hrnID);
1483                                                                         }
1484                                                                 }
1485                                                         }
1486
1487                                                         if (writeSet != null) {
1488                                                                 Iterator<EffectsKey> writeIter = writeSet
1489                                                                                 .iterator();
1490                                                                 while (writeIter.hasNext()) {
1491                                                                         EffectsKey key = writeIter.next();
1492
1493                                                                         Set<Integer> hrnSet = getCallerHRNId(
1494                                                                                         new Integer(i + base), calleeOG,
1495                                                                                         key.getHRNId(), decomp);
1496                                                                         Iterator<Integer> hrnIter = hrnSet
1497                                                                                         .iterator();
1498                                                                         while (hrnIter.hasNext()) {
1499                                                                                 Integer hrnID = (Integer) hrnIter
1500                                                                                                 .next();
1501                                                                                 currentSESE.writeEffects(affectedTD,
1502                                                                                                 key.getFieldDescriptor(), key
1503                                                                                                                 .getTypeDescriptor(),
1504                                                                                                 hrnID, false);
1505                                                                         }
1506
1507                                                                 }
1508                                                         }
1509
1510                                                         if (strongUpdateSet != null) {
1511                                                                 Iterator<EffectsKey> strongUpdateIter = strongUpdateSet
1512                                                                                 .iterator();
1513                                                                 while (strongUpdateIter.hasNext()) {
1514                                                                         EffectsKey key = strongUpdateIter.next();
1515
1516                                                                         Set<Integer> hrnSet = getCallerHRNId(
1517                                                                                         new Integer(i + base), calleeOG,
1518                                                                                         key.getHRNId(), decomp);
1519                                                                         Iterator<Integer> hrnIter = hrnSet
1520                                                                                         .iterator();
1521                                                                         while (hrnIter.hasNext()) {
1522                                                                                 Integer hrnID = (Integer) hrnIter
1523                                                                                                 .next();
1524                                                                                 currentSESE.writeEffects(affectedTD,
1525                                                                                                 key.getFieldDescriptor(), key
1526                                                                                                                 .getTypeDescriptor(),
1527                                                                                                 hrnID, true);
1528                                                                         }
1529
1530                                                                 }
1531                                                         }
1532
1533                                                 }
1534
1535                                         }
1536
1537                                 }
1538
1539                         }
1540
1541                 }
1542                         break;
1543
1544                 }
1545         }
1546
1547         private void addLiveInAllocationSite(MethodContext mc, AllocationSite ac){
1548                 HashSet<AllocationSite> set=mapMethodContextToLiveInAllocationSiteSet.get(mc);
1549                 if(set==null){
1550                         set=new HashSet<AllocationSite>();
1551                 }
1552                 set.add(ac);
1553                 mapMethodContextToLiveInAllocationSiteSet.put(mc, set);
1554         }
1555
1556         private void followReference(HeapRegionNode hrn,HashSet<TempDescriptor> tdSet, HashSet<HeapRegionNode> visited, FlatSESEEnterNode currentSESE){
1557
1558                 Iterator<ReferenceEdge> referIter=hrn.iteratorToReferencers();
1559                 // check whether hrn is referenced by TD
1560                 while (referIter.hasNext()) {
1561                         ReferenceEdge referEdge = (ReferenceEdge) referIter.next();
1562                         if(referEdge.getSrc() instanceof LabelNode){
1563                                 LabelNode ln=(LabelNode)referEdge.getSrc();
1564                                 if(currentSESE.getInVarSet().contains(ln.getTempDescriptor())){
1565                                         tdSet.add(ln.getTempDescriptor());
1566                                 }
1567                         }else if(referEdge.getSrc() instanceof HeapRegionNode){
1568                                 HeapRegionNode nextHRN=(HeapRegionNode)referEdge.getSrc();
1569                                 if(!visited.contains(nextHRN)){
1570                                         visited.add(nextHRN);
1571                                         followReference(nextHRN,tdSet,visited,currentSESE);
1572                                 }
1573
1574                         }
1575                 }
1576
1577         }
1578
1579         private Set<Integer> getCallerHRNId(Integer paramIdx,
1580                         OwnershipGraph calleeOG, Integer calleeHRNId,
1581                         ParameterDecomposition paramDecom) {
1582
1583                 Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx);
1584                 Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx);
1585
1586                 if (calleeHRNId.equals(hrnPrimaryID)) {
1587                         // it references to primary param heap region
1588                         return paramDecom.getParamObject_hrnIDs(paramIdx);
1589                 } else if (calleeHRNId.equals(hrnSecondaryID)) {
1590                         // it references to secondary param heap region
1591                         return paramDecom.getParamReachable_hrnIDs(paramIdx);
1592                 }
1593
1594                 return new HashSet<Integer>();
1595         }
1596
1597         private void taintLabelNode(LabelNode ln, int identifier) {
1598
1599                 Iterator<ReferenceEdge> edgeIter = ln.iteratorToReferencees();
1600                 while (edgeIter.hasNext()) {
1601                         ReferenceEdge edge = edgeIter.next();
1602                         HeapRegionNode hrn = edge.getDst();
1603
1604                         Iterator<ReferenceEdge> edgeReferencerIter = hrn
1605                                         .iteratorToReferencers();
1606                         while (edgeReferencerIter.hasNext()) {
1607                                 ReferenceEdge referencerEdge = edgeReferencerIter.next();
1608                                 OwnershipNode node = referencerEdge.getSrc();
1609                                 if (node instanceof LabelNode) {
1610                                         referencerEdge.unionSESETaintIdentifier(identifier);
1611                                 }else if(node instanceof HeapRegionNode){
1612                                         referencerEdge.unionSESETaintIdentifier(identifier);
1613                                 }
1614                         }
1615
1616                 }
1617
1618         }
1619
1620         private HashSet<TempDescriptor> getReferenceNodeSet(HeapRegionNode hrn){
1621
1622                 HashSet<TempDescriptor> returnSet=new HashSet<TempDescriptor>();
1623
1624                 Iterator<ReferenceEdge> edgeIter=hrn.iteratorToReferencers();
1625                 while(edgeIter.hasNext()){
1626                         ReferenceEdge edge=edgeIter.next();
1627                         if(edge.getSrc() instanceof LabelNode){
1628                                 LabelNode ln=(LabelNode)edge.getSrc();
1629                                 returnSet.add(ln.getTempDescriptor());
1630                         }
1631                 }
1632
1633                 return returnSet;
1634
1635         }
1636
1637
1638         private HashSet<HeapRegionNode> getReferenceHeapIDSet(OwnershipGraph og, TempDescriptor td){
1639
1640                 HashSet<HeapRegionNode> returnSet=new HashSet<HeapRegionNode>();
1641
1642                 LabelNode ln=og.td2ln.get(td);
1643                 Iterator<ReferenceEdge> edgeIter=ln.iteratorToReferencees();
1644                 while(edgeIter.hasNext()){
1645                         ReferenceEdge edge=edgeIter.next();
1646                                 HeapRegionNode hrn=edge.getDst();
1647                                 returnSet.add(hrn);
1648                 }
1649                 return returnSet;
1650         }
1651
1652
1653         private HashSet<TempDescriptor> getAccessedTaintNodeSet(LabelNode ln) {
1654
1655                 HashSet<TempDescriptor> returnSet = new HashSet<TempDescriptor>();
1656
1657                 Iterator<ReferenceEdge> edgeIter = ln.iteratorToReferencees();
1658                 while (edgeIter.hasNext()) {
1659                         ReferenceEdge edge = edgeIter.next();
1660                         HeapRegionNode hrn = edge.getDst();
1661
1662                         Iterator<ReferenceEdge> edgeReferencerIter = hrn
1663                                         .iteratorToReferencers();
1664                         while (edgeReferencerIter.hasNext()) {
1665                                 ReferenceEdge referencerEdge = edgeReferencerIter.next();
1666
1667                                 if (referencerEdge.getSrc() instanceof LabelNode) {
1668                                         if (!((LabelNode) referencerEdge.getSrc()).equals(ln)) {
1669
1670                                                 if (referencerEdge.getSESETaintIdentifier() > 0) {
1671                                                         TempDescriptor td = ((LabelNode) referencerEdge
1672                                                                         .getSrc()).getTempDescriptor();
1673                                                         returnSet.add(td);
1674                                                 }
1675                                         }
1676                                 }
1677                         }
1678
1679                 }
1680
1681                 return returnSet;
1682
1683         }
1684
1685
1686   private void codePlansForward( FlatMethod fm ) {
1687
1688     // start from flat method top, visit every node in
1689     // method exactly once
1690     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1691     flatNodesToVisit.add( fm );
1692
1693     Set<FlatNode> visited = new HashSet<FlatNode>();
1694
1695     while( !flatNodesToVisit.isEmpty() ) {
1696       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
1697       FlatNode fn = fnItr.next();
1698
1699       flatNodesToVisit.remove( fn );
1700       visited.add( fn );
1701
1702       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
1703       assert seseStack != null;
1704
1705       // use incoming results as "dot statement" or just
1706       // before the current statement
1707       VarSrcTokTable dotSTtable = new VarSrcTokTable();
1708       for( int i = 0; i < fn.numPrev(); i++ ) {
1709         FlatNode nn = fn.getPrev( i );
1710         dotSTtable.merge( variableResults.get( nn ) );
1711       }
1712
1713       // find dt-st notAvailableSet also
1714       Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
1715       for( int i = 0; i < fn.numPrev(); i++ ) {
1716         FlatNode nn = fn.getPrev( i );
1717         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
1718         if( notAvailIn != null ) {
1719           dotSTnotAvailSet.addAll( notAvailIn );
1720         }
1721       }
1722
1723       Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
1724
1725       if( !seseStack.empty() ) {
1726         codePlans_nodeActions( fn,
1727                                dotSTlive,
1728                                dotSTtable,
1729                                dotSTnotAvailSet,
1730                                seseStack.peek()
1731                                );
1732       }
1733
1734       for( int i = 0; i < fn.numNext(); i++ ) {
1735         FlatNode nn = fn.getNext( i );
1736
1737         if( !visited.contains( nn ) ) {
1738           flatNodesToVisit.add( nn );
1739         }
1740       }
1741     }
1742   }
1743
1744   private void codePlans_nodeActions( FlatNode fn,
1745                                       Set<TempDescriptor> liveSetIn,
1746                                       VarSrcTokTable vstTableIn,
1747                                       Set<TempDescriptor> notAvailSetIn,
1748                                       FlatSESEEnterNode currentSESE ) {
1749
1750     CodePlan plan = new CodePlan( currentSESE);
1751
1752     switch( fn.kind() ) {
1753
1754     case FKind.FlatSESEEnterNode: {
1755       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
1756
1757       // track the source types of the in-var set so generated
1758       // code at this SESE issue can compute the number of
1759       // dependencies properly
1760       Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
1761       while( inVarItr.hasNext() ) {
1762         TempDescriptor inVar = inVarItr.next();
1763         Integer srcType =
1764           vstTableIn.getRefVarSrcType( inVar,
1765                                        fsen,
1766                                        fsen.getParent() );
1767
1768         // the current SESE needs a local space to track the dynamic
1769         // variable and the child needs space in its SESE record
1770         if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1771           fsen.addDynamicInVar( inVar );
1772           fsen.getParent().addDynamicVar( inVar );
1773
1774         } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1775           fsen.addStaticInVar( inVar );
1776           VariableSourceToken vst = vstTableIn.get( inVar ).iterator().next();
1777           fsen.putStaticInVar2src( inVar, vst );
1778           fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
1779                                                       vst.getAge()
1780                                                     )
1781                                 );
1782
1783         } else {
1784           assert srcType.equals( VarSrcTokTable.SrcType_READY );
1785           fsen.addReadyInVar( inVar );
1786         }
1787       }
1788
1789     } break;
1790
1791     case FKind.FlatSESEExitNode: {
1792       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
1793     } break;
1794
1795     case FKind.FlatOpNode: {
1796       FlatOpNode fon = (FlatOpNode) fn;
1797
1798       if( fon.getOp().getOp() == Operation.ASSIGN ) {
1799         TempDescriptor lhs = fon.getDest();
1800         TempDescriptor rhs = fon.getLeft();
1801
1802         // if this is an op node, don't stall, copy
1803         // source and delay until we need to use value
1804
1805         // ask whether lhs and rhs sources are dynamic, static, etc.
1806         Integer lhsSrcType
1807           = vstTableIn.getRefVarSrcType( lhs,
1808                                          currentSESE,
1809                                          currentSESE.getParent() );
1810
1811         Integer rhsSrcType
1812           = vstTableIn.getRefVarSrcType( rhs,
1813                                          currentSESE,
1814                                          currentSESE.getParent() );
1815
1816         if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1817           // if rhs is dynamic going in, lhs will definitely be dynamic
1818           // going out of this node, so track that here
1819           plan.addDynAssign( lhs, rhs );
1820           currentSESE.addDynamicVar( lhs );
1821           currentSESE.addDynamicVar( rhs );
1822
1823         } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1824           // otherwise, if the lhs is dynamic, but the rhs is not, we
1825           // need to update the variable's dynamic source as "current SESE"
1826           plan.addDynAssign( lhs );
1827         }
1828
1829         // only break if this is an ASSIGN op node,
1830         // otherwise fall through to default case
1831         break;
1832       }
1833     }
1834
1835     // note that FlatOpNode's that aren't ASSIGN
1836     // fall through to this default case
1837     default: {
1838
1839       // a node with no live set has nothing to stall for
1840       if( liveSetIn == null ) {
1841         break;
1842       }
1843
1844       TempDescriptor[] readarray = fn.readsTemps();
1845       for( int i = 0; i < readarray.length; i++ ) {
1846         TempDescriptor readtmp = readarray[i];
1847
1848         // ignore temps that are definitely available
1849         // when considering to stall on it
1850         if( !notAvailSetIn.contains( readtmp ) ) {
1851           continue;
1852         }
1853
1854         // check the source type of this variable
1855         Integer srcType
1856           = vstTableIn.getRefVarSrcType( readtmp,
1857                                          currentSESE,
1858                                          currentSESE.getParent() );
1859
1860         if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1861           // 1) It is not clear statically where this variable will
1862           // come from statically, so dynamically we must keep track
1863           // along various control paths, and therefore when we stall,
1864           // just stall for the exact thing we need and move on
1865           plan.addDynamicStall( readtmp );
1866           currentSESE.addDynamicVar( readtmp );
1867
1868         } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1869           // 2) Single token/age pair: Stall for token/age pair, and copy
1870           // all live variables with same token/age pair at the same
1871           // time.  This is the same stuff that the notavaialable analysis
1872           // marks as now available.
1873
1874           VariableSourceToken vst = vstTableIn.get( readtmp ).iterator().next();
1875
1876           Iterator<VariableSourceToken> availItr =
1877             vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
1878
1879           while( availItr.hasNext() ) {
1880             VariableSourceToken vstAlsoAvail = availItr.next();
1881
1882             // only grab additional stuff that is live
1883             Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
1884
1885             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
1886             while( refVarItr.hasNext() ) {
1887               TempDescriptor refVar = refVarItr.next();
1888               if( liveSetIn.contains( refVar ) ) {
1889                 copySet.add( refVar );
1890               }
1891             }
1892
1893             if( !copySet.isEmpty() ) {
1894               plan.addStall2CopySet( vstAlsoAvail, copySet );
1895             }
1896           }
1897
1898         } else {
1899           // the other case for srcs is READY, so do nothing
1900         }
1901
1902         // assert that everything being stalled for is in the
1903         // "not available" set coming into this flat node and
1904         // that every VST identified is in the possible "stall set"
1905         // that represents VST's from children SESE's
1906
1907       }
1908     } break;
1909
1910     } // end switch
1911
1912
1913     // identify sese-age pairs that are statically useful
1914     // and should have an associated SESE variable in code
1915     // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1916     // AND ALWAYS GIVE NAMES TO PARENTS
1917     Set<VariableSourceToken> staticSet = vstTableIn.get();
1918     Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1919     while( vstItr.hasNext() ) {
1920       VariableSourceToken vst = vstItr.next();
1921
1922       // placeholder source tokens are useful results, but
1923       // the placeholder static name is never needed
1924       if( vst.getSESE().getIsCallerSESEplaceholder() ) {
1925         continue;
1926       }
1927
1928       FlatSESEEnterNode sese = currentSESE;
1929       while( sese != null ) {
1930         sese.addNeededStaticName(
1931                                  new SESEandAgePair( vst.getSESE(), vst.getAge() )
1932                                   );
1933         sese.mustTrackAtLeastAge( vst.getAge() );
1934
1935         sese = sese.getParent();
1936       }
1937     }
1938
1939
1940     codePlans.put( fn, plan );
1941
1942
1943     // if any variables at this-node-*dot* have a static source (exactly one vst)
1944     // but go to a dynamic source at next-node-*dot*, create a new IR graph
1945     // node on that edge to track the sources dynamically
1946     VarSrcTokTable thisVstTable = variableResults.get( fn );
1947     for( int i = 0; i < fn.numNext(); i++ ) {
1948       FlatNode            nn           = fn.getNext( i );
1949       VarSrcTokTable      nextVstTable = variableResults.get( nn );
1950       Set<TempDescriptor> nextLiveIn   = livenessRootView.get( nn );
1951
1952       // the table can be null if it is one of the few IR nodes
1953       // completely outside of the root SESE scope
1954       if( nextVstTable != null && nextLiveIn != null ) {
1955
1956         Hashtable<TempDescriptor, VariableSourceToken> static2dynamicSet =
1957           thisVstTable.getStatic2DynamicSet( nextVstTable,
1958                                              nextLiveIn,
1959                                              currentSESE,
1960                                              currentSESE.getParent()
1961                                            );
1962
1963         if( !static2dynamicSet.isEmpty() ) {
1964
1965           // either add these results to partial fixed-point result
1966           // or make a new one if we haven't made any here yet
1967           FlatEdge fe = new FlatEdge( fn, nn );
1968           FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
1969
1970           if( fwdvn == null ) {
1971             fwdvn = new FlatWriteDynamicVarNode( fn,
1972                                                  nn,
1973                                                  static2dynamicSet,
1974                                                  currentSESE
1975                                                  );
1976             wdvNodesToSpliceIn.put( fe, fwdvn );
1977           } else {
1978             fwdvn.addMoreVar2Src( static2dynamicSet );
1979           }
1980         }
1981       }
1982     }
1983   }
1984
1985
1986   public void writeReports( String timeReport ) throws java.io.IOException {
1987
1988     BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
1989     bw.write( "MLP Analysis Results\n\n" );
1990     bw.write( timeReport+"\n\n" );
1991     printSESEHierarchy( bw );
1992     bw.write( "\n" );
1993     printSESEInfo( bw );
1994     bw.close();
1995
1996     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
1997     while( methItr.hasNext() ) {
1998       MethodDescriptor md = (MethodDescriptor) methItr.next();
1999       FlatMethod       fm = state.getMethodFlat( md );
2000       bw = new BufferedWriter( new FileWriter( "mlpReport_"+
2001                                                md.getClassMethodName()+
2002                                                md.getSafeMethodDescriptor()+
2003                                                ".txt" ) );
2004       bw.write( "MLP Results for "+md+"\n-------------------\n");
2005       bw.write( "\n\nLive-In, Root View\n------------------\n"          +fm.printMethod( livenessRootView ) );
2006       bw.write( "\n\nVariable Results-Out\n----------------\n"          +fm.printMethod( variableResults ) );
2007       bw.write( "\n\nNot Available Results-Out\n---------------------\n"+fm.printMethod( notAvailableResults ) );
2008       bw.write( "\n\nCode Plans\n----------\n"                          +fm.printMethod( codePlans ) );
2009       bw.write("\n\nSESE Effects\n----------------------\n"+printSESEEffects());
2010       bw.close();
2011     }
2012   }
2013
2014         private String printSESEEffects() {
2015
2016                 StringWriter writer = new StringWriter();
2017
2018                 Iterator<FlatSESEEnterNode> keyIter = allSESEs.iterator();
2019
2020                 while (keyIter.hasNext()) {
2021                         FlatSESEEnterNode seseEnter = keyIter.next();
2022                         String result = seseEnter.getSeseEffectsSet().printSet();
2023                         if (result.length() > 0) {
2024                                 writer.write("\nSESE " + seseEnter + "\n");
2025                                 writer.write(result);
2026                         }
2027                 }
2028                 keyIter = rootSESEs.iterator();
2029                 while (keyIter.hasNext()) {
2030                         FlatSESEEnterNode seseEnter = keyIter.next();
2031                         if (seseEnter.getIsCallerSESEplaceholder()) {
2032                                 if (!seseEnter.getChildren().isEmpty()) {
2033                                         String result = seseEnter.getSeseEffectsSet().printSet();
2034                                         if (result.length() > 0) {
2035                                                 writer.write("\nSESE " + seseEnter + "\n");
2036                                                 writer.write(result);
2037                                         }
2038                                 }
2039                         }
2040                 }
2041
2042                 return writer.toString();
2043
2044         }
2045
2046   private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
2047     bw.write( "SESE Hierarchy\n--------------\n" );
2048     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
2049     while( rootItr.hasNext() ) {
2050       FlatSESEEnterNode root = rootItr.next();
2051       if( root.getIsCallerSESEplaceholder() ) {
2052         if( !root.getChildren().isEmpty() ) {
2053           printSESEHierarchyTree( bw, root, 0 );
2054         }
2055       } else {
2056         printSESEHierarchyTree( bw, root, 0 );
2057       }
2058     }
2059   }
2060
2061   private void printSESEHierarchyTree( BufferedWriter bw,
2062                                        FlatSESEEnterNode fsen,
2063                                        int depth
2064                                      ) throws java.io.IOException {
2065     for( int i = 0; i < depth; ++i ) {
2066       bw.write( "  " );
2067     }
2068     bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
2069
2070     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
2071     while( childItr.hasNext() ) {
2072       FlatSESEEnterNode fsenChild = childItr.next();
2073       printSESEHierarchyTree( bw, fsenChild, depth + 1 );
2074     }
2075   }
2076
2077
2078   private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
2079     bw.write("\nSESE info\n-------------\n" );
2080     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
2081     while( rootItr.hasNext() ) {
2082       FlatSESEEnterNode root = rootItr.next();
2083       if( root.getIsCallerSESEplaceholder() ) {
2084         if( !root.getChildren().isEmpty() ) {
2085           printSESEInfoTree( bw, root );
2086         }
2087       } else {
2088         printSESEInfoTree( bw, root );
2089       }
2090     }
2091   }
2092
2093   private void printSESEInfoTree( BufferedWriter bw,
2094                                   FlatSESEEnterNode fsen
2095                                 ) throws java.io.IOException {
2096
2097     if( !fsen.getIsCallerSESEplaceholder() ) {
2098       bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
2099
2100       bw.write( "  in-set: "+fsen.getInVarSet()+"\n" );
2101       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
2102       while( tItr.hasNext() ) {
2103         TempDescriptor inVar = tItr.next();
2104         if( fsen.getReadyInVarSet().contains( inVar ) ) {
2105           bw.write( "    (ready)  "+inVar+"\n" );
2106         }
2107         if( fsen.getStaticInVarSet().contains( inVar ) ) {
2108           bw.write( "    (static) "+inVar+"\n" );
2109         }
2110         if( fsen.getDynamicInVarSet().contains( inVar ) ) {
2111           bw.write( "    (dynamic)"+inVar+"\n" );
2112         }
2113       }
2114
2115       bw.write( "  out-set: "+fsen.getOutVarSet()+"\n" );
2116       bw.write( "}\n" );
2117     }
2118
2119     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
2120     while( childItr.hasNext() ) {
2121       FlatSESEEnterNode fsenChild = childItr.next();
2122       printSESEInfoTree( bw, fsenChild );
2123     }
2124   }
2125 }