Robust/src/Analysis/MLP/MLPAnalysis.java

   1 package Analysis.MLP;
   2
   3 import Analysis.CallGraph.*;
   4 import Analysis.OwnershipAnalysis.*;
   5 import IR.*;
   6 import IR.Flat.*;
   7 import IR.Tree.*;
   8 import java.util.*;
   9 import java.io.*;
  10
  11
  12 public class MLPAnalysis {
  13
  14   // data from the compiler
  15   private State             state;
  16   private TypeUtil          typeUtil;
  17   private CallGraph         callGraph;
  18   private OwnershipAnalysis ownAnalysis;
  19
  20
  21   // an implicit SESE is automatically spliced into
  22   // the IR graph around the C main before this analysis--it
  23   // is nothing special except that we can make assumptions
  24   // about it, such as the whole program ends when it ends
  25   private FlatSESEEnterNode mainSESE;
  26
  27   // SESEs that are the root of an SESE tree belong to this
  28   // set--the main SESE is always a root, statically SESEs
  29   // inside methods are a root because we don't know how they
  30   // will fit into the runtime tree of SESEs
  31   private Set<FlatSESEEnterNode> rootSESEs;
  32
  33   // simply a set of every reachable SESE in the program, not
  34   // including caller placeholder SESEs
  35   private Set<FlatSESEEnterNode> allSESEs;
  36
  37
  38   // A mapping of flat nodes to the stack of SESEs for that node, where
  39   // an SESE is the child of the SESE directly below it on the stack.
  40   // These stacks do not reflect the heirarchy over methods calls--whenever
  41   // there is an empty stack it means all variables are available.
  42   private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
  43
  44   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessRootView;
  45   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessVirtualReads;
  46   private Hashtable< FlatNode, VarSrcTokTable           > variableResults;
  47   private Hashtable< FlatNode, Set<TempDescriptor>      > notAvailableResults;
  48   private Hashtable< FlatNode, CodePlan                 > codePlans;
  49
  50   private Hashtable< FlatEdge, FlatWriteDynamicVarNode  > wdvNodesToSpliceIn;
  51
  52   public static int maxSESEage = -1;
  53
  54
  55   // use these methods in BuildCode to have access to analysis results
  56   public FlatSESEEnterNode getMainSESE() {
  57     return mainSESE;
  58   }
  59
  60   public Set<FlatSESEEnterNode> getRootSESEs() {
  61     return rootSESEs;
  62   }
  63
  64   public Set<FlatSESEEnterNode> getAllSESEs() {
  65     return allSESEs;
  66   }
  67
  68   public int getMaxSESEage() {
  69     return maxSESEage;
  70   }
  71
  72   // may be null
  73   public CodePlan getCodePlan( FlatNode fn ) {
  74     CodePlan cp = codePlans.get( fn );
  75     return cp;
  76   }
  77
  78
  79   public MLPAnalysis( State             state,
  80                       TypeUtil          tu,
  81                       CallGraph         callGraph,
  82                       OwnershipAnalysis ownAnalysis
  83                       ) {
  84
  85     double timeStartAnalysis = (double) System.nanoTime();
  86
  87     this.state       = state;
  88     this.typeUtil    = tu;
  89     this.callGraph   = callGraph;
  90     this.ownAnalysis = ownAnalysis;
  91     this.maxSESEage  = state.MLP_MAXSESEAGE;
  92
  93     rootSESEs = new HashSet<FlatSESEEnterNode>();
  94     allSESEs  = new HashSet<FlatSESEEnterNode>();
  95
  96     seseStacks           = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
  97     livenessRootView     = new Hashtable< FlatNode, Set<TempDescriptor>      >();
  98     livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor>      >();
  99     variableResults      = new Hashtable< FlatNode, VarSrcTokTable           >();
 100     notAvailableResults  = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 101     codePlans            = new Hashtable< FlatNode, CodePlan                 >();
 102     wdvNodesToSpliceIn   = new Hashtable< FlatEdge, FlatWriteDynamicVarNode  >();
 103
 104
 105     FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
 106
 107     mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
 108     mainSESE.setfmEnclosing( fmMain );
 109     mainSESE.setmdEnclosing( fmMain.getMethod() );
 110     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
 111
 112
 113     // 1st pass
 114     // run analysis on each method that is actually called
 115     // reachability analysis already computed this so reuse
 116     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 117     while( methItr.hasNext() ) {
 118       Descriptor d  = methItr.next();
 119       FlatMethod fm = state.getMethodFlat( d );
 120
 121       // find every SESE from methods that may be called
 122       // and organize them into roots and children
 123       buildForestForward( fm );
 124     }
 125
 126
 127     // 2nd pass, results are saved in FlatSESEEnterNode, so
 128     // intermediate results, for safety, are discarded
 129     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
 130     while( rootItr.hasNext() ) {
 131       FlatSESEEnterNode root = rootItr.next();
 132       livenessAnalysisBackward( root,
 133                                 true,
 134                                 null );
 135     }
 136
 137
 138     // 3rd pass
 139     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 140     while( methItr.hasNext() ) {
 141       Descriptor d  = methItr.next();
 142       FlatMethod fm = state.getMethodFlat( d );
 143
 144       // starting from roots do a forward, fixed-point
 145       // variable analysis for refinement and stalls
 146       variableAnalysisForward( fm );
 147     }
 148
 149     // 4th pass, compute liveness contribution from
 150     // virtual reads discovered in variable pass
 151     rootItr = rootSESEs.iterator();
 152     while( rootItr.hasNext() ) {
 153       FlatSESEEnterNode root = rootItr.next();
 154       livenessAnalysisBackward( root,
 155                                 true,
 156                                 null );
 157     }
 158
 159
 160     /*
 161       SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
 162
 163     // 5th pass
 164     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 165     while( methItr.hasNext() ) {
 166       Descriptor d  = methItr.next();
 167       FlatMethod fm = state.getMethodFlat( d );
 168
 169       // prune variable results in one traversal
 170       // by removing reference variables that are not live
 171       pruneVariableResultsWithLiveness( fm );
 172     }
 173     */
 174
 175
 176     // 6th pass
 177     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 178     while( methItr.hasNext() ) {
 179       Descriptor d  = methItr.next();
 180       FlatMethod fm = state.getMethodFlat( d );
 181
 182       // compute what is not available at every program
 183       // point, in a forward fixed-point pass
 184       notAvailableForward( fm );
 185     }
 186
 187     // new pass
 188     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 189     while( methItr.hasNext() ) {
 190       Descriptor d  = methItr.next();
 191       FlatMethod fm = state.getMethodFlat( d );
 192       methodEffects(fm);
 193     }
 194
 195
 196     // 7th pass
 197     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 198     while( methItr.hasNext() ) {
 199       Descriptor d  = methItr.next();
 200       FlatMethod fm = state.getMethodFlat( d );
 201
 202       // compute a plan for code injections
 203       codePlansForward( fm );
 204     }
 205
 206
 207     // splice new IR nodes into graph after all
 208     // analysis passes are complete
 209     Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
 210     while( spliceItr.hasNext() ) {
 211       Map.Entry               me    = (Map.Entry)               spliceItr.next();
 212       FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
 213       fwdvn.spliceIntoIR();
 214     }
 215
 216
 217     double timeEndAnalysis = (double) System.nanoTime();
 218     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 219     String treport = String.format( "The mlp analysis took %.3f sec.", dt );
 220     System.out.println( treport );
 221
 222     if( state.MLPDEBUG ) {
 223       try {
 224         writeReports( treport );
 225       } catch( IOException e ) {}
 226     }
 227   }
 228
 229
 230   private void buildForestForward( FlatMethod fm ) {
 231
 232     // start from flat method top, visit every node in
 233     // method exactly once, find SESEs and remember
 234     // roots and child relationships
 235     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 236     flatNodesToVisit.add( fm );
 237
 238     Set<FlatNode> visited = new HashSet<FlatNode>();
 239
 240     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 241     seseStacks.put( fm, seseStackFirst );
 242
 243     while( !flatNodesToVisit.isEmpty() ) {
 244       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 245       FlatNode fn = fnItr.next();
 246
 247       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 248       assert seseStack != null;
 249
 250       flatNodesToVisit.remove( fn );
 251       visited.add( fn );
 252
 253       buildForest_nodeActions( fn, seseStack, fm );
 254
 255       for( int i = 0; i < fn.numNext(); i++ ) {
 256         FlatNode nn = fn.getNext( i );
 257
 258         if( !visited.contains( nn ) ) {
 259           flatNodesToVisit.add( nn );
 260
 261           // clone stack and send along each analysis path
 262           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 263         }
 264       }
 265     }
 266   }
 267
 268   private void buildForest_nodeActions( FlatNode fn,
 269                                         Stack<FlatSESEEnterNode> seseStack,
 270                                         FlatMethod fm ) {
 271     switch( fn.kind() ) {
 272
 273     case FKind.FlatSESEEnterNode: {
 274       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 275
 276       if( !fsen.getIsCallerSESEplaceholder() ) {
 277         allSESEs.add( fsen );
 278       }
 279
 280       fsen.setfmEnclosing( fm );
 281       fsen.setmdEnclosing( fm.getMethod() );
 282       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 283
 284       if( seseStack.empty() ) {
 285         rootSESEs.add( fsen );
 286         fsen.setParent( null );
 287       } else {
 288         seseStack.peek().addChild( fsen );
 289         fsen.setParent( seseStack.peek() );
 290       }
 291
 292       seseStack.push( fsen );
 293     } break;
 294
 295     case FKind.FlatSESEExitNode: {
 296       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 297       assert !seseStack.empty();
 298       FlatSESEEnterNode fsen = seseStack.pop();
 299     } break;
 300
 301     case FKind.FlatReturnNode: {
 302       FlatReturnNode frn = (FlatReturnNode) fn;
 303       if( !seseStack.empty() &&
 304           !seseStack.peek().getIsCallerSESEplaceholder()
 305         ) {
 306         throw new Error( "Error: return statement enclosed within SESE "+
 307                          seseStack.peek().getPrettyIdentifier() );
 308       }
 309     } break;
 310
 311     }
 312   }
 313
 314
 315   private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
 316                                          boolean toplevel,
 317                                          Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
 318
 319     // start from an SESE exit, visit nodes in reverse up to
 320     // SESE enter in a fixed-point scheme, where children SESEs
 321     // should already be analyzed and therefore can be skipped
 322     // because child SESE enter node has all necessary info
 323     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 324
 325     if( toplevel ) {
 326       flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
 327     } else {
 328       flatNodesToVisit.add( fsen.getFlatExit() );
 329     }
 330
 331     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
 332       new Hashtable< FlatNode, Set<TempDescriptor> >();
 333
 334     if( toplevel ) {
 335       liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
 336     }
 337
 338     while( !flatNodesToVisit.isEmpty() ) {
 339       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 340       flatNodesToVisit.remove( fn );
 341
 342       Set<TempDescriptor> prev = livenessResults.get( fn );
 343
 344       // merge sets from control flow joins
 345       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 346       for( int i = 0; i < fn.numNext(); i++ ) {
 347         FlatNode nn = fn.getNext( i );
 348         Set<TempDescriptor> s = livenessResults.get( nn );
 349         if( s != null ) {
 350           u.addAll( s );
 351         }
 352       }
 353
 354       Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
 355
 356       // if a new result, schedule backward nodes for analysis
 357       if( !curr.equals( prev ) ) {
 358         livenessResults.put( fn, curr );
 359
 360         // don't flow backwards past current SESE enter
 361         if( !fn.equals( fsen ) ) {
 362           for( int i = 0; i < fn.numPrev(); i++ ) {
 363             FlatNode nn = fn.getPrev( i );
 364             flatNodesToVisit.add( nn );
 365           }
 366         }
 367       }
 368     }
 369
 370     Set<TempDescriptor> s = livenessResults.get( fsen );
 371     if( s != null ) {
 372       fsen.addInVarSet( s );
 373     }
 374
 375     // remember liveness per node from the root view as the
 376     // global liveness of variables for later passes to use
 377     if( toplevel ) {
 378       livenessRootView.putAll( livenessResults );
 379     }
 380
 381     // post-order traversal, so do children first
 382     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 383     while( childItr.hasNext() ) {
 384       FlatSESEEnterNode fsenChild = childItr.next();
 385       livenessAnalysisBackward( fsenChild, false, liveout );
 386     }
 387   }
 388
 389   private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
 390                                                     Set<TempDescriptor> liveIn,
 391                                                     FlatSESEEnterNode currentSESE,
 392                                                     boolean toplevel,
 393                                                     Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
 394                                                   ) {
 395     switch( fn.kind() ) {
 396
 397     case FKind.FlatSESEExitNode:
 398       if( toplevel ) {
 399         FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 400         if( !liveout.containsKey( fsexn ) ) {
 401           liveout.put( fsexn, new HashSet<TempDescriptor>() );
 402         }
 403         liveout.get( fsexn ).addAll( liveIn );
 404       }
 405       // no break, sese exits should also execute default actions
 406
 407     default: {
 408       // handle effects of statement in reverse, writes then reads
 409       TempDescriptor [] writeTemps = fn.writesTemps();
 410       for( int i = 0; i < writeTemps.length; ++i ) {
 411         liveIn.remove( writeTemps[i] );
 412
 413         if( !toplevel ) {
 414           FlatSESEExitNode fsexn = currentSESE.getFlatExit();
 415           Set<TempDescriptor> livetemps = liveout.get( fsexn );
 416           if( livetemps != null &&
 417               livetemps.contains( writeTemps[i] ) ) {
 418             // write to a live out temp...
 419             // need to put in SESE liveout set
 420             currentSESE.addOutVar( writeTemps[i] );
 421           }
 422         }
 423       }
 424
 425       TempDescriptor [] readTemps = fn.readsTemps();
 426       for( int i = 0; i < readTemps.length; ++i ) {
 427         liveIn.add( readTemps[i] );
 428       }
 429
 430       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
 431       if( virtualReadTemps != null ) {
 432         liveIn.addAll( virtualReadTemps );
 433       }
 434
 435     } break;
 436
 437     } // end switch
 438
 439     return liveIn;
 440   }
 441
 442
 443   private void variableAnalysisForward( FlatMethod fm ) {
 444
 445     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 446     flatNodesToVisit.add( fm );
 447
 448     while( !flatNodesToVisit.isEmpty() ) {
 449       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 450       flatNodesToVisit.remove( fn );
 451
 452       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 453       assert seseStack != null;
 454
 455       VarSrcTokTable prev = variableResults.get( fn );
 456
 457       // merge sets from control flow joins
 458       VarSrcTokTable curr = new VarSrcTokTable();
 459       for( int i = 0; i < fn.numPrev(); i++ ) {
 460         FlatNode nn = fn.getPrev( i );
 461         VarSrcTokTable incoming = variableResults.get( nn );
 462         curr.merge( incoming );
 463       }
 464
 465       if( !seseStack.empty() ) {
 466         variable_nodeActions( fn, curr, seseStack.peek() );
 467       }
 468
 469       // if a new result, schedule forward nodes for analysis
 470       if( !curr.equals( prev ) ) {
 471         variableResults.put( fn, curr );
 472
 473         for( int i = 0; i < fn.numNext(); i++ ) {
 474           FlatNode nn = fn.getNext( i );
 475           flatNodesToVisit.add( nn );
 476         }
 477       }
 478     }
 479   }
 480
 481   private void variable_nodeActions( FlatNode fn,
 482                                      VarSrcTokTable vstTable,
 483                                      FlatSESEEnterNode currentSESE ) {
 484     switch( fn.kind() ) {
 485
 486     case FKind.FlatSESEEnterNode: {
 487       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 488       assert fsen.equals( currentSESE );
 489
 490       vstTable.age( currentSESE );
 491       vstTable.assertConsistency();
 492     } break;
 493
 494     case FKind.FlatSESEExitNode: {
 495       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 496       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 497       assert currentSESE.getChildren().contains( fsen );
 498
 499       vstTable.remapChildTokens( fsen );
 500
 501       // liveness virtual reads are things that might be
 502       // written by an SESE and should be added to the in-set
 503       // anything virtually read by this SESE should be pruned
 504       // of parent or sibling sources
 505       Set<TempDescriptor> liveVars         = livenessRootView.get( fn );
 506       Set<TempDescriptor> fsenVirtReads    = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
 507       Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
 508       if( fsenVirtReadsOld != null ) {
 509         fsenVirtReads.addAll( fsenVirtReadsOld );
 510       }
 511       livenessVirtualReads.put( fn, fsenVirtReads );
 512
 513
 514       // then all child out-set tokens are guaranteed
 515       // to be filled in, so clobber those entries with
 516       // the latest, clean sources
 517       Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
 518       while( outVarItr.hasNext() ) {
 519         TempDescriptor outVar = outVarItr.next();
 520         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 521         ts.add( outVar );
 522         VariableSourceToken vst =
 523           new VariableSourceToken( ts,
 524                                    fsen,
 525                                    new Integer( 0 ),
 526                                    outVar
 527                                    );
 528         vstTable.remove( outVar );
 529         vstTable.add( vst );
 530       }
 531       vstTable.assertConsistency();
 532
 533     } break;
 534
 535     case FKind.FlatOpNode: {
 536       FlatOpNode fon = (FlatOpNode) fn;
 537
 538       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 539         TempDescriptor lhs = fon.getDest();
 540         TempDescriptor rhs = fon.getLeft();
 541
 542         vstTable.remove( lhs );
 543
 544         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 545
 546         Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
 547         while( itr.hasNext() ) {
 548           VariableSourceToken vst = itr.next();
 549
 550           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 551           ts.add( lhs );
 552
 553           if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
 554             // if the source comes from a child, copy it over
 555             forAddition.add( new VariableSourceToken( ts,
 556                                                       vst.getSESE(),
 557                                                       vst.getAge(),
 558                                                       vst.getAddrVar()
 559                                                       )
 560                              );
 561           } else {
 562             // otherwise, stamp it as us as the source
 563             forAddition.add( new VariableSourceToken( ts,
 564                                                       currentSESE,
 565                                                       new Integer( 0 ),
 566                                                       lhs
 567                                                       )
 568                              );
 569           }
 570         }
 571
 572         vstTable.addAll( forAddition );
 573
 574         // only break if this is an ASSIGN op node,
 575         // otherwise fall through to default case
 576         vstTable.assertConsistency();
 577         break;
 578       }
 579     }
 580
 581     // note that FlatOpNode's that aren't ASSIGN
 582     // fall through to this default case
 583     default: {
 584       TempDescriptor [] writeTemps = fn.writesTemps();
 585       if( writeTemps.length > 0 ) {
 586
 587
 588         // for now, when writeTemps > 1, make sure
 589         // its a call node, programmer enforce only
 590         // doing stuff like calling a print routine
 591         //assert writeTemps.length == 1;
 592         if( writeTemps.length > 1 ) {
 593           assert fn.kind() == FKind.FlatCall ||
 594                  fn.kind() == FKind.FlatMethod;
 595           break;
 596         }
 597
 598         vstTable.remove( writeTemps[0] );
 599
 600         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 601         ts.add( writeTemps[0] );
 602
 603         vstTable.add( new VariableSourceToken( ts,
 604                                                currentSESE,
 605                                                new Integer( 0 ),
 606                                                writeTemps[0]
 607                                              )
 608                       );
 609       }
 610
 611       vstTable.assertConsistency();
 612     } break;
 613
 614     } // end switch
 615   }
 616
 617
 618   private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
 619
 620     // start from flat method top, visit every node in
 621     // method exactly once
 622     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 623     flatNodesToVisit.add( fm );
 624
 625     Set<FlatNode> visited = new HashSet<FlatNode>();
 626
 627     while( !flatNodesToVisit.isEmpty() ) {
 628       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 629       FlatNode fn = fnItr.next();
 630
 631       flatNodesToVisit.remove( fn );
 632       visited.add( fn );
 633
 634       Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
 635       VarSrcTokTable      vstTable    = variableResults.get( fn );
 636
 637       vstTable.pruneByLiveness( rootLiveSet );
 638
 639       for( int i = 0; i < fn.numNext(); i++ ) {
 640         FlatNode nn = fn.getNext( i );
 641
 642         if( !visited.contains( nn ) ) {
 643           flatNodesToVisit.add( nn );
 644         }
 645       }
 646     }
 647   }
 648
 649
 650   private void notAvailableForward( FlatMethod fm ) {
 651
 652     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 653     flatNodesToVisit.add( fm );
 654
 655     while( !flatNodesToVisit.isEmpty() ) {
 656       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 657       flatNodesToVisit.remove( fn );
 658
 659       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 660       assert seseStack != null;
 661
 662       Set<TempDescriptor> prev = notAvailableResults.get( fn );
 663
 664       Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
 665       for( int i = 0; i < fn.numPrev(); i++ ) {
 666         FlatNode nn = fn.getPrev( i );
 667         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
 668         if( notAvailIn != null ) {
 669           curr.addAll( notAvailIn );
 670         }
 671       }
 672
 673       if( !seseStack.empty() ) {
 674         notAvailable_nodeActions( fn, curr, seseStack.peek() );
 675       }
 676
 677       // if a new result, schedule forward nodes for analysis
 678       if( !curr.equals( prev ) ) {
 679         notAvailableResults.put( fn, curr );
 680
 681         for( int i = 0; i < fn.numNext(); i++ ) {
 682           FlatNode nn = fn.getNext( i );
 683           flatNodesToVisit.add( nn );
 684         }
 685       }
 686     }
 687   }
 688
 689   private void notAvailable_nodeActions( FlatNode fn,
 690                                          Set<TempDescriptor> notAvailSet,
 691                                          FlatSESEEnterNode currentSESE ) {
 692
 693     // any temps that are removed from the not available set
 694     // at this node should be marked in this node's code plan
 695     // as temps to be grabbed at runtime!
 696
 697     switch( fn.kind() ) {
 698
 699     case FKind.FlatSESEEnterNode: {
 700       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 701       assert fsen.equals( currentSESE );
 702       notAvailSet.clear();
 703     } break;
 704
 705     case FKind.FlatSESEExitNode: {
 706       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 707       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 708       assert currentSESE.getChildren().contains( fsen );
 709       notAvailSet.addAll( fsen.getOutVarSet() );
 710     } break;
 711
 712     case FKind.FlatMethod: {
 713       notAvailSet.clear();
 714     }
 715
 716     case FKind.FlatOpNode: {
 717       FlatOpNode fon = (FlatOpNode) fn;
 718
 719       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 720         TempDescriptor lhs = fon.getDest();
 721         TempDescriptor rhs = fon.getLeft();
 722
 723         // copy makes lhs same availability as rhs
 724         if( notAvailSet.contains( rhs ) ) {
 725           notAvailSet.add( lhs );
 726         } else {
 727           notAvailSet.remove( lhs );
 728         }
 729
 730         // only break if this is an ASSIGN op node,
 731         // otherwise fall through to default case
 732         break;
 733       }
 734     }
 735
 736     // note that FlatOpNode's that aren't ASSIGN
 737     // fall through to this default case
 738     default: {
 739       TempDescriptor [] writeTemps = fn.writesTemps();
 740       for( int i = 0; i < writeTemps.length; i++ ) {
 741         TempDescriptor wTemp = writeTemps[i];
 742         notAvailSet.remove( wTemp );
 743       }
 744       TempDescriptor [] readTemps = fn.readsTemps();
 745       for( int i = 0; i < readTemps.length; i++ ) {
 746         TempDescriptor rTemp = readTemps[i];
 747         notAvailSet.remove( rTemp );
 748
 749         // if this variable has exactly one source, potentially
 750         // get other things from this source as well
 751         VarSrcTokTable vstTable = variableResults.get( fn );
 752
 753         Integer srcType =
 754           vstTable.getRefVarSrcType( rTemp,
 755                                      currentSESE,
 756                                      currentSESE.getParent() );
 757
 758         if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
 759
 760           VariableSourceToken vst = vstTable.get( rTemp ).iterator().next();
 761
 762           Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
 763                                                                  vst.getAge()
 764                                                                  ).iterator();
 765
 766           // look through things that are also available from same source
 767           while( availItr.hasNext() ) {
 768             VariableSourceToken vstAlsoAvail = availItr.next();
 769
 770             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
 771             while( refVarItr.hasNext() ) {
 772               TempDescriptor refVarAlso = refVarItr.next();
 773
 774               // if a variable is available from the same source, AND it ALSO
 775               // only comes from one statically known source, mark it available
 776               Integer srcTypeAlso =
 777                 vstTable.getRefVarSrcType( refVarAlso,
 778                                            currentSESE,
 779                                            currentSESE.getParent() );
 780               if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
 781                 notAvailSet.remove( refVarAlso );
 782               }
 783             }
 784           }
 785         }
 786       }
 787     } break;
 788
 789     } // end switch
 790   }
 791
 792         private void methodEffects(FlatMethod fm) {
 793
 794                 MethodDescriptor md=fm.getMethod();
 795                 HashSet<MethodContext> mcSet=ownAnalysis.getAllMethodContextSetByDescriptor(md);
 796                 Iterator<MethodContext> mcIter=mcSet.iterator();
 797
 798                 while(mcIter.hasNext()){
 799                         MethodContext mc=mcIter.next();
 800
 801                         Set<FlatNode> visited = new HashSet<FlatNode>();
 802
 803                         Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 804                         flatNodesToVisit.add(fm);
 805
 806                         while (!flatNodesToVisit.isEmpty()) {
 807                                 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 808                                 flatNodesToVisit.remove(fn);
 809
 810                                 Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
 811                                 assert seseStack != null;
 812
 813                                 if (!seseStack.empty()) {
 814                                         effects_nodeActions(mc, fn, seseStack.peek());
 815                                 }
 816
 817                                 flatNodesToVisit.remove(fn);
 818                                 visited.add(fn);
 819
 820                                 for (int i = 0; i < fn.numNext(); i++) {
 821                                         FlatNode nn = fn.getNext(i);
 822                                         if (!visited.contains(nn)) {
 823                                                 flatNodesToVisit.add(nn);
 824                                         }
 825                                 }
 826
 827                         }
 828
 829
 830                 }
 831
 832         }
 833
 834         private void effects_nodeActions(MethodContext mc, FlatNode fn,
 835                         FlatSESEEnterNode currentSESE) {
 836
 837                 OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc);
 838
 839                 switch (fn.kind()) {
 840
 841                 case FKind.FlatSESEEnterNode: {
 842
 843                         FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 844                         assert fsen.equals(currentSESE);
 845
 846                         // uniquely taint each live-in variable
 847                         Set<TempDescriptor> set = fsen.getInVarSet();
 848                         Iterator<TempDescriptor> iter = set.iterator();
 849                         int idx = 0;
 850                         while (iter.hasNext()) {
 851                                 TempDescriptor td = iter.next();
 852                                 LabelNode ln = og.td2ln.get(td);
 853                                 if (ln != null) {
 854                                         int taint = (int) Math.pow(2, idx);
 855                                         taintLabelNode(ln, taint);
 856                                 }
 857                                 idx++;
 858                         }
 859
 860                 }
 861                         break;
 862
 863                 case FKind.FlatSESEExitNode: {
 864                         FlatSESEExitNode fsexit = (FlatSESEExitNode) fn;
 865
 866                         FlatSESEEnterNode enterNode = fsexit.getFlatEnter();
 867                         FlatSESEEnterNode parent = enterNode.getParent();
 868                         if (parent != null) {
 869
 870                                 SESEEffectsSet set = enterNode.getSeseEffectsSet();
 871                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> readTable = set
 872                                                 .getReadTable();
 873                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentReadTable = parent
 874                                                 .getSeseEffectsSet().getReadTable();
 875                                 Set<TempDescriptor> keys = readTable.keySet();
 876                                 Iterator<TempDescriptor> keyIter = keys.iterator();
 877                                 while (keyIter.hasNext()) {
 878                                         TempDescriptor td = (TempDescriptor) keyIter.next();
 879                                         HashSet<SESEEffectsKey> effectsSet = readTable.get(td);
 880                                         HashSet<SESEEffectsKey> parentEffectsSet = parentReadTable
 881                                                         .get(td);
 882                                         if (parentEffectsSet == null) {
 883                                                 parentEffectsSet = new HashSet<SESEEffectsKey>();
 884                                         }
 885
 886                                         for (Iterator iterator = effectsSet.iterator(); iterator
 887                                                         .hasNext();) {
 888                                                 SESEEffectsKey seseKey = (SESEEffectsKey) iterator
 889                                                                 .next();
 890                                                 parentEffectsSet.add(new SESEEffectsKey(seseKey.getFieldDescriptor(), seseKey.getTypeDescriptor(), seseKey.getHRNId()));
 891                                         }
 892
 893                                         parentReadTable.put(td, parentEffectsSet);
 894                                 }
 895
 896                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> writeTable = set
 897                                                 .getWriteTable();
 898                                 Hashtable<TempDescriptor, HashSet<SESEEffectsKey>> parentWriteTable = parent
 899                                                 .getSeseEffectsSet().getWriteTable();
 900                                 keys = writeTable.keySet();
 901                                 keyIter = keys.iterator();
 902                                 while (keyIter.hasNext()) {
 903                                         TempDescriptor td = (TempDescriptor) keyIter.next();
 904                                         HashSet<SESEEffectsKey> effectsSet = writeTable.get(td);
 905                                         HashSet<SESEEffectsKey> parentEffectsSet = parentWriteTable
 906                                                         .get(td);
 907                                         if (parentEffectsSet == null) {
 908                                                 parentEffectsSet = new HashSet<SESEEffectsKey>();
 909                                         }
 910
 911                                         for (Iterator iterator = effectsSet.iterator(); iterator
 912                                                         .hasNext();) {
 913                                                 SESEEffectsKey seseKey = (SESEEffectsKey) iterator
 914                                                                 .next();
 915                                                 parentEffectsSet.add(new SESEEffectsKey(seseKey
 916                                                                 .getFieldDescriptor(), seseKey
 917                                                                 .getTypeDescriptor(), seseKey.getHRNId()));
 918                                         }
 919
 920                                         parentWriteTable.put(td, parentEffectsSet);
 921                                 }
 922
 923                         }
 924
 925                 }
 926                         break;
 927
 928                 case FKind.FlatFieldNode: {
 929
 930                         FlatFieldNode ffn = (FlatFieldNode) fn;
 931                         TempDescriptor src = ffn.getSrc();
 932                         FieldDescriptor field = ffn.getField();
 933
 934                         LabelNode srcLN = og.td2ln.get(src);
 935                         if (srcLN != null) {
 936                                 HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(srcLN);
 937                                 Iterator<TempDescriptor> affectedIter = affectedTDSet
 938                                                 .iterator();
 939                                 while (affectedIter.hasNext()) {
 940                                         TempDescriptor affectedTD = affectedIter.next();
 941                                         if (currentSESE.getInVarSet().contains(affectedTD)) {
 942
 943                                                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
 944                                                                 og, affectedTD);
 945                                                 Iterator<HeapRegionNode> hrnIter = hrnSet.iterator();
 946                                                 while (hrnIter.hasNext()) {
 947                                                         HeapRegionNode hrn = hrnIter.next();
 948
 949                                                         Iterator<ReferenceEdge> referencers = hrn
 950                                                                         .iteratorToReferencers();
 951                                                         while (referencers.hasNext()) {
 952                                                                 ReferenceEdge referenceEdge = (ReferenceEdge) referencers
 953                                                                                 .next();
 954                                                                 if (field.getSymbol().equals(
 955                                                                                 referenceEdge.getField())) {
 956                                                                         currentSESE.readEffects(affectedTD, field
 957                                                                                         .getSymbol(), src.getType(),
 958                                                                                         referenceEdge.getDst().getID());
 959                                                                 }
 960                                                         }
 961
 962                                                 }
 963                                         }
 964                                 }
 965
 966                                 //  handle tainted case
 967
 968                                 Iterator<ReferenceEdge> edgeIter = srcLN
 969                                                 .iteratorToReferencees();
 970                                 while (edgeIter.hasNext()) {
 971                                         ReferenceEdge edge = edgeIter.next();
 972
 973                                         if(edge.getTaintIdentifier()>0){
 974                                                 HeapRegionNode accessHRN = edge.getDst();
 975                                                 affectedTDSet = getReferenceNodeSet(accessHRN);
 976                                                 affectedIter = affectedTDSet.iterator();
 977                                                 while (affectedIter.hasNext()) {
 978                                                         TempDescriptor affectedTD = affectedIter.next();
 979                                                         if (currentSESE.getInVarSet().contains(affectedTD)) {
 980
 981                                                                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
 982                                                                                 og, affectedTD);
 983                                                                 Iterator<HeapRegionNode> hrnIter = hrnSet
 984                                                                                 .iterator();
 985                                                                 while (hrnIter.hasNext()) {
 986                                                                         HeapRegionNode hrn = hrnIter.next();
 987                                                                         currentSESE.readEffects(affectedTD, field
 988                                                                                         .getSymbol(), src.getType(), hrn
 989                                                                                         .getID());
 990                                                                 }
 991
 992                                                         }
 993
 994                                                 }
 995                                         }
 996                                 }
 997                         }
 998
 999                 }
