LLVM  13.0.0git
Macros | Typedefs | 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/MapVector.h"
#include "llvm/ADT/PostOrderIterator.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/MemoryLocation.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.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/InstIterator.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/PatternMatch.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <map>
#include <utility>

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 >
 

Functions

 STATISTIC (NumRemainingStores, "Number of stores remaining after DSE")
 
 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")
 
 STATISTIC (NumCFGChecks, "Number of stores modified")
 
 STATISTIC (NumCFGTries, "Number of stores modified")
 
 STATISTIC (NumCFGSuccess, "Number of stores modified")
 
 STATISTIC (NumGetDomMemoryDefPassed, "Number of times a valid candidate is returned from getDomMemoryDef")
 
 STATISTIC (NumDomMemDefChecks, "Number iterations check for reads in getDomMemoryDef")
 
 DEBUG_COUNTER (MemorySSACounter, "dse-memoryssa", "Controls which MemoryDefs are eliminated.")
 
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, const TargetLibraryInfo &TLI)
 Return a Location stored to by the specified instruction. 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 uint64_t getPointerSize (const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function *F)
 
static OverwriteResult isMaskedStoreOverwrite (const Instruction *Later, const Instruction *Earlier, BatchAAResults &AA)
 Check if two instruction are masked stores that completely overwrite one another. More...
 
static OverwriteResult isPartialOverwrite (const MemoryLocation &Later, const MemoryLocation &Earlier, int64_t EarlierOff, int64_t LaterOff, Instruction *DepWrite, InstOverlapIntervalsTy &IOL)
 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 memoryIsNotModifiedBetween (Instruction *FirstI, Instruction *SecondI, BatchAAResults &AA, const DataLayout &DL, DominatorTree *DT)
 Returns true if the memory which is accessed by the second instruction is not modified between the first and the second instruction. More...
 
static bool tryToShorten (Instruction *EarlierWrite, int64_t &EarlierStart, uint64_t &EarlierSize, int64_t LaterStart, uint64_t LaterSize, bool IsOverwriteEnd)
 
static bool tryToShortenEnd (Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, uint64_t &EarlierSize)
 
static bool tryToShortenBegin (Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, uint64_t &EarlierSize)
 
static bool removePartiallyOverlappedStores (const DataLayout &DL, InstOverlapIntervalsTy &IOL, const TargetLibraryInfo &TLI)
 
