diff options
Diffstat (limited to 'include/llvm/Transforms/Scalar')
-rw-r--r-- | include/llvm/Transforms/Scalar/GVNExpression.h | 313 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/JumpThreading.h | 10 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/LoopDataPrefetch.h | 8 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/LoopDeletion.h | 17 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/LoopLoadElimination.h | 30 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/LoopPassManager.h | 36 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/LoopPredication.h | 32 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/LoopSink.h | 40 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/LoopUnrollPass.h | 30 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/MemCpyOptimizer.h | 11 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/SROA.h | 18 | ||||
-rw-r--r-- | include/llvm/Transforms/Scalar/SimplifyCFG.h | 9 |
12 files changed, 370 insertions, 184 deletions
diff --git a/include/llvm/Transforms/Scalar/GVNExpression.h b/include/llvm/Transforms/Scalar/GVNExpression.h index 3458696e0687a..2670a0c1a5339 100644 --- a/include/llvm/Transforms/Scalar/GVNExpression.h +++ b/include/llvm/Transforms/Scalar/GVNExpression.h @@ -1,4 +1,4 @@ -//======- GVNExpression.h - GVN Expression classes -------*- C++ -*-==-------=// +//======- GVNExpression.h - GVN Expression classes --------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -17,18 +17,22 @@ #define LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H #include "llvm/ADT/Hashing.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Analysis/MemorySSA.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/Casting.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/MemorySSA.h" #include <algorithm> +#include <cassert> +#include <iterator> +#include <utility> namespace llvm { -class MemoryAccess; namespace GVNExpression { @@ -39,11 +43,13 @@ enum ExpressionType { ET_Unknown, ET_BasicStart, ET_Basic, - ET_Call, ET_AggregateValue, ET_Phi, + ET_MemoryStart, + ET_Call, ET_Load, ET_Store, + ET_MemoryEnd, ET_BasicEnd }; @@ -53,23 +59,22 @@ private: unsigned Opcode; public: - Expression(const Expression &) = delete; Expression(ExpressionType ET = ET_Base, unsigned O = ~2U) : EType(ET), Opcode(O) {} - void operator=(const Expression &) = delete; + Expression(const Expression &) = delete; + Expression &operator=(const Expression &) = delete; virtual ~Expression(); static unsigned getEmptyKey() { return ~0U; } static unsigned getTombstoneKey() { return ~1U; } - + bool operator!=(const Expression &Other) const { return !(*this == Other); } 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. + // For load and store we set the opcode to zero to make them equal. if (getExpressionType() != ET_Load && getExpressionType() != ET_Store && getExpressionType() != Other.getExpressionType()) return false; @@ -83,9 +88,8 @@ public: void setOpcode(unsigned opcode) { Opcode = opcode; } ExpressionType getExpressionType() const { return EType; } - virtual hash_code getHashValue() const { - return hash_combine(getExpressionType(), getOpcode()); - } + // We deliberately leave the expression type out of the hash value. + virtual hash_code getHashValue() const { return getOpcode(); } // // Debugging support @@ -101,7 +105,11 @@ public: printInternal(OS, true); OS << "}"; } - void dump() const { print(dbgs()); } + + LLVM_DUMP_METHOD void dump() const { + print(dbgs()); + dbgs() << "\n"; + } }; inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) { @@ -119,20 +127,20 @@ private: 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; + BasicExpression(const BasicExpression &) = delete; + BasicExpression &operator=(const BasicExpression &) = delete; + ~BasicExpression() override; + + static bool classof(const Expression *EB) { + ExpressionType ET = EB->getExpressionType(); + return ET > ET_BasicStart && ET < ET_BasicEnd; + } /// \brief Swap two operands. Used during GVN to put commutative operands in /// order. @@ -185,7 +193,7 @@ public: void setType(Type *T) { ValueType = T; } Type *getType() const { return ValueType; } - virtual bool equals(const Expression &Other) const override { + bool equals(const Expression &Other) const override { if (getOpcode() != Other.getOpcode()) return false; @@ -194,15 +202,15 @@ public: std::equal(op_begin(), op_end(), OE.op_begin()); } - virtual hash_code getHashValue() const override { - return hash_combine(getExpressionType(), getOpcode(), ValueType, + hash_code getHashValue() const override { + return hash_combine(this->Expression::getHashValue(), ValueType, hash_combine_range(op_begin(), op_end())); } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeBasic, "; @@ -216,6 +224,7 @@ public: OS << "} "; } }; + class op_inserter : public std::iterator<std::output_iterator_tag, void, void, void, void> { private: @@ -235,131 +244,143 @@ public: op_inserter &operator++(int) { return *this; } }; -class CallExpression final : public BasicExpression { +class MemoryExpression : public BasicExpression { private: - CallInst *Call; - MemoryAccess *DefiningAccess; + const MemoryAccess *MemoryLeader; public: + MemoryExpression(unsigned NumOperands, enum ExpressionType EType, + const MemoryAccess *MemoryLeader) + : BasicExpression(NumOperands, EType), MemoryLeader(MemoryLeader){}; + + MemoryExpression() = delete; + MemoryExpression(const MemoryExpression &) = delete; + MemoryExpression &operator=(const MemoryExpression &) = delete; static bool classof(const Expression *EB) { - return EB->getExpressionType() == ET_Call; + return EB->getExpressionType() > ET_MemoryStart && + EB->getExpressionType() < ET_MemoryEnd; + } + hash_code getHashValue() const override { + return hash_combine(this->BasicExpression::getHashValue(), MemoryLeader); } - 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 { + bool equals(const Expression &Other) const override { if (!this->BasicExpression::equals(Other)) return false; - const auto &OE = cast<CallExpression>(Other); - return DefiningAccess == OE.DefiningAccess; + const MemoryExpression &OtherMCE = cast<MemoryExpression>(Other); + + return MemoryLeader == OtherMCE.MemoryLeader; } - virtual hash_code getHashValue() const override { - return hash_combine(this->BasicExpression::getHashValue(), DefiningAccess); + const MemoryAccess *getMemoryLeader() const { return MemoryLeader; } + void setMemoryLeader(const MemoryAccess *ML) { MemoryLeader = ML; } +}; + +class CallExpression final : public MemoryExpression { +private: + CallInst *Call; + +public: + CallExpression(unsigned NumOperands, CallInst *C, + const MemoryAccess *MemoryLeader) + : MemoryExpression(NumOperands, ET_Call, MemoryLeader), Call(C) {} + CallExpression() = delete; + CallExpression(const CallExpression &) = delete; + CallExpression &operator=(const CallExpression &) = delete; + ~CallExpression() override; + + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Call; } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeCall, "; this->BasicExpression::printInternal(OS, false); - OS << " represents call at " << Call; + OS << " represents call at "; + Call->printAsOperand(OS); } }; -class LoadExpression final : public BasicExpression { +class LoadExpression final : public MemoryExpression { 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(unsigned NumOperands, LoadInst *L, + const MemoryAccess *MemoryLeader) + : LoadExpression(ET_Load, NumOperands, L, MemoryLeader) {} LoadExpression(enum ExpressionType EType, unsigned NumOperands, LoadInst *L, - MemoryAccess *DA) - : BasicExpression(NumOperands, EType), Load(L), DefiningAccess(DA) { + const MemoryAccess *MemoryLeader) + : MemoryExpression(NumOperands, EType, MemoryLeader), Load(L) { Alignment = L ? L->getAlignment() : 0; } - void operator=(const LoadExpression &) = delete; - LoadExpression(const LoadExpression &) = delete; LoadExpression() = delete; - virtual ~LoadExpression() override; + LoadExpression(const LoadExpression &) = delete; + LoadExpression &operator=(const LoadExpression &) = delete; + ~LoadExpression() override; + + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Load; + } 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(op_begin(), op_end())); - } + bool equals(const Expression &Other) const override; // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + 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; + OS << " represents Load at "; + Load->printAsOperand(OS); + OS << " with MemoryLeader " << *getMemoryLeader(); } }; -class StoreExpression final : public BasicExpression { +class StoreExpression final : public MemoryExpression { private: StoreInst *Store; - MemoryAccess *DefiningAccess; + Value *StoredValue; public: + StoreExpression(unsigned NumOperands, StoreInst *S, Value *StoredValue, + const MemoryAccess *MemoryLeader) + : MemoryExpression(NumOperands, ET_Store, MemoryLeader), Store(S), + StoredValue(StoredValue) {} + StoreExpression() = delete; + StoreExpression(const StoreExpression &) = delete; + StoreExpression &operator=(const StoreExpression &) = delete; + ~StoreExpression() override; + 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; } + Value *getStoredValue() const { return StoredValue; } - virtual bool equals(const Expression &Other) const override; + bool equals(const Expression &Other) const override; - virtual hash_code getHashValue() const override { - return hash_combine(getOpcode(), getType(), DefiningAccess, - hash_combine_range(op_begin(), op_end())); - } - - // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeStore, "; this->BasicExpression::printInternal(OS, false); - OS << " represents Store at " << Store; - OS << " with DefiningAccess " << *DefiningAccess; + OS << " represents Store " << *Store; + OS << " with MemoryLeader " << *getMemoryLeader(); } }; @@ -370,19 +391,19 @@ private: 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; + AggregateValueExpression(const AggregateValueExpression &) = delete; + AggregateValueExpression & + operator=(const AggregateValueExpression &) = delete; + ~AggregateValueExpression() override; + + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_AggregateValue; + } typedef unsigned *int_arg_iterator; typedef const unsigned *const_int_arg_iterator; @@ -407,7 +428,7 @@ public: IntOperands = Allocator.Allocate<unsigned>(MaxIntOperands); } - virtual bool equals(const Expression &Other) const override { + bool equals(const Expression &Other) const override { if (!this->BasicExpression::equals(Other)) return false; const AggregateValueExpression &OE = cast<AggregateValueExpression>(Other); @@ -415,7 +436,7 @@ public: std::equal(int_op_begin(), int_op_end(), OE.int_op_begin()); } - virtual hash_code getHashValue() const override { + hash_code getHashValue() const override { return hash_combine(this->BasicExpression::getHashValue(), hash_combine_range(int_op_begin(), int_op_end())); } @@ -423,7 +444,7 @@ public: // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeAggregateValue, "; this->BasicExpression::printInternal(OS, false); @@ -434,6 +455,7 @@ public: OS << "}"; } }; + class int_op_inserter : public std::iterator<std::output_iterator_tag, void, void, void, void> { private: @@ -443,6 +465,7 @@ private: public: explicit int_op_inserter(AggregateValueExpression &E) : AVE(&E) {} explicit int_op_inserter(AggregateValueExpression *E) : AVE(E) {} + int_op_inserter &operator=(unsigned int val) { AVE->int_op_push_back(val); return *this; @@ -457,32 +480,32 @@ 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; + PHIExpression(const PHIExpression &) = delete; + PHIExpression &operator=(const PHIExpression &) = delete; + ~PHIExpression() override; - virtual bool equals(const Expression &Other) const override { + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Phi; + } + + bool equals(const Expression &Other) const override { if (!this->BasicExpression::equals(Other)) return false; const PHIExpression &OE = cast<PHIExpression>(Other); return BB == OE.BB; } - virtual hash_code getHashValue() const override { + hash_code getHashValue() const override { return hash_combine(this->BasicExpression::getHashValue(), BB); } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypePhi, "; this->BasicExpression::printInternal(OS, false); @@ -495,31 +518,32 @@ private: Value *VariableValue; public: + VariableExpression(Value *V) : Expression(ET_Variable), VariableValue(V) {} + VariableExpression() = delete; + VariableExpression(const VariableExpression &) = delete; + VariableExpression &operator=(const VariableExpression &) = delete; + 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 { + + bool equals(const Expression &Other) const override { const VariableExpression &OC = cast<VariableExpression>(Other); return VariableValue == OC.VariableValue; } - virtual hash_code getHashValue() const override { - return hash_combine(getExpressionType(), VariableValue->getType(), - VariableValue); + hash_code getHashValue() const override { + return hash_combine(this->Expression::getHashValue(), + VariableValue->getType(), VariableValue); } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeVariable, "; this->Expression::printInternal(OS, false); @@ -529,36 +553,36 @@ public: class ConstantExpression final : public Expression { private: - Constant *ConstantValue; + Constant *ConstantValue = nullptr; public: - static bool classof(const Expression *EB) { - return EB->getExpressionType() == ET_Constant; - } - - ConstantExpression() : Expression(ET_Constant), ConstantValue(NULL) {} + ConstantExpression() : Expression(ET_Constant) {} ConstantExpression(Constant *constantValue) : Expression(ET_Constant), ConstantValue(constantValue) {} - void operator=(const ConstantExpression &) = delete; ConstantExpression(const ConstantExpression &) = delete; + ConstantExpression &operator=(const ConstantExpression &) = delete; + + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Constant; + } Constant *getConstantValue() const { return ConstantValue; } void setConstantValue(Constant *V) { ConstantValue = V; } - virtual bool equals(const Expression &Other) const override { + 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); + hash_code getHashValue() const override { + return hash_combine(this->Expression::getHashValue(), + ConstantValue->getType(), ConstantValue); } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeConstant, "; this->Expression::printInternal(OS, false); @@ -571,35 +595,40 @@ private: Instruction *Inst; public: + UnknownExpression(Instruction *I) : Expression(ET_Unknown), Inst(I) {} + UnknownExpression() = delete; + UnknownExpression(const UnknownExpression &) = delete; + UnknownExpression &operator=(const UnknownExpression &) = delete; + static bool classof(const Expression *EB) { return EB->getExpressionType() == ET_Unknown; } - UnknownExpression(Instruction *I) : Expression(ET_Unknown), Inst(I) {} - void operator=(const UnknownExpression &) = delete; - UnknownExpression(const UnknownExpression &) = delete; - UnknownExpression() = delete; - Instruction *getInstruction() const { return Inst; } void setInstruction(Instruction *I) { Inst = I; } - virtual bool equals(const Expression &Other) const override { + + bool equals(const Expression &Other) const override { const auto &OU = cast<UnknownExpression>(Other); return Inst == OU.Inst; } - virtual hash_code getHashValue() const override { - return hash_combine(getExpressionType(), Inst); + + hash_code getHashValue() const override { + return hash_combine(this->Expression::getHashValue(), Inst); } + // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeUnknown, "; this->Expression::printInternal(OS, false); OS << " inst = " << *Inst; } }; -} -} -#endif +} // end namespace GVNExpression + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H diff --git a/include/llvm/Transforms/Scalar/JumpThreading.h b/include/llvm/Transforms/Scalar/JumpThreading.h index f96741c0127d8..1da86132591b7 100644 --- a/include/llvm/Transforms/Scalar/JumpThreading.h +++ b/include/llvm/Transforms/Scalar/JumpThreading.h @@ -17,12 +17,14 @@ #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BlockFrequencyInfoImpl.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/ValueHandle.h" namespace llvm { @@ -59,9 +61,11 @@ enum ConstantPreference { WantInteger, WantBlockAddress }; class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> { TargetLibraryInfo *TLI; LazyValueInfo *LVI; + AliasAnalysis *AA; std::unique_ptr<BlockFrequencyInfo> BFI; std::unique_ptr<BranchProbabilityInfo> BPI; bool HasProfileData = false; + bool HasGuards = false; #ifdef NDEBUG SmallPtrSet<const BasicBlock *, 16> LoopHeaders; #else @@ -88,7 +92,8 @@ public: // Glue for old PM. bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, - bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_, + AliasAnalysis *AA_, bool HasProfileData_, + std::unique_ptr<BlockFrequencyInfo> BFI_, std::unique_ptr<BranchProbabilityInfo> BPI_); PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); @@ -122,6 +127,9 @@ public: bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); bool TryToUnfoldSelectInCurrBB(BasicBlock *BB); + bool ProcessGuards(BasicBlock *BB); + bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI); + private: BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, const char *Suffix); diff --git a/include/llvm/Transforms/Scalar/LoopDataPrefetch.h b/include/llvm/Transforms/Scalar/LoopDataPrefetch.h index 114d1bad17a5c..12c7a030ff8b7 100644 --- a/include/llvm/Transforms/Scalar/LoopDataPrefetch.h +++ b/include/llvm/Transforms/Scalar/LoopDataPrefetch.h @@ -22,10 +22,12 @@ namespace llvm { /// An optimization pass inserting data prefetches in loops. class LoopDataPrefetchPass : public PassInfoMixin<LoopDataPrefetchPass> { public: - LoopDataPrefetchPass() {} + LoopDataPrefetchPass() = default; + /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPDATAPREFETCH_H diff --git a/include/llvm/Transforms/Scalar/LoopDeletion.h b/include/llvm/Transforms/Scalar/LoopDeletion.h index b44f823a82cac..7b8cb1e115c97 100644 --- a/include/llvm/Transforms/Scalar/LoopDeletion.h +++ b/include/llvm/Transforms/Scalar/LoopDeletion.h @@ -1,4 +1,4 @@ -//===- LoopDeletion.h - Loop Deletion -------------------------------------===// +//===- LoopDeletion.h - Loop Deletion ---------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,6 +14,7 @@ #ifndef LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H #define LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H +#include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/IR/PassManager.h" @@ -23,18 +24,12 @@ namespace llvm { class LoopDeletionPass : public PassInfoMixin<LoopDeletionPass> { public: - LoopDeletionPass() {} + LoopDeletionPass() = default; + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); - bool runImpl(Loop *L, DominatorTree &DT, ScalarEvolution &SE, - LoopInfo &loopInfo); - -private: - bool isLoopDead(Loop *L, ScalarEvolution &SE, - SmallVectorImpl<BasicBlock *> &exitingBlocks, - SmallVectorImpl<BasicBlock *> &exitBlocks, bool &Changed, - BasicBlock *Preheader); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H diff --git a/include/llvm/Transforms/Scalar/LoopLoadElimination.h b/include/llvm/Transforms/Scalar/LoopLoadElimination.h new file mode 100644 index 0000000000000..7a007a7e822d2 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopLoadElimination.h @@ -0,0 +1,30 @@ +//===---- LoopLoadElimination.h ---------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This header defines the LoopLoadEliminationPass object. This pass forwards +/// loaded values around loop backedges to allow their use in subsequent +/// iterations. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H +#define LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Pass to forward loads in a loop around the backedge to subsequent +/// iterations. +struct LoopLoadEliminationPass : public PassInfoMixin<LoopLoadEliminationPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H diff --git a/include/llvm/Transforms/Scalar/LoopPassManager.h b/include/llvm/Transforms/Scalar/LoopPassManager.h index b0e6dd6f4c081..715b11d3d9749 100644 --- a/include/llvm/Transforms/Scalar/LoopPassManager.h +++ b/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -51,6 +51,8 @@ #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Utils/LCSSA.h" +#include "llvm/Transforms/Utils/LoopSimplify.h" namespace llvm { @@ -248,19 +250,25 @@ template <typename LoopPassT> class FunctionToLoopPassAdaptor : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> { public: - explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) {} + explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) { + LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); + LoopCanonicalizationFPM.addPass(LCSSAPass()); + } /// \brief Runs the loop passes across every loop in the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { - // Setup the loop analysis manager from its proxy. - LoopAnalysisManager &LAM = - AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager(); + // Before we even compute any loop analyses, first run a miniature function + // pass pipeline to put loops into their canonical form. Note that we can + // directly build up function analyses after this as the function pass + // manager handles all the invalidation at that layer. + PreservedAnalyses PA = LoopCanonicalizationFPM.run(F, AM); + // Get the loop structure for this function LoopInfo &LI = AM.getResult<LoopAnalysis>(F); // If there are no loops, there is nothing to do here. if (LI.empty()) - return PreservedAnalyses::all(); + return PA; // Get the analysis results needed by loop passes. LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F), @@ -271,7 +279,13 @@ public: AM.getResult<TargetLibraryAnalysis>(F), AM.getResult<TargetIRAnalysis>(F)}; - PreservedAnalyses PA = PreservedAnalyses::all(); + // Setup the loop analysis manager from its proxy. It is important that + // this is only done when there are loops to process and we have built the + // LoopStandardAnalysisResults object. The loop analyses cached in this + // manager have access to those analysis results and so it must invalidate + // itself when they go away. + LoopAnalysisManager &LAM = + AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager(); // A postorder worklist of loops to process. SmallPriorityWorklist<Loop *, 4> Worklist; @@ -294,8 +308,15 @@ public: // Reset the update structure for this loop. Updater.CurrentL = L; Updater.SkipCurrentLoop = false; + #ifndef NDEBUG + // Save a parent loop pointer for asserts. Updater.ParentL = L->getParentLoop(); + + // Verify the loop structure and LCSSA form before visiting the loop. + L->verifyLoop(); + assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) && + "Loops must remain in LCSSA form!"); #endif PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater); @@ -321,7 +342,6 @@ public: PA.preserveSet<AllAnalysesOn<Loop>>(); PA.preserve<LoopAnalysisManagerFunctionProxy>(); // We also preserve the set of standard analyses. - PA.preserve<AssumptionAnalysis>(); PA.preserve<DominatorTreeAnalysis>(); PA.preserve<LoopAnalysis>(); PA.preserve<ScalarEvolutionAnalysis>(); @@ -336,6 +356,8 @@ public: private: LoopPassT Pass; + + FunctionPassManager LoopCanonicalizationFPM; }; /// \brief A function to deduce a loop pass type and wrap it in the templated diff --git a/include/llvm/Transforms/Scalar/LoopPredication.h b/include/llvm/Transforms/Scalar/LoopPredication.h new file mode 100644 index 0000000000000..57398bdb6bd1c --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopPredication.h @@ -0,0 +1,32 @@ +//===- LoopPredication.h - Guard based loop predication pass ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass tries to convert loop variant range checks to loop invariant by +// widening checks across loop iterations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPPREDICATION_H +#define LLVM_TRANSFORMS_SCALAR_LOOPPREDICATION_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +/// Performs Loop Predication Pass. +class LoopPredicationPass : public PassInfoMixin<LoopPredicationPass> { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPPREDICATION_H diff --git a/include/llvm/Transforms/Scalar/LoopSink.h b/include/llvm/Transforms/Scalar/LoopSink.h new file mode 100644 index 0000000000000..371a7c8d2c446 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopSink.h @@ -0,0 +1,40 @@ +//===- LoopSink.h - Loop Sink Pass ------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Loop Sink pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPSINK_H +#define LLVM_TRANSFORMS_SCALAR_LOOPSINK_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +/// A pass that does profile-guided sinking of instructions into loops. +/// +/// This is a function pass as it shouldn't be composed into any kind of +/// unified loop pass pipeline. The goal of it is to sink code into loops that +/// is loop invariant but only required within the loop body when doing so +/// reduces the global expected dynamic frequency with which it executes. +/// A classic example is an extremely cold branch within a loop body. +/// +/// We do this as a separate pass so that during normal optimization all +/// invariant operations can be held outside the loop body to simplify +/// fundamental analyses and transforms of the loop. +class LoopSinkPass : public PassInfoMixin<LoopSinkPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPSINK_H diff --git a/include/llvm/Transforms/Scalar/LoopUnrollPass.h b/include/llvm/Transforms/Scalar/LoopUnrollPass.h index 9da95ef81fad4..7253bd09766ef 100644 --- a/include/llvm/Transforms/Scalar/LoopUnrollPass.h +++ b/include/llvm/Transforms/Scalar/LoopUnrollPass.h @@ -16,12 +16,30 @@ namespace llvm { -struct LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> { - Optional<unsigned> ProvidedCount; - Optional<unsigned> ProvidedThreshold; - Optional<bool> ProvidedAllowPartial; - Optional<bool> ProvidedRuntime; - Optional<bool> ProvidedUpperBound; +class LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> { + const bool AllowPartialUnrolling; + const int OptLevel; + + explicit LoopUnrollPass(bool AllowPartialUnrolling, int OptLevel) + : AllowPartialUnrolling(AllowPartialUnrolling), OptLevel(OptLevel) {} + +public: + /// Create an instance of the loop unroll pass that will support both full + /// and partial unrolling. + /// + /// This uses the target information (or flags) to control the thresholds for + /// different unrolling stategies but supports all of them. + static LoopUnrollPass create(int OptLevel = 2) { + return LoopUnrollPass(/*AllowPartialUnrolling*/ true, OptLevel); + } + + /// Create an instance of the loop unroll pass that only does full loop + /// unrolling. + /// + /// This will disable any runtime or partial unrolling. + static LoopUnrollPass createFull(int OptLevel = 2) { + return LoopUnrollPass(/*AllowPartialUnrolling*/ false, OptLevel); + } PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); diff --git a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h index 4308e44e7c4bd..f52872dd2ea78 100644 --- a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h +++ b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h @@ -15,17 +15,18 @@ #ifndef LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H #define LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H -#include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/BasicBlock.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/PassManager.h" +#include <cstdint> +#include <functional> namespace llvm { @@ -37,7 +38,8 @@ class MemCpyOptPass : public PassInfoMixin<MemCpyOptPass> { std::function<DominatorTree &()> LookupDomTree; public: - MemCpyOptPass() {} + MemCpyOptPass() = default; + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); // Glue for the old PM. bool runImpl(Function &F, MemoryDependenceResults *MD_, @@ -63,6 +65,7 @@ private: bool iterateOnFunction(Function &F); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H diff --git a/include/llvm/Transforms/Scalar/SROA.h b/include/llvm/Transforms/Scalar/SROA.h index 3e93f46dd4e50..3080b75ba8949 100644 --- a/include/llvm/Transforms/Scalar/SROA.h +++ b/include/llvm/Transforms/Scalar/SROA.h @@ -21,17 +21,21 @@ #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" +#include "llvm/Support/Compiler.h" +#include <vector> namespace llvm { /// A private "module" namespace for types and utilities used by SROA. These /// are implementation details and should not be used by clients. namespace sroa LLVM_LIBRARY_VISIBILITY { + class AllocaSliceRewriter; class AllocaSlices; class Partition; class SROALegacyPass; -} + +} // end namespace sroa /// \brief An optimization pass providing Scalar Replacement of Aggregates. /// @@ -52,9 +56,9 @@ class SROALegacyPass; /// this form. By doing so, it will enable promotion of vector aggregates to /// SSA vector values. class SROA : public PassInfoMixin<SROA> { - LLVMContext *C; - DominatorTree *DT; - AssumptionCache *AC; + LLVMContext *C = nullptr; + DominatorTree *DT = nullptr; + AssumptionCache *AC = nullptr; /// \brief Worklist of alloca instructions to simplify. /// @@ -99,7 +103,7 @@ class SROA : public PassInfoMixin<SROA> { SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects; public: - SROA() : C(nullptr), DT(nullptr), AC(nullptr) {} + SROA() = default; /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); @@ -122,6 +126,6 @@ private: bool promoteAllocas(Function &F); }; -} +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_SCALAR_SROA_H diff --git a/include/llvm/Transforms/Scalar/SimplifyCFG.h b/include/llvm/Transforms/Scalar/SimplifyCFG.h index 96e1658c00b0e..54b51c405ad41 100644 --- a/include/llvm/Transforms/Scalar/SimplifyCFG.h +++ b/include/llvm/Transforms/Scalar/SimplifyCFG.h @@ -27,13 +27,16 @@ namespace llvm { /// by the rest of the mid-level optimizer. class SimplifyCFGPass : public PassInfoMixin<SimplifyCFGPass> { int BonusInstThreshold; + bool LateSimplifyCFG; public: - /// \brief Construct a pass with the default thresholds. + /// \brief Construct a pass with the default thresholds + /// and switch optimizations. SimplifyCFGPass(); - /// \brief Construct a pass with a specific bonus threshold. - SimplifyCFGPass(int BonusInstThreshold); + /// \brief Construct a pass with a specific bonus threshold + /// and optional switch optimizations. + SimplifyCFGPass(int BonusInstThreshold, bool LateSimplifyCFG); /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |