-
-/// isSafeCandidateForDeletion- Check all paths from the SrcBlock till
-/// SinkBlock to see if Store 'SI' is safe to be remove.
-/// Returns true if the candidate store SI is safe to delete
-/// else returns false.
-bool DSE::isSafeCandidateForDeletion(BasicBlock *SrcBlock,
- BasicBlock *SinkBlock, StoreInst *SI) {
- SmallVector<BasicBlock *, 16> WorkList;
- SmallPtrSet<BasicBlock *, 8> Visited;
- BasicBlock::iterator BBI(SI);
-
- // Check from the store till end of block and make sure we have no references
- // to memory stored by this Store Instruction.
- for (auto BI = ++BBI, BE = SrcBlock->end(); BI != BE; ++BI) {
- Instruction *I = BI;
- StoreInst *CSI = dyn_cast<StoreInst>(I);
- if (CSI) {
- AliasResult R =
- AA->alias(MemoryLocation::get(SI), MemoryLocation::get(CSI));
- if (R == MustAlias)
- return true;
- } else {
- ModRefInfo Res = AA->getModRefInfo(I, MemoryLocation::get(SI));
- if (Res != MRI_NoModRef)
- return false;
- }
- }
-
- // Add successors of the block to stack and start DFS.
- for (succ_iterator I = succ_begin(SrcBlock), E = succ_end(SrcBlock); I != E;
- ++I) {
- if (!Visited.insert(*I).second)
- continue;
- // A path with backedge may not be safe. Conservatively mark
- // this store unsafe.
- if (BackEdgesMap.count(std::make_pair(SrcBlock, *I)))
- return false;
- WorkList.push_back(*I);
- }
-
- while (!WorkList.empty()) {
- BasicBlock *B = WorkList.pop_back_val();
- auto BI = B->begin();
- auto BE = B->end();
- for (; BI != BE; ++BI) {
- Instruction *I = BI;
- StoreInst *CSI = dyn_cast<StoreInst>(I);
- if (CSI) {
- AliasResult R =
- AA->alias(MemoryLocation::get(SI), MemoryLocation::get(CSI));
- if (R == MustAlias)
- break;
- } else {
- ModRefInfo Res = AA->getModRefInfo(I, MemoryLocation::get(SI));
- if (Res != MRI_NoModRef)
- return false;
- }
- }
-
- // If we reached the sink node or we found a block which has a stores that
- // overwrites the candidate block we need not look at their successors.
- if (B == SinkBlock || BI != BE)
- continue;
-
- for (succ_iterator I = succ_begin(B), E = succ_end(B); I != E; ++I) {
- if (!Visited.insert(*I).second)
- continue;
- // A path with backedge may not be safe.Conservatively mark
- // this store unsafe.
- if (BackEdgesMap.count(std::make_pair(B, *I)))
- return false;
- WorkList.push_back(*I);
- }
- }
-
- return true;
-}
-
-/// handleNonLocalStoreDeletion - Handle non local dead store elimination.
-/// This works by finding candidate stores using PDT and then running DFS
-/// from candidate store block checking all paths to make sure the store is
-/// safe to delete.
-void DSE::handleNonLocalStoreDeletion(StoreInst *SI, BasicBlock::iterator &BBI,
- BasicBlock &CurBlock) {
- BasicBlock *BB = SI->getParent();
- Value *Pointer = SI->getPointerOperand();
- DomTreeNode *DTNode = PDT->getNode(BB);
- if (!DTNode)
- return;
-
- int DFSNumIn = DTNode->getDFSNumIn();
- int DFSNumOut = DTNode->getDFSNumOut();
- for (int i = DFSNumIn + 1; i < DFSNumOut; ++i) {
- for (auto &I : Candidates[i]) {
- StoreInst *CandidateSI = I;
- if (DeadStores.count(CandidateSI))
- continue;
- Value *MemPtr = CandidateSI->getPointerOperand();
- if (!MemPtr)
- continue;
- if (Pointer->getType() != MemPtr->getType())
- continue;
- AliasResult R =
- AA->alias(MemoryLocation::get(SI), MemoryLocation::get(CandidateSI));
- if (R != MustAlias)
- continue;
- if (isSafeCandidateForDeletion(CandidateSI->getParent(), BB,
- CandidateSI)) {
- DeleteDeadInstruction(CandidateSI, *MD, *TLI);
- ++NumCrossBlockStores;
- // DeleteDeadInstruction can delete the current instruction in loop
- // cases, reset BBI.
- BBI = SI;
- if (BBI != CurBlock.begin())
- --BBI;
- }
- }
- }
-}