Robust/src/Analysis/MLP/MLPAnalysis.java

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