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 @@ -247,6 +247,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 @@ -165,6 +165,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 @@ -341,6 +341,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 =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/GVNExpression.h @@ -0,0 +1,583 @@ +//===- GVNExpression.h - GVN Expression classes -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// The header file for the GVN pass that contains expression handling +/// 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" +#include "llvm/IR/Value.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/ArrayRecycler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include + +namespace llvm { +class MemoryAccess; + +namespace GVNExpression { + +enum ExpressionType { + ExpressionTypeBase, + ExpressionTypeConstant, + ExpressionTypeVariable, + ExpressionTypeBasicStart, + ExpressionTypeBasic, + ExpressionTypeCall, + ExpressionTypeAggregateValue, + ExpressionTypePhi, + ExpressionTypeLoad, + ExpressionTypeStore, + ExpressionTypeBasicEnd +}; +class Expression { + +private: + void operator=(const Expression &) = delete; + Expression(const Expression &) = delete; + +protected: + ExpressionType EType; + unsigned int Opcode; + +public: + unsigned int getOpcode() const { return Opcode; } + + void setOpcode(unsigned int 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; } + + Expression(unsigned int o = ~2U) + : EType(ExpressionTypeBase), Opcode(o) {} + Expression(ExpressionType etype, unsigned int o = ~2U) + : EType(etype), Opcode(o) {} + + virtual ~Expression() {} + + 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 + if (getExpressionType() != ExpressionTypeLoad && + getExpressionType() != ExpressionTypeStore && + getExpressionType() != Other.getExpressionType()) + return false; + + return equals(Other); + } + + virtual bool equals(const Expression &other) const { return true; } + + virtual hash_code getHashValue() const { + return hash_combine(EType, Opcode); + } + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "etype = " << EType << ","; + OS << "opcode = " << Opcode << ", "; + } + + void print(raw_ostream &OS) const { + OS << "{ "; + printInternal(OS, true); + OS << "}"; + } + void dump() const { print(dbgs()); } +}; +inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) { + E.print(OS); + return OS; +} + +class BasicExpression : public Expression { +private: + void operator=(const BasicExpression &) = delete; + BasicExpression(const BasicExpression &) = delete; + BasicExpression() = delete; + typedef ArrayRecycler RecyclerType; + typedef RecyclerType::Capacity RecyclerCapacity; + +protected: + Value **Operands; + unsigned int MaxOperands; + unsigned int NumOperands; + Type *ValueType; + +public: + typedef Value **op_iterator; + typedef Value *const *const_ops_iterator; + + /// \brief Swap two operands. Used during GVN to put commutative operands in + /// order. + inline void swapOperands(unsigned First, unsigned Second) { + std::swap(Operands[First], Operands[Second]); + } + inline 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) { + assert(Operands && "Operands not allocated before setting"); + assert(N < NumOperands && "Operand out of range"); + Operands[N] = V; + } + inline unsigned int 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() { + return iterator_range(ops_begin(), ops_end()); + } + + inline iterator_range operands() const { + return iterator_range(ops_begin(), ops_end()); + } + + inline 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; } + + /// 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) { + ExpressionType et = EB->getExpressionType(); + return et > ExpressionTypeBasicStart && et < ExpressionTypeBasicEnd; + } + + void allocateOperands(RecyclerType &Recycler, BumpPtrAllocator &Allocator) { + assert(!Operands && "Operands already allocated"); + Operands = Recycler.allocate(RecyclerCapacity::get(MaxOperands), Allocator); + } + void deallocateOperands(RecyclerType &Recycler) { + Recycler.deallocate(RecyclerCapacity::get(MaxOperands), Operands); + } + + void setType(Type *T) { ValueType = T; } + + Type *getType() const { return ValueType; } + + BasicExpression(unsigned int NumOperands) + : BasicExpression(NumOperands, ExpressionTypeBasic) {} + BasicExpression(unsigned int NumOperands, ExpressionType ET) + : Expression(ET), Operands(nullptr), MaxOperands(NumOperands), + NumOperands(0), ValueType(nullptr) {} + + virtual ~BasicExpression() {} + + virtual bool equals(const Expression &Other) const { + const BasicExpression &OE = cast(Other); + if (Opcode != OE.Opcode) + return false; + if (ValueType != OE.ValueType) + return false; + if (NumOperands != OE.NumOperands) + return false; + if (!std::equal(ops_begin(), ops_end(), OE.ops_begin())) + return false; + return true; + } + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "ExpressionTypeBasic, "; + + this->Expression::printInternal(OS, false); + OS << "operands = {"; + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + OS << "[" << i << "] = "; + Operands[i]->printAsOperand(OS); + OS << " "; + } + OS << "} "; + } + + virtual hash_code getHashValue() const { + return hash_combine(EType, Opcode, ValueType, + hash_combine_range(ops_begin(), ops_end())); + } +}; +class CallExpression final : public BasicExpression { +private: + void operator=(const CallExpression &) = delete; + CallExpression(const CallExpression &) = delete; + CallExpression() = delete; + +protected: + CallInst *Call; + 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) { + return EB->getExpressionType() == ExpressionTypeCall; + } + CallExpression(unsigned int NumOperands, CallInst *C, MemoryAccess *DA) + : BasicExpression(NumOperands, ExpressionTypeCall), Call(C), + DefiningAccess(DA) {} + + virtual ~CallExpression() {} + + virtual bool equals(const Expression &Other) const { + if (!this->BasicExpression::equals(Other)) + return false; + const CallExpression &OE = cast(Other); + if (DefiningAccess != OE.DefiningAccess) + return false; + return true; + } + + virtual hash_code getHashValue() const { + return hash_combine(this->BasicExpression::getHashValue(), DefiningAccess); + } + + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "ExpressionTypeCall, "; + this->BasicExpression::printInternal(OS, false); + OS << " represents call at " << Call; + } +}; +class LoadExpression : public BasicExpression { +private: + void operator=(const LoadExpression &) = delete; + LoadExpression(const LoadExpression &) = delete; + LoadExpression() = delete; + +protected: + LoadInst *Load; + MemoryAccess *DefiningAccess; + unsigned Alignment; + + LoadExpression(enum ExpressionType EType, unsigned int NumOperands, + LoadInst *L, MemoryAccess *DA) + : BasicExpression(NumOperands, EType), Load(L), DefiningAccess(DA) { + Alignment = L ? L->getAlignment() : 0; + } + +public: + LoadInst *getLoadInst() const { return Load; } + void setLoadInst(LoadInst *L) { Load = L; } + + MemoryAccess *getDefiningAccess() const { return DefiningAccess; } + void setDefiningAccess(MemoryAccess *MA) { DefiningAccess = MA; } + 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) { + return EB->getExpressionType() == ExpressionTypeLoad; + } + + LoadExpression(unsigned int NumOperands, LoadInst *L, MemoryAccess *DA) + : LoadExpression(ExpressionTypeLoad, NumOperands, L, DA) {} + + virtual ~LoadExpression() {} + + virtual bool equals(const Expression &Other) const; + + virtual hash_code getHashValue() const { + return hash_combine(Opcode, ValueType, DefiningAccess, + hash_combine_range(ops_begin(), ops_end())); + } + + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "ExpressionTypeLoad, "; + this->BasicExpression::printInternal(OS, false); + OS << " represents Load at " << Load; + OS << " with DefiningAccess " << DefiningAccess; + } +}; + +class StoreExpression final : public BasicExpression { +private: + void operator=(const StoreExpression &) = delete; + StoreExpression(const StoreExpression &) = delete; + StoreExpression() = delete; + +protected: + StoreInst *Store; + MemoryAccess *DefiningAccess; + +public: + 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) { + return EB->getExpressionType() == ExpressionTypeStore; + } + StoreExpression(unsigned int NumOperands, StoreInst *S, MemoryAccess *DA) + : BasicExpression(NumOperands, ExpressionTypeStore), Store(S), + DefiningAccess(DA) {} + + virtual ~StoreExpression() {} + + virtual bool equals(const Expression &Other) const; + + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "ExpressionTypeStore, "; + this->BasicExpression::printInternal(OS, false); + OS << " represents Store at " << Store; + } + + virtual hash_code getHashValue() const { + return hash_combine(Opcode, ValueType, DefiningAccess, + hash_combine_range(ops_begin(), ops_end())); + } +}; + +class AggregateValueExpression final : public BasicExpression { +private: + void operator=(const AggregateValueExpression &) = delete; + AggregateValueExpression(const AggregateValueExpression &) = delete; + AggregateValueExpression() = delete; + + unsigned int MaxIntOperands; + unsigned int NumIntOperands; + unsigned int *IntOperands; + +public: + typedef unsigned int *int_arg_iterator; + typedef const unsigned int *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 { + 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) { + 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) { + return EB->getExpressionType() == ExpressionTypeAggregateValue; + } + + AggregateValueExpression(unsigned int NumOperands, + unsigned int NumIntOperands) + : BasicExpression(NumOperands, ExpressionTypeAggregateValue), + MaxIntOperands(NumIntOperands), NumIntOperands(0), + IntOperands(nullptr) {} + + virtual ~AggregateValueExpression() {} + virtual void allocateIntOperands(BumpPtrAllocator &Allocator) { + assert(!IntOperands && "Operands already allocated"); + IntOperands = Allocator.Allocate(MaxIntOperands); + } + + virtual bool equals(const Expression &Other) const { + if (!this->BasicExpression::equals(Other)) + return false; + const AggregateValueExpression &OE = cast(Other); + if (NumIntOperands != OE.NumIntOperands) + return false; + if (!std::equal(int_ops_begin(), int_ops_end(), OE.int_ops_begin())) + return false; + + return true; + } + + virtual hash_code getHashValue() const { + return hash_combine(this->BasicExpression::getHashValue(), + hash_combine_range(int_ops_begin(), int_ops_end())); + } + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "ExpressionTypeAggregateValue, "; + this->BasicExpression::printInternal(OS, false); + OS << ", intoperands = {"; + for (unsigned i = 0, e = int_ops_size(); i != e; ++i) { + OS << "[" << i << "] = " << IntOperands[i] << " "; + } + OS << "}"; + } +}; + +class PHIExpression : 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) { + return EB->getExpressionType() == ExpressionTypePhi; + } + BasicBlock *getBB() const { return BB; } + + void setBB(BasicBlock *bb) { BB = bb; } + + virtual bool equals(const Expression &Other) const { + if (!this->BasicExpression::equals(Other)) + return false; + const PHIExpression &OE = cast(Other); + if (BB != OE.BB) + return false; + return true; + } + + PHIExpression(unsigned int NumOperands, BasicBlock *B) + : BasicExpression(NumOperands, ExpressionTypePhi), BB(B) {} + + virtual ~PHIExpression() {} + + virtual hash_code getHashValue() const { + return hash_combine(this->BasicExpression::getHashValue(), BB); + } + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "ExpressionTypePhi, "; + this->BasicExpression::printInternal(OS, false); + OS << "bb = " << BB; + } + +private: + void operator=(const PHIExpression &) = delete; + PHIExpression(const PHIExpression &) = delete; + PHIExpression() = delete; + BasicBlock *BB; +}; +class VariableExpression : 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) { + return EB->getExpressionType() == ExpressionTypeVariable; + } + + Value *getVariableValue() const { return VariableValue; } + void setVariableValue(Value *V) { VariableValue = V; } + virtual bool equals(const Expression &Other) const { + const VariableExpression &OC = cast(Other); + if (VariableValue != OC.VariableValue) + return false; + return true; + } + + VariableExpression(Value *V) + : Expression(ExpressionTypeVariable), VariableValue(V) {} + virtual hash_code getHashValue() const { + return hash_combine(EType, VariableValue->getType(), VariableValue); + } + + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "ExpressionTypeVariable, "; + this->Expression::printInternal(OS, false); + OS << " variable = " << *VariableValue; + } + +private: + void operator=(const VariableExpression &) = delete; + VariableExpression(const VariableExpression &) = delete; + VariableExpression() = delete; + + Value *VariableValue; +}; +class ConstantExpression : 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) { + return EB->getExpressionType() == ExpressionTypeConstant; + } + Constant *getConstantValue() const { return ConstantValue; } + + void setConstantValue(Constant *V) { ConstantValue = V; } + virtual bool equals(const Expression &Other) const { + const ConstantExpression &OC = cast(Other); + if (ConstantValue != OC.ConstantValue) + return false; + return true; + } + + ConstantExpression() + : Expression(ExpressionTypeConstant), ConstantValue(NULL) {} + + ConstantExpression(Constant *constantValue) + : Expression(ExpressionTypeConstant), ConstantValue(constantValue) {} + virtual hash_code getHashValue() const { + return hash_combine(EType, ConstantValue->getType(), ConstantValue); + } + virtual void printInternal(raw_ostream &OS, bool printEType) const { + if (printEType) + OS << "ExpressionTypeConstant, "; + this->Expression::printInternal(OS, false); + OS << " constant = " << *ConstantValue; + } + +private: + void operator=(const ConstantExpression &) = delete; + ConstantExpression(const ConstantExpression &) = delete; + + Constant *ConstantValue; +}; + +bool LoadExpression::equals(const Expression &Other) const { + if (!isa(Other) && !isa(Other)) + return false; + if (!this->BasicExpression::equals(Other)) + return false; + if (const LoadExpression *OtherL = dyn_cast(&Other)) { + if (DefiningAccess != OtherL->getDefiningAccess()) + return false; + } else if (const StoreExpression *OtherS = + dyn_cast(&Other)) { + if (DefiningAccess != OtherS->getDefiningAccess()) + return false; + } + + return true; +} +bool StoreExpression::equals(const Expression &Other) const { + if (!isa(Other) && !isa(Other)) + return false; + if (!this->BasicExpression::equals(Other)) + return false; + if (const LoadExpression *OtherL = dyn_cast(&Other)) { + if (DefiningAccess != OtherL->getDefiningAccess()) + return false; + } else if (const StoreExpression *OtherS = + dyn_cast(&Other)) { + if (DefiningAccess != OtherS->getDefiningAccess()) + return false; + } + + return true; +} +} +} + +#endif Index: include/llvm/Transforms/Scalar/NewGVN.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/NewGVN.h @@ -0,0 +1,30 @@ +//===- NewGVN.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_NEWGVN_H +#define LLVM_TRANSFORMS_SCALAR_NEWGVN_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { +class NewGVNPass : public PassInfoMixin { +public: + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, AnalysisManager &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_NEWGVN_H + Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -38,6 +38,7 @@ MemCpyOptimizer.cpp MergedLoadStoreMotion.cpp NaryReassociate.cpp + NewGVN.cpp PartiallyInlineLibCalls.cpp PlaceSafepoints.cpp Reassociate.cpp Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- /dev/null +++ lib/Transforms/Scalar/NewGVN.cpp @@ -0,0 +1,1800 @@ +//===- GVN.cpp - Eliminate redundant values and loads ---------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs global value numbering to eliminate fully redundant +// instructions. It also performs simple dead load elimination. +// +// Note that this pass does the value numbering itself; it does not use the +// ValueNumbering analysis passes. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/NewGVN.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/Hashing.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SparseBitVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/TinyPtrVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/CFG.h" +#include "llvm/Analysis/CFGPrinter.h" +#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/PHITransAddr.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/IR/PredIteratorCache.h" +#include "llvm/IR/Type.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVNExpression.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/MemorySSA.h" +#include "llvm/Transforms/Utils/SSAUpdater.h" +#include +#include +#include +using namespace llvm; +using namespace PatternMatch; +using namespace llvm::GVNExpression; + +#define DEBUG_TYPE "newgvn" + +STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted"); +STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted"); +STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified"); +STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same"); + +//===----------------------------------------------------------------------===// +// GVN Pass +//===----------------------------------------------------------------------===// + +// Congruence classes represent the set of expressions/instructions +// that are all the same *during some scope in the function*. +// That is, because of the way we perform equality propagation, and +// because of memory value numbering, it is not correct to assume +// you can willy-nilly replace any member with any other at any +// point in the function. +// +// For any Value in the Member set, it is valid to replace any dominated member +// with that Value. +// +// Every congruence class has a leader, and the leader is used to +// symbolize instructions in a canonical way (IE every operand of an +// instruction that is a member of the same congruence class will +// always be replaced with leader during symbolization). +// To simplify symbolization, we keep the leader as a constant if class can be +// proved to be a constant value. +// Otherwise, the leader is a randomly chosen member of the value set, it does +// not matter which one is chosen. +// Each congruence class also has a defining expression, +// though the expression may be null. If it exists, it can be used for forward +// propagation and reassociation of values. +// +struct CongruenceClass { + typedef SmallPtrSet MemberSet; + unsigned int ID; + // Representative leader + Value *RepLeader; + // Defining Expression + const Expression *DefiningExpr; + // Actual members of this class. These are the things the same everywhere + 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) + : ID(ID), RepLeader(0), DefiningExpr(0), Dead(false) {} + CongruenceClass(unsigned int ID, Value *Leader, const Expression *E) + : ID(ID), RepLeader(Leader), DefiningExpr(E), Dead(false) {} +}; + +namespace llvm { + template <> struct DenseMapInfo { + static inline const Expression *getEmptyKey() { + uintptr_t Val = static_cast(-1); + Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; + return reinterpret_cast(Val); + } + static inline const Expression *getTombstoneKey() { + uintptr_t Val = static_cast(-2); + Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; + return reinterpret_cast(Val); + } + static unsigned getHashValue(const Expression *V) { + return static_cast(V->getHashValue()); + } + static bool isEqual(const Expression *LHS, const Expression *RHS) { + if (LHS == RHS) + return true; + if (LHS == getTombstoneKey() || RHS == getTombstoneKey() || + LHS == getEmptyKey() || RHS == getEmptyKey()) + return false; + return *LHS == *RHS; + } + }; +} // end namespace llvm + +class NewGVN : public FunctionPass { + DominatorTree *DT; + const DataLayout *DL; + const TargetLibraryInfo *TLI; + AssumptionCache *AC; + AliasAnalysis *AA; + MemorySSA *MSSA; + MemorySSAWalker *MSSAWalker; + BumpPtrAllocator ExpressionAllocator; + ArrayRecycler ArgRecycler; + + // Congruence class info + CongruenceClass *InitialClass; + std::vector CongruenceClasses; + unsigned int NextCongruenceNum = 0; + + // Value Mappings + DenseMap ValueToClass; + DenseMap ValueToExpression; + + // Expression to class mapping + typedef DenseMap ExpressionClassMap; + ExpressionClassMap ExpressionToClass; + + // Which values have changed as a result of leader changes + SmallPtrSet ChangedValues; + + // Reachability info + typedef BasicBlockEdge BlockEdge; + DenseSet ReachableEdges; + SmallPtrSet ReachableBlocks; + + // This is a bitvector because, on larger functions, we may have + // thousands of touched instructions at once (entire blocks, + // instructions with hundreds of uses, etc). Even with optimization + // for when we mark whole blocks as touched, when this was a + // SmallPtrSet or DenseSet, for some functions, we spent >20% of all + // the time in GVN just managing this list. The bitvector, on the + // other hand, efficiently supports test/set/clear of both + // 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 + DenseMap ProcessedCount; + + // DFS info + DenseMap> DFSDomMap; + DenseMap InstrDFS; + std::vector DFSToInstr; + + // Deletion info + SmallPtrSet InstructionsToErase; + +public: + static char ID; // Pass identification, replacement for typeid + explicit NewGVN() : FunctionPass(ID) { + initializeNewGVNPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override; + bool runGVN(Function &F, DominatorTree *DT, AssumptionCache *AC, + TargetLibraryInfo *TLI, AliasAnalysis *AA, + MemorySSA *MSSA); + +private: + // This transformation requires dominator postdominator info + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + + AU.addPreserved(); + AU.addPreserved(); + } + + // expression handling + const Expression *createExpression(Instruction *, const BasicBlock *); + const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *, + const BasicBlock *); + bool setBasicExpressionInfo(Instruction *, BasicExpression *, + const BasicBlock *); + PHIExpression *createPHIExpression(Instruction *); + const VariableExpression *createVariableExpression(Value *); + const ConstantExpression *createConstantExpression(Constant *); + const Expression *createVariableOrConstant(Value *V, const BasicBlock *B); + const StoreExpression *createStoreExpression(StoreInst *, MemoryAccess *, + const BasicBlock *); + LoadExpression *createLoadExpression(Type *, Value *, LoadInst *, + MemoryAccess *, const BasicBlock *); + + const CallExpression *createCallExpression(CallInst *, MemoryAccess *, + const BasicBlock *); + const AggregateValueExpression * + createAggregateValueExpression(Instruction *, const BasicBlock *); + + // Congruence class handling + CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) { + CongruenceClass *result = + new CongruenceClass(NextCongruenceNum++, Leader, E); + CongruenceClasses.emplace_back(result); + return result; + } + + CongruenceClass *createSingletonCongruenceClass(Value *Member) { + CongruenceClass *CClass = createCongruenceClass(Member, NULL); + CClass->Members.insert(Member); + ValueToClass[Member] = CClass; + return CClass; + } + void initializeCongruenceClasses(Function &F); + + // Symbolic evaluation + const Expression *checkSimplificationResults(Expression *, Instruction *, + Value *); + const Expression *performSymbolicEvaluation(Value *, const BasicBlock *); + const Expression *performSymbolicLoadEvaluation(Instruction *, + const BasicBlock *); + const Expression *performSymbolicStoreEvaluation(Instruction *, + const BasicBlock *); + const Expression *performSymbolicCallEvaluation(Instruction *, + const BasicBlock *); + const Expression *performSymbolicPHIEvaluation(Instruction *, + const BasicBlock *); + const Expression *performSymbolicAggrValueEvaluation(Instruction *, + const BasicBlock *); + + // 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 + void updateReachableEdge(BasicBlock *, BasicBlock *); + void processOutgoingEdges(TerminatorInst *, BasicBlock *); + bool isOnlyReachableViaThisEdge(const BasicBlockEdge &); + Value *findConditionEquivalence(Value *, BasicBlock *) const; + + // Elimination + struct ValueDFS; + void convertDenseToDFSOrdered(CongruenceClass::MemberSet &, + std::vector &); + + bool eliminateInstructions(Function &); + void replaceInstruction(Instruction *, Value *); + void markInstructionForDeletion(Instruction *); + void deleteInstructionsInBlock(BasicBlock *); + + // New instruction creation + void handleNewInstruction(Instruction *){}; + void markUsersTouched(Value *); + + // Utilities + void cleanupTables(); + std::pair assignDFSNumbers(BasicBlock *, unsigned); + void updateProcessedCount(Value *V); +}; + +char NewGVN::ID = 0; + +// createGVNPass - The public interface to this file... +FunctionPass *llvm::createNewGVNPass() { return new NewGVN(); } + +#ifndef NDEBUG +static std::string getBlockName(const BasicBlock *B) { + return DOTGraphTraits::getSimpleNodeLabel(B, NULL); +} +#endif + +INITIALIZE_PASS_BEGIN(NewGVN, "newgvn", "Global Value Numbering", false, false) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) +INITIALIZE_PASS_END(NewGVN, "newgvn", "Global Value Numbering", false, false) +PHIExpression *NewGVN::createPHIExpression(Instruction *I) { + BasicBlock *PhiBlock = I->getParent(); + PHINode *PN = cast(I); + PHIExpression *E = new (ExpressionAllocator) + PHIExpression(PN->getNumOperands(), I->getParent()); + + E->allocateOperands(ArgRecycler, ExpressionAllocator); + E->setType(I->getType()); + E->setOpcode(I->getOpcode()); + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { + BasicBlock *B = PN->getIncomingBlock(i); + if (!ReachableBlocks.count(B)) { + DEBUG(dbgs() << "Skipping unreachable block " << getBlockName(B) + << " in PHI node " << *PN << "\n"); + continue; + } + if (I->getOperand(i) != I) { + const BasicBlockEdge BBE(B, PhiBlock); + auto Operand = lookupOperandLeader(I->getOperand(i), I, BBE); + E->ops_push_back(Operand); + } else { + E->ops_push_back(I->getOperand(i)); + } + } + return E; +} + +// Set basic expression info (Arguments, type, opcode) for Expression +// 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)) + E->setType(GEP->getSourceElementType()); + else + E->setType(I->getType()); + E->setOpcode(I->getOpcode()); + E->allocateOperands(ArgRecycler, ExpressionAllocator); + + for (auto &O : I->operands()) { + auto Operand = lookupOperandLeader(O, I, B); + if (!isa(Operand)) + AllConstant = false; + E->ops_push_back(Operand); + } + return AllConstant; +} + +const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T, + Value *Arg1, Value *Arg2, + const BasicBlock *B) { + BasicExpression *E = new (ExpressionAllocator) BasicExpression(2); + + E->setType(T); + E->setOpcode(Opcode); + E->allocateOperands(ArgRecycler, ExpressionAllocator); + if (Instruction::isCommutative(Opcode)) { + // Ensure that commutative instructions that only differ by a permutation + // of their operands get the same value number by sorting the operand value + // numbers. Since all commutative instructions have two operands it is more + // efficient to sort by hand rather than using, say, std::sort. + if (Arg1 > Arg2) + std::swap(Arg1, Arg2); + } + auto BinaryLeader = lookupOperandLeader(Arg1, nullptr, B); + E->ops_push_back(BinaryLeader); + BinaryLeader = lookupOperandLeader(Arg2, nullptr, B); + E->ops_push_back(BinaryLeader); + + Value *V = SimplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), *DL, TLI, + DT, AC); + if (const Expression *SimplifiedE = checkSimplificationResults(E, nullptr, V)) + return SimplifiedE; + return E; +} + +// Take a Value returned by simplification of Expression E/Instruction +// I, and see if it resulted in a simpler expression. If so, return +// that expression +// TODO: Once finished, this should not take an Instruction, we only +// use it for printing +const Expression *NewGVN::checkSimplificationResults(Expression *E, + Instruction *I, Value *V) { + if (!V) + return NULL; + if (Constant *C = dyn_cast(V)) { +#ifndef NDEBUG + if (I) + DEBUG(dbgs() << "Simplified " << *I << " to " + << " constant " << *C << "\n"); +#endif + NumGVNOpsSimplified++; + assert(isa(E) && + "We should always have had a basic expression here"); + + cast(E)->deallocateOperands(ArgRecycler); + ExpressionAllocator.Deallocate(E); + return createConstantExpression(C); + } else if (isa(V) || isa(V)) { +#ifndef NDEBUG + if (I) + DEBUG(dbgs() << "Simplified " << *I << " to " + << " variable " << *V << "\n"); +#endif + cast(E)->deallocateOperands(ArgRecycler); + ExpressionAllocator.Deallocate(E); + return createVariableExpression(V); + } + + CongruenceClass *CC = ValueToClass.lookup(V); + if (CC && CC->DefiningExpr) { +#ifndef NDEBUG + if (I) + DEBUG(dbgs() << "Simplified " << *I << " to " + << " expression " << *V << "\n"); + +#endif + NumGVNOpsSimplified++; + assert(isa(E) && + "We should always have had a basic expression here"); + cast(E)->deallocateOperands(ArgRecycler); + ExpressionAllocator.Deallocate(E); + return CC->DefiningExpr; + } + return NULL; +} + +const Expression *NewGVN::createExpression(Instruction *I, + const BasicBlock *B) { + + BasicExpression *E = + new (ExpressionAllocator) BasicExpression(I->getNumOperands()); + + bool AllConstant = setBasicExpressionInfo(I, E, B); + + 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 + // numbers. Since all commutative instructions have two operands it is more + // efficient to sort by hand rather than using, say, std::sort. + assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!"); + if (E->getOperand(0) > E->getOperand(1)) + E->swapOperands(0, 1); + } + + // Perform simplificaiton + // TODO: Right now we only check to see if we get a constant result. + // We may get a less than constant, but still better, result for + // some operations. + // IE + // add 0, x -> x + // and x, x -> x + // We should handle this by simply rewriting the expression. + if (CmpInst *CI = dyn_cast(I)) { + // Sort the operand value numbers so xx get the same value + // number. + CmpInst::Predicate Predicate = CI->getPredicate(); + if (E->getOperand(0) > E->getOperand(1)) { + E->swapOperands(0, 1); + Predicate = CmpInst::getSwappedPredicate(Predicate); + } + E->setOpcode((CI->getOpcode() << 8) | Predicate); + // TODO: 25% of our time is spent in SimplifyCmpInst with pointer operands + // TODO: Since we noop bitcasts, we may need to check types before + // simplifying, so that we don't end up simplifying based on a wrong + // type assumption. We should clean this up so we can use constants of the + // wrong type + + assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() && + "Wrong types on cmp instruction"); + if ((E->getOperand(0)->getType() == I->getOperand(0)->getType() && + E->getOperand(1)->getType() == I->getOperand(1)->getType())) { + Value *V = SimplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), + *DL, TLI, DT, AC); + if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) + return SimplifiedE; + } + + } else if (isa(I)) { + if (isa(E->getOperand(0)) || + (E->getOperand(1)->getType() == I->getOperand(1)->getType() && + E->getOperand(2)->getType() == I->getOperand(2)->getType())) { + Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1), + E->getOperand(2), *DL, TLI, DT, AC); + if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) + return SimplifiedE; + } + } else if (I->isBinaryOp()) { + Value *V = SimplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), + *DL, TLI, DT, AC); + if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) + return SimplifiedE; + } else if (BitCastInst *BI = dyn_cast(I)) { + Value *V = SimplifyInstruction(BI, *DL, TLI, DT, AC); + if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) + return SimplifiedE; + } else if (isa(I)) { + Value *V = SimplifyGEPInst(E->getType(), + ArrayRef(E->ops_begin(), E->ops_end()), + *DL, TLI, DT, AC); + if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) + return SimplifiedE; + } else if (AllConstant) { + // We don't bother trying to simplify unless all of the operands + // 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) + + SmallVector C; + for (Value *Arg : E->operands()) + C.emplace_back(cast(Arg)); + + Value *V = ConstantFoldInstOperands(I, C, *DL, TLI); + if (V) { + if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) + return SimplifiedE; + } + } + return E; +} + +const AggregateValueExpression * +NewGVN::createAggregateValueExpression(Instruction *I, const BasicBlock *B) { + if (InsertValueInst *II = dyn_cast(I)) { + AggregateValueExpression *E = new (ExpressionAllocator) + AggregateValueExpression(I->getNumOperands(), II->getNumIndices()); + setBasicExpressionInfo(I, E, B); + E->allocateIntOperands(ExpressionAllocator); + + for (auto &Index : II->indices()) + E->int_ops_push_back(Index); + return E; + + } else if (ExtractValueInst *EI = dyn_cast(I)) { + AggregateValueExpression *E = new (ExpressionAllocator) + AggregateValueExpression(I->getNumOperands(), EI->getNumIndices()); + setBasicExpressionInfo(EI, E, B); + E->allocateIntOperands(ExpressionAllocator); + + for (auto &Index : EI->indices()) + E->int_ops_push_back(Index); + return E; + } + llvm_unreachable("Unhandled type of aggregate value operation"); +} + +const VariableExpression * +NewGVN::createVariableExpression(Value *V) { + VariableExpression *E = new (ExpressionAllocator) VariableExpression(V); + E->setOpcode(V->getValueID()); + return E; +} + +const Expression *NewGVN::createVariableOrConstant(Value *V, + const BasicBlock *B) { + auto Leader = lookupOperandLeader(V, nullptr, B); + if (Constant *C = dyn_cast(Leader)) + return createConstantExpression(C); + return createVariableExpression(Leader); +} + +const ConstantExpression * +NewGVN::createConstantExpression(Constant *C) { + ConstantExpression *E = new (ExpressionAllocator) ConstantExpression(C); + E->setOpcode(C->getValueID()); + return E; +} + +const CallExpression *NewGVN::createCallExpression(CallInst *CI, + MemoryAccess *HV, + const BasicBlock *B) { + CallExpression *E = + new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, HV); + setBasicExpressionInfo(CI, E, B); + return E; +} + +// lookupOperandLeader -- See if we have a congruence class and leader +// for this operand, and if so, return it. Otherwise, return the +// original operand. +template +Value *NewGVN::lookupOperandLeader(Value *V, const User *U, + const T &B) const { + CongruenceClass *CC = ValueToClass.lookup(V); + if (CC && (CC != InitialClass)) + return CC->RepLeader; + return V; +} + +LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp, + LoadInst *LI, MemoryAccess *DA, + const BasicBlock *B) { + 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 + E->setOpcode(0); + auto Operand = lookupOperandLeader(PointerOp, LI, B); + E->ops_push_back(Operand); + if (LI) + E->setAlignment(LI->getAlignment()); + + // 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) + return E; +} + +const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI, + MemoryAccess *DA, + const BasicBlock *B) { + StoreExpression *E = + 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 + 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) + return E; +} + +const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I, + const BasicBlock *B) { + StoreInst *SI = cast(I); + const Expression *E = createStoreExpression(SI, MSSA->getMemoryAccess(SI), B); + return E; +} + +const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I, + const BasicBlock *B) { + LoadInst *LI = cast(I); + + // We can eliminate in favor of non-simple loads, but we won't be able to + // eliminate them + if (!LI->isSimple()) + return nullptr; + + Value *LoadAddressLeader = + lookupOperandLeader(LI->getPointerOperand(), I, B); + // 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)) { + Instruction *DefiningInst = MD->getMemoryInst(); + // If the defining instruction is not reachable, replace with + // undef + if (!ReachableBlocks.count(DefiningInst->getParent())) + return createConstantExpression(UndefValue::get(LI->getType())); + } + } + + const Expression *E = createLoadExpression( + LI->getType(), LI->getPointerOperand(), LI, DefiningAccess, B); + return E; +} + +/// performSymbolicCallEvaluation - Evaluate read only and pure calls, and +/// create an expression result +const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I, + const BasicBlock *B) { + CallInst *CI = cast(I); + if (AA->doesNotAccessMemory(CI)) + return createCallExpression(CI, nullptr, B); + else if (AA->onlyReadsMemory(CI)) + return createCallExpression(CI, MSSAWalker->getClobberingMemoryAccess(CI), + B); + else + return nullptr; +} + +// performSymbolicPHIEvaluation - Evaluate PHI nodes symbolically, and +// create an expression result +const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I, + const BasicBlock *B) { + PHIExpression *E = cast(createPHIExpression(I)); + if (E->ops_empty()) { + DEBUG(dbgs() << "Simplified PHI node " << *I << " to undef" + << "\n"); + E->deallocateOperands(ArgRecycler); + ExpressionAllocator.Deallocate(E); + return createConstantExpression(UndefValue::get(I->getType())); + } + + Value *AllSameValue = E->getOperand(0); + + // See if all arguments are the same, ignoring undef arguments, because we can + // choose a value that is the same for them. + for (const Value *Arg : E->operands()) + if (Arg != AllSameValue && !isa(Arg)) { + AllSameValue = NULL; + break; + } + + 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 + // 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. + if (isa(AllSameValue)) + return E; + NumGVNPhisAllSame++; + DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue + << "\n"); + E->deallocateOperands(ArgRecycler); + ExpressionAllocator.Deallocate(E); + if (Constant *C = dyn_cast(AllSameValue)) + return createConstantExpression(C); + return createVariableExpression(AllSameValue); + } + return E; +} + +const Expression * +NewGVN::performSymbolicAggrValueEvaluation(Instruction *I, + const BasicBlock *B) { + if (ExtractValueInst *EI = dyn_cast(I)) { + IntrinsicInst *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 + // is we'll synthesize a semantically equivalent expression instead on + // an extract value expression. + switch (II->getIntrinsicID()) { + case Intrinsic::sadd_with_overflow: + case Intrinsic::uadd_with_overflow: + Opcode = Instruction::Add; + break; + case Intrinsic::ssub_with_overflow: + case Intrinsic::usub_with_overflow: + Opcode = Instruction::Sub; + break; + case Intrinsic::smul_with_overflow: + case Intrinsic::umul_with_overflow: + Opcode = Instruction::Mul; + break; + default: + break; + } + + if (Opcode != 0) { + // Intrinsic recognized. Grab its args to finish building the + // expression. + assert(II->getNumArgOperands() == 2 && + "Expect two args for recognised intrinsics."); + return createBinaryExpression(Opcode, EI->getType(), + II->getArgOperand(0), + II->getArgOperand(1), B); + } + } + } + + return createAggregateValueExpression(I, B); +} + +/// performSymbolicEvaluation - Substitute and symbolize the value +/// before value numbering +const Expression *NewGVN::performSymbolicEvaluation(Value *V, + const BasicBlock *B) { + const Expression *E = NULL; + if (Constant *C = dyn_cast(V)) + E = createConstantExpression(C); + else if (isa(V) || isa(V)) { + E = createVariableExpression(V); + } else { + // TODO: memory intrinsics + // TODO: Some day, we should do the forward propagation and reassociation + // parts of the algorithm. + Instruction *I = cast(V); + switch (I->getOpcode()) { + case Instruction::ExtractValue: + case Instruction::InsertValue: + E = performSymbolicAggrValueEvaluation(I, B); + break; + case Instruction::PHI: + E = performSymbolicPHIEvaluation(I, B); + break; + case Instruction::Call: + E = performSymbolicCallEvaluation(I, B); + break; + case Instruction::Store: + E = performSymbolicStoreEvaluation(I, B); + break; + case Instruction::Load: + E = performSymbolicLoadEvaluation(I, B); + break; + case Instruction::BitCast: { + E = createExpression(I, B); + } break; + + case Instruction::Add: + case Instruction::FAdd: + case Instruction::Sub: + case Instruction::FSub: + case Instruction::Mul: + case Instruction::FMul: + case Instruction::UDiv: + case Instruction::SDiv: + case Instruction::FDiv: + case Instruction::URem: + case Instruction::SRem: + case Instruction::FRem: + case Instruction::Shl: + case Instruction::LShr: + case Instruction::AShr: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + case Instruction::ICmp: + case Instruction::FCmp: + case Instruction::Trunc: + case Instruction::ZExt: + case Instruction::SExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::UIToFP: + case Instruction::SIToFP: + case Instruction::FPTrunc: + case Instruction::FPExt: + case Instruction::PtrToInt: + case Instruction::IntToPtr: + case Instruction::Select: + case Instruction::ExtractElement: + case Instruction::InsertElement: + case Instruction::ShuffleVector: + case Instruction::GetElementPtr: + E = createExpression(I, B); + break; + default: + return NULL; + } + } + if (!E) + return NULL; + 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'. +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. + const BasicBlock *Pred = E.getEnd()->getSinglePredecessor(); + const BasicBlock *Src = E.getStart(); + assert((!Pred || Pred == Src) && "No edge between these basic blocks!"); + (void)Src; + return Pred != nullptr; +} + +void NewGVN::markUsersTouched(Value *V) { + // Now mark the users as touched + for (auto &U : V->uses()) { + Instruction *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::performCongruenceFinding(Value *V, const Expression *E) { + + ValueToExpression[V] = E; + // This is guaranteed to return something, since it will at least find + // INITIAL + CongruenceClass *VClass = ValueToClass[V]; + assert(VClass && "Should have found a vclass"); + // 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 + if (E == NULL) { + // 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 + 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)) { + 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 (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)) + NewClass->RepLeader = CE->getConstantValue(); + else if (const VariableExpression *VE = dyn_cast(E)) + NewClass->RepLeader = VE->getVariableValue(); + else if (const StoreExpression *SE = dyn_cast(E)) + NewClass->RepLeader = SE->getStoreInst()->getValueOperand(); + else + NewClass->RepLeader = V; + + EClass = NewClass; + DEBUG(dbgs() << "Created new congruence class for " << *V + << " using expression " << *E << " at " << NewClass->ID + << "\n"); + DEBUG(dbgs() << "Hash value was " << E->getHashValue() << "\n"); + } else { + EClass = lookupResult.first->second; + assert(EClass && "Somehow don't have an eclass"); + + assert(!EClass->Dead && "We accidentally looked up a dead class"); + } + } + bool WasInChanged = ChangedValues.erase(V); + if (VClass != EClass || WasInChanged) { + DEBUG(dbgs() << "Found class " << EClass->ID << " for expression " << E + << "\n"); + + if (VClass != EClass) { + DEBUG(dbgs() << "New congruence class for " << V << " is " << EClass->ID + << "\n"); + + VClass->Members.erase(V); + EClass->Members.insert(V); + ValueToClass[V] = EClass; + // See if we destroyed the class or need to swap leaders + if (VClass->Members.empty() && VClass != InitialClass) { + if (VClass->DefiningExpr) { + VClass->Dead = true; + DEBUG(dbgs() << "Erasing expression " << *E << " from table\n"); + 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. + VClass->RepLeader = *(VClass->Members.begin()); + for (auto M : VClass->Members) { + if (Instruction *I = dyn_cast(M)) + TouchedInstructions.set(InstrDFS[I]); + ChangedValues.insert(M); + } + } + } + markUsersTouched(V); + } +} + +// updateReachableEdge - Process the fact that Edge (from, to) is +// reachable, including marking any newly reachable blocks and +// instructions for processing +void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) { + // 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 (ReachableBlocks.insert(To).second) { + DEBUG(dbgs() << "Block " << getBlockName(To) << " marked reachable\n"); + const auto &InstRange = BlockInstRange.lookup(To); + TouchedInstructions.set(InstRange.first, InstRange.second); + } else { + 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 + auto BI = To->begin(); + while (isa(BI)) { + TouchedInstructions.set(InstrDFS[&*BI]); + ++BI; + } + } + } +} + +// 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 *NewGVN::findConditionEquivalence(Value *Cond, BasicBlock *B) const { + auto Result = lookupOperandLeader(Cond, nullptr, B); + if (isa(Result)) + return Result; + return nullptr; +} + +// processOutgoingEdges - Process the outgoing edges of a block for +// reachability. +void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) { + // Evaluate Reachability of terminator instruction + // Conditional branch + 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)) { + const Expression *E = createExpression(I, B); + if (const ConstantExpression *CE = dyn_cast(E)) { + CondEvaluated = CE->getConstantValue(); + } + } else if (isa(Cond)) { + CondEvaluated = Cond; + } + } + ConstantInt *CI; + BasicBlock *TrueSucc = BR->getSuccessor(0); + BasicBlock *FalseSucc = BR->getSuccessor(1); + if (CondEvaluated && (CI = dyn_cast(CondEvaluated))) { + if (CI->isOne()) { + DEBUG(dbgs() << "Condition for Terminator " << *TI + << " evaluated to true\n"); + updateReachableEdge(B, TrueSucc); + } else if (CI->isZero()) { + DEBUG(dbgs() << "Condition for Terminator " << *TI + << " evaluated to false\n"); + updateReachableEdge(B, FalseSucc); + } + } else { + updateReachableEdge(B, TrueSucc); + updateReachableEdge(B, FalseSucc); + } + } else if (SwitchInst *SI = dyn_cast(TI)) { + // For switches, propagate the case values into the case + // destinations. + + // Remember how many outgoing edges there are to every successor. + SmallDenseMap SwitchEdges; + + 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 + if (CondEvaluated && isa(CondEvaluated)) { + ConstantInt *CondVal = cast(CondEvaluated); + // 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. + // We can't do anything other than mark the default dest as reachable, + // and go home. + updateReachableEdge(B, SI->getDefaultDest()); + return; + } + // Now get where it goes and mark it reachable + BasicBlock *TargetBlock = CaseVal.getCaseSuccessor(); + updateReachableEdge(B, TargetBlock); + unsigned WhichSucc = CaseVal.getSuccessorIndex(); + // Calculate whether our single reachable edge is really a single edge to + // the target block. If not, and the block has multiple predecessors, we + // can only replace phi node values. + for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { + if (i == WhichSucc) + continue; + BasicBlock *Block = SI->getSuccessor(i); + if (Block == TargetBlock) + MultipleEdgesOneReachable = true; + } + } else { + for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { + BasicBlock *TargetBlock = SI->getSuccessor(i); + ++SwitchEdges[TargetBlock]; + updateReachableEdge(B, TargetBlock); + } + } + } else { + // Otherwise this is either unconditional, or a type we have no + // 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); + } + } +} + +// The algorithm initially places the values of the routine in the INITIAL congruence +// class. The leader of INITIAL is the undetermined value `TOP`. +// When the algorithm has finished, values still in INITIAL are unreachable. +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 + CongruenceClass::MemberSet InitialValues; + for (auto &B : F) + for (auto &I : B) + InitialValues.insert(&I); + + InitialClass = createCongruenceClass(NULL, NULL); + for (auto L : InitialValues) + ValueToClass[L] = InitialClass; + 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); +} + +void NewGVN::cleanupTables() { +#ifndef NDEBUG + for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) { + DEBUG(dbgs() << "Congruence class " << CongruenceClasses[i]->ID << " has " + << CongruenceClasses[i]->Members.size() << " members\n"); + } +#endif + + ValueToClass.clear(); + ArgRecycler.clear(ExpressionAllocator); + ExpressionAllocator.Reset(); + CongruenceClasses.clear(); + ExpressionToClass.clear(); + ValueToExpression.clear(); + ReachableBlocks.clear(); + ReachableEdges.clear(); + ProcessedCount.clear(); + DFSDomMap.clear(); + InstrDFS.clear(); + InstructionsToErase.clear(); + + DFSToInstr.clear(); + BlockInstRange.clear(); + TouchedInstructions.clear(); + DominatedInstRange.clear(); +} + +std::pair NewGVN::assignDFSNumbers(BasicBlock *B, + unsigned Start) { + unsigned int 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); +} + +void NewGVN::updateProcessedCount(Value *V) { +#ifndef NDEBUG + if (ProcessedCount.count(V) == 0) { + ProcessedCount.insert({V, 1}); + } else { + ProcessedCount[V] += 1; + assert(ProcessedCount[V] < 100 && + "Seem to have processed the same Value a lot\n"); + } +#endif +} + +/// 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) { + bool Changed = false; + this->DT = DT; + this->AC = AC; + this->TLI = TLI; + this->AA = AA; + this->MSSA = MSSA; + DL = &F.getParent()->getDataLayout(); + MSSAWalker = MSSA->getWalker(); + + // Count number of instructions for sizing of hash tables, and come + // up with a global dfs numbering for instructions. + unsigned ICount = 0; + SmallPtrSet VisitedBlocks; + + // Note: We want RPO traversal of the blocks, which is not quite the same as + // dominator tree order, particularly with regard whether backedges get + // visited first or second, given a block with multiple successors. + // If we visit in the wrong order, we will end up performing N times as many + // iterations. + ReversePostOrderTraversal RPOT(&F); + for (auto &B : RPOT) { + VisitedBlocks.insert(B); + const auto &BlockRange = assignDFSNumbers(B, ICount); + BlockInstRange.insert({B, BlockRange}); + ICount += BlockRange.second - BlockRange.first; + } + + // Handle forward unreachable blocks and figure out which blocks + // have single preds + + for (auto &B : F) { + // Assign numbers to unreachable blocks + if (!VisitedBlocks.count(&B)) { + const auto &BlockRange = assignDFSNumbers(&B, ICount); + BlockInstRange.insert({&B, BlockRange}); + ICount += BlockRange.second - BlockRange.first; + } + } + + TouchedInstructions.resize(ICount + 1); + DominatedInstRange.reserve(F.size()); + // Ensure we don't end up resizing the expressionToClass map, as + // 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 + 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 + BasicBlock *LastBlock = &F.getEntryBlock(); + while (TouchedInstructions.any()) { + // 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 (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 (!BlockReachable) { + TouchedInstructions.reset(InstRange.first, InstRange.second); + DEBUG(dbgs() << "Skipping instructions in block " + << getBlockName(CurrBlock) + << " because it is unreachable\n"); + continue; + } + updateProcessedCount(CurrBlock); + } + DEBUG(dbgs() << "Processing instruction " << *I << "\n"); + if (I->use_empty() && !I->getType()->isVoidTy()) { + DEBUG(dbgs() << "Skipping unused instruction\n"); + if (isInstructionTriviallyDead(I, TLI)) + markInstructionForDeletion(I); + TouchedInstructions.reset(InstrNum); + continue; + } + updateProcessedCount(I); + + if (!I->isTerminator()) { + const Expression *Symbolized = performSymbolicEvaluation(I, CurrBlock); + performCongruenceFinding(I, Symbolized); + } else { + processOutgoingEdges(dyn_cast(I), CurrBlock); + } + // Reset after processing (because we may mark ourselves as touched when + // we propagate equalities) + TouchedInstructions.reset(InstrNum); + } + } + + Changed |= eliminateInstructions(F); + + // Delete all instructions marked for deletion. + for (Instruction *ToErase : InstructionsToErase) { + if (!ToErase->use_empty()) + ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType())); + + ToErase->eraseFromParent(); + } + + // Delete all unreachable blocks + for (auto &B : F) { + BasicBlock *BB = &B; + if (!ReachableBlocks.count(BB)) { + DEBUG(dbgs() << "We believe block " << getBlockName(BB) + << " is unreachable\n"); + deleteInstructionsInBlock(BB); + Changed = true; + } + } + + cleanupTables(); + return Changed; +} + +bool NewGVN::runOnFunction(Function &F) { + if (skipFunction(F)) + return false; + return runGVN(F, &getAnalysis().getDomTree(), + &getAnalysis().getAssumptionCache(F), + &getAnalysis().getTLI(), + &getAnalysis().getAAResults(), + &getAnalysis().getMSSA()); +} + +PreservedAnalyses NewGVNPass::run(Function &F, + AnalysisManager &AM) { + NewGVN Impl; + + // Apparently the order in which we get these results matter for + // the old GVN (see Chandler's comment in GVN.cpp). I'll keep + // the same order here, just in case. + auto &AC = AM.getResult(F); + auto &DT = AM.getResult(F); + auto &TLI = AM.getResult(F); + auto &AA = AM.getResult(F); + auto &MSSA = AM.getResult(F).getMSSA(); + bool Changed = Impl.runGVN(F, &DT, &AC, &TLI, &AA, &MSSA); + if (!Changed) + return PreservedAnalyses::all(); + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + return PA; +} + +// 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 +// TODO: Separate cost from availability + +static bool alwaysAvailable(Value *V) { + return isa(V) || isa(V); +} + +// Get the basic block from an instruction/value +static BasicBlock *getBlockForValue(Value *V) { + if (Instruction *I = dyn_cast(V)) + return I->getParent(); + return nullptr; +} +struct NewGVN::ValueDFS { + int DFSIn; + int DFSOut; + int LocalNum; + // Only one of these will be set + Value *Val; + Use *U; + ValueDFS() + : DFSIn(0), DFSOut(0), LocalNum(0), Val(nullptr), U(nullptr) {} + + 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 + // DFS (1, 3) + // Val 0 + // DFS (1, 2) + // Val 50 + // We want the second to be less than the first, but if we just go field + // by field, we will get to Val 0 < Val 50 and say the first is less than + // the second. We only want it to be less than if the DFS orders are equal. + + if (DFSIn < other.DFSIn) + return true; + else if (DFSIn == other.DFSIn) { + if (DFSOut < other.DFSOut) + return true; + else if (DFSOut == other.DFSOut) { + if (LocalNum < other.LocalNum) + return true; + else if (LocalNum == other.LocalNum) { + if (Val < other.Val) + return true; + if (U < other.U) + return true; + } + } + } + return false; + } +}; + +void NewGVN::convertDenseToDFSOrdered(CongruenceClass::MemberSet &Dense, + std::vector &DFSOrderedSet) { + for (auto D : Dense) { + // 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 + assert(BB || "Should have figured out a basic block for value"); + ValueDFS VD; + + std::pair DFSPair = DFSDomMap[BB]; + assert(DFSPair.first != -1 && DFSPair.second != -1 && "Invalid DFS Pair"); + 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)) + VD.LocalNum = InstrDFS[I]; + else + llvm_unreachable("Should have been an instruction"); + + DFSOrderedSet.emplace_back(VD); + + // Now add the users + for (auto &U : D->uses()) { + if (Instruction *I = dyn_cast(U.getUser())) { + ValueDFS VD; + // Put the phi node uses in the incoming block + BasicBlock *IBlock; + if (PHINode *P = dyn_cast(I)) { + IBlock = P->getIncomingBlock(U); + // Make phi node users appear last in the incoming block + // they are from. + VD.LocalNum = InstrDFS.size() + 1; + } else { + IBlock = I->getParent(); + VD.LocalNum = InstrDFS[I]; + } + std::pair DFSPair = DFSDomMap[IBlock]; + VD.DFSIn = DFSPair.first; + VD.DFSOut = DFSPair.second; + VD.U = &U; + DFSOrderedSet.emplace_back(VD); + } + } + } +} + +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); + + if (Op && ReplOp) + ReplOp->andIRFlags(Op); + + if (Instruction *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 + // 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. + 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) { + patchReplacementInstruction(I, Repl); + I->replaceAllUsesWith(Repl); +} + +void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) { + DEBUG(dbgs() << " BasicBlock Dead:" << *BB); + ++NumGVNBlocksDeleted; + + // Check to see if there are non-terminating instructions to delete. + if (isa(BB->begin())) + 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 + auto StartPoint = BB->rbegin(); + ++StartPoint; + // Note that we explicitly recalculate BB->rend() on each iteration, + // as it may change when we remove the first instruction. + for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) { + Instruction &Inst = *I++; + if (!Inst.use_empty()) + Inst.replaceAllUsesWith(UndefValue::get(Inst.getType())); + if (isa(Inst)) + continue; + + Inst.eraseFromParent(); + ++NumGVNInstrDeleted; + } +} + +void NewGVN::markInstructionForDeletion(Instruction *I) { + DEBUG(dbgs() << "Marking " << *I << " for deletion\n"); + InstructionsToErase.insert(I); +} + +void NewGVN::replaceInstruction(Instruction *I, Value *V) { + + DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n"); + patchAndReplaceAllUsesWith(I, V); + // We save the actual erasing to avoid invalidating memory + // dependencies until we are done with everything. + markInstructionForDeletion(I); +} + +namespace { +// 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(); } + std::pair dfs_back() const { return DFSStack.back(); } + + void push_back(Value *V, int DFSIn, int DFSOut) { + ValueStack.emplace_back(V); + DFSStack.emplace_back(DFSIn, DFSOut); + } + bool empty() const { return DFSStack.empty(); } + bool isInScope(int DFSIn, int DFSOut) const { + if (empty()) + return false; + return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second; + } + + void popUntilDFSScope(int DFSIn, int DFSOut) { + // These two should always be in sync at this point + assert(ValueStack.size() == DFSStack.size() && + "Mismatch between ValueStack and DFSStack"); + while ( + !DFSStack.empty() && + !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) { + DFSStack.pop_back(); + ValueStack.pop_back(); + } + } + +private: + SmallVector ValueStack; + SmallVector, 8> DFSStack; +}; +} + +bool NewGVN::eliminateInstructions(Function &F) { + // This is a non-standard eliminator. The normal way to eliminate is + // to walk the dominator tree in order, keeping track of available + // values, and eliminating them. However, this is mildly + // pointless. It requires doing lookups on every instruction, + // regardless of whether we will ever eliminate it. For + // instructions part of most singleton congruence class, we know we + // will never eliminate it. + + // Instead, this eliminator looks at the congruence classes directly, sorts + // them into a DFS ordering of the dominator tree, and then we just + // perform eliminate straight on the sets by walking the congruence + // class member uses in order, and eliminate the ones dominated by the + // last member. This is technically O(N log N) where N = number of + // instructions (since in theory all instructions may be in the same + // congruence class). + // When we find something not dominated, it becomes the new leader + // for elimination purposes + + bool AnythingReplaced = false; + + // 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)) { + for (auto II = S->begin(); isa(II); ++II) { + PHINode &Phi = cast(*II); + DEBUG(dbgs() << "Replacing incoming value of " << *II << " for block " + << getBlockName(&B) + << " with undef due to it being unreachable\n"); + for (auto &Operand : Phi.incoming_values()) + if (Phi.getIncomingBlock(Operand) == &B) + Operand.set(UndefValue::get(Phi.getType())); + } + } + } + DomTreeNode *Node = DT->getNode(&B); + if (Node) + DFSDomMap[&B] = {Node->getDFSNumIn(), Node->getDFSNumOut()}; + } + + 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) + if (CC == InitialClass || CC->Dead) + continue; + assert(CC->RepLeader && "We should have had a leader"); + + // If this is a leader that is always available, and it's a + // constant or has no equivalences, just replace everything with + // it. We then update the congruence class with whatever members + // are left. + if (alwaysAvailable(CC->RepLeader)) { + SmallPtrSet MembersLeft; + for (auto M : CC->Members) { + + Value *Member = M; + + // Void things have no uses we can replace + if (Member == CC->RepLeader || Member->getType()->isVoidTy()) { + MembersLeft.insert(Member); + continue; + } + + DEBUG(dbgs() << "Found replacement " << *(CC->RepLeader) << " for " + << *Member << "\n"); + // 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)) { + assert(CC->RepLeader != I && + "About to accidentally remove our leader"); + replaceInstruction(I, CC->RepLeader); + AnythingReplaced = true; + + continue; + } else { + MembersLeft.insert(I); + } + } + CC->Members.swap(MembersLeft); + + } else { + DEBUG(dbgs() << "Eliminating in congruence class " << CC->ID << "\n"); + // 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. + std::vector DFSOrderedSet; + convertDenseToDFSOrdered(CC->Members, DFSOrderedSet); + + // Sort the whole thing + sort(DFSOrderedSet.begin(), DFSOrderedSet.end()); + + for (auto &C : DFSOrderedSet) { + int MemberDFSIn = C.DFSIn; + int MemberDFSOut = C.DFSOut; + Value *Member = C.Val; + Use *MemberUse = C.U; + + // We ignore void things because we can't get a value from + // them. + if (Member && Member->getType()->isVoidTy()) + continue; + + if (EliminationStack.empty()) { + DEBUG(dbgs() << "Elimination Stack is empty\n"); + } else { + DEBUG(dbgs() << "Elimination Stack Top DFS numbers are (" + << EliminationStack.dfs_back().first << "," + << EliminationStack.dfs_back().second << ")\n"); + } + if (Member && isa(Member)) + assert(isa(CC->RepLeader)); + + DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << "," + << MemberDFSOut << ")\n"); + // 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) + // 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 + // Otherwise, we walk along, processing members who are + // 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 + EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut); + // Push if we need to + ShouldPush |= Member && EliminationStack.empty(); + if (ShouldPush) { + EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut); + } + } + + // 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 + if (EliminationStack.empty()) + continue; + + // 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 + if (MemberUse->get() == Result) + continue; + + DEBUG(dbgs() << "Found replacement " << *Result << " for " + << *MemberUse->get() << " in " << *(MemberUse->getUser()) + << "\n"); + + // If we replaced something in an instruction, handle the patching of + // metadata + if (Instruction *ReplacedInst = + dyn_cast(MemberUse->get())) + patchReplacementInstruction(ReplacedInst, Result); + + assert(isa(MemberUse->getUser())); + MemberUse->set(Result); + AnythingReplaced = true; + } + } + } + // Cleanup the congruence class + SmallPtrSet MembersLeft; + for (auto MI = CC->Members.begin(), ME = CC->Members.end(); MI != ME;) { + auto CurrIter = MI; + ++MI; + Value *Member = *CurrIter; + if (Member->getType()->isVoidTy()) { + MembersLeft.insert(Member); + continue; + } + + if (Instruction *MemberInst = dyn_cast(Member)) { + if (isInstructionTriviallyDead(MemberInst)) { + // TODO: Don't mark loads of undefs. + markInstructionForDeletion(MemberInst); + continue; + } + } + MembersLeft.insert(Member); + } + CC->Members.swap(MembersLeft); + } + + return AnythingReplaced; +} + 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); @@ -125,6 +126,10 @@ unwrap(PM)->add(createGVNPass()); } +void LLVMAddNewGVNPass(LLVMPassManagerRef PM) { + unwrap(PM)->add(createNewGVNPass()); +} + void LLVMAddMergedLoadStoreMotionPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createMergedLoadStoreMotionPass()); }