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