Robust/src/Analysis/MLP/MLPAnalysis.java

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