LLVM  14.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/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/MustExecute.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/IRBuilder.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/BuildLibCalls.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 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 *KillingI, const Instruction *DeadI, BatchAAResults &AA)
 Check if two instruction are masked stores that completely overwrite one another. More...
 
static OverwriteResult isPartialOverwrite (const MemoryLocation &KillingLoc, const MemoryLocation &DeadLoc, int64_t KillingOff, int64_t DeadOff, Instruction *DeadI, InstOverlapIntervalsTy &IOL)
 Return 'OW_Complete' if a store to the 'KillingLoc' location completely overwrites a store to the 'DeadLoc' location, 'OW_End' if the end of the 'DeadLoc' location is completely overwritten by 'KillingLoc', 'OW_Begin' if the beginning of the 'DeadLoc' location is overwritten by 'KillingLoc'. 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 *DeadI, int64_t &DeadStart, uint64_t &DeadSize, int64_t KillingStart, uint64_t KillingSize, bool IsOverwriteEnd)
 
static bool tryToShortenEnd (Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize)
 
static bool tryToShortenBegin (Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize)
 
static ConstanttryToMergePartialOverlappingStores (StoreInst *KillingI, StoreInst *DeadI, int64_t KillingOffset, int64_t DeadOffset, 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 = 150)"))
 
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)"))
 
static cl::opt< bool > OptimizeMemorySSA ("dse-optimize-memoryssa", cl::init(true), cl::Hidden, cl::desc("Allow DSE to optimize memory accesses."))
 
 dse
 
Dead Store Elimination
 
Dead Store false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "dse"

Definition at line 95 of file DeadStoreElimination.cpp.

Typedef Documentation

◆ InstOverlapIntervalsTy

Definition at line 176 of file DeadStoreElimination.cpp.

◆ OverlapIntervalsTy

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

Definition at line 175 of file DeadStoreElimination.cpp.

Function Documentation

◆ DEBUG_COUNTER()

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

◆ getPointerSize()

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

◆ INITIALIZE_PASS_BEGIN()

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

◆ isMaskedStoreOverwrite()

static OverwriteResult isMaskedStoreOverwrite ( const Instruction KillingI,
const Instruction DeadI,
BatchAAResults AA 
)
static

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

More specifically, KillingI has to overwrite DeadI.

Definition at line 278 of file DeadStoreElimination.cpp.

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

◆ isPartialOverwrite()

static OverwriteResult isPartialOverwrite ( const MemoryLocation KillingLoc,
const MemoryLocation DeadLoc,
int64_t  KillingOff,
int64_t  DeadOff,
Instruction DeadI,
InstOverlapIntervalsTy IOL 
)
static

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

'OW_PartialEarlierWithFullLater' means that a dead (big) store was overwritten by a killing (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 KillingLoc and DeadLoc belong to the same underlying object with valid KillingOff and DeadOff.

Definition at line 310 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 180 of file DeadStoreElimination.cpp.

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

◆ isShortenableAtTheBeginning()

static bool isShortenableAtTheBeginning ( Instruction I)
static

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

Definition at line 243 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 218 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

◆ 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 KillingI,
StoreInst DeadI,
int64_t  KillingOffset,
int64_t  DeadOffset,
const DataLayout DL,
BatchAAResults AA,
DominatorTree DT 
)
static

◆ tryToShorten()

static bool tryToShorten ( Instruction DeadI,
int64_t &  DeadStart,
uint64_t DeadSize,
int64_t  KillingStart,
uint64_t  KillingSize,
bool  IsOverwriteEnd 
)
static

◆ tryToShortenBegin()

static bool tryToShortenBegin ( Instruction DeadI,
OverlapIntervalsTy IntervalMap,
int64_t &  DeadStart,
uint64_t DeadSize 
)
static

◆ tryToShortenEnd()

static bool tryToShortenEnd ( Instruction DeadI,
OverlapIntervalsTy IntervalMap,
int64_t &  DeadStart,
uint64_t DeadSize 
)
static

Variable Documentation

◆ dse

dse

Definition at line 2214 of file DeadStoreElimination.cpp.

◆ Elimination

Dead Store Elimination

Definition at line 2214 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 2214 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 = 150)"))
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

◆ OptimizeMemorySSA

cl::opt<bool> OptimizeMemorySSA("dse-optimize-memoryssa", cl::init(true), cl::Hidden, cl::desc("Allow DSE to optimize memory accesses."))
static