+/// A helper for handleNonLocalDependency() function to find all blocks
+/// that lead to the input block BB and append them to the output PredBlocks.
+/// PredBlocks will include not only predecessors of BB that unconditionally
+/// lead to BB but also:
+/// - single-block loops that lead to BB, and
+/// - if-blocks for which one edge goes to BB and the other edge goes to
+/// a block in the input SafeBlocks.
+/// PredBlocks will not include blocks unreachable from the entry block, nor
+/// blocks that form cycles with BB.
+static void findSafePreds(SmallVectorImpl<BasicBlock *> &PredBlocks,
+ SmallSetVector<BasicBlock *, 8> &SafeBlocks,
+ BasicBlock *BB, DominatorTree *DT) {
+ for (auto *Pred : predecessors(BB)) {
+ if (Pred == BB)
+ continue;
+ // The second check below prevents adding blocks that form a cycle with BB
+ // in order to avoid potential problems due to MemoryDependenceAnalysis,
+ // isOverwrite, etc. being not loop-aware.
+ if (!DT->isReachableFromEntry(Pred) || DT->dominates(BB, Pred))
+ continue;
+
+ bool PredIsSafe = true;
+ for (auto *Succ : successors(Pred)) {
+ if (Succ == BB || Succ == Pred) // shortcut, BB should be in SafeBlocks
+ continue;
+ if (!SafeBlocks.count(Succ)) {
+ PredIsSafe = false;
+ break;
+ }
+ }
+ if (PredIsSafe)
+ PredBlocks.push_back(Pred);
+ }
+}
+
+static bool underlyingObjectsDoNotAlias(StoreInst *SI, LoadInst *LI,
+ const DataLayout &DL,
+ AliasAnalysis &AA) {
+ Value *AObj = GetUnderlyingObject(SI->getPointerOperand(), DL);
+ SmallVector<Value *, 4> Pointers;
+ GetUnderlyingObjects(LI->getPointerOperand(), Pointers, DL);
+
+ for (auto *BObj : Pointers) {
+ if (!AA.isNoAlias(AObj, DL.getTypeStoreSize(AObj->getType()), BObj,
+ DL.getTypeStoreSize(BObj->getType())))
+ return false;
+ }
+ return true;
+}
+
+/// handleNonLocalDependency - Handle a non-local dependency on
+/// the input instruction Inst located in BB in attempt to remove
+/// redundant stores outside BB.
+bool DSE::handleNonLocalDependency(Instruction *Inst) {
+ auto *SI = dyn_cast<StoreInst>(Inst);
+ if (!SI)
+ return false;
+ // Get the location being stored to.
+ // If we don't get a useful location, bail out.
+ MemoryLocation Loc = getLocForWrite(SI, *AA);
+ if (!Loc.Ptr)
+ return false;
+
+ bool MadeChange = false;
+ BasicBlock *BB = Inst->getParent();
+ const DataLayout &DL = BB->getModule()->getDataLayout();
+
+ // Worklist of predecessor blocks of BB
+ SmallVector<BasicBlock *, 8> Blocks;
+ // Keep track of all predecessor blocks that are safe to search through
+ SmallSetVector<BasicBlock *, 8> SafeBlocks;
+ SafeBlocks.insert(BB);
+ findSafePreds(Blocks, SafeBlocks, BB, DT);
+
+ while (!Blocks.empty()) {
+ BasicBlock *PB = Blocks.pop_back_val();
+ MemDepResult Dep =
+ MD->getPointerDependencyFrom(Loc, false, PB->end(), PB, SI);
+ while (Dep.isDef() || Dep.isClobber()) {
+ Instruction *Dependency = Dep.getInst();
+
+ // Filter out false dependency from a load to SI looking through phis.
+ if (auto *LI = dyn_cast<LoadInst>(Dependency)) {
+ if (underlyingObjectsDoNotAlias(SI, LI, DL, *AA)) {
+ Dep = MD->getPointerDependencyFrom(Loc, false,
+ Dependency->getIterator(), PB, SI);
+ continue;
+ }
+ }
+
+ // If we don't get a useful location for the dependent instruction,
+ // it doesn't write memory, it is not removable, or it might read Loc,
+ // then bail out.
+ MemoryLocation DepLoc = getLocForWrite(Dependency, *AA);
+ if (!DepLoc.Ptr || !hasMemoryWrite(Dependency, *TLI) ||
+ !isRemovable(Dependency) ||
+ (AA->getModRefInfo(Dependency, Loc) & MRI_Ref))
+ break;
+
+ // Don't remove a store within single-block loops;
+ // we need more analysis: e.g. looking for an interferring load
+ // above the store within the loop, etc.
+ bool SingleBlockLoop = false;
+ for (auto I = succ_begin(PB), E = succ_end(PB); I != E; ++I) {
+ BasicBlock *Succ = *I;
+ if (Succ == PB) {
+ SingleBlockLoop = true;
+ break;
+ }
+ }
+ if (SingleBlockLoop)
+ break;
+
+ int64_t InstWriteOffset, DepWriteOffset;
+ OverwriteResult OR =
+ isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset);
+ if (OR == OverwriteComplete) {
+ DEBUG(dbgs() << "DSE: Remove Non-Local Dead Store:\n DEAD: "
+ << *Dependency << "\n KILLER: " << *SI << '\n');
+
+ // Delete redundant store and now-dead instructions that feed it.
+ auto Next = std::next(Dependency->getIterator());
+ DeleteDeadInstruction(Dependency, *MD, *TLI);
+ ++NumNonLocalStores;
+ MadeChange = true;
+ Dep = MD->getPointerDependencyFrom(Loc, false, Next, PB, SI);
+ continue;
+ }
+ // TODO: attempt shortening of Dependency inst as in the local case
+ break;
+ }
+
+ if (Dep.isNonLocal()) {
+ SafeBlocks.insert(PB);
+ findSafePreds(Blocks, SafeBlocks, PB, DT);
+ }
+ }
+
+ return MadeChange;
+}
+
+/// Returns true if the memory which is accessed by the second instruction is not
+/// modified between the first and the second instruction.
+/// Precondition: Second instruction must be dominated by the first
+/// instruction.
+bool DSE::MemoryIsNotModifiedBetween(Instruction *FirstI,
+ Instruction *SecondI) {
+ SmallVector<BasicBlock *, 16> WorkList;
+ SmallPtrSet<BasicBlock *, 8> Visited;
+ BasicBlock::iterator FirstBBI(FirstI);
+ ++FirstBBI;
+ BasicBlock::iterator SecondBBI(SecondI);
+ BasicBlock *FirstBB = FirstI->getParent();
+ BasicBlock *SecondBB = SecondI->getParent();
+ MemoryLocation MemLoc = MemoryLocation::get(SecondI);
+
+ // Start checking the store-block.
+ WorkList.push_back(SecondBB);
+ bool isFirstBlock = true;
+
+ // Check all blocks going backward until we reach the load-block.
+ while (!WorkList.empty()) {
+ BasicBlock *B = WorkList.pop_back_val();
+
+ // Ignore instructions before LI if this is the FirstBB.
+ BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
+
+ BasicBlock::iterator EI;
+ if (isFirstBlock) {
+ // Ignore instructions after SI if this is the first visit of SecondBB.
+ assert(B == SecondBB && "first block is not the store block");
+ EI = SecondBBI;
+ isFirstBlock = false;
+ } else {
+ // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
+ // In this case we also have to look at instructions after SI.
+ EI = B->end();
+ }
+ for (; BI != EI; ++BI) {
+ Instruction *I = &*BI;
+ if (I->mayWriteToMemory() && I != SecondI) {
+ auto Res = AA->getModRefInfo(I, MemLoc);
+ if (Res != MRI_NoModRef)
+ return false;
+ }
+ }
+ if (B != FirstBB) {
+ assert(B != &FirstBB->getParent()->getEntryBlock() &&
+ "Should not hit the entry block because SI must be dominated by LI");
+ for (auto *PredI : predecessors(B)) {
+ if (!Visited.insert(PredI).second)
+ continue;
+ WorkList.push_back(PredI);
+ }
+ }
+ }
+ return true;
+}
+