EarlyCSE.cpp revision 263508 
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/Dominators.h"
21#include "llvm/Analysis/InstructionSimplify.h"
22#include "llvm/IR/DataLayout.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 <deque>
30using namespace llvm;
31
32STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
33STATISTIC(NumCSE,      "Number of instructions CSE'd");
34STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
35STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
36STATISTIC(NumDSE,      "Number of trivial dead stores removed");
37
38static unsigned getHash(const void *V) {
39  return DenseMapInfo<const void*>::getHashValue(V);
40}
41
42//===----------------------------------------------------------------------===//
43// SimpleValue
44//===----------------------------------------------------------------------===//
45
46namespace {
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
74namespace llvm {
75template<> 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
87unsigned 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
141bool 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
189namespace {
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
217namespace 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}
229unsigned 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
243bool 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
255namespace {
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.
263class EarlyCSE : public FunctionPass {
264public:
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
308private:
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<DominatorTree>();
381    AU.addRequired<TargetLibraryInfo>();
382    AU.setPreservesCFG();
383  }
384};
385}
386
387char EarlyCSE::ID = 0;
388
389// createEarlyCSEPass - The public interface to this file.
390FunctionPass *llvm::createEarlyCSEPass() {
391  return new EarlyCSE();
392}
393
394INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
395INITIALIZE_PASS_DEPENDENCY(DominatorTree)
396INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
397INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
398
399bool 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
554bool EarlyCSE::runOnFunction(Function &F) {
555  std::deque<StackNode *> nodesToProcess;
556
557  TD = getAnalysisIfAvailable<DataLayout>();
558  TLI = &getAnalysis<TargetLibraryInfo>();
559  DT = &getAnalysis<DominatorTree>();
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_front(
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.front();
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_front(
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_front();
611    }
612  } // while (!nodes...)
613
614  // Reset the current generation.
615  CurrentGeneration = LiveOutGeneration;
616
617  return Changed;
618}
619