Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java

   1 package Analysis.OoOJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.Set;
   7 import java.util.Stack;
   8
   9 import Analysis.CallGraph.CallGraph;
  10 import Analysis.ArrayReferencees;
  11 import Analysis.Liveness;
  12 import Analysis.RBlockRelationAnalysis;
  13 import Analysis.Disjoint.DisjointAnalysis;
  14 import IR.Descriptor;
  15 import IR.MethodDescriptor;
  16 import IR.Operation;
  17 import IR.State;
  18 import IR.TypeUtil;
  19 import IR.Flat.FKind;
  20 import IR.Flat.FlatEdge;
  21 import IR.Flat.FlatMethod;
  22 import IR.Flat.FlatNode;
  23 import IR.Flat.FlatOpNode;
  24 import IR.Flat.FlatReturnNode;
  25 import IR.Flat.FlatSESEEnterNode;
  26 import IR.Flat.FlatSESEExitNode;
  27 import IR.Flat.FlatWriteDynamicVarNode;
  28 import IR.Flat.TempDescriptor;
  29
  30 public class OoOJavaAnalysis {
  31
  32   // data from the compiler
  33   private State state;
  34   private TypeUtil typeUtil;
  35   private CallGraph callGraph;
  36   private RBlockRelationAnalysis rblockRel;
  37   private DisjointAnalysis disjointAnalysisTaints;
  38   private DisjointAnalysis disjointAnalysisReach;
  39
  40   private Hashtable<FlatNode, Set<TempDescriptor>> livenessRootView;
  41   private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
  42   private Hashtable<FlatNode, VarSrcTokTable> variableResults;
  43   private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
  44   private Hashtable<FlatNode, CodePlan> codePlans;
  45
  46   private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
  47
  48   private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
  49
  50 //  private Hashtable<FlatNode, ParentChildConflictsMap> conflictsResults;
  51 //  private Hashtable<FlatMethod, MethodSummary> methodSummaryResults;
  52 //  private OwnershipAnalysis ownAnalysisForSESEConflicts;
  53 //  private Hashtable<FlatNode, ConflictGraph> conflictGraphResults;
  54
  55 //  static private int uniqueLockSetId = 0;
  56
  57   public static int maxSESEage = -1;
  58
  59   public int getMaxSESEage() {
  60     return maxSESEage;
  61   }
  62
  63   // may be null
  64   public CodePlan getCodePlan(FlatNode fn) {
  65     CodePlan cp = codePlans.get(fn);
  66     return cp;
  67   }
  68
  69   public OoOJavaAnalysis(State state,
  70                          TypeUtil typeUtil,
  71                          CallGraph callGraph,
  72                          Liveness liveness,
  73                          ArrayReferencees arrayReferencees) {
  74
  75     double timeStartAnalysis = (double) System.nanoTime();
  76
  77     this.state = state;
  78     this.typeUtil = typeUtil;
  79     this.callGraph = callGraph;
  80     this.maxSESEage = state.MLP_MAXSESEAGE;
  81
  82     livenessRootView = new Hashtable<FlatNode, Set<TempDescriptor>>();
  83     livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
  84     variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
  85     notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
  86     codePlans = new Hashtable<FlatNode, CodePlan>();
  87     wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
  88
  89     notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
  90
  91     // add all methods transitively reachable from the
  92     // source's main to set for analysis
  93     MethodDescriptor mdSourceEntry = typeUtil.getMain();
  94     FlatMethod       fmMain        = state.getMethodFlat( mdSourceEntry );
  95
  96     Set<MethodDescriptor> descriptorsToAnalyze =
  97       callGraph.getAllMethods( mdSourceEntry );
  98
  99     descriptorsToAnalyze.add( mdSourceEntry );
 100
 101
 102 //    conflictsResults = new Hashtable<FlatNode, ParentChildConflictsMap>();
 103 //    methodSummaryResults = new Hashtable<FlatMethod, MethodSummary>();
 104 //    conflictGraphResults = new Hashtable<FlatNode, ConflictGraph>();
 105
 106     // seseSummaryMap = new Hashtable<FlatNode, SESESummary>();
 107     // isAfterChildSESEIndicatorMap = new Hashtable<FlatNode, Boolean>();
 108     // conflictGraphLockMap = new Hashtable<ConflictGraph, HashSet<SESELock>>();
 109
 110     // 1st pass, find basic rblock relations
 111     rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
 112
 113     // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
 114     Iterator<FlatSESEEnterNode> rootItr =
 115       rblockRel.getRootSESEs().iterator();
 116     while (rootItr.hasNext()) {
 117       FlatSESEEnterNode root = rootItr.next();
 118       livenessAnalysisBackward(root, true, null);
 119     }
 120
 121     // 3rd pass, variable analysis
 122     Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
 123     while (methItr.hasNext()) {
 124       Descriptor d = methItr.next();
 125       FlatMethod fm = state.getMethodFlat(d);
 126
 127       // starting from roots do a forward, fixed-point
 128       // variable analysis for refinement and stalls
 129       variableAnalysisForward(fm);
 130     }
 131
 132     // 4th pass, compute liveness contribution from
 133     // virtual reads discovered in variable pass
 134     rootItr = rblockRel.getRootSESEs().iterator();
 135     while (rootItr.hasNext()) {
 136       FlatSESEEnterNode root = rootItr.next();
 137       livenessAnalysisBackward(root, true, null);
 138     }
 139
 140     // 5th pass, use disjointness with NO FLAGGED REGIONS
 141     // to compute taints and effects
 142     disjointAnalysisTaints =
 143       new DisjointAnalysis(state,
 144                            typeUtil,
 145                            callGraph,
 146                            liveness,
 147                            arrayReferencees,
 148                            rblockRel);
 149
 150     // 6th pass, not available analysis FOR VARIABLES!
 151     methItr = descriptorsToAnalyze.iterator();
 152     while (methItr.hasNext()) {
 153       Descriptor d = methItr.next();
 154       FlatMethod fm = state.getMethodFlat(d);
 155
 156       // compute what is not available at every program
 157       // point, in a forward fixed-point pass
 158       notAvailableForward(fm);
 159     }
 160
 161     // MORE PASSES?
 162
 163
 164   }
 165
 166
 167   private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel,
 168       Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
 169
 170     // start from an SESE exit, visit nodes in reverse up to
 171     // SESE enter in a fixed-point scheme, where children SESEs
 172     // should already be analyzed and therefore can be skipped
 173     // because child SESE enter node has all necessary info
 174     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 175
 176     if (toplevel) {
 177       flatNodesToVisit.add(fsen.getfmEnclosing().getFlatExit());
 178     } else {
 179       flatNodesToVisit.add(fsen.getFlatExit());
 180     }
 181
 182     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
 183
 184     if (toplevel) {
 185       liveout = new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
 186     }
 187
 188     while (!flatNodesToVisit.isEmpty()) {
 189       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 190       flatNodesToVisit.remove(fn);
 191
 192       Set<TempDescriptor> prev = livenessResults.get(fn);
 193
 194       // merge sets from control flow joins
 195       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 196       for (int i = 0; i < fn.numNext(); i++) {
 197         FlatNode nn = fn.getNext(i);
 198         Set<TempDescriptor> s = livenessResults.get(nn);
 199         if (s != null) {
 200           u.addAll(s);
 201         }
 202       }
 203
 204       Set<TempDescriptor> curr = liveness_nodeActions(fn, u, fsen, toplevel, liveout);
 205
 206       // if a new result, schedule backward nodes for analysis
 207       if (!curr.equals(prev)) {
 208         livenessResults.put(fn, curr);
 209
 210         // don't flow backwards past current SESE enter
 211         if (!fn.equals(fsen)) {
 212           for (int i = 0; i < fn.numPrev(); i++) {
 213             FlatNode nn = fn.getPrev(i);
 214             flatNodesToVisit.add(nn);
 215           }
 216         }
 217       }
 218     }
 219
 220     Set<TempDescriptor> s = livenessResults.get(fsen);
 221     if (s != null) {
 222       fsen.addInVarSet(s);
 223     }
 224
 225     // remember liveness per node from the root view as the
 226     // global liveness of variables for later passes to use
 227     if (toplevel) {
 228       livenessRootView.putAll(livenessResults);
 229     }
 230
 231     // post-order traversal, so do children first
 232     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 233     while (childItr.hasNext()) {
 234       FlatSESEEnterNode fsenChild = childItr.next();
 235       livenessAnalysisBackward(fsenChild, false, liveout);
 236     }
 237   }
 238
 239   private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn,
 240       FlatSESEEnterNode currentSESE, boolean toplevel,
 241       Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
 242     switch (fn.kind()) {
 243
 244     case FKind.FlatSESEExitNode:
 245       if (toplevel) {
 246         FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 247         if (!liveout.containsKey(fsexn)) {
 248           liveout.put(fsexn, new HashSet<TempDescriptor>());
 249         }
 250         liveout.get(fsexn).addAll(liveIn);
 251       }
 252       // no break, sese exits should also execute default actions
 253
 254     default: {
 255       // handle effects of statement in reverse, writes then reads
 256       TempDescriptor[] writeTemps = fn.writesTemps();
 257       for (int i = 0; i < writeTemps.length; ++i) {
 258         liveIn.remove(writeTemps[i]);
 259
 260         if (!toplevel) {
 261           FlatSESEExitNode fsexn = currentSESE.getFlatExit();
 262           Set<TempDescriptor> livetemps = liveout.get(fsexn);
 263           if (livetemps != null && livetemps.contains(writeTemps[i])) {
 264             // write to a live out temp...
 265             // need to put in SESE liveout set
 266             currentSESE.addOutVar(writeTemps[i]);
 267           }
 268         }
 269       }
 270
 271       TempDescriptor[] readTemps = fn.readsTemps();
 272       for (int i = 0; i < readTemps.length; ++i) {
 273         liveIn.add(readTemps[i]);
 274       }
 275
 276       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
 277       if (virtualReadTemps != null) {
 278         liveIn.addAll(virtualReadTemps);
 279       }
 280
 281     }
 282       break;
 283
 284     } // end switch
 285
 286     return liveIn;
 287   }
 288
 289   private void variableAnalysisForward(FlatMethod fm) {
 290
 291     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 292     flatNodesToVisit.add(fm);
 293
 294     while (!flatNodesToVisit.isEmpty()) {
 295       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 296       flatNodesToVisit.remove(fn);
 297
 298       Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
 299       assert seseStack != null;
 300
 301       VarSrcTokTable prev = variableResults.get(fn);
 302
 303       // merge sets from control flow joins
 304       VarSrcTokTable curr = new VarSrcTokTable();
 305       for (int i = 0; i < fn.numPrev(); i++) {
 306         FlatNode nn = fn.getPrev(i);
 307         VarSrcTokTable incoming = variableResults.get(nn);
 308         curr.merge(incoming);
 309       }
 310
 311       if (!seseStack.empty()) {
 312         variable_nodeActions(fn, curr, seseStack.peek());
 313       }
 314
 315       // if a new result, schedule forward nodes for analysis
 316       if (!curr.equals(prev)) {
 317         variableResults.put(fn, curr);
 318
 319         for (int i = 0; i < fn.numNext(); i++) {
 320           FlatNode nn = fn.getNext(i);
 321           flatNodesToVisit.add(nn);
 322         }
 323       }
 324     }
 325   }
 326
 327   private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
 328       FlatSESEEnterNode currentSESE) {
 329     switch (fn.kind()) {
 330
 331     case FKind.FlatSESEEnterNode: {
 332       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 333       assert fsen.equals(currentSESE);
 334
 335       vstTable.age(currentSESE);
 336       vstTable.assertConsistency();
 337     }
 338       break;
 339
 340     case FKind.FlatSESEExitNode: {
 341       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 342       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 343       assert currentSESE.getChildren().contains(fsen);
 344
 345       // remap all of this child's children tokens to be
 346       // from this child as the child exits
 347       vstTable.remapChildTokens(fsen);
 348
 349       // liveness virtual reads are things that might be
 350       // written by an SESE and should be added to the in-set
 351       // anything virtually read by this SESE should be pruned
 352       // of parent or sibling sources
 353       Set<TempDescriptor> liveVars = livenessRootView.get(fn);
 354       Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(
 355           fsen, liveVars);
 356       Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
 357       if (fsenVirtReadsOld != null) {
 358         fsenVirtReads.addAll(fsenVirtReadsOld);
 359       }
 360       livenessVirtualReads.put(fn, fsenVirtReads);
 361
 362       // then all child out-set tokens are guaranteed
 363       // to be filled in, so clobber those entries with
 364       // the latest, clean sources
 365       Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
 366       while (outVarItr.hasNext()) {
 367         TempDescriptor outVar = outVarItr.next();
 368         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 369         ts.add(outVar);
 370         VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
 371         vstTable.remove(outVar);
 372         vstTable.add(vst);
 373       }
 374       vstTable.assertConsistency();
 375
 376     }
 377       break;
 378
 379     case FKind.FlatOpNode: {
 380       FlatOpNode fon = (FlatOpNode) fn;
 381
 382       if (fon.getOp().getOp() == Operation.ASSIGN) {
 383         TempDescriptor lhs = fon.getDest();
 384         TempDescriptor rhs = fon.getLeft();
 385
 386         vstTable.remove(lhs);
 387
 388         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 389
 390         Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
 391         while (itr.hasNext()) {
 392           VariableSourceToken vst = itr.next();
 393
 394           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 395           ts.add(lhs);
 396
 397           if (currentSESE.getChildren().contains(vst.getSESE())) {
 398             // if the source comes from a child, copy it over
 399             forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
 400                 .getAddrVar()));
 401           } else {
 402             // otherwise, stamp it as us as the source
 403             forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
 404           }
 405         }
 406
 407         vstTable.addAll(forAddition);
 408
 409         // only break if this is an ASSIGN op node,
 410         // otherwise fall through to default case
 411         vstTable.assertConsistency();
 412         break;
 413       }
 414     }
 415
 416       // note that FlatOpNode's that aren't ASSIGN
 417       // fall through to this default case
 418     default: {
 419       TempDescriptor[] writeTemps = fn.writesTemps();
 420       if (writeTemps.length > 0) {
 421
 422         // for now, when writeTemps > 1, make sure
 423         // its a call node, programmer enforce only
 424         // doing stuff like calling a print routine
 425         // assert writeTemps.length == 1;
 426         if (writeTemps.length > 1) {
 427           assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
 428           break;
 429         }
 430
 431         vstTable.remove(writeTemps[0]);
 432
 433         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 434         ts.add(writeTemps[0]);
 435
 436         vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
 437       }
 438
 439       vstTable.assertConsistency();
 440     }
 441       break;
 442
 443     } // end switch
 444   }
 445
 446   private void notAvailableForward(FlatMethod fm) {
 447
 448     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 449     flatNodesToVisit.add(fm);
 450
 451     while (!flatNodesToVisit.isEmpty()) {
 452       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 453       flatNodesToVisit.remove(fn);
 454
 455       Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
 456       assert seseStack != null;
 457
 458       Set<TempDescriptor> prev = notAvailableResults.get(fn);
 459
 460       Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
 461       for (int i = 0; i < fn.numPrev(); i++) {
 462         FlatNode nn = fn.getPrev(i);
 463         Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
 464         if (notAvailIn != null) {
 465           curr.addAll(notAvailIn);
 466         }
 467       }
 468
 469       if (!seseStack.empty()) {
 470         notAvailable_nodeActions(fn, curr, seseStack.peek());
 471       }
 472
 473       // if a new result, schedule forward nodes for analysis
 474       if (!curr.equals(prev)) {
 475         notAvailableResults.put(fn, curr);
 476
 477         for (int i = 0; i < fn.numNext(); i++) {
 478           FlatNode nn = fn.getNext(i);
 479           flatNodesToVisit.add(nn);
 480         }
 481       }
 482     }
 483   }
 484
 485   private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
 486       FlatSESEEnterNode currentSESE) {
 487
 488     // any temps that are removed from the not available set
 489     // at this node should be marked in this node's code plan
 490     // as temps to be grabbed at runtime!
 491
 492     switch (fn.kind()) {
 493
 494     case FKind.FlatSESEEnterNode: {
 495       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 496       assert fsen.equals(currentSESE);
 497
 498       // keep a copy of what's not available into the SESE
 499       // and restore it at the matching exit node
 500       Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
 501       Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
 502       while (tdItr.hasNext()) {
 503         notAvailCopy.add(tdItr.next());
 504       }
 505       notAvailableIntoSESE.put(fsen, notAvailCopy);
 506
 507       notAvailSet.clear();
 508     }
 509       break;
 510
 511     case FKind.FlatSESEExitNode: {
 512       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 513       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 514       assert currentSESE.getChildren().contains(fsen);
 515
 516       notAvailSet.addAll(fsen.getOutVarSet());
 517
 518       Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
 519       assert notAvailIn != null;
 520       notAvailSet.addAll(notAvailIn);
 521
 522     }
 523       break;
 524
 525     case FKind.FlatMethod: {
 526       notAvailSet.clear();
 527     }
 528
 529     case FKind.FlatOpNode: {
 530       FlatOpNode fon = (FlatOpNode) fn;
 531
 532       if (fon.getOp().getOp() == Operation.ASSIGN) {
 533         TempDescriptor lhs = fon.getDest();
 534         TempDescriptor rhs = fon.getLeft();
 535
 536         // copy makes lhs same availability as rhs
 537         if (notAvailSet.contains(rhs)) {
 538           notAvailSet.add(lhs);
 539         } else {
 540           notAvailSet.remove(lhs);
 541         }
 542
 543         // only break if this is an ASSIGN op node,
 544         // otherwise fall through to default case
 545         break;
 546       }
 547     }
 548
 549       // note that FlatOpNode's that aren't ASSIGN
 550       // fall through to this default case
 551     default: {
 552       TempDescriptor[] writeTemps = fn.writesTemps();
 553       for (int i = 0; i < writeTemps.length; i++) {
 554         TempDescriptor wTemp = writeTemps[i];
 555         notAvailSet.remove(wTemp);
 556       }
 557       TempDescriptor[] readTemps = fn.readsTemps();
 558       for (int i = 0; i < readTemps.length; i++) {
 559         TempDescriptor rTemp = readTemps[i];
 560         notAvailSet.remove(rTemp);
 561
 562         // if this variable has exactly one source, potentially
 563         // get other things from this source as well
 564         VarSrcTokTable vstTable = variableResults.get(fn);
 565
 566         VSTWrapper vstIfStatic = new VSTWrapper();
 567         Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
 568
 569         if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
 570
 571           VariableSourceToken vst = vstIfStatic.vst;
 572
 573           Iterator<VariableSourceToken> availItr = vstTable.get(vst.getSESE(), vst.getAge())
 574               .iterator();
 575
 576           // look through things that are also available from same source
 577           while (availItr.hasNext()) {
 578             VariableSourceToken vstAlsoAvail = availItr.next();
 579
 580             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
 581             while (refVarItr.hasNext()) {
 582               TempDescriptor refVarAlso = refVarItr.next();
 583
 584               // if a variable is available from the same source, AND it ALSO
 585               // only comes from one statically known source, mark it available
 586               VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
 587               Integer srcTypeAlso = vstTable.getRefVarSrcType(refVarAlso, currentSESE,
 588                   vstIfStaticNotUsed);
 589               if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
 590                 notAvailSet.remove(refVarAlso);
 591               }
 592             }
 593           }
 594         }
 595       }
 596     }
 597       break;
 598
 599     } // end switch
 600   }
 601
 602 }