lib/Transforms/Scalar/EarlyCSE.cpp

   1 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass performs a simple dominator tree walk that eliminates trivially
  11 // redundant instructions.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "early-cse"
  16 #include "llvm/Transforms/Scalar.h"
  17 #include "llvm/ADT/Hashing.h"
  18 #include "llvm/ADT/ScopedHashTable.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/Analysis/InstructionSimplify.h"
  21 #include "llvm/IR/DataLayout.h"
  22 #include "llvm/IR/Dominators.h"
  23 #include "llvm/IR/Instructions.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/RecyclingAllocator.h"
  27 #include "llvm/Target/TargetLibraryInfo.h"
  28 #include "llvm/Transforms/Utils/Local.h"
  29 #include <vector>
  30 using namespace llvm;
  31
  32 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
  33 STATISTIC(NumCSE,      "Number of instructions CSE'd");
  34 STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
  35 STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
  36 STATISTIC(NumDSE,      "Number of trivial dead stores removed");
  37
  38 static unsigned getHash(const void *V) {
  39   return DenseMapInfo<const void*>::getHashValue(V);
  40 }
  41
  42 //===----------------------------------------------------------------------===//
  43 // SimpleValue
  44 //===----------------------------------------------------------------------===//
  45
  46 namespace {
  47   /// SimpleValue - Instances of this struct represent available values in the
  48   /// scoped hash table.
  49   struct SimpleValue {
  50     Instruction *Inst;
  51
  52     SimpleValue(Instruction *I) : Inst(I) {
  53       assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
  54     }
  55
  56     bool isSentinel() const {
  57       return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
  58              Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
  59     }
  60
  61     static bool canHandle(Instruction *Inst) {
  62       // This can only handle non-void readnone functions.
  63       if (CallInst *CI = dyn_cast<CallInst>(Inst))
  64         return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
  65       return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
  66              isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
  67              isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
  68              isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
  69              isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
  70     }
  71   };
  72 }
  73
  74 namespace llvm {
  75 template<> struct DenseMapInfo<SimpleValue> {
  76   static inline SimpleValue getEmptyKey() {
  77     return DenseMapInfo<Instruction*>::getEmptyKey();
  78   }
  79   static inline SimpleValue getTombstoneKey() {
  80     return DenseMapInfo<Instruction*>::getTombstoneKey();
  81   }
  82   static unsigned getHashValue(SimpleValue Val);
  83   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
  84 };
  85 }
  86
  87 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
  88   Instruction *Inst = Val.Inst;
  89   // Hash in all of the operands as pointers.
  90   if (BinaryOperator* BinOp = dyn_cast<BinaryOperator>(Inst)) {
  91     Value *LHS = BinOp->getOperand(0);
  92     Value *RHS = BinOp->getOperand(1);
  93     if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
  94       std::swap(LHS, RHS);
  95
  96     if (isa<OverflowingBinaryOperator>(BinOp)) {
  97       // Hash the overflow behavior
  98       unsigned Overflow =
  99         BinOp->hasNoSignedWrap()   * OverflowingBinaryOperator::NoSignedWrap |
 100         BinOp->hasNoUnsignedWrap() * OverflowingBinaryOperator::NoUnsignedWrap;
 101       return hash_combine(BinOp->getOpcode(), Overflow, LHS, RHS);
 102     }
 103
 104     return hash_combine(BinOp->getOpcode(), LHS, RHS);
 105   }
 106
 107   if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
 108     Value *LHS = CI->getOperand(0);
 109     Value *RHS = CI->getOperand(1);
 110     CmpInst::Predicate Pred = CI->getPredicate();
 111     if (Inst->getOperand(0) > Inst->getOperand(1)) {
 112       std::swap(LHS, RHS);
 113       Pred = CI->getSwappedPredicate();
 114     }
 115     return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
 116   }
 117
 118   if (CastInst *CI = dyn_cast<CastInst>(Inst))
 119     return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
 120
 121   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
 122     return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
 123                         hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
 124
 125   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
 126     return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
 127                         IVI->getOperand(1),
 128                         hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
 129
 130   assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) ||
 131           isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) ||
 132           isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
 133           isa<ShuffleVectorInst>(Inst)) && "Invalid/unknown instruction");
 134
 135   // Mix in the opcode.
 136   return hash_combine(Inst->getOpcode(),
 137                       hash_combine_range(Inst->value_op_begin(),
 138                                          Inst->value_op_end()));
 139 }
 140
 141 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
 142   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 143
 144   if (LHS.isSentinel() || RHS.isSentinel())
 145     return LHSI == RHSI;
 146
 147   if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
 148   if (LHSI->isIdenticalTo(RHSI)) return true;
 149
 150   // If we're not strictly identical, we still might be a commutable instruction
 151   if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
 152     if (!LHSBinOp->isCommutative())
 153       return false;
 154
 155     assert(isa<BinaryOperator>(RHSI)
 156            && "same opcode, but different instruction type?");
 157     BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
 158
 159     // Check overflow attributes
 160     if (isa<OverflowingBinaryOperator>(LHSBinOp)) {
 161       assert(isa<OverflowingBinaryOperator>(RHSBinOp)
 162              && "same opcode, but different operator type?");
 163       if (LHSBinOp->hasNoUnsignedWrap() != RHSBinOp->hasNoUnsignedWrap() ||
 164           LHSBinOp->hasNoSignedWrap() != RHSBinOp->hasNoSignedWrap())
 165         return false;
 166     }
 167
 168     // Commuted equality
 169     return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
 170       LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
 171   }
 172   if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
 173     assert(isa<CmpInst>(RHSI)
 174            && "same opcode, but different instruction type?");
 175     CmpInst *RHSCmp = cast<CmpInst>(RHSI);
 176     // Commuted equality
 177     return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
 178       LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
 179       LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
 180   }
 181
 182   return false;
 183 }
 184
 185 //===----------------------------------------------------------------------===//
 186 // CallValue
 187 //===----------------------------------------------------------------------===//
 188
 189 namespace {
 190   /// CallValue - Instances of this struct represent available call values in
 191   /// the scoped hash table.
 192   struct CallValue {
 193     Instruction *Inst;
 194
 195     CallValue(Instruction *I) : Inst(I) {
 196       assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
 197     }
 198
 199     bool isSentinel() const {
 200       return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
 201              Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
 202     }
 203
 204     static bool canHandle(Instruction *Inst) {
 205       // Don't value number anything that returns void.
 206       if (Inst->getType()->isVoidTy())
 207         return false;
 208
 209       CallInst *CI = dyn_cast<CallInst>(Inst);
 210       if (CI == 0 || !CI->onlyReadsMemory())
 211         return false;
 212       return true;
 213     }
 214   };
 215 }
 216
 217 namespace llvm {
 218   template<> struct DenseMapInfo<CallValue> {
 219     static inline CallValue getEmptyKey() {
 220       return DenseMapInfo<Instruction*>::getEmptyKey();
 221     }
 222     static inline CallValue getTombstoneKey() {
 223       return DenseMapInfo<Instruction*>::getTombstoneKey();
 224     }
 225     static unsigned getHashValue(CallValue Val);
 226     static bool isEqual(CallValue LHS, CallValue RHS);
 227   };
 228 }
 229 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
 230   Instruction *Inst = Val.Inst;
 231   // Hash in all of the operands as pointers.
 232   unsigned Res = 0;
 233   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) {
 234     assert(!Inst->getOperand(i)->getType()->isMetadataTy() &&
 235            "Cannot value number calls with metadata operands");
 236     Res ^= getHash(Inst->getOperand(i)) << (i & 0xF);
 237   }
 238
 239   // Mix in the opcode.
 240   return (Res << 1) ^ Inst->getOpcode();
 241 }
 242
 243 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
 244   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 245   if (LHS.isSentinel() || RHS.isSentinel())
 246     return LHSI == RHSI;
 247   return LHSI->isIdenticalTo(RHSI);
 248 }
 249
 250
 251 //===----------------------------------------------------------------------===//
 252 // EarlyCSE pass.
 253 //===----------------------------------------------------------------------===//
 254
 255 namespace {
 256
 257 /// EarlyCSE - This pass does a simple depth-first walk over the dominator
 258 /// tree, eliminating trivially redundant instructions and using instsimplify
 259 /// to canonicalize things as it goes.  It is intended to be fast and catch
 260 /// obvious cases so that instcombine and other passes are more effective.  It
 261 /// is expected that a later pass of GVN will catch the interesting/hard
 262 /// cases.
 263 class EarlyCSE : public FunctionPass {
 264 public:
 265   const DataLayout *TD;
 266   const TargetLibraryInfo *TLI;
 267   DominatorTree *DT;
 268   typedef RecyclingAllocator<BumpPtrAllocator,
 269                       ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy;
 270   typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>,
 271                           AllocatorTy> ScopedHTType;
 272
 273   /// AvailableValues - This scoped hash table contains the current values of
 274   /// all of our simple scalar expressions.  As we walk down the domtree, we
 275   /// look to see if instructions are in this: if so, we replace them with what
 276   /// we find, otherwise we insert them so that dominated values can succeed in
 277   /// their lookup.
 278   ScopedHTType *AvailableValues;
 279
 280   /// AvailableLoads - This scoped hash table contains the current values
 281   /// of loads.  This allows us to get efficient access to dominating loads when
 282   /// we have a fully redundant load.  In addition to the most recent load, we
 283   /// keep track of a generation count of the read, which is compared against
 284   /// the current generation count.  The current generation count is
 285   /// incremented after every possibly writing memory operation, which ensures
 286   /// that we only CSE loads with other loads that have no intervening store.
 287   typedef RecyclingAllocator<BumpPtrAllocator,
 288     ScopedHashTableVal<Value*, std::pair<Value*, unsigned> > > LoadMapAllocator;
 289   typedef ScopedHashTable<Value*, std::pair<Value*, unsigned>,
 290                           DenseMapInfo<Value*>, LoadMapAllocator> LoadHTType;
 291   LoadHTType *AvailableLoads;
 292
 293   /// AvailableCalls - This scoped hash table contains the current values
 294   /// of read-only call values.  It uses the same generation count as loads.
 295   typedef ScopedHashTable<CallValue, std::pair<Value*, unsigned> > CallHTType;
 296   CallHTType *AvailableCalls;
 297
 298   /// CurrentGeneration - This is the current generation of the memory value.
 299   unsigned CurrentGeneration;
 300
 301   static char ID;
 302   explicit EarlyCSE() : FunctionPass(ID) {
 303     initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
 304   }
 305
 306   bool runOnFunction(Function &F);
 307
 308 private:
 309
 310   // NodeScope - almost a POD, but needs to call the constructors for the
 311   // scoped hash tables so that a new scope gets pushed on. These are RAII so
 312   // that the scope gets popped when the NodeScope is destroyed.
 313   class NodeScope {
 314    public:
 315     NodeScope(ScopedHTType *availableValues,
 316               LoadHTType *availableLoads,
 317               CallHTType *availableCalls) :
 318         Scope(*availableValues),
 319         LoadScope(*availableLoads),
 320         CallScope(*availableCalls) {}
 321
 322    private:
 323     NodeScope(const NodeScope&) LLVM_DELETED_FUNCTION;
 324     void operator=(const NodeScope&) LLVM_DELETED_FUNCTION;
 325
 326     ScopedHTType::ScopeTy Scope;
 327     LoadHTType::ScopeTy LoadScope;
 328     CallHTType::ScopeTy CallScope;
 329   };
 330
 331   // StackNode - contains all the needed information to create a stack for
 332   // doing a depth first tranversal of the tree. This includes scopes for
 333   // values, loads, and calls as well as the generation. There is a child
 334   // iterator so that the children do not need to be store spearately.
 335   class StackNode {
 336    public:
 337     StackNode(ScopedHTType *availableValues,
 338               LoadHTType *availableLoads,
 339               CallHTType *availableCalls,
 340               unsigned cg, DomTreeNode *n,
 341               DomTreeNode::iterator child, DomTreeNode::iterator end) :
 342         CurrentGeneration(cg), ChildGeneration(cg), Node(n),
 343         ChildIter(child), EndIter(end),
 344         Scopes(availableValues, availableLoads, availableCalls),
 345         Processed(false) {}
 346
 347     // Accessors.
 348     unsigned currentGeneration() { return CurrentGeneration; }
 349     unsigned childGeneration() { return ChildGeneration; }
 350     void childGeneration(unsigned generation) { ChildGeneration = generation; }
 351     DomTreeNode *node() { return Node; }
 352     DomTreeNode::iterator childIter() { return ChildIter; }
 353     DomTreeNode *nextChild() {
 354       DomTreeNode *child = *ChildIter;
 355       ++ChildIter;
 356       return child;
 357     }
 358     DomTreeNode::iterator end() { return EndIter; }
 359     bool isProcessed() { return Processed; }
 360     void process() { Processed = true; }
 361
 362    private:
 363     StackNode(const StackNode&) LLVM_DELETED_FUNCTION;
 364     void operator=(const StackNode&) LLVM_DELETED_FUNCTION;
 365
 366     // Members.
 367     unsigned CurrentGeneration;
 368     unsigned ChildGeneration;
 369     DomTreeNode *Node;
 370     DomTreeNode::iterator ChildIter;
 371     DomTreeNode::iterator EndIter;
 372     NodeScope Scopes;
 373     bool Processed;
 374   };
 375
 376   bool processNode(DomTreeNode *Node);
 377
 378   // This transformation requires dominator postdominator info
 379   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 380     AU.addRequired<DominatorTreeWrapperPass>();
 381     AU.addRequired<TargetLibraryInfo>();
 382     AU.setPreservesCFG();
 383   }
 384 };
 385 }
 386
 387 char EarlyCSE::ID = 0;
 388
 389 // createEarlyCSEPass - The public interface to this file.
 390 FunctionPass *llvm::createEarlyCSEPass() {
 391   return new EarlyCSE();
 392 }
 393
 394 INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
 395 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 396 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 397 INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
 398
 399 bool EarlyCSE::processNode(DomTreeNode *Node) {
 400   BasicBlock *BB = Node->getBlock();
 401
 402   // If this block has a single predecessor, then the predecessor is the parent
 403   // of the domtree node and all of the live out memory values are still current
 404   // in this block.  If this block has multiple predecessors, then they could
 405   // have invalidated the live-out memory values of our parent value.  For now,
 406   // just be conservative and invalidate memory if this block has multiple
 407   // predecessors.
 408   if (BB->getSinglePredecessor() == 0)
 409     ++CurrentGeneration;
 410
 411   /// LastStore - Keep track of the last non-volatile store that we saw... for
 412   /// as long as there in no instruction that reads memory.  If we see a store
 413   /// to the same location, we delete the dead store.  This zaps trivial dead
 414   /// stores which can occur in bitfield code among other things.
 415   StoreInst *LastStore = 0;
 416
 417   bool Changed = false;
 418
 419   // See if any instructions in the block can be eliminated.  If so, do it.  If
 420   // not, add them to AvailableValues.
 421   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 422     Instruction *Inst = I++;
 423
 424     // Dead instructions should just be removed.
 425     if (isInstructionTriviallyDead(Inst, TLI)) {
 426       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
 427       Inst->eraseFromParent();
 428       Changed = true;
 429       ++NumSimplify;
 430       continue;
 431     }
 432
 433     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
 434     // its simpler value.
 435     if (Value *V = SimplifyInstruction(Inst, TD, TLI, DT)) {
 436       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
 437       Inst->replaceAllUsesWith(V);
 438       Inst->eraseFromParent();
 439       Changed = true;
 440       ++NumSimplify;
 441       continue;
 442     }
 443
 444     // If this is a simple instruction that we can value number, process it.
 445     if (SimpleValue::canHandle(Inst)) {
 446       // See if the instruction has an available value.  If so, use it.
 447       if (Value *V = AvailableValues->lookup(Inst)) {
 448         DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
 449         Inst->replaceAllUsesWith(V);
 450         Inst->eraseFromParent();
 451         Changed = true;
 452         ++NumCSE;
 453         continue;
 454       }
 455
 456       // Otherwise, just remember that this value is available.
 457       AvailableValues->insert(Inst, Inst);
 458       continue;
 459     }
 460
 461     // If this is a non-volatile load, process it.
 462     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 463       // Ignore volatile loads.
 464       if (!LI->isSimple()) {
 465         LastStore = 0;
 466         continue;
 467       }
 468
 469       // If we have an available version of this load, and if it is the right
 470       // generation, replace this instruction.
 471       std::pair<Value*, unsigned> InVal =
 472         AvailableLoads->lookup(Inst->getOperand(0));
 473       if (InVal.first != 0 && InVal.second == CurrentGeneration) {
 474         DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst << "  to: "
 475               << *InVal.first << '\n');
 476         if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
 477         Inst->eraseFromParent();
 478         Changed = true;
 479         ++NumCSELoad;
 480         continue;
 481       }
 482
 483       // Otherwise, remember that we have this instruction.
 484       AvailableLoads->insert(Inst->getOperand(0),
 485                           std::pair<Value*, unsigned>(Inst, CurrentGeneration));
 486       LastStore = 0;
 487       continue;
 488     }
 489
 490     // If this instruction may read from memory, forget LastStore.
 491     if (Inst->mayReadFromMemory())
 492       LastStore = 0;
 493
 494     // If this is a read-only call, process it.
 495     if (CallValue::canHandle(Inst)) {
 496       // If we have an available version of this call, and if it is the right
 497       // generation, replace this instruction.
 498       std::pair<Value*, unsigned> InVal = AvailableCalls->lookup(Inst);
 499       if (InVal.first != 0 && InVal.second == CurrentGeneration) {
 500         DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst << "  to: "
 501                      << *InVal.first << '\n');
 502         if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
 503         Inst->eraseFromParent();
 504         Changed = true;
 505         ++NumCSECall;
 506         continue;
 507       }
 508
 509       // Otherwise, remember that we have this instruction.
 510       AvailableCalls->insert(Inst,
 511                          std::pair<Value*, unsigned>(Inst, CurrentGeneration));
 512       continue;
 513     }
 514
 515     // Okay, this isn't something we can CSE at all.  Check to see if it is
 516     // something that could modify memory.  If so, our available memory values
 517     // cannot be used so bump the generation count.
 518     if (Inst->mayWriteToMemory()) {
 519       ++CurrentGeneration;
 520
 521       if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 522         // We do a trivial form of DSE if there are two stores to the same
 523         // location with no intervening loads.  Delete the earlier store.
 524         if (LastStore &&
 525             LastStore->getPointerOperand() == SI->getPointerOperand()) {
 526           DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore << "  due to: "
 527                        << *Inst << '\n');
 528           LastStore->eraseFromParent();
 529           Changed = true;
 530           ++NumDSE;
 531           LastStore = 0;
 532           continue;
 533         }
 534
 535         // Okay, we just invalidated anything we knew about loaded values.  Try
 536         // to salvage *something* by remembering that the stored value is a live
 537         // version of the pointer.  It is safe to forward from volatile stores
 538         // to non-volatile loads, so we don't have to check for volatility of
 539         // the store.
 540         AvailableLoads->insert(SI->getPointerOperand(),
 541          std::pair<Value*, unsigned>(SI->getValueOperand(), CurrentGeneration));
 542
 543         // Remember that this was the last store we saw for DSE.
 544         if (SI->isSimple())
 545           LastStore = SI;
 546       }
 547     }
 548   }
 549
 550   return Changed;
 551 }
 552
 553
 554 bool EarlyCSE::runOnFunction(Function &F) {
 555   std::vector<StackNode *> nodesToProcess;
 556
 557   TD = getAnalysisIfAvailable<DataLayout>();
 558   TLI = &getAnalysis<TargetLibraryInfo>();
 559   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 560
 561   // Tables that the pass uses when walking the domtree.
 562   ScopedHTType AVTable;
 563   AvailableValues = &AVTable;
 564   LoadHTType LoadTable;
 565   AvailableLoads = &LoadTable;
 566   CallHTType CallTable;
 567   AvailableCalls = &CallTable;
 568
 569   CurrentGeneration = 0;
 570   bool Changed = false;
 571
 572   // Process the root node.
 573   nodesToProcess.push_back(
 574       new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
 575                     CurrentGeneration, DT->getRootNode(),
 576                     DT->getRootNode()->begin(),
 577                     DT->getRootNode()->end()));
 578
 579   // Save the current generation.
 580   unsigned LiveOutGeneration = CurrentGeneration;
 581
 582   // Process the stack.
 583   while (!nodesToProcess.empty()) {
 584     // Grab the first item off the stack. Set the current generation, remove
 585     // the node from the stack, and process it.
 586     StackNode *NodeToProcess = nodesToProcess.back();
 587
 588     // Initialize class members.
 589     CurrentGeneration = NodeToProcess->currentGeneration();
 590
 591     // Check if the node needs to be processed.
 592     if (!NodeToProcess->isProcessed()) {
 593       // Process the node.
 594       Changed |= processNode(NodeToProcess->node());
 595       NodeToProcess->childGeneration(CurrentGeneration);
 596       NodeToProcess->process();
 597     } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
 598       // Push the next child onto the stack.
 599       DomTreeNode *child = NodeToProcess->nextChild();
 600       nodesToProcess.push_back(
 601           new StackNode(AvailableValues,
 602                         AvailableLoads,
 603                         AvailableCalls,
 604                         NodeToProcess->childGeneration(), child,
 605                         child->begin(), child->end()));
 606     } else {
 607       // It has been processed, and there are no more children to process,
 608       // so delete it and pop it off the stack.
 609       delete NodeToProcess;
 610       nodesToProcess.pop_back();
 611     }
 612   } // while (!nodes...)
 613
 614   // Reset the current generation.
 615   CurrentGeneration = LiveOutGeneration;
 616
 617   return Changed;
 618 }