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