summaryrefslogtreecommitdiff
path: root/include/llvm/Transforms/Scalar
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/Transforms/Scalar')
-rw-r--r--include/llvm/Transforms/Scalar/GVNExpression.h313
-rw-r--r--include/llvm/Transforms/Scalar/JumpThreading.h10
-rw-r--r--include/llvm/Transforms/Scalar/LoopDataPrefetch.h8
-rw-r--r--include/llvm/Transforms/Scalar/LoopDeletion.h17
-rw-r--r--include/llvm/Transforms/Scalar/LoopLoadElimination.h30
-rw-r--r--include/llvm/Transforms/Scalar/LoopPassManager.h36
-rw-r--r--include/llvm/Transforms/Scalar/LoopPredication.h32
-rw-r--r--include/llvm/Transforms/Scalar/LoopSink.h40
-rw-r--r--include/llvm/Transforms/Scalar/LoopUnrollPass.h30
-rw-r--r--include/llvm/Transforms/Scalar/MemCpyOptimizer.h11
-rw-r--r--include/llvm/Transforms/Scalar/SROA.h18
-rw-r--r--include/llvm/Transforms/Scalar/SimplifyCFG.h9
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);