diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp | 187 |
1 files changed, 64 insertions, 123 deletions
diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp index e0d3a6accadd..eadbb4293539 100644 --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -175,44 +175,6 @@ static cl::opt<bool> using OverlapIntervalsTy = std::map<int64_t, int64_t>; using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>; -/// If the value of this instruction and the memory it writes to is unused, may -/// we delete this instruction? -static bool isRemovable(Instruction *I) { - // Don't remove volatile/atomic stores. - if (StoreInst *SI = dyn_cast<StoreInst>(I)) - return SI->isUnordered(); - - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { - switch (II->getIntrinsicID()) { - default: llvm_unreachable("Does not have LocForWrite"); - case Intrinsic::lifetime_end: - // Never remove dead lifetime_end's, e.g. because it is followed by a - // free. - return false; - case Intrinsic::init_trampoline: - // Always safe to remove init_trampoline. - return true; - case Intrinsic::memset: - case Intrinsic::memmove: - case Intrinsic::memcpy: - case Intrinsic::memcpy_inline: - // Don't remove volatile memory intrinsics. - return !cast<MemIntrinsic>(II)->isVolatile(); - case Intrinsic::memcpy_element_unordered_atomic: - case Intrinsic::memmove_element_unordered_atomic: - case Intrinsic::memset_element_unordered_atomic: - case Intrinsic::masked_store: - return true; - } - } - - // note: only get here for calls with analyzable writes - i.e. libcalls - if (auto *CB = dyn_cast<CallBase>(I)) - return CB->use_empty(); - - return false; -} - /// Returns true if the end of this instruction can be safely shortened in /// length. static bool isShortenableAtTheEnd(Instruction *I) { @@ -835,7 +797,7 @@ struct DSEState { auto *MD = dyn_cast_or_null<MemoryDef>(MA); if (MD && MemDefs.size() < MemorySSADefsPerBlockLimit && - (getLocForWriteEx(&I) || isMemTerminatorInst(&I))) + (getLocForWrite(&I) || isMemTerminatorInst(&I))) MemDefs.push_back(MD); } } @@ -1022,48 +984,39 @@ struct DSEState { return I.first->second; } - Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const { + Optional<MemoryLocation> getLocForWrite(Instruction *I) const { if (!I->mayWriteToMemory()) return None; - if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I)) - return {MemoryLocation::getForDest(MTI)}; + if (auto *CB = dyn_cast<CallBase>(I)) + return MemoryLocation::getForDest(CB, TLI); + + return MemoryLocation::getOrNone(I); + } + + /// Assuming this instruction has a dead analyzable write, can we delete + /// this instruction? + bool isRemovable(Instruction *I) { + assert(getLocForWrite(I) && "Must have analyzable write"); + + // Don't remove volatile/atomic stores. + if (StoreInst *SI = dyn_cast<StoreInst>(I)) + return SI->isUnordered(); if (auto *CB = dyn_cast<CallBase>(I)) { - // If the functions may write to memory we do not know about, bail out. - if (!CB->onlyAccessesArgMemory() && - !CB->onlyAccessesInaccessibleMemOrArgMem()) - return None; + // Don't remove volatile memory intrinsics. + if (auto *MI = dyn_cast<MemIntrinsic>(CB)) + return !MI->isVolatile(); - LibFunc LF; - if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) { - switch (LF) { - case LibFunc_strncpy: - if (const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2))) - return MemoryLocation(CB->getArgOperand(0), - LocationSize::precise(Len->getZExtValue()), - CB->getAAMetadata()); - LLVM_FALLTHROUGH; - case LibFunc_strcpy: - case LibFunc_strcat: - case LibFunc_strncat: - return {MemoryLocation::getAfter(CB->getArgOperand(0))}; - default: - break; - } - } - switch (CB->getIntrinsicID()) { - case Intrinsic::init_trampoline: - return {MemoryLocation::getAfter(CB->getArgOperand(0))}; - case Intrinsic::masked_store: - return {MemoryLocation::getForArgument(CB, 1, TLI)}; - default: - break; - } - return None; + // Never remove dead lifetime intrinsics, e.g. because they are followed + // by a free. + if (CB->isLifetimeStartOrEnd()) + return false; + + return CB->use_empty() && CB->willReturn() && CB->doesNotThrow(); } - return MemoryLocation::getOrNone(I); + return false; } /// Returns true if \p UseInst completely overwrites \p DefLoc @@ -1081,7 +1034,7 @@ struct DSEState { return false; int64_t InstWriteOffset, DepWriteOffset; - if (auto CC = getLocForWriteEx(UseInst)) + if (auto CC = getLocForWrite(UseInst)) return isOverwrite(UseInst, DefInst, *CC, DefLoc, InstWriteOffset, DepWriteOffset) == OW_Complete; return false; @@ -1093,7 +1046,7 @@ struct DSEState { << *Def->getMemoryInst() << ") is at the end the function \n"); - auto MaybeLoc = getLocForWriteEx(Def->getMemoryInst()); + auto MaybeLoc = getLocForWrite(Def->getMemoryInst()); if (!MaybeLoc) { LLVM_DEBUG(dbgs() << " ... could not get location for write.\n"); return false; @@ -1237,30 +1190,14 @@ struct DSEState { /// loop. In particular, this guarantees that it only references a single /// MemoryLocation during execution of the containing function. bool isGuaranteedLoopInvariant(const Value *Ptr) { - auto IsGuaranteedLoopInvariantBase = [this](const Value *Ptr) { - Ptr = Ptr->stripPointerCasts(); - if (auto *I = dyn_cast<Instruction>(Ptr)) { - if (isa<AllocaInst>(Ptr)) - return true; - - if (isAllocLikeFn(I, &TLI)) - return true; - - return false; - } - return true; - }; - Ptr = Ptr->stripPointerCasts(); - if (auto *I = dyn_cast<Instruction>(Ptr)) { - if (I->getParent()->isEntryBlock()) - return true; - } - if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) { - return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) && - GEP->hasAllConstantIndices(); - } - return IsGuaranteedLoopInvariantBase(Ptr); + if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) + if (GEP->hasAllConstantIndices()) + Ptr = GEP->getPointerOperand()->stripPointerCasts(); + + if (auto *I = dyn_cast<Instruction>(Ptr)) + return I->getParent()->isEntryBlock(); + return true; } // Find a MemoryDef writing to \p KillingLoc and dominating \p StartAccess, @@ -1372,7 +1309,7 @@ struct DSEState { // If Current does not have an analyzable write location or is not // removable, skip it. - CurrentLoc = getLocForWriteEx(CurrentI); + CurrentLoc = getLocForWrite(CurrentI); if (!CurrentLoc || !isRemovable(CurrentI)) { CanOptimize = false; continue; @@ -1729,14 +1666,13 @@ struct DSEState { LLVM_DEBUG( dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"); - for (int I = MemDefs.size() - 1; I >= 0; I--) { - MemoryDef *Def = MemDefs[I]; - if (SkipStores.contains(Def) || !isRemovable(Def->getMemoryInst())) + for (MemoryDef *Def : llvm::reverse(MemDefs)) { + if (SkipStores.contains(Def)) continue; Instruction *DefI = Def->getMemoryInst(); - auto DefLoc = getLocForWriteEx(DefI); - if (!DefLoc) + auto DefLoc = getLocForWrite(DefI); + if (!DefLoc || !isRemovable(DefI)) continue; // NOTE: Currently eliminating writes at the end of a function is limited @@ -1763,13 +1699,19 @@ struct DSEState { /// \returns true if \p Def is a no-op store, either because it /// directly stores back a loaded value or stores zero to a calloced object. bool storeIsNoop(MemoryDef *Def, const Value *DefUO) { - StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst()); - MemSetInst *MemSet = dyn_cast<MemSetInst>(Def->getMemoryInst()); + Instruction *DefI = Def->getMemoryInst(); + StoreInst *Store = dyn_cast<StoreInst>(DefI); + MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI); Constant *StoredConstant = nullptr; if (Store) StoredConstant = dyn_cast<Constant>(Store->getOperand(0)); - if (MemSet) + else if (MemSet) StoredConstant = dyn_cast<Constant>(MemSet->getValue()); + else + return false; + + if (!isRemovable(DefI)) + return false; if (StoredConstant && StoredConstant->isNullValue()) { auto *DefUOInst = dyn_cast<Instruction>(DefUO); @@ -1902,7 +1844,7 @@ struct DSEState { bool Changed = false; for (auto OI : IOL) { Instruction *DeadI = OI.first; - MemoryLocation Loc = *getLocForWriteEx(DeadI); + MemoryLocation Loc = *getLocForWrite(DeadI); assert(isRemovable(DeadI) && "Expect only removable instruction"); const Value *Ptr = Loc.Ptr->stripPointerCasts(); @@ -1925,9 +1867,14 @@ struct DSEState { LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the " "already existing value\n"); for (auto *Def : MemDefs) { - if (SkipStores.contains(Def) || MSSA.isLiveOnEntryDef(Def) || - !isRemovable(Def->getMemoryInst())) + if (SkipStores.contains(Def) || MSSA.isLiveOnEntryDef(Def)) continue; + + Instruction *DefInst = Def->getMemoryInst(); + auto MaybeDefLoc = getLocForWrite(DefInst); + if (!MaybeDefLoc || !isRemovable(DefInst)) + continue; + MemoryDef *UpperDef; // To conserve compile-time, we avoid walking to the next clobbering def. // Instead, we just try to get the optimized access, if it exists. DSE @@ -1939,17 +1886,14 @@ struct DSEState { if (!UpperDef || MSSA.isLiveOnEntryDef(UpperDef)) continue; - Instruction *DefInst = Def->getMemoryInst(); Instruction *UpperInst = UpperDef->getMemoryInst(); - auto IsRedundantStore = [this, DefInst, - UpperInst](MemoryLocation UpperLoc) { + auto IsRedundantStore = [&]() { if (DefInst->isIdenticalTo(UpperInst)) return true; if (auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) { if (auto *SI = dyn_cast<StoreInst>(DefInst)) { - auto MaybeDefLoc = getLocForWriteEx(DefInst); - if (!MaybeDefLoc) - return false; + // MemSetInst must have a write location. + MemoryLocation UpperLoc = *getLocForWrite(UpperInst); int64_t InstWriteOffset = 0; int64_t DepWriteOffset = 0; auto OR = isOverwrite(UpperInst, DefInst, UpperLoc, *MaybeDefLoc, @@ -1962,9 +1906,7 @@ struct DSEState { return false; }; - auto MaybeUpperLoc = getLocForWriteEx(UpperInst); - if (!MaybeUpperLoc || !IsRedundantStore(*MaybeUpperLoc) || - isReadClobber(*MaybeUpperLoc, DefInst)) + if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst)) continue; LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *DefInst << '\n'); @@ -1995,7 +1937,7 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, MaybeKillingLoc = State.getLocForTerminator(KillingI).map( [](const std::pair<MemoryLocation, bool> &P) { return P.first; }); else - MaybeKillingLoc = State.getLocForWriteEx(KillingI); + MaybeKillingLoc = State.getLocForWrite(KillingI); if (!MaybeKillingLoc) { LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for " @@ -2059,7 +2001,7 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, if (!DebugCounter::shouldExecute(MemorySSACounter)) continue; - MemoryLocation DeadLoc = *State.getLocForWriteEx(DeadI); + MemoryLocation DeadLoc = *State.getLocForWrite(DeadI); if (IsMemTerm) { const Value *DeadUndObj = getUnderlyingObject(DeadLoc.Ptr); @@ -2124,8 +2066,7 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, } // Check if the store is a no-op. - if (!Shortend && isRemovable(KillingI) && - State.storeIsNoop(KillingDef, KillingUndObj)) { + if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) { LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *KillingI << '\n'); State.deleteDeadInstruction(KillingI); |