Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -138,7 +138,7 @@ void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&); void initializeGCMachineCodeAnalysisPass(PassRegistry&); void initializeGCModuleInfoPass(PassRegistry&); -void initializeGVNPass(PassRegistry&); +void initializeGVNLegacyPassPass(PassRegistry&); void initializeGlobalDCEPass(PassRegistry&); void initializeGlobalOptPass(PassRegistry&); void initializeGlobalsAAWrapperPassPass(PassRegistry&); Index: llvm/trunk/include/llvm/LinkAllPasses.h =================================================================== --- llvm/trunk/include/llvm/LinkAllPasses.h +++ llvm/trunk/include/llvm/LinkAllPasses.h @@ -42,6 +42,7 @@ #include "llvm/Transforms/Instrumentation.h" #include "llvm/Transforms/ObjCARC.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/Transforms/Utils/SymbolRewriter.h" #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" #include "llvm/Transforms/Vectorize.h" Index: llvm/trunk/include/llvm/Transforms/Scalar.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar.h +++ llvm/trunk/include/llvm/Transforms/Scalar.h @@ -335,13 +335,6 @@ //===----------------------------------------------------------------------===// // -// GVN - This pass performs global value numbering and redundant load -// elimination cotemporaneously. -// -FunctionPass *createGVNPass(bool NoLoads = false); - -//===----------------------------------------------------------------------===// -// // MemCpyOpt - This pass performs optimizations related to eliminating memcpy // calls and/or combining multiple stores into memset's. // Index: llvm/trunk/include/llvm/Transforms/Scalar/GVN.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar/GVN.h +++ llvm/trunk/include/llvm/Transforms/Scalar/GVN.h @@ -0,0 +1,232 @@ +//===- GVN.h - Eliminate redundant values and loads -------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file provides the interface for LLVM's Global Value Numbering pass +/// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc +/// PRE and dead load elimination. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_GVN_H +#define LLVM_TRANSFORMS_SCALAR_GVN_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by GVN. These +/// are implementation details and should not be used by clients. +namespace gvn LLVM_LIBRARY_VISIBILITY { +struct AvailableValue; +struct AvailableValueInBlock; +struct Expression; +class GVNLegacyPass; +} + +/// The core GVN pass object. +/// +/// FIXME: We should have a good summary of the GVN algorithm implemented by +/// this particular pass here. +class GVN : public PassBase { +public: + + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, AnalysisManager *AM); + + /// 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(); } + MemoryDependenceResults &getMemDep() const { return *MD; } + +private: + friend class gvn::GVNLegacyPass; + + /// 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. + class ValueTable { + DenseMap valueNumbering; + DenseMap expressionNumbering; + AliasAnalysis *AA; + MemoryDependenceResults *MD; + DominatorTree *DT; + + uint32_t nextValueNumber; + + gvn::Expression create_expression(Instruction *I); + gvn::Expression create_cmp_expression(unsigned Opcode, + CmpInst::Predicate Predicate, + Value *LHS, Value *RHS); + gvn::Expression create_extractvalue_expression(ExtractValueInst *EI); + uint32_t lookup_or_add_call(CallInst *C); + + public: + ValueTable(); + ValueTable(const ValueTable &Arg); + ValueTable(ValueTable &&Arg); + ~ValueTable(); + + 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(MemoryDependenceResults *M) { MD = M; } + void setDomTree(DominatorTree *D) { DT = D; } + uint32_t getNextUnusedValueNumber() { return nextValueNumber; } + void verifyRemoved(const Value *) const; + }; + + MemoryDependenceResults *MD; + DominatorTree *DT; + const TargetLibraryInfo *TLI; + AssumptionCache *AC; + SetVector 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 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 ReplaceWithConstMap; + SmallVector InstrsToErase; + + typedef SmallVector LoadDepVect; + typedef SmallVector AvailValInBlkVect; + typedef SmallVector UnavailBlkVect; + + bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, + const TargetLibraryInfo &RunTLI, AAResults &RunAA, + MemoryDependenceResults *RunMD); + + /// 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(); + 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, 4> toSplit; + + // Helper functions of redundant load elimination + bool processLoad(LoadInst *L); + bool processNonLocalLoad(LoadInst *L); + bool processAssumeIntrinsic(IntrinsicInst *II); + /// Given a local dependency (Def or Clobber) determine if a value is + /// available for the load. Returns true if an value is known to be + /// available and populates Res. Returns false otherwise. + bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, + Value *Address, gvn::AvailableValue &Res); + /// Given a list of non-local dependencies, determine if a value is + /// available for the load in each specified block. If it is, add it to + /// ValuesPerBlock. If not, add it to UnavailableBlocks. + 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 &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(); +}; + +/// Create a legacy GVN pass. This also allows parameterizing whether or not +/// loads are eliminated by the pass. +FunctionPass *createGVNPass(bool NoLoads = false); + +} + +#endif Index: llvm/trunk/lib/LTO/LTOCodeGenerator.cpp =================================================================== --- llvm/trunk/lib/LTO/LTOCodeGenerator.cpp +++ llvm/trunk/lib/LTO/LTOCodeGenerator.cpp @@ -111,7 +111,7 @@ initializeGlobalsAAWrapperPassPass(R); initializeLICMPass(R); initializeMergedLoadStoreMotionPass(R); - initializeGVNPass(R); + initializeGVNLegacyPassPass(R); initializeMemCpyOptPass(R); initializeDCEPass(R); initializeCFGSimplifyPassPass(R); Index: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -51,6 +51,7 @@ #include "llvm/Transforms/Scalar/ADCE.h" #include "llvm/Transforms/Scalar/EarlyCSE.h" #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/Transforms/Scalar/SROA.h" #include "llvm/Transforms/Scalar/SimplifyCFG.h" #include Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/lib/Passes/PassRegistry.def @@ -92,6 +92,7 @@ FUNCTION_PASS("invalidate", InvalidateAllAnalysesPass()) FUNCTION_PASS("no-op-function", NoOpFunctionPass()) FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass()) +FUNCTION_PASS("gvn", GVN()) FUNCTION_PASS("print", PrintFunctionPass(dbgs())) FUNCTION_PASS("print", AssumptionPrinterPass(dbgs())) FUNCTION_PASS("print", DominatorTreePrinterPass(dbgs())) Index: llvm/trunk/lib/Target/NVPTX/NVPTXTargetMachine.cpp =================================================================== --- llvm/trunk/lib/Target/NVPTX/NVPTXTargetMachine.cpp +++ llvm/trunk/lib/Target/NVPTX/NVPTXTargetMachine.cpp @@ -44,6 +44,7 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" using namespace llvm; Index: llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp +++ llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -34,6 +34,7 @@ #include "llvm/Transforms/IPO/FunctionAttrs.h" #include "llvm/Transforms/IPO/InferFunctionAttrs.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/Transforms/Vectorize.h" #include "llvm/Transforms/Instrumentation.h" Index: llvm/trunk/lib/Transforms/Scalar/GVN.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/GVN.cpp +++ llvm/trunk/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" @@ -53,6 +53,7 @@ #include "llvm/Transforms/Utils/SSAUpdater.h" #include using namespace llvm; +using namespace llvm::gvn; using namespace PatternMatch; #define DEBUG_TYPE "gvn" @@ -74,13 +75,7 @@ MaxRecurseDepth("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, cl::desc("Max recurse depth (default = 1000)")); -//===----------------------------------------------------------------------===// -// ValueTable Class -//===----------------------------------------------------------------------===// - -namespace { - -struct Expression { +struct llvm::gvn::Expression { uint32_t opcode; Type *type; SmallVector varargs; @@ -106,45 +101,6 @@ } }; -/// 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. -class ValueTable { - DenseMap valueNumbering; - DenseMap expressionNumbering; - AliasAnalysis *AA; - MemoryDependenceResults *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(MemoryDependenceResults *M) { MD = M; } - void setDomTree(DominatorTree *D) { DT = D; } - uint32_t getNextUnusedValueNumber() { return nextValueNumber; } - void verifyRemoved(const Value *) const; -}; - -} // End anonymous namespace. - namespace llvm { template <> struct DenseMapInfo { static inline Expression getEmptyKey() { return ~0U; } @@ -161,11 +117,119 @@ }; } // 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 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(Val.getPointer()); + } + + MemIntrinsic *getMemIntrinValue() const { + assert(isMemIntrinValue() && "Wrong accessor"); + return cast(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) { +Expression GVN::ValueTable::create_expression(Instruction *I) { Expression e; e.type = I->getType(); e.opcode = I->getOpcode(); @@ -199,7 +263,7 @@ return e; } -Expression ValueTable::create_cmp_expression(unsigned Opcode, +Expression GVN::ValueTable::create_cmp_expression(unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && @@ -218,7 +282,7 @@ return e; } -Expression ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { +Expression GVN::ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { assert(EI && "Not an ExtractValueInst?"); Expression e; e.type = EI->getType(); @@ -274,12 +338,24 @@ // 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::lookup_or_add_call(CallInst *C) { if (AA->doesNotAccessMemory(C)) { Expression exp = create_expression(C); uint32_t &e = expressionNumbering[exp]; @@ -389,11 +465,11 @@ } /// 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::lookup_or_add(Value *V) { DenseMap::iterator VI = valueNumbering.find(V); if (VI != valueNumbering.end()) return VI->second; @@ -464,7 +540,7 @@ /// 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::const_iterator VI = valueNumbering.find(V); assert(VI != valueNumbering.end() && "Value not numbered?"); return VI->second; @@ -474,7 +550,7 @@ /// 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, +uint32_t GVN::ValueTable::lookup_or_add_cmp(unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { Expression exp = create_cmp_expression(Opcode, Predicate, LHS, RHS); @@ -484,20 +560,20 @@ } /// 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::const_iterator I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) { assert(I->first != V && "Inst still occurs in value numbering map!"); @@ -508,287 +584,15 @@ // GVN Pass //===----------------------------------------------------------------------===// -namespace { -class GVN; - -/// 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 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 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(Val.getPointer()); - } - - MemIntrinsic *getMemIntrinValue() const { - assert(isMemIntrinValue() && "Wrong accessor"); - return cast(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 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); - } -}; - -class GVN : public FunctionPass { - bool NoLoads; - MemoryDependenceResults *MD; - DominatorTree *DT; - const TargetLibraryInfo *TLI; - AssumptionCache *AC; - SetVector 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 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 ReplaceWithConstMap; - SmallVector InstrsToErase; - - typedef SmallVector LoadDepVect; - typedef SmallVector AvailValInBlkVect; - typedef SmallVector 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(); } - MemoryDependenceResults &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(); - 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, 4> toSplit; - - // This transformation requires dominator postdominator info - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - if (!NoLoads) - AU.addRequired(); - AU.addRequired(); - - AU.addPreserved(); - AU.addPreserved(); - } - - // Helper functions of redundant load elimination - bool processLoad(LoadInst *L); - bool processNonLocalLoad(LoadInst *L); - bool processAssumeIntrinsic(IntrinsicInst *II); - /// Given a local dependency (Def or Clobber) determine if a value is - /// available for the load. Returns true if an value is known to be - /// available and populates Res. Returns false otherwise. - bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, - Value *Address, AvailableValue &Res); - /// Given a list of non-local dependencies, determine if a value is - /// available for the load in each specified block. If it is, add it to - /// ValuesPerBlock. If not, add it to UnavailableBlocks. - 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 &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; - -} // End anonymous namespace. - -// The public interface to this file... -FunctionPass *llvm::createGVNPass(bool NoLoads) { - return new GVN(NoLoads); +PreservedAnalyses GVN::run(Function &F, AnalysisManager *AM) { + bool Changed = runImpl(F, AM->getResult(F), + AM->getResult(F), + AM->getResult(F), + AM->getResult(F), + &AM->getResult(F)); + return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); } -INITIALIZE_PASS_BEGIN(GVN, "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(GVN, "gvn", "Global Value Numbering", false, false) - #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void GVN::dump(DenseMap& d) { errs() << "{\n"; @@ -2350,18 +2154,16 @@ } /// 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().getMemDep(); - DT = &getAnalysis().getDomTree(); - AC = &getAnalysis().getAssumptionCache(F); - TLI = &getAnalysis().getTLI(); - VN.setAliasAnalysis(&getAnalysis().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; @@ -2857,3 +2659,57 @@ } } } + +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 (skipOptnoneFunction(F)) + return false; + + return Impl.runImpl( + F, getAnalysis().getAssumptionCache(F), + getAnalysis().getDomTree(), + getAnalysis().getTLI(), + getAnalysis().getAAResults(), + NoLoads ? nullptr + : &getAnalysis().getMemDep()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + if (!NoLoads) + AU.addRequired(); + AU.addRequired(); + + AU.addPreserved(); + AU.addPreserved(); + } + +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) Index: llvm/trunk/lib/Transforms/Scalar/Scalar.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/Scalar.cpp +++ llvm/trunk/lib/Transforms/Scalar/Scalar.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ScopedNoAliasAA.h" #include "llvm/Analysis/TypeBasedAliasAnalysis.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Verifier.h" #include "llvm/InitializePasses.h" @@ -40,7 +41,7 @@ initializeDeadInstEliminationPass(Registry); initializeScalarizerPass(Registry); initializeDSEPass(Registry); - initializeGVNPass(Registry); + initializeGVNLegacyPassPass(Registry); initializeEarlyCSELegacyPassPass(Registry); initializeFlattenCFGPassPass(Registry); initializeInductiveRangeCheckEliminationPass(Registry); Index: llvm/trunk/test/Transforms/GVN/basic.ll =================================================================== --- llvm/trunk/test/Transforms/GVN/basic.ll +++ llvm/trunk/test/Transforms/GVN/basic.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -gvn -S | not grep "%z2 =" +; RUN: opt < %s -passes=gvn -S | not grep "%z2 =" define i32 @main() { block1: Index: llvm/trunk/test/Transforms/GVN/pre-gep-load.ll =================================================================== --- llvm/trunk/test/Transforms/GVN/pre-gep-load.ll +++ llvm/trunk/test/Transforms/GVN/pre-gep-load.ll @@ -1,4 +1,6 @@ ; RUN: opt < %s -basicaa -gvn -enable-load-pre -S | FileCheck %s +; RUN: opt < %s -aa-pipeline=basic-aa -passes=gvn -enable-load-pre -S | FileCheck %s + target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128" target triple = "aarch64--linux-gnu"