Index: include/llvm-c/Transforms/Scalar.h =================================================================== --- include/llvm-c/Transforms/Scalar.h +++ include/llvm-c/Transforms/Scalar.h @@ -56,6 +56,9 @@ /** See llvm::createGVNPass function. */ void LLVMAddGVNPass(LLVMPassManagerRef PM); +/** See llvm::createGVNPass function. */ +void LLVMAddNewGVNPass(LLVMPassManagerRef PM); + /** See llvm::createIndVarSimplifyPass function. */ void LLVMAddIndVarSimplifyPass(LLVMPassManagerRef PM); Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -252,6 +252,7 @@ void initializeModuleSummaryIndexWrapperPassPass(PassRegistry &); void initializeNameAnonGlobalLegacyPassPass(PassRegistry &); void initializeNaryReassociateLegacyPassPass(PassRegistry &); +void initializeNewGVNPass(PassRegistry&); void initializeNoAAPass(PassRegistry&); void initializeObjCARCAAWrapperPassPass(PassRegistry&); void initializeObjCARCAPElimPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -167,6 +167,7 @@ (void) llvm::createGVNHoistPass(); (void) llvm::createMergedLoadStoreMotionPass(); (void) llvm::createGVNPass(); + (void) llvm::createNewGVNPass(); (void) llvm::createMemCpyOptPass(); (void) llvm::createLoopDeletionPass(); (void) llvm::createPostDomTree(); Index: include/llvm/Transforms/Scalar.h =================================================================== --- include/llvm/Transforms/Scalar.h +++ include/llvm/Transforms/Scalar.h @@ -348,6 +348,13 @@ //===----------------------------------------------------------------------===// // +// GVN - This pass performs global value numbering and redundant load +// elimination cotemporaneously. +// +FunctionPass *createNewGVNPass(); + +//===----------------------------------------------------------------------===// +// // MemCpyOpt - This pass performs optimizations related to eliminating memcpy // calls and/or combining multiple stores into memset's. // Index: include/llvm/Transforms/Scalar/GVNExpression.h =================================================================== --- include/llvm/Transforms/Scalar/GVNExpression.h +++ include/llvm/Transforms/Scalar/GVNExpression.h @@ -1,4 +1,4 @@ -//===- GVNExpression.h - GVN Expression classes -------*- C++ -*-===// +//======- GVNExpression.h - GVN Expression classes -------*- C++ -*-==-------=// // // The LLVM Compiler Infrastructure // @@ -12,8 +12,10 @@ /// classes /// //===----------------------------------------------------------------------===// + #ifndef LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H #define LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H + #include "llvm/ADT/Hashing.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Instructions.h" @@ -50,30 +52,28 @@ protected: ExpressionType EType; - unsigned int Opcode; + unsigned Opcode; public: - unsigned int getOpcode() const { return Opcode; } + unsigned getOpcode() const { return Opcode; } - void setOpcode(unsigned int opcode) { Opcode = opcode; } + void setOpcode(unsigned opcode) { Opcode = opcode; } ExpressionType getExpressionType() const { return EType; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const Expression *) { return true; } + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const Expression *) { return true; } - Expression(unsigned int o = ~2U) - : EType(ExpressionTypeBase), Opcode(o) {} - Expression(ExpressionType etype, unsigned int o = ~2U) - : EType(etype), Opcode(o) {} + Expression(ExpressionType ET = ExpressionTypeBase, unsigned O = ~2U) + : EType(ET), Opcode(O) {} - virtual ~Expression() {} + virtual ~Expression() = default; bool operator==(const Expression &Other) const { if (Opcode != Other.Opcode) return false; if (Opcode == ~0U || Opcode == ~1U) return true; - // Compare etype for anything but load and store + // Compare etype for anything but load and store. if (getExpressionType() != ExpressionTypeLoad && getExpressionType() != ExpressionTypeStore && getExpressionType() != Other.getExpressionType()) @@ -82,7 +82,7 @@ return equals(Other); } - virtual bool equals(const Expression &other) const { return true; } + virtual bool equals(const Expression &Other) const { return true; } virtual hash_code getHashValue() const { return hash_combine(EType, Opcode); @@ -100,6 +100,7 @@ } void dump() const { print(dbgs()); } }; + inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) { E.print(OS); return OS; @@ -115,8 +116,8 @@ protected: Value **Operands; - unsigned int MaxOperands; - unsigned int NumOperands; + unsigned MaxOperands; + unsigned NumOperands; Type *ValueType; public: @@ -125,44 +126,44 @@ /// \brief Swap two operands. Used during GVN to put commutative operands in /// order. - inline void swapOperands(unsigned First, unsigned Second) { + void swapOperands(unsigned First, unsigned Second) { std::swap(Operands[First], Operands[Second]); } - inline Value *getOperand(unsigned N) const { + Value *getOperand(unsigned N) const { assert(Operands && "Operands not allocated"); assert(N < NumOperands && "Operand out of range"); return Operands[N]; } - inline void setOperand(unsigned N, Value *V) { + void setOperand(unsigned N, Value *V) { assert(Operands && "Operands not allocated before setting"); assert(N < NumOperands && "Operand out of range"); Operands[N] = V; } - inline unsigned int getNumOperands() const { return NumOperands; } + unsigned getNumOperands() const { return NumOperands; } - inline op_iterator ops_begin() { return Operands; } - inline op_iterator ops_end() { return Operands + NumOperands; } - inline const_ops_iterator ops_begin() const { return Operands; } - inline const_ops_iterator ops_end() const { return Operands + NumOperands; } - inline iterator_range operands() { + op_iterator ops_begin() { return Operands; } + op_iterator ops_end() { return Operands + NumOperands; } + const_ops_iterator ops_begin() const { return Operands; } + const_ops_iterator ops_end() const { return Operands + NumOperands; } + iterator_range operands() { return iterator_range(ops_begin(), ops_end()); } - inline iterator_range operands() const { + iterator_range operands() const { return iterator_range(ops_begin(), ops_end()); } - inline void ops_push_back(Value *Arg) { + void ops_push_back(Value *Arg) { assert(NumOperands < MaxOperands && "Tried to add too many operands"); assert(Operands && "Operandss not allocated before pushing"); Operands[NumOperands++] = Arg; } - inline bool ops_empty() const { return getNumOperands() == 0; } + bool ops_empty() const { return getNumOperands() == 0; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const BasicExpression *) { return true; } - static inline bool classof(const Expression *EB) { + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const BasicExpression *) { return true; } + static bool classof(const Expression *EB) { ExpressionType et = EB->getExpressionType(); return et > ExpressionTypeBasicStart && et < ExpressionTypeBasicEnd; } @@ -179,13 +180,13 @@ Type *getType() const { return ValueType; } - BasicExpression(unsigned int NumOperands) + BasicExpression(unsigned NumOperands) : BasicExpression(NumOperands, ExpressionTypeBasic) {} - BasicExpression(unsigned int NumOperands, ExpressionType ET) + BasicExpression(unsigned NumOperands, ExpressionType ET) : Expression(ET), Operands(nullptr), MaxOperands(NumOperands), NumOperands(0), ValueType(nullptr) {} - virtual ~BasicExpression() {} + virtual ~BasicExpression() = default; virtual bool equals(const Expression &Other) const { const BasicExpression &OE = cast(Other); @@ -229,16 +230,16 @@ MemoryAccess *DefiningAccess; public: - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const CallExpression *) { return true; } - static inline bool classof(const Expression *EB) { + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const CallExpression *) { return true; } + static bool classof(const Expression *EB) { return EB->getExpressionType() == ExpressionTypeCall; } - CallExpression(unsigned int NumOperands, CallInst *C, MemoryAccess *DA) + CallExpression(unsigned NumOperands, CallInst *C, MemoryAccess *DA) : BasicExpression(NumOperands, ExpressionTypeCall), Call(C), DefiningAccess(DA) {} - virtual ~CallExpression() {} + virtual ~CallExpression() = default; virtual bool equals(const Expression &Other) const { if (!this->BasicExpression::equals(Other)) @@ -260,7 +261,7 @@ OS << " represents call at " << Call; } }; -class LoadExpression : public BasicExpression { +class LoadExpression final : public BasicExpression { private: void operator=(const LoadExpression &) = delete; LoadExpression(const LoadExpression &) = delete; @@ -271,7 +272,7 @@ MemoryAccess *DefiningAccess; unsigned Alignment; - LoadExpression(enum ExpressionType EType, unsigned int NumOperands, + LoadExpression(enum ExpressionType EType, unsigned NumOperands, LoadInst *L, MemoryAccess *DA) : BasicExpression(NumOperands, EType), Load(L), DefiningAccess(DA) { Alignment = L ? L->getAlignment() : 0; @@ -286,16 +287,16 @@ unsigned getAlignment() const { return Alignment; } void setAlignment(unsigned Align) { Alignment = Align; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const LoadExpression *) { return true; } - static inline bool classof(const Expression *EB) { + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const LoadExpression *) { return true; } + static bool classof(const Expression *EB) { return EB->getExpressionType() == ExpressionTypeLoad; } - LoadExpression(unsigned int NumOperands, LoadInst *L, MemoryAccess *DA) + LoadExpression(unsigned NumOperands, LoadInst *L, MemoryAccess *DA) : LoadExpression(ExpressionTypeLoad, NumOperands, L, DA) {} - virtual ~LoadExpression() {} + virtual ~LoadExpression() = default; virtual bool equals(const Expression &Other) const; @@ -327,16 +328,16 @@ StoreInst *getStoreInst() const { return Store; } MemoryAccess *getDefiningAccess() const { return DefiningAccess; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const StoreExpression *) { return true; } - static inline bool classof(const Expression *EB) { + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const StoreExpression *) { return true; } + static bool classof(const Expression *EB) { return EB->getExpressionType() == ExpressionTypeStore; } - StoreExpression(unsigned int NumOperands, StoreInst *S, MemoryAccess *DA) + StoreExpression(unsigned NumOperands, StoreInst *S, MemoryAccess *DA) : BasicExpression(NumOperands, ExpressionTypeStore), Store(S), DefiningAccess(DA) {} - virtual ~StoreExpression() {} + virtual ~StoreExpression() = default; virtual bool equals(const Expression &Other) const; @@ -359,45 +360,46 @@ AggregateValueExpression(const AggregateValueExpression &) = delete; AggregateValueExpression() = delete; - unsigned int MaxIntOperands; - unsigned int NumIntOperands; - unsigned int *IntOperands; + unsigned MaxIntOperands; + unsigned NumIntOperands; + unsigned *IntOperands; public: - typedef unsigned int *int_arg_iterator; - typedef const unsigned int *const_int_arg_iterator; + typedef unsigned *int_arg_iterator; + typedef const unsigned *const_int_arg_iterator; - inline int_arg_iterator int_ops_begin() { return IntOperands; } - inline int_arg_iterator int_ops_end() { return IntOperands + NumIntOperands; } - inline const_int_arg_iterator int_ops_begin() const { return IntOperands; } - inline const_int_arg_iterator int_ops_end() const { + int_arg_iterator int_ops_begin() { return IntOperands; } + int_arg_iterator int_ops_end() { return IntOperands + NumIntOperands; } + const_int_arg_iterator int_ops_begin() const { return IntOperands; } + const_int_arg_iterator int_ops_end() const { return IntOperands + NumIntOperands; } - inline unsigned int int_ops_size() const { return NumIntOperands; } - inline bool int_ops_empty() const { return NumIntOperands == 0; } - inline void int_ops_push_back(unsigned int IntOperand) { + unsigned int_ops_size() const { return NumIntOperands; } + bool int_ops_empty() const { return NumIntOperands == 0; } + void int_ops_push_back(unsigned IntOperand) { assert(NumIntOperands < MaxIntOperands && "Tried to add too many int operands"); assert(IntOperands && "Operands not allocated before pushing"); IntOperands[NumIntOperands++] = IntOperand; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const AggregateValueExpression *) { return true; } - static inline bool classof(const Expression *EB) { + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const AggregateValueExpression *) { return true; } + static bool classof(const Expression *EB) { return EB->getExpressionType() == ExpressionTypeAggregateValue; } - AggregateValueExpression(unsigned int NumOperands, - unsigned int NumIntOperands) + AggregateValueExpression(unsigned NumOperands, + unsigned NumIntOperands) : BasicExpression(NumOperands, ExpressionTypeAggregateValue), MaxIntOperands(NumIntOperands), NumIntOperands(0), IntOperands(nullptr) {} - virtual ~AggregateValueExpression() {} + virtual ~AggregateValueExpression() = default; + virtual void allocateIntOperands(BumpPtrAllocator &Allocator) { assert(!IntOperands && "Operands already allocated"); - IntOperands = Allocator.Allocate(MaxIntOperands); + IntOperands = Allocator.Allocate(MaxIntOperands); } virtual bool equals(const Expression &Other) const { @@ -428,11 +430,11 @@ } }; -class PHIExpression : public BasicExpression { +class PHIExpression final : public BasicExpression { public: - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const PHIExpression *) { return true; } - static inline bool classof(const Expression *EB) { + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const PHIExpression *) { return true; } + static bool classof(const Expression *EB) { return EB->getExpressionType() == ExpressionTypePhi; } BasicBlock *getBB() const { return BB; } @@ -448,10 +450,10 @@ return true; } - PHIExpression(unsigned int NumOperands, BasicBlock *B) + PHIExpression(unsigned NumOperands, BasicBlock *B) : BasicExpression(NumOperands, ExpressionTypePhi), BB(B) {} - virtual ~PHIExpression() {} + virtual ~PHIExpression() = default; virtual hash_code getHashValue() const { return hash_combine(this->BasicExpression::getHashValue(), BB); @@ -469,11 +471,11 @@ PHIExpression() = delete; BasicBlock *BB; }; -class VariableExpression : public Expression { +class VariableExpression final : public Expression { public: - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const VariableExpression *) { return true; } - static inline bool classof(const Expression *EB) { + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const VariableExpression *) { return true; } + static bool classof(const Expression *EB) { return EB->getExpressionType() == ExpressionTypeVariable; } @@ -506,11 +508,11 @@ Value *VariableValue; }; -class ConstantExpression : public Expression { +class ConstantExpression final : public Expression { public: - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const ConstantExpression *) { return true; } - static inline bool classof(const Expression *EB) { + // Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const ConstantExpression *) { return true; } + static bool classof(const Expression *EB) { return EB->getExpressionType() == ExpressionTypeConstant; } Constant *getConstantValue() const { return ConstantValue; } @@ -550,11 +552,10 @@ return false; if (!this->BasicExpression::equals(Other)) return false; - if (const LoadExpression *OtherL = dyn_cast(&Other)) { + if (const auto *OtherL = dyn_cast(&Other)) { if (DefiningAccess != OtherL->getDefiningAccess()) return false; - } else if (const StoreExpression *OtherS = - dyn_cast(&Other)) { + } else if (const auto *OtherS = dyn_cast(&Other)) { if (DefiningAccess != OtherS->getDefiningAccess()) return false; } @@ -566,11 +567,10 @@ return false; if (!this->BasicExpression::equals(Other)) return false; - if (const LoadExpression *OtherL = dyn_cast(&Other)) { + if (const auto *OtherL = dyn_cast(&Other)) { if (DefiningAccess != OtherL->getDefiningAccess()) return false; - } else if (const StoreExpression *OtherS = - dyn_cast(&Other)) { + } else if (const auto *OtherS = dyn_cast(&Other)) { if (DefiningAccess != OtherS->getDefiningAccess()) return false; } Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -39,6 +39,7 @@ MemCpyOptimizer.cpp MergedLoadStoreMotion.cpp NaryReassociate.cpp + NewGVN.cpp PartiallyInlineLibCalls.cpp PlaceSafepoints.cpp Reassociate.cpp Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- lib/Transforms/Scalar/NewGVN.cpp +++ lib/Transforms/Scalar/NewGVN.cpp @@ -103,32 +103,32 @@ // struct CongruenceClass { typedef SmallPtrSet MemberSet; - unsigned int ID; - // Representative leader + unsigned ID; + // Representative leader. Value *RepLeader; - // Defining Expression + // Defining Expression. const Expression *DefiningExpr; - // Actual members of this class. These are the things the same everywhere + // Actual members of this class. MemberSet Members; // True if this class has no members left. This is mainly used for assertion // purposes, and for skipping empty classes. bool Dead; - explicit CongruenceClass(unsigned int ID) + explicit CongruenceClass(unsigned ID) : ID(ID), RepLeader(0), DefiningExpr(0), Dead(false) {} - CongruenceClass(unsigned int ID, Value *Leader, const Expression *E) + CongruenceClass(unsigned ID, Value *Leader, const Expression *E) : ID(ID), RepLeader(Leader), DefiningExpr(E), Dead(false) {} }; namespace llvm { template <> struct DenseMapInfo { - static inline const Expression *getEmptyKey() { + static const Expression *getEmptyKey() { uintptr_t Val = static_cast(-1); Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; return reinterpret_cast(Val); } - static inline const Expression *getTombstoneKey() { + static const Expression *getTombstoneKey() { uintptr_t Val = static_cast(-2); Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; return reinterpret_cast(Val); @@ -158,23 +158,23 @@ BumpPtrAllocator ExpressionAllocator; ArrayRecycler ArgRecycler; - // Congruence class info + // Congruence class info. CongruenceClass *InitialClass; std::vector CongruenceClasses; - unsigned int NextCongruenceNum = 0; + unsigned NextCongruenceNum = 0; - // Value Mappings + // Value Mappings. DenseMap ValueToClass; DenseMap ValueToExpression; - // Expression to class mapping + // Expression to class mapping. typedef DenseMap ExpressionClassMap; ExpressionClassMap ExpressionToClass; - // Which values have changed as a result of leader changes + // Which values have changed as a result of leader changes. SmallPtrSet ChangedValues; - // Reachability info + // Reachability info. typedef BasicBlockEdge BlockEdge; DenseSet ReachableEdges; SmallPtrSet ReachableBlocks; @@ -189,22 +189,24 @@ // individual and ranges, as well as "find next element" This // enables us to use it as a worklist with essentially 0 cost. BitVector TouchedInstructions; + DenseMap> BlockInstRange; DenseMap> DominatedInstRange; - // Debugging for how many times each block and instruction got processed + + // Debugging for how many times each block and instruction got processed. DenseMap ProcessedCount; - // DFS info + // DFS info. DenseMap> DFSDomMap; - DenseMap InstrDFS; + DenseMap InstrDFS; std::vector DFSToInstr; - // Deletion info + // Deletion info. SmallPtrSet InstructionsToErase; public: - static char ID; // Pass identification, replacement for typeid + static char ID; // Pass identification, replacement for typeid. explicit NewGVN() : FunctionPass(ID) { initializeNewGVNPass(*PassRegistry::getPassRegistry()); } @@ -215,7 +217,7 @@ MemorySSA *MSSA); private: - // This transformation requires dominator postdominator info + // This transformation requires dominator postdominator info. void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addRequired(); @@ -227,7 +229,7 @@ AU.addPreserved(); } - // expression handling + // Expression handling. const Expression *createExpression(Instruction *, const BasicBlock *); const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *, const BasicBlock *); @@ -247,7 +249,7 @@ const AggregateValueExpression * createAggregateValueExpression(Instruction *, const BasicBlock *); - // Congruence class handling + // Congruence class handling. CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) { CongruenceClass *result = new CongruenceClass(NextCongruenceNum++, Leader, E); @@ -263,7 +265,7 @@ } void initializeCongruenceClasses(Function &F); - // Symbolic evaluation + // Symbolic evaluation. const Expression *checkSimplificationResults(Expression *, Instruction *, Value *); const Expression *performSymbolicEvaluation(Value *, const BasicBlock *); @@ -278,19 +280,19 @@ const Expression *performSymbolicAggrValueEvaluation(Instruction *, const BasicBlock *); - // Congruence finding - // Templated to allow them to work both on BB's and BB-edges + // Congruence finding. + // Templated to allow them to work both on BB's and BB-edges. template Value *lookupOperandLeader(Value *, const User *, const T &) const; void performCongruenceFinding(Value *, const Expression *); - // Reachability handling + // Reachability handling. void updateReachableEdge(BasicBlock *, BasicBlock *); void processOutgoingEdges(TerminatorInst *, BasicBlock *); bool isOnlyReachableViaThisEdge(const BasicBlockEdge &); Value *findConditionEquivalence(Value *, BasicBlock *) const; - // Elimination + // Elimination. struct ValueDFS; void convertDenseToDFSOrdered(CongruenceClass::MemberSet &, std::vector &); @@ -300,11 +302,12 @@ void markInstructionForDeletion(Instruction *); void deleteInstructionsInBlock(BasicBlock *); - // New instruction creation + // New instruction creation. void handleNewInstruction(Instruction *){}; void markUsersTouched(Value *); + void markMemoryUsersTouched(MemoryAccess *); - // Utilities + // Utilities. void cleanupTables(); std::pair assignDFSNumbers(BasicBlock *, unsigned); void updateProcessedCount(Value *V); @@ -312,7 +315,7 @@ char NewGVN::ID = 0; -// createGVNPass - The public interface to this file... +// createGVNPass - The public interface to this file. FunctionPass *llvm::createNewGVNPass() { return new NewGVN(); } #ifndef NDEBUG @@ -357,12 +360,11 @@ } // Set basic expression info (Arguments, type, opcode) for Expression -// E from Instruction I in block B - +// E from Instruction I in block B. bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E, const BasicBlock *B) { bool AllConstant = true; - if (auto GEP = dyn_cast(I)) + if (auto *GEP = dyn_cast(I)) E->setType(GEP->getSourceElementType()); else E->setType(I->getType()); @@ -415,7 +417,7 @@ Instruction *I, Value *V) { if (!V) return NULL; - if (Constant *C = dyn_cast(V)) { + if (auto *C = dyn_cast(V)) { #ifndef NDEBUG if (I) DEBUG(dbgs() << "Simplified " << *I << " to " @@ -483,7 +485,7 @@ // add 0, x -> x // and x, x -> x // We should handle this by simply rewriting the expression. - if (CmpInst *CI = dyn_cast(I)) { + if (auto *CI = dyn_cast(I)) { // Sort the operand value numbers so xx get the same value // number. CmpInst::Predicate Predicate = CI->getPredicate(); @@ -522,7 +524,7 @@ *DL, TLI, DT, AC); if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) return SimplifiedE; - } else if (BitCastInst *BI = dyn_cast(I)) { + } else if (auto *BI = dyn_cast(I)) { Value *V = SimplifyInstruction(BI, *DL, TLI, DT, AC); if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) return SimplifiedE; @@ -534,11 +536,11 @@ return SimplifiedE; } else if (AllConstant) { // We don't bother trying to simplify unless all of the operands - // were constant + // were constant. // TODO: There are a lot of Simplify*'s we could call here, if we // wanted to. The original motivating case for this code was a // zext i1 false to i8, which we don't have an interface to - // simplify (IE there is no SimplifyZExt) + // simplify (IE there is no SimplifyZExt). SmallVector C; for (Value *Arg : E->operands()) @@ -555,7 +557,7 @@ const AggregateValueExpression * NewGVN::createAggregateValueExpression(Instruction *I, const BasicBlock *B) { - if (InsertValueInst *II = dyn_cast(I)) { + if (auto *II = dyn_cast(I)) { AggregateValueExpression *E = new (ExpressionAllocator) AggregateValueExpression(I->getNumOperands(), II->getNumIndices()); setBasicExpressionInfo(I, E, B); @@ -565,7 +567,7 @@ E->int_ops_push_back(Index); return E; - } else if (ExtractValueInst *EI = dyn_cast(I)) { + } else if (auto *EI = dyn_cast(I)) { AggregateValueExpression *E = new (ExpressionAllocator) AggregateValueExpression(I->getNumOperands(), EI->getNumIndices()); setBasicExpressionInfo(EI, E, B); @@ -588,7 +590,7 @@ const Expression *NewGVN::createVariableOrConstant(Value *V, const BasicBlock *B) { auto Leader = lookupOperandLeader(V, nullptr, B); - if (Constant *C = dyn_cast(Leader)) + if (auto *C = dyn_cast(Leader)) return createConstantExpression(C); return createVariableExpression(Leader); } @@ -627,7 +629,8 @@ LoadExpression *E = new (ExpressionAllocator) LoadExpression(1, LI, DA); E->allocateOperands(ArgRecycler, ExpressionAllocator); E->setType(LoadType); - // Give store and loads same opcode so they value number together + + // Give store and loads same opcode so they value number together. E->setOpcode(0); auto Operand = lookupOperandLeader(PointerOp, LI, B); E->ops_push_back(Operand); @@ -636,7 +639,7 @@ // TODO: Value number heap versions. We may be able to discover // things alias analysis can't on it's own (IE that a store and a - // load have the same value, and thus, it isn't clobbering the load) + // load have the same value, and thus, it isn't clobbering the load). return E; } @@ -647,13 +650,15 @@ new (ExpressionAllocator) StoreExpression(SI->getNumOperands(), SI, DA); E->allocateOperands(ArgRecycler, ExpressionAllocator); E->setType(SI->getValueOperand()->getType()); - // Give store and loads same opcode so they value number together + + // Give store and loads same opcode so they value number together. E->setOpcode(0); auto Operand = lookupOperandLeader(SI->getPointerOperand(), SI, B); E->ops_push_back(Operand); + // TODO: Value number heap versions. We may be able to discover // things alias analysis can't on it's own (IE that a store and a - // load have the same value, and thus, it isn't clobbering the load) + // load have the same value, and thus, it isn't clobbering the load). return E; } @@ -669,23 +674,22 @@ LoadInst *LI = cast(I); // We can eliminate in favor of non-simple loads, but we won't be able to - // eliminate them + // eliminate them. if (!LI->isSimple()) return nullptr; Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand(), I, B); - // Load of undef is undef + // Load of undef is undef. if (isa(LoadAddressLeader)) return createConstantExpression(UndefValue::get(LI->getType())); MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(I); if (!MSSA->isLiveOnEntryDef(DefiningAccess)) { - if (MemoryDef *MD = dyn_cast(DefiningAccess)) { + if (auto *MD = dyn_cast(DefiningAccess)) { Instruction *DefiningInst = MD->getMemoryInst(); - // If the defining instruction is not reachable, replace with - // undef + // If the defining instruction is not reachable, replace with undef. if (!ReachableBlocks.count(DefiningInst->getParent())) return createConstantExpression(UndefValue::get(LI->getType())); } @@ -697,7 +701,7 @@ } /// performSymbolicCallEvaluation - Evaluate read only and pure calls, and -/// create an expression result +/// create an expression result. const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I, const BasicBlock *B) { CallInst *CI = cast(I); @@ -711,7 +715,7 @@ } // performSymbolicPHIEvaluation - Evaluate PHI nodes symbolically, and -// create an expression result +// create an expression result. const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I, const BasicBlock *B) { PHIExpression *E = cast(createPHIExpression(I)); @@ -736,16 +740,13 @@ if (AllSameValue) { // It's possible to have phi nodes with cycles (IE dependent on // other phis that are .... dependent on the original phi node), - // especially - // in weird CFG's where some arguments are unreachable, or + // especially in weird CFG's where some arguments are unreachable, or // uninitialized along certain paths. // This can cause infinite loops during evaluation (even if you disable - // the - // recursion below, you will simply ping-pong between congruence classes) - // If a phi node symbolically evaluates to another phi node, just - // leave it alone - // If they are really the same, we will still eliminate them in - // favor of each other. + // the recursion below, you will simply ping-pong between congruence + // classes). If a phi node symbolically evaluates to another phi node, + // just leave it alone. If they are really the same, we will still + // eliminate them in favor of each other. if (isa(AllSameValue)) return E; NumGVNPhisAllSame++; @@ -753,7 +754,7 @@ << "\n"); E->deallocateOperands(ArgRecycler); ExpressionAllocator.Deallocate(E); - if (Constant *C = dyn_cast(AllSameValue)) + if (auto *C = dyn_cast(AllSameValue)) return createConstantExpression(C); return createVariableExpression(AllSameValue); } @@ -763,8 +764,8 @@ const Expression * NewGVN::performSymbolicAggrValueEvaluation(Instruction *I, const BasicBlock *B) { - if (ExtractValueInst *EI = dyn_cast(I)) { - IntrinsicInst *II = dyn_cast(EI->getAggregateOperand()); + if (auto *EI = dyn_cast(I)) { + auto *II = dyn_cast(EI->getAggregateOperand()); if (II != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) { unsigned Opcode = 0; // EI might be an extract from one of our recognised intrinsics. If it @@ -803,16 +804,16 @@ } /// performSymbolicEvaluation - Substitute and symbolize the value -/// before value numbering +/// before value numbering. const Expression *NewGVN::performSymbolicEvaluation(Value *V, const BasicBlock *B) { const Expression *E = NULL; - if (Constant *C = dyn_cast(V)) + if (auto *C = dyn_cast(V)) E = createConstantExpression(C); else if (isa(V) || isa(V)) { E = createVariableExpression(V); } else { - // TODO: memory intrinsics + // TODO: memory intrinsics. // TODO: Some day, we should do the forward propagation and reassociation // parts of the algorithm. Instruction *I = cast(V); @@ -884,15 +885,16 @@ return E; } -/// There is an edge from 'Src' to 'Dst'. Return -/// true if every path from the entry block to 'Dst' passes via this edge. In -/// particular 'Dst' must not be reachable via another edge from 'Src'. +/// There is an edge from 'Src' to 'Dst'. Return true if every path from +/// the entry block to 'Dst' passes via this edge. In particular 'Dst' +/// must not be reachable via another edge from 'Src'. bool NewGVN::isOnlyReachableViaThisEdge(const BasicBlockEdge &E) { -// While in theory it is interesting to consider the case in which Dst has -// more than one predecessor, because Dst might be part of a loop which is -// only reachable from Src, in practice it is pointless since at the time -// GVN runs all such loops have preheaders, which means that Dst will have -// been changed to have only one predecessor, namely Src. + + // While in theory it is interesting to consider the case in which Dst has + // more than one predecessor, because Dst might be part of a loop which is + // only reachable from Src, in practice it is pointless since at the time + // 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!"); @@ -901,57 +903,66 @@ } void NewGVN::markUsersTouched(Value *V) { - // Now mark the users as touched + // Now mark the users as touched. for (auto &U : V->uses()) { - Instruction *User = dyn_cast(U.getUser()); + auto *User = dyn_cast(U.getUser()); assert(User && "Use of value not within an instruction?"); TouchedInstructions.set(InstrDFS[User]); } } -/// performCongruenceFinding - Perform congruence finding on a given -/// value numbering expression +void NewGVN::markMemoryUsersTouched(MemoryAccess *MA) { + for (auto U : MA->users()) { + if (auto *MUD = dyn_cast(U)) + TouchedInstructions.set(InstrDFS[MUD->getMemoryInst()]); + else + TouchedInstructions.set(InstrDFS[MA]); + } +} + +/// perf rmCongruenceFinding - Perform congruence finding on a given +/// value numbering expression. void NewGVN::performCongruenceFinding(Value *V, const Expression *E) { ValueToExpression[V] = E; // This is guaranteed to return something, since it will at least find - // INITIAL + // INITIAL. CongruenceClass *VClass = ValueToClass[V]; assert(VClass && "Should have found a vclass"); - // Dead classes should have been eliminated from the mapping + // Dead classes should have been eliminated from the mapping. assert(!VClass->Dead && "Found a dead class"); CongruenceClass *EClass; // Expressions we can't symbolize are always in their own unique - // congruence class + // congruence class. if (E == NULL) { - // We may have already made a unique class + // We may have already made a unique class. if (VClass->Members.size() != 1 || VClass->RepLeader != V) { CongruenceClass *NewClass = createCongruenceClass(V, NULL); - // We should always be adding the member in the below code + // We should always be adding the member in the below code. EClass = NewClass; DEBUG(dbgs() << "Created new congruence class for " << *V << " due to NULL expression\n"); } else { EClass = VClass; } - } else if (const VariableExpression *VE = dyn_cast(E)) { + } else if (const auto *VE = dyn_cast(E)) { EClass = ValueToClass[VE->getVariableValue()]; } else { auto lookupResult = ExpressionToClass.insert({E, nullptr}); - // If it's not in the value table, create a new congruence class + // If it's not in the value table, create a new congruence class. if (lookupResult.second) { CongruenceClass *NewClass = createCongruenceClass(NULL, E); auto place = lookupResult.first; place->second = NewClass; - // Constants and variables should always be made the leader - if (const ConstantExpression *CE = dyn_cast(E)) + // Constants and variables should always be made the leader. + if (const auto *CE = dyn_cast(E)) NewClass->RepLeader = CE->getConstantValue(); - else if (const VariableExpression *VE = dyn_cast(E)) + else if (const auto *VE = dyn_cast(E)) NewClass->RepLeader = VE->getVariableValue(); - else if (const StoreExpression *SE = dyn_cast(E)) + else if (const auto *SE = dyn_cast(E)) NewClass->RepLeader = SE->getStoreInst()->getValueOperand(); else NewClass->RepLeader = V; @@ -980,7 +991,7 @@ VClass->Members.erase(V); EClass->Members.insert(V); ValueToClass[V] = EClass; - // See if we destroyed the class or need to swap leaders + // See if we destroyed the class or need to swap leaders. if (VClass->Members.empty() && VClass != InitialClass) { if (VClass->DefiningExpr) { VClass->Dead = true; @@ -988,27 +999,30 @@ ExpressionToClass.erase(VClass->DefiningExpr); } } else if (VClass->RepLeader == V) { - /// XXX: Check this. When the leader changes, the value numbering of - /// everything may change, so we need to reprocess. + // FIXME: When the leader changes, the value numbering of + // everything may change, so we need to reprocess. VClass->RepLeader = *(VClass->Members.begin()); for (auto M : VClass->Members) { - if (Instruction *I = dyn_cast(M)) + if (auto *I = dyn_cast(M)) TouchedInstructions.set(InstrDFS[I]); ChangedValues.insert(M); } } } markUsersTouched(V); + if (Instruction *I = dyn_cast(V)) + if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) + markMemoryUsersTouched(MA); } } // updateReachableEdge - Process the fact that Edge (from, to) is // reachable, including marking any newly reachable blocks and -// instructions for processing +// instructions for processing. void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) { - // Check if the Edge was reachable before + // Check if the Edge was reachable before. if (ReachableEdges.insert({From, To}).second) { - // If this block wasn't reachable before, all instructions are touched + // If this block wasn't reachable before, all instructions are touched. if (ReachableBlocks.insert(To).second) { DEBUG(dbgs() << "Block " << getBlockName(To) << " marked reachable\n"); const auto &InstRange = BlockInstRange.lookup(To); @@ -1017,11 +1031,11 @@ DEBUG(dbgs() << "Block " << getBlockName(To) << " was reachable, but new edge {" << getBlockName(From) << "," << getBlockName(To) << "} to it found\n"); + // We've made an edge reachable to an existing block, which may - // impact predicates. - // Otherwise, only mark the phi nodes as touched, as they are - // the only thing that depend on new edges. Anything using their - // values will get propagated to if necessary + // impact predicates. Otherwise, only mark the phi nodes as touched, as + // they are the only thing that depend on new edges. Anything using their + // values will get propagated to if necessary. auto BI = To->begin(); while (isa(BI)) { TouchedInstructions.set(InstrDFS[&*BI]); @@ -1033,7 +1047,7 @@ // findConditionEquivalence - Given a predicate condition (from a // switch, cmp, or whatever) and a block, see if we know some constant -// value for it already +// value for it already. Value *NewGVN::findConditionEquivalence(Value *Cond, BasicBlock *B) const { auto Result = lookupOperandLeader(Cond, nullptr, B); if (isa(Result)) @@ -1044,16 +1058,15 @@ // processOutgoingEdges - Process the outgoing edges of a block for // reachability. void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) { - // Evaluate Reachability of terminator instruction - // Conditional branch + // Evaluate reachability of terminator instruction. BranchInst *BR; if ((BR = dyn_cast(TI)) && BR->isConditional()) { Value *Cond = BR->getCondition(); Value *CondEvaluated = findConditionEquivalence(Cond, B); if (!CondEvaluated) { - if (Instruction *I = dyn_cast(Cond)) { + if (auto *I = dyn_cast(Cond)) { const Expression *E = createExpression(I, B); - if (const ConstantExpression *CE = dyn_cast(E)) { + if (const auto *CE = dyn_cast(E)) { CondEvaluated = CE->getConstantValue(); } } else if (isa(Cond)) { @@ -1077,7 +1090,7 @@ updateReachableEdge(B, TrueSucc); updateReachableEdge(B, FalseSucc); } - } else if (SwitchInst *SI = dyn_cast(TI)) { + } else if (auto *SI = dyn_cast(TI)) { // For switches, propagate the case values into the case // destinations. @@ -1087,10 +1100,10 @@ bool MultipleEdgesOneReachable = false; Value *SwitchCond = SI->getCondition(); Value *CondEvaluated = findConditionEquivalence(SwitchCond, B); - // See if we were able to turn this switch statement into a constant + // See if we were able to turn this switch statement into a constant. if (CondEvaluated && isa(CondEvaluated)) { ConstantInt *CondVal = cast(CondEvaluated); - // We should be able to get case value for this + // We should be able to get case value for this. auto CaseVal = SI->findCaseValue(CondVal); if (CaseVal.getCaseSuccessor() == SI->getDefaultDest()) { // We proved the value is outside of the range of the case. @@ -1099,7 +1112,7 @@ updateReachableEdge(B, SI->getDefaultDest()); return; } - // Now get where it goes and mark it reachable + // Now get where it goes and mark it reachable. BasicBlock *TargetBlock = CaseVal.getCaseSuccessor(); updateReachableEdge(B, TargetBlock); unsigned WhichSucc = CaseVal.getSuccessorIndex(); @@ -1122,7 +1135,7 @@ } } else { // Otherwise this is either unconditional, or a type we have no - // idea about. Just mark successors as reachable + // idea about. Just mark successors as reachable. for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { BasicBlock *TargetBlock = TI->getSuccessor(i); updateReachableEdge(B, TargetBlock); @@ -1136,7 +1149,7 @@ void NewGVN::initializeCongruenceClasses(Function &F) { // FIXME now i can't remember why this is 2 NextCongruenceNum = 2; - // Initialize all other instructions to be in INITIAL class + // Initialize all other instructions to be in INITIAL class. CongruenceClass::MemberSet InitialValues; for (auto &B : F) for (auto &I : B) @@ -1148,7 +1161,6 @@ InitialClass->Members.swap(InitialValues); // Initialize arguments to be in their own unique congruence classes - // In an IPA-GVN, this would not be done for (auto &FA : F.args()) createSingletonCongruenceClass(&FA); } @@ -1182,15 +1194,15 @@ std::pair NewGVN::assignDFSNumbers(BasicBlock *B, unsigned Start) { - unsigned int End = Start; + unsigned End = Start; for (auto &I : *B) { InstrDFS[&I] = End++; DFSToInstr.emplace_back(&I); } + // All of the range functions taken half-open ranges (open on the end side). // So we do not subtract one from count, because at this point it is one // greater than the last instruction. - return std::make_pair(Start, End); } @@ -1206,8 +1218,7 @@ #endif } -/// runOnFunction - This is the main transformation entry point for a -/// function. +// runOnFunction - This is the main transformation entry point for a function. bool NewGVN::runGVN(Function &F, DominatorTree *DT, AssumptionCache *AC, TargetLibraryInfo *TLI, AliasAnalysis *AA, MemorySSA *MSSA) { @@ -1239,10 +1250,9 @@ } // Handle forward unreachable blocks and figure out which blocks - // have single preds - + // have single preds. for (auto &B : F) { - // Assign numbers to unreachable blocks + // Assign numbers to unreachable blocks. if (!VisitedBlocks.count(&B)) { const auto &BlockRange = assignDFSNumbers(&B, ICount); BlockInstRange.insert({&B, BlockRange}); @@ -1256,29 +1266,30 @@ // that can be quite expensive. At most, we have one expression per // instruction. ExpressionToClass.reserve(ICount + 1); - // Initialize the touched instructions to include the entry block + + // Initialize the touched instructions to include the entry block. const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock()); TouchedInstructions.set(InstRange.first, InstRange.second); ReachableBlocks.insert(&F.getEntryBlock()); initializeCongruenceClasses(F); - // We start out in the entry block + // We start out in the entry block. BasicBlock *LastBlock = &F.getEntryBlock(); while (TouchedInstructions.any()) { - // Walk through all the instructions in all the blocks in RPO + // Walk through all the instructions in all the blocks in RPO. for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1; InstrNum = TouchedInstructions.find_next(InstrNum)) { Instruction *I = DFSToInstr[InstrNum]; BasicBlock *CurrBlock = I->getParent(); - // If we hit a new block, do reachability processing + // If we hit a new block, do reachability processing. if (CurrBlock != LastBlock) { LastBlock = CurrBlock; bool BlockReachable = ReachableBlocks.count(CurrBlock); const auto &InstRange = BlockInstRange.lookup(CurrBlock); - // If it's not reachable, erase any touched instructions and - // move on + + // If it's not reachable, erase any touched instructions and move on. if (!BlockReachable) { TouchedInstructions.reset(InstRange.first, InstRange.second); DEBUG(dbgs() << "Skipping instructions in block " @@ -1305,7 +1316,7 @@ processOutgoingEdges(dyn_cast(I), CurrBlock); } // Reset after processing (because we may mark ourselves as touched when - // we propagate equalities) + // we propagate equalities). TouchedInstructions.reset(InstrNum); } } @@ -1320,7 +1331,7 @@ ToErase->eraseFromParent(); } - // Delete all unreachable blocks + // Delete all unreachable blocks. for (auto &B : F) { BasicBlock *BB = &B; if (!ReachableBlocks.count(BB)) { @@ -1368,16 +1379,15 @@ // Return true if V is a value that will always be available (IE can // be placed anywhere) in the function. We don't do globals here -// because they are often worse to put in place +// because they are often worse to put in place. // TODO: Separate cost from availability - static bool alwaysAvailable(Value *V) { return isa(V) || isa(V); } -// Get the basic block from an instruction/value +// Get the basic block from an instruction/value. static BasicBlock *getBlockForValue(Value *V) { - if (Instruction *I = dyn_cast(V)) + if (auto *I = dyn_cast(V)) return I->getParent(); return nullptr; } @@ -1385,7 +1395,7 @@ int DFSIn; int DFSOut; int LocalNum; - // Only one of these will be set + // Only one of these will be set. Value *Val; Use *U; ValueDFS() @@ -1393,8 +1403,8 @@ bool operator<(const ValueDFS &other) const { // It's not enough that any given field be less than - we have sets - // of fields that need to be evaluated together to give a proper ordering - // for example, if you have + // of fields that need to be evaluated together to give a proper ordering. + // For example, if you have; // DFS (1, 3) // Val 0 // DFS (1, 2) @@ -1426,10 +1436,10 @@ void NewGVN::convertDenseToDFSOrdered(CongruenceClass::MemberSet &Dense, std::vector &DFSOrderedSet) { for (auto D : Dense) { - // First add the value + // First add the value. BasicBlock *BB = getBlockForValue(D); // Constants are handled prior to ever calling this function, so - // we should only be left with instructions as members + // we should only be left with instructions as members. assert(BB || "Should have figured out a basic block for value"); ValueDFS VD; @@ -1438,21 +1448,21 @@ VD.DFSIn = DFSPair.first; VD.DFSOut = DFSPair.second; VD.Val = D; - // If it's an instruction, use the real local dfs number, - if (Instruction *I = dyn_cast(D)) + // If it's an instruction, use the real local dfs number. + if (auto *I = dyn_cast(D)) VD.LocalNum = InstrDFS[I]; else llvm_unreachable("Should have been an instruction"); DFSOrderedSet.emplace_back(VD); - // Now add the users + // Now add the users. for (auto &U : D->uses()) { - if (Instruction *I = dyn_cast(U.getUser())) { + if (auto *I = dyn_cast(U.getUser())) { ValueDFS VD; - // Put the phi node uses in the incoming block + // Put the phi node uses in the incoming block. BasicBlock *IBlock; - if (PHINode *P = dyn_cast(I)) { + if (auto *P = dyn_cast(I)) { IBlock = P->getIncomingBlock(U); // Make phi node users appear last in the incoming block // they are from. @@ -1474,13 +1484,13 @@ static void patchReplacementInstruction(Instruction *I, Value *Repl) { // Patch the replacement so that it is not more restrictive than the value // being replaced. - BinaryOperator *Op = dyn_cast(I); - BinaryOperator *ReplOp = dyn_cast(Repl); + auto *Op = dyn_cast(I); + auto *ReplOp = dyn_cast(Repl); if (Op && ReplOp) ReplOp->andIRFlags(Op); - if (Instruction *ReplInst = dyn_cast(Repl)) { + if (auto *ReplInst = dyn_cast(Repl)) { // FIXME: If both the original and replacement value are part of the // same control-flow region (meaning that the execution of one // guarentees the executation of the other), then we can combine the @@ -1513,8 +1523,7 @@ return; // Delete the instructions backwards, as it has a reduced likelihood of having - // to update as many def-use and use-def chains. - // Start after the terminator + // to update as many def-use and use-def chains. Start after the terminator. auto StartPoint = BB->rbegin(); ++StartPoint; // Note that we explicitly recalculate BB->rend() on each iteration, @@ -1546,9 +1555,9 @@ } namespace { -// This is a stack that contains both the value and dfs info of where -// that value is valid +// This is a stack that contains both the value and dfs info of where +// that value is valid. class ValueDFSStack { public: Value *back() const { return ValueStack.back(); } @@ -1566,7 +1575,8 @@ } void popUntilDFSScope(int DFSIn, int DFSOut) { - // These two should always be in sync at this point + + // These two should always be in sync at this point. assert(ValueStack.size() == DFSStack.size() && "Mismatch between ValueStack and DFSStack"); while ( @@ -1606,8 +1616,8 @@ // Since we are going to walk the domtree anyway, and we can't guarantee the // DFS numbers are updated, we compute some ourselves. - DT->updateDFSNumbers(); + for (auto &B : F) { if (!ReachableBlocks.count(&B)) { for (const auto S : successors(&B)) { @@ -1629,10 +1639,11 @@ for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) { CongruenceClass *CC = CongruenceClasses[i]; + // FIXME: We should eventually be able to replace everything still // in the initial class with undef, as they should be unreachable. // Right now, initial still contains some things we skip value - // numbering of (UNREACHABLE's, for example) + // numbering of (UNREACHABLE's, for example). if (CC == InitialClass || CC->Dead) continue; assert(CC->RepLeader && "We should have had a leader"); @@ -1647,7 +1658,7 @@ Value *Member = M; - // Void things have no uses we can replace + // Void things have no uses we can replace. if (Member == CC->RepLeader || Member->getType()->isVoidTy()) { MembersLeft.insert(Member); continue; @@ -1658,7 +1669,7 @@ // Due to equality propagation, these may not always be // instructions, they may be real values. We don't really // care about trying to replace the non-instructions. - if (Instruction *I = dyn_cast(Member)) { + if (auto *I = dyn_cast(Member)) { assert(CC->RepLeader != I && "About to accidentally remove our leader"); replaceInstruction(I, CC->RepLeader); @@ -1673,22 +1684,20 @@ } else { DEBUG(dbgs() << "Eliminating in congruence class " << CC->ID << "\n"); - // If this is a singleton, we can skip it + // If this is a singleton, we can skip it. if (CC->Members.size() != 1) { // This is a stack because equality replacement/etc may place // constants in the middle of the member list, and we want to use // those constant values in preference to the current leader, over // the scope of those constants. - ValueDFSStack EliminationStack; - // Convert the members to DFS ordered sets and - // then merge them. + // Convert the members to DFS ordered sets and then merge them. std::vector DFSOrderedSet; convertDenseToDFSOrdered(CC->Members, DFSOrderedSet); - // Sort the whole thing + // Sort the whole thing. sort(DFSOrderedSet.begin(), DFSOrderedSet.end()); for (auto &C : DFSOrderedSet) { @@ -1697,8 +1706,7 @@ Value *Member = C.Val; Use *MemberUse = C.U; - // We ignore void things because we can't get a value from - // them. + // We ignore void things because we can't get a value from them. if (Member && Member->getType()->isVoidTy()) continue; @@ -1717,25 +1725,24 @@ // First, we see if we are out of scope or empty. If so, // and there equivalences, we try to replace the top of // stack with equivalences (if it's on the stack, it must - // not have been eliminated yet) + // not have been eliminated yet). // Then we synchronize to our current scope, by // popping until we are back within a DFS scope that // dominates the current member. // Then, what happens depends on a few factors // If the stack is now empty, we need to push // If we have a constant or a local equivalence we want to - // start using, we also push + // start using, we also push. // Otherwise, we walk along, processing members who are - // dominated by this scope, and eliminate them + // dominated by this scope, and eliminate them. bool ShouldPush = Member && (EliminationStack.empty() || isa(Member)); bool OutOfScope = !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut); if (OutOfScope || ShouldPush) { - // Sync to our current scope + // Sync to our current scope. EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut); - // Push if we need to ShouldPush |= Member && EliminationStack.empty(); if (ShouldPush) { EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut); @@ -1743,16 +1750,16 @@ } // If we get to this point, and the stack is empty we must have a use - // with nothing we can use to eliminate it, just skip it + // with nothing we can use to eliminate it, just skip it. if (EliminationStack.empty()) continue; - // Skip the Value's, we only want to eliminate on their uses + // Skip the Value's, we only want to eliminate on their uses. if (Member) continue; Value *Result = EliminationStack.back(); - // Don't replace our existing users with ourselves + // Don't replace our existing users with ourselves. if (MemberUse->get() == Result) continue; @@ -1761,8 +1768,8 @@ << "\n"); // If we replaced something in an instruction, handle the patching of - // metadata - if (Instruction *ReplacedInst = + // metadata. + if (auto *ReplacedInst = dyn_cast(MemberUse->get())) patchReplacementInstruction(ReplacedInst, Result); @@ -1772,7 +1779,8 @@ } } } - // Cleanup the congruence class + + // Cleanup the congruence class. SmallPtrSet MembersLeft; for (auto MI = CC->Members.begin(), ME = CC->Members.end(); MI != ME;) { auto CurrIter = MI; @@ -1783,7 +1791,7 @@ continue; } - if (Instruction *MemberInst = dyn_cast(Member)) { + if (auto *MemberInst = dyn_cast(Member)) { if (isInstructionTriviallyDead(MemberInst)) { // TODO: Don't mark loads of undefs. markInstructionForDeletion(MemberInst); Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -43,6 +43,7 @@ initializeDSELegacyPassPass(Registry); initializeGuardWideningLegacyPassPass(Registry); initializeGVNLegacyPassPass(Registry); + initializeNewGVNPass(Registry); initializeEarlyCSELegacyPassPass(Registry); initializeEarlyCSEMemSSALegacyPassPass(Registry); initializeGVNHoistLegacyPassPass(Registry); @@ -126,6 +127,10 @@ unwrap(PM)->add(createGVNPass()); } +void LLVMAddNewGVNPass(LLVMPassManagerRef PM) { + unwrap(PM)->add(createNewGVNPass()); +} + void LLVMAddMergedLoadStoreMotionPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createMergedLoadStoreMotionPass()); }