static ConstanttryToMergePartialOverlappingStores (StoreInst *Earlier, StoreInst *Later, int64_t InstWriteOffset, int64_t DepWriteOffset, const DataLayout &DL, BatchAAResults &AA, DominatorTree *DT)
 
 INITIALIZE_PASS_BEGIN (DSELegacyPass, "dse", "Dead Store Elimination", false, false) INITIALIZE_PASS_END(DSELegacyPass
 

Variables

static cl::opt< bool > EnablePartialOverwriteTracking ("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))
 
static cl::opt< bool > EnablePartialStoreMerging ("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))
 
static cl::opt< unsigned > MemorySSAScanLimit ("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden, cl::desc("The number of memory instructions to scan for " "dead store elimination (default = 100)"))
 
static cl::opt< unsigned > MemorySSAUpwardsStepLimit ("dse-memoryssa-walklimit", cl::init(90), cl::Hidden, cl::desc("The maximum number of steps while walking upwards to find " "MemoryDefs that may be killed (default = 90)"))
 
static cl::opt< unsigned > MemorySSAPartialStoreLimit ("dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden, cl::desc("The maximum number candidates that only partially overwrite the " "killing MemoryDef to consider" " (default = 5)"))
 
static cl::opt< unsigned > MemorySSADefsPerBlockLimit ("dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden, cl::desc("The number of MemoryDefs we consider as candidates to eliminated " "other stores per basic block (default = 5000)"))
 
static cl::opt< unsigned > MemorySSASameBBStepCost ("dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden, cl::desc("The cost of a step in the same basic block as the killing MemoryDef" "(default = 1)"))
 
static cl::opt< unsigned > MemorySSAOtherBBStepCost ("dse-memoryssa-otherbb-cost", cl::init(5), cl::Hidden, cl::desc("The cost of a step in a different basic " "block than the killing MemoryDef" "(default = 5)"))
 
static cl::opt< unsigned > MemorySSAPathCheckLimit ("dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden, cl::desc("The maximum number of blocks to check when trying to prove that " "all paths to an exit go through a killing block (default = 50)"))
 
 dse
 
Dead Store Elimination
 
Dead Store false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "dse"

Definition at line 91 of file DeadStoreElimination.cpp.

Typedef Documentation

◆ InstOverlapIntervalsTy

Definition at line 162 of file DeadStoreElimination.cpp.

◆ OverlapIntervalsTy

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

Definition at line 161 of file DeadStoreElimination.cpp.

Function Documentation

◆ DEBUG_COUNTER()

DEBUG_COUNTER ( MemorySSACounter  ,
"dse-memoryssa ,
"Controls which MemoryDefs are eliminated."   
)

◆ getLocForWrite()

static MemoryLocation getLocForWrite ( Instruction Inst,
const TargetLibraryInfo TLI 
)
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 207 of file DeadStoreElimination.cpp.

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

Referenced by removePartiallyOverlappedStores().

◆ getPointerSize()

static uint64_t getPointerSize ( const Value V,
const DataLayout DL,
const TargetLibraryInfo TLI,
const Function F 
)
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 166 of file DeadStoreElimination.cpp.

References llvm::TargetLibraryInfo::getLibFunc(), llvm::TargetLibraryInfo::has(), I, and memcpy().

◆ INITIALIZE_PASS_BEGIN()

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

◆ isMaskedStoreOverwrite()

static OverwriteResult isMaskedStoreOverwrite ( const Instruction Later,
const Instruction Earlier,
BatchAAResults AA 
)
static

Check if two instruction are masked stores that completely overwrite one another.

More specifically, Later has to overwrite Earlier.

Definition at line 336 of file DeadStoreElimination.cpp.

References llvm::BatchAAResults::isMustAlias(), and llvm::Value::stripPointerCasts().

◆ isPartialOverwrite()

static OverwriteResult isPartialOverwrite ( const MemoryLocation Later,
const MemoryLocation Earlier,
int64_t  EarlierOff,
int64_t  LaterOff,
Instruction DepWrite,
InstOverlapIntervalsTy IOL 
)
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. NOTE: This function must only be called if both Later and Earlier write to the same underlying object with valid EarlierOff and LaterOff.

Definition at line 368 of file DeadStoreElimination.cpp.

References assert(), llvm::dbgs(), EnablePartialOverwriteTracking, EnablePartialStoreMerging, llvm::LocationSize::getValue(), LLVM_DEBUG, llvm::max(), llvm::min(), and llvm::MemoryLocation::Size.

◆ 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 239 of file DeadStoreElimination.cpp.

References I, llvm_unreachable, memcpy(), and SI.

Referenced by 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 302 of file DeadStoreElimination.cpp.

References I.

Referenced by 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 277 of file DeadStoreElimination.cpp.

References I, and memcpy().

Referenced by tryToShortenEnd().

◆ memoryIsNotModifiedBetween()

static bool memoryIsNotModifiedBetween ( Instruction FirstI,
Instruction SecondI,
BatchAAResults AA,
const DataLayout DL,
DominatorTree DT 
)
static

◆ removePartiallyOverlappedStores()

static bool removePartiallyOverlappedStores ( const DataLayout DL,
InstOverlapIntervalsTy IOL,
const TargetLibraryInfo TLI 
)
static

◆ STATISTIC() [1/11]

STATISTIC ( NumCFGChecks  ,
"Number of stores modified"   
)

◆ STATISTIC() [2/11]

STATISTIC ( NumCFGSuccess  ,
"Number of stores modified"   
)

◆ STATISTIC() [3/11]

STATISTIC ( NumCFGTries  ,
"Number of stores modified"   
)

◆ STATISTIC() [4/11]

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

◆ STATISTIC() [5/11]

STATISTIC ( NumDomMemDefChecks  ,
"Number iterations check for reads in getDomMemoryDef"   
)

◆ STATISTIC() [6/11]

STATISTIC ( NumFastOther  ,
"Number of other instrs removed  
)

◆ STATISTIC() [7/11]

STATISTIC ( NumFastStores  ,
"Number of stores deleted"   
)

◆ STATISTIC() [8/11]

STATISTIC ( NumGetDomMemoryDefPassed  ,
"Number of times a valid candidate is returned from getDomMemoryDef"   
)

◆ STATISTIC() [9/11]

STATISTIC ( NumModifiedStores  ,
"Number of stores modified"   
)

◆ STATISTIC() [10/11]

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

◆ STATISTIC() [11/11]

STATISTIC ( NumRemainingStores  ,
"Number of stores remaining after DSE"   
)

◆ tryToMergePartialOverlappingStores()

static Constant* tryToMergePartialOverlappingStores ( StoreInst Earlier,
StoreInst Later,
int64_t  InstWriteOffset,
int64_t  DepWriteOffset,
const DataLayout DL,
BatchAAResults AA,
DominatorTree DT 
)
static

◆ tryToShorten()

static bool tryToShorten ( Instruction EarlierWrite,
int64_t &  EarlierStart,
uint64_t &  EarlierSize,
int64_t  LaterStart,
uint64_t  LaterSize,
bool  IsOverwriteEnd 
)
static

◆ tryToShortenBegin()

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

◆ tryToShortenEnd()

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

Variable Documentation

◆ dse

dse

Definition at line 2098 of file DeadStoreElimination.cpp.

◆ Elimination

Dead Store Elimination

Definition at line 2098 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 isPartialOverwrite().

◆ 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 isPartialOverwrite().

◆ false

Dead Store false

Definition at line 2098 of file DeadStoreElimination.cpp.

◆ MemorySSADefsPerBlockLimit

cl::opt<unsigned> MemorySSADefsPerBlockLimit("dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden, cl::desc("The number of MemoryDefs we consider as candidates to eliminated " "other stores per basic block (default = 5000)"))
static

◆ MemorySSAOtherBBStepCost

cl::opt<unsigned> MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5), cl::Hidden, cl::desc("The cost of a step in a different basic " "block than the killing MemoryDef" "(default = 5)"))
static

◆ MemorySSAPartialStoreLimit

cl::opt<unsigned> MemorySSAPartialStoreLimit("dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden, cl::desc("The maximum number candidates that only partially overwrite the " "killing MemoryDef to consider" " (default = 5)"))
static

◆ MemorySSAPathCheckLimit

cl::opt<unsigned> MemorySSAPathCheckLimit("dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden, cl::desc("The maximum number of blocks to check when trying to prove that " "all paths to an exit go through a killing block (default = 50)"))
static

◆ MemorySSASameBBStepCost

cl::opt<unsigned> MemorySSASameBBStepCost("dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden, cl::desc( "The cost of a step in the same basic block as the killing MemoryDef" "(default = 1)"))
static

◆ MemorySSAScanLimit

cl::opt<unsigned> MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden, cl::desc("The number of memory instructions to scan for " "dead store elimination (default = 100)"))
static

◆ MemorySSAUpwardsStepLimit

cl::opt<unsigned> MemorySSAUpwardsStepLimit("dse-memoryssa-walklimit", cl::init(90), cl::Hidden, cl::desc("The maximum number of steps while walking upwards to find " "MemoryDefs that may be killed (default = 90)"))
static