112be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
212be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//
312be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//                     The LLVM Compiler Infrastructure
412be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//
512be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner// This file is distributed under the University of Illinois Open Source
612be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner// License. See LICENSE.TXT for details.
712be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//
812be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//===----------------------------------------------------------------------===//
912be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//
1012be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner// This pass performs a simple dominator tree walk that eliminates trivially
1112be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner// redundant instructions.
1212be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//
1312be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner//===----------------------------------------------------------------------===//
1412be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner
1512be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner#include "llvm/Transforms/Scalar.h"
16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Hashing.h"
17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/ScopedHashTable.h"
18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h"
19cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner#include "llvm/Analysis/InstructionSimplify.h"
200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h"
2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h"
220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h"
23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h"
2491139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner#include "llvm/Support/Debug.h"
2582dcd5edd22f017b74ebe98acc07b3a7191e7ff1Chris Lattner#include "llvm/Support/RecyclingAllocator.h"
26d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetLibraryInfo.h"
27d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h"
2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include <vector>
2912be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattnerusing namespace llvm;
3012be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner
31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "early-cse"
32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines
33a60a8b0eb773eabb3ad83e610e737efda525a0daChris LattnerSTATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
34a60a8b0eb773eabb3ad83e610e737efda525a0daChris LattnerSTATISTIC(NumCSE,      "Number of instructions CSE'd");
3585db61066a370f5d6e2d3c667eb5fa02493593c7Chris LattnerSTATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
3685db61066a370f5d6e2d3c667eb5fa02493593c7Chris LattnerSTATISTIC(NumCSECall,  "Number of call instructions CSE'd");
3775637154c38da0243c51f4338137a78849808e50Chris LattnerSTATISTIC(NumDSE,      "Number of trivial dead stores removed");
388e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner
398e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattnerstatic unsigned getHash(const void *V) {
408e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  return DenseMapInfo<const void*>::getHashValue(V);
418e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner}
4291139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner
43f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner//===----------------------------------------------------------------------===//
44a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem// SimpleValue
45f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner//===----------------------------------------------------------------------===//
46f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner
4712be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattnernamespace {
48f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  /// SimpleValue - Instances of this struct represent available values in the
49cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  /// scoped hash table.
50f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  struct SimpleValue {
51cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    Instruction *Inst;
52a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
53a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner    SimpleValue(Instruction *I) : Inst(I) {
54a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner      assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
55a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner    }
56a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
57cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    bool isSentinel() const {
58cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
59cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner             Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
60cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    }
61a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
62cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    static bool canHandle(Instruction *Inst) {
63e508dd4c75705f325764e1197854c0e83266a7eaChris Lattner      // This can only handle non-void readnone functions.
64e508dd4c75705f325764e1197854c0e83266a7eaChris Lattner      if (CallInst *CI = dyn_cast<CallInst>(Inst))
65e508dd4c75705f325764e1197854c0e83266a7eaChris Lattner        return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
6691139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner      return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
6791139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner             isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
6891139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner             isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
6991139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner             isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
7091139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner             isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
71cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    }
72cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  };
73cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner}
74cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
75cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattnernamespace llvm {
76f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattnertemplate<> struct DenseMapInfo<SimpleValue> {
77f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  static inline SimpleValue getEmptyKey() {
78a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner    return DenseMapInfo<Instruction*>::getEmptyKey();
79cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  }
80f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  static inline SimpleValue getTombstoneKey() {
81a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner    return DenseMapInfo<Instruction*>::getTombstoneKey();
82cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  }
83f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  static unsigned getHashValue(SimpleValue Val);
84f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  static bool isEqual(SimpleValue LHS, SimpleValue RHS);
85cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner};
86cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner}
87cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
88f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattnerunsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
89cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  Instruction *Inst = Val.Inst;
90d957c717918c412402157b85fc51b4c6d2631381Chris Lattner  // Hash in all of the operands as pointers.
9139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  if (BinaryOperator* BinOp = dyn_cast<BinaryOperator>(Inst)) {
9239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    Value *LHS = BinOp->getOperand(0);
9339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    Value *RHS = BinOp->getOperand(1);
9439285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
9539285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      std::swap(LHS, RHS);
9639285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
9739285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    if (isa<OverflowingBinaryOperator>(BinOp)) {
9839285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      // Hash the overflow behavior
9939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      unsigned Overflow =
10039285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman        BinOp->hasNoSignedWrap()   * OverflowingBinaryOperator::NoSignedWrap |
10139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman        BinOp->hasNoUnsignedWrap() * OverflowingBinaryOperator::NoUnsignedWrap;
10239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      return hash_combine(BinOp->getOpcode(), Overflow, LHS, RHS);
10339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    }
104d957c717918c412402157b85fc51b4c6d2631381Chris Lattner
10539285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    return hash_combine(BinOp->getOpcode(), LHS, RHS);
10639285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  }
10739285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
10839285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
10939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    Value *LHS = CI->getOperand(0);
11039285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    Value *RHS = CI->getOperand(1);
11139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    CmpInst::Predicate Pred = CI->getPredicate();
11239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    if (Inst->getOperand(0) > Inst->getOperand(1)) {
11339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      std::swap(LHS, RHS);
11439285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      Pred = CI->getSwappedPredicate();
11539285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    }
11639285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
11791139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner  }
118d957c717918c412402157b85fc51b4c6d2631381Chris Lattner
11939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  if (CastInst *CI = dyn_cast<CastInst>(Inst))
12039285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
12139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
12239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
12339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
12439285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman                        hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
12539285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
12639285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
12739285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
12839285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman                        IVI->getOperand(1),
12939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman                        hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
13039285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
13139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) ||
13239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman          isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) ||
13339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman          isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
13439285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman          isa<ShuffleVectorInst>(Inst)) && "Invalid/unknown instruction");
13539285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
136d957c717918c412402157b85fc51b4c6d2631381Chris Lattner  // Mix in the opcode.
13739285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  return hash_combine(Inst->getOpcode(),
13839285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman                      hash_combine_range(Inst->value_op_begin(),
13939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman                                         Inst->value_op_end()));
140cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner}
141cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
142f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattnerbool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
143cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
144cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
145cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  if (LHS.isSentinel() || RHS.isSentinel())
146cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    return LHSI == RHSI;
147a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
148cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
14939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  if (LHSI->isIdenticalTo(RHSI)) return true;
15039285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
15139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  // If we're not strictly identical, we still might be a commutable instruction
15239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
15339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    if (!LHSBinOp->isCommutative())
15439285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      return false;
15539285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
15639285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    assert(isa<BinaryOperator>(RHSI)
15739285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman           && "same opcode, but different instruction type?");
15839285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
15939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
16039285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    // Check overflow attributes
16139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    if (isa<OverflowingBinaryOperator>(LHSBinOp)) {
16239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      assert(isa<OverflowingBinaryOperator>(RHSBinOp)
16339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman             && "same opcode, but different operator type?");
16439285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      if (LHSBinOp->hasNoUnsignedWrap() != RHSBinOp->hasNoUnsignedWrap() ||
16539285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman          LHSBinOp->hasNoSignedWrap() != RHSBinOp->hasNoSignedWrap())
16639285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman        return false;
16739285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    }
16839285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
16939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    // Commuted equality
17039285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
17139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
17239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  }
17339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
17439285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    assert(isa<CmpInst>(RHSI)
17539285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman           && "same opcode, but different instruction type?");
17639285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    CmpInst *RHSCmp = cast<CmpInst>(RHSI);
17739285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    // Commuted equality
17839285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman    return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
17939285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
18039285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman      LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
18139285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  }
18239285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman
18339285ab6dd985ecd725a4533460e90048a5297eaMichael Ilseman  return false;
184cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner}
185cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
1868e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner//===----------------------------------------------------------------------===//
187a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem// CallValue
1888e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner//===----------------------------------------------------------------------===//
1898e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner
1908e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattnernamespace {
19185db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// CallValue - Instances of this struct represent available call values in
19285db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// the scoped hash table.
19385db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  struct CallValue {
1948e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    Instruction *Inst;
195a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
19685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    CallValue(Instruction *I) : Inst(I) {
197a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner      assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
198a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner    }
199a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
2008e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    bool isSentinel() const {
2018e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner      return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
2028e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner             Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
2038e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    }
204a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
2058e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    static bool canHandle(Instruction *Inst) {
20610b883b13ff3ad44892758c7a57a435cdb379b45Chris Lattner      // Don't value number anything that returns void.
20710b883b13ff3ad44892758c7a57a435cdb379b45Chris Lattner      if (Inst->getType()->isVoidTy())
20810b883b13ff3ad44892758c7a57a435cdb379b45Chris Lattner        return false;
209a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
210a12ba39a1d4d22c8c2d348f1397d52be58391177Chris Lattner      CallInst *CI = dyn_cast<CallInst>(Inst);
211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines      if (!CI || !CI->onlyReadsMemory())
212a12ba39a1d4d22c8c2d348f1397d52be58391177Chris Lattner        return false;
213a12ba39a1d4d22c8c2d348f1397d52be58391177Chris Lattner      return true;
2148e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    }
2158e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  };
2168e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner}
2178e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner
2188e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattnernamespace llvm {
21985db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  template<> struct DenseMapInfo<CallValue> {
22085db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    static inline CallValue getEmptyKey() {
221a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner      return DenseMapInfo<Instruction*>::getEmptyKey();
2228e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    }
22385db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    static inline CallValue getTombstoneKey() {
224a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner      return DenseMapInfo<Instruction*>::getTombstoneKey();
2258e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    }
22685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    static unsigned getHashValue(CallValue Val);
22785db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    static bool isEqual(CallValue LHS, CallValue RHS);
2288e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  };
2298e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner}
23085db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattnerunsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
2318e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  Instruction *Inst = Val.Inst;
2328e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  // Hash in all of the operands as pointers.
2338e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  unsigned Res = 0;
23410b883b13ff3ad44892758c7a57a435cdb379b45Chris Lattner  for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) {
23510b883b13ff3ad44892758c7a57a435cdb379b45Chris Lattner    assert(!Inst->getOperand(i)->getType()->isMetadataTy() &&
23610b883b13ff3ad44892758c7a57a435cdb379b45Chris Lattner           "Cannot value number calls with metadata operands");
23718ead6b587159993b340ad4e2e2c5fed76e978c0Eli Friedman    Res ^= getHash(Inst->getOperand(i)) << (i & 0xF);
23810b883b13ff3ad44892758c7a57a435cdb379b45Chris Lattner  }
239a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
2408e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  // Mix in the opcode.
2418e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  return (Res << 1) ^ Inst->getOpcode();
2428e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner}
2438e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner
24485db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattnerbool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
2458e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
2468e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  if (LHS.isSentinel() || RHS.isSentinel())
2478e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    return LHSI == RHSI;
2488e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  return LHSI->isIdenticalTo(RHSI);
2498e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner}
2508e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner
251cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
252f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner//===----------------------------------------------------------------------===//
253a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem// EarlyCSE pass.
254f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner//===----------------------------------------------------------------------===//
255f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner
256cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattnernamespace {
257a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
25812be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner/// EarlyCSE - This pass does a simple depth-first walk over the dominator
25912be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner/// tree, eliminating trivially redundant instructions and using instsimplify
26012be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner/// to canonicalize things as it goes.  It is intended to be fast and catch
26112be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner/// obvious cases so that instcombine and other passes are more effective.  It
26212be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner/// is expected that a later pass of GVN will catch the interesting/hard
26312be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner/// cases.
26412be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattnerclass EarlyCSE : public FunctionPass {
26512be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattnerpublic:
26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  const DataLayout *DL;
267618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier  const TargetLibraryInfo *TLI;
268cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  DominatorTree *DT;
26982dcd5edd22f017b74ebe98acc07b3a7191e7ff1Chris Lattner  typedef RecyclingAllocator<BumpPtrAllocator,
270f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner                      ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy;
271f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>,
27282dcd5edd22f017b74ebe98acc07b3a7191e7ff1Chris Lattner                          AllocatorTy> ScopedHTType;
273a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
274f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  /// AvailableValues - This scoped hash table contains the current values of
275f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  /// all of our simple scalar expressions.  As we walk down the domtree, we
276f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  /// look to see if instructions are in this: if so, we replace them with what
277f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  /// we find, otherwise we insert them so that dominated values can succeed in
278f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  /// their lookup.
279f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  ScopedHTType *AvailableValues;
280a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
28185db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// AvailableLoads - This scoped hash table contains the current values
28285db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// of loads.  This allows us to get efficient access to dominating loads when
28385db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// we have a fully redundant load.  In addition to the most recent load, we
28485db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// keep track of a generation count of the read, which is compared against
28585db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// the current generation count.  The current generation count is
28685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// incremented after every possibly writing memory operation, which ensures
28785db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// that we only CSE loads with other loads that have no intervening store.
28871230acbbe734678b9ced643fa024166413b8824Chris Lattner  typedef RecyclingAllocator<BumpPtrAllocator,
28971230acbbe734678b9ced643fa024166413b8824Chris Lattner    ScopedHashTableVal<Value*, std::pair<Value*, unsigned> > > LoadMapAllocator;
29071230acbbe734678b9ced643fa024166413b8824Chris Lattner  typedef ScopedHashTable<Value*, std::pair<Value*, unsigned>,
29171230acbbe734678b9ced643fa024166413b8824Chris Lattner                          DenseMapInfo<Value*>, LoadMapAllocator> LoadHTType;
29285db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  LoadHTType *AvailableLoads;
293a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
29485db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// AvailableCalls - This scoped hash table contains the current values
29585db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  /// of read-only call values.  It uses the same generation count as loads.
29685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  typedef ScopedHashTable<CallValue, std::pair<Value*, unsigned> > CallHTType;
29785db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  CallHTType *AvailableCalls;
298a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
2998e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  /// CurrentGeneration - This is the current generation of the memory value.
3008e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  unsigned CurrentGeneration;
301a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
30212be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner  static char ID;
303f19745947daafd81d0d3bbdcdc7854053e0231fcChris Lattner  explicit EarlyCSE() : FunctionPass(ID) {
30412be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner    initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
30512be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner  }
30612be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner
30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  bool runOnFunction(Function &F) override;
30812be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner
30912be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattnerprivate:
310e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
311e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // NodeScope - almost a POD, but needs to call the constructors for the
312e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // scoped hash tables so that a new scope gets pushed on. These are RAII so
313e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // that the scope gets popped when the NodeScope is destroyed.
314e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  class NodeScope {
315e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani   public:
316e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    NodeScope(ScopedHTType *availableValues,
317e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani              LoadHTType *availableLoads,
318e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani              CallHTType *availableCalls) :
319e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani        Scope(*availableValues),
320e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani        LoadScope(*availableLoads),
321e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani        CallScope(*availableCalls) {}
322e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
323e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani   private:
32486a1c32e67b23c5e9e42dff9eb86e99ba15bb42fCraig Topper    NodeScope(const NodeScope&) LLVM_DELETED_FUNCTION;
32586a1c32e67b23c5e9e42dff9eb86e99ba15bb42fCraig Topper    void operator=(const NodeScope&) LLVM_DELETED_FUNCTION;
326e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
327e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    ScopedHTType::ScopeTy Scope;
328e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    LoadHTType::ScopeTy LoadScope;
329e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    CallHTType::ScopeTy CallScope;
330e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  };
331e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
332e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // StackNode - contains all the needed information to create a stack for
333e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // doing a depth first tranversal of the tree. This includes scopes for
334e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // values, loads, and calls as well as the generation. There is a child
335e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // iterator so that the children do not need to be store spearately.
336e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  class StackNode {
337e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani   public:
338e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    StackNode(ScopedHTType *availableValues,
339e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani              LoadHTType *availableLoads,
340e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani              CallHTType *availableCalls,
341e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani              unsigned cg, DomTreeNode *n,
342e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani              DomTreeNode::iterator child, DomTreeNode::iterator end) :
343e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani        CurrentGeneration(cg), ChildGeneration(cg), Node(n),
344e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani        ChildIter(child), EndIter(end),
345e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani        Scopes(availableValues, availableLoads, availableCalls),
346e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani        Processed(false) {}
347e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
348e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    // Accessors.
349e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    unsigned currentGeneration() { return CurrentGeneration; }
350e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    unsigned childGeneration() { return ChildGeneration; }
351e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    void childGeneration(unsigned generation) { ChildGeneration = generation; }
352e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    DomTreeNode *node() { return Node; }
353e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    DomTreeNode::iterator childIter() { return ChildIter; }
354e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    DomTreeNode *nextChild() {
355e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      DomTreeNode *child = *ChildIter;
356e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      ++ChildIter;
357e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      return child;
358e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    }
359e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    DomTreeNode::iterator end() { return EndIter; }
360e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    bool isProcessed() { return Processed; }
361e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    void process() { Processed = true; }
362e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
363e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani   private:
36486a1c32e67b23c5e9e42dff9eb86e99ba15bb42fCraig Topper    StackNode(const StackNode&) LLVM_DELETED_FUNCTION;
36586a1c32e67b23c5e9e42dff9eb86e99ba15bb42fCraig Topper    void operator=(const StackNode&) LLVM_DELETED_FUNCTION;
366e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
367e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    // Members.
368e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    unsigned CurrentGeneration;
369e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    unsigned ChildGeneration;
370e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    DomTreeNode *Node;
371e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    DomTreeNode::iterator ChildIter;
372e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    DomTreeNode::iterator EndIter;
373e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    NodeScope Scopes;
374e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    bool Processed;
375e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  };
376e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
377cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  bool processNode(DomTreeNode *Node);
378a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
37912be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner  // This transformation requires dominator postdominator info
38036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  void getAnalysisUsage(AnalysisUsage &AU) const override {
38136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    AU.addRequired<DominatorTreeWrapperPass>();
382618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier    AU.addRequired<TargetLibraryInfo>();
38312be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner    AU.setPreservesCFG();
38412be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner  }
38512be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner};
38612be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner}
38712be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner
38812be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattnerchar EarlyCSE::ID = 0;
38912be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner
39012be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner// createEarlyCSEPass - The public interface to this file.
39112be936cc912b1ff4d1c73c7f2c805a3462da1abChris LattnerFunctionPass *llvm::createEarlyCSEPass() {
39212be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner  return new EarlyCSE();
39312be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner}
39412be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner
39512be936cc912b1ff4d1c73c7f2c805a3462da1abChris LattnerINITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
39636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
397618c1dbd293d15ee19f61b1156ab8086ad28311aChad RosierINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
39812be936cc912b1ff4d1c73c7f2c805a3462da1abChris LattnerINITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
39912be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner
400cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattnerbool EarlyCSE::processNode(DomTreeNode *Node) {
401cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  BasicBlock *BB = Node->getBlock();
402a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
4038e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  // If this block has a single predecessor, then the predecessor is the parent
4048e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  // of the domtree node and all of the live out memory values are still current
4058e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  // in this block.  If this block has multiple predecessors, then they could
4068e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  // have invalidated the live-out memory values of our parent value.  For now,
4078e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  // just be conservative and invalidate memory if this block has multiple
4088e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  // predecessors.
409dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  if (!BB->getSinglePredecessor())
4108e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    ++CurrentGeneration;
411a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
41275637154c38da0243c51f4338137a78849808e50Chris Lattner  /// LastStore - Keep track of the last non-volatile store that we saw... for
41375637154c38da0243c51f4338137a78849808e50Chris Lattner  /// as long as there in no instruction that reads memory.  If we see a store
41475637154c38da0243c51f4338137a78849808e50Chris Lattner  /// to the same location, we delete the dead store.  This zaps trivial dead
41575637154c38da0243c51f4338137a78849808e50Chris Lattner  /// stores which can occur in bitfield code among other things.
416dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  StoreInst *LastStore = nullptr;
417a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
418cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  bool Changed = false;
419cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
420cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  // See if any instructions in the block can be eliminated.  If so, do it.  If
421cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  // not, add them to AvailableValues.
422cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
423cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    Instruction *Inst = I++;
424a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
425cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    // Dead instructions should just be removed.
4268e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer    if (isInstructionTriviallyDead(Inst, TLI)) {
42791139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner      DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
428cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      Inst->eraseFromParent();
429cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      Changed = true;
43091139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner      ++NumSimplify;
431cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      continue;
432cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    }
433a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
434cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    // If the instruction can be simplified (e.g. X+0 = X) then replace it with
435cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    // its simpler value.
43636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    if (Value *V = SimplifyInstruction(Inst, DL, TLI, DT)) {
43791139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner      DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
438cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      Inst->replaceAllUsesWith(V);
439cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      Inst->eraseFromParent();
440cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      Changed = true;
44191139ccd995149dd0d5e4ab3604d9239e1f90a54Chris Lattner      ++NumSimplify;
442cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      continue;
443cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    }
444a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
4458e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    // If this is a simple instruction that we can value number, process it.
4468e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    if (SimpleValue::canHandle(Inst)) {
4478e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner      // See if the instruction has an available value.  If so, use it.
448a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner      if (Value *V = AvailableValues->lookup(Inst)) {
4498e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
4508e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        Inst->replaceAllUsesWith(V);
4518e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        Inst->eraseFromParent();
4528e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        Changed = true;
4538e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        ++NumCSE;
4548e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        continue;
4558e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner      }
456a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
4578e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner      // Otherwise, just remember that this value is available.
458a60a8b0eb773eabb3ad83e610e737efda525a0daChris Lattner      AvailableValues->insert(Inst, Inst);
459cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      continue;
4608e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    }
461a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
46285db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    // If this is a non-volatile load, process it.
46385db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
46485db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      // Ignore volatile loads.
4652bc3d52b9ab422ee9f7e42a1a4e3b818e623a5f7Eli Friedman      if (!LI->isSimple()) {
466dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines        LastStore = nullptr;
46775637154c38da0243c51f4338137a78849808e50Chris Lattner        continue;
46875637154c38da0243c51f4338137a78849808e50Chris Lattner      }
469a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
47085db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      // If we have an available version of this load, and if it is the right
4718e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner      // generation, replace this instruction.
47285db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      std::pair<Value*, unsigned> InVal =
47385db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        AvailableLoads->lookup(Inst->getOperand(0));
474dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines      if (InVal.first != nullptr && InVal.second == CurrentGeneration) {
47585db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst << "  to: "
47685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner              << *InVal.first << '\n');
47785db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
47885db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        Inst->eraseFromParent();
47985db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        Changed = true;
48085db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        ++NumCSELoad;
48185db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        continue;
48285db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      }
483a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
48485db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      // Otherwise, remember that we have this instruction.
48585db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      AvailableLoads->insert(Inst->getOperand(0),
48685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner                          std::pair<Value*, unsigned>(Inst, CurrentGeneration));
487dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines      LastStore = nullptr;
48885db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      continue;
48985db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    }
490a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
49175637154c38da0243c51f4338137a78849808e50Chris Lattner    // If this instruction may read from memory, forget LastStore.
49275637154c38da0243c51f4338137a78849808e50Chris Lattner    if (Inst->mayReadFromMemory())
493dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines      LastStore = nullptr;
494a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
49585db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    // If this is a read-only call, process it.
49685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner    if (CallValue::canHandle(Inst)) {
49785db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      // If we have an available version of this call, and if it is the right
49885db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      // generation, replace this instruction.
49985db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      std::pair<Value*, unsigned> InVal = AvailableCalls->lookup(Inst);
500dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines      if (InVal.first != nullptr && InVal.second == CurrentGeneration) {
50185db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst << "  to: "
5028e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner                     << *InVal.first << '\n');
5038e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
5048e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        Inst->eraseFromParent();
5058e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        Changed = true;
50685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner        ++NumCSECall;
5078e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner        continue;
5088e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner      }
509a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
5108e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner      // Otherwise, remember that we have this instruction.
51185db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner      AvailableCalls->insert(Inst,
5128e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner                         std::pair<Value*, unsigned>(Inst, CurrentGeneration));
513cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner      continue;
514cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner    }
515a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
5168e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    // Okay, this isn't something we can CSE at all.  Check to see if it is
5178e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    // something that could modify memory.  If so, our available memory values
5188e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner    // cannot be used so bump the generation count.
519ef87fc2e0a19c3da55c596244e71e2ad03ae4b43Chris Lattner    if (Inst->mayWriteToMemory()) {
5208e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner      ++CurrentGeneration;
521a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
522ef87fc2e0a19c3da55c596244e71e2ad03ae4b43Chris Lattner      if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
52375637154c38da0243c51f4338137a78849808e50Chris Lattner        // We do a trivial form of DSE if there are two stores to the same
52475637154c38da0243c51f4338137a78849808e50Chris Lattner        // location with no intervening loads.  Delete the earlier store.
52575637154c38da0243c51f4338137a78849808e50Chris Lattner        if (LastStore &&
52675637154c38da0243c51f4338137a78849808e50Chris Lattner            LastStore->getPointerOperand() == SI->getPointerOperand()) {
52775637154c38da0243c51f4338137a78849808e50Chris Lattner          DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore << "  due to: "
528a12ba39a1d4d22c8c2d348f1397d52be58391177Chris Lattner                       << *Inst << '\n');
52975637154c38da0243c51f4338137a78849808e50Chris Lattner          LastStore->eraseFromParent();
53075637154c38da0243c51f4338137a78849808e50Chris Lattner          Changed = true;
53175637154c38da0243c51f4338137a78849808e50Chris Lattner          ++NumDSE;
532dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines          LastStore = nullptr;
53375637154c38da0243c51f4338137a78849808e50Chris Lattner          continue;
53475637154c38da0243c51f4338137a78849808e50Chris Lattner        }
535a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
53675637154c38da0243c51f4338137a78849808e50Chris Lattner        // Okay, we just invalidated anything we knew about loaded values.  Try
53775637154c38da0243c51f4338137a78849808e50Chris Lattner        // to salvage *something* by remembering that the stored value is a live
53875637154c38da0243c51f4338137a78849808e50Chris Lattner        // version of the pointer.  It is safe to forward from volatile stores
53975637154c38da0243c51f4338137a78849808e50Chris Lattner        // to non-volatile loads, so we don't have to check for volatility of
54075637154c38da0243c51f4338137a78849808e50Chris Lattner        // the store.
541ef87fc2e0a19c3da55c596244e71e2ad03ae4b43Chris Lattner        AvailableLoads->insert(SI->getPointerOperand(),
542ef87fc2e0a19c3da55c596244e71e2ad03ae4b43Chris Lattner         std::pair<Value*, unsigned>(SI->getValueOperand(), CurrentGeneration));
543a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
54475637154c38da0243c51f4338137a78849808e50Chris Lattner        // Remember that this was the last store we saw for DSE.
5452bc3d52b9ab422ee9f7e42a1a4e3b818e623a5f7Eli Friedman        if (SI->isSimple())
54675637154c38da0243c51f4338137a78849808e50Chris Lattner          LastStore = SI;
547ef87fc2e0a19c3da55c596244e71e2ad03ae4b43Chris Lattner      }
548ef87fc2e0a19c3da55c596244e71e2ad03ae4b43Chris Lattner    }
549cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  }
550e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
551cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  return Changed;
552cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner}
553cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
554cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner
55512be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattnerbool EarlyCSE::runOnFunction(Function &F) {
55636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  if (skipOptnoneFunction(F))
55736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    return false;
558e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
55936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  std::vector<StackNode *> nodesToProcess;
56036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines
56136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
562dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  DL = DLP ? &DLP->getDataLayout() : nullptr;
563618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier  TLI = &getAnalysis<TargetLibraryInfo>();
56436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
565a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
56685db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  // Tables that the pass uses when walking the domtree.
56782dcd5edd22f017b74ebe98acc07b3a7191e7ff1Chris Lattner  ScopedHTType AVTable;
568cc9eab26b3867fa4a835deb518a6a606882e8f49Chris Lattner  AvailableValues = &AVTable;
56985db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  LoadHTType LoadTable;
57085db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  AvailableLoads = &LoadTable;
57185db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  CallHTType CallTable;
57285db61066a370f5d6e2d3c667eb5fa02493593c7Chris Lattner  AvailableCalls = &CallTable;
573a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem
5748e7f0d70c7dd3864126c746378a7b928d57f971fChris Lattner  CurrentGeneration = 0;
575e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  bool Changed = false;
576e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
577e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // Process the root node.
57836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  nodesToProcess.push_back(
579e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
580e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani                    CurrentGeneration, DT->getRootNode(),
581e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani                    DT->getRootNode()->begin(),
582e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani                    DT->getRootNode()->end()));
583e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
584e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // Save the current generation.
585e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  unsigned LiveOutGeneration = CurrentGeneration;
586e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
587e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // Process the stack.
588e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  while (!nodesToProcess.empty()) {
589e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    // Grab the first item off the stack. Set the current generation, remove
590e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    // the node from the stack, and process it.
59136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    StackNode *NodeToProcess = nodesToProcess.back();
592e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
593e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    // Initialize class members.
594e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    CurrentGeneration = NodeToProcess->currentGeneration();
595e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
596e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    // Check if the node needs to be processed.
597e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    if (!NodeToProcess->isProcessed()) {
598e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      // Process the node.
599e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      Changed |= processNode(NodeToProcess->node());
600e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      NodeToProcess->childGeneration(CurrentGeneration);
601e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      NodeToProcess->process();
602e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
603e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      // Push the next child onto the stack.
604e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      DomTreeNode *child = NodeToProcess->nextChild();
60536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines      nodesToProcess.push_back(
606e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani          new StackNode(AvailableValues,
607e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani                        AvailableLoads,
608e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani                        AvailableCalls,
609e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani                        NodeToProcess->childGeneration(), child,
610e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani                        child->begin(), child->end()));
611e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    } else {
612e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      // It has been processed, and there are no more children to process,
613e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      // so delete it and pop it off the stack.
614e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani      delete NodeToProcess;
61536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines      nodesToProcess.pop_back();
616e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani    }
617e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  } // while (!nodes...)
618e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
619e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  // Reset the current generation.
620e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  CurrentGeneration = LiveOutGeneration;
621e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani
622e0c7cfa7236341110ec20a17d5291a64f5f6b7dfLenny Maiorani  return Changed;
62312be936cc912b1ff4d1c73c7f2c805a3462da1abChris Lattner}
624