1000                         break;
1001
1002                 case FKind.FlatSetFieldNode: {
1003
1004                         FlatSetFieldNode fsen = (FlatSetFieldNode) fn;
1005                         TempDescriptor dst = fsen.getDst();
1006                         FieldDescriptor field = fsen.getField();
1007
1008                         LabelNode dstLN = og.td2ln.get(dst);
1009                         if (dstLN != null) {
1010                                 HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(dstLN);
1011
1012                                 Iterator<TempDescriptor> affectedIter = affectedTDSet
1013                                                 .iterator();
1014
1015                                 while (affectedIter.hasNext()) {
1016                                         TempDescriptor affectedTD = affectedIter.next();
1017                                         if (currentSESE.getInVarSet().contains(affectedTD)) {
1018
1019                                                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
1020                                                                 og, affectedTD);
1021                                                 Iterator<HeapRegionNode> hrnIter = hrnSet.iterator();
1022                                                 while (hrnIter.hasNext()) {
1023                                                         HeapRegionNode hrn = hrnIter.next();
1024
1025                                                         if (field.getType().isImmutable()) {
1026                                                                 currentSESE.writeEffects(affectedTD, field
1027                                                                                 .getSymbol(), dst.getType(), hrn
1028                                                                                 .getID());
1029
1030                                                         } else {
1031                                                                 Iterator<ReferenceEdge> referencers = hrn
1032                                                                                 .iteratorToReferencers();
1033                                                                 while (referencers.hasNext()) {
1034                                                                         ReferenceEdge referenceEdge = (ReferenceEdge) referencers
1035                                                                                         .next();
1036                                                                         if (field.getSymbol().equals(
1037                                                                                         referenceEdge.getField())) {
1038                                                                                 currentSESE.writeEffects(affectedTD,
1039                                                                                                 field.getSymbol(), dst
1040                                                                                                                 .getType(),
1041                                                                                                 referenceEdge.getDst().getID());
1042                                                                         }
1043                                                                 }
1044                                                         }
1045
1046                                                 }
1047                                         }
1048                                 }
1049
1050                                 // handle tainted case
1051                                 Iterator<ReferenceEdge> edgeIter = dstLN
1052                                                 .iteratorToReferencees();
1053                                 while (edgeIter.hasNext()) {
1054                                         ReferenceEdge edge = edgeIter.next();
1055                                         if (edge.getTaintIdentifier() > 0) {
1056                                                 HeapRegionNode accessHRN = edge.getDst();
1057                                                 affectedTDSet = getReferenceNodeSet(accessHRN);
1058                                                 affectedIter = affectedTDSet.iterator();
1059                                                 while (affectedIter.hasNext()) {
1060                                                         TempDescriptor affectedTD = affectedIter.next();
1061                                                         if (currentSESE.getInVarSet().contains(affectedTD)) {
1062
1063                                                                 HashSet<HeapRegionNode> hrnSet = getReferenceHeapIDSet(
1064                                                                                 og, affectedTD);
1065                                                                 Iterator<HeapRegionNode> hrnIter = hrnSet
1066                                                                                 .iterator();
1067                                                                 while (hrnIter.hasNext()) {
1068                                                                         HeapRegionNode hrn = hrnIter.next();
1069                                                                         currentSESE.writeEffects(affectedTD, field
1070                                                                                         .getSymbol(), dst.getType(), hrn
1071                                                                                         .getID());
1072
1073                                                                 }
1074
1075                                                         }
1076
1077                                                 }
1078                                         }
1079                                 }
1080
1081                         }
1082
1083                 }
1084                         break;
1085
1086                 case FKind.FlatCall: {
1087                         FlatCall fc = (FlatCall) fn;
1088
1089                         MethodContext calleeMC = ownAnalysis.getCalleeMethodContext(mc, fc);
1090
1091                         MethodEffects me = ownAnalysis.getMethodEffectsAnalysis()
1092                                         .getMethodEffectsByMethodContext(calleeMC);
1093
1094                         OwnershipGraph calleeOG = ownAnalysis
1095                                         .getOwnvershipGraphByMethodContext(calleeMC);
1096
1097                         FlatMethod fm = state.getMethodFlat(fc.getMethod());
1098                         ParameterDecomposition decomp = new ParameterDecomposition(
1099                                         ownAnalysis, fc, fm, calleeMC, calleeOG, og);
1100
1101                         int base;
1102                         if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) {
1103                                 base = 0;
1104                         } else {
1105                                 base = 1;
1106                         }
1107
1108                         for (int i = 0; i < fc.numArgs(); i++) {
1109
1110                                 TempDescriptor arg = fc.getArg(i);
1111                                 Set<EffectsKey> readSet = me.getEffects().getReadingSet(
1112                                                 i + base);
1113                                 Set<EffectsKey> writeSet = me.getEffects().getWritingSet(
1114                                                 i + base);
1115
1116                                 LabelNode argLN = og.td2ln.get(arg);
1117                                 if (argLN != null) {
1118                                         HashSet<TempDescriptor> affectedTDSet = getAccessedTaintNodeSet(argLN);
1119                                         Iterator<TempDescriptor> affectedIter = affectedTDSet
1120                                                         .iterator();
1121
1122                                         while (affectedIter.hasNext()) {
1123
1124                                                 TempDescriptor affectedTD = affectedIter.next();
1125                                                 if (currentSESE.getInVarSet().contains(affectedTD)) {
1126
1127                                                         if (readSet != null) {
1128                                                                 Iterator<EffectsKey> readIter = readSet
1129                                                                                 .iterator();
1130                                                                 while (readIter.hasNext()) {
1131                                                                         EffectsKey key = readIter.next();
1132                                                                         Set<Integer> hrnSet = getCallerHRNId(
1133                                                                                         new Integer(i + base), calleeOG,
1134                                                                                         key.getHRNId(), decomp);
1135                                                                         Iterator<Integer> hrnIter = hrnSet
1136                                                                                         .iterator();
1137                                                                         while (hrnIter.hasNext()) {
1138                                                                                 Integer hrnID = (Integer) hrnIter
1139                                                                                                 .next();
1140                                                                                 currentSESE.readEffects(affectedTD, key
1141                                                                                                 .getFieldDescriptor(), key
1142                                                                                                 .getTypeDescriptor(), hrnID);
1143                                                                         }
1144                                                                 }
1145                                                         }
1146
1147                                                         if (writeSet != null) {
1148                                                                 Iterator<EffectsKey> writeIter = writeSet
1149                                                                                 .iterator();
1150                                                                 while (writeIter.hasNext()) {
1151                                                                         EffectsKey key = writeIter.next();
1152
1153                                                                         Set<Integer> hrnSet = getCallerHRNId(
1154                                                                                         new Integer(i + base), calleeOG,
1155                                                                                         key.getHRNId(), decomp);
1156                                                                         Iterator<Integer> hrnIter = hrnSet
1157                                                                                         .iterator();
1158                                                                         while (hrnIter.hasNext()) {
1159                                                                                 Integer hrnID = (Integer) hrnIter
1160                                                                                                 .next();
1161                                                                                 currentSESE.writeEffects(affectedTD,
1162                                                                                                 key.getFieldDescriptor(), key
1163                                                                                                                 .getTypeDescriptor(),
1164                                                                                                 hrnID);
1165                                                                         }
1166
1167                                                                 }
1168                                                         }
1169
1170                                                 }
1171
1172                                         }
1173
1174                                 }
1175
1176                         }
1177
1178                 }
1179                         break;
1180
1181                 }
1182         }
1183
1184         private Set<Integer> getCallerHRNId(Integer paramIdx,
1185                         OwnershipGraph calleeOG, Integer calleeHRNId,
1186                         ParameterDecomposition paramDecom) {
1187
1188                 Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx);
1189                 Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx);
1190
1191                 if (calleeHRNId.equals(hrnPrimaryID)) {
1192                         // it references to primary param heap region
1193                         return paramDecom.getParamObject_hrnIDs(paramIdx);
1194                 } else if (calleeHRNId.equals(hrnSecondaryID)) {
1195                         // it references to secondary param heap region
1196                         return paramDecom.getParamReachable_hrnIDs(paramIdx);
1197                 }
1198
1199                 return new HashSet<Integer>();
1200         }
1201
1202         private void taintLabelNode(LabelNode ln, int identifier) {
1203
1204                 Iterator<ReferenceEdge> edgeIter = ln.iteratorToReferencees();
1205                 while (edgeIter.hasNext()) {
1206                         ReferenceEdge edge = edgeIter.next();
1207                         HeapRegionNode hrn = edge.getDst();
1208
1209                         Iterator<ReferenceEdge> edgeReferencerIter = hrn
1210                                         .iteratorToReferencers();
1211                         while (edgeReferencerIter.hasNext()) {
1212                                 ReferenceEdge referencerEdge = edgeReferencerIter.next();
1213                                 OwnershipNode node = referencerEdge.getSrc();
1214                                 if (node instanceof LabelNode) {
1215                                         referencerEdge.unionSESETaintIdentifier(identifier);
1216                                 }
1217                         }
1218
1219                 }
1220
1221         }
1222
1223         private HashSet<TempDescriptor> getReferenceNodeSet(HeapRegionNode hrn){
1224
1225                 HashSet<TempDescriptor> returnSet=new HashSet<TempDescriptor>();
1226
1227                 Iterator<ReferenceEdge> edgeIter=hrn.iteratorToReferencers();
1228                 while(edgeIter.hasNext()){
1229                         ReferenceEdge edge=edgeIter.next();
1230                         if(edge.getSrc() instanceof LabelNode){
1231                                 LabelNode ln=(LabelNode)edge.getSrc();
1232                                 returnSet.add(ln.getTempDescriptor());
1233                         }
1234                 }
1235
1236                 return returnSet;
1237
1238         }
1239
1240
1241         private HashSet<HeapRegionNode> getReferenceHeapIDSet(OwnershipGraph og, TempDescriptor td){
1242
1243                 HashSet<HeapRegionNode> returnSet=new HashSet<HeapRegionNode>();
1244
1245                 LabelNode ln=og.td2ln.get(td);
1246                 Iterator<ReferenceEdge> edgeIter=ln.iteratorToReferencees();
1247                 while(edgeIter.hasNext()){
1248                         ReferenceEdge edge=edgeIter.next();
1249                                 HeapRegionNode hrn=edge.getDst();
1250                                 returnSet.add(hrn);
1251                 }
1252                 return returnSet;
1253         }
1254
1255
1256         private HashSet<TempDescriptor> getAccessedTaintNodeSet(LabelNode ln) {
1257
1258                 HashSet<TempDescriptor> returnSet = new HashSet<TempDescriptor>();
1259
1260                 Iterator<ReferenceEdge> edgeIter = ln.iteratorToReferencees();
1261                 while (edgeIter.hasNext()) {
1262                         ReferenceEdge edge = edgeIter.next();
1263                         HeapRegionNode hrn = edge.getDst();
1264
1265                         Iterator<ReferenceEdge> edgeReferencerIter = hrn
1266                                         .iteratorToReferencers();
1267                         while (edgeReferencerIter.hasNext()) {
1268                                 ReferenceEdge referencerEdge = edgeReferencerIter.next();
1269
1270                                 if (referencerEdge.getSrc() instanceof LabelNode) {
1271                                         if (!((LabelNode) referencerEdge.getSrc()).equals(ln)) {
1272
1273                                                 if (referencerEdge.getSESETaintIdentifier() > 0) {
1274                                                         TempDescriptor td = ((LabelNode) referencerEdge
1275                                                                         .getSrc()).getTempDescriptor();
1276                                                         returnSet.add(td);
1277                                                 }
1278                                         }
1279                                 }
1280                         }
1281
1282                 }
1283
1284                 return returnSet;
1285
1286         }
1287
1288
1289   private void codePlansForward( FlatMethod fm ) {
1290
1291     // start from flat method top, visit every node in
1292     // method exactly once
1293     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1294     flatNodesToVisit.add( fm );
1295
1296     Set<FlatNode> visited = new HashSet<FlatNode>();
1297
1298     while( !flatNodesToVisit.isEmpty() ) {
1299       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
1300       FlatNode fn = fnItr.next();
1301
1302       flatNodesToVisit.remove( fn );
1303       visited.add( fn );
1304
1305       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
1306       assert seseStack != null;
1307
1308       // use incoming results as "dot statement" or just
1309       // before the current statement
1310       VarSrcTokTable dotSTtable = new VarSrcTokTable();
1311       for( int i = 0; i < fn.numPrev(); i++ ) {
1312         FlatNode nn = fn.getPrev( i );
1313         dotSTtable.merge( variableResults.get( nn ) );
1314       }
1315
1316       // find dt-st notAvailableSet also
1317       Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
1318       for( int i = 0; i < fn.numPrev(); i++ ) {
1319         FlatNode nn = fn.getPrev( i );
1320         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
1321         if( notAvailIn != null ) {
1322           dotSTnotAvailSet.addAll( notAvailIn );
1323         }
1324       }
1325
1326       Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
1327
1328       if( !seseStack.empty() ) {
1329         codePlans_nodeActions( fn,
1330                                dotSTlive,
1331                                dotSTtable,
1332                                dotSTnotAvailSet,
1333                                seseStack.peek()
1334                                );
1335       }
1336
1337       for( int i = 0; i < fn.numNext(); i++ ) {
1338         FlatNode nn = fn.getNext( i );
1339
1340         if( !visited.contains( nn ) ) {
1341           flatNodesToVisit.add( nn );
1342         }
1343       }
1344     }
1345   }
1346
1347   private void codePlans_nodeActions( FlatNode fn,
1348                                       Set<TempDescriptor> liveSetIn,
1349                                       VarSrcTokTable vstTableIn,
1350                                       Set<TempDescriptor> notAvailSetIn,
1351                                       FlatSESEEnterNode currentSESE ) {
1352
1353     CodePlan plan = new CodePlan( currentSESE);
1354
1355     switch( fn.kind() ) {
1356
1357     case FKind.FlatSESEEnterNode: {
1358       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
1359
1360       // track the source types of the in-var set so generated
1361       // code at this SESE issue can compute the number of
1362       // dependencies properly
1363       Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
1364       while( inVarItr.hasNext() ) {
1365         TempDescriptor inVar = inVarItr.next();
1366         Integer srcType =
1367           vstTableIn.getRefVarSrcType( inVar,
1368                                        fsen,
1369                                        fsen.getParent() );
1370
1371         // the current SESE needs a local space to track the dynamic
1372         // variable and the child needs space in its SESE record
1373         if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1374           fsen.addDynamicInVar( inVar );
1375           fsen.getParent().addDynamicVar( inVar );
1376
1377         } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1378           fsen.addStaticInVar( inVar );
1379           VariableSourceToken vst = vstTableIn.get( inVar ).iterator().next();
1380           fsen.putStaticInVar2src( inVar, vst );
1381           fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
1382                                                       vst.getAge()
1383                                                     )
1384                                 );
1385
1386         } else {
1387           assert srcType.equals( VarSrcTokTable.SrcType_READY );
1388           fsen.addReadyInVar( inVar );
1389         }
1390       }
1391
1392     } break;
1393
1394     case FKind.FlatSESEExitNode: {
1395       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
1396     } break;
1397
1398     case FKind.FlatOpNode: {
1399       FlatOpNode fon = (FlatOpNode) fn;
1400
1401       if( fon.getOp().getOp() == Operation.ASSIGN ) {
1402         TempDescriptor lhs = fon.getDest();
1403         TempDescriptor rhs = fon.getLeft();
1404
1405         // if this is an op node, don't stall, copy
1406         // source and delay until we need to use value
1407
1408         // ask whether lhs and rhs sources are dynamic, static, etc.
1409         Integer lhsSrcType
1410           = vstTableIn.getRefVarSrcType( lhs,
1411                                          currentSESE,
1412                                          currentSESE.getParent() );
1413
1414         Integer rhsSrcType
1415           = vstTableIn.getRefVarSrcType( rhs,
1416                                          currentSESE,
1417                                          currentSESE.getParent() );
1418
1419         if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1420           // if rhs is dynamic going in, lhs will definitely be dynamic
1421           // going out of this node, so track that here
1422           plan.addDynAssign( lhs, rhs );
1423           currentSESE.addDynamicVar( lhs );
1424           currentSESE.addDynamicVar( rhs );
1425
1426         } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1427           // otherwise, if the lhs is dynamic, but the rhs is not, we
1428           // need to update the variable's dynamic source as "current SESE"
1429           plan.addDynAssign( lhs );
1430         }
1431
1432         // only break if this is an ASSIGN op node,
1433         // otherwise fall through to default case
1434         break;
1435       }
1436     }
1437
1438     // note that FlatOpNode's that aren't ASSIGN
1439     // fall through to this default case
1440     default: {
1441
1442       // a node with no live set has nothing to stall for
1443       if( liveSetIn == null ) {
1444         break;
1445       }
1446
1447       TempDescriptor[] readarray = fn.readsTemps();
1448       for( int i = 0; i < readarray.length; i++ ) {
1449         TempDescriptor readtmp = readarray[i];
1450
1451         // ignore temps that are definitely available
1452         // when considering to stall on it
1453         if( !notAvailSetIn.contains( readtmp ) ) {
1454           continue;
1455         }
1456
1457         // check the source type of this variable
1458         Integer srcType
1459           = vstTableIn.getRefVarSrcType( readtmp,
1460                                          currentSESE,
1461                                          currentSESE.getParent() );
1462
1463         if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1464           // 1) It is not clear statically where this variable will
1465           // come from statically, so dynamically we must keep track
1466           // along various control paths, and therefore when we stall,
1467           // just stall for the exact thing we need and move on
1468           plan.addDynamicStall( readtmp );
1469           currentSESE.addDynamicVar( readtmp );
1470
1471         } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1472           // 2) Single token/age pair: Stall for token/age pair, and copy
1473           // all live variables with same token/age pair at the same
1474           // time.  This is the same stuff that the notavaialable analysis
1475           // marks as now available.
1476
1477           VariableSourceToken vst = vstTableIn.get( readtmp ).iterator().next();
1478
1479           Iterator<VariableSourceToken> availItr =
1480             vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
1481
1482           while( availItr.hasNext() ) {
1483             VariableSourceToken vstAlsoAvail = availItr.next();
1484
1485             // only grab additional stuff that is live
1486             Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
1487
1488             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
1489             while( refVarItr.hasNext() ) {
1490               TempDescriptor refVar = refVarItr.next();
1491               if( liveSetIn.contains( refVar ) ) {
1492                 copySet.add( refVar );
1493               }
1494             }
1495
1496             if( !copySet.isEmpty() ) {
1497               plan.addStall2CopySet( vstAlsoAvail, copySet );
1498             }
1499           }
1500
1501         } else {
1502           // the other case for srcs is READY, so do nothing
1503         }
1504
1505         // assert that everything being stalled for is in the
1506         // "not available" set coming into this flat node and
1507         // that every VST identified is in the possible "stall set"
1508         // that represents VST's from children SESE's
1509
1510       }
1511     } break;
1512
1513     } // end switch
1514
1515
1516     // identify sese-age pairs that are statically useful
1517     // and should have an associated SESE variable in code
1518     // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1519     // AND ALWAYS GIVE NAMES TO PARENTS
1520     Set<VariableSourceToken> staticSet = vstTableIn.get();
1521     Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1522     while( vstItr.hasNext() ) {
1523       VariableSourceToken vst = vstItr.next();
1524
1525       // placeholder source tokens are useful results, but
1526       // the placeholder static name is never needed
1527       if( vst.getSESE().getIsCallerSESEplaceholder() ) {
1528         continue;
1529       }
1530
1531       FlatSESEEnterNode sese = currentSESE;
1532       while( sese != null ) {
1533         sese.addNeededStaticName(
1534                                  new SESEandAgePair( vst.getSESE(), vst.getAge() )
1535                                   );
1536         sese.mustTrackAtLeastAge( vst.getAge() );
1537
1538         sese = sese.getParent();
1539       }
1540     }
1541
1542
1543     codePlans.put( fn, plan );
1544
1545
1546     // if any variables at this-node-*dot* have a static source (exactly one vst)
1547     // but go to a dynamic source at next-node-*dot*, create a new IR graph
1548     // node on that edge to track the sources dynamically
1549     VarSrcTokTable thisVstTable = variableResults.get( fn );
1550     for( int i = 0; i < fn.numNext(); i++ ) {
1551       FlatNode            nn           = fn.getNext( i );
1552       VarSrcTokTable      nextVstTable = variableResults.get( nn );
1553       Set<TempDescriptor> nextLiveIn   = livenessRootView.get( nn );
1554
1555       // the table can be null if it is one of the few IR nodes
1556       // completely outside of the root SESE scope
1557       if( nextVstTable != null && nextLiveIn != null ) {
1558
1559         Hashtable<TempDescriptor, VariableSourceToken> static2dynamicSet =
1560           thisVstTable.getStatic2DynamicSet( nextVstTable,
1561                                              nextLiveIn,
1562                                              currentSESE,
1563                                              currentSESE.getParent()
1564                                            );
1565
1566         if( !static2dynamicSet.isEmpty() ) {
1567
1568           // either add these results to partial fixed-point result
1569           // or make a new one if we haven't made any here yet
1570           FlatEdge fe = new FlatEdge( fn, nn );
1571           FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
1572
1573           if( fwdvn == null ) {
1574             fwdvn = new FlatWriteDynamicVarNode( fn,
1575                                                  nn,
1576                                                  static2dynamicSet,
1577                                                  currentSESE
1578                                                  );
1579             wdvNodesToSpliceIn.put( fe, fwdvn );
1580           } else {
1581             fwdvn.addMoreVar2Src( static2dynamicSet );
1582           }
1583         }
1584       }
1585     }
1586   }
1587
1588
1589   public void writeReports( String timeReport ) throws java.io.IOException {
1590
1591     BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
1592     bw.write( "MLP Analysis Results\n\n" );
1593     bw.write( timeReport+"\n\n" );
1594     printSESEHierarchy( bw );
1595     bw.write( "\n" );
1596     printSESEInfo( bw );
1597     bw.close();
1598
1599     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
1600     while( methItr.hasNext() ) {
1601       MethodDescriptor md = (MethodDescriptor) methItr.next();
1602       FlatMethod       fm = state.getMethodFlat( md );
1603       bw = new BufferedWriter( new FileWriter( "mlpReport_"+
1604                                                md.getClassMethodName()+
1605                                                md.getSafeMethodDescriptor()+
1606                                                ".txt" ) );
1607       bw.write( "MLP Results for "+md+"\n-------------------\n");
1608       bw.write( "\n\nLive-In, Root View\n------------------\n"          +fm.printMethod( livenessRootView ) );
1609       bw.write( "\n\nVariable Results-Out\n----------------\n"          +fm.printMethod( variableResults ) );
1610       bw.write( "\n\nNot Available Results-Out\n---------------------\n"+fm.printMethod( notAvailableResults ) );
1611       bw.write( "\n\nCode Plans\n----------\n"                          +fm.printMethod( codePlans ) );
1612       bw.write("\n\nSESE Effects\n----------------------\n"+printSESEEffects());
1613       bw.close();
1614     }
1615   }
1616
1617         private String printSESEEffects() {
1618
1619                 StringWriter writer = new StringWriter();
1620
1621                 Iterator<FlatSESEEnterNode> keyIter = allSESEs.iterator();
1622
1623                 while (keyIter.hasNext()) {
1624                         FlatSESEEnterNode seseEnter = keyIter.next();
1625                         String result = seseEnter.getSeseEffectsSet().printSet();
1626                         if (result.length() > 0) {
1627                                 writer.write("\nSESE " + seseEnter + "\n");
1628                                 writer.write(result);
1629                         }
1630                 }
1631                 keyIter = rootSESEs.iterator();
1632                 while (keyIter.hasNext()) {
1633                         FlatSESEEnterNode seseEnter = keyIter.next();
1634                         if (seseEnter.getIsCallerSESEplaceholder()) {
1635                                 if (!seseEnter.getChildren().isEmpty()) {
1636                                         String result = seseEnter.getSeseEffectsSet().printSet();
1637                                         if (result.length() > 0) {
1638                                                 writer.write("\nSESE " + seseEnter + "\n");
1639                                                 writer.write(result);
1640                                         }
1641                                 }
1642                         }
1643                 }
1644
1645                 return writer.toString();
1646
1647         }
1648
1649   private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
1650     bw.write( "SESE Hierarchy\n--------------\n" );
1651     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
1652     while( rootItr.hasNext() ) {
1653       FlatSESEEnterNode root = rootItr.next();
1654       if( root.getIsCallerSESEplaceholder() ) {
1655         if( !root.getChildren().isEmpty() ) {
1656           printSESEHierarchyTree( bw, root, 0 );
1657         }
1658       } else {
1659         printSESEHierarchyTree( bw, root, 0 );
1660       }
1661     }
1662   }
1663
1664   private void printSESEHierarchyTree( BufferedWriter bw,
1665                                        FlatSESEEnterNode fsen,
1666                                        int depth
1667                                      ) throws java.io.IOException {
1668     for( int i = 0; i < depth; ++i ) {
1669       bw.write( "  " );
1670     }
1671     bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
1672
1673     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1674     while( childItr.hasNext() ) {
1675       FlatSESEEnterNode fsenChild = childItr.next();
1676       printSESEHierarchyTree( bw, fsenChild, depth + 1 );
1677     }
1678   }
1679
1680
1681   private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
1682     bw.write("\nSESE info\n-------------\n" );
1683     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
1684     while( rootItr.hasNext() ) {
1685       FlatSESEEnterNode root = rootItr.next();
1686       if( root.getIsCallerSESEplaceholder() ) {
1687         if( !root.getChildren().isEmpty() ) {
1688           printSESEInfoTree( bw, root );
1689         }
1690       } else {
1691         printSESEInfoTree( bw, root );
1692       }
1693     }
1694   }
1695
1696   private void printSESEInfoTree( BufferedWriter bw,
1697                                   FlatSESEEnterNode fsen
1698                                 ) throws java.io.IOException {
1699
1700     if( !fsen.getIsCallerSESEplaceholder() ) {
1701       bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
1702
1703       bw.write( "  in-set: "+fsen.getInVarSet()+"\n" );
1704       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1705       while( tItr.hasNext() ) {
1706         TempDescriptor inVar = tItr.next();
1707         if( fsen.getReadyInVarSet().contains( inVar ) ) {
1708           bw.write( "    (ready)  "+inVar+"\n" );
1709         }
1710         if( fsen.getStaticInVarSet().contains( inVar ) ) {
1711           bw.write( "    (static) "+inVar+"\n" );
1712         }
1713         if( fsen.getDynamicInVarSet().contains( inVar ) ) {
1714           bw.write( "    (dynamic)"+inVar+"\n" );
1715         }
1716       }
1717
1718       bw.write( "  out-set: "+fsen.getOutVarSet()+"\n" );
1719       bw.write( "}\n" );
1720     }
1721
1722     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1723     while( childItr.hasNext() ) {
1724       FlatSESEEnterNode fsenChild = childItr.next();
1725       printSESEInfoTree( bw, fsenChild );
1726     }
1727   }
1728 }