diff options
Diffstat (limited to 'lib/Transforms/Scalar/GVN.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/GVN.cpp | 1285 |
1 files changed, 554 insertions, 731 deletions
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index a028b8c444bae..a35a1062cbcd8 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -15,7 +15,7 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Hashing.h" @@ -44,7 +44,6 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/PatternMatch.h" -#include "llvm/Support/Allocator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -53,6 +52,7 @@ #include "llvm/Transforms/Utils/SSAUpdater.h" #include <vector> using namespace llvm; +using namespace llvm::gvn; using namespace PatternMatch; #define DEBUG_TYPE "gvn" @@ -74,106 +74,167 @@ static cl::opt<uint32_t> MaxRecurseDepth("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, cl::desc("Max recurse depth (default = 1000)")); -//===----------------------------------------------------------------------===// -// ValueTable Class -//===----------------------------------------------------------------------===// - -/// This class holds the mapping between values and value numbers. It is used -/// as an efficient mechanism to determine the expression-wise equivalence of -/// two values. -namespace { - struct Expression { - uint32_t opcode; - Type *type; - SmallVector<uint32_t, 4> varargs; +struct llvm::GVN::Expression { + uint32_t opcode; + Type *type; + SmallVector<uint32_t, 4> varargs; - Expression(uint32_t o = ~2U) : opcode(o) { } + Expression(uint32_t o = ~2U) : opcode(o) {} - bool operator==(const Expression &other) const { - if (opcode != other.opcode) - return false; - if (opcode == ~0U || opcode == ~1U) - return true; - if (type != other.type) - return false; - if (varargs != other.varargs) - return false; + bool operator==(const Expression &other) const { + if (opcode != other.opcode) + return false; + if (opcode == ~0U || opcode == ~1U) return true; - } - - friend hash_code hash_value(const Expression &Value) { - return hash_combine(Value.opcode, Value.type, - hash_combine_range(Value.varargs.begin(), - Value.varargs.end())); - } - }; + if (type != other.type) + return false; + if (varargs != other.varargs) + return false; + return true; + } - class ValueTable { - DenseMap<Value*, uint32_t> valueNumbering; - DenseMap<Expression, uint32_t> expressionNumbering; - AliasAnalysis *AA; - MemoryDependenceAnalysis *MD; - DominatorTree *DT; - - uint32_t nextValueNumber; - - Expression create_expression(Instruction* I); - Expression create_cmp_expression(unsigned Opcode, - CmpInst::Predicate Predicate, - Value *LHS, Value *RHS); - Expression create_extractvalue_expression(ExtractValueInst* EI); - uint32_t lookup_or_add_call(CallInst* C); - public: - ValueTable() : nextValueNumber(1) { } - uint32_t lookup_or_add(Value *V); - uint32_t lookup(Value *V) const; - uint32_t lookup_or_add_cmp(unsigned Opcode, CmpInst::Predicate Pred, - Value *LHS, Value *RHS); - bool exists(Value *V) const; - void add(Value *V, uint32_t num); - void clear(); - void erase(Value *v); - void setAliasAnalysis(AliasAnalysis* A) { AA = A; } - AliasAnalysis *getAliasAnalysis() const { return AA; } - void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } - void setDomTree(DominatorTree* D) { DT = D; } - uint32_t getNextUnusedValueNumber() { return nextValueNumber; } - void verifyRemoved(const Value *) const; - }; -} + friend hash_code hash_value(const Expression &Value) { + return hash_combine( + Value.opcode, Value.type, + hash_combine_range(Value.varargs.begin(), Value.varargs.end())); + } +}; namespace llvm { -template <> struct DenseMapInfo<Expression> { - static inline Expression getEmptyKey() { - return ~0U; - } +template <> struct DenseMapInfo<GVN::Expression> { + static inline GVN::Expression getEmptyKey() { return ~0U; } - static inline Expression getTombstoneKey() { - return ~1U; - } + static inline GVN::Expression getTombstoneKey() { return ~1U; } - static unsigned getHashValue(const Expression e) { + static unsigned getHashValue(const GVN::Expression &e) { using llvm::hash_value; return static_cast<unsigned>(hash_value(e)); } - static bool isEqual(const Expression &LHS, const Expression &RHS) { + static bool isEqual(const GVN::Expression &LHS, const GVN::Expression &RHS) { return LHS == RHS; } }; +} // End llvm namespace. + +/// Represents a particular available value that we know how to materialize. +/// Materialization of an AvailableValue never fails. An AvailableValue is +/// implicitly associated with a rematerialization point which is the +/// location of the instruction from which it was formed. +struct llvm::gvn::AvailableValue { + enum ValType { + SimpleVal, // A simple offsetted value that is accessed. + LoadVal, // A value produced by a load. + MemIntrin, // A memory intrinsic which is loaded from. + UndefVal // A UndefValue representing a value from dead block (which + // is not yet physically removed from the CFG). + }; -} + /// V - The value that is live out of the block. + PointerIntPair<Value *, 2, ValType> Val; + + /// Offset - The byte offset in Val that is interesting for the load query. + unsigned Offset; + + static AvailableValue get(Value *V, unsigned Offset = 0) { + AvailableValue Res; + Res.Val.setPointer(V); + Res.Val.setInt(SimpleVal); + Res.Offset = Offset; + return Res; + } + + static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) { + AvailableValue Res; + Res.Val.setPointer(MI); + Res.Val.setInt(MemIntrin); + Res.Offset = Offset; + return Res; + } + + static AvailableValue getLoad(LoadInst *LI, unsigned Offset = 0) { + AvailableValue Res; + Res.Val.setPointer(LI); + Res.Val.setInt(LoadVal); + Res.Offset = Offset; + return Res; + } + + static AvailableValue getUndef() { + AvailableValue Res; + Res.Val.setPointer(nullptr); + Res.Val.setInt(UndefVal); + Res.Offset = 0; + return Res; + } + + bool isSimpleValue() const { return Val.getInt() == SimpleVal; } + bool isCoercedLoadValue() const { return Val.getInt() == LoadVal; } + bool isMemIntrinValue() const { return Val.getInt() == MemIntrin; } + bool isUndefValue() const { return Val.getInt() == UndefVal; } + + Value *getSimpleValue() const { + assert(isSimpleValue() && "Wrong accessor"); + return Val.getPointer(); + } + + LoadInst *getCoercedLoadValue() const { + assert(isCoercedLoadValue() && "Wrong accessor"); + return cast<LoadInst>(Val.getPointer()); + } + + MemIntrinsic *getMemIntrinValue() const { + assert(isMemIntrinValue() && "Wrong accessor"); + return cast<MemIntrinsic>(Val.getPointer()); + } + + /// Emit code at the specified insertion point to adjust the value defined + /// here to the specified type. This handles various coercion cases. + Value *MaterializeAdjustedValue(LoadInst *LI, Instruction *InsertPt, + GVN &gvn) const; +}; + +/// Represents an AvailableValue which can be rematerialized at the end of +/// the associated BasicBlock. +struct llvm::gvn::AvailableValueInBlock { + /// BB - The basic block in question. + BasicBlock *BB; + + /// AV - The actual available value + AvailableValue AV; + + static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV) { + AvailableValueInBlock Res; + Res.BB = BB; + Res.AV = std::move(AV); + return Res; + } + + static AvailableValueInBlock get(BasicBlock *BB, Value *V, + unsigned Offset = 0) { + return get(BB, AvailableValue::get(V, Offset)); + } + static AvailableValueInBlock getUndef(BasicBlock *BB) { + return get(BB, AvailableValue::getUndef()); + } + + /// Emit code at the end of this block to adjust the value defined here to + /// the specified type. This handles various coercion cases. + Value *MaterializeAdjustedValue(LoadInst *LI, GVN &gvn) const { + return AV.MaterializeAdjustedValue(LI, BB->getTerminator(), gvn); + } +}; //===----------------------------------------------------------------------===// // ValueTable Internal Functions //===----------------------------------------------------------------------===// -Expression ValueTable::create_expression(Instruction *I) { +GVN::Expression GVN::ValueTable::createExpr(Instruction *I) { Expression e; e.type = I->getType(); e.opcode = I->getOpcode(); for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) - e.varargs.push_back(lookup_or_add(*OI)); + e.varargs.push_back(lookupOrAdd(*OI)); if (I->isCommutative()) { // Ensure that commutative instructions that only differ by a permutation // of their operands get the same value number by sorting the operand value @@ -201,15 +262,15 @@ Expression ValueTable::create_expression(Instruction *I) { return e; } -Expression ValueTable::create_cmp_expression(unsigned Opcode, - CmpInst::Predicate Predicate, - Value *LHS, Value *RHS) { +GVN::Expression GVN::ValueTable::createCmpExpr(unsigned Opcode, + CmpInst::Predicate Predicate, + Value *LHS, Value *RHS) { assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && "Not a comparison!"); Expression e; e.type = CmpInst::makeCmpResultType(LHS->getType()); - e.varargs.push_back(lookup_or_add(LHS)); - e.varargs.push_back(lookup_or_add(RHS)); + e.varargs.push_back(lookupOrAdd(LHS)); + e.varargs.push_back(lookupOrAdd(RHS)); // Sort the operand value numbers so x<y and y>x get the same value number. if (e.varargs[0] > e.varargs[1]) { @@ -220,7 +281,7 @@ Expression ValueTable::create_cmp_expression(unsigned Opcode, return e; } -Expression ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { +GVN::Expression GVN::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) { assert(EI && "Not an ExtractValueInst?"); Expression e; e.type = EI->getType(); @@ -252,8 +313,8 @@ Expression ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { // Intrinsic recognized. Grab its args to finish building the expression. assert(I->getNumArgOperands() == 2 && "Expect two args for recognised intrinsics."); - e.varargs.push_back(lookup_or_add(I->getArgOperand(0))); - e.varargs.push_back(lookup_or_add(I->getArgOperand(1))); + e.varargs.push_back(lookupOrAdd(I->getArgOperand(0))); + e.varargs.push_back(lookupOrAdd(I->getArgOperand(1))); return e; } } @@ -263,7 +324,7 @@ Expression ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { e.opcode = EI->getOpcode(); for (Instruction::op_iterator OI = EI->op_begin(), OE = EI->op_end(); OI != OE; ++OI) - e.varargs.push_back(lookup_or_add(*OI)); + e.varargs.push_back(lookupOrAdd(*OI)); for (ExtractValueInst::idx_iterator II = EI->idx_begin(), IE = EI->idx_end(); II != IE; ++II) @@ -276,20 +337,32 @@ Expression ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { // ValueTable External Functions //===----------------------------------------------------------------------===// +GVN::ValueTable::ValueTable() : nextValueNumber(1) {} +GVN::ValueTable::ValueTable(const ValueTable &Arg) + : valueNumbering(Arg.valueNumbering), + expressionNumbering(Arg.expressionNumbering), AA(Arg.AA), MD(Arg.MD), + DT(Arg.DT), nextValueNumber(Arg.nextValueNumber) {} +GVN::ValueTable::ValueTable(ValueTable &&Arg) + : valueNumbering(std::move(Arg.valueNumbering)), + expressionNumbering(std::move(Arg.expressionNumbering)), + AA(std::move(Arg.AA)), MD(std::move(Arg.MD)), DT(std::move(Arg.DT)), + nextValueNumber(std::move(Arg.nextValueNumber)) {} +GVN::ValueTable::~ValueTable() {} + /// add - Insert a value into the table with a specified value number. -void ValueTable::add(Value *V, uint32_t num) { +void GVN::ValueTable::add(Value *V, uint32_t num) { valueNumbering.insert(std::make_pair(V, num)); } -uint32_t ValueTable::lookup_or_add_call(CallInst *C) { +uint32_t GVN::ValueTable::lookupOrAddCall(CallInst *C) { if (AA->doesNotAccessMemory(C)) { - Expression exp = create_expression(C); + Expression exp = createExpr(C); uint32_t &e = expressionNumbering[exp]; if (!e) e = nextValueNumber++; valueNumbering[C] = e; return e; } else if (AA->onlyReadsMemory(C)) { - Expression exp = create_expression(C); + Expression exp = createExpr(C); uint32_t &e = expressionNumbering[exp]; if (!e) { e = nextValueNumber++; @@ -318,21 +391,21 @@ uint32_t ValueTable::lookup_or_add_call(CallInst *C) { } for (unsigned i = 0, e = C->getNumArgOperands(); i < e; ++i) { - uint32_t c_vn = lookup_or_add(C->getArgOperand(i)); - uint32_t cd_vn = lookup_or_add(local_cdep->getArgOperand(i)); + uint32_t c_vn = lookupOrAdd(C->getArgOperand(i)); + uint32_t cd_vn = lookupOrAdd(local_cdep->getArgOperand(i)); if (c_vn != cd_vn) { valueNumbering[C] = nextValueNumber; return nextValueNumber++; } } - uint32_t v = lookup_or_add(local_cdep); + uint32_t v = lookupOrAdd(local_cdep); valueNumbering[C] = v; return v; } // Non-local case. - const MemoryDependenceAnalysis::NonLocalDepInfo &deps = + const MemoryDependenceResults::NonLocalDepInfo &deps = MD->getNonLocalCallDependency(CallSite(C)); // FIXME: Move the checking logic to MemDep! CallInst* cdep = nullptr; @@ -372,15 +445,15 @@ uint32_t ValueTable::lookup_or_add_call(CallInst *C) { return nextValueNumber++; } for (unsigned i = 0, e = C->getNumArgOperands(); i < e; ++i) { - uint32_t c_vn = lookup_or_add(C->getArgOperand(i)); - uint32_t cd_vn = lookup_or_add(cdep->getArgOperand(i)); + uint32_t c_vn = lookupOrAdd(C->getArgOperand(i)); + uint32_t cd_vn = lookupOrAdd(cdep->getArgOperand(i)); if (c_vn != cd_vn) { valueNumbering[C] = nextValueNumber; return nextValueNumber++; } } - uint32_t v = lookup_or_add(cdep); + uint32_t v = lookupOrAdd(cdep); valueNumbering[C] = v; return v; @@ -391,11 +464,11 @@ uint32_t ValueTable::lookup_or_add_call(CallInst *C) { } /// Returns true if a value number exists for the specified value. -bool ValueTable::exists(Value *V) const { return valueNumbering.count(V) != 0; } +bool GVN::ValueTable::exists(Value *V) const { return valueNumbering.count(V) != 0; } /// lookup_or_add - Returns the value number for the specified value, assigning /// it a new number if it did not have one before. -uint32_t ValueTable::lookup_or_add(Value *V) { +uint32_t GVN::ValueTable::lookupOrAdd(Value *V) { DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); if (VI != valueNumbering.end()) return VI->second; @@ -409,7 +482,7 @@ uint32_t ValueTable::lookup_or_add(Value *V) { Expression exp; switch (I->getOpcode()) { case Instruction::Call: - return lookup_or_add_call(cast<CallInst>(I)); + return lookupOrAddCall(cast<CallInst>(I)); case Instruction::Add: case Instruction::FAdd: case Instruction::Sub: @@ -448,10 +521,10 @@ uint32_t ValueTable::lookup_or_add(Value *V) { case Instruction::ShuffleVector: case Instruction::InsertValue: case Instruction::GetElementPtr: - exp = create_expression(I); + exp = createExpr(I); break; case Instruction::ExtractValue: - exp = create_extractvalue_expression(cast<ExtractValueInst>(I)); + exp = createExtractvalueExpr(cast<ExtractValueInst>(I)); break; default: valueNumbering[V] = nextValueNumber; @@ -466,7 +539,7 @@ uint32_t ValueTable::lookup_or_add(Value *V) { /// Returns the value number of the specified value. Fails if /// the value has not yet been numbered. -uint32_t ValueTable::lookup(Value *V) const { +uint32_t GVN::ValueTable::lookup(Value *V) const { DenseMap<Value*, uint32_t>::const_iterator VI = valueNumbering.find(V); assert(VI != valueNumbering.end() && "Value not numbered?"); return VI->second; @@ -476,30 +549,30 @@ uint32_t ValueTable::lookup(Value *V) const { /// assigning it a new number if it did not have one before. Useful when /// we deduced the result of a comparison, but don't immediately have an /// instruction realizing that comparison to hand. -uint32_t ValueTable::lookup_or_add_cmp(unsigned Opcode, - CmpInst::Predicate Predicate, - Value *LHS, Value *RHS) { - Expression exp = create_cmp_expression(Opcode, Predicate, LHS, RHS); +uint32_t GVN::ValueTable::lookupOrAddCmp(unsigned Opcode, + CmpInst::Predicate Predicate, + Value *LHS, Value *RHS) { + Expression exp = createCmpExpr(Opcode, Predicate, LHS, RHS); uint32_t& e = expressionNumbering[exp]; if (!e) e = nextValueNumber++; return e; } /// Remove all entries from the ValueTable. -void ValueTable::clear() { +void GVN::ValueTable::clear() { valueNumbering.clear(); expressionNumbering.clear(); nextValueNumber = 1; } /// Remove a value from the value numbering. -void ValueTable::erase(Value *V) { +void GVN::ValueTable::erase(Value *V) { valueNumbering.erase(V); } /// verifyRemoved - Verify that the value is removed from all internal data /// structures. -void ValueTable::verifyRemoved(const Value *V) const { +void GVN::ValueTable::verifyRemoved(const Value *V) const { for (DenseMap<Value*, uint32_t>::const_iterator I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) { assert(I->first != V && "Inst still occurs in value numbering map!"); @@ -510,251 +583,26 @@ void ValueTable::verifyRemoved(const Value *V) const { // GVN Pass //===----------------------------------------------------------------------===// -namespace { - class GVN; - struct AvailableValueInBlock { - /// BB - The basic block in question. - BasicBlock *BB; - enum ValType { - SimpleVal, // A simple offsetted value that is accessed. - LoadVal, // A value produced by a load. - MemIntrin, // A memory intrinsic which is loaded from. - UndefVal // A UndefValue representing a value from dead block (which - // is not yet physically removed from the CFG). - }; - - /// V - The value that is live out of the block. - PointerIntPair<Value *, 2, ValType> Val; - - /// Offset - The byte offset in Val that is interesting for the load query. - unsigned Offset; - - static AvailableValueInBlock get(BasicBlock *BB, Value *V, - unsigned Offset = 0) { - AvailableValueInBlock Res; - Res.BB = BB; - Res.Val.setPointer(V); - Res.Val.setInt(SimpleVal); - Res.Offset = Offset; - return Res; - } - - static AvailableValueInBlock getMI(BasicBlock *BB, MemIntrinsic *MI, - unsigned Offset = 0) { - AvailableValueInBlock Res; - Res.BB = BB; - Res.Val.setPointer(MI); - Res.Val.setInt(MemIntrin); - Res.Offset = Offset; - return Res; - } - - static AvailableValueInBlock getLoad(BasicBlock *BB, LoadInst *LI, - unsigned Offset = 0) { - AvailableValueInBlock Res; - Res.BB = BB; - Res.Val.setPointer(LI); - Res.Val.setInt(LoadVal); - Res.Offset = Offset; - return Res; - } - - static AvailableValueInBlock getUndef(BasicBlock *BB) { - AvailableValueInBlock Res; - Res.BB = BB; - Res.Val.setPointer(nullptr); - Res.Val.setInt(UndefVal); - Res.Offset = 0; - return Res; - } - - bool isSimpleValue() const { return Val.getInt() == SimpleVal; } - bool isCoercedLoadValue() const { return Val.getInt() == LoadVal; } - bool isMemIntrinValue() const { return Val.getInt() == MemIntrin; } - bool isUndefValue() const { return Val.getInt() == UndefVal; } - - Value *getSimpleValue() const { - assert(isSimpleValue() && "Wrong accessor"); - return Val.getPointer(); - } - - LoadInst *getCoercedLoadValue() const { - assert(isCoercedLoadValue() && "Wrong accessor"); - return cast<LoadInst>(Val.getPointer()); - } - - MemIntrinsic *getMemIntrinValue() const { - assert(isMemIntrinValue() && "Wrong accessor"); - return cast<MemIntrinsic>(Val.getPointer()); - } - - /// Emit code into this block to adjust the value defined here to the - /// specified type. This handles various coercion cases. - Value *MaterializeAdjustedValue(LoadInst *LI, GVN &gvn) const; - }; - - class GVN : public FunctionPass { - bool NoLoads; - MemoryDependenceAnalysis *MD; - DominatorTree *DT; - const TargetLibraryInfo *TLI; - AssumptionCache *AC; - SetVector<BasicBlock *> DeadBlocks; - - ValueTable VN; - - /// A mapping from value numbers to lists of Value*'s that - /// have that value number. Use findLeader to query it. - struct LeaderTableEntry { - Value *Val; - const BasicBlock *BB; - LeaderTableEntry *Next; - }; - DenseMap<uint32_t, LeaderTableEntry> LeaderTable; - BumpPtrAllocator TableAllocator; - - // Block-local map of equivalent values to their leader, does not - // propagate to any successors. Entries added mid-block are applied - // to the remaining instructions in the block. - SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap; - SmallVector<Instruction*, 8> InstrsToErase; - - typedef SmallVector<NonLocalDepResult, 64> LoadDepVect; - typedef SmallVector<AvailableValueInBlock, 64> AvailValInBlkVect; - typedef SmallVector<BasicBlock*, 64> UnavailBlkVect; - - public: - static char ID; // Pass identification, replacement for typeid - explicit GVN(bool noloads = false) - : FunctionPass(ID), NoLoads(noloads), MD(nullptr) { - initializeGVNPass(*PassRegistry::getPassRegistry()); - } - - bool runOnFunction(Function &F) override; - - /// This removes the specified instruction from - /// our various maps and marks it for deletion. - void markInstructionForDeletion(Instruction *I) { - VN.erase(I); - InstrsToErase.push_back(I); - } - - DominatorTree &getDominatorTree() const { return *DT; } - AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } - MemoryDependenceAnalysis &getMemDep() const { return *MD; } - private: - /// Push a new Value to the LeaderTable onto the list for its value number. - void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { - LeaderTableEntry &Curr = LeaderTable[N]; - if (!Curr.Val) { - Curr.Val = V; - Curr.BB = BB; - return; - } - - LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>(); - Node->Val = V; - Node->BB = BB; - Node->Next = Curr.Next; - Curr.Next = Node; - } - - /// Scan the list of values corresponding to a given - /// value number, and remove the given instruction if encountered. - void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { - LeaderTableEntry* Prev = nullptr; - LeaderTableEntry* Curr = &LeaderTable[N]; - - while (Curr && (Curr->Val != I || Curr->BB != BB)) { - Prev = Curr; - Curr = Curr->Next; - } - - if (!Curr) - return; - - if (Prev) { - Prev->Next = Curr->Next; - } else { - if (!Curr->Next) { - Curr->Val = nullptr; - Curr->BB = nullptr; - } else { - LeaderTableEntry* Next = Curr->Next; - Curr->Val = Next->Val; - Curr->BB = Next->BB; - Curr->Next = Next->Next; - } - } - } - - // List of critical edges to be split between iterations. - SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit; - - // This transformation requires dominator postdominator info - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired<AssumptionCacheTracker>(); - AU.addRequired<DominatorTreeWrapperPass>(); - AU.addRequired<TargetLibraryInfoWrapperPass>(); - if (!NoLoads) - AU.addRequired<MemoryDependenceAnalysis>(); - AU.addRequired<AAResultsWrapperPass>(); - - AU.addPreserved<DominatorTreeWrapperPass>(); - AU.addPreserved<GlobalsAAWrapperPass>(); - } - - - // Helper functions of redundant load elimination - bool processLoad(LoadInst *L); - bool processNonLocalLoad(LoadInst *L); - bool processAssumeIntrinsic(IntrinsicInst *II); - void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, - AvailValInBlkVect &ValuesPerBlock, - UnavailBlkVect &UnavailableBlocks); - bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, - UnavailBlkVect &UnavailableBlocks); - - // Other helper routines - bool processInstruction(Instruction *I); - bool processBlock(BasicBlock *BB); - void dump(DenseMap<uint32_t, Value*> &d); - bool iterateOnFunction(Function &F); - bool performPRE(Function &F); - bool performScalarPRE(Instruction *I); - bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, - unsigned int ValNo); - Value *findLeader(const BasicBlock *BB, uint32_t num); - void cleanupGlobalSets(); - void verifyRemoved(const Instruction *I) const; - bool splitCriticalEdges(); - BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); - bool replaceOperandsWithConsts(Instruction *I) const; - bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, - bool DominatesByEdge); - bool processFoldableCondBr(BranchInst *BI); - void addDeadBlock(BasicBlock *BB); - void assignValNumForDeadCode(); - }; - - char GVN::ID = 0; -} - -// The public interface to this file... -FunctionPass *llvm::createGVNPass(bool NoLoads) { - return new GVN(NoLoads); +PreservedAnalyses GVN::run(Function &F, AnalysisManager<Function> &AM) { + // FIXME: The order of evaluation of these 'getResult' calls is very + // significant! Re-ordering these variables will cause GVN when run alone to + // be less effective! We should fix memdep and basic-aa to not exhibit this + // behavior, but until then don't change the order here. + auto &AC = AM.getResult<AssumptionAnalysis>(F); + auto &DT = AM.getResult<DominatorTreeAnalysis>(F); + auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); + auto &AA = AM.getResult<AAManager>(F); + auto &MemDep = AM.getResult<MemoryDependenceAnalysis>(F); + bool Changed = runImpl(F, AC, DT, TLI, AA, &MemDep); + if (!Changed) + return PreservedAnalyses::all(); + PreservedAnalyses PA; + PA.preserve<DominatorTreeAnalysis>(); + PA.preserve<GlobalsAA>(); + return PA; } -INITIALIZE_PASS_BEGIN(GVN, "gvn", "Global Value Numbering", false, false) -INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) -INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) -INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) -INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) -INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) -INITIALIZE_PASS_END(GVN, "gvn", "Global Value Numbering", false, false) - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void GVN::dump(DenseMap<uint32_t, Value*>& d) { errs() << "{\n"; for (DenseMap<uint32_t, Value*>::iterator I = d.begin(), @@ -764,7 +612,6 @@ void GVN::dump(DenseMap<uint32_t, Value*>& d) { } errs() << "}\n"; } -#endif /// Return true if we can prove that the value /// we're analyzing is fully available in the specified block. As we go, keep @@ -875,38 +722,45 @@ static bool CanCoerceMustAliasedValueToLoad(Value *StoredVal, static Value *CoerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy, IRBuilder<> &IRB, const DataLayout &DL) { - if (!CanCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL)) - return nullptr; + assert(CanCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL) && + "precondition violation - materialization can't fail"); + + if (auto *CExpr = dyn_cast<ConstantExpr>(StoredVal)) + StoredVal = ConstantFoldConstantExpression(CExpr, DL); // If this is already the right type, just return it. Type *StoredValTy = StoredVal->getType(); - uint64_t StoreSize = DL.getTypeSizeInBits(StoredValTy); - uint64_t LoadSize = DL.getTypeSizeInBits(LoadedTy); + uint64_t StoredValSize = DL.getTypeSizeInBits(StoredValTy); + uint64_t LoadedValSize = DL.getTypeSizeInBits(LoadedTy); // If the store and reload are the same size, we can always reuse it. - if (StoreSize == LoadSize) { + if (StoredValSize == LoadedValSize) { // Pointer to Pointer -> use bitcast. if (StoredValTy->getScalarType()->isPointerTy() && - LoadedTy->getScalarType()->isPointerTy()) - return IRB.CreateBitCast(StoredVal, LoadedTy); + LoadedTy->getScalarType()->isPointerTy()) { + StoredVal = IRB.CreateBitCast(StoredVal, LoadedTy); + } else { + // Convert source pointers to integers, which can be bitcast. + if (StoredValTy->getScalarType()->isPointerTy()) { + StoredValTy = DL.getIntPtrType(StoredValTy); + StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy); + } - // Convert source pointers to integers, which can be bitcast. - if (StoredValTy->getScalarType()->isPointerTy()) { - StoredValTy = DL.getIntPtrType(StoredValTy); - StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy); - } + Type *TypeToCastTo = LoadedTy; + if (TypeToCastTo->getScalarType()->isPointerTy()) + TypeToCastTo = DL.getIntPtrType(TypeToCastTo); - Type *TypeToCastTo = LoadedTy; - if (TypeToCastTo->getScalarType()->isPointerTy()) - TypeToCastTo = DL.getIntPtrType(TypeToCastTo); + if (StoredValTy != TypeToCastTo) + StoredVal = IRB.CreateBitCast(StoredVal, TypeToCastTo); - if (StoredValTy != TypeToCastTo) - StoredVal = IRB.CreateBitCast(StoredVal, TypeToCastTo); + // Cast to pointer if the load needs a pointer type. + if (LoadedTy->getScalarType()->isPointerTy()) + StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy); + } - // Cast to pointer if the load needs a pointer type. - if (LoadedTy->getScalarType()->isPointerTy()) - StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy); + if (auto *CExpr = dyn_cast<ConstantExpr>(StoredVal)) + StoredVal = ConstantFoldConstantExpression(CExpr, DL); return StoredVal; } @@ -914,7 +768,8 @@ static Value *CoerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy, // If the loaded value is smaller than the available value, then we can // extract out a piece from it. If the available value is too small, then we // can't do anything. - assert(StoreSize >= LoadSize && "CanCoerceMustAliasedValueToLoad fail"); + assert(StoredValSize >= LoadedValSize && + "CanCoerceMustAliasedValueToLoad fail"); // Convert source pointers to integers, which can be manipulated. if (StoredValTy->getScalarType()->isPointerTy()) { @@ -924,29 +779,35 @@ static Value *CoerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy, // Convert vectors and fp to integer, which can be manipulated. if (!StoredValTy->isIntegerTy()) { - StoredValTy = IntegerType::get(StoredValTy->getContext(), StoreSize); + StoredValTy = IntegerType::get(StoredValTy->getContext(), StoredValSize); StoredVal = IRB.CreateBitCast(StoredVal, StoredValTy); } // If this is a big-endian system, we need to shift the value down to the low // bits so that a truncate will work. if (DL.isBigEndian()) { - StoredVal = IRB.CreateLShr(StoredVal, StoreSize - LoadSize, "tmp"); + uint64_t ShiftAmt = DL.getTypeStoreSizeInBits(StoredValTy) - + DL.getTypeStoreSizeInBits(LoadedTy); + StoredVal = IRB.CreateLShr(StoredVal, ShiftAmt, "tmp"); } // Truncate the integer to the right size now. - Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadSize); + Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadedValSize); StoredVal = IRB.CreateTrunc(StoredVal, NewIntTy, "trunc"); - if (LoadedTy == NewIntTy) - return StoredVal; + if (LoadedTy != NewIntTy) { + // If the result is a pointer, inttoptr. + if (LoadedTy->getScalarType()->isPointerTy()) + StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy, "inttoptr"); + else + // Otherwise, bitcast. + StoredVal = IRB.CreateBitCast(StoredVal, LoadedTy, "bitcast"); + } - // If the result is a pointer, inttoptr. - if (LoadedTy->getScalarType()->isPointerTy()) - return IRB.CreateIntToPtr(StoredVal, LoadedTy, "inttoptr"); + if (auto *CExpr = dyn_cast<ConstantExpr>(StoredVal)) + StoredVal = ConstantFoldConstantExpression(CExpr, DL); - // Otherwise, bitcast. - return IRB.CreateBitCast(StoredVal, LoadedTy, "bitcast"); + return StoredVal; } /// This function is called when we have a @@ -1067,10 +928,15 @@ static int AnalyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, GetPointerBaseWithConstantOffset(LoadPtr, LoadOffs, DL); unsigned LoadSize = DL.getTypeStoreSize(LoadTy); - unsigned Size = MemoryDependenceAnalysis::getLoadLoadClobberFullWidthSize( + unsigned Size = MemoryDependenceResults::getLoadLoadClobberFullWidthSize( LoadBase, LoadOffs, LoadSize, DepLI); if (Size == 0) return -1; + // Check non-obvious conditions enforced by MDA which we rely on for being + // able to materialize this potentially available value + assert(DepLI->isSimple() && "Cannot widen volatile/atomic load!"); + assert(DepLI->getType()->isIntegerTy() && "Can't widen non-integer load"); + return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, Size*8, DL); } @@ -1117,7 +983,7 @@ static int AnalyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src, OffsetCst); Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS)); - if (ConstantFoldLoadFromConstPtr(Src, DL)) + if (ConstantFoldLoadFromConstPtr(Src, LoadTy, DL)) return Offset; return -1; } @@ -1173,9 +1039,9 @@ static Value *GetLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, const DataLayout &DL = SrcVal->getModule()->getDataLayout(); // If Offset+LoadTy exceeds the size of SrcVal, then we must be wanting to // widen SrcVal out to a larger load. - unsigned SrcValSize = DL.getTypeStoreSize(SrcVal->getType()); + unsigned SrcValStoreSize = DL.getTypeStoreSize(SrcVal->getType()); unsigned LoadSize = DL.getTypeStoreSize(LoadTy); - if (Offset+LoadSize > SrcValSize) { + if (Offset+LoadSize > SrcValStoreSize) { assert(SrcVal->isSimple() && "Cannot widen volatile/atomic load!"); assert(SrcVal->getType()->isIntegerTy() && "Can't widen non-integer load"); // If we have a load/load clobber an DepLI can be widened to cover this @@ -1207,8 +1073,7 @@ static Value *GetLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, // system, we need to shift down to get the relevant bits. Value *RV = NewLoad; if (DL.isBigEndian()) - RV = Builder.CreateLShr(RV, - NewLoadSize*8-SrcVal->getType()->getPrimitiveSizeInBits()); + RV = Builder.CreateLShr(RV, (NewLoadSize - SrcValStoreSize) * 8); RV = Builder.CreateTrunc(RV, SrcVal->getType()); SrcVal->replaceAllUsesWith(RV); @@ -1279,7 +1144,7 @@ static Value *GetMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src, OffsetCst); Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS)); - return ConstantFoldLoadFromConstPtr(Src, DL); + return ConstantFoldLoadFromConstPtr(Src, LoadTy, DL); } @@ -1294,7 +1159,8 @@ static Value *ConstructSSAForLoadSet(LoadInst *LI, if (ValuesPerBlock.size() == 1 && gvn.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB, LI->getParent())) { - assert(!ValuesPerBlock[0].isUndefValue() && "Dead BB dominate this block"); + assert(!ValuesPerBlock[0].AV.isUndefValue() && + "Dead BB dominate this block"); return ValuesPerBlock[0].MaterializeAdjustedValue(LI, gvn); } @@ -1316,15 +1182,16 @@ static Value *ConstructSSAForLoadSet(LoadInst *LI, return SSAUpdate.GetValueInMiddleOfBlock(LI->getParent()); } -Value *AvailableValueInBlock::MaterializeAdjustedValue(LoadInst *LI, - GVN &gvn) const { +Value *AvailableValue::MaterializeAdjustedValue(LoadInst *LI, + Instruction *InsertPt, + GVN &gvn) const { Value *Res; Type *LoadTy = LI->getType(); const DataLayout &DL = LI->getModule()->getDataLayout(); if (isSimpleValue()) { Res = getSimpleValue(); if (Res->getType() != LoadTy) { - Res = GetStoreValueForLoad(Res, Offset, LoadTy, BB->getTerminator(), DL); + Res = GetStoreValueForLoad(Res, Offset, LoadTy, InsertPt, DL); DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset << " " << *getSimpleValue() << '\n' @@ -1335,16 +1202,15 @@ Value *AvailableValueInBlock::MaterializeAdjustedValue(LoadInst *LI, if (Load->getType() == LoadTy && Offset == 0) { Res = Load; } else { - Res = GetLoadValueForLoad(Load, Offset, LoadTy, BB->getTerminator(), - gvn); - + Res = GetLoadValueForLoad(Load, Offset, LoadTy, InsertPt, gvn); + DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset << " " << *getCoercedLoadValue() << '\n' << *Res << '\n' << "\n\n\n"); } } else if (isMemIntrinValue()) { Res = GetMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy, - BB->getTerminator(), DL); + InsertPt, DL); DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset << " " << *getMemIntrinValue() << '\n' << *Res << '\n' << "\n\n\n"); @@ -1353,6 +1219,7 @@ Value *AvailableValueInBlock::MaterializeAdjustedValue(LoadInst *LI, DEBUG(dbgs() << "GVN COERCED NONLOCAL Undef:\n";); return UndefValue::get(LoadTy); } + assert(Res && "failed to materialize?"); return Res; } @@ -1362,7 +1229,134 @@ static bool isLifetimeStart(const Instruction *Inst) { return false; } -void GVN::AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, +bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, + Value *Address, AvailableValue &Res) { + + assert((DepInfo.isDef() || DepInfo.isClobber()) && + "expected a local dependence"); + assert(LI->isUnordered() && "rules below are incorrect for ordered access"); + + const DataLayout &DL = LI->getModule()->getDataLayout(); + + if (DepInfo.isClobber()) { + // If the dependence is to a store that writes to a superset of the bits + // read by the load, we can extract the bits we need for the load from the + // stored value. + if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) { + // Can't forward from non-atomic to atomic without violating memory model. + if (Address && LI->isAtomic() <= DepSI->isAtomic()) { + int Offset = + AnalyzeLoadFromClobberingStore(LI->getType(), Address, DepSI); + if (Offset != -1) { + Res = AvailableValue::get(DepSI->getValueOperand(), Offset); + return true; + } + } + } + + // Check to see if we have something like this: + // load i32* P + // load i8* (P+1) + // if we have this, replace the later with an extraction from the former. + if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInfo.getInst())) { + // If this is a clobber and L is the first instruction in its block, then + // we have the first instruction in the entry block. + // Can't forward from non-atomic to atomic without violating memory model. + if (DepLI != LI && Address && LI->isAtomic() <= DepLI->isAtomic()) { + int Offset = + AnalyzeLoadFromClobberingLoad(LI->getType(), Address, DepLI, DL); + + if (Offset != -1) { + Res = AvailableValue::getLoad(DepLI, Offset); + return true; + } + } + } + + // If the clobbering value is a memset/memcpy/memmove, see if we can + // forward a value on from it. + if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInfo.getInst())) { + if (Address && !LI->isAtomic()) { + int Offset = AnalyzeLoadFromClobberingMemInst(LI->getType(), Address, + DepMI, DL); + if (Offset != -1) { + Res = AvailableValue::getMI(DepMI, Offset); + return true; + } + } + } + // Nothing known about this clobber, have to be conservative + DEBUG( + // fast print dep, using operator<< on instruction is too slow. + dbgs() << "GVN: load "; + LI->printAsOperand(dbgs()); + Instruction *I = DepInfo.getInst(); + dbgs() << " is clobbered by " << *I << '\n'; + ); + return false; + } + assert(DepInfo.isDef() && "follows from above"); + + Instruction *DepInst = DepInfo.getInst(); + + // Loading the allocation -> undef. + if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI) || + // Loading immediately after lifetime begin -> undef. + isLifetimeStart(DepInst)) { + Res = AvailableValue::get(UndefValue::get(LI->getType())); + return true; + } + + // Loading from calloc (which zero initializes memory) -> zero + if (isCallocLikeFn(DepInst, TLI)) { + Res = AvailableValue::get(Constant::getNullValue(LI->getType())); + return true; + } + + if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) { + // Reject loads and stores that are to the same address but are of + // different types if we have to. If the stored value is larger or equal to + // the loaded value, we can reuse it. + if (S->getValueOperand()->getType() != LI->getType() && + !CanCoerceMustAliasedValueToLoad(S->getValueOperand(), + LI->getType(), DL)) + return false; + + // Can't forward from non-atomic to atomic without violating memory model. + if (S->isAtomic() < LI->isAtomic()) + return false; + + Res = AvailableValue::get(S->getValueOperand()); + return true; + } + + if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) { + // If the types mismatch and we can't handle it, reject reuse of the load. + // If the stored value is larger or equal to the loaded value, we can reuse + // it. + if (LD->getType() != LI->getType() && + !CanCoerceMustAliasedValueToLoad(LD, LI->getType(), DL)) + return false; + + // Can't forward from non-atomic to atomic without violating memory model. + if (LD->isAtomic() < LI->isAtomic()) + return false; + + Res = AvailableValue::getLoad(LD); + return true; + } + + // Unknown def - must be conservative + DEBUG( + // fast print dep, using operator<< on instruction is too slow. + dbgs() << "GVN: load "; + LI->printAsOperand(dbgs()); + dbgs() << " has unknown def " << *DepInst << '\n'; + ); + return false; +} + +void GVN::AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks) { @@ -1371,7 +1365,6 @@ void GVN::AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, // dependencies that produce an unknown value for the load (such as a call // that could potentially clobber the load). unsigned NumDeps = Deps.size(); - const DataLayout &DL = LI->getModule()->getDataLayout(); for (unsigned i = 0, e = NumDeps; i != e; ++i) { BasicBlock *DepBB = Deps[i].getBB(); MemDepResult DepInfo = Deps[i].getResult(); @@ -1388,122 +1381,28 @@ void GVN::AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, continue; } - if (DepInfo.isClobber()) { - // The address being loaded in this non-local block may not be the same as - // the pointer operand of the load if PHI translation occurs. Make sure - // to consider the right address. - Value *Address = Deps[i].getAddress(); - - // If the dependence is to a store that writes to a superset of the bits - // read by the load, we can extract the bits we need for the load from the - // stored value. - if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) { - if (Address) { - int Offset = - AnalyzeLoadFromClobberingStore(LI->getType(), Address, DepSI); - if (Offset != -1) { - ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB, - DepSI->getValueOperand(), - Offset)); - continue; - } - } - } - - // Check to see if we have something like this: - // load i32* P - // load i8* (P+1) - // if we have this, replace the later with an extraction from the former. - if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInfo.getInst())) { - // If this is a clobber and L is the first instruction in its block, then - // we have the first instruction in the entry block. - if (DepLI != LI && Address) { - int Offset = - AnalyzeLoadFromClobberingLoad(LI->getType(), Address, DepLI, DL); - - if (Offset != -1) { - ValuesPerBlock.push_back(AvailableValueInBlock::getLoad(DepBB,DepLI, - Offset)); - continue; - } - } - } - - // If the clobbering value is a memset/memcpy/memmove, see if we can - // forward a value on from it. - if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInfo.getInst())) { - if (Address) { - int Offset = AnalyzeLoadFromClobberingMemInst(LI->getType(), Address, - DepMI, DL); - if (Offset != -1) { - ValuesPerBlock.push_back(AvailableValueInBlock::getMI(DepBB, DepMI, - Offset)); - continue; - } - } - } - - UnavailableBlocks.push_back(DepBB); - continue; - } - - // DepInfo.isDef() here - - Instruction *DepInst = DepInfo.getInst(); - - // Loading the allocation -> undef. - if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI) || - // Loading immediately after lifetime begin -> undef. - isLifetimeStart(DepInst)) { - ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB, - UndefValue::get(LI->getType()))); - continue; - } - - // Loading from calloc (which zero initializes memory) -> zero - if (isCallocLikeFn(DepInst, TLI)) { - ValuesPerBlock.push_back(AvailableValueInBlock::get( - DepBB, Constant::getNullValue(LI->getType()))); - continue; - } - - if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) { - // Reject loads and stores that are to the same address but are of - // different types if we have to. - if (S->getValueOperand()->getType() != LI->getType()) { - // If the stored value is larger or equal to the loaded value, we can - // reuse it. - if (!CanCoerceMustAliasedValueToLoad(S->getValueOperand(), - LI->getType(), DL)) { - UnavailableBlocks.push_back(DepBB); - continue; - } - } + // The address being loaded in this non-local block may not be the same as + // the pointer operand of the load if PHI translation occurs. Make sure + // to consider the right address. + Value *Address = Deps[i].getAddress(); + AvailableValue AV; + if (AnalyzeLoadAvailability(LI, DepInfo, Address, AV)) { + // subtlety: because we know this was a non-local dependency, we know + // it's safe to materialize anywhere between the instruction within + // DepInfo and the end of it's block. ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB, - S->getValueOperand())); - continue; - } - - if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) { - // If the types mismatch and we can't handle it, reject reuse of the load. - if (LD->getType() != LI->getType()) { - // If the stored value is larger or equal to the loaded value, we can - // reuse it. - if (!CanCoerceMustAliasedValueToLoad(LD, LI->getType(), DL)) { - UnavailableBlocks.push_back(DepBB); - continue; - } - } - ValuesPerBlock.push_back(AvailableValueInBlock::getLoad(DepBB, LD)); - continue; + std::move(AV))); + } else { + UnavailableBlocks.push_back(DepBB); } - - UnavailableBlocks.push_back(DepBB); } + + assert(NumDeps == ValuesPerBlock.size() + UnavailableBlocks.size() && + "post condition violation"); } -bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, +bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks) { // Okay, we have *some* definitions of the value. This means that the value // is available in some of our (transitive) predecessors. Lets think about @@ -1661,16 +1560,17 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, // parent's availability map. However, in doing so, we risk getting into // ordering issues. If a block hasn't been processed yet, we would be // marking a value as AVAIL-IN, which isn't what we intend. - VN.lookup_or_add(I); + VN.lookupOrAdd(I); } for (const auto &PredLoad : PredLoads) { BasicBlock *UnavailablePred = PredLoad.first; Value *LoadPtr = PredLoad.second; - Instruction *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false, - LI->getAlignment(), - UnavailablePred->getTerminator()); + auto *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", + LI->isVolatile(), LI->getAlignment(), + LI->getOrdering(), LI->getSynchScope(), + UnavailablePred->getTerminator()); // Transfer the old load's AA tags to the new load. AAMDNodes Tags; @@ -1682,6 +1582,8 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD); if (auto *InvGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group)) NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD); + if (auto *RangeMD = LI->getMetadata(LLVMContext::MD_range)) + NewLoad->setMetadata(LLVMContext::MD_range, RangeMD); // Transfer DebugLoc. NewLoad->setDebugLoc(LI->getDebugLoc()); @@ -1846,30 +1748,29 @@ bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) { } static void patchReplacementInstruction(Instruction *I, Value *Repl) { + auto *ReplInst = dyn_cast<Instruction>(Repl); + if (!ReplInst) + return; + // Patch the replacement so that it is not more restrictive than the value // being replaced. - BinaryOperator *Op = dyn_cast<BinaryOperator>(I); - BinaryOperator *ReplOp = dyn_cast<BinaryOperator>(Repl); - if (Op && ReplOp) - ReplOp->andIRFlags(Op); - - if (Instruction *ReplInst = dyn_cast<Instruction>(Repl)) { - // FIXME: If both the original and replacement value are part of the - // same control-flow region (meaning that the execution of one - // guarantees the execution of the other), then we can combine the - // noalias scopes here and do better than the general conservative - // answer used in combineMetadata(). - - // In general, GVN unifies expressions over different control-flow - // regions, and so we need a conservative combination of the noalias - // scopes. - static const unsigned KnownIDs[] = { - LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, - LLVMContext::MD_noalias, LLVMContext::MD_range, - LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load, - LLVMContext::MD_invariant_group}; - combineMetadata(ReplInst, I, KnownIDs); - } + ReplInst->andIRFlags(I); + + // FIXME: If both the original and replacement value are part of the + // same control-flow region (meaning that the execution of one + // guarantees the execution of the other), then we can combine the + // noalias scopes here and do better than the general conservative + // answer used in combineMetadata(). + + // In general, GVN unifies expressions over different control-flow + // regions, and so we need a conservative combination of the noalias + // scopes. + static const unsigned KnownIDs[] = { + LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, + LLVMContext::MD_noalias, LLVMContext::MD_range, + LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load, + LLVMContext::MD_invariant_group}; + combineMetadata(ReplInst, I, KnownIDs); } static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) { @@ -1883,7 +1784,8 @@ bool GVN::processLoad(LoadInst *L) { if (!MD) return false; - if (!L->isSimple()) + // This code hasn't been audited for ordered or volatile memory access + if (!L->isUnordered()) return false; if (L->use_empty()) { @@ -1893,84 +1795,14 @@ bool GVN::processLoad(LoadInst *L) { // ... to a pointer that has been loaded from before... MemDepResult Dep = MD->getDependency(L); - const DataLayout &DL = L->getModule()->getDataLayout(); - - // If we have a clobber and target data is around, see if this is a clobber - // that we can fix up through code synthesis. - if (Dep.isClobber()) { - // Check to see if we have something like this: - // store i32 123, i32* %P - // %A = bitcast i32* %P to i8* - // %B = gep i8* %A, i32 1 - // %C = load i8* %B - // - // We could do that by recognizing if the clobber instructions are obviously - // a common base + constant offset, and if the previous store (or memset) - // completely covers this load. This sort of thing can happen in bitfield - // access code. - Value *AvailVal = nullptr; - if (StoreInst *DepSI = dyn_cast<StoreInst>(Dep.getInst())) { - int Offset = AnalyzeLoadFromClobberingStore( - L->getType(), L->getPointerOperand(), DepSI); - if (Offset != -1) - AvailVal = GetStoreValueForLoad(DepSI->getValueOperand(), Offset, - L->getType(), L, DL); - } - - // Check to see if we have something like this: - // load i32* P - // load i8* (P+1) - // if we have this, replace the later with an extraction from the former. - if (LoadInst *DepLI = dyn_cast<LoadInst>(Dep.getInst())) { - // If this is a clobber and L is the first instruction in its block, then - // we have the first instruction in the entry block. - if (DepLI == L) - return false; - - int Offset = AnalyzeLoadFromClobberingLoad( - L->getType(), L->getPointerOperand(), DepLI, DL); - if (Offset != -1) - AvailVal = GetLoadValueForLoad(DepLI, Offset, L->getType(), L, *this); - } - - // If the clobbering value is a memset/memcpy/memmove, see if we can forward - // a value on from it. - if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(Dep.getInst())) { - int Offset = AnalyzeLoadFromClobberingMemInst( - L->getType(), L->getPointerOperand(), DepMI, DL); - if (Offset != -1) - AvailVal = GetMemInstValueForLoad(DepMI, Offset, L->getType(), L, DL); - } - - if (AvailVal) { - DEBUG(dbgs() << "GVN COERCED INST:\n" << *Dep.getInst() << '\n' - << *AvailVal << '\n' << *L << "\n\n\n"); - - // Replace the load! - L->replaceAllUsesWith(AvailVal); - if (AvailVal->getType()->getScalarType()->isPointerTy()) - MD->invalidateCachedPointerInfo(AvailVal); - markInstructionForDeletion(L); - ++NumGVNLoad; - return true; - } - - // If the value isn't available, don't do anything! - DEBUG( - // fast print dep, using operator<< on instruction is too slow. - dbgs() << "GVN: load "; - L->printAsOperand(dbgs()); - Instruction *I = Dep.getInst(); - dbgs() << " is clobbered by " << *I << '\n'; - ); - return false; - } // If it is defined in another block, try harder. if (Dep.isNonLocal()) return processNonLocalLoad(L); - if (!Dep.isDef()) { + // Only handle the local case below + if (!Dep.isDef() && !Dep.isClobber()) { + // This might be a NonFuncLocal or an Unknown DEBUG( // fast print dep, using operator<< on instruction is too slow. dbgs() << "GVN: load "; @@ -1980,86 +1812,18 @@ bool GVN::processLoad(LoadInst *L) { return false; } - Instruction *DepInst = Dep.getInst(); - if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) { - Value *StoredVal = DepSI->getValueOperand(); - - // The store and load are to a must-aliased pointer, but they may not - // actually have the same type. See if we know how to reuse the stored - // value (depending on its type). - if (StoredVal->getType() != L->getType()) { - IRBuilder<> Builder(L); - StoredVal = - CoerceAvailableValueToLoadType(StoredVal, L->getType(), Builder, DL); - if (!StoredVal) - return false; - - DEBUG(dbgs() << "GVN COERCED STORE:\n" << *DepSI << '\n' << *StoredVal - << '\n' << *L << "\n\n\n"); - } - - // Remove it! - L->replaceAllUsesWith(StoredVal); - if (StoredVal->getType()->getScalarType()->isPointerTy()) - MD->invalidateCachedPointerInfo(StoredVal); - markInstructionForDeletion(L); - ++NumGVNLoad; - return true; - } - - if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { - Value *AvailableVal = DepLI; - - // The loads are of a must-aliased pointer, but they may not actually have - // the same type. See if we know how to reuse the previously loaded value - // (depending on its type). - if (DepLI->getType() != L->getType()) { - IRBuilder<> Builder(L); - AvailableVal = - CoerceAvailableValueToLoadType(DepLI, L->getType(), Builder, DL); - if (!AvailableVal) - return false; - - DEBUG(dbgs() << "GVN COERCED LOAD:\n" << *DepLI << "\n" << *AvailableVal - << "\n" << *L << "\n\n\n"); - } - - // Remove it! - patchAndReplaceAllUsesWith(L, AvailableVal); - if (DepLI->getType()->getScalarType()->isPointerTy()) - MD->invalidateCachedPointerInfo(DepLI); - markInstructionForDeletion(L); - ++NumGVNLoad; - return true; - } - - // If this load really doesn't depend on anything, then we must be loading an - // undef value. This can happen when loading for a fresh allocation with no - // intervening stores, for example. - if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI)) { - L->replaceAllUsesWith(UndefValue::get(L->getType())); - markInstructionForDeletion(L); - ++NumGVNLoad; - return true; - } + AvailableValue AV; + if (AnalyzeLoadAvailability(L, Dep, L->getPointerOperand(), AV)) { + Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this); - // If this load occurs either right after a lifetime begin, - // then the loaded value is undefined. - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(DepInst)) { - if (II->getIntrinsicID() == Intrinsic::lifetime_start) { - L->replaceAllUsesWith(UndefValue::get(L->getType())); - markInstructionForDeletion(L); - ++NumGVNLoad; - return true; - } - } - - // If this load follows a calloc (which zero initializes memory), - // then the loaded value is zero - if (isCallocLikeFn(DepInst, TLI)) { - L->replaceAllUsesWith(Constant::getNullValue(L->getType())); + // Replace the load! + patchAndReplaceAllUsesWith(L, AvailableValue); markInstructionForDeletion(L); ++NumGVNLoad; + // Tell MDA to rexamine the reused pointer since we might have more + // information after forwarding it. + if (MD && AvailableValue->getType()->getScalarType()->isPointerTy()) + MD->invalidateCachedPointerInfo(AvailableValue); return true; } @@ -2105,9 +1869,8 @@ static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, // GVN runs all such loops have preheaders, which means that Dst will have // been changed to have only one predecessor, namely Src. const BasicBlock *Pred = E.getEnd()->getSinglePredecessor(); - const BasicBlock *Src = E.getStart(); - assert((!Pred || Pred == Src) && "No edge between these basic blocks!"); - (void)Src; + assert((!Pred || Pred == E.getStart()) && + "No edge between these basic blocks!"); return Pred != nullptr; } @@ -2133,7 +1896,8 @@ bool GVN::replaceOperandsWithConsts(Instruction *Instr) const { /// The given values are known to be equal in every block /// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with /// 'RHS' everywhere in the scope. Returns whether a change was made. -/// If DominatesByEdge is false, then it means that it is dominated by Root.End. +/// If DominatesByEdge is false, then it means that we will propagate the RHS +/// value starting from the end of Root.Start. bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, bool DominatesByEdge) { SmallVector<std::pair<Value*, Value*>, 4> Worklist; @@ -2141,7 +1905,7 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, bool Changed = false; // For speed, compute a conservative fast approximation to // DT->dominates(Root, Root.getEnd()); - bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT); + const bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT); while (!Worklist.empty()) { std::pair<Value*, Value*> Item = Worklist.pop_back_val(); @@ -2164,12 +1928,12 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, // right-hand side, ensure the longest lived term is on the right-hand side, // so the shortest lived term will be replaced by the longest lived. // This tends to expose more simplifications. - uint32_t LVN = VN.lookup_or_add(LHS); + uint32_t LVN = VN.lookupOrAdd(LHS); if ((isa<Argument>(LHS) && isa<Argument>(RHS)) || (isa<Instruction>(LHS) && isa<Instruction>(RHS))) { // Move the 'oldest' value to the right-hand side, using the value number // as a proxy for age. - uint32_t RVN = VN.lookup_or_add(RHS); + uint32_t RVN = VN.lookupOrAdd(RHS); if (LVN < RVN) { std::swap(LHS, RHS); LVN = RVN; @@ -2195,7 +1959,7 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, unsigned NumReplacements = DominatesByEdge ? replaceDominatedUsesWith(LHS, RHS, *DT, Root) - : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd()); + : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart()); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; @@ -2245,7 +2009,7 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, // Floating point -0.0 and 0.0 compare equal, so we can only // propagate values if we know that we have a constant and that // its value is non-zero. - + // FIXME: We should do this optimization if 'no signed zeros' is // applicable via an instruction-level fast-math-flag or some other // indicator that relaxed FP semantics are being used. @@ -2253,7 +2017,7 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, if (isa<ConstantFP>(Op1) && !cast<ConstantFP>(Op1)->isZero()) Worklist.push_back(std::make_pair(Op0, Op1)); } - + // If "A >= B" is known true, replace "A < B" with false everywhere. CmpInst::Predicate NotPred = Cmp->getInversePredicate(); Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse); @@ -2261,7 +2025,7 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, // out the value number that it would have and use that to find an // appropriate instruction (if any). uint32_t NextNum = VN.getNextUnusedValueNumber(); - uint32_t Num = VN.lookup_or_add_cmp(Cmp->getOpcode(), NotPred, Op0, Op1); + uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1); // If the number we were assigned was brand new then there is no point in // looking for an instruction realizing it: there cannot be one! if (Num < NextNum) { @@ -2271,7 +2035,7 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, DominatesByEdge ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root) : replaceDominatedUsesWith(NotCmp, NotVal, *DT, - Root.getEnd()); + Root.getStart()); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; } @@ -2303,12 +2067,21 @@ bool GVN::processInstruction(Instruction *I) { // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify. const DataLayout &DL = I->getModule()->getDataLayout(); if (Value *V = SimplifyInstruction(I, DL, TLI, DT, AC)) { - I->replaceAllUsesWith(V); - if (MD && V->getType()->getScalarType()->isPointerTy()) - MD->invalidateCachedPointerInfo(V); - markInstructionForDeletion(I); - ++NumGVNSimpl; - return true; + bool Changed = false; + if (!I->use_empty()) { + I->replaceAllUsesWith(V); + Changed = true; + } + if (isInstructionTriviallyDead(I, TLI)) { + markInstructionForDeletion(I); + Changed = true; + } + if (Changed) { + if (MD && V->getType()->getScalarType()->isPointerTy()) + MD->invalidateCachedPointerInfo(V); + ++NumGVNSimpl; + return true; + } } if (IntrinsicInst *IntrinsicI = dyn_cast<IntrinsicInst>(I)) @@ -2319,7 +2092,7 @@ bool GVN::processInstruction(Instruction *I) { if (processLoad(LI)) return true; - unsigned Num = VN.lookup_or_add(LI); + unsigned Num = VN.lookupOrAdd(LI); addToLeaderTable(Num, LI, LI->getParent()); return false; } @@ -2383,7 +2156,7 @@ bool GVN::processInstruction(Instruction *I) { return false; uint32_t NextNum = VN.getNextUnusedValueNumber(); - unsigned Num = VN.lookup_or_add(I); + unsigned Num = VN.lookupOrAdd(I); // Allocations are always uniquely numbered, so we can save time and memory // by fast failing them. @@ -2422,18 +2195,16 @@ bool GVN::processInstruction(Instruction *I) { } /// runOnFunction - This is the main transformation entry point for a function. -bool GVN::runOnFunction(Function& F) { - if (skipOptnoneFunction(F)) - return false; - - if (!NoLoads) - MD = &getAnalysis<MemoryDependenceAnalysis>(); - DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); - AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); - TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); - VN.setAliasAnalysis(&getAnalysis<AAResultsWrapperPass>().getAAResults()); - VN.setMemDep(MD); +bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, + const TargetLibraryInfo &RunTLI, AAResults &RunAA, + MemoryDependenceResults *RunMD) { + AC = &RunAC; + DT = &RunDT; VN.setDomTree(DT); + TLI = &RunTLI; + VN.setAliasAnalysis(&RunAA); + MD = RunMD; + VN.setMemDep(MD); bool Changed = false; bool ShouldContinue = true; @@ -2476,7 +2247,7 @@ bool GVN::runOnFunction(Function& F) { cleanupGlobalSets(); // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each - // iteration. + // iteration. DeadBlocks.clear(); return Changed; @@ -2576,8 +2347,6 @@ bool GVN::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, } bool GVN::performScalarPRE(Instruction *CurInst) { - SmallVector<std::pair<Value*, BasicBlock*>, 8> predMap; - if (isa<AllocaInst>(CurInst) || isa<TerminatorInst>(CurInst) || isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() || CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() || @@ -2608,8 +2377,8 @@ bool GVN::performScalarPRE(Instruction *CurInst) { unsigned NumWithout = 0; BasicBlock *PREPred = nullptr; BasicBlock *CurrentBlock = CurInst->getParent(); - predMap.clear(); + SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap; for (BasicBlock *P : predecessors(CurrentBlock)) { // We're not interested in PRE where the block is its // own predecessor, or in blocks with predecessors @@ -2702,7 +2471,7 @@ bool GVN::performScalarPRE(Instruction *CurInst) { DEBUG(verifyRemoved(CurInst)); CurInst->eraseFromParent(); ++NumGVNInstr; - + return true; } @@ -2825,7 +2594,7 @@ void GVN::addDeadBlock(BasicBlock *BB) { SmallVector<BasicBlock *, 8> Dom; DT->getDescendants(D, Dom); DeadBlocks.insert(Dom.begin(), Dom.end()); - + // Figure out the dominance-frontier(D). for (BasicBlock *B : Dom) { for (BasicBlock *S : successors(B)) { @@ -2883,13 +2652,13 @@ void GVN::addDeadBlock(BasicBlock *BB) { // If the given branch is recognized as a foldable branch (i.e. conditional // branch with constant condition), it will perform following analyses and // transformation. -// 1) If the dead out-coming edge is a critical-edge, split it. Let +// 1) If the dead out-coming edge is a critical-edge, split it. Let // R be the target of the dead out-coming edge. // 1) Identify the set of dead blocks implied by the branch's dead outcoming // edge. The result of this step will be {X| X is dominated by R} // 2) Identify those blocks which haves at least one dead predecessor. The // result of this step will be dominance-frontier(R). -// 3) Update the PHIs in DF(R) by replacing the operands corresponding to +// 3) Update the PHIs in DF(R) by replacing the operands corresponding to // dead blocks with "UndefVal" in an hope these PHIs will optimized away. // // Return true iff *NEW* dead code are found. @@ -2905,8 +2674,8 @@ bool GVN::processFoldableCondBr(BranchInst *BI) { if (!Cond) return false; - BasicBlock *DeadRoot = Cond->getZExtValue() ? - BI->getSuccessor(1) : BI->getSuccessor(0); + BasicBlock *DeadRoot = + Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0); if (DeadBlocks.count(DeadRoot)) return false; @@ -2924,8 +2693,62 @@ bool GVN::processFoldableCondBr(BranchInst *BI) { void GVN::assignValNumForDeadCode() { for (BasicBlock *BB : DeadBlocks) { for (Instruction &Inst : *BB) { - unsigned ValNum = VN.lookup_or_add(&Inst); + unsigned ValNum = VN.lookupOrAdd(&Inst); addToLeaderTable(ValNum, &Inst, BB); } } } + +class llvm::gvn::GVNLegacyPass : public FunctionPass { +public: + static char ID; // Pass identification, replacement for typeid + explicit GVNLegacyPass(bool NoLoads = false) + : FunctionPass(ID), NoLoads(NoLoads) { + initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override { + if (skipFunction(F)) + return false; + + return Impl.runImpl( + F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F), + getAnalysis<DominatorTreeWrapperPass>().getDomTree(), + getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(), + getAnalysis<AAResultsWrapperPass>().getAAResults(), + NoLoads ? nullptr + : &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<AssumptionCacheTracker>(); + AU.addRequired<DominatorTreeWrapperPass>(); + AU.addRequired<TargetLibraryInfoWrapperPass>(); + if (!NoLoads) + AU.addRequired<MemoryDependenceWrapperPass>(); + AU.addRequired<AAResultsWrapperPass>(); + + AU.addPreserved<DominatorTreeWrapperPass>(); + AU.addPreserved<GlobalsAAWrapperPass>(); + } + +private: + bool NoLoads; + GVN Impl; +}; + +char GVNLegacyPass::ID = 0; + +// The public interface to this file... +FunctionPass *llvm::createGVNPass(bool NoLoads) { + return new GVNLegacyPass(NoLoads); +} + +INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) +INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false) |