LLVM  8.0.0svn
Macros | Typedefs | Enumerations | Functions | Variables
DeadStoreElimination.cpp File Reference
#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.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/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <map>
#include <utility>
Include dependency graph for DeadStoreElimination.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "dse"
 

Typedefs

using OverlapIntervalsTy = std::map< int64_t, int64_t >
 
using InstOverlapIntervalsTy = DenseMap< Instruction *, OverlapIntervalsTy >
 

Enumerations

enum  OverwriteResult
 

Functions

 STATISTIC (NumRedundantStores, "Number of redundant stores deleted")
 
 STATISTIC (NumFastStores, "Number of stores deleted")
 
 STATISTIC (NumFastOther, "Number of other instrs removed")
 
 STATISTIC (NumCompletePartials, "Number of stores dead by later partials")
 
 STATISTIC (NumModifiedStores, "Number of stores modified")
 
static void deleteDeadInstruction (Instruction *I, BasicBlock::iterator *BBI, MemoryDependenceResults &MD, const TargetLibraryInfo &TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction *, size_t > *InstrOrdering, SmallSetVector< Value *, 16 > *ValueSet=nullptr)
 Delete this instruction. More...
 
static bool hasAnalyzableMemoryWrite (Instruction *I, const TargetLibraryInfo &TLI)
 Does this instruction write some memory? This only returns true for things that we can analyze with other helpers below. More...
 
static MemoryLocation getLocForWrite (Instruction *Inst)
 Return a Location stored to by the specified instruction. More...
 
static MemoryLocation getLocForRead (Instruction *Inst, const TargetLibraryInfo &TLI)
 Return the location read by the specified "hasAnalyzableMemoryWrite" instruction if any. More...
 
static bool isRemovable (Instruction *I)
 If the value of this instruction and the memory it writes to is unused, may we delete this instruction? More...
 
static bool isShortenableAtTheEnd (Instruction *I)
 Returns true if the end of this instruction can be safely shortened in length. More...
 
static bool isShortenableAtTheBeginning (Instruction *I)
 Returns true if the beginning of this instruction can be safely shortened in length. More...
 
static ValuegetStoredPointerOperand (Instruction *I)
 Return the pointer that is being written to. More...
 
static uint64_t getPointerSize (const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function *F)
 
static OverwriteResult isOverwrite (const MemoryLocation &Later, const MemoryLocation &Earlier, const DataLayout &DL, const TargetLibraryInfo &TLI, int64_t &EarlierOff, int64_t &LaterOff, Instruction *DepWrite, InstOverlapIntervalsTy &IOL, AliasAnalysis &AA, const Function *F)
 Return 'OW_Complete' if a store to the 'Later' location completely overwrites a store to the 'Earlier' location, 'OW_End' if the end of the 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the beginning of the 'Earlier' location is overwritten by 'Later'. More...
 
