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