Robust/src/Analysis/MLP/MLPAnalysis.java

   1 package Analysis.MLP;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.FileWriter;
   5 import java.io.IOException;
   6 import java.io.StringWriter;
   7 import java.util.Enumeration;
   8 import java.util.HashSet;
   9 import java.util.Hashtable;
  10 import java.util.Iterator;
  11 import java.util.LinkedList;
  12 import java.util.Map;
  13 import java.util.Set;
  14 import java.util.Stack;
  15 import java.util.Map.Entry;
  16 import Analysis.CallGraph.CallGraph;
  17 import Analysis.CallGraph.JavaCallGraph;
  18 import Analysis.OwnershipAnalysis.AllocationSite;
  19 import Analysis.OwnershipAnalysis.EffectsKey;
  20 import Analysis.OwnershipAnalysis.HeapRegionNode;
  21 import Analysis.OwnershipAnalysis.LabelNode;
  22 import Analysis.OwnershipAnalysis.MethodContext;
  23 import Analysis.OwnershipAnalysis.MethodEffects;
  24 import Analysis.OwnershipAnalysis.OwnershipAnalysis;
  25 import Analysis.OwnershipAnalysis.OwnershipGraph;
  26 import Analysis.OwnershipAnalysis.OwnershipNode;
  27 import Analysis.OwnershipAnalysis.ParameterDecomposition;
  28 import Analysis.OwnershipAnalysis.ReachabilitySet;
  29 import Analysis.OwnershipAnalysis.ReferenceEdge;
  30 import Analysis.OwnershipAnalysis.TokenTuple;
  31 import Analysis.OwnershipAnalysis.TokenTupleSet;
  32 import IR.Descriptor;
  33 import IR.FieldDescriptor;
  34 import IR.MethodDescriptor;
  35 import IR.Operation;
  36 import IR.State;
  37 import IR.TypeDescriptor;
  38 import IR.TypeUtil;
  39 import IR.Flat.FKind;
  40 import IR.Flat.FlatCall;
  41 import IR.Flat.FlatCondBranch;
  42 import IR.Flat.FlatEdge;
  43 import IR.Flat.FlatElementNode;
  44 import IR.Flat.FlatFieldNode;
  45 import IR.Flat.FlatMethod;
  46 import IR.Flat.FlatNew;
  47 import IR.Flat.FlatNode;
  48 import IR.Flat.FlatOpNode;
  49 import IR.Flat.FlatReturnNode;
  50 import IR.Flat.FlatSESEEnterNode;
  51 import IR.Flat.FlatSESEExitNode;
  52 import IR.Flat.FlatSetElementNode;
  53 import IR.Flat.FlatSetFieldNode;
  54 import IR.Flat.FlatWriteDynamicVarNode;
  55 import IR.Flat.TempDescriptor;
  56
  57
  58 public class MLPAnalysis {
  59
  60   // data from the compiler
  61   private State             state;
  62   private TypeUtil          typeUtil;
  63   private CallGraph         callGraph;
  64   private OwnershipAnalysis ownAnalysis;
  65
  66
  67   // an implicit SESE is automatically spliced into
  68   // the IR graph around the C main before this analysis--it
  69   // is nothing special except that we can make assumptions
  70   // about it, such as the whole program ends when it ends
  71   private FlatSESEEnterNode mainSESE;
  72
  73   // SESEs that are the root of an SESE tree belong to this
  74   // set--the main SESE is always a root, statically SESEs
  75   // inside methods are a root because we don't know how they
  76   // will fit into the runtime tree of SESEs
  77   private Set<FlatSESEEnterNode> rootSESEs;
  78
  79   // simply a set of every reachable SESE in the program, not
  80   // including caller placeholder SESEs
  81   private Set<FlatSESEEnterNode> allSESEs;
  82
  83
  84   // A mapping of flat nodes to the stack of SESEs for that node, where
  85   // an SESE is the child of the SESE directly below it on the stack.
  86   // These stacks do not reflect the heirarchy over methods calls--whenever
  87   // there is an empty stack it means all variables are available.
  88   private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
  89
  90   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessRootView;
  91   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessVirtualReads;
  92   private Hashtable< FlatNode, VarSrcTokTable           > variableResults;
  93   private Hashtable< FlatNode, Set<TempDescriptor>      > notAvailableResults;
  94   private Hashtable< FlatNode, CodePlan                 > codePlans;
  95
  96   private Hashtable< FlatSESEEnterNode, Set<TempDescriptor> > notAvailableIntoSESE;
  97
  98   private Hashtable< FlatEdge, FlatWriteDynamicVarNode  > wdvNodesToSpliceIn;
  99
 100   private Hashtable< MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet;
 101
 102   private Hashtable < FlatNode, ParentChildConflictsMap > conflictsResults;
 103   private Hashtable< FlatMethod, MethodSummary > methodSummaryResults;
 104   private OwnershipAnalysis ownAnalysisForSESEConflicts;
 105   private Hashtable <FlatNode, ConflictGraph> conflictGraphResults;
 106
 107   // temporal data structures to track analysis progress.
 108   private MethodSummary currentMethodSummary;
 109   private HashSet<PreEffectsKey> preeffectsSet;
 110   private Hashtable<FlatNode, Boolean> isAfterChildSESEIndicatorMap;
 111   private Hashtable<FlatNode, SESESummary> seseSummaryMap;
 112   private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraphLockMap;
 113   static private int uniqueLockSetId = 0;
 114
 115   public static int maxSESEage = -1;
 116
 117
 118   // use these methods in BuildCode to have access to analysis results
 119   public FlatSESEEnterNode getMainSESE() {
 120     return mainSESE;
 121   }
 122
 123   public Set<FlatSESEEnterNode> getRootSESEs() {
 124     return rootSESEs;
 125   }
 126
 127   public Set<FlatSESEEnterNode> getAllSESEs() {
 128     return allSESEs;
 129   }
 130
 131   public int getMaxSESEage() {
 132     return maxSESEage;
 133   }
 134
 135   // may be null
 136   public CodePlan getCodePlan( FlatNode fn ) {
 137     CodePlan cp = codePlans.get( fn );
 138     return cp;
 139   }
 140
 141
 142   public MLPAnalysis( State             state,
 143                       TypeUtil          tu,
 144                       CallGraph         callGraph,
 145                       OwnershipAnalysis ownAnalysis
 146                       ) {
 147
 148     double timeStartAnalysis = (double) System.nanoTime();
 149
 150     this.state       = state;
 151     this.typeUtil    = tu;
 152     this.callGraph   = callGraph;
 153     this.ownAnalysis = ownAnalysis;
 154     this.maxSESEage  = state.MLP_MAXSESEAGE;
 155
 156     rootSESEs = new HashSet<FlatSESEEnterNode>();
 157     allSESEs  = new HashSet<FlatSESEEnterNode>();
 158
 159     seseStacks           = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
 160     livenessRootView     = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 161     livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 162     variableResults      = new Hashtable< FlatNode, VarSrcTokTable           >();
 163     notAvailableResults  = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 164     codePlans            = new Hashtable< FlatNode, CodePlan                 >();
 165     wdvNodesToSpliceIn   = new Hashtable< FlatEdge, FlatWriteDynamicVarNode  >();
 166
 167     notAvailableIntoSESE = new Hashtable< FlatSESEEnterNode, Set<TempDescriptor> >();
 168
 169     mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet<AllocationSite>>();
 170
 171     conflictsResults = new Hashtable < FlatNode, ParentChildConflictsMap >();
 172     methodSummaryResults=new Hashtable<FlatMethod, MethodSummary>();
 173     conflictGraphResults=new Hashtable<FlatNode, ConflictGraph>();
 174
 175     seseSummaryMap= new Hashtable<FlatNode, SESESummary>();
 176     isAfterChildSESEIndicatorMap= new Hashtable<FlatNode, Boolean>();
 177     conflictGraphLockMap=new Hashtable<ConflictGraph, HashSet<SESELock>>();
 178
 179     FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
 180
 181     mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
 182     mainSESE.setfmEnclosing( fmMain );
 183     mainSESE.setmdEnclosing( fmMain.getMethod() );
 184     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
 185
 186
 187     // 1st pass
 188     // run analysis on each method that is actually called
 189     // reachability analysis already computed this so reuse
 190     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 191     while( methItr.hasNext() ) {
 192       Descriptor d  = methItr.next();
 193       FlatMethod fm = state.getMethodFlat( d );
 194
 195       // find every SESE from methods that may be called
 196       // and organize them into roots and children
 197       buildForestForward( fm );
 198     }
 199
 200
 201     // 2nd pass, results are saved in FlatSESEEnterNode, so
 202     // intermediate results, for safety, are discarded
 203     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
 204     while( rootItr.hasNext() ) {
 205       FlatSESEEnterNode root = rootItr.next();
 206       livenessAnalysisBackward( root,
 207                                 true,
 208                                 null );
 209     }
 210
 211
 212     // 3rd pass
 213     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 214     while( methItr.hasNext() ) {
 215       Descriptor d  = methItr.next();
 216       FlatMethod fm = state.getMethodFlat( d );
 217
 218       // starting from roots do a forward, fixed-point
 219       // variable analysis for refinement and stalls
 220       variableAnalysisForward( fm );
 221     }
 222
 223     // 4th pass, compute liveness contribution from
 224     // virtual reads discovered in variable pass
 225     rootItr = rootSESEs.iterator();
 226     while( rootItr.hasNext() ) {
 227       FlatSESEEnterNode root = rootItr.next();
 228       livenessAnalysisBackward( root,
 229                                 true,
 230                                 null );
 231     }
 232
 233
 234     /*
 235       SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
 236
 237     // 5th pass
 238     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 239     while( methItr.hasNext() ) {
 240       Descriptor d  = methItr.next();
 241       FlatMethod fm = state.getMethodFlat( d );
 242
 243       // prune variable results in one traversal
 244       // by removing reference variables that are not live
 245       pruneVariableResultsWithLiveness( fm );
 246     }
 247     */
 248
 249
 250     // 6th pass
 251     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 252     while( methItr.hasNext() ) {
 253       Descriptor d  = methItr.next();
 254       FlatMethod fm = state.getMethodFlat( d );
 255
 256       // compute what is not available at every program
 257       // point, in a forward fixed-point pass
 258       notAvailableForward( fm );
 259     }
 260
 261     if(state.METHODEFFECTS){
 262         // new pass, sese effects analysis
 263         methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 264         JavaCallGraph javaCallGraph = new JavaCallGraph(state,tu);
 265         while( methItr.hasNext() ) {
 266           Descriptor d  = methItr.next();
 267           FlatMethod fm = state.getMethodFlat( d );
 268           methodEffects(fm,javaCallGraph);
 269         }
 270
 271         // Parent/child memory conflicts analysis
 272         seseConflictsForward(javaCallGraph);
 273
 274         Set<MethodContext> keySet=mapMethodContextToLiveInAllocationSiteSet.keySet();
 275         for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 276                 MethodContext methodContext = (MethodContext) iterator.next();
 277                 HashSet<AllocationSite> asSet=mapMethodContextToLiveInAllocationSiteSet.get(methodContext);
 278                 for (Iterator iterator2 = asSet.iterator(); iterator2.hasNext();) {
 279                         AllocationSite allocationSite = (AllocationSite) iterator2.next();
 280                 }
 281         }
 282
 283          // disjoint analysis with a set of flagged allocation sites of live-in variables & stall sites
 284         try {
 285           ownAnalysisForSESEConflicts = new OwnershipAnalysis(state,
 286                                                             tu,
 287                                                             callGraph,
 288                                                             ownAnalysis.liveness,
 289                                                             ownAnalysis.arrayReferencees,
 290                                                             state.OWNERSHIPALLOCDEPTH, false,
 291                                                             false, state.OWNERSHIPALIASFILE,
 292                                                             state.METHODEFFECTS,
 293                                                             mapMethodContextToLiveInAllocationSiteSet);
 294                 // debug
 295                 methItr = ownAnalysisForSESEConflicts.descriptorsToAnalyze.iterator();
 296                 while (methItr.hasNext()) {
 297                         Descriptor d = methItr.next();
 298                         FlatMethod fm = state.getMethodFlat(d);
 299                         debugFunction(ownAnalysisForSESEConflicts, fm);
 300                 }
 301                 //
 302         } catch (IOException e) {
 303                 System.err.println(e);
 304         }
 305
 306         //      postSESEConflictsForward(javaCallGraph);
 307         // another pass for making graph
 308         makeConflictGraph();
 309
 310         // lock synthesis
 311         synthesizeLocks();
 312         /*
 313         methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 314         while (methItr.hasNext()) {
 315                 Descriptor d = methItr.next();
 316                 FlatMethod fm = state.getMethodFlat(d);
 317                 makeConflictGraph2(fm);
 318         }
 319
 320         Enumeration<FlatNode> keyEnum1=conflictGraphResults.keys();
 321                 while (keyEnum1.hasMoreElements()) {
 322                         FlatNode flatNode = (FlatNode) keyEnum1.nextElement();
 323                         ConflictGraph conflictGraph=conflictGraphResults.get(flatNode);
 324                         conflictGraph.analyzeConflicts();
 325                         conflictGraphResults.put(flatNode, conflictGraph);
 326                 }
 327                 */
 328
 329         Enumeration<FlatNode> keyEnum=conflictGraphResults.keys();
 330         while (keyEnum.hasMoreElements()) {
 331                         FlatNode key = (FlatNode) keyEnum.nextElement();
 332                         ConflictGraph cg=conflictGraphResults.get(key);
 333                         try {
 334                                 if(cg.hasConflictEdge()){
 335                                         cg.writeGraph("ConflictGraphFor"+key, false);
 336                                 }
 337                         } catch (IOException e) {
 338                                 System.out.println("Error writing");
 339                                 System.exit(0);
 340                         }
 341                 }
 342     }
 343
 344
 345     // 7th pass
 346     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 347     while( methItr.hasNext() ) {
 348       Descriptor d  = methItr.next();
 349       FlatMethod fm = state.getMethodFlat( d );
 350
 351       // compute a plan for code injections
 352       codePlansForward( fm );
 353     }
 354
 355
 356     // splice new IR nodes into graph after all
 357     // analysis passes are complete
 358     Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
 359     while( spliceItr.hasNext() ) {
 360       Map.Entry               me    = (Map.Entry)               spliceItr.next();
 361       FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
 362       fwdvn.spliceIntoIR();
 363     }
 364
 365
 366     double timeEndAnalysis = (double) System.nanoTime();
 367     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 368     String treport = String.format( "The mlp analysis took %.3f sec.", dt );
 369     System.out.println( treport );
 370
 371     if( state.MLPDEBUG ) {
 372       try {
 373         writeReports( treport );
 374       } catch( IOException e ) {}
 375     }
 376   }
 377
 378
 379   private void buildForestForward( FlatMethod fm ) {
 380
 381     // start from flat method top, visit every node in
 382     // method exactly once, find SESEs and remember
 383     // roots and child relationships
 384     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 385     flatNodesToVisit.add( fm );
 386
 387     Set<FlatNode> visited = new HashSet<FlatNode>();
 388
 389     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 390     seseStacks.put( fm, seseStackFirst );
 391
 392     while( !flatNodesToVisit.isEmpty() ) {
 393       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 394       FlatNode fn = fnItr.next();
 395
 396       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 397       assert seseStack != null;
 398
 399       flatNodesToVisit.remove( fn );
 400       visited.add( fn );
 401
 402       buildForest_nodeActions( fn, seseStack, fm );
 403
 404       for( int i = 0; i < fn.numNext(); i++ ) {
 405         FlatNode nn = fn.getNext( i );
 406
 407         if( !visited.contains( nn ) ) {
 408           flatNodesToVisit.add( nn );
 409
 410           // clone stack and send along each analysis path
 411           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 412         }
 413       }
 414     }
 415   }
 416
 417   private void buildForest_nodeActions( FlatNode fn,
 418                                         Stack<FlatSESEEnterNode> seseStack,
 419                                         FlatMethod fm ) {
 420     switch( fn.kind() ) {
 421
 422     case FKind.FlatSESEEnterNode: {
 423       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 424
 425       if( !fsen.getIsCallerSESEplaceholder() ) {
 426         allSESEs.add( fsen );
 427       }
 428
 429       fsen.setfmEnclosing( fm );
 430       fsen.setmdEnclosing( fm.getMethod() );
 431       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 432
 433       if( seseStack.empty() ) {
 434         rootSESEs.add( fsen );
 435         fsen.setParent( null );
 436       } else {
 437         seseStack.peek().addChild( fsen );
 438         fsen.setParent( seseStack.peek() );
 439       }
 440
 441       seseStack.push( fsen );
 442     } break;
 443
 444     case FKind.FlatSESEExitNode: {
 445       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 446       assert !seseStack.empty();
 447       FlatSESEEnterNode fsen = seseStack.pop();
 448     } break;
 449
 450     case FKind.FlatReturnNode: {
 451       FlatReturnNode frn = (FlatReturnNode) fn;
 452       if( !seseStack.empty() &&
 453           !seseStack.peek().getIsCallerSESEplaceholder()
 454         ) {
 455         throw new Error( "Error: return statement enclosed within SESE "+
 456                          seseStack.peek().getPrettyIdentifier() );
 457       }
 458     } break;
 459
 460     }
 461   }
 462
 463
 464   private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
 465                                          boolean toplevel,
 466                                          Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
 467
 468     // start from an SESE exit, visit nodes in reverse up to
 469     // SESE enter in a fixed-point scheme, where children SESEs
 470     // should already be analyzed and therefore can be skipped
 471     // because child SESE enter node has all necessary info
 472     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 473
 474     if( toplevel ) {
 475       flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
 476     } else {
 477       flatNodesToVisit.add( fsen.getFlatExit() );
 478     }
 479
 480     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
 481       new Hashtable< FlatNode, Set<TempDescriptor> >();
 482
 483     if( toplevel ) {
 484       liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
 485     }
 486
 487     while( !flatNodesToVisit.isEmpty() ) {
 488       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 489       flatNodesToVisit.remove( fn );
 490
 491       Set<TempDescriptor> prev = livenessResults.get( fn );
 492
 493       // merge sets from control flow joins
 494       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 495       for( int i = 0; i < fn.numNext(); i++ ) {
 496         FlatNode nn = fn.getNext( i );
 497         Set<TempDescriptor> s = livenessResults.get( nn );
 498         if( s != null ) {
 499           u.addAll( s );
 500         }
 501       }
 502
 503       Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
 504
 505       // if a new result, schedule backward nodes for analysis
 506       if( !curr.equals( prev ) ) {
 507         livenessResults.put( fn, curr );
 508
 509         // don't flow backwards past current SESE enter
 510         if( !fn.equals( fsen ) ) {
 511           for( int i = 0; i < fn.numPrev(); i++ ) {
 512             FlatNode nn = fn.getPrev( i );
 513             flatNodesToVisit.add( nn );
 514           }
 515         }
 516       }
 517     }
 518
 519     Set<TempDescriptor> s = livenessResults.get( fsen );
 520     if( s != null ) {
 521       fsen.addInVarSet( s );
 522     }
 523
 524     // remember liveness per node from the root view as the
 525     // global liveness of variables for later passes to use
 526     if( toplevel ) {
 527       livenessRootView.putAll( livenessResults );
 528     }
 529
 530     // post-order traversal, so do children first
 531     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 532     while( childItr.hasNext() ) {
 533       FlatSESEEnterNode fsenChild = childItr.next();
 534       livenessAnalysisBackward( fsenChild, false, liveout );
 535     }
 536   }
 537
 538   private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
 539                                                     Set<TempDescriptor> liveIn,
 540                                                     FlatSESEEnterNode currentSESE,
 541                                                     boolean toplevel,
 542                                                     Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
 543                                                   ) {
 544     switch( fn.kind() ) {
 545
 546     case FKind.FlatSESEExitNode:
 547       if( toplevel ) {
 548         FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 549         if( !liveout.containsKey( fsexn ) ) {
 550           liveout.put( fsexn, new HashSet<TempDescriptor>() );
 551         }
 552         liveout.get( fsexn ).addAll( liveIn );
 553       }
 554       // no break, sese exits should also execute default actions
 555
 556     default: {
 557       // handle effects of statement in reverse, writes then reads
 558       TempDescriptor [] writeTemps = fn.writesTemps();
 559       for( int i = 0; i < writeTemps.length; ++i ) {
 560         liveIn.remove( writeTemps[i] );
 561
 562         if( !toplevel ) {
 563           FlatSESEExitNode fsexn = currentSESE.getFlatExit();
 564           Set<TempDescriptor> livetemps = liveout.get( fsexn );
 565           if( livetemps != null &&
 566               livetemps.contains( writeTemps[i] ) ) {
 567             // write to a live out temp...
 568             // need to put in SESE liveout set
 569             currentSESE.addOutVar( writeTemps[i] );
 570           }
 571         }
 572       }
 573
 574       TempDescriptor [] readTemps = fn.readsTemps();
 575       for( int i = 0; i < readTemps.length; ++i ) {
 576         liveIn.add( readTemps[i] );
 577       }
 578
 579       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
 580       if( virtualReadTemps != null ) {
 581         liveIn.addAll( virtualReadTemps );
 582       }
 583
 584     } break;
 585
 586     } // end switch
 587
 588     return liveIn;
 589   }
 590
 591
 592   private void variableAnalysisForward( FlatMethod fm ) {
 593
 594     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 595     flatNodesToVisit.add( fm );
 596
 597     while( !flatNodesToVisit.isEmpty() ) {
 598       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 599       flatNodesToVisit.remove( fn );
 600
 601       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 602       assert seseStack != null;
 603
 604       VarSrcTokTable prev = variableResults.get( fn );
 605
 606       // merge sets from control flow joins
 607       VarSrcTokTable curr = new VarSrcTokTable();
 608       for( int i = 0; i < fn.numPrev(); i++ ) {
 609         FlatNode nn = fn.getPrev( i );
 610         VarSrcTokTable incoming = variableResults.get( nn );
 611         curr.merge( incoming );
 612       }
 613
 614       if( !seseStack.empty() ) {
 615         variable_nodeActions( fn, curr, seseStack.peek() );
 616       }
 617
 618       // if a new result, schedule forward nodes for analysis
 619       if( !curr.equals( prev ) ) {
 620         variableResults.put( fn, curr );
 621
 622         for( int i = 0; i < fn.numNext(); i++ ) {
 623           FlatNode nn = fn.getNext( i );
 624           flatNodesToVisit.add( nn );
 625         }
 626       }
 627     }
 628   }
 629
 630   private void variable_nodeActions( FlatNode fn,
 631                                      VarSrcTokTable vstTable,
 632                                      FlatSESEEnterNode currentSESE ) {
 633     switch( fn.kind() ) {
 634
 635     case FKind.FlatSESEEnterNode: {
 636       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 637       assert fsen.equals( currentSESE );
 638
 639       vstTable.age( currentSESE );
 640       vstTable.assertConsistency();
 641     } break;
 642
 643     case FKind.FlatSESEExitNode: {
 644       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 645       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 646       assert currentSESE.getChildren().contains( fsen );
 647
 648       // remap all of this child's children tokens to be
 649       // from this child as the child exits
 650       vstTable.remapChildTokens( fsen );
 651
 652       // liveness virtual reads are things that might be
 653       // written by an SESE and should be added to the in-set
 654       // anything virtually read by this SESE should be pruned
 655       // of parent or sibling sources
 656       Set<TempDescriptor> liveVars         = livenessRootView.get( fn );
 657       Set<TempDescriptor> fsenVirtReads    = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
 658       Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
 659       if( fsenVirtReadsOld != null ) {
 660         fsenVirtReads.addAll( fsenVirtReadsOld );
 661       }
 662       livenessVirtualReads.put( fn, fsenVirtReads );
 663
 664
 665       // then all child out-set tokens are guaranteed
 666       // to be filled in, so clobber those entries with
 667       // the latest, clean sources
 668       Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
 669       while( outVarItr.hasNext() ) {
 670         TempDescriptor outVar = outVarItr.next();
 671         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 672         ts.add( outVar );
 673         VariableSourceToken vst =
 674           new VariableSourceToken( ts,
 675                                    fsen,
 676                                    new Integer( 0 ),
 677                                    outVar
 678                                    );
 679         vstTable.remove( outVar );
 680         vstTable.add( vst );
 681       }
 682       vstTable.assertConsistency();
 683
 684     } break;
 685
 686     case FKind.FlatOpNode: {
 687       FlatOpNode fon = (FlatOpNode) fn;
 688
 689       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 690         TempDescriptor lhs = fon.getDest();
 691         TempDescriptor rhs = fon.getLeft();
 692
 693         vstTable.remove( lhs );
 694
 695         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 696
 697         Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
 698         while( itr.hasNext() ) {
 699           VariableSourceToken vst = itr.next();
 700
 701           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 702           ts.add( lhs );
 703
 704           if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
 705             // if the source comes from a child, copy it over
 706             forAddition.add( new VariableSourceToken( ts,
 707                                                       vst.getSESE(),
 708                                                       vst.getAge(),
 709                                                       vst.getAddrVar()
 710                                                       )
 711                              );
 712           } else {
 713             // otherwise, stamp it as us as the source
 714             forAddition.add( new VariableSourceToken( ts,
 715                                                       currentSESE,
 716                                                       new Integer( 0 ),
 717                                                       lhs
 718                                                       )
 719                              );
 720           }
 721         }
 722
 723         vstTable.addAll( forAddition );
 724
 725         // only break if this is an ASSIGN op node,
 726         // otherwise fall through to default case
 727         vstTable.assertConsistency();
 728         break;
 729       }
 730     }
 731
 732     // note that FlatOpNode's that aren't ASSIGN
 733     // fall through to this default case
 734     default: {
 735       TempDescriptor [] writeTemps = fn.writesTemps();
 736       if( writeTemps.length > 0 ) {
 737
 738
 739         // for now, when writeTemps > 1, make sure
 740         // its a call node, programmer enforce only
 741         // doing stuff like calling a print routine
 742         //assert writeTemps.length == 1;
 743         if( writeTemps.length > 1 ) {
 744           assert fn.kind() == FKind.FlatCall ||
 745                  fn.kind() == FKind.FlatMethod;
 746           break;
 747         }
 748
 749         vstTable.remove( writeTemps[0] );
 750
 751         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 752         ts.add( writeTemps[0] );
 753
 754         vstTable.add( new VariableSourceToken( ts,
 755                                                currentSESE,
 756                                                new Integer( 0 ),
 757                                                writeTemps[0]
 758                                              )
 759                       );
 760       }
 761
 762       vstTable.assertConsistency();
 763     } break;
 764
 765     } // end switch
 766   }
 767
 768
 769   private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
 770
 771     // start from flat method top, visit every node in
 772     // method exactly once
 773     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 774     flatNodesToVisit.add( fm );
 775
 776     Set<FlatNode> visited = new HashSet<FlatNode>();
 777
 778     while( !flatNodesToVisit.isEmpty() ) {
 779       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 780       FlatNode fn = fnItr.next();
 781
 782       flatNodesToVisit.remove( fn );
 783       visited.add( fn );
 784
 785       Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
 786       VarSrcTokTable      vstTable    = variableResults.get( fn );
 787
 788       vstTable.pruneByLiveness( rootLiveSet );
 789
 790       for( int i = 0; i < fn.numNext(); i++ ) {
 791         FlatNode nn = fn.getNext( i );
 792
 793         if( !visited.contains( nn ) ) {
 794           flatNodesToVisit.add( nn );
 795         }
 796       }
 797     }
 798   }
 799
 800
 801   private void notAvailableForward( FlatMethod fm ) {
 802
 803     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 804     flatNodesToVisit.add( fm );
 805
 806     while( !flatNodesToVisit.isEmpty() ) {
 807       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 808       flatNodesToVisit.remove( fn );
 809
 810       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 811       assert seseStack != null;
 812
 813       Set<TempDescriptor> prev = notAvailableResults.get( fn );
 814
 815       Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
 816       for( int i = 0; i < fn.numPrev(); i++ ) {
 817         FlatNode nn = fn.getPrev( i );
 818         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
 819         if( notAvailIn != null ) {
 820           curr.addAll( notAvailIn );
 821         }
 822       }
 823
 824       if( !seseStack.empty() ) {
 825         notAvailable_nodeActions( fn, curr, seseStack.peek() );
 826       }
 827
 828       // if a new result, schedule forward nodes for analysis
 829       if( !curr.equals( prev ) ) {
 830         notAvailableResults.put( fn, curr );
 831
 832         for( int i = 0; i < fn.numNext(); i++ ) {
 833           FlatNode nn = fn.getNext( i );
 834           flatNodesToVisit.add( nn );
 835         }
 836       }
 837     }
 838   }
 839
 840   private void notAvailable_nodeActions( FlatNode fn,
 841                                          Set<TempDescriptor> notAvailSet,
 842                                          FlatSESEEnterNode currentSESE ) {
 843
 844     // any temps that are removed from the not available set
 845     // at this node should be marked in this node's code plan
 846     // as temps to be grabbed at runtime!
 847
 848     switch( fn.kind() ) {
 849
 850     case FKind.FlatSESEEnterNode: {
 851       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 852       assert fsen.equals( currentSESE );
 853
 854       // keep a copy of what's not available into the SESE
 855       // and restore it at the matching exit node
 856       Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
 857       Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
 858       while( tdItr.hasNext() ) {
 859         notAvailCopy.add( tdItr.next() );
 860       }
 861       notAvailableIntoSESE.put( fsen, notAvailCopy );
 862
 863       notAvailSet.clear();
 864     } break;
 865
 866     case FKind.FlatSESEExitNode: {
 867       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 868       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 869       assert currentSESE.getChildren().contains( fsen );
 870
 871       notAvailSet.addAll( fsen.getOutVarSet() );
 872
 873       Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get( fsen );
 874       assert notAvailIn != null;
 875       notAvailSet.addAll( notAvailIn );
 876
 877     } break;
 878
 879     case FKind.FlatMethod: {
 880       notAvailSet.clear();
 881     }
 882
 883     case FKind.FlatOpNode: {
 884       FlatOpNode fon = (FlatOpNode) fn;
 885
 886       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 887         TempDescriptor lhs = fon.getDest();
 888         TempDescriptor rhs = fon.getLeft();
 889
 890         // copy makes lhs same availability as rhs
 891         if( notAvailSet.contains( rhs ) ) {
 892           notAvailSet.add( lhs );
 893         } else {
 894           notAvailSet.remove( lhs );
 895         }
 896
 897         // only break if this is an ASSIGN op node,
 898         // otherwise fall through to default case
 899         break;
 900       }
 901     }
 902
 903     // note that FlatOpNode's that aren't ASSIGN
 904     // fall through to this default case
 905     default: {
 906       TempDescriptor [] writeTemps = fn.writesTemps();
 907       for( int i = 0; i < writeTemps.length; i++ ) {
 908         TempDescriptor wTemp = writeTemps[i];
 909         notAvailSet.remove( wTemp );
 910       }
 911       TempDescriptor [] readTemps = fn.readsTemps();
 912       for( int i = 0; i < readTemps.length; i++ ) {
 913         TempDescriptor rTemp = readTemps[i];
 914         notAvailSet.remove( rTemp );
 915
 916         // if this variable has exactly one source, potentially
 917         // get other things from this source as well
 918         VarSrcTokTable vstTable = variableResults.get( fn );
 919
 920         VSTWrapper vstIfStatic = new VSTWrapper();
 921         Integer srcType =
 922           vstTable.getRefVarSrcType( rTemp,
 923                                      currentSESE,
 924                                      vstIfStatic
 925                                      );
 926
 927         if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
 928
 929           VariableSourceToken vst = vstIfStatic.vst;
 930
 931           Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
 932                                                                  vst.getAge()
 933                                                                  ).iterator();
 934
 935           // look through things that are also available from same source
 936           while( availItr.hasNext() ) {
 937             VariableSourceToken vstAlsoAvail = availItr.next();
 938
 939             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
 940             while( refVarItr.hasNext() ) {
 941               TempDescriptor refVarAlso = refVarItr.next();
 942
 943               // if a variable is available from the same source, AND it ALSO
 944               // only comes from one statically known source, mark it available
 945               VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
 946               Integer srcTypeAlso =
 947                 vstTable.getRefVarSrcType( refVarAlso,
 948                                            currentSESE,
 949                                            vstIfStaticNotUsed
 950                                            );
 951               if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
 952                 notAvailSet.remove( refVarAlso );
 953               }
 954             }
 955           }
 956         }
 957       }
 958     } break;
 959
 960     } // end switch
 961   }
 962
 963   private void debugFunction(OwnershipAnalysis oa2, FlatMethod fm) {
 964
 965           String methodName="SomeWork";
 966
 967           MethodDescriptor md=fm.getMethod();
 968                 HashSet<MethodContext> mcSet=oa2.getAllMethodContextSetByDescriptor(md);
 969                 Iterator<MethodContext> mcIter=mcSet.iterator();
 970
 971                 while(mcIter.hasNext()){
 972                         MethodContext mc=mcIter.next();
 973
 974                         OwnershipGraph og=oa2.getOwnvershipGraphByMethodContext(mc);
 975
 976                         if(fm.toString().indexOf(methodName)>0){
 977                                  try {
 978                                    og.writeGraph("SECONDGRAPH"+fm.toString(),
 979                                                  true,  // write labels (variables)
 980                                                  true,  // selectively hide intermediate temp vars
 981                                                  true,  // prune unreachable heap regions
 982                                                  false, // show back edges to confirm graph validity
 983                                                  false, // show parameter indices (unmaintained!)
 984                                                  true,  // hide subset reachability states
 985                                                  false);// hide edge taints
 986                                  } catch (IOException e) {
 987                                  System.out.println("Error writing debug capture.");
 988                                  System.exit(0);
 989                                  }
 990                         }
 991                 }
 992
 993   }
 994
 995         private void methodEffects(FlatMethod fm, CallGraph callGraph) {
 996
 997                 MethodDescriptor md=fm.getMethod();
 998                 HashSet<MethodContext> mcSet=ownAnalysis.getAllMethodContextSetByDescriptor(md);
 999                 Iterator<MethodContext> mcIter=mcSet.iterator();
1000
1001                 while(mcIter.hasNext()){
1002                         MethodContext mc=mcIter.next();
1003
1004                         Set<FlatNode> visited = new HashSet<FlatNode>();
1005
1006                         Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1007                         flatNodesToVisit.add(fm);
1008
1009                         Hashtable<TempDescriptor, TempDescriptor> invarMap=new Hashtable<TempDescriptor,TempDescriptor>();
1010
1011                         while (!flatNodesToVisit.isEmpty()) {
1012                                 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1013                                 flatNodesToVisit.remove(fn);
1014
1015                                 Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
1016                                 assert seseStack != null;
1017
1018                                 if (!seseStack.empty()) {
1019                                         effects_nodeActions(mc, fn, seseStack.peek(), callGraph,invarMap);
1020                                 }
1021
1022                                 flatNodesToVisit.remove(fn);
1023                                 visited.add(fn);
1024
1025                                 for (int i = 0; i < fn.numNext(); i++) {
1026                                         FlatNode nn = fn.getNext(i);
1027                                         if (!visited.contains(nn)) {
1028                                                 flatNodesToVisit.add(nn);
1029                                         }
1030                                 }
1031
1032                         }
1033
1034
1035                 }
1036
1037         }
1038
1039         private void analyzeRelatedAllocationSite(MethodDescriptor callerMD,
1040                         MethodContext calleeMC, HashSet<Integer> paramIndexSet,
1041                         HashSet<HeapRegionNode> visitedHRN) {
1042
1043                 HashSet<MethodContext> mcSet = ownAnalysis
1044                                 .getAllMethodContextSetByDescriptor(callerMD);
1045
1046                 if (mcSet != null) {
1047
1048                         Iterator<MethodContext> mcIter = mcSet.iterator();
1049
1050                         FlatMethod callerFM = state.getMethodFlat(callerMD);
1051
1052                         while (mcIter.hasNext()) {
1053                                 MethodContext mc = mcIter.next();
1054
1055                                 Set<FlatNode> visited = new HashSet<FlatNode>();
1056                                 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1057                                 flatNodesToVisit.add(callerFM);
1058
1059                                 while (!flatNodesToVisit.isEmpty()) {
1060                                         FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1061                                         flatNodesToVisit.remove(fn);
1062
1063                                         analyzeRelatedAllocationSite_NodeAction(fn, mc, calleeMC,
1064                                                         paramIndexSet,visitedHRN);
1065
1066                                         flatNodesToVisit.remove(fn);
1067                                         visited.add(fn);
1068
1069                                         for (int i = 0; i < fn.numNext(); i++) {
1070                                                 FlatNode nn = fn.getNext(i);
1071                                                 if (!visited.contains(nn)) {
1072                                                         flatNodesToVisit.add(nn);
1073                                                 }
1074                                         }
1075                                 }
1076                         }
1077                 }
1078
1079         }
1080
1081         private void analyzeRelatedAllocationSite_NodeAction(FlatNode fn, MethodContext callerMC,
1082  MethodContext calleeMC,
1083                         HashSet<Integer> paramIndexSet, HashSet<HeapRegionNode> visitedHRN) {
1084
1085                 OwnershipGraph og = ownAnalysis
1086                                 .getOwnvershipGraphByMethodContext(callerMC);
1087
1088                 switch (fn.kind()) {
1089
1090                 case FKind.FlatCall: {
1091
1092                         FlatCall fc = (FlatCall) fn;
1093
1094
1095                         if(fc.numArgs()>0 && fc.getMethod().equals(calleeMC.getDescriptor())){
1096                                 MethodContext calleeMCfromOG = ownAnalysis.getCalleeMethodContext(
1097                                                 callerMC, fc);
1098
1099                                 // disable below condition. currently collect all possible
1100                                 // allocation sites without regarding method context
1101
1102                                 // if (calleeMC.equals(calleeMCfromOG)) { // in this case, this
1103                                 // method context calls corresponding callee.
1104
1105                                 int base;
1106                                 if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
1107                                         base = 0;
1108                                 } else {
1109                                         base = 1;
1110                                 }
1111
1112                                 for (Iterator iterator = paramIndexSet.iterator(); iterator
1113                                                 .hasNext();) {
1114                                         Integer integer = (Integer) iterator.next();
1115
1116                                         int paramIdx = integer - base;
1117                                         if (paramIdx >= 0) {
1118                                                 // if paramIdx is less than 0, assumes that it is
1119                                                 // related with wrong method contexts.
1120                                                 TempDescriptor arg = fc.getArg(paramIdx);
1121                                                 LabelNode argLN = og.td2ln.get(arg);
1122                                                 if (argLN != null) {
1123                                                         Iterator<ReferenceEdge> iterEdge = argLN
1124                                                                         .iteratorToReferencees();
1125                                                         while (iterEdge.hasNext()) {
1126                                                                 ReferenceEdge referenceEdge = (ReferenceEdge) iterEdge
1127                                                                                 .next();
1128
1129                                                                 HeapRegionNode dstHRN = referenceEdge.getDst();
1130                                                                 if (dstHRN.isParameter()) {
1131                                                                         if (!visitedHRN.contains(dstHRN)) {
1132                                                                                 setupRelatedAllocSiteAnalysis(og, callerMC,
1133                                                                                                 dstHRN, visitedHRN);
1134                                                                         }
1135                                                                 } else {
1136 //                                                                      System.out.println("FLAGGED "+callerMC+":fc="+fc+":arg="+arg+" , paramIdx="+paramIdx);
1137                                                                         flagAllocationSite(callerMC, dstHRN
1138                                                                                         .getAllocationSite());
1139                                                                 }
1140                                                         }
1141                                                 }
1142                                         }
1143                                 }
1144                         }
1145
1146
1147                         // }
1148
1149                 }
1150                         break;
1151
1152                 }
1153         }
1154
1155         private void setupRelatedAllocSiteAnalysis(OwnershipGraph og,
1156                         MethodContext mc, HeapRegionNode dstHRN,
1157                         HashSet<HeapRegionNode> visitedHRN) {
1158
1159                 HashSet<Integer> paramIndexSet = new HashSet<Integer>();
1160
1161                 // collect corresponding param index
1162                 Set<Integer> pIndexSet = og.idPrimary2paramIndexSet.get(dstHRN.getID());
1163                 if (pIndexSet != null) {
1164                         for (Iterator iterator = pIndexSet.iterator(); iterator.hasNext();) {
1165                                 Integer integer = (Integer) iterator.next();
1166                                 paramIndexSet.add(integer);
1167                         }
1168                 }
1169
1170                 Set<Integer> sIndexSet = og.idSecondary2paramIndexSet.get(dstHRN
1171                                 .getID());
1172                 if (sIndexSet != null) {
1173                         for (Iterator iterator = sIndexSet.iterator(); iterator.hasNext();) {
1174                                 Integer integer = (Integer) iterator.next();
1175                                 paramIndexSet.add(integer);
1176                         }
1177                 }
1178
1179                 if (mc.getDescriptor() instanceof MethodDescriptor) {
1180                         Set callerSet = callGraph.getCallerSet((MethodDescriptor) mc
1181                                         .getDescriptor());
1182                         for (Iterator iterator = callerSet.iterator(); iterator.hasNext();) {
1183                                 Object obj = (Object) iterator.next();
1184                                 if (obj instanceof MethodDescriptor) {
1185                                         MethodDescriptor callerMD = (MethodDescriptor) obj;
1186
1187                                         if(callerMD.equals(mc.getDescriptor())){
1188                                                 continue;
1189                                         }
1190                                         analyzeRelatedAllocationSite(callerMD, mc, paramIndexSet,visitedHRN);
1191
1192                                 }
1193                         }
1194                 }
1195         }
1196
1197         private void effects_nodeActions(MethodContext mc, FlatNode fn,
1198                         FlatSESEEnterNode currentSESE, CallGraph callGraph,Hashtable<TempDescriptor, TempDescriptor> invarMap) {
1199
1200                 OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc);
1201
1202                 switch (fn.kind()) {
1203
1204                 case FKind.FlatSESEEnterNode: {
1205
1206                         FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
1207                         assert fsen.equals(currentSESE);
1208
1209                         if (!fsen.getIsCallerSESEplaceholder()) {
1210                                 // uniquely taint each live-in variable
1211                                 Set<TempDescriptor> set = fsen.getInVarSet();
1212                                 Iterator<TempDescriptor> iter = set.iterator();
1213                                 int idx = 0;
1214                                 while (iter.hasNext()) {
1215                                         TempDescriptor td = iter.next();
1216                                         LabelNode ln = og.td2ln.get(td);
1217
1218                                         if(currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx().containsKey(td)){
1219                                                 idx=currentSESE.getSeseEffectsSet().getInVarIdx(td);
1220                                         }
1221
1222                                         if (ln != null) {
1223                                                 int taint = (int) Math.pow(2, idx);
1224                                                 taintLabelNode(ln, taint,currentSESE.getSeseEffectsSet());
1225                                                 currentSESE.getSeseEffectsSet().setInVarIdx(idx, td);
1226
1227                                                 // collects related allocation sites
1228                                                 Iterator<ReferenceEdge> referenceeIter = ln
1229                                                                 .iteratorToReferencees();
1230                                                 while (referenceeIter.hasNext()) {
1231                                                         ReferenceEdge referenceEdge = (ReferenceEdge) referenceeIter
1232                                                                         .next();
1233                                                         HeapRegionNode dstHRN = referenceEdge.getDst();
1234                                                         if (dstHRN.isParameter()) {
1235
1236                                                                 HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
1237                                                                 visitedHRN.add(dstHRN);
1238                                                                 setupRelatedAllocSiteAnalysis(og, mc, dstHRN,
1239                                                                                 visitedHRN);
1240
1241                                                         } else {
1242 //                                                              System.out.println("FLAGGED "+fsen+":"+td);
1243                                                                 flagAllocationSite(mc, dstHRN
1244                                                                                 .getAllocationSite());
1245                                                         }
1246                                                 }
1247
1248                                         }
1249
1250                                         idx++;
1251                                 }
1252                         }
1253
1254                 }
1255                         break;
1256
1257                 case FKind.FlatSESEExitNode: {
1258                         FlatSESEExitNode fsexit = (FlatSESEExitNode) fn;
1259
1260                         if (!fsexit.getFlatEnter().getIsCallerSESEplaceholder()) {
1261
1262                                 // clear taint information of live-in variables
1263                                 Set<Integer> keySet=og.id2hrn.keySet();
1264                                 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1265                                         Integer hrnID = (Integer) iterator.next();
1266                                         HeapRegionNode hrn=og.id2hrn.get(hrnID);
1267                                         Iterator<ReferenceEdge> edgeIter=hrn.iteratorToReferencers();
1268                                         while (edgeIter.hasNext()) {
1269                                                 ReferenceEdge refEdge = (ReferenceEdge) edgeIter
1270                                                                 .next();
1271                                                 refEdge.setSESETaintIdentifier(0);
1272                                         }
1273                                 }
1274
1275                                 FlatSESEEnterNode enterNode = fsexit.getFlatEnter();
1276                                 FlatSESEEnterNode parent = enterNode.getParent();
1277                                 if (parent != null) {
1278
1279                                         SESEEffectsSet set = enterNode.getSeseEffectsSet();
1280                                         Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> readTable = set
1281                                                         .getReadTable();
1282                                         Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentReadTable = parent
1283                                                         .getSeseEffectsSet().getReadTable();
1284                                         Set<TempDescriptor> keys = readTable.keySet();
1285                                         Iterator<TempDescriptor> keyIter = keys.iterator();
1286                                         while (keyIter.hasNext()) {
1287                                                 TempDescriptor td = (TempDescriptor) keyIter.next();
1288                                                 HashSet<SESEEffectsKey> effectsSet = readTable.get(td);
1289                                                 HashSet<SESEEffectsKey> parentEffectsSet = parentReadTable
1290                                                                 .get(td);
1291                                                 if (parentEffectsSet == null) {
1292                                                         parentEffectsSet = new HashSet<SESEEffectsKey>();
1293                                                 }
1294
1295                                                 for (Iterator iterator = effectsSet.iterator(); iterator
1296                                                                 .hasNext();) {
1297                                                         SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1298                                                                         .next();
1299                                                         parentEffectsSet.add(new SESEEffectsKey(seseKey
1300                                                                         .getFieldDescriptor(), seseKey
1301                                                                         .getTypeDescriptor(), seseKey.getHRNId(),
1302                                                                         seseKey.getHRNUniqueId()));
1303                                                 }
1304
1305                                                 parentReadTable.put(td, parentEffectsSet);
1306                                         }
1307
1308                                         Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> writeTable = set
1309                                                         .getWriteTable();
1310                                         Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentWriteTable = parent
1311                                                         .getSeseEffectsSet().getWriteTable();
1312                                         keys = writeTable.keySet();
1313                                         keyIter = keys.iterator();
1314                                         while (keyIter.hasNext()) {
1315                                                 TempDescriptor td = (TempDescriptor) keyIter.next();
1316                                                 HashSet<SESEEffectsKey> effectsSet = writeTable.get(td);
1317                                                 HashSet<SESEEffectsKey> parentEffectsSet = parentWriteTable
1318                                                                 .get(td);
1319                                                 if (parentEffectsSet == null) {
1320                                                         parentEffectsSet = new HashSet<SESEEffectsKey>();
1321                                                 }
1322
1323                                                 for (Iterator iterator = effectsSet.iterator(); iterator
1324                                                                 .hasNext();) {
1325                                                         SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1326                                                                         .next();
1327                                                         parentEffectsSet.add(new SESEEffectsKey(seseKey
1328                                                                         .getFieldDescriptor(), seseKey
1329                                                                         .getTypeDescriptor(), seseKey.getHRNId(),
1330                                                                         seseKey.getHRNUniqueId()));
1331                                                 }
1332
1333                                                 parentWriteTable.put(td, parentEffectsSet);
1334                                         }
1335
1336                                         Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> strongUpdateTable = set
1337                                                         .getStrongUpdateTable();
1338                                         Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentstrongUpdateTable = parent
1339                                                         .getSeseEffectsSet().getStrongUpdateTable();
1340                                         keys = strongUpdateTable.keySet();
1341                                         keyIter = keys.iterator();
1342                                         while (keyIter.hasNext()) {
1343                                                 TempDescriptor td = (TempDescriptor) keyIter.next();
1344                                                 HashSet<SESEEffectsKey> effectsSet = strongUpdateTable
1345                                                                 .get(td);
1346                                                 HashSet<SESEEffectsKey> parentEffectsSet = parentstrongUpdateTable
1347                                                                 .get(td);
1348                                                 if (parentEffectsSet == null) {
1349                                                         parentEffectsSet = new HashSet<SESEEffectsKey>();
1350                                                 }
1351
1352                                                 for (Iterator iterator = effectsSet.iterator(); iterator
1353                                                                 .hasNext();) {
1354                                                         SESEEffectsKey seseKey = (SESEEffectsKey) iterator
1355                                                                         .next();
1356                                                         parentEffectsSet.add(new SESEEffectsKey(seseKey
1357                                                                         .getFieldDescriptor(), seseKey
1358                                                                         .getTypeDescriptor(), seseKey.getHRNId(),
1359                                                                         seseKey.getHRNUniqueId()));
1360                                                 }
1361
1362                                                 parentstrongUpdateTable.put(td, parentEffectsSet);
1363                                         }
1364
1365                                 }
1366
1367                         }
1368
1369                 }
1370                         break;
1371
1372                 case FKind.FlatFieldNode: {
1373
1374                         FlatFieldNode ffn = (FlatFieldNode) fn;
1375                         TempDescriptor dst = ffn.getDst();
1376                         TempDescriptor src = ffn.getSrc();
1377                         FieldDescriptor field = ffn.getField();
1378
1379                         LabelNode srcLN = og.td2ln.get(src);
1380                         if(srcLN!=null){
1381                                 Iterator<ReferenceEdge> edgeIter=srcLN.iteratorToReferencees();
1382                                 int taintIdentifier=0;
1383                                 while (edgeIter.hasNext()) {
1384                                         ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1385                                                         .next();
1386                                         HeapRegionNode refHRN=referenceEdge.getDst();
1387                                         taintIdentifier=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1388 //                                      taintIdentifier=referenceEdge.getSESETaintIdentifier();
1389
1390                                         // figure out which invar has related effects
1391                                         Hashtable<TempDescriptor, Integer> map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx();
1392                                         Set<TempDescriptor> keySet=map.keySet();
1393                                         for (Iterator iterator = keySet.iterator(); iterator
1394                                                         .hasNext();) {
1395                                                 TempDescriptor inVarTD = (TempDescriptor) iterator
1396                                                                 .next();
1397                                                 int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue());
1398                                                 if((inVarMask&taintIdentifier)>0){
1399                                                         // found related invar, contribute effects
1400                                                         currentSESE.readEffects(inVarTD, field.getSymbol(),src.getType(), refHRN);
1401                                                 }
1402                                         }
1403                                 }
1404
1405                                 // taint
1406                                 if(!field.getType().isImmutable()){
1407                                                 LabelNode dstLN = og.td2ln.get(dst);
1408                                                 edgeIter=dstLN.iteratorToReferencees();
1409                                                 while (edgeIter.hasNext()) {
1410                                                         ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1411                                                                         .next();
1412                                                         currentSESE.getSeseEffectsSet().mapEdgeToTaint(referenceEdge, taintIdentifier);
1413 //                                                      referenceEdge.unionSESETaintIdentifier(taintIdentifier);
1414                                                 }
1415                                 }
1416                         }
1417
1418
1419                 }
1420                         break;
1421
1422                 case FKind.FlatOpNode:{
1423
1424                         FlatOpNode fon=(FlatOpNode)fn;
1425                         TempDescriptor dest=fon.getDest();
1426                         TempDescriptor src=fon.getLeft();
1427
1428                         if(currentSESE.getInVarSet().contains(src)){
1429                                 int idx=currentSESE.getSeseEffectsSet().getInVarIdx(src);
1430                                 if(idx==-1){
1431                                         break;
1432                                 }
1433
1434                                 //mark dest's edges for corresponding  sese live in-var.
1435                                 LabelNode srcLN = og.td2ln.get(dest);
1436                                 if (srcLN != null) {
1437                                         Iterator<ReferenceEdge> refEdgeIter=srcLN.iteratorToReferencees();
1438                                         while (refEdgeIter.hasNext()) {
1439                                                 ReferenceEdge edge = refEdgeIter.next();
1440                                                 int newTaint = (int) Math.pow(2, idx);
1441 //                                              System.out.println("fon="+fon);
1442 //                                              System.out.println(currentSESE+" src:"+src+"->"+"dest:"+dest+" with taint="+newTaint);
1443 //                                              System.out.println("referenceEdge="+edge);
1444                                                 currentSESE.getSeseEffectsSet().mapEdgeToTaint(edge, newTaint);
1445 //                                              System.out.println("after tainting="+edge.getSESETaintIdentifier());
1446                                         }
1447                                 }
1448                         }
1449                 }break;
1450
1451                 case FKind.FlatElementNode:{
1452
1453                         FlatElementNode fsen=(FlatElementNode)fn;
1454                         TempDescriptor src = fsen.getSrc();
1455                         TempDescriptor dst = fsen.getDst();
1456                         String field="___element_";
1457
1458                         LabelNode srcLN = og.td2ln.get(src);
1459                         int taintIdentifier=0;
1460                         if(srcLN!=null){
1461                                 Iterator<ReferenceEdge> edgeIter=srcLN.iteratorToReferencees();
1462                                 while (edgeIter.hasNext()) {
1463                                         ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1464                                                         .next();
1465                                         HeapRegionNode dstHRN=referenceEdge.getDst();
1466                                         taintIdentifier=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1467 //                                      taintIdentifier=referenceEdge.getSESETaintIdentifier();
1468
1469                                         // figure out which invar has related effects
1470                                         Hashtable<TempDescriptor, Integer> map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx();
1471                                         Set<TempDescriptor> keySet=map.keySet();
1472                                         for (Iterator iterator = keySet.iterator(); iterator
1473                                                         .hasNext();) {
1474                                                 TempDescriptor inVarTD = (TempDescriptor) iterator
1475                                                                 .next();
1476                                                 int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue());
1477                                                 if((inVarMask&taintIdentifier)>0){
1478                                                         // found related invar, contribute effects
1479                                                         currentSESE.readEffects(inVarTD, field,src.getType(), dstHRN);
1480                                                 }
1481                                         }
1482
1483                                 }
1484                         }
1485
1486                         // taint
1487                         LabelNode dstLN = og.td2ln.get(dst);
1488                         if(dstLN!=null){
1489                                 Iterator<ReferenceEdge> edgeIter=dstLN.iteratorToReferencees();
1490                                 while (edgeIter.hasNext()) {
1491                                         ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1492                                                         .next();
1493                                         currentSESE.getSeseEffectsSet().mapEdgeToTaint(referenceEdge, taintIdentifier);
1494 //                                      referenceEdge.unionSESETaintIdentifier(taintIdentifier);
1495                                 }
1496                         }
1497
1498                 }break;
1499
1500                 case FKind.FlatSetElementNode: {
1501
1502                         FlatSetElementNode fsen = (FlatSetElementNode) fn;
1503                         TempDescriptor dst = fsen.getDst();
1504                         TypeDescriptor  tdElement = dst.getType().dereference();
1505
1506                         String field = "___element_";
1507
1508                         LabelNode dstLN=og.td2ln.get(dst);
1509                         if(dst!=null){
1510
1511                                 Iterator<ReferenceEdge> edgeIter=dstLN.iteratorToReferencees();
1512                                 while (edgeIter.hasNext()) {
1513                                         ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1514                                                         .next();
1515                                         HeapRegionNode dstHRN=referenceEdge.getDst();
1516                                         int edgeTaint=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1517 //                                      int edgeTaint=referenceEdge.getSESETaintIdentifier();
1518
1519                                         // we can do a strong update here if one of two cases
1520                                         // holds
1521                                         boolean strongUpdate=false;
1522                                         if (field != null && !dst.getType().isImmutable()
1523                                                         && ((dstHRN.getNumReferencers() == 1) || // case 1
1524                                                         (dstHRN.isSingleObject() && dstLN
1525                                                                         .getNumReferencees() == 1) // case 2
1526                                                         )) {
1527                                                 strongUpdate = true;
1528                                         }
1529
1530
1531                                         // figure out which invar has related effects
1532                                         Hashtable<TempDescriptor, Integer> map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx();
1533                                         Set<TempDescriptor> keySet=map.keySet();
1534                                         for (Iterator iterator = keySet.iterator(); iterator
1535                                                         .hasNext();) {
1536                                                 TempDescriptor inVarTD = (TempDescriptor) iterator
1537                                                                 .next();
1538                                                 int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue());
1539                                                 if((inVarMask&edgeTaint)>0){
1540                                                         // found related invar, contribute effects
1541                                                         currentSESE.writeEffects(inVarTD, field, dst.getType(),dstHRN, strongUpdate);
1542                                         }
1543                                 }
1544
1545
1546                         }
1547
1548                         }
1549
1550                 }break;
1551
1552                 case FKind.FlatSetFieldNode: {
1553
1554                         FlatSetFieldNode fsen = (FlatSetFieldNode) fn;
1555                         TempDescriptor dst = fsen.getDst();
1556                         FieldDescriptor field = fsen.getField();
1557
1558                         LabelNode dstLN = og.td2ln.get(dst);
1559                         if(dstLN!=null){
1560
1561                                 Iterator<ReferenceEdge> edgeIter=dstLN.iteratorToReferencees();
1562                                 while (edgeIter.hasNext()) {
1563                                         ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1564                                                         .next();
1565                                         HeapRegionNode dstHRN=referenceEdge.getDst();
1566                                         int edgeTaint=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1567 //                                      int edgeTaint=referenceEdge.getSESETaintIdentifier();
1568
1569                                         // we can do a strong update here if one of two cases
1570                                         // holds
1571                                         boolean strongUpdate=false;
1572                                         if (field != null && !field.getType().isImmutable()
1573                                                         && field != OwnershipAnalysis
1574                                                                         .getArrayField(field.getType())
1575                                                         && ((dstHRN.getNumReferencers() == 1) || // case 1
1576                                                         (dstHRN.isSingleObject() && dstLN
1577                                                                         .getNumReferencees() == 1) // case 2
1578                                                         )) {
1579                                                 strongUpdate = true;
1580                                         }
1581
1582
1583                                         // figure out which invar has related effects
1584                                         Hashtable<TempDescriptor, Integer> map = currentSESE
1585                                                         .getSeseEffectsSet().getMapTempDescToInVarIdx();
1586                                         Set<TempDescriptor> keySet = map.keySet();
1587                                         for (Iterator iterator = keySet.iterator(); iterator
1588                                                         .hasNext();) {
1589                                                 TempDescriptor inVarTD = (TempDescriptor) iterator
1590                                                                 .next();
1591                                                 int inVarMask = (int) Math.pow(2, map.get(inVarTD)
1592                                                                 .intValue());
1593                                                 if ((inVarMask & edgeTaint) > 0) {
1594                                                         // found related invar, contribute effects
1595                                                         currentSESE.writeEffects(inVarTD,
1596                                                                         field.getSymbol(), dst.getType(), dstHRN,
1597                                                                         strongUpdate);
1598                                                 }
1599                                         }
1600
1601
1602                         }
1603                         }
1604                 }
1605                         break;
1606
1607                 case FKind.FlatCall: {
1608                         FlatCall fc = (FlatCall) fn;
1609
1610                         MethodContext calleeMC = ownAnalysis.getCalleeMethodContext(mc, fc);
1611
1612                         MethodEffects me = ownAnalysis.getMethodEffectsAnalysis()
1613                                         .getMethodEffectsByMethodContext(calleeMC);
1614
1615                         OwnershipGraph calleeOG = ownAnalysis
1616                                         .getOwnvershipGraphByMethodContext(calleeMC);
1617
1618
1619                         FlatMethod fm = state.getMethodFlat(fc.getMethod());
1620                         ParameterDecomposition decomp = new ParameterDecomposition(
1621                                         ownAnalysis, fc, fm, calleeMC, calleeOG, og);
1622
1623                         int base=0;
1624                         if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
1625                                 base = 0;
1626                         } else {
1627                                 base = 1;
1628                         }
1629
1630                         for (int i = 0; i < fc.numArgs()+base; i++) {
1631
1632                                 TempDescriptor arg ;
1633                                 Set<EffectsKey> readSet;
1634                                 Set<EffectsKey> writeSet;
1635                                 Set<EffectsKey> strongUpdateSet;
1636
1637                                 int paramIdx=0;
1638
1639                                 boolean isThis=false;
1640                                 if(i==fc.numArgs()){
1641                                         paramIdx=0;
1642                                          arg = fc.getThis();
1643                                                 Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx);
1644                                                 Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx);
1645                                                  readSet = me.getEffects().getReadingSet(
1646                                                                 0);
1647                                                  writeSet = me.getEffects().getWritingSet(
1648                                                                 0);
1649                                                  strongUpdateSet = me.getEffects()
1650                                                                 .getStrongUpdateSet(0);
1651                                                  isThis=true;
1652                                 }else{
1653                                         paramIdx=i + base;
1654                                          arg = fc.getArg(i);
1655                                          readSet = me.getEffects().getReadingSet(
1656                                                         i + base);
1657                                          writeSet = me.getEffects().getWritingSet(
1658                                                         i + base);
1659                                          strongUpdateSet = me.getEffects()
1660                                                         .getStrongUpdateSet(i + base);
1661                                 }
1662
1663                                 LabelNode argLN = og.td2ln.get(arg);
1664                                 if(     argLN!=null){
1665                                         Iterator<ReferenceEdge> edgeIter=argLN.iteratorToReferencees();
1666                                         while (edgeIter.hasNext()) {
1667                                                 ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter
1668                                                                 .next();
1669                                                 HeapRegionNode dstHRN=referenceEdge.getDst();
1670                                                 int edgeTaint=currentSESE.getSeseEffectsSet().getTaint(referenceEdge);
1671 //                                              int edgeTaint=referenceEdge.getSESETaintIdentifier();
1672
1673                                                 // figure out which invar has related effects
1674                                                 Hashtable<TempDescriptor, Integer> map = currentSESE
1675                                                                 .getSeseEffectsSet().getMapTempDescToInVarIdx();
1676                                                 Set<TempDescriptor> keySet = map.keySet();
1677                                                 for (Iterator iterator = keySet.iterator(); iterator
1678                                                                 .hasNext();) {
1679                                                         TempDescriptor inVarTD = (TempDescriptor) iterator
1680                                                                         .next();
1681                                                         int inVarMask = (int) Math.pow(2, map.get(inVarTD)
1682                                                                         .intValue());
1683
1684                                                         if ((inVarMask & edgeTaint) > 0) {
1685                                                                 // found related invar, contribute effects
1686
1687                                                                 if (readSet != null) {
1688                                                                         Iterator<EffectsKey> readIter = readSet
1689                                                                                         .iterator();
1690                                                                         while (readIter.hasNext()) {
1691                                                                                 EffectsKey key = readIter.next();
1692                                                                                 Set<Integer> hrnSet = getCallerHRNId(
1693                                                                                                 new Integer(paramIdx), calleeOG,
1694                                                                                                 key.getHRNId(), decomp);
1695                                                                                 Iterator<Integer> hrnIter = hrnSet
1696                                                                                                 .iterator();
1697                                                                                 while (hrnIter.hasNext()) {
1698                                                                                         Integer hrnID = (Integer) hrnIter
1699                                                                                                         .next();
1700
1701                                                                                         HeapRegionNode refHRN = og.id2hrn
1702                                                                                                         .get(hrnID);
1703
1704                                                                                         currentSESE.readEffects(inVarTD, key
1705                                                                                                         .getFieldDescriptor(), key
1706                                                                                                         .getTypeDescriptor(), refHRN);
1707
1708                                                                                 }
1709                                                                         }
1710                                                                 }
1711
1712                                                                 if (writeSet != null) {
1713                                                                         Iterator<EffectsKey> writeIter = writeSet
1714                                                                                         .iterator();
1715                                                                         while (writeIter.hasNext()) {
1716                                                                                 EffectsKey key = writeIter.next();
1717
1718                                                                                 Set<Integer> hrnSet = getCallerHRNId(
1719                                                                                                 new Integer(paramIdx), calleeOG,
1720                                                                                                 key.getHRNId(), decomp);
1721                                                                                 Iterator<Integer> hrnIter = hrnSet
1722                                                                                                 .iterator();
1723                                                                                 while (hrnIter.hasNext()) {
1724                                                                                         Integer hrnID = (Integer) hrnIter
1725                                                                                                         .next();
1726
1727                                                                                         HeapRegionNode refHRN = og.id2hrn
1728                                                                                                         .get(hrnID);
1729
1730                                                                                         currentSESE.writeEffects(inVarTD,
1731                                                                                                         key.getFieldDescriptor(), key
1732                                                                                                                         .getTypeDescriptor(),
1733                                                                                                         refHRN, false);
1734                                                                                 }
1735
1736                                                                         }
1737                                                                 }
1738
1739                                                                 if (strongUpdateSet != null) {
1740                                                                         Iterator<EffectsKey> strongUpdateIter = strongUpdateSet
1741                                                                                         .iterator();
1742                                                                         while (strongUpdateIter.hasNext()) {
1743                                                                                 EffectsKey key = strongUpdateIter
1744                                                                                                 .next();
1745
1746                                                                                 Set<Integer> hrnSet = getCallerHRNId(
1747                                                                                                 new Integer(paramIdx),
1748                                                                                                 calleeOG, key.getHRNId(),
1749                                                                                                 decomp);
1750                                                                                 Iterator<Integer> hrnIter = hrnSet
1751                                                                                                 .iterator();
1752                                                                                 while (hrnIter.hasNext()) {
1753                                                                                         Integer hrnID = (Integer) hrnIter
1754                                                                                                         .next();
1755
1756                                                                                         HeapRegionNode refHRN = og.id2hrn
1757                                                                                                         .get(hrnID);
1758
1759                                                                                         currentSESE.writeEffects(inVarTD,
1760                                                                                                         key.getFieldDescriptor(),
1761                                                                                                         key.getTypeDescriptor(),
1762                                                                                                         refHRN, true);
1763                                                                                 }
1764                                                                         }
1765                                                                 } // end of     if (strongUpdateSet != null)
1766
1767                                                         } // end of if ((inVarMask & edgeTaint) > 0)
1768                                                 }
1769
1770                                         }
1771                                 }
1772
1773                         }
1774
1775                 }
1776                         break;
1777
1778                 }
1779         }
1780
1781         private void flagAllocationSite(MethodContext mc, AllocationSite ac){
1782                 HashSet<AllocationSite> set=mapMethodContextToLiveInAllocationSiteSet.get(mc);
1783                 if(set==null){
1784                         set=new HashSet<AllocationSite>();
1785                 }
1786                 set.add(ac);
1787                 mapMethodContextToLiveInAllocationSiteSet.put(mc, set);
1788         }
1789
1790         private void followReference(HeapRegionNode hrn,HashSet<TempDescriptor> tdSet, HashSet<HeapRegionNode> visited, FlatSESEEnterNode currentSESE){
1791
1792                 Iterator<ReferenceEdge> referIter=hrn.iteratorToReferencers();
1793                 // check whether hrn is referenced by TD
1794                 while (referIter.hasNext()) {
1795                         ReferenceEdge referEdge = (ReferenceEdge) referIter.next();
1796                         if(referEdge.getSrc() instanceof LabelNode){
1797                                 LabelNode ln=(LabelNode)referEdge.getSrc();
1798                                 if(currentSESE.getInVarSet().contains(ln.getTempDescriptor())){
1799                                         tdSet.add(ln.getTempDescriptor());
1800                                 }
1801                         }else if(referEdge.getSrc() instanceof HeapRegionNode){
1802                                 HeapRegionNode nextHRN=(HeapRegionNode)referEdge.getSrc();
1803                                 if(!visited.contains(nextHRN)){
1804                                         visited.add(nextHRN);
1805                                         followReference(nextHRN,tdSet,visited,currentSESE);
1806                                 }
1807
1808                         }
1809                 }
1810
1811         }
1812
1813         private Set<Integer> getCallerHRNId(Integer paramIdx,
1814                         OwnershipGraph calleeOG, Integer calleeHRNId,
1815                         ParameterDecomposition paramDecom) {
1816
1817                 Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx);
1818                 Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx);
1819
1820                 if (calleeHRNId.equals(hrnPrimaryID)) {
1821                         // it references to primary param heap region
1822                         return paramDecom.getParamObject_hrnIDs(paramIdx);
1823                 } else if (calleeHRNId.equals(hrnSecondaryID)) {
1824                         // it references to secondary param heap region
1825                         return paramDecom.getParamReachable_hrnIDs(paramIdx);
1826                 }
1827
1828                 return new HashSet<Integer>();
1829         }
1830
1831         private void taintLabelNode(LabelNode ln, int identifier, SESEEffectsSet effectSet) {
1832
1833                 Iterator<ReferenceEdge> edgeIter = ln.iteratorToReferencees();
1834                 while (edgeIter.hasNext()) {
1835                         ReferenceEdge edge = edgeIter.next();
1836                         effectSet.mapEdgeToTaint(edge, identifier);
1837                 }
1838
1839         }
1840
1841         private HashSet<HeapRegionNode> getReferenceHeapIDSet(OwnershipGraph og, TempDescriptor td){
1842
1843                 HashSet<HeapRegionNode> returnSet=new HashSet<HeapRegionNode>();
1844
1845                 LabelNode ln=og.td2ln.get(td);
1846                 if(ln!=null){
1847                         Iterator<ReferenceEdge> edgeIter=ln.iteratorToReferencees();
1848                         while(edgeIter.hasNext()){
1849                                 ReferenceEdge edge=edgeIter.next();
1850                                         HeapRegionNode hrn=edge.getDst();
1851                                         returnSet.add(hrn);
1852                         }
1853                 }
1854                 return returnSet;
1855         }
1856
1857
1858         private HashSet<ReferenceEdge> getRefEdgeSetReferenceToSameHRN(
1859                         OwnershipGraph og, TempDescriptor td) {
1860
1861                 HashSet<ReferenceEdge> returnSet = new HashSet<ReferenceEdge>();
1862
1863                 HashSet<HeapRegionNode> heapIDs = getReferenceHeapIDSet(og, td);
1864                 for (Iterator<HeapRegionNode> iterator = heapIDs.iterator(); iterator
1865                                 .hasNext();) {
1866                         HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next();
1867                         Iterator<ReferenceEdge> referenceeIter = heapRegionNode
1868                                         .iteratorToReferencees();
1869                         while (referenceeIter.hasNext()) {
1870                                 ReferenceEdge edge = (ReferenceEdge) referenceeIter.next();
1871                                 if (edge.getSrc() instanceof HeapRegionNode) {
1872                                         returnSet.add(edge);
1873                                 }
1874                         }
1875                 }
1876                 return returnSet;
1877         }
1878
1879         private HashSet<TempDescriptor> getTempDescSetReferenceToSameHRN(
1880                         OwnershipGraph og, TempDescriptor td) {
1881
1882                 HashSet<TempDescriptor> returnSet = new HashSet<TempDescriptor>();
1883
1884                 HashSet<HeapRegionNode> heapIDs = getReferenceHeapIDSet(og, td);
1885                 for (Iterator<HeapRegionNode> iterator = heapIDs.iterator(); iterator
1886                                 .hasNext();) {
1887                         HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next();
1888                         Iterator<ReferenceEdge> referencerIter = heapRegionNode
1889                                         .iteratorToReferencers();
1890                         while (referencerIter.hasNext()) {
1891                                 ReferenceEdge edge = (ReferenceEdge) referencerIter.next();
1892                                 if (edge.getSrc() instanceof LabelNode) {
1893                                         LabelNode ln = (LabelNode) edge.getSrc();
1894                                         returnSet.add(ln.getTempDescriptor());
1895                                 }
1896                         }
1897                 }
1898                 return returnSet;
1899         }
1900
1901         private void DFSVisit( MethodDescriptor md,
1902                          LinkedList<MethodDescriptor> sorted,
1903                         HashSet<MethodDescriptor> discovered, JavaCallGraph javaCallGraph) {
1904
1905                 discovered.add(md);
1906
1907                 Iterator itr = javaCallGraph.getCallerSet(md).iterator();
1908                 while (itr.hasNext()) {
1909                         MethodDescriptor mdCaller = (MethodDescriptor) itr.next();
1910
1911                         if (!discovered.contains(mdCaller)) {
1912                                 DFSVisit(mdCaller, sorted, discovered, javaCallGraph);
1913                         }
1914                 }
1915
1916                 sorted.addFirst(md);
1917         }
1918
1919
1920         private LinkedList<MethodDescriptor> topologicalSort(Set set,
1921                         JavaCallGraph javaCallGraph) {
1922                 HashSet<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1923                 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1924
1925                 Iterator<MethodDescriptor> itr = set.iterator();
1926                 while (itr.hasNext()) {
1927                         MethodDescriptor md = itr.next();
1928
1929                         if (!discovered.contains(md)) {
1930                                 DFSVisit(md, sorted, discovered, javaCallGraph);
1931                         }
1932                 }
1933
1934                 return sorted;
1935         }
1936
1937         private void calculateCovering(ConflictGraph conflictGraph){
1938                 uniqueLockSetId=0; // reset lock counter for every new conflict graph
1939                 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1940                 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1941                 HashSet<SESELock> lockSet=new HashSet<SESELock>();
1942
1943                 HashSet<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1944                 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1945                         ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1946                         if(conflictEdge.getType()==ConflictEdge.FINE_GRAIN_EDGE){
1947                                 fineToCover.add(conflictEdge);
1948                         }else if(conflictEdge.getType()==ConflictEdge.COARSE_GRAIN_EDGE){
1949                                 coarseToCover.add(conflictEdge);
1950                         }
1951                 }
1952
1953                 HashSet<ConflictEdge> toCover=new HashSet<ConflictEdge>();
1954                 toCover.addAll(fineToCover);
1955                 toCover.addAll(coarseToCover);
1956
1957                 while (!toCover.isEmpty()) {
1958
1959                         SESELock seseLock = new SESELock();
1960                         seseLock.setID(uniqueLockSetId++);
1961
1962                         boolean changed;
1963
1964                         do{     // fine-grained edge
1965
1966                                 changed=false;
1967
1968                                 for (Iterator iterator = fineToCover.iterator(); iterator
1969                                                 .hasNext();) {
1970
1971                                         int type;
1972                                         ConflictEdge edge = (ConflictEdge) iterator.next();
1973                                         if(seseLock.getConflictNodeSet().size()==0){
1974                                                 //initial setup
1975                                                 if(seseLock.isWriteNode(edge.getVertexU())){
1976                                                         // mark as fine_write
1977                                                         if(edge.getVertexU() instanceof StallSiteNode){
1978                                                                 type=ConflictNode.PARENT_WRITE;
1979                                                         }else{
1980                                                                 type=ConflictNode.FINE_WRITE;
1981                                                         }
1982                                                         seseLock.addConflictNode(edge.getVertexU(), type);
1983                                                 }else{
1984                                                         // mark as fine_read
1985                                                         if(edge.getVertexU() instanceof StallSiteNode){
1986                                                                 type=ConflictNode.PARENT_READ;
1987                                                         }else{
1988                                                                 type=ConflictNode.FINE_READ;
1989                                                         }
1990                                                         seseLock.addConflictNode(edge.getVertexU(), type);
1991                                                 }
1992                                                 if(edge.getVertexV()!=edge.getVertexU()){
1993                                                         if(seseLock.isWriteNode(edge.getVertexV())){
1994                                                                 // mark as fine_write
1995                                                                 if(edge.getVertexV() instanceof StallSiteNode){
1996                                                                         type=ConflictNode.PARENT_WRITE;
1997                                                                 }else{
1998                                                                         type=ConflictNode.FINE_WRITE;
1999                                                                 }
2000                                                                 seseLock.addConflictNode(edge.getVertexV(), type);
2001                                                         }else{
2002                                                                 // mark as fine_read
2003                                                                 if(edge.getVertexV() instanceof StallSiteNode){
2004                                                                         type=ConflictNode.PARENT_READ;
2005                                                                 }else{
2006                                                                         type=ConflictNode.FINE_READ;
2007                                                                 }
2008                                                                 seseLock.addConflictNode(edge.getVertexV(), type);
2009                                                         }
2010                                                 }
2011                                                 changed=true;
2012                                                 seseLock.addConflictEdge(edge);
2013                                                 fineToCover.remove(edge);
2014                                                 break;// exit iterator loop
2015                                         }// end of initial setup
2016
2017                                         ConflictNode newNode;
2018                                         if((newNode=seseLock.getNewNodeConnectedWithGroup(edge))!=null){
2019                                                 // new node has a fine-grained edge to all current node
2020                                                 // If there is a coarse grained edge where need a fine edge, it's okay to add the node
2021                                                 // but the edge must remain uncovered.
2022
2023                                                 changed=true;
2024
2025                                                 if(seseLock.isWriteNode(newNode)){
2026                                                         if(newNode instanceof StallSiteNode){
2027                                                                 type=ConflictNode.PARENT_WRITE;
2028                                                         }else{
2029                                                                 type=ConflictNode.FINE_WRITE;
2030                                                         }
2031                                                         seseLock.setNodeType(newNode,type);
2032                                                 }else{
2033                                                         if(newNode instanceof StallSiteNode){
2034                                                                 type=ConflictNode.PARENT_READ;
2035                                                         }else{
2036                                                                 type=ConflictNode.FINE_READ;
2037                                                         }
2038                                                         seseLock.setNodeType(newNode,type);
2039                                                 }
2040
2041                                                 seseLock.addEdge(edge);
2042                                                 HashSet<ConflictEdge> edgeSet=newNode.getEdgeSet();
2043                                                 for (Iterator iterator2 = edgeSet.iterator(); iterator2
2044                                                                 .hasNext();) {
2045                                                         ConflictEdge conflictEdge = (ConflictEdge) iterator2
2046                                                                         .next();
2047
2048
2049                                                         // mark all fine edges between new node and nodes in the group as covered
2050                                                         if(!conflictEdge.getVertexU().equals(newNode)){
2051                                                                 if(seseLock.containsConflictNode(conflictEdge.getVertexU())){
2052                                                                         changed=true;
2053                                                                         seseLock.addConflictEdge(conflictEdge);
2054                                                                         fineToCover.remove(conflictEdge);
2055                                                                 }
2056                                                         }else if(!conflictEdge.getVertexV().equals(newNode)){
2057                                                                 if(seseLock.containsConflictNode(conflictEdge.getVertexV())){
2058                                                                         changed=true;
2059                                                                         seseLock.addConflictEdge(conflictEdge);
2060                                                                         fineToCover.remove(conflictEdge);
2061                                                                 }
2062                                                         }
2063
2064                                                 }
2065
2066                                                 break;// exit iterator loop
2067                                         }
2068                                 }
2069
2070                         }while(changed);
2071                         do{             // coarse
2072                                 changed=false;
2073                                 int type;
2074                                 for (Iterator iterator = coarseToCover.iterator(); iterator
2075                                 .hasNext();) {
2076
2077                                         ConflictEdge edge = (ConflictEdge) iterator.next();
2078
2079                                         if(seseLock.getConflictNodeSet().size()==0){
2080                                                 //initial setup
2081                                                 if(seseLock.hasSelfCoarseEdge(edge.getVertexU())){
2082                                                         // node has a coarse-grained edge with itself
2083                                                         if(!(edge.getVertexU() instanceof StallSiteNode)){
2084                                                                 // and it is not parent
2085                                                                 type=ConflictNode.SCC;
2086                                                         }else{
2087                                                                 type=ConflictNode.PARENT_COARSE;
2088                                                         }
2089                                                         seseLock.addConflictNode(edge.getVertexU(), type);
2090                                                 }else{
2091                                                         if(edge.getVertexU() instanceof StallSiteNode){
2092                                                                 type=ConflictNode.PARENT_COARSE;
2093                                                         }else{
2094                                                                 type=ConflictNode.COARSE;
2095                                                         }
2096                                                         seseLock.addConflictNode(edge.getVertexU(), type);
2097                                                 }
2098                                                 if(seseLock.hasSelfCoarseEdge(edge.getVertexV())){
2099                                                         // node has a coarse-grained edge with itself
2100                                                         if(!(edge.getVertexV() instanceof StallSiteNode)){
2101                                                                 // and it is not parent
2102                                                                 type=ConflictNode.SCC;
2103                                                         }else{
2104                                                                 type=ConflictNode.PARENT_COARSE;
2105                                                         }
2106                                                         seseLock.addConflictNode(edge.getVertexV(), type);
2107                                                 }else{
2108                                                         if(edge.getVertexV() instanceof StallSiteNode){
2109                                                                 type=ConflictNode.PARENT_COARSE;
2110                                                         }else{
2111                                                                 type=ConflictNode.COARSE;
2112                                                         }
2113                                                         seseLock.addConflictNode(edge.getVertexV(), type);
2114                                                 }
2115                                                 changed=true;
2116                                                 coarseToCover.remove(edge);
2117                                                 seseLock.addConflictEdge(edge);
2118                                                 break;// exit iterator loop
2119                                         }// end of initial setup
2120
2121
2122                                         ConflictNode newNode;
2123                                         if((newNode=seseLock.getNewNodeConnectedWithGroup(edge))!=null){
2124                                                 // new node has a coarse-grained edge to all fine-read, fine-write, parent
2125                                                 changed=true;
2126
2127                                                 if(seseLock.hasSelfCoarseEdge(newNode)){
2128                                                         //SCC
2129                                                         if(newNode instanceof StallSiteNode){
2130                                                                 type=ConflictNode.PARENT_COARSE;
2131                                                         }else{
2132                                                                 type=ConflictNode.SCC;
2133                                                         }
2134                                                         seseLock.setNodeType(newNode, type);
2135                                                 }else{
2136                                                         if(newNode instanceof StallSiteNode){
2137                                                                 type=ConflictNode.PARENT_COARSE;
2138                                                         }else{
2139                                                                 type=ConflictNode.COARSE;
2140                                                         }
2141                                                         seseLock.setNodeType(newNode, type);
2142                                                 }
2143
2144                                                 seseLock.addEdge(edge);
2145                                                 HashSet<ConflictEdge> edgeSet=newNode.getEdgeSet();
2146                                                 for (Iterator iterator2 = edgeSet.iterator(); iterator2
2147                                                                 .hasNext();) {
2148                                                         ConflictEdge conflictEdge = (ConflictEdge) iterator2
2149                                                                         .next();
2150                                                         // mark all coarse edges between new node and nodes in the group as covered
2151                                                         if(!conflictEdge.getVertexU().equals(newNode)){
2152                                                                 if(seseLock.containsConflictNode(conflictEdge.getVertexU())){
2153                                                                         changed=true;
2154                                                                         seseLock.addConflictEdge(conflictEdge);
2155                                                                         coarseToCover.remove(conflictEdge);
2156                                                                 }
2157                                                         }else if(!conflictEdge.getVertexV().equals(newNode)){
2158                                                                 if(seseLock.containsConflictNode(conflictEdge.getVertexV())){
2159                                                                         changed=true;
2160                                                                         seseLock.addConflictEdge(conflictEdge);
2161                                                                         coarseToCover.remove(conflictEdge);
2162                                                                 }
2163                                                         }
2164
2165                                                 }
2166                                                 break;// exit iterator loop
2167                                         }
2168
2169                                 }
2170
2171                         }while(changed);
2172                         lockSet.add(seseLock);
2173
2174                         toCover.clear();
2175                         toCover.addAll(fineToCover);
2176                         toCover.addAll(coarseToCover);
2177
2178                 }
2179
2180                 conflictGraphLockMap.put(conflictGraph, lockSet);
2181         }
2182
2183         private void synthesizeLocks(){
2184                 Set<Entry<FlatNode,ConflictGraph>> graphEntrySet=conflictGraphResults.entrySet();
2185                 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
2186                         Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator
2187                                         .next();
2188                         FlatNode sese=graphEntry.getKey();
2189                         ConflictGraph conflictGraph=graphEntry.getValue();
2190                         calculateCovering(conflictGraph);
2191                 }
2192         }
2193
2194         private void makeConflictGraph() {
2195                 Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze
2196                                 .iterator();
2197                 while (methItr.hasNext()) {
2198                         Descriptor d = methItr.next();
2199                         FlatMethod fm = state.getMethodFlat(d);
2200
2201                         HashSet<MethodContext> mcSet = ownAnalysisForSESEConflicts
2202                                         .getAllMethodContextSetByDescriptor(fm.getMethod());
2203                         Iterator<MethodContext> mcIter = mcSet.iterator();
2204
2205                         while (mcIter.hasNext()) {
2206                                 MethodContext mc = mcIter.next();
2207                                 OwnershipGraph og=ownAnalysisForSESEConflicts.getOwnvershipGraphByMethodContext(mc);
2208
2209                                 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
2210                                 flatNodesToVisit.add(fm);
2211
2212                                 Set<FlatNode> visited = new HashSet<FlatNode>();
2213
2214                                 SESESummary summary = new SESESummary(null, fm);
2215                                 seseSummaryMap.put(fm, summary);
2216
2217                                 Hashtable<TempDescriptor, TempDescriptor> invarMap=new Hashtable<TempDescriptor,TempDescriptor>();
2218
2219                                 while (!flatNodesToVisit.isEmpty()) {
2220                                         Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
2221                                         FlatNode fn = fnItr.next();
2222
2223                                         flatNodesToVisit.remove(fn);
2224                                         visited.add(fn);
2225
2226                                         // Adding Stall Node of current program statement
2227                                         ParentChildConflictsMap currentConflictsMap = conflictsResults
2228                                                         .get(fn);
2229
2230                                         Hashtable<TempDescriptor, StallSite> stallMap = currentConflictsMap
2231                                                         .getStallMap();
2232
2233                                         Set<Entry<TempDescriptor, StallSite>> entrySet = stallMap
2234                                                         .entrySet();
2235
2236                                         SESESummary seseSummary = seseSummaryMap.get(fn);
2237
2238                                         ConflictGraph conflictGraph = null;
2239                                         conflictGraph = conflictGraphResults.get(seseSummary
2240                                                         .getCurrentSESE());
2241
2242                                         if (conflictGraph == null) {
2243                                                 conflictGraph = new ConflictGraph(og);
2244                                         }
2245                                         for (Iterator<Entry<TempDescriptor, StallSite>> iterator2 = entrySet
2246                                                         .iterator(); iterator2.hasNext();) {
2247                                                 Entry<TempDescriptor, StallSite> entry = iterator2
2248                                                                 .next();
2249                                                 TempDescriptor td = entry.getKey();
2250                                                 StallSite stallSite = entry.getValue();
2251
2252                                                 // reachability set
2253                                                 og = ownAnalysisForSESEConflicts
2254                                                                 .getOwnvershipGraphByMethodContext(mc);
2255                                                 Set<Set> reachabilitySet = calculateReachabilitySet(og,
2256                                                                 td);
2257                                                 conflictGraph.addStallNode(td, fm, stallSite,
2258                                                                 reachabilitySet);
2259
2260                                         }
2261
2262                                         if (conflictGraph.id2cn.size() > 0) {
2263                                                 conflictGraphResults.put(seseSummary.getCurrentSESE(),
2264                                                                 conflictGraph);
2265                                         }
2266
2267                                         conflictGraph_nodeAction(mc, fm, fn,invarMap);
2268
2269                                         for (int i = 0; i < fn.numNext(); i++) {
2270                                                 FlatNode nn = fn.getNext(i);
2271                                                 if (!visited.contains(nn)) {
2272                                                         flatNodesToVisit.add(nn);
2273                                                 }
2274                                         }
2275                                 } // end of while(flatNodesToVisit)
2276
2277                         } // end of while(mcIter)
2278
2279                 }
2280
2281                 // decide fine-grain edge or coarse-grain edge among all vertexes by pair-wise comparison
2282         Enumeration<FlatNode> keyEnum1=conflictGraphResults.keys();
2283                 while (keyEnum1.hasMoreElements()) {
2284                         FlatNode flatNode = (FlatNode) keyEnum1.nextElement();
2285                         ConflictGraph conflictGraph=conflictGraphResults.get(flatNode);
2286                         conflictGraph.analyzeConflicts();
2287                         conflictGraphResults.put(flatNode, conflictGraph);
2288                 }
2289
2290         }
2291
2292         private Set<Set> calculateReachabilitySet(OwnershipGraph og,
2293                         TempDescriptor tempDescriptor) {
2294                 // reachability set
2295                 Set<Set> reachabilitySet = new HashSet();
2296                 LabelNode ln = og.td2ln.get(tempDescriptor);
2297                 if(ln!=null){
2298                         Iterator<ReferenceEdge> refEdgeIter = ln.iteratorToReferencees();
2299                         while (refEdgeIter.hasNext()) {
2300                                 ReferenceEdge referenceEdge = (ReferenceEdge) refEdgeIter.next();
2301
2302                                 ReachabilitySet set = referenceEdge.getBeta();
2303                                 Iterator<TokenTupleSet> ttsIter = set.iterator();
2304                                 while (ttsIter.hasNext()) {
2305                                         TokenTupleSet tokenTupleSet = (TokenTupleSet) ttsIter.next();
2306
2307                                         HashSet<GloballyUniqueTokenTuple> newTokenTupleSet = new HashSet<GloballyUniqueTokenTuple>();
2308                                         // reachabilitySet.add(tokenTupleSet);
2309
2310                                         Iterator iter = tokenTupleSet.iterator();
2311                                         while (iter.hasNext()) {
2312                                                 TokenTuple tt = (TokenTuple) iter.next();
2313                                                 int token = tt.getToken();
2314                                                 String uniqueID = og.id2hrn.get(new Integer(token))
2315                                                                 .getGloballyUniqueIdentifier();
2316                                                 GloballyUniqueTokenTuple gtt = new GloballyUniqueTokenTuple(
2317                                                                 uniqueID, tt);
2318                                                 newTokenTupleSet.add(gtt);
2319                                         }
2320
2321                                         reachabilitySet.add(newTokenTupleSet);
2322                                 }
2323                         }
2324                 }
2325
2326                 return reachabilitySet;
2327         }
2328
2329         private ReachabilitySet packupStates(OwnershipGraph og, HeapRegionNode hrn) {
2330
2331                 ReachabilitySet betaSet = new ReachabilitySet().makeCanonical();
2332
2333                 Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
2334                 while (itrEdge.hasNext()) {
2335                         ReferenceEdge edge = itrEdge.next();
2336                         betaSet = betaSet.union(edge.getBeta());
2337                 }
2338
2339                 return betaSet;
2340
2341         }
2342
2343         private ReachabilitySet packupStates(OwnershipGraph og, AllocationSite as) {
2344
2345                 ReachabilitySet betaSet = new ReachabilitySet().makeCanonical();
2346                 assert as!=null;
2347                 HeapRegionNode hrnSummary = og.id2hrn.get(as.getSummary());
2348                 if(hrnSummary!=null){
2349                         Iterator<ReferenceEdge> itrEdge = hrnSummary.iteratorToReferencers();
2350                         while (itrEdge.hasNext()) {
2351                                 ReferenceEdge edge = itrEdge.next();
2352                                 betaSet = betaSet.union(edge.getBeta());
2353                         }
2354                 }
2355
2356                 // check for other nodes
2357                 for (int i = 0; i < as.getAllocationDepth(); ++i) {
2358
2359                         HeapRegionNode hrnIthOldest = og.id2hrn.get(as.getIthOldest(i));
2360 //                      betaSet = new ReachabilitySet().makeCanonical();
2361 //                      itrEdge = hrnIthOldest.iteratorToReferencees();
2362                         Iterator<ReferenceEdge> itrEdge = hrnIthOldest.iteratorToReferencers();
2363                         while (itrEdge.hasNext()) {
2364                                 ReferenceEdge edge = itrEdge.next();
2365                                 betaSet = betaSet.union(edge.getBeta());
2366                         }
2367                 }
2368
2369                 Iterator<TokenTupleSet> ttSetIter = betaSet.iterator();
2370                 while (ttSetIter.hasNext()) {
2371                         TokenTupleSet tokenTupleSet = (TokenTupleSet) ttSetIter.next();
2372                         Iterator iter = tokenTupleSet.iterator();
2373                         while (iter.hasNext()) {
2374                                 TokenTuple tt = (TokenTuple) iter.next();
2375                                 int token = tt.getToken();
2376                                 String uniqueID = og.id2hrn.get(new Integer(token))
2377                                                 .getGloballyUniqueIdentifier();
2378                                 GloballyUniqueTokenTuple gtt = new GloballyUniqueTokenTuple(
2379                                                 uniqueID, tt);
2380                         }
2381                 }
2382                 return betaSet;
2383         }
2384
2385         private void conflictGraph_nodeAction(MethodContext mc, FlatMethod fm,
2386                         FlatNode fn,Hashtable<TempDescriptor, TempDescriptor> invarMap) {
2387
2388                 switch (fn.kind()) {
2389
2390                 case FKind.FlatSESEEnterNode: {
2391
2392                         FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
2393                         OwnershipGraph og = ownAnalysisForSESEConflicts
2394                                         .getOwnvershipGraphByMethodContext(mc);
2395
2396                         if (!fsen.getIsCallerSESEplaceholder()) {
2397                                 Set<TempDescriptor> invar_set = fsen.getInVarSet();
2398
2399                                 SESESummary seseSummary=seseSummaryMap.get(fsen);
2400                                 ConflictGraph conflictGraph=null;
2401                                 conflictGraph=conflictGraphResults.get(seseSummary.getCurrentParent());
2402
2403                                 if(conflictGraph==null){
2404                                         conflictGraph = new ConflictGraph(og);
2405                                 }
2406
2407
2408                                 for (Iterator iterator = invar_set.iterator(); iterator
2409                                                 .hasNext();) {
2410                                         TempDescriptor tempDescriptor = (TempDescriptor) iterator
2411                                                         .next();
2412
2413                                         if(!tempDescriptor.getType().isArray() && tempDescriptor.getType().isImmutable()){
2414                                                 continue;
2415                                         }
2416
2417                                         // effects set
2418                                         SESEEffectsSet seseEffectsSet = fsen.getSeseEffectsSet();
2419                                         Set<SESEEffectsKey> readEffectsSet = seseEffectsSet
2420                                                         .getReadingSet(tempDescriptor);
2421
2422                                         if (readEffectsSet != null) {
2423                                                 for (Iterator iterator2 = readEffectsSet.iterator(); iterator2
2424                                                                 .hasNext();) {
2425                                                         SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator2
2426                                                                         .next();
2427                                                         String uniqueID = seseEffectsKey.getHRNUniqueId();
2428                                                         HeapRegionNode node = og.gid2hrn.get(uniqueID);
2429                                                         if(node.isParameter()){
2430                                                                 seseEffectsKey.setRSet(packupStates(og,node));
2431                                                         }else{
2432                                                                 AllocationSite as = node.getAllocationSite();
2433                                                                 seseEffectsKey.setRSet(packupStates(og,as));
2434                                                         }
2435                                                 }
2436                                         }
2437
2438                                         if (readEffectsSet != null) {
2439                                                 for (Iterator iterator2 = readEffectsSet.iterator(); iterator2
2440                                                                 .hasNext();) {
2441                                                         SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator2
2442                                                         .next();
2443                                                 }
2444                                         }
2445                                         Set<SESEEffectsKey> writeEffectsSet = seseEffectsSet
2446                                                         .getWritingSet(tempDescriptor);
2447
2448                                         if (writeEffectsSet != null) {
2449                                                 for (Iterator iterator2 = writeEffectsSet.iterator(); iterator2
2450                                                                 .hasNext();) {
2451                                                         SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator2
2452                                                                         .next();
2453                                                         String uniqueID = seseEffectsKey.getHRNUniqueId();
2454                                                         HeapRegionNode node = og.gid2hrn.get(uniqueID);
2455
2456                                                         if(node.isParameter()){
2457                                                                 seseEffectsKey.setRSet(packupStates(og,node));
2458                                                         }else{
2459                                                                 AllocationSite as = node.getAllocationSite();
2460                                                                 seseEffectsKey.setRSet(packupStates(og,as));
2461                                                         }
2462                                                 }
2463                                         }
2464
2465                                         Set<SESEEffectsKey> strongUpdateSet = seseEffectsSet.getStrongUpdateSet(tempDescriptor);
2466
2467                                         Set<Set> reachabilitySet = calculateReachabilitySet(og,
2468                                                         tempDescriptor);
2469
2470                                         // add new live-in node
2471
2472                                         OwnershipGraph lastOG = ownAnalysis
2473                                         .getOwnvershipGraphByMethodContext(mc);
2474                                         LabelNode ln = lastOG.td2ln.get(tempDescriptor);
2475
2476
2477                                         Set<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
2478                                         Iterator<ReferenceEdge> refIter = ln
2479                                                         .iteratorToReferencees();
2480                                         while (refIter.hasNext()) {
2481                                                 ReferenceEdge referenceEdge = (ReferenceEdge) refIter
2482                                                                 .next();
2483                                                 //
2484                                                 SESEEffectsSet seseEffects=fsen.getSeseEffectsSet();
2485                                                 int taintIdentifier=fsen.getSeseEffectsSet().getTaint(referenceEdge);
2486                                                 int invarIdx=fsen.getSeseEffectsSet().getInVarIdx(tempDescriptor);
2487                                                 int inVarMask=(int) Math.pow(2,invarIdx);
2488                                                 if((inVarMask&taintIdentifier)>0){
2489                                                         // find tainted edge, add heap root to live-in node
2490                                                         hrnSet.add(referenceEdge.getDst());
2491                                                 }
2492                                                 //
2493                                         }
2494
2495                                         conflictGraph.addLiveInNode(tempDescriptor, hrnSet, fsen,
2496                                                         readEffectsSet, writeEffectsSet, strongUpdateSet, reachabilitySet);
2497                                 }
2498
2499
2500                                 if(conflictGraph.id2cn.size()>0){
2501                                         conflictGraphResults.put(seseSummary.getCurrentParent(),conflictGraph);
2502                                 }
2503
2504                         }
2505
2506                 }
2507
2508                         break;
2509
2510                 }
2511
2512         }
2513
2514         private void seseConflictsForward(JavaCallGraph javaCallGraph) {
2515
2516                 Set methodCallSet = javaCallGraph.getAllMethods(typeUtil.getMain());
2517
2518                 // topologically sort java call chain so that leaf calls are ordered
2519                 // first
2520                 LinkedList<MethodDescriptor> sortedMethodCalls = topologicalSort(
2521                                 methodCallSet, javaCallGraph);
2522
2523                 for (Iterator iterator = sortedMethodCalls.iterator(); iterator
2524                                 .hasNext();) {
2525
2526                         MethodDescriptor md = (MethodDescriptor) iterator.next();
2527
2528                         FlatMethod fm = state.getMethodFlat(md);
2529
2530                         HashSet<MethodContext> mcSet = ownAnalysis
2531                                         .getAllMethodContextSetByDescriptor(md);
2532                         Iterator<MethodContext> mcIter = mcSet.iterator();
2533
2534                         currentMethodSummary = new MethodSummary();
2535                         preeffectsSet = new HashSet<PreEffectsKey>();
2536
2537                         // iterates over all possible method context
2538                         while (mcIter.hasNext()) {
2539                                 MethodContext mc = mcIter.next();
2540
2541                                 LinkedList<FlatNode> flatNodesToVisit=new LinkedList<FlatNode>();
2542                                 flatNodesToVisit.add(fm);
2543
2544                                 SESESummary summary = new SESESummary(null, fm);
2545                                 seseSummaryMap.put(fm, summary);
2546
2547                                 Hashtable<TempDescriptor, TempDescriptor> invarMap=new Hashtable<TempDescriptor,TempDescriptor>();
2548
2549                                 while (!flatNodesToVisit.isEmpty()) {
2550                                         FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
2551                                         flatNodesToVisit.remove(fn);
2552                                         ParentChildConflictsMap prevResult = conflictsResults
2553                                                         .get(fn);
2554
2555                                         // merge sets from control flow
2556                                         Boolean prevSESE=null;
2557                                         ParentChildConflictsMap currentConflictsMap = new ParentChildConflictsMap();
2558                                         for (int i = 0; i < fn.numPrev(); i++) {
2559                                                 FlatNode prevFlatNode = fn.getPrev(i);
2560                                                 ParentChildConflictsMap incoming = conflictsResults
2561                                                                 .get(prevFlatNode);
2562                                                 if (incoming != null) {
2563                                                         currentConflictsMap.merge(incoming);
2564                                                 }
2565
2566                                                 if(prevFlatNode instanceof FlatCondBranch){
2567                                                         prevSESE=isAfterChildSESEIndicatorMap.get(prevFlatNode);
2568                                                 }
2569                                         }
2570                                         SESESummary currentSummary = seseSummaryMap.get(fn);
2571                                         //if (currentSummary == null) {
2572                                         if(!(fn instanceof FlatMethod)){
2573                                                 FlatNode current = null;
2574                                                 FlatNode currentParent = null;
2575                                                 // calculate sese summary info from previous flat nodes
2576
2577                                                 for (int i = 0; i < fn.numPrev(); i++) {
2578                                                         FlatNode prevFlatNode = fn.getPrev(i);
2579                                                         SESESummary prevSummary = seseSummaryMap
2580                                                                         .get(prevFlatNode);
2581                                                         if (prevSummary != null) {
2582                                                                 if (prevFlatNode instanceof FlatSESEExitNode
2583                                                                                 && !((FlatSESEExitNode) prevFlatNode)
2584                                                                                                 .getFlatEnter()
2585                                                                                                 .getIsCallerSESEplaceholder()) {
2586                                                                         current = prevSummary.getCurrentParent();
2587                                                                         SESESummary temp = seseSummaryMap
2588                                                                                         .get(current);
2589                                                                         currentParent = temp.getCurrentParent();
2590                                                                 } else {
2591                                                                         current = prevSummary.getCurrentSESE();
2592                                                                         currentParent = prevSummary
2593                                                                                         .getCurrentParent();
2594                                                                 }
2595
2596                                                                 break;
2597                                                         }
2598                                                 }
2599
2600                                                 currentSummary = new SESESummary(currentParent, current);
2601                                                 seseSummaryMap.put(fn, currentSummary);
2602                                         }
2603
2604                                         if(prevSESE!=null){
2605                                                 if(fn instanceof FlatSESEEnterNode){
2606                                                         isAfterChildSESEIndicatorMap.put(currentSummary.getCurrentSESE(), currentConflictsMap.isAfterSESE());
2607                                                 }else{
2608                                                         isAfterChildSESEIndicatorMap.put(currentSummary.getCurrentSESE(), prevSESE);
2609                                                 }
2610                                         }
2611
2612                                         Boolean b=isAfterChildSESEIndicatorMap.get(currentSummary.getCurrentSESE());;
2613                                         if(b==null){
2614                                                 currentConflictsMap.setIsAfterSESE(false);
2615                                         }else{
2616                                                 currentConflictsMap.setIsAfterSESE(b.booleanValue());
2617                                         }
2618
2619                                         FlatNode tempP=currentSummary.getCurrentParent();
2620                                         FlatNode tempS=currentSummary.getCurrentSESE();
2621
2622                                         conflicts_nodeAction(mc, fn, callGraph, preeffectsSet,
2623                                                         currentConflictsMap, currentSummary,invarMap);
2624
2625
2626                                         // if we have a new result, schedule forward nodes for
2627                                         // analysis
2628                                         if (!currentConflictsMap.equals(prevResult)) {
2629                                                 seseSummaryMap.put(fn, currentSummary);
2630                                                 conflictsResults.put(fn, currentConflictsMap);
2631                                                 for (int i = 0; i < fn.numNext(); i++) {
2632                                                         FlatNode nn = fn.getNext(i);
2633                                                         flatNodesToVisit.addFirst(nn);
2634                                                 }
2635                                         }
2636
2637                                 }
2638
2639                         }
2640
2641                 }
2642
2643         }
2644
2645
2646         private void conflicts_nodeAction(MethodContext mc, FlatNode fn,
2647                         CallGraph callGraph, HashSet<PreEffectsKey> preeffectsSet,
2648                         ParentChildConflictsMap currentConflictsMap,
2649                         SESESummary currentSummary,
2650                         Hashtable<TempDescriptor, TempDescriptor> invarMap) {
2651
2652                 OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc);
2653
2654                 currentConflictsMap.clearStallMap();
2655
2656                 switch (fn.kind()) {
2657
2658                 case FKind.FlatSESEEnterNode: {
2659
2660                         FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
2661
2662                         if (!fsen.getIsCallerSESEplaceholder()) {
2663                                 FlatNode parentNode = currentSummary.getCurrentSESE();
2664                                 currentSummary.setCurrentParent(parentNode);
2665                                 currentSummary.setCurrentSESE(fsen);
2666 //                              seseSummaryMap.put(fsen, currentSummary);
2667                         }
2668
2669                         if (!fsen.getIsCallerSESEplaceholder()) {
2670                                 currentMethodSummary.increaseChildSESECount();
2671                         }
2672                         if (currentMethodSummary.getChildSESECount() == 1) {
2673                                 // need to store pre-effects
2674                                 currentMethodSummary.getEffectsSet().addAll(preeffectsSet);
2675                                 for (Iterator iterator = currentMethodSummary.getEffectsSet()
2676                                                 .iterator(); iterator.hasNext();) {
2677                                         PreEffectsKey preEffectsKey = (PreEffectsKey) iterator
2678                                                         .next();
2679                                 }
2680                                 preeffectsSet.clear();
2681                         }
2682                 }
2683                         break;
2684
2685                 case FKind.FlatSESEExitNode: {
2686
2687                         FlatSESEExitNode fsen = (FlatSESEExitNode) fn;
2688
2689                         if (!fsen.getFlatEnter().getIsCallerSESEplaceholder()) {
2690                                 // all object variables are inaccessible.
2691                                 isAfterChildSESEIndicatorMap.put(currentSummary
2692                                                 .getCurrentParent(), new Boolean(true));
2693                         }
2694 //                      currentConflictsMap = new ParentChildConflictsMap();
2695                         currentConflictsMap.clear();
2696
2697                 }
2698                         break;
2699
2700                 case FKind.FlatCondBranch: {
2701                         boolean isAfterChildSESE = false;
2702                         FlatNode current = currentSummary.getCurrentSESE();
2703                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2704                         if (isAfter != null && isAfter.booleanValue()) {
2705                                 isAfterChildSESE = true;
2706                         }
2707                         isAfterChildSESEIndicatorMap.put(fn, new Boolean(isAfterChildSESE));
2708                 }
2709                 break;
2710
2711                 case FKind.FlatNew: {
2712
2713                         FlatNew fnew = (FlatNew) fn;
2714
2715                         boolean isAfterChildSESE = false;
2716                         FlatNode current = currentSummary.getCurrentSESE();
2717                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2718                         if (isAfter != null && isAfter.booleanValue()) {
2719                                 isAfterChildSESE = true;
2720                         }
2721
2722                         if (isAfterChildSESE) {
2723                                 TempDescriptor dst = fnew.getDst();
2724                                 currentConflictsMap.addAccessibleVar(dst);
2725                         }
2726
2727                 }
2728                         break;
2729
2730                 case FKind.FlatElementNode:{
2731
2732
2733                         FlatElementNode fen = (FlatElementNode) fn;
2734                         TempDescriptor src=fen.getSrc();
2735
2736                         boolean isAfterChildSESE = false;
2737                         FlatNode current = currentSummary.getCurrentSESE();
2738                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2739                         if (isAfter != null && isAfter.booleanValue()) {
2740                                 isAfterChildSESE = true;
2741                         }
2742
2743                         if(isAfterChildSESE){
2744
2745                                 if (!currentConflictsMap.isAccessible(src)) {
2746                                         if(invarMap.containsKey(src)){
2747                                                 currentConflictsMap.addStallSite(src, new HashSet<HeapRegionNode>(),
2748                                                                 new StallTag(fn),invarMap.get(src));
2749                                         }else{
2750                                                 currentConflictsMap.addStallSite(src, new HashSet<HeapRegionNode>(),
2751                                                                 new StallTag(fn),null);
2752                                         }
2753                                 }
2754                                 currentConflictsMap.addAccessibleVar(src);
2755
2756                                 // contribute read effect on source's stall site
2757                                 currentConflictsMap.contributeEffect(src, "", "",
2758                                                 StallSite.READ_EFFECT);
2759
2760                         }
2761
2762                         if (currentMethodSummary.getChildSESECount() == 0) {
2763                                 // analyze preeffects
2764                                 preEffectAnalysis(og, src, null, PreEffectsKey.READ_EFFECT);
2765                         }
2766
2767
2768                 } break;
2769
2770                 case FKind.FlatFieldNode: {
2771
2772                         FlatFieldNode ffn = (FlatFieldNode) fn;
2773                         TempDescriptor dst = ffn.getDst();
2774                         TempDescriptor src = ffn.getSrc();
2775                         FieldDescriptor field = ffn.getField();
2776
2777                         boolean isAfterChildSESE = false;
2778                         FlatNode current = currentSummary.getCurrentSESE();
2779                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2780                         if (isAfter != null && isAfter.booleanValue()) {
2781                                 isAfterChildSESE = true;
2782                         }
2783
2784                         if (isAfterChildSESE) {
2785
2786                                 if (!currentConflictsMap.isAccessible(src)) {
2787                                         HashSet<HeapRegionNode> refHRN = getReferenceHeapIDSet(
2788                                                         og, src);
2789                                         currentConflictsMap.addStallSite(src, refHRN,
2790                                                         new StallTag(fn),null);
2791
2792                                         // flag stall site for disjoint analysis
2793                                         for (Iterator iterator2 = refHRN.iterator(); iterator2
2794                                                         .hasNext();) {
2795                                                 HeapRegionNode hrn = (HeapRegionNode) iterator2
2796                                                                 .next();
2797                                                 if (hrn.isParameter()) {
2798                                                         // if stall site is paramter heap region, need
2799                                                         // to decompose into caller's
2800                                                         HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
2801                                                         visitedHRN.add(hrn);
2802                                                         setupRelatedAllocSiteAnalysis(og, mc, hrn,
2803                                                                         visitedHRN);
2804                                                 } else {
2805 //                                                      System.out.println("FLAGGED "+mc+":"+ffn);
2806                                                         flagAllocationSite(mc, hrn.getAllocationSite());
2807                                                 }
2808                                         }
2809
2810                                 }
2811                                 currentConflictsMap.addAccessibleVar(src);
2812
2813                                 // contribute read effect on source's stall site
2814                                 currentConflictsMap.contributeEffect(src, field
2815                                                 .getType().getSafeSymbol(), field.getSymbol(),
2816                                                 StallSite.READ_EFFECT);
2817
2818                                 if(field.getType().isImmutable()){
2819                                         currentConflictsMap.addAccessibleVar(dst);
2820                                 }
2821
2822                         }
2823
2824                         if (currentMethodSummary.getChildSESECount() == 0) {
2825                                 // analyze preeffects
2826                                 preEffectAnalysis(og, src, field, PreEffectsKey.READ_EFFECT);
2827                         }
2828
2829                 }
2830                         break;
2831
2832                 case FKind.FlatSetElementNode:{
2833
2834                         FlatSetElementNode fsen=(FlatSetElementNode)fn;
2835                         TempDescriptor dst = fsen.getDst();
2836                         TempDescriptor src = fsen.getSrc();
2837
2838                         boolean isAfterChildSESE = false;
2839                         FlatNode current = currentSummary.getCurrentSESE();
2840                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2841                         if (isAfter != null && isAfter.booleanValue()) {
2842                                 isAfterChildSESE = true;
2843                         }
2844
2845                         if (isAfterChildSESE) {
2846
2847                                 if (!currentConflictsMap.isAccessible(src)) {
2848                                         HashSet<HeapRegionNode> refHRN = getReferenceHeapIDSet(og,
2849                                                         src);
2850                                         currentConflictsMap.addStallSite(src, refHRN , new StallTag(
2851                                                         fn),null);
2852                                 }
2853                                 currentConflictsMap.addAccessibleVar(src);
2854
2855                                 if (!currentConflictsMap.isAccessible(dst)) {
2856                                         if(invarMap.containsKey(dst)){
2857                                                 currentConflictsMap.addStallSite(dst, new       HashSet<HeapRegionNode>(),
2858                                                                 new StallTag(fn),invarMap.get(dst));
2859                                         }else{
2860                                                 currentConflictsMap.addStallSite(dst, new       HashSet<HeapRegionNode>(),
2861                                                                 new StallTag(fn),null);
2862                                         }
2863                                 }
2864                                 currentConflictsMap.addAccessibleVar(dst);
2865                                 // contribute write effect on destination's stall site
2866                                 currentConflictsMap.contributeEffect(dst, "","",
2867                                                 StallSite.WRITE_EFFECT);
2868
2869                         }
2870
2871                         if (currentMethodSummary.getChildSESECount() == 0) {
2872                                 // analyze preeffects
2873                                 preEffectAnalysis(og, dst, null, PreEffectsKey.WRITE_EFFECT);
2874                         }
2875
2876                 } break;
2877
2878                 case FKind.FlatSetFieldNode: {
2879
2880                         FlatSetFieldNode fsen = (FlatSetFieldNode) fn;
2881                         TempDescriptor dst = fsen.getDst();
2882                         FieldDescriptor field = fsen.getField();
2883                         TempDescriptor src = fsen.getSrc();
2884
2885                         boolean isAfterChildSESE = false;
2886                         FlatNode current = currentSummary.getCurrentSESE();
2887                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2888                         if (isAfter != null && isAfter.booleanValue()) {
2889                                 isAfterChildSESE = true;
2890                         }
2891
2892                         if (isAfterChildSESE) {
2893
2894                                 if (!currentConflictsMap.isAccessible(src)) {
2895                                         HashSet<HeapRegionNode> refHRN = getReferenceHeapIDSet(og,
2896                                                         src);
2897                                         currentConflictsMap.addStallSite(src, refHRN, new StallTag(
2898                                                         fn),null);
2899
2900                                         // flag stall site for disjoint analysis
2901                                         for (Iterator iterator2 = refHRN.iterator(); iterator2
2902                                                         .hasNext();) {
2903                                                 HeapRegionNode hrn = (HeapRegionNode) iterator2.next();
2904
2905                                                 if (hrn.isParameter()) {
2906                                                         // if stall site is paramter heap region, need
2907                                                         // to decompose into caller's
2908                                                         HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
2909                                                         visitedHRN.add(hrn);
2910                                                         setupRelatedAllocSiteAnalysis(og, mc, hrn,
2911                                                                         visitedHRN);
2912                                                 } else {
2913                                                         flagAllocationSite(mc, hrn.getAllocationSite());
2914                                                 }
2915
2916                                         }
2917
2918                                 }
2919                                 currentConflictsMap.addAccessibleVar(src);
2920
2921
2922                                 if (!currentConflictsMap.isAccessible(dst)) {
2923                                         HashSet<HeapRegionNode> refHRN = getReferenceHeapIDSet(
2924                                                         og, dst);
2925                                         currentConflictsMap.addStallSite(dst, refHRN,
2926                                                         new StallTag(fn),null);
2927
2928                                         // flag stall site for disjoint analysis
2929                                         for (Iterator iterator2 = refHRN.iterator(); iterator2
2930                                                         .hasNext();) {
2931                                                 HeapRegionNode hrn = (HeapRegionNode) iterator2
2932                                                                 .next();
2933                                                 if (hrn.isParameter()) {
2934                                                         // if stall site is paramter heap region, need
2935                                                         // to decompose into caller's
2936                                                         HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
2937                                                         visitedHRN.add(hrn);
2938                                                         setupRelatedAllocSiteAnalysis(og, mc, hrn,
2939                                                                         visitedHRN);
2940                                                 } else {
2941                                                         flagAllocationSite(mc, hrn.getAllocationSite());
2942                                                 }
2943                                         }
2944                                 }
2945
2946                                 currentConflictsMap.addAccessibleVar(dst);
2947                                 // contribute write effect on destination's stall site
2948                                 currentConflictsMap.contributeEffect(dst, field
2949                                                 .getType().getSafeSymbol(), field.getSymbol(),
2950                                                 StallSite.WRITE_EFFECT);
2951
2952
2953                                 // TODO need to create edge mapping for newly created edge
2954                                 HashSet<ReferenceEdge> edges = getRefEdgeSetReferenceToSameHRN(
2955                                                 og, dst);
2956
2957                                 StallSite ss = currentConflictsMap.getStallMap().get(dst);
2958                                 if (ss != null) {
2959                                         for (Iterator iterator = edges.iterator(); iterator
2960                                                         .hasNext();) {
2961                                                 ReferenceEdge referenceEdge = (ReferenceEdge) iterator
2962                                                                 .next();
2963                                                 if (!(referenceEdge.getSrc() instanceof LabelNode)) {
2964                                                         currentConflictsMap.addStallEdge(referenceEdge,
2965                                                                         new StallTag(fn));
2966                                                 }
2967                                         }
2968                                 }
2969                         }
2970
2971                         if (currentMethodSummary.getChildSESECount() == 0) {
2972                                 // analyze preeffects
2973                                 preEffectAnalysis(og, dst, field, PreEffectsKey.WRITE_EFFECT);
2974                         }
2975
2976                 }
2977                         break;
2978
2979                 case FKind.FlatOpNode: {
2980
2981                         FlatOpNode fon = (FlatOpNode) fn;
2982
2983                         boolean isAfterChildSESE = false;
2984                         FlatNode current = currentSummary.getCurrentSESE();
2985                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
2986
2987
2988                         if( fon.getOp().getOp() ==Operation.ASSIGN){
2989                                 invarMap.put(fon.getDest(), fon.getLeft());
2990                         }
2991
2992                         if (isAfter != null && isAfter.booleanValue()) {
2993                                 isAfterChildSESE = true;
2994                         }
2995
2996                         if (isAfterChildSESE) {
2997
2998                                 // destination variable gets the status of source.
2999
3000                                 if (fon.getOp().getOp() == Operation.ASSIGN) {
3001
3002                                         TempDescriptor dst = fon.getDest();
3003                                         TempDescriptor src = fon.getLeft();
3004
3005                                         Integer sourceStatus = currentConflictsMap
3006                                                         .getAccessibleMap().get(src);
3007                                         if (sourceStatus == null) {
3008                                                 sourceStatus = ParentChildConflictsMap.INACCESSIBLE;
3009                                         }
3010
3011                                         HashSet<TempDescriptor> dstTempSet = getTempDescSetReferenceToSameHRN(
3012                                                         og, dst);
3013
3014                                         for (Iterator<TempDescriptor> iterator = dstTempSet
3015                                                         .iterator(); iterator.hasNext();) {
3016                                                 TempDescriptor possibleDst = iterator.next();
3017
3018                                                 if (sourceStatus
3019                                                                 .equals(ParentChildConflictsMap.ACCESSIBLE)) {
3020                                                         currentConflictsMap.addAccessibleVar(possibleDst);
3021                                                 } else {
3022                                                         currentConflictsMap.addInaccessibleVar(possibleDst);
3023
3024                                                 }
3025
3026                                         }
3027                                 }
3028
3029                         }
3030                 }
3031                         break;
3032
3033                 case FKind.FlatCall: {
3034
3035                         FlatCall fc = (FlatCall) fn;
3036
3037                         boolean isAfterChildSESE = false;
3038                         FlatNode current = currentSummary.getCurrentSESE();
3039                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
3040                         if (isAfter != null && isAfter.booleanValue()) {
3041                                 isAfterChildSESE = true;
3042                         }
3043
3044                         int base = 0;
3045                         if (!fc.getMethod().isStatic()) {
3046                                 base = 1;
3047                         }
3048
3049                         FlatMethod calleeFM = state.getMethodFlat(fc.getMethod());
3050
3051                         // retrieve callee's method summary
3052                         MethodSummary calleeMethodSummary = methodSummaryResults
3053                                         .get(calleeFM);
3054
3055                         if (calleeMethodSummary != null
3056                                         && calleeMethodSummary.getChildSESECount() > 0) {
3057
3058                                 // when parameter variable is accessible,
3059                                 // use callee's preeffects to figure out about how it affects
3060                                 // caller's stall site
3061
3062                                 for (int i = 0; i < fc.numArgs(); i++) {
3063                                         TempDescriptor paramTemp = fc.getArg(i);
3064
3065                                         if (isAfterChildSESE) {
3066                                                 if (currentConflictsMap.isAccessible(paramTemp)
3067                                                                 && currentConflictsMap.hasStallSite(paramTemp)) {
3068                                                         // preeffect contribute its effect to caller's stall
3069                                                         // site
3070
3071                                                         int offset = 0;
3072                                                         if (!fc.getMethod().isStatic()) {
3073                                                                 offset = 1;
3074                                                         }
3075
3076                                                         HashSet<PreEffectsKey> preeffectSet = calleeMethodSummary
3077                                                                         .getEffectsSetByParamIdx(i + offset);
3078
3079                                                         for (Iterator iterator = preeffectSet.iterator(); iterator
3080                                                                         .hasNext();) {
3081                                                                 PreEffectsKey preEffectsKey = (PreEffectsKey) iterator
3082                                                                                 .next();
3083                                                                 currentConflictsMap.contributeEffect(paramTemp,
3084                                                                                 preEffectsKey.getType(), preEffectsKey
3085                                                                                                 .getField(), preEffectsKey
3086                                                                                                 .getEffectType());
3087                                                         }
3088                                                 }
3089                                         }
3090                                         // in other cases, child SESE has not been discovered,
3091                                         // assumes that all variables are accessible
3092
3093                                 }
3094
3095                                 // If callee has at least one child sese, all parent object
3096                                 // is going to be inaccessible.
3097                                 // currentConflictsMap = new ParentChildConflictsMap();
3098                                 currentConflictsMap.makeAllInaccessible();
3099                                 isAfterChildSESEIndicatorMap.put(currentSummary
3100                                                 .getCurrentSESE(), new Boolean(true));
3101
3102                                 TempDescriptor returnTemp = fc.getReturnTemp();
3103
3104                                 if (calleeMethodSummary.getReturnValueAccessibility().equals(
3105                                                 MethodSummary.ACCESSIBLE)) {
3106                                         // when return value is accessible, associate with its
3107                                         // stall site
3108                                         currentConflictsMap.addAccessibleVar(returnTemp);
3109
3110                                         StallSite returnStallSite = calleeMethodSummary
3111                                                         .getReturnStallSite().copy();
3112                                         // handling parameter regions
3113                                         HashSet<Integer> stallParamIdx = returnStallSite
3114                                                         .getCallerParamIdxSet();
3115                                         for (Iterator iterator = stallParamIdx.iterator(); iterator
3116                                                         .hasNext();) {
3117                                                 Integer idx = (Integer) iterator.next();
3118
3119                                                 int paramIdx = idx.intValue() - base;
3120                                                 TempDescriptor paramTD = fc.getArg(paramIdx);
3121
3122                                                 // TODO: resolve callee's parameter heap regions by
3123                                                 // following call chain
3124
3125                                         }
3126
3127                                         // flag stall site's allocation sites for disjointness
3128                                         // analysis
3129                                         HashSet<HeapRegionNode> hrnSet = returnStallSite
3130                                                         .getHRNSet();
3131                                         for (Iterator iterator = hrnSet.iterator(); iterator
3132                                                         .hasNext();) {
3133                                                 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
3134                                                 if (hrn.isParameter()) {
3135                                                         // if stall site is paramter heap region, need to
3136                                                         // decompose into caller's
3137                                                         HashSet<HeapRegionNode> visitedHRN = new HashSet<HeapRegionNode>();
3138                                                         visitedHRN.add(hrn);
3139                                                         setupRelatedAllocSiteAnalysis(og, mc, hrn,
3140                                                                         visitedHRN);
3141                                                 } else {
3142                                                         flagAllocationSite(mc, hrn.getAllocationSite());
3143                                                 }
3144                                         }
3145
3146                                         currentConflictsMap.addStallSite(returnTemp,
3147                                                         returnStallSite);
3148
3149                                 } else if (calleeMethodSummary.getReturnValueAccessibility()
3150                                                 .equals(MethodSummary.INACCESSIBLE)) {
3151                                         // when return value is inaccessible
3152                                         currentConflictsMap.addInaccessibleVar(returnTemp);
3153                                 }
3154
3155                                 // TODO: need to handle edge mappings from callee
3156                                 Set<Integer> stallParamIdx = calleeMethodSummary
3157                                                 .getStallParamIdxSet();
3158                                 for (Iterator iterator = stallParamIdx.iterator(); iterator
3159                                                 .hasNext();) {
3160                                         Integer paramIdx = (Integer) iterator.next();
3161                                         HashSet<StallTag> stallTagSet = calleeMethodSummary
3162                                                         .getStallTagByParamIdx(paramIdx);
3163
3164                                         int argIdx = paramIdx.intValue() - base;
3165                                         TempDescriptor argTD = fc.getArg(argIdx);
3166
3167                                         putStallTagOnReferenceEdges(og, argTD, stallTagSet,
3168                                                         currentConflictsMap);
3169                                 }
3170                         }
3171
3172                 }
3173                         break;
3174
3175                 /*
3176                  * do we need this case? case FKind.FlatLiteralNode: {
3177                  *
3178                  * if (currentConflictsMap.isAfterChildSESE()) { FlatLiteralNode fln =
3179                  * (FlatLiteralNode) fn; TempDescriptor dst = fln.getDst();
3180                  * currentConflictsMap.addAccessibleVar(dst); }
3181                  *
3182                  * } break;
3183                  */
3184
3185                 case FKind.FlatReturnNode: {
3186
3187                         FlatReturnNode frn = (FlatReturnNode) fn;
3188                         TempDescriptor returnTD = frn.getReturnTemp();
3189
3190                         boolean isAfterChildSESE = false;
3191                         FlatNode current = currentSummary.getCurrentSESE();
3192                         Boolean isAfter = isAfterChildSESEIndicatorMap.get(current);
3193                         if (isAfter != null && isAfter.booleanValue()) {
3194                                 isAfterChildSESE = true;
3195                         }
3196
3197                         if (returnTD != null) {
3198                                 if (!isAfterChildSESE) {
3199                                         // in this case, all variables are accessible. There are no
3200                                         // child SESEs.
3201                                 } else {
3202                                         if (currentConflictsMap.isAccessible(returnTD)) {
3203
3204                                                 currentMethodSummary
3205                                                                 .setReturnValueAccessibility(MethodSummary.ACCESSIBLE);
3206                                                 StallSite returnStallSite = currentConflictsMap
3207                                                                 .getStallMap().get(returnTD);
3208
3209                                                 HashSet<HeapRegionNode> stallSiteHRNSet = returnStallSite
3210                                                                 .getHRNSet();
3211                                                 for (Iterator iterator = stallSiteHRNSet.iterator(); iterator
3212                                                                 .hasNext();) {
3213                                                         HeapRegionNode stallSiteHRN = (HeapRegionNode) iterator
3214                                                                         .next();
3215                                                         Set<Integer> paramSet = og.idPrimary2paramIndexSet
3216                                                                         .get(stallSiteHRN.getID());
3217                                                         returnStallSite.addCallerParamIdxSet(paramSet);
3218                                                         paramSet = og.idSecondary2paramIndexSet
3219                                                                         .get(stallSiteHRN.getID());
3220                                                         returnStallSite.addCallerParamIdxSet(paramSet);
3221                                                 }
3222
3223                                                 currentMethodSummary
3224                                                                 .setReturnStallSite(returnStallSite);
3225
3226                                         } else {
3227                                                 currentMethodSummary
3228                                                                 .setReturnValueAccessibility(MethodSummary.INACCESSIBLE);
3229                                         }
3230                                 }
3231                         }
3232                 }
3233                         break;
3234
3235                 case FKind.FlatExit: {
3236
3237                         // store method summary when it has at least one child SESE
3238                         if (currentMethodSummary.getChildSESECount() > 0) {
3239                                 // current flat method
3240                                 FlatMethod fm = state.getMethodFlat(mc.getDescriptor());
3241                                 Set<TempDescriptor> stallTempSet = currentConflictsMap
3242                                                 .getStallMap().keySet();
3243                                 for (Iterator iterator = stallTempSet.iterator(); iterator
3244                                                 .hasNext();) {
3245                                         TempDescriptor stallTD = (TempDescriptor) iterator.next();
3246                                         StallSite stallSite = currentConflictsMap.getStallMap()
3247                                                         .get(stallTD);
3248
3249                                         HashSet<HeapRegionNode> stallSiteHRNSet = stallSite
3250                                                         .getHRNSet();
3251                                         for (Iterator iterator2 = stallSiteHRNSet.iterator(); iterator2
3252                                                         .hasNext();) {
3253                                                 HeapRegionNode stallSiteHRN = (HeapRegionNode) iterator2
3254                                                                 .next();
3255
3256                                                 if (stallSiteHRN.isParameter()) {
3257
3258                                                         Set<Integer> paramSet = og.idPrimary2paramIndexSet
3259                                                                         .get(stallSiteHRN.getID());
3260                                                         currentMethodSummary.addStallParamIdxSet(paramSet,
3261                                                                         stallSite.getStallTagSet());
3262
3263                                                         paramSet = og.idSecondary2paramIndexSet
3264                                                                         .get(stallSiteHRN.getID());
3265                                                         currentMethodSummary.addStallParamIdxSet(paramSet,
3266                                                                         stallSite.getStallTagSet());
3267                                                 }
3268
3269                                         }
3270
3271                                 }
3272                                 methodSummaryResults.put(fm, currentMethodSummary);
3273                         }
3274                 }
3275                         break;
3276
3277                 }
3278
3279 //              seseSummaryMap.put(fn, currentSummary);
3280
3281         }
3282
3283         private void putStallTagOnReferenceEdges(OwnershipGraph og,
3284                         TempDescriptor argTD, HashSet stallTagSet,
3285                         ParentChildConflictsMap currentConflictsMap) {
3286
3287                 LabelNode ln=og.td2ln.get(argTD);
3288                 if(ln!=null){
3289
3290                         Iterator<ReferenceEdge> refrenceeIter=ln.iteratorToReferencees();
3291                         while (refrenceeIter.hasNext()) {
3292                                 ReferenceEdge refEdge = (ReferenceEdge) refrenceeIter.next();
3293                                 HeapRegionNode stallHRN=refEdge.getDst();
3294
3295                                 Iterator<ReferenceEdge> referencerIter=stallHRN.iteratorToReferencers();
3296                                 while (referencerIter.hasNext()) {
3297                                         ReferenceEdge referencer = (ReferenceEdge) referencerIter
3298                                                         .next();
3299                                         for (Iterator iterator = stallTagSet.iterator(); iterator
3300                                                         .hasNext();) {
3301                                                 StallTag stallTag = (StallTag) iterator.next();
3302                                                 currentConflictsMap.addStallEdge(referencer, stallTag);
3303                                         }
3304                                 }
3305                         }
3306                 }
3307         }
3308
3309         private void preEffectAnalysis(OwnershipGraph og, TempDescriptor td,
3310                         FieldDescriptor field, Integer effectType) {
3311
3312                 // analyze preeffects
3313                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(og, td);
3314                 for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) {
3315                         HeapRegionNode hrn = (HeapRegionNode) iterator.next();
3316                         if (hrn.isParameter()) {
3317                                 // effects on param heap region
3318
3319                                 Set<Integer> paramSet = og.idPrimary2paramIndexSet.get(hrn
3320                                                 .getID());
3321
3322                                 if (paramSet != null) {
3323                                         Iterator<Integer> paramIter = paramSet.iterator();
3324                                         while (paramIter.hasNext()) {
3325                                                 Integer paramID = paramIter.next();
3326                                                 PreEffectsKey effectKey=null;
3327                                                 if(field!=null){
3328                                                         effectKey = new PreEffectsKey(paramID,
3329                                                                         field.getSymbol(), field.getType()
3330                                                                                         .getSafeSymbol(), effectType);
3331                                                 }else{
3332                                                         effectKey = new PreEffectsKey(paramID,
3333                                                                         "", "", effectType);
3334                                                 }
3335                                                 preeffectsSet.add(effectKey);
3336                                         }
3337                                 }
3338
3339                                 // check weather this heap region is parameter
3340                                 // reachable...
3341
3342                                 paramSet = og.idSecondary2paramIndexSet.get(hrn.getID());
3343                                 if (paramSet != null) {
3344                                         Iterator<Integer> paramIter = paramSet.iterator();
3345
3346                                         while (paramIter.hasNext()) {
3347                                                 Integer paramID = paramIter.next();
3348                                                 PreEffectsKey effectKey=null;
3349                                                 if(field!=null){
3350                                                         effectKey = new PreEffectsKey(paramID,
3351                                                                         field.getSymbol(), field.getType()
3352                                                                                         .getSafeSymbol(), effectType);
3353                                                 }else{
3354                                                         effectKey = new PreEffectsKey(paramID,
3355                                                                         "", "", effectType);
3356                                                 }
3357                                                 preeffectsSet.add(effectKey);
3358                                         }
3359                                 }
3360
3361                         }
3362                 }
3363         }
3364
3365   private void codePlansForward( FlatMethod fm ) {
3366
3367     // start from flat method top, visit every node in
3368     // method exactly once
3369     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
3370     flatNodesToVisit.add( fm );
3371
3372     Set<FlatNode> visited = new HashSet<FlatNode>();
3373
3374     while( !flatNodesToVisit.isEmpty() ) {
3375       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
3376       FlatNode fn = fnItr.next();
3377
3378       flatNodesToVisit.remove( fn );
3379       visited.add( fn );
3380
3381       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
3382       assert seseStack != null;
3383
3384       // use incoming results as "dot statement" or just
3385       // before the current statement
3386       VarSrcTokTable dotSTtable = new VarSrcTokTable();
3387       for( int i = 0; i < fn.numPrev(); i++ ) {
3388         FlatNode nn = fn.getPrev( i );
3389         dotSTtable.merge( variableResults.get( nn ) );
3390       }
3391
3392       // find dt-st notAvailableSet also
3393       Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
3394       for( int i = 0; i < fn.numPrev(); i++ ) {
3395         FlatNode nn = fn.getPrev( i );
3396         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
3397         if( notAvailIn != null ) {
3398           dotSTnotAvailSet.addAll( notAvailIn );
3399         }
3400       }
3401
3402       Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
3403
3404       if( !seseStack.empty() ) {
3405         codePlans_nodeActions( fn,
3406                                dotSTlive,
3407                                dotSTtable,
3408                                dotSTnotAvailSet,
3409                                seseStack.peek()
3410                                );
3411       }
3412
3413       for( int i = 0; i < fn.numNext(); i++ ) {
3414         FlatNode nn = fn.getNext( i );
3415
3416         if( !visited.contains( nn ) ) {
3417           flatNodesToVisit.add( nn );
3418         }
3419       }
3420     }
3421   }
3422
3423   private void codePlans_nodeActions( FlatNode fn,
3424                                       Set<TempDescriptor> liveSetIn,
3425                                       VarSrcTokTable vstTableIn,
3426                                       Set<TempDescriptor> notAvailSetIn,
3427                                       FlatSESEEnterNode currentSESE ) {
3428
3429     CodePlan plan = new CodePlan( currentSESE);
3430
3431     switch( fn.kind() ) {
3432
3433     case FKind.FlatSESEEnterNode: {
3434       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
3435       assert fsen.equals( currentSESE );
3436
3437       // track the source types of the in-var set so generated
3438       // code at this SESE issue can compute the number of
3439       // dependencies properly
3440       Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
3441       while( inVarItr.hasNext() ) {
3442         TempDescriptor inVar = inVarItr.next();
3443
3444         // when we get to an SESE enter node we change the
3445         // currentSESE variable of this analysis to the
3446         // child that is declared by the enter node, so
3447         // in order to classify in-vars correctly, pass
3448         // the parent SESE in--at other FlatNode types just
3449         // use the currentSESE
3450         VSTWrapper vstIfStatic = new VSTWrapper();
3451         Integer srcType =
3452           vstTableIn.getRefVarSrcType( inVar,
3453                                        fsen.getParent(),
3454                                        vstIfStatic
3455                                        );
3456
3457         // the current SESE needs a local space to track the dynamic
3458         // variable and the child needs space in its SESE record
3459         if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
3460           fsen.addDynamicInVar( inVar );
3461           fsen.getParent().addDynamicVar( inVar );
3462
3463         } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
3464           fsen.addStaticInVar( inVar );
3465           VariableSourceToken vst = vstIfStatic.vst;
3466           fsen.putStaticInVar2src( inVar, vst );
3467           fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
3468                                                       vst.getAge()
3469                                                     )
3470                                 );
3471         } else {
3472           assert srcType.equals( VarSrcTokTable.SrcType_READY );
3473           fsen.addReadyInVar( inVar );
3474         }
3475       }
3476
3477     } break;
3478
3479     case FKind.FlatSESEExitNode: {
3480       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
3481     } break;
3482
3483     case FKind.FlatOpNode: {
3484       FlatOpNode fon = (FlatOpNode) fn;
3485
3486       if( fon.getOp().getOp() == Operation.ASSIGN ) {
3487         TempDescriptor lhs = fon.getDest();
3488         TempDescriptor rhs = fon.getLeft();
3489
3490         // if this is an op node, don't stall, copy
3491         // source and delay until we need to use value
3492
3493         // ask whether lhs and rhs sources are dynamic, static, etc.
3494         VSTWrapper vstIfStatic = new VSTWrapper();
3495         Integer lhsSrcType
3496           = vstTableIn.getRefVarSrcType( lhs,
3497                                          currentSESE,
3498                                          vstIfStatic
3499                                          );
3500         Integer rhsSrcType
3501           = vstTableIn.getRefVarSrcType( rhs,
3502                                          currentSESE,
3503                                          vstIfStatic
3504                                          );
3505
3506         if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
3507           // if rhs is dynamic going in, lhs will definitely be dynamic
3508           // going out of this node, so track that here
3509           plan.addDynAssign( lhs, rhs );
3510           currentSESE.addDynamicVar( lhs );
3511           currentSESE.addDynamicVar( rhs );
3512
3513         } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
3514           // otherwise, if the lhs is dynamic, but the rhs is not, we
3515           // need to update the variable's dynamic source as "current SESE"
3516           plan.addDynAssign( lhs );
3517         }
3518
3519         // only break if this is an ASSIGN op node,
3520         // otherwise fall through to default case
3521         break;
3522       }
3523     }
3524
3525     // note that FlatOpNode's that aren't ASSIGN
3526     // fall through to this default case
3527     default: {
3528
3529       // a node with no live set has nothing to stall for
3530       if( liveSetIn == null ) {
3531         break;
3532       }
3533
3534       TempDescriptor[] readarray = fn.readsTemps();
3535       for( int i = 0; i < readarray.length; i++ ) {
3536         TempDescriptor readtmp = readarray[i];
3537
3538         // ignore temps that are definitely available
3539         // when considering to stall on it
3540         if( !notAvailSetIn.contains( readtmp ) ) {
3541           continue;
3542         }
3543
3544         // check the source type of this variable
3545         VSTWrapper vstIfStatic = new VSTWrapper();
3546         Integer srcType
3547           = vstTableIn.getRefVarSrcType( readtmp,
3548                                          currentSESE,
3549                                          vstIfStatic
3550                                          );
3551
3552         if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
3553           // 1) It is not clear statically where this variable will
3554           // come from, so dynamically we must keep track
3555           // along various control paths, and therefore when we stall,
3556           // just stall for the exact thing we need and move on
3557           plan.addDynamicStall( readtmp );
3558           currentSESE.addDynamicVar( readtmp );
3559
3560         } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
3561           // 2) Single token/age pair: Stall for token/age pair, and copy
3562           // all live variables with same token/age pair at the same
3563           // time.  This is the same stuff that the notavaialable analysis
3564           // marks as now available.
3565           VariableSourceToken vst = vstIfStatic.vst;
3566
3567           Iterator<VariableSourceToken> availItr =
3568             vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
3569
3570           while( availItr.hasNext() ) {
3571             VariableSourceToken vstAlsoAvail = availItr.next();
3572
3573             // only grab additional stuff that is live
3574             Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
3575
3576             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
3577             while( refVarItr.hasNext() ) {
3578               TempDescriptor refVar = refVarItr.next();
3579               if( liveSetIn.contains( refVar ) ) {
3580                 copySet.add( refVar );
3581               }
3582             }
3583
3584             if( !copySet.isEmpty() ) {
3585               plan.addStall2CopySet( vstAlsoAvail, copySet );
3586             }
3587           }
3588
3589         } else {
3590           // the other case for srcs is READY, so do nothing
3591         }
3592
3593         // assert that everything being stalled for is in the
3594         // "not available" set coming into this flat node and
3595         // that every VST identified is in the possible "stall set"
3596         // that represents VST's from children SESE's
3597
3598       }
3599     } break;
3600
3601     } // end switch
3602
3603
3604     // identify sese-age pairs that are statically useful
3605     // and should have an associated SESE variable in code
3606     // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
3607     // AND ALWAYS GIVE NAMES TO PARENTS
3608     Set<VariableSourceToken> staticSet = vstTableIn.get();
3609     Iterator<VariableSourceToken> vstItr = staticSet.iterator();
3610     while( vstItr.hasNext() ) {
3611       VariableSourceToken vst = vstItr.next();
3612
3613       // placeholder source tokens are useful results, but
3614       // the placeholder static name is never needed
3615       if( vst.getSESE().getIsCallerSESEplaceholder() ) {
3616         continue;
3617       }
3618
3619       FlatSESEEnterNode sese = currentSESE;
3620       while( sese != null ) {
3621         sese.addNeededStaticName(
3622                                  new SESEandAgePair( vst.getSESE(), vst.getAge() )
3623                                   );
3624         sese.mustTrackAtLeastAge( vst.getAge() );
3625
3626         sese = sese.getParent();
3627       }
3628     }
3629
3630
3631     codePlans.put( fn, plan );
3632
3633
3634     // if any variables at this-node-*dot* have a static source (exactly one vst)
3635     // but go to a dynamic source at next-node-*dot*, create a new IR graph
3636     // node on that edge to track the sources dynamically
3637     VarSrcTokTable thisVstTable = variableResults.get( fn );
3638     for( int i = 0; i < fn.numNext(); i++ ) {
3639       FlatNode            nn           = fn.getNext( i );
3640       VarSrcTokTable      nextVstTable = variableResults.get( nn );
3641       Set<TempDescriptor> nextLiveIn   = livenessRootView.get( nn );
3642
3643       // the table can be null if it is one of the few IR nodes
3644       // completely outside of the root SESE scope
3645       if( nextVstTable != null && nextLiveIn != null ) {
3646
3647         Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
3648           thisVstTable.getReadyOrStatic2DynamicSet( nextVstTable,
3649                                                     nextLiveIn,
3650                                                     currentSESE
3651                                                     );
3652
3653         if( !readyOrStatic2dynamicSet.isEmpty() ) {
3654
3655           // either add these results to partial fixed-point result
3656           // or make a new one if we haven't made any here yet
3657           FlatEdge fe = new FlatEdge( fn, nn );
3658           FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
3659
3660           if( fwdvn == null ) {
3661             fwdvn = new FlatWriteDynamicVarNode( fn,
3662                                                  nn,
3663                                                  readyOrStatic2dynamicSet,
3664                                                  currentSESE
3665                                                  );
3666             wdvNodesToSpliceIn.put( fe, fwdvn );
3667           } else {
3668             fwdvn.addMoreVar2Src( readyOrStatic2dynamicSet );
3669           }
3670         }
3671       }
3672     }
3673   }
3674
3675
3676   public void writeReports( String timeReport ) throws java.io.IOException {
3677
3678     BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
3679     bw.write( "MLP Analysis Results\n\n" );
3680     bw.write( timeReport+"\n\n" );
3681     printSESEHierarchy( bw );
3682     bw.write( "\n" );
3683     printSESEInfo( bw );
3684     bw.close();
3685
3686     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
3687     while( methItr.hasNext() ) {
3688       MethodDescriptor md = (MethodDescriptor) methItr.next();
3689       FlatMethod       fm = state.getMethodFlat( md );
3690       bw = new BufferedWriter( new FileWriter( "mlpReport_"+
3691                                                md.getClassMethodName()+
3692                                                md.getSafeMethodDescriptor()+
3693                                                ".txt" ) );
3694       bw.write( "MLP Results for "+md+"\n-------------------\n");
3695
3696       FlatSESEEnterNode implicitSESE = (FlatSESEEnterNode) fm.getNext(0);
3697       if( !implicitSESE.getIsCallerSESEplaceholder() &&
3698            implicitSESE != mainSESE
3699            ) {
3700           System.out.println( implicitSESE+" is not implicit?!" );
3701           System.exit( -1 );
3702       }
3703       bw.write( "Dynamic vars to manage:\n  "+implicitSESE.getDynamicVarSet());
3704
3705       bw.write( "\n\nLive-In, Root View\n------------------\n"          +fm.printMethod( livenessRootView ) );
3706       bw.write( "\n\nVariable Results-Out\n----------------\n"          +fm.printMethod( variableResults ) );
3707       bw.write( "\n\nNot Available Results-Out\n---------------------\n"+fm.printMethod( notAvailableResults ) );
3708       bw.write( "\n\nCode Plans\n----------\n"                          +fm.printMethod( codePlans ) );
3709       bw.write("\n\nSESE Effects\n----------------------\n"+printSESEEffects());
3710       bw.close();
3711     }
3712   }
3713
3714         private String printSESEEffects() {
3715
3716                 StringWriter writer = new StringWriter();
3717
3718                 Iterator<FlatSESEEnterNode> keyIter = allSESEs.iterator();
3719
3720                 while (keyIter.hasNext()) {
3721                         FlatSESEEnterNode seseEnter = keyIter.next();
3722                         String result = seseEnter.getSeseEffectsSet().printSet();
3723                         if (result.length() > 0) {
3724                                 writer.write("\nSESE " + seseEnter + "\n");
3725                                 writer.write(result);
3726                         }
3727                 }
3728                 keyIter = rootSESEs.iterator();
3729                 while (keyIter.hasNext()) {
3730                         FlatSESEEnterNode seseEnter = keyIter.next();
3731                         if (seseEnter.getIsCallerSESEplaceholder()) {
3732                                 if (!seseEnter.getChildren().isEmpty()) {
3733                                         String result = seseEnter.getSeseEffectsSet().printSet();
3734                                         if (result.length() > 0) {
3735                                                 writer.write("\nSESE " + seseEnter + "\n");
3736                                                 writer.write(result);
3737                                         }
3738                                 }
3739                         }
3740                 }
3741
3742                 return writer.toString();
3743
3744         }
3745
3746   private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
3747     bw.write( "SESE Hierarchy\n--------------\n" );
3748     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
3749     while( rootItr.hasNext() ) {
3750       FlatSESEEnterNode root = rootItr.next();
3751       if( root.getIsCallerSESEplaceholder() ) {
3752         if( !root.getChildren().isEmpty() ) {
3753           printSESEHierarchyTree( bw, root, 0 );
3754         }
3755       } else {
3756         printSESEHierarchyTree( bw, root, 0 );
3757       }
3758     }
3759   }
3760
3761   private void printSESEHierarchyTree( BufferedWriter bw,
3762                                        FlatSESEEnterNode fsen,
3763                                        int depth
3764                                      ) throws java.io.IOException {
3765     for( int i = 0; i < depth; ++i ) {
3766       bw.write( "  " );
3767     }
3768     bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
3769
3770     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
3771     while( childItr.hasNext() ) {
3772       FlatSESEEnterNode fsenChild = childItr.next();
3773       printSESEHierarchyTree( bw, fsenChild, depth + 1 );
3774     }
3775   }
3776
3777
3778   private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
3779     bw.write("\nSESE info\n-------------\n" );
3780     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
3781     while( rootItr.hasNext() ) {
3782       FlatSESEEnterNode root = rootItr.next();
3783       if( root.getIsCallerSESEplaceholder() ) {
3784         if( !root.getChildren().isEmpty() ) {
3785           printSESEInfoTree( bw, root );
3786         }
3787       } else {
3788         printSESEInfoTree( bw, root );
3789       }
3790     }
3791   }
3792
3793   private void printSESEInfoTree( BufferedWriter bw,
3794                                   FlatSESEEnterNode fsen
3795                                 ) throws java.io.IOException {
3796
3797     if( !fsen.getIsCallerSESEplaceholder() ) {
3798       bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
3799
3800       bw.write( "  in-set: "+fsen.getInVarSet()+"\n" );
3801       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
3802       while( tItr.hasNext() ) {
3803         TempDescriptor inVar = tItr.next();
3804         if( fsen.getReadyInVarSet().contains( inVar ) ) {
3805           bw.write( "    (ready)  "+inVar+"\n" );
3806         }
3807         if( fsen.getStaticInVarSet().contains( inVar ) ) {
3808           bw.write( "    (static) "+inVar+" from "+
3809                     fsen.getStaticInVarSrc( inVar )+"\n" );
3810         }
3811         if( fsen.getDynamicInVarSet().contains( inVar ) ) {
3812           bw.write( "    (dynamic)"+inVar+"\n" );
3813         }
3814       }
3815
3816       bw.write( "   Dynamic vars to manage: "+fsen.getDynamicVarSet()+"\n");
3817
3818       bw.write( "  out-set: "+fsen.getOutVarSet()+"\n" );
3819       bw.write( "}\n" );
3820     }
3821
3822     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
3823     while( childItr.hasNext() ) {
3824       FlatSESEEnterNode fsenChild = childItr.next();
3825       printSESEInfoTree( bw, fsenChild );
3826     }
3827   }
3828
3829   public Hashtable <FlatNode, ConflictGraph> getConflictGraphResults(){
3830           return conflictGraphResults;
3831   }
3832
3833   public Hashtable < FlatNode, ParentChildConflictsMap > getConflictsResults(){
3834           return conflictsResults;
3835   }
3836
3837   public Hashtable<FlatNode, SESESummary> getSeseSummaryMap(){
3838           return seseSummaryMap;
3839   }
3840
3841   public Hashtable<ConflictGraph, HashSet<SESELock>> getConflictGraphLockMap(){
3842           return conflictGraphLockMap;
3843   }
3844
3845 }