summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Scalar/EarlyCSE.cpp')
-rw-r--r--llvm/lib/Transforms/Scalar/EarlyCSE.cpp132
1 files changed, 90 insertions, 42 deletions
diff --git a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
index c5c9b2c185d..6d1362a6a28 100644
--- a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
+++ b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
@@ -13,9 +13,12 @@
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar/EarlyCSE.h"
+#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopedHashTable.h"
#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/GlobalsModRef.h"
@@ -24,18 +27,36 @@
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Use.h"
+#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/AtomicOrdering.h"
+#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/RecyclingAllocator.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
+#include <cassert>
#include <deque>
+#include <memory>
+#include <utility>
+
using namespace llvm;
using namespace llvm::PatternMatch;
@@ -53,6 +74,7 @@ STATISTIC(NumDSE, "Number of trivial dead stores removed");
//===----------------------------------------------------------------------===//
namespace {
+
/// \brief Struct representing the available values in the scoped hash table.
struct SimpleValue {
Instruction *Inst;
@@ -77,20 +99,25 @@ struct SimpleValue {
isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
}
};
-}
+
+} // end anonymous namespace
namespace llvm {
+
template <> struct DenseMapInfo<SimpleValue> {
static inline SimpleValue getEmptyKey() {
return DenseMapInfo<Instruction *>::getEmptyKey();
}
+
static inline SimpleValue getTombstoneKey() {
return DenseMapInfo<Instruction *>::getTombstoneKey();
}
+
static unsigned getHashValue(SimpleValue Val);
static bool isEqual(SimpleValue LHS, SimpleValue RHS);
};
-}
+
+} // end namespace llvm
unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
Instruction *Inst = Val.Inst;
@@ -181,6 +208,7 @@ bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
//===----------------------------------------------------------------------===//
namespace {
+
/// \brief Struct representing the available call values in the scoped hash
/// table.
struct CallValue {
@@ -206,20 +234,25 @@ struct CallValue {
return true;
}
};
-}
+
+} // end anonymous namespace
namespace llvm {
+
template <> struct DenseMapInfo<CallValue> {
static inline CallValue getEmptyKey() {
return DenseMapInfo<Instruction *>::getEmptyKey();
}
+
static inline CallValue getTombstoneKey() {
return DenseMapInfo<Instruction *>::getTombstoneKey();
}
+
static unsigned getHashValue(CallValue Val);
static bool isEqual(CallValue LHS, CallValue RHS);
};
-}
+
+} // end namespace llvm
unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
Instruction *Inst = Val.Inst;
@@ -241,6 +274,7 @@ bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
//===----------------------------------------------------------------------===//
namespace {
+
/// \brief A simple and fast domtree-based CSE pass.
///
/// This pass does a simple depth-first walk over the dominator tree,
@@ -257,10 +291,13 @@ public:
const SimplifyQuery SQ;
MemorySSA *MSSA;
std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
- typedef RecyclingAllocator<
- BumpPtrAllocator, ScopedHashTableVal<SimpleValue, Value *>> AllocatorTy;
- typedef ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
- AllocatorTy> ScopedHTType;
+
+ using AllocatorTy =
+ RecyclingAllocator<BumpPtrAllocator,
+ ScopedHashTableVal<SimpleValue, Value *>>;
+ using ScopedHTType =
+ ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
+ AllocatorTy>;
/// \brief A scoped hash table of the current values of all of our simple
/// scalar expressions.
@@ -285,44 +322,45 @@ public:
/// present the table; it is the responsibility of the consumer to inspect
/// the atomicity/volatility if needed.
struct LoadValue {
- Instruction *DefInst;
- unsigned Generation;
- int MatchingId;
- bool IsAtomic;
- bool IsInvariant;
- LoadValue()
- : DefInst(nullptr), Generation(0), MatchingId(-1), IsAtomic(false),
- IsInvariant(false) {}
+ Instruction *DefInst = nullptr;
+ unsigned Generation = 0;
+ int MatchingId = -1;
+ bool IsAtomic = false;
+ bool IsInvariant = false;
+
+ LoadValue() = default;
LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
bool IsAtomic, bool IsInvariant)
: DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
IsAtomic(IsAtomic), IsInvariant(IsInvariant) {}
};
- typedef RecyclingAllocator<BumpPtrAllocator,
- ScopedHashTableVal<Value *, LoadValue>>
- LoadMapAllocator;
- typedef ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
- LoadMapAllocator> LoadHTType;
+
+ using LoadMapAllocator =
+ RecyclingAllocator<BumpPtrAllocator,
+ ScopedHashTableVal<Value *, LoadValue>>;
+ using LoadHTType =
+ ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
+ LoadMapAllocator>;
+
LoadHTType AvailableLoads;
/// \brief A scoped hash table of the current values of read-only call
/// values.
///
/// It uses the same generation count as loads.
- typedef ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>
- CallHTType;
+ using CallHTType =
+ ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>;
CallHTType AvailableCalls;
/// \brief This is the current generation of the memory value.
- unsigned CurrentGeneration;
+ unsigned CurrentGeneration = 0;
/// \brief Set up the EarlyCSE runner for a particular function.
EarlyCSE(const DataLayout &DL, const TargetLibraryInfo &TLI,
const TargetTransformInfo &TTI, DominatorTree &DT,
AssumptionCache &AC, MemorySSA *MSSA)
: TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(DL, &TLI, &DT, &AC), MSSA(MSSA),
- MSSAUpdater(make_unique<MemorySSAUpdater>(MSSA)), CurrentGeneration(0) {
- }
+ MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
bool run();
@@ -336,11 +374,10 @@ private:
CallHTType &AvailableCalls)
: Scope(AvailableValues), LoadScope(AvailableLoads),
CallScope(AvailableCalls) {}
-
- private:
NodeScope(const NodeScope &) = delete;
- void operator=(const NodeScope &) = delete;
+ NodeScope &operator=(const NodeScope &) = delete;
+ private:
ScopedHTType::ScopeTy Scope;
LoadHTType::ScopeTy LoadScope;
CallHTType::ScopeTy CallScope;
@@ -356,8 +393,10 @@ private:
CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n,
DomTreeNode::iterator child, DomTreeNode::iterator end)
: CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
- EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls),
- Processed(false) {}
+ EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls)
+ {}
+ StackNode(const StackNode &) = delete;
+ StackNode &operator=(const StackNode &) = delete;
// Accessors.
unsigned currentGeneration() { return CurrentGeneration; }
@@ -365,27 +404,25 @@ private:
void childGeneration(unsigned generation) { ChildGeneration = generation; }
DomTreeNode *node() { return Node; }
DomTreeNode::iterator childIter() { return ChildIter; }
+
DomTreeNode *nextChild() {
DomTreeNode *child = *ChildIter;
++ChildIter;
return child;
}
+
DomTreeNode::iterator end() { return EndIter; }
bool isProcessed() { return Processed; }
void process() { Processed = true; }
private:
- StackNode(const StackNode &) = delete;
- void operator=(const StackNode &) = delete;
-
- // Members.
unsigned CurrentGeneration;
unsigned ChildGeneration;
DomTreeNode *Node;
DomTreeNode::iterator ChildIter;
DomTreeNode::iterator EndIter;
NodeScope Scopes;
- bool Processed;
+ bool Processed = false;
};
/// \brief Wrapper class to handle memory instructions, including loads,
@@ -393,24 +430,28 @@ private:
class ParseMemoryInst {
public:
ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
- : IsTargetMemInst(false), Inst(Inst) {
+ : Inst(Inst) {
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
if (TTI.getTgtMemIntrinsic(II, Info))
IsTargetMemInst = true;
}
+
bool isLoad() const {
if (IsTargetMemInst) return Info.ReadMem;
return isa<LoadInst>(Inst);
}
+
bool isStore() const {
if (IsTargetMemInst) return Info.WriteMem;
return isa<StoreInst>(Inst);
}
+
bool isAtomic() const {
if (IsTargetMemInst)
return Info.Ordering != AtomicOrdering::NotAtomic;
return Inst->isAtomic();
}
+
bool isUnordered() const {
if (IsTargetMemInst)
return Info.isUnordered();
@@ -447,6 +488,7 @@ private:
return (getPointerOperand() == Inst.getPointerOperand() &&
getMatchingId() == Inst.getMatchingId());
}
+
bool isValid() const { return getPointerOperand() != nullptr; }
// For regular (non-intrinsic) loads/stores, this is set to -1. For
@@ -457,6 +499,7 @@ private:
if (IsTargetMemInst) return Info.MatchingId;
return -1;
}
+
Value *getPointerOperand() const {
if (IsTargetMemInst) return Info.PtrVal;
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
@@ -466,17 +509,19 @@ private:
}
return nullptr;
}
+
bool mayReadFromMemory() const {
if (IsTargetMemInst) return Info.ReadMem;
return Inst->mayReadFromMemory();
}
+
bool mayWriteToMemory() const {
if (IsTargetMemInst) return Info.WriteMem;
return Inst->mayWriteToMemory();
}
private:
- bool IsTargetMemInst;
+ bool IsTargetMemInst = false;
MemIntrinsicInfo Info;
Instruction *Inst;
};
@@ -524,8 +569,8 @@ private:
for (MemoryPhi *MP : PhisToCheck) {
MemoryAccess *FirstIn = MP->getIncomingValue(0);
- if (all_of(MP->incoming_values(),
- [=](Use &In) { return In == FirstIn; }))
+ if (llvm::all_of(MP->incoming_values(),
+ [=](Use &In) { return In == FirstIn; }))
WorkQueue.push_back(MP);
}
PhisToCheck.clear();
@@ -533,7 +578,8 @@ private:
}
}
};
-}
+
+} // end anonymous namespace
/// Determine if the memory referenced by LaterInst is from the same heap
/// version as EarlierInst.
@@ -1014,6 +1060,7 @@ PreservedAnalyses EarlyCSEPass::run(Function &F,
}
namespace {
+
/// \brief A simple and fast domtree-based CSE pass.
///
/// This pass does a simple depth-first walk over the dominator tree,
@@ -1062,7 +1109,8 @@ public:
AU.setPreservesCFG();
}
};
-}
+
+} // end anonymous namespace
using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
OpenPOWER on IntegriCloud