static bool isPossibleSelfRead (Instruction *Inst, const MemoryLocation &InstStoreLoc, Instruction *DepWrite, const TargetLibraryInfo &TLI, AliasAnalysis &AA)
 If 'Inst' might be a self read (i.e. More...
 
static bool memoryIsNotModifiedBetween (Instruction *FirstI, Instruction *SecondI, AliasAnalysis *AA)
 Returns true if the memory which is accessed by the second instruction is not modified between the first and the second instruction. More...
 
static void findUnconditionalPreds (SmallVectorImpl< BasicBlock *> &Blocks, BasicBlock *BB, DominatorTree *DT)
 Find all blocks that will unconditionally lead to the block BB and append them to F. More...
 
static bool handleFree (CallInst *F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction *, size_t > *InstrOrdering)
 Handle frees of entire structures whose dependency is a store to a field of that structure. More...
 
static void removeAccessedObjects (const MemoryLocation &LoadedLoc, SmallSetVector< Value *, 16 > &DeadStackObjects, const DataLayout &DL, AliasAnalysis *AA, const TargetLibraryInfo *TLI, const Function *F)
 Check to see if the specified location may alias any of the stack objects in the DeadStackObjects set. More...
 
static bool handleEndBlock (BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction *, size_t > *InstrOrdering)
 Remove dead stores to stack-allocated locations in the function end block. More...
 
static bool tryToShorten (Instruction *EarlierWrite, int64_t &EarlierOffset, int64_t &EarlierSize, int64_t LaterOffset, int64_t LaterSize, bool IsOverwriteEnd)
 
static bool tryToShortenEnd (Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, int64_t &EarlierSize)
 
static bool tryToShortenBegin (Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, int64_t &EarlierSize)
 
static bool removePartiallyOverlappedStores (AliasAnalysis *AA, const DataLayout &DL, InstOverlapIntervalsTy &IOL)
 
static bool eliminateNoopStore (Instruction *Inst, BasicBlock::iterator &BBI, AliasAnalysis *AA, MemoryDependenceResults *MD, const DataLayout &DL, const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction *, size_t > *InstrOrdering)
 
static bool eliminateDeadStores (BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI)
 
static bool eliminateDeadStores (Function &F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI)
 
 INITIALIZE_PASS_BEGIN (DSELegacyPass, "dse", "Dead Store Elimination", false, false) INITIALIZE_PASS_END(DSELegacyPass
 

Variables

static cl::opt< boolEnablePartialOverwriteTracking ("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))
 
static cl::opt< boolEnablePartialStoreMerging ("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))
 
 dse
 
Dead Store Elimination
 
Dead Store false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "dse"

Definition at line 70 of file DeadStoreElimination.cpp.

Typedef Documentation

◆ InstOverlapIntervalsTy

Definition at line 92 of file DeadStoreElimination.cpp.

◆ OverlapIntervalsTy

using OverlapIntervalsTy = std::map<int64_t, int64_t>

Definition at line 91 of file DeadStoreElimination.cpp.

Enumeration Type Documentation

◆ OverwriteResult

Definition at line 326 of file DeadStoreElimination.cpp.

Function Documentation

◆ deleteDeadInstruction()

static void deleteDeadInstruction ( Instruction I,
BasicBlock::iterator BBI,
MemoryDependenceResults MD,
const TargetLibraryInfo TLI,
InstOverlapIntervalsTy IOL,
DenseMap< Instruction *, size_t > *  InstrOrdering,
SmallSetVector< Value *, 16 > *  ValueSet = nullptr 
)
static

◆ eliminateDeadStores() [1/2]

static bool eliminateDeadStores ( BasicBlock BB,
AliasAnalysis AA,
MemoryDependenceResults MD,
DominatorTree DT,
const TargetLibraryInfo TLI 
)
static

Definition at line 1070 of file DeadStoreElimination.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::dbgs(), deleteDeadInstruction(), llvm::dyn_cast(), eliminateNoopStore(), EnablePartialOverwriteTracking, EnablePartialStoreMerging, llvm::BasicBlock::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::erase(), F(), llvm::BasicBlock::front(), llvm::ConstantInt::get(), llvm::APInt::getBitsSet(), llvm::APInt::getBitWidth(), llvm::Module::getDataLayout(), llvm::MemoryDependenceResults::getDefaultBlockScanLimit(), llvm::MemoryDependenceResults::getDependency(), llvm::MemDepResult::getInst(), llvm::ilist_node_impl< OptionsT >::getIterator(), getLocForWrite(), llvm::AAResults::getModRefInfo(), llvm::BasicBlock::getModule(), llvm::Instruction::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::MemoryDependenceResults::getPointerDependencyFrom(), llvm::BasicBlock::getTerminator(), llvm::GetUnderlyingObject(), llvm::LocationSize::getValue(), handleEndBlock(), handleFree(), hasAnalyzableMemoryWrite(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::isAllocLikeFn(), llvm::DataLayout::isBigEndian(), llvm::MemDepResult::isClobber(), llvm::MemDepResult::isDef(), llvm::isFreeCall(), isOverwrite(), isPossibleSelfRead(), llvm::isRefSet(), isRemovable(), isShortenableAtTheBeginning(), isShortenableAtTheEnd(), LLVM_DEBUG, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::BitmaskEnumDetail::Mask(), llvm::Instruction::mayThrow(), llvm::LLVMContext::MD_alias_scope, llvm::LLVMContext::MD_dbg, llvm::LLVMContext::MD_noalias, llvm::LLVMContext::MD_nontemporal, llvm::LLVMContext::MD_tbaa, memoryIsNotModifiedBetween(), OR, llvm::PointerMayBeCaptured(), llvm::MemoryLocation::Ptr, removePartiallyOverlappedStores(), SI, llvm::MemoryLocation::Size, tryToShorten(), llvm::BitmaskEnumDetail::Underlying(), and llvm::APInt::zext().

Referenced by eliminateDeadStores(), and llvm::DSEPass::run().

◆ eliminateDeadStores() [2/2]

static bool eliminateDeadStores ( Function F,
AliasAnalysis AA,
MemoryDependenceResults MD,
DominatorTree DT,
const TargetLibraryInfo TLI 
)
static

◆ eliminateNoopStore()

static bool eliminateNoopStore ( Instruction Inst,
BasicBlock::iterator BBI,
AliasAnalysis AA,
MemoryDependenceResults MD,
const DataLayout DL,
const TargetLibraryInfo TLI,
InstOverlapIntervalsTy IOL,
DenseMap< Instruction *, size_t > *  InstrOrdering 
)
static

◆ findUnconditionalPreds()

static void findUnconditionalPreds ( SmallVectorImpl< BasicBlock *> &  Blocks,
BasicBlock BB,
DominatorTree DT 
)
static

◆ getLocForRead()

static MemoryLocation getLocForRead ( Instruction Inst,
const TargetLibraryInfo TLI 
)
static

Return the location read by the specified "hasAnalyzableMemoryWrite" instruction if any.

Definition at line 222 of file DeadStoreElimination.cpp.

References assert(), llvm::MemoryLocation::getForSource(), and hasAnalyzableMemoryWrite().

Referenced by isPossibleSelfRead().

◆ getLocForWrite()

static MemoryLocation getLocForWrite ( Instruction Inst)
static

Return a Location stored to by the specified instruction.

If isRemovable returns true, this function and getLocForRead completely describe the memory operations for this instruction.

Definition at line 190 of file DeadStoreElimination.cpp.

References llvm::MemoryLocation::get(), llvm::MemoryLocation::getForDest(), MI, and SI.

Referenced by eliminateDeadStores(), getStoredPointerOperand(), and removePartiallyOverlappedStores().

◆ getPointerSize()

static uint64_t getPointerSize ( const Value V,
const DataLayout DL,
const TargetLibraryInfo TLI,
const Function F 
)
static

◆ getStoredPointerOperand()

static Value* getStoredPointerOperand ( Instruction I)
static

Return the pointer that is being written to.

Definition at line 303 of file DeadStoreElimination.cpp.

References assert(), getLocForWrite(), and llvm::MemoryLocation::Ptr.

Referenced by handleEndBlock(), and handleFree().

◆ handleEndBlock()

static bool handleEndBlock ( BasicBlock BB,
AliasAnalysis AA,
MemoryDependenceResults MD,
const TargetLibraryInfo TLI,
InstOverlapIntervalsTy IOL,
DenseMap< Instruction *, size_t > *  InstrOrdering 
)
static

◆ handleFree()

static bool handleFree ( CallInst F,
AliasAnalysis AA,
MemoryDependenceResults MD,
DominatorTree DT,
const TargetLibraryInfo TLI,
InstOverlapIntervalsTy IOL,
DenseMap< Instruction *, size_t > *  InstrOrdering 
)
static

◆ hasAnalyzableMemoryWrite()

static bool hasAnalyzableMemoryWrite ( Instruction I,
const TargetLibraryInfo TLI 
)
static

Does this instruction write some memory? This only returns true for things that we can analyze with other helpers below.

Definition at line 152 of file DeadStoreElimination.cpp.

References F(), llvm::TargetLibraryInfo::getName(), and llvm::TargetLibraryInfo::has().

Referenced by eliminateDeadStores(), getLocForRead(), handleEndBlock(), and handleFree().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( DSELegacyPass  ,
"dse"  ,
"Dead Store Elimination ,
false  ,
false   
)

Referenced by llvm::DSEPass::run().

◆ isOverwrite()

static OverwriteResult isOverwrite ( const MemoryLocation Later,
const MemoryLocation Earlier,
const DataLayout DL,
const TargetLibraryInfo TLI,
int64_t &  EarlierOff,
int64_t &  LaterOff,
Instruction DepWrite,
InstOverlapIntervalsTy IOL,
AliasAnalysis AA,
const Function F 
)
static

Return 'OW_Complete' if a store to the 'Later' location completely overwrites a store to the 'Earlier' location, 'OW_End' if the end of the 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the beginning of the 'Earlier' location is overwritten by 'Later'.

'OW_PartialEarlierWithFullLater' means that an earlier (big) store was overwritten by a latter (smaller) store which doesn't write outside the big store's memory locations. Returns 'OW_Unknown' if nothing can be determined.

Definition at line 343 of file DeadStoreElimination.cpp.

References assert(), llvm::dbgs(), EnablePartialOverwriteTracking, EnablePartialStoreMerging, llvm::GetPointerBaseWithConstantOffset(), getPointerSize(), llvm::GetUnderlyingObject(), llvm::LocationSize::getValue(), llvm::AAResults::isMustAlias(), llvm::LocationSize::isPrecise(), LLVM_DEBUG, llvm::max(), llvm::MemoryLocation::Ptr, llvm::MemoryLocation::Size, llvm::Value::stripPointerCasts(), and llvm::MemoryLocation::UnknownSize.

Referenced by eliminateDeadStores().

◆ isPossibleSelfRead()

static bool isPossibleSelfRead ( Instruction Inst,
const MemoryLocation InstStoreLoc,
Instruction DepWrite,
const TargetLibraryInfo TLI,
AliasAnalysis AA 
)
static

If 'Inst' might be a self read (i.e.

a noop copy of a memory region into an identical pointer) then it doesn't actually make its input dead in the traditional sense. Consider this case:

memmove(A <- B) memmove(A <- A)

In this case, the second store to A does not make the first store to A dead. The usual situation isn't an explicit A<-A store like this (which can be trivially removed) but a case where two pointers may alias.

This function detects when it is unsafe to remove a dependent instruction because the DSE inducing instruction may be a self-read.

Definition at line 540 of file DeadStoreElimination.cpp.

References getLocForRead(), llvm::AAResults::isMustAlias(), llvm::AAResults::isNoAlias(), and llvm::MemoryLocation::Ptr.

Referenced by eliminateDeadStores().

◆ isRemovable()

static bool isRemovable ( Instruction I)
static

If the value of this instruction and the memory it writes to is unused, may we delete this instruction?

Definition at line 235 of file DeadStoreElimination.cpp.

References isVolatile(), llvm_unreachable, and SI.

Referenced by eliminateDeadStores(), eliminateNoopStore(), handleEndBlock(), handleFree(), and removePartiallyOverlappedStores().

◆ isShortenableAtTheBeginning()

static bool isShortenableAtTheBeginning ( Instruction I)
static

Returns true if the beginning of this instruction can be safely shortened in length.

Definition at line 296 of file DeadStoreElimination.cpp.

References I.

Referenced by eliminateDeadStores(), and tryToShortenBegin().

◆ isShortenableAtTheEnd()

static bool isShortenableAtTheEnd ( Instruction I)
static

Returns true if the end of this instruction can be safely shortened in length.

Definition at line 271 of file DeadStoreElimination.cpp.

Referenced by eliminateDeadStores(), and tryToShortenEnd().

◆ memoryIsNotModifiedBetween()

static bool memoryIsNotModifiedBetween ( Instruction FirstI,
Instruction SecondI,
AliasAnalysis AA 
)
static

◆ removeAccessedObjects()

static void removeAccessedObjects ( const MemoryLocation LoadedLoc,
SmallSetVector< Value *, 16 > &  DeadStackObjects,
const DataLayout DL,
AliasAnalysis AA,
const TargetLibraryInfo TLI,
const Function F 
)
static

Check to see if the specified location may alias any of the stack objects in the DeadStackObjects set.

If so, they become live because the location is being loaded.

Definition at line 717 of file DeadStoreElimination.cpp.

References getPointerSize(), llvm::GetUnderlyingObject(), I, llvm::AAResults::isNoAlias(), llvm::MemoryLocation::Ptr, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove(), and llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove_if().

Referenced by handleEndBlock().

◆ removePartiallyOverlappedStores()

static bool removePartiallyOverlappedStores ( AliasAnalysis AA,
const DataLayout DL,
InstOverlapIntervalsTy IOL 
)
static

◆ STATISTIC() [1/5]

STATISTIC ( NumRedundantStores  ,
"Number of redundant stores deleted"   
)

◆ STATISTIC() [2/5]

STATISTIC ( NumFastStores  ,
"Number of stores deleted"   
)

◆ STATISTIC() [3/5]

STATISTIC ( NumFastOther  ,
"Number of other instrs removed"   
)

◆ STATISTIC() [4/5]

STATISTIC ( NumCompletePartials  ,
"Number of stores dead by later partials"   
)

◆ STATISTIC() [5/5]

STATISTIC ( NumModifiedStores  ,
"Number of stores modified"   
)

◆ tryToShorten()

static bool tryToShorten ( Instruction EarlierWrite,
int64_t &  EarlierOffset,
int64_t &  EarlierSize,
int64_t  LaterOffset,
int64_t  LaterSize,
bool  IsOverwriteEnd 
)
static

◆ tryToShortenBegin()

static bool tryToShortenBegin ( Instruction EarlierWrite,
OverlapIntervalsTy IntervalMap,
int64_t &  EarlierStart,
int64_t &  EarlierSize 
)
static

◆ tryToShortenEnd()

static bool tryToShortenEnd ( Instruction EarlierWrite,
OverlapIntervalsTy IntervalMap,
int64_t &  EarlierStart,
int64_t &  EarlierSize 
)
static

Definition at line 956 of file DeadStoreElimination.cpp.

References isShortenableAtTheEnd(), and tryToShorten().

Referenced by removePartiallyOverlappedStores().

Variable Documentation

◆ dse

dse

Definition at line 1394 of file DeadStoreElimination.cpp.

◆ Elimination

Dead Store Elimination

Definition at line 1394 of file DeadStoreElimination.cpp.

◆ EnablePartialOverwriteTracking

cl::opt<bool> EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))
static

Referenced by eliminateDeadStores(), and isOverwrite().

◆ EnablePartialStoreMerging

cl::opt<bool> EnablePartialStoreMerging("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))
static

Referenced by eliminateDeadStores(), and isOverwrite().

◆ false

Dead Store false

Definition at line 1394 of file DeadStoreElimination.cpp.