Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

Differential D72182 Diff 236201 llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

Changeset View

Standalone View

View Options

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

Show All 12 Lines
// traversal. Doing so would be pretty trivial. // traversal. Doing so would be pretty trivial.
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar/DeadStoreElimination.h" #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
#include "llvm/ADT/APInt.h" #include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h" #include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h" #include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h" #include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h" #include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h" #include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h" #include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h" #include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h" #include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h" #include "llvm/IR/DataLayout.h"
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 LinesEnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
cl::init(true), cl::Hidden, cl::init(true), cl::Hidden,
cl::desc("Enable partial-overwrite tracking in DSE")); cl::desc("Enable partial-overwrite tracking in DSE"));
static cl::opt<bool> static cl::opt<bool>
EnablePartialStoreMerging("enable-dse-partial-store-merging", EnablePartialStoreMerging("enable-dse-partial-store-merging",
cl::init(true), cl::Hidden, cl::init(true), cl::Hidden,
cl::desc("Enable partial store merging in DSE")); cl::desc("Enable partial store merging in DSE"));
static cl::opt<bool>
EnableMemorySSA("enable-dse-memoryssa", cl::init(false), cl::Hidden,
cl::desc("Use the new MemorySSA-backed DSE."));
static cl::opt<unsigned>
MaxDSEIteration("dse-max-iteration", cl::init(24), cl::Hidden,
cl::desc("Maximum number of iteration for graph traversal "
"operation inside MemorySSA-backed DSE"));
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// Helper functions // Helper functions
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
using OverlapIntervalsTy = std::map<int64_t, int64_t>; using OverlapIntervalsTy = std::map<int64_t, int64_t>;
using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>; using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>;
/// Delete this instruction. Before we do, go through and zero out all the /// Delete this instruction. Before we do, go through and zero out all the
/// operands of this instruction. If any of them become dead, delete them and /// operands of this instruction. If any of them become dead, delete them and
▲ Show 20 Lines • Show All 1,243 Lines • ▼ Show 20 Lines for (BasicBlock &BB : F)
// Only check non-dead blocks. Dead blocks may have strange pointer // Only check non-dead blocks. Dead blocks may have strange pointer
// cycles that will confuse alias analysis. // cycles that will confuse alias analysis.
if (DT->isReachableFromEntry(&BB)) if (DT->isReachableFromEntry(&BB))
MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI); MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
return MadeChange; return MadeChange;
} }
namespace {
bool isIncomplete(MemoryLocation Loc) { return !Loc.Ptr; }
/// Check if I is a volatile operation.
/// FIXME: Maybe this should be moved to Value.
bool isVolatile(Instruction *I) {
if (auto *SI = dyn_cast<StoreInst>(I))
return SI->isVolatile();
if (auto *LI = dyn_cast<LoadInst>(I))
return LI->isVolatile();
if (auto *MemOp = dyn_cast<AnyMemIntrinsic>(I))
return MemOp->isVolatile();
return false;
}
struct DSEContext {
Function &F;
AliasAnalysis &AA;
MemorySSA &MSSA;
DominatorTree &DT;
PostDominatorTree &PDT;
const TargetLibraryInfo &TLI;
bool MadeChange = false;
/// Index associated of an instruction. it can be used to know the ordering of
/// instruction in a basic block. indexes are in reverse order.
using InstIndex = unsigned;
/// All instruction instruction that can act as an optimization barrier.
/// eg: throw, fence, atomics ...
/// Those barrier are used to not prevent transformation removal of a store
/// being overriden by another store when an optimization barrier
/// could be executed between the two stores.
/// They are not garanted to prevent optimization based on a non-escaping
/// pointer not being used.
SmallVector<InstIndex, 16> OptBarrierInst;
/// StoreInst or memory intrinsics that writes to memory. mapped to there
/// index in there basic block.
SmallDenseMap<Instruction *, InstIndex, 32> InstructionIndex;
enum DSECandidateFlags : unsigned {
DCF_NormalStore = 0,
DCF_LifetimeEndLike = 1,
};
using DSECandidate = PointerIntPair<Instruction *, 2>;
SmallVector<DSECandidate, 16> DSECandidates;
/// Set of pointer we know to be non-escaping.
/// non-escaping mean that at the end of the function the value store at there
/// address is not observable.
SmallSet<const Value *, 16> NonEscapingPtr;
/// state we need to keep track of for every BasicBlock.
struct BBState {
/// Instruction index of the first/last instruction in the basic block that
/// is an optimization barrier.
unsigned FirstBarrierIdx;
unsigned LastBarrierIdx;
/// Its the PostOrder index of the BasicBlock. it is used to detect
/// backedges.
InstIndex BlockPostOrder;
};
/// Map of BasicBlocks to there state. [First, Last[ OptBarrierInst.
SmallDenseMap<BasicBlock *, BBState, 16> BBStateMap;
/// isOveride needs this, but it is currently unused.
InstOverlapIntervalsTy IOL;
DSEContext(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
: F(F), AA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI) {}
bool run();
void deleteDeadInstruction(Instruction *I);
MemoryLocation getWriteLoc(Instruction *I) {
assert(I->mayWriteToMemory());
return getLocForWrite(I);
}
MemoryLocation getReadLoc(Instruction *I) {
assert(I->mayReadFromMemory() && !isEndLifetimeLike(I));
if (auto *LI = dyn_cast<LoadInst>(I))
return MemoryLocation::get(LI);
// TODO: extend the definition. to handle libray functions and builtins.
return MemoryLocation();
}
enum BarrierPlacement { BP_Before, BP_After };
/// check if there is any Instruction form the OptBarrierInst
/// before or after in the current BasicBlock.
template <BarrierPlacement BP> bool hasOptBarrier(Instruction *I) {
BBState &BBS = BBStateMap[I->getParent()];
if (BBS.FirstBarrierIdx == BBS.LastBarrierIdx)
return false;
if (BP == BP_Before)
return InstructionIndex[I] < OptBarrierInst[BBS.FirstBarrierIdx];
assert(BP == BP_After);
return InstructionIndex[I] > OptBarrierInst[BBS.LastBarrierIdx - 1];
}
bool isFullOverrite(const MemoryLocation &Loc, Instruction *I) {
assert(mustWriteToMemory(I));
MemoryLocation OtherLoc = getWriteLoc(I);
int64_t DeadOffset, KillerOffset;
OverwriteResult OR =
isOverwriteWrapper(OtherLoc, Loc, KillerOffset, DeadOffset, I);
return OR == OW_Complete;
}
static Instruction *getMemInst(const MemoryAccess *MA) {
if (!MA)
return nullptr;
if (auto *UOD = dyn_cast<MemoryUseOrDef>(MA))
return UOD->getMemoryInst();
return nullptr;
}
OverwriteResult isOverwriteWrapper(const MemoryLocation &Later,
const MemoryLocation &Earlier,
int64_t &LaterOff, int64_t &EarlierOff,
Instruction *LaterWrite) {
if (isEndLifetimeLike(LaterWrite)) {
if (GetUnderlyingObject(Earlier.Ptr, F.getParent()->getDataLayout()) ==
GetUnderlyingObject(Later.Ptr, F.getParent()->getDataLayout()))
return OW_Complete;
return OW_Unknown;
}
return isOverwrite(Later, Earlier, F.getParent()->getDataLayout(), TLI,
EarlierOff, LaterOff, LaterWrite, IOL, AA, &F);
}
bool mustWriteToMemory(Instruction *I) {
if (!I->mayWriteToMemory())
return false;
if (auto *Intr = dyn_cast<AnyMemIntrinsic>(I)) {
switch (Intr->getIntrinsicID()) {
case Intrinsic::memcpy:
case Intrinsic::memset:
case Intrinsic::memmove:
case Intrinsic::memcpy_element_unordered_atomic:
case Intrinsic::memset_element_unordered_atomic:
case Intrinsic::memmove_element_unordered_atomic:
/// This is not strictly a write but treating it as such does exactly
/// what we want.
case Intrinsic::lifetime_end:
return true;
default:
return false;
}
}
/// For calls we don't know if they actually write to memory just if they
/// can.
if (isa<CallBase>(I) && !isEndLifetimeLike(I))
return false;
return true;
}
bool hasLoadUsersInFunction(
MemoryAccess *Start, const MemoryLocation &FirstLoc,
SmallDenseMap<BasicBlock *, MemoryAccess *, 8> &LastAccessOfPath,
bool isNonEscapingPtr) {
SmallSet<MemoryAccess *, 8> Visited;
SmallVector<User *, 8> WL;
unsigned Iterations = 0;
Visited.insert(Start);
WL.append(Start->user_begin(), Start->user_end());
while (!WL.empty()) {
if (WL.size() + Iterations++ >= MaxDSEIteration)
return true;
MemoryAccess *MA = cast_or_null<MemoryAccess>(WL.pop_back_val());
if (Visited.find(MA) != Visited.end())
return true;
if (!MA)
continue;
Visited.insert(MA);
if (Instruction *Access = getMemInst(MA)) {
if (isOptBarrier(Access))
return true;
if (Access->mayReadFromMemory() && !isEndLifetimeLike(Access)) {
MemoryLocation Loc = getReadLoc(Access);
if (isIncomplete(Loc) || !AA.isNoAlias(Loc, FirstLoc))
return true;
}
if (mustWriteToMemory(Access) && isFullOverrite(FirstLoc, Access)) {
LastAccessOfPath[MA->getBlock()] = MA;
continue;
}
}
if (!isa<MemoryUse>(MA)) {
if (MA->user_empty() && !isNonEscapingPtr)
return true;
WL.append(MA->user_begin(), MA->user_end());
}
}
return false;
}
/// Check If there is an optimization barrier and if all LastAccessOfPath
/// together post-dominate First.
bool hasOptBarrierInReachableBB(
SmallDenseMap<BasicBlock *, MemoryAccess *, 8> &LastAccessOfPath,
Instruction *First, bool isNonEscapingPtr) {
// TODO: When a path from the non-escaping pointer reaches the end of the
// function. we do not need to check for optimization barrier because they
// will not skip any overriding instruction as there is none in this case.
// Currently we always check for optimization barriers event when we don't
// need to.
/// Special case for overrite in the same block in the right order.
/// If instruction are in the reverse order we trying to remove stores in a
/// loop so we need to check all reachble basic blocks.
auto SameBBIterator = LastAccessOfPath.find(First->getParent());
if (SameBBIterator != LastAccessOfPath.end()) {
if (isNonEscapingPtr && SameBBIterator->second->user_empty())
return false;
unsigned FirstIdx = InstructionIndex[First];
unsigned LastIdx = InstructionIndex[getMemInst(SameBBIterator->second)];
if (FirstIdx > LastIdx) {
assert(LastAccessOfPath.size() == 1);
BBState &BBS = BBStateMap[First->getParent()];
if (BBS.FirstBarrierIdx == BBS.LastBarrierIdx)
return false;
for (unsigned Idx = BBS.FirstBarrierIdx; Idx < BBS.LastBarrierIdx;
Idx++)
if (OptBarrierInst[Idx] < FirstIdx && OptBarrierInst[Idx] > LastIdx)
return true;
return false;
}
}
/// We know that the elimination doesn't occur in the same block or the if
/// above would have been taken.
if (!isNonEscapingPtr && succ_empty(First->getParent())) {
assert(LastAccessOfPath.empty());
return true;
}
if (hasOptBarrier<BP_After>(First))
return true;
SmallSet<BasicBlock *, 8> VisitedBB;
SmallVector<BasicBlock *, 8> WL;
/// BasicBlock this set of BasicBlock postdominate the BasicBlock of First
/// and a LastAccessOfPath. It is used to reduce the search
/// space of the following DFS algorithm. When this block is reached it can
/// be treated as a end of function.
/// This set is only used for function with many BasicBlocks.
SmallSet<BasicBlock *, 8> EndOfSearchSpace;
unsigned Iterations = 0;
if (BBStateMap.size() > MaxDSEIteration)
for (auto Elem : LastAccessOfPath) {
BasicBlock *PostDom =
PDT.findNearestCommonDominator(Elem.first, First->getParent());
if (PostDom && PostDom != Elem.first)
EndOfSearchSpace.insert(PostDom);
}
WL.append(succ_begin(First->getParent()), succ_end(First->getParent()));
while (!WL.empty()) {
if (WL.size() + Iterations++ >= MaxDSEIteration)
return true;
BasicBlock *N = WL.pop_back_val();
assert(N);
if (VisitedBB.find(N) != VisitedBB.end())
continue;
VisitedBB.insert(N);
auto LookupResult = LastAccessOfPath.find(N);
if (LookupResult != LastAccessOfPath.end()) {
if (hasOptBarrier<BP_Before>(getMemInst(LookupResult->second)))
return true;
continue;
}
/// If we are here this block is entirely traversed.
BBState &BBS = BBStateMap[N];
if (BBS.FirstBarrierIdx != BBS.LastBarrierIdx)
return true;
if (succ_empty(N) || EndOfSearchSpace.find(N) != EndOfSearchSpace.end()) {
/// We have reached an exit of the function or equivalent. if the
/// pointer can escape the function it is observable.
if (isNonEscapingPtr)
continue;
else
return true;
}
WL.append(succ_begin(N), succ_end(N));
}
return false;
}
bool isEndLifetimeLike(Instruction *I) {
if (auto *Intrinsic = dyn_cast<IntrinsicInst>(I)) {
return Intrinsic->getIntrinsicID() == Intrinsic::lifetime_end;
}
if (auto *Call = dyn_cast<CallBase>(I)) {
if (isFreeCall(I, &TLI))
return true;
}
return false;
}
DSECandidate getDSECandidate(Instruction *I) {
if (isVolatile(I) || I->isAtomic())
return {nullptr, DCF_NormalStore};
if (auto *SI = dyn_cast<StoreInst>(I))
return {I, DCF_NormalStore};
if (isEndLifetimeLike(I))
return {I, DCF_LifetimeEndLike};
/// TODO : make DSE remove handle calls too.
return {nullptr, DCF_NormalStore};
}
bool isOptBarrier(Instruction *I) {
if (isEndLifetimeLike(I))
return false;
return I->mayThrow() || I->isAtomic();
}
};
void DSEContext::deleteDeadInstruction(Instruction *I) {
MadeChange = true;
SmallVector<Instruction *, 32> NowDeadInsts;
MemorySSAUpdater MSSAUpdater(&MSSA);
NowDeadInsts.push_back(I);
--NumFastOther;
InstructionIndex.erase(I);
do {
Instruction *DeadInst = NowDeadInsts.pop_back_val();
++NumFastOther;
// Try to preserve debug information attached to the dead instruction.
salvageDebugInfo(*DeadInst);
// This instruction is dead, zap it, in stages. Start by removing it from
// MemDep, which needs to know the operands and needs it to be in the
// function.
MSSAUpdater.removeMemoryAccess(DeadInst);
for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
Value *Op = DeadInst->getOperand(op);
DeadInst->setOperand(op, nullptr);
// If this operand just became dead, add it to the NowDeadInsts list.
if (!Op->use_empty())
continue;
if (Instruction *OpI = dyn_cast<Instruction>(Op))
if (isInstructionTriviallyDead(OpI, &TLI))
NowDeadInsts.push_back(OpI);
}
DeadInst->eraseFromParent();
} while (!NowDeadInsts.empty());
}
// Expand the set of non-escaping pointer by propagating the property down there
// use chain.
static void PropagateNonEscaping(SmallSet<const Value *, 16> &NonEscapingPtr) {
SmallVector<const Value *, 32> WL;
WL.append(NonEscapingPtr.begin(), NonEscapingPtr.end());
while (!WL.empty()) {
const Value *V = WL.pop_back_val();
NonEscapingPtr.insert(V);
assert(V->getType()->isPointerTy());
for (const User *U : V->users()) {
if (auto *I = dyn_cast<Instruction>(U)) {
switch (I->getOpcode()) {
case Instruction::GetElementPtr:
case Instruction::BitCast:
WL.push_back(I);
break;
case Instruction::PHI:
if (llvm::all_of(
I->operand_values(), [&NonEscapingPtr](const Value *Op) {
assert(Op->getType()->isPointerTy());
return NonEscapingPtr.find(Op) != NonEscapingPtr.end();
}))
WL.push_back(I);
break;
default:
if (auto *Call = dyn_cast<CallBase>(I))
if (V == Call->getReturnedArgOperand()) {
WL.push_back(I);
break;
}
/// TODO: there is propably many other ways to propagate down the
/// use chain.
}
}
}
}
}
bool DSEContext::run() {
InstIndex FuncIdx = 0;
/// Build the various data structures that are needed for DSE.
for (BasicBlock *BB : post_order(&F)) {
unsigned BBStartOptBarrier = OptBarrierInst.size();
if (DT.isReachableFromEntry(BB))
for (Instruction &I : reverse(*BB)) {
/// We can know they are non-escaping.
if (isa<AllocaInst>(&I))
NonEscapingPtr.insert(&I);
else if (isAllocationFn(&I, &TLI) &&
!PointerMayBeCaptured(&I, true, true))
NonEscapingPtr.insert(&I);
if (isOptBarrier(&I))
OptBarrierInst.push_back(FuncIdx);
if (I.mayReadOrWriteMemory())
InstructionIndex.insert(std::make_pair(&I, FuncIdx));
DSECandidate Cand = getDSECandidate(&I);
if (Cand.getPointer())
DSECandidates.push_back(Cand);
FuncIdx++;
}
BBState &State = BBStateMap[BB];
State.FirstBarrierIdx = BBStartOptBarrier;
State.LastBarrierIdx = OptBarrierInst.size();
State.BlockPostOrder = FuncIdx++;
}
for (Argument &Arg : F.args())
if (Arg.hasByValOrInAllocaAttr())
NonEscapingPtr.insert(&Arg);
PropagateNonEscaping(NonEscapingPtr);
/// Map containing the Last Access of each Path.
SmallDenseMap<BasicBlock *, MemoryAccess *, 8> LastAccessOfPath;
/// Element are pushed in the DSECandidate in post order so looking at the in
/// reverse order gives iterate in normal order. which is easier for debuging.
for (DSECandidate Cand : reverse(DSECandidates)) {
/// Check if the instruction hasn't already been deleted.
if (InstructionIndex.find(Cand.getPointer()) == InstructionIndex.end())
continue;
MemoryLocation CandLoc = getWriteLoc(Cand.getPointer());
/// Check if we may have enough information the optimize the store.
if (isIncomplete(CandLoc))
continue;
MemoryAccess *MA = MSSA.getMemoryAccess(Cand.getPointer());
if (Cand.getInt() & DCF_LifetimeEndLike) {
// traverseMemSSA(MA, Cand.getPointer(), CandLoc, 6);
continue;
}
bool isNonEscapingPtr =
NonEscapingPtr.find(CandLoc.Ptr) != NonEscapingPtr.end();
LastAccessOfPath.clear();
if (!hasLoadUsersInFunction(MA, CandLoc, LastAccessOfPath,
isNonEscapingPtr) &&
!hasOptBarrierInReachableBB(LastAccessOfPath, Cand.getPointer(),
isNonEscapingPtr)) {
NumFastStores++;
deleteDeadInstruction(Cand.getPointer());
}
}
return MadeChange;
}
} // namespace
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// DSE Pass // DSE Pass
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) { PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
AliasAnalysis *AA = &AM.getResult<AAManager>(F); AliasAnalysis &AA = AM.getResult<AAManager>(F);
DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F); const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
MemoryDependenceResults *MD = &AM.getResult<MemoryDependenceAnalysis>(F); DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
const TargetLibraryInfo *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
if (EnableMemorySSA) {
MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
if (!eliminateDeadStores(F, AA, MD, DT, TLI)) if (!std::make_unique<DSEContext>(F, AA, MSSA, DT, PDT, TLI)->run())
return PreservedAnalyses::all(); return PreservedAnalyses::all();
} else {
MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
if (!eliminateDeadStores(F, &AA, &MD, &DT, &TLI))
return PreservedAnalyses::all();
}
PreservedAnalyses PA; PreservedAnalyses PA;
PA.preserveSet<CFGAnalyses>(); PA.preserveSet<CFGAnalyses>();
PA.preserve<GlobalsAA>(); PA.preserve<GlobalsAA>();
if (EnableMemorySSA)
PA.preserve<MemorySSAAnalysis>();
else
PA.preserve<MemoryDependenceAnalysis>(); PA.preserve<MemoryDependenceAnalysis>();
return PA; return PA;
} }
namespace { namespace {
/// A legacy pass for the legacy pass manager that wraps \c DSEPass. /// A legacy pass for the legacy pass manager that wraps \c DSEPass.
class DSELegacyPass : public FunctionPass { class DSELegacyPass : public FunctionPass {
public: public:
static char ID; // Pass identification, replacement for typeid static char ID; // Pass identification, replacement for typeid
DSELegacyPass() : FunctionPass(ID) { DSELegacyPass() : FunctionPass(ID) {
initializeDSELegacyPassPass(*PassRegistry::getPassRegistry()); initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
} }
bool runOnFunction(Function &F) override { bool runOnFunction(Function &F) override {
if (skipFunction(F)) if (skipFunction(F))
return false; return false;
DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
MemoryDependenceResults *MD = const TargetLibraryInfo &TLI =
&getAnalysis<MemoryDependenceWrapperPass>().getMemDep(); getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
const TargetLibraryInfo *TLI =
&getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); if (EnableMemorySSA) {
MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
PostDominatorTree &PDT =
getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
return eliminateDeadStores(F, AA, MD, DT, TLI); return std::make_unique<DSEContext>(F, AA, MSSA, DT, PDT, TLI)->run();
} else {
MemoryDependenceResults &MD =
getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
return eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
}
} }
void getAnalysisUsage(AnalysisUsage &AU) const override { void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG(); AU.setPreservesCFG();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<AAResultsWrapperPass>(); AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<MemoryDependenceWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>(); AU.addRequired<TargetLibraryInfoWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>(); AU.addPreserved<GlobalsAAWrapperPass>();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
if (EnableMemorySSA) {
AU.addRequired<PostDominatorTreeWrapperPass>();
AU.addRequired<MemorySSAWrapperPass>();
AU.addPreserved<PostDominatorTreeWrapperPass>();
AU.addPreserved<MemorySSAWrapperPass>();
} else {
AU.addRequired<MemoryDependenceWrapperPass>();
AU.addPreserved<MemoryDependenceWrapperPass>(); AU.addPreserved<MemoryDependenceWrapperPass>();
} }
}
}; };
} // end anonymous namespace } // end anonymous namespace
char DSELegacyPass::ID = 0; char DSELegacyPass::ID = 0;
INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false, INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
false) false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false, INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,
false) false)
FunctionPass *llvm::createDeadStoreEliminationPass() { FunctionPass *llvm::createDeadStoreEliminationPass() {
return new DSELegacyPass(); return new DSELegacyPass();
} }