diff options
Diffstat (limited to 'llvm/include')
| -rw-r--r-- | llvm/include/llvm-c/Transforms/Scalar.h | 3 | ||||
| -rw-r--r-- | llvm/include/llvm/InitializePasses.h | 1 | ||||
| -rw-r--r-- | llvm/include/llvm/LinkAllPasses.h | 1 | ||||
| -rw-r--r-- | llvm/include/llvm/Transforms/Scalar.h | 7 | ||||
| -rw-r--r-- | llvm/include/llvm/Transforms/Scalar/GVNExpression.h | 551 | ||||
| -rw-r--r-- | llvm/include/llvm/Transforms/Scalar/NewGVN.h | 28 |
6 files changed, 591 insertions, 0 deletions
diff --git a/llvm/include/llvm-c/Transforms/Scalar.h b/llvm/include/llvm-c/Transforms/Scalar.h index e45a780c5a5..8991e090484 100644 --- a/llvm/include/llvm-c/Transforms/Scalar.h +++ b/llvm/include/llvm-c/Transforms/Scalar.h @@ -56,6 +56,9 @@ void LLVMAddMergedLoadStoreMotionPass(LLVMPassManagerRef PM); /** See llvm::createGVNPass function. */ void LLVMAddGVNPass(LLVMPassManagerRef PM); +/** See llvm::createGVNPass function. */ +void LLVMAddNewGVNPass(LLVMPassManagerRef PM); + /** See llvm::createIndVarSimplifyPass function. */ void LLVMAddIndVarSimplifyPass(LLVMPassManagerRef PM); diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index acd99ef9986..45c6fc571de 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -252,6 +252,7 @@ void initializeModuleDebugInfoPrinterPass(PassRegistry&); void initializeModuleSummaryIndexWrapperPassPass(PassRegistry &); void initializeNameAnonGlobalLegacyPassPass(PassRegistry &); void initializeNaryReassociateLegacyPassPass(PassRegistry &); +void initializeNewGVNPass(PassRegistry&); void initializeNoAAPass(PassRegistry&); void initializeObjCARCAAWrapperPassPass(PassRegistry&); void initializeObjCARCAPElimPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h index a6bc9cf09d4..e50137f8e02 100644 --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -167,6 +167,7 @@ namespace { (void) llvm::createGVNHoistPass(); (void) llvm::createMergedLoadStoreMotionPass(); (void) llvm::createGVNPass(); + (void) llvm::createNewGVNPass(); (void) llvm::createMemCpyOptPass(); (void) llvm::createLoopDeletionPass(); (void) llvm::createPostDomTree(); diff --git a/llvm/include/llvm/Transforms/Scalar.h b/llvm/include/llvm/Transforms/Scalar.h index 1c834e9367f..92558937d04 100644 --- a/llvm/include/llvm/Transforms/Scalar.h +++ b/llvm/include/llvm/Transforms/Scalar.h @@ -348,6 +348,13 @@ FunctionPass *createMergedLoadStoreMotionPass(); //===----------------------------------------------------------------------===// // +// 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. // diff --git a/llvm/include/llvm/Transforms/Scalar/GVNExpression.h b/llvm/include/llvm/Transforms/Scalar/GVNExpression.h new file mode 100644 index 00000000000..db67db8e6b6 --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/GVNExpression.h @@ -0,0 +1,551 @@ +//======- 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 <algorithm> + +namespace llvm { +class MemoryAccess; + +namespace GVNExpression { + +enum ExpressionType { + ET_Base, + ET_Constant, + ET_Variable, + ET_BasicStart, + ET_Basic, + ET_Call, + ET_AggregateValue, + ET_Phi, + ET_Load, + ET_Store, + ET_BasicEnd +}; + +class Expression { +private: + ExpressionType EType; + unsigned Opcode; + +public: + Expression(const Expression &) = delete; + Expression(ExpressionType ET = ET_Base, unsigned O = ~2U) + : EType(ET), Opcode(O) {} + void operator=(const Expression &) = delete; + virtual ~Expression(); + + static unsigned getEmptyKey() { return ~0U; } + static unsigned getTombstoneKey() { return ~1U; } + + bool operator==(const Expression &Other) const { + if (getOpcode() != Other.getOpcode()) + return false; + if (getOpcode() == getEmptyKey() || getOpcode() == getTombstoneKey()) + return true; + // Compare the expression type for anything but load and store. + // For load and store we set the opcode to zero. + // This is needed for load coercion. + if (getExpressionType() != ET_Load && + getExpressionType() != ET_Store && + getExpressionType() != Other.getExpressionType()) + return false; + + return equals(Other); + } + + virtual bool equals(const Expression &Other) const { return true; } + + unsigned getOpcode() const { return Opcode; } + void setOpcode(unsigned opcode) { Opcode = opcode; } + ExpressionType getExpressionType() const { return EType; } + + virtual hash_code getHashValue() const { + return hash_combine(getExpressionType(), getOpcode()); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const { + if (PrintEType) + OS << "etype = " << getExpressionType() << ","; + OS << "opcode = " << getOpcode() << ", "; + } + + 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: + typedef ArrayRecycler<Value *> RecyclerType; + typedef RecyclerType::Capacity RecyclerCapacity; + Value **Operands; + unsigned MaxOperands; + unsigned NumOperands; + Type *ValueType; + +public: + static bool classof(const Expression *EB) { + ExpressionType ET = EB->getExpressionType(); + return ET > ET_BasicStart && ET < ET_BasicEnd; + } + + BasicExpression(unsigned NumOperands) + : BasicExpression(NumOperands, ET_Basic) {} + BasicExpression(unsigned NumOperands, ExpressionType ET) + : Expression(ET), Operands(nullptr), MaxOperands(NumOperands), + NumOperands(0), ValueType(nullptr) {} + virtual ~BasicExpression() override; + void operator=(const BasicExpression &) = delete; + BasicExpression(const BasicExpression &) = delete; + BasicExpression() = delete; + + /// \brief Swap two operands. Used during GVN to put commutative operands in + /// order. + void swapOperands(unsigned First, unsigned Second) { + std::swap(Operands[First], Operands[Second]); + } + + Value *getOperand(unsigned N) const { + assert(Operands && "Operands not allocated"); + assert(N < NumOperands && "Operand out of range"); + return Operands[N]; + } + + void setOperand(unsigned N, Value *V) { + assert(Operands && "Operands not allocated before setting"); + assert(N < NumOperands && "Operand out of range"); + Operands[N] = V; + } + + unsigned getNumOperands() const { return NumOperands; } + + typedef Value **op_iterator; + typedef Value *const *const_ops_iterator; + 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<op_iterator> operands() { + return iterator_range<op_iterator>(ops_begin(), ops_end()); + } + iterator_range<const_ops_iterator> operands() const { + return iterator_range<const_ops_iterator>(ops_begin(), ops_end()); + } + + 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; + } + bool ops_empty() const { return getNumOperands() == 0; } + + 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; } + + virtual bool equals(const Expression &Other) const override { + if (getOpcode() != Other.getOpcode()) + return false; + + const auto &OE = cast<BasicExpression>(Other); + if (getType() != OE.getType()) + return false; + if (NumOperands != OE.NumOperands) + return false; + if (!std::equal(ops_begin(), ops_end(), OE.ops_begin())) + return false; + return true; + } + + virtual hash_code getHashValue() const override { + return hash_combine(getExpressionType(), getOpcode(), ValueType, + hash_combine_range(ops_begin(), ops_end())); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + 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 << "} "; + } +}; + +class CallExpression final : public BasicExpression { +private: + CallInst *Call; + MemoryAccess *DefiningAccess; + +public: + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Call; + } + + CallExpression(unsigned NumOperands, CallInst *C, MemoryAccess *DA) + : BasicExpression(NumOperands, ET_Call), Call(C), + DefiningAccess(DA) {} + void operator=(const CallExpression &) = delete; + CallExpression(const CallExpression &) = delete; + CallExpression() = delete; + virtual ~CallExpression() override; + + virtual bool equals(const Expression &Other) const override { + if (!this->BasicExpression::equals(Other)) + return false; + const auto &OE = cast<CallExpression>(Other); + return DefiningAccess == OE.DefiningAccess; + } + + virtual hash_code getHashValue() const override { + return hash_combine(this->BasicExpression::getHashValue(), DefiningAccess); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + if (PrintEType) + OS << "ExpressionTypeCall, "; + this->BasicExpression::printInternal(OS, false); + OS << " represents call at " << Call; + } +}; + +class LoadExpression final : public BasicExpression { +private: + LoadInst *Load; + MemoryAccess *DefiningAccess; + unsigned Alignment; + +public: + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Load; + } + + LoadExpression(unsigned NumOperands, LoadInst *L, MemoryAccess *DA) + : LoadExpression(ET_Load, NumOperands, L, DA) {} + LoadExpression(enum ExpressionType EType, unsigned NumOperands, + LoadInst *L, MemoryAccess *DA) + : BasicExpression(NumOperands, EType), Load(L), DefiningAccess(DA) { + Alignment = L ? L->getAlignment() : 0; + } + void operator=(const LoadExpression &) = delete; + LoadExpression(const LoadExpression &) = delete; + LoadExpression() = delete; + virtual ~LoadExpression() override; + + 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; } + + virtual bool equals(const Expression &Other) const override; + + virtual hash_code getHashValue() const override { + return hash_combine(getOpcode(), getType(), DefiningAccess, + hash_combine_range(ops_begin(), ops_end())); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + if (PrintEType) + OS << "ExpressionTypeLoad, "; + this->BasicExpression::printInternal(OS, false); + OS << " represents Load at " << Load; + OS << " with DefiningAccess " << DefiningAccess; + } +}; + +class StoreExpression final : public BasicExpression { +private: + StoreInst *Store; + MemoryAccess *DefiningAccess; + +public: + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Store; + } + + StoreExpression(unsigned NumOperands, StoreInst *S, MemoryAccess *DA) + : BasicExpression(NumOperands, ET_Store), Store(S), + DefiningAccess(DA) {} + void operator=(const StoreExpression &) = delete; + StoreExpression(const StoreExpression &) = delete; + StoreExpression() = delete; + virtual ~StoreExpression() override; + + StoreInst *getStoreInst() const { return Store; } + MemoryAccess *getDefiningAccess() const { return DefiningAccess; } + + virtual bool equals(const Expression &Other) const override; + + virtual hash_code getHashValue() const override { + return hash_combine(getOpcode(), getType(), DefiningAccess, + hash_combine_range(ops_begin(), ops_end())); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + if (PrintEType) + OS << "ExpressionTypeStore, "; + this->BasicExpression::printInternal(OS, false); + OS << " represents Store at " << Store; + } +}; + +class AggregateValueExpression final : public BasicExpression { +private: + unsigned MaxIntOperands; + unsigned NumIntOperands; + unsigned *IntOperands; + +public: + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_AggregateValue; + } + + AggregateValueExpression(unsigned NumOperands, + unsigned NumIntOperands) + : BasicExpression(NumOperands, ET_AggregateValue), + MaxIntOperands(NumIntOperands), NumIntOperands(0), + IntOperands(nullptr) {} + + void operator=(const AggregateValueExpression &) = delete; + AggregateValueExpression(const AggregateValueExpression &) = delete; + AggregateValueExpression() = delete; + virtual ~AggregateValueExpression() override; + + typedef unsigned *int_arg_iterator; + typedef const unsigned *const_int_arg_iterator; + + 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; + } + 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; + } + + virtual void allocateIntOperands(BumpPtrAllocator &Allocator) { + assert(!IntOperands && "Operands already allocated"); + IntOperands = Allocator.Allocate<unsigned>(MaxIntOperands); + } + + virtual bool equals(const Expression &Other) const override { + if (!this->BasicExpression::equals(Other)) + return false; + const AggregateValueExpression &OE = cast<AggregateValueExpression>(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 override { + return hash_combine(this->BasicExpression::getHashValue(), + hash_combine_range(int_ops_begin(), int_ops_end())); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + 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 final : public BasicExpression { +private: + BasicBlock *BB; + +public: + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Phi; + } + + PHIExpression(unsigned NumOperands, BasicBlock *B) + : BasicExpression(NumOperands, ET_Phi), BB(B) {} + void operator=(const PHIExpression &) = delete; + PHIExpression(const PHIExpression &) = delete; + PHIExpression() = delete; + virtual ~PHIExpression() override; + + virtual bool equals(const Expression &Other) const override { + if (!this->BasicExpression::equals(Other)) + return false; + const PHIExpression &OE = cast<PHIExpression>(Other); + if (BB != OE.BB) + return false; + return true; + } + + virtual hash_code getHashValue() const override { + return hash_combine(this->BasicExpression::getHashValue(), BB); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + if (PrintEType) + OS << "ExpressionTypePhi, "; + this->BasicExpression::printInternal(OS, false); + OS << "bb = " << BB; + } +}; + +class VariableExpression final : public Expression { +private: + Value *VariableValue; + +public: + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Variable; + } + + VariableExpression(Value *V) + : Expression(ET_Variable), VariableValue(V) {} + void operator=(const VariableExpression &) = delete; + VariableExpression(const VariableExpression &) = delete; + VariableExpression() = delete; + + Value *getVariableValue() const { return VariableValue; } + void setVariableValue(Value *V) { VariableValue = V; } + virtual bool equals(const Expression &Other) const override { + const VariableExpression &OC = cast<VariableExpression>(Other); + if (VariableValue != OC.VariableValue) + return false; + return true; + } + + virtual hash_code getHashValue() const override { + return hash_combine(getExpressionType(), VariableValue->getType(), + VariableValue); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + if (PrintEType) + OS << "ExpressionTypeVariable, "; + this->Expression::printInternal(OS, false); + OS << " variable = " << *VariableValue; + } +}; + +class ConstantExpression final : public Expression { +private: + Constant *ConstantValue; + +public: + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Constant; + } + + ConstantExpression() + : Expression(ET_Constant), ConstantValue(NULL) {} + ConstantExpression(Constant *constantValue) + : Expression(ET_Constant), ConstantValue(constantValue) {} + void operator=(const ConstantExpression &) = delete; + ConstantExpression(const ConstantExpression &) = delete; + + Constant *getConstantValue() const { return ConstantValue; } + void setConstantValue(Constant *V) { ConstantValue = V; } + + virtual bool equals(const Expression &Other) const override { + const ConstantExpression &OC = cast<ConstantExpression>(Other); + return ConstantValue == OC.ConstantValue; + } + + virtual hash_code getHashValue() const override { + return hash_combine(getExpressionType(), ConstantValue->getType(), + ConstantValue); + } + + // + // Debugging support + // + virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + if (PrintEType) + OS << "ExpressionTypeConstant, "; + this->Expression::printInternal(OS, false); + OS << " constant = " << *ConstantValue; + } +}; +} +} + +#endif diff --git a/llvm/include/llvm/Transforms/Scalar/NewGVN.h b/llvm/include/llvm/Transforms/Scalar/NewGVN.h new file mode 100644 index 00000000000..d0425aa4345 --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/NewGVN.h @@ -0,0 +1,28 @@ +//===----- NewGVN.h - Global Value Numbering Pass ---------------*- 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. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_NEWGVN_H +#define LLVM_TRANSFORMS_SCALAR_NEWGVN_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { +class NewGVNPass : public PassInfoMixin<NewGVNPass> { +public: + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_NEWGVN_H + |
