LLVM 20.0.0git
|
#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/ConstantRangeList.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.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/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Value.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/raw_ostream.h"
#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <map>
#include <optional>
#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 | isShortenableAtTheEnd (Instruction *I) |
Returns true if the end of this instruction can be safely shortened in length. | |
static bool | isShortenableAtTheBeginning (Instruction *I) |
Returns true if the beginning of this instruction can be safely shortened in length. | |
static std::optional< TypeSize > | 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. | |
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'. | |
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. | |
static void | shortenAssignment (Instruction *Inst, Value *OriginalDest, uint64_t OldOffsetInBits, uint64_t OldSizeInBits, uint64_t NewSizeInBits, bool IsOverwriteEnd) |
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 Constant * | tryToMergePartialOverlappingStores (StoreInst *KillingI, StoreInst *DeadI, int64_t KillingOffset, int64_t DeadOffset, const DataLayout &DL, BatchAAResults &AA, DominatorTree *DT) |
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.")) |
static cl::opt< bool > | EnableInitializesImprovement ("enable-dse-initializes-attr-improvement", cl::init(false), cl::Hidden, cl::desc("Enable the initializes attr improvement in DSE")) |
#define DEBUG_TYPE "dse" |
Definition at line 90 of file DeadStoreElimination.cpp.
using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy> |
Definition at line 176 of file DeadStoreElimination.cpp.
using OverlapIntervalsTy = std::map<int64_t, int64_t> |
Definition at line 175 of file DeadStoreElimination.cpp.
DEBUG_COUNTER | ( | MemorySSACounter | , |
"dse-memoryssa" | , | ||
"Controls which MemoryDefs are eliminated." | |||
) |
|
static |
Definition at line 211 of file DeadStoreElimination.cpp.
References DL, F, llvm::TypeSize::getFixed(), llvm::getObjectSize(), llvm::ObjectSizeOpts::NullIsUnknownSize, llvm::NullPointerIsDefined(), and Size.
|
static |
Check if two instruction are masked stores that completely overwrite one another.
More specifically, KillingI
has to overwrite DeadI
.
Definition at line 241 of file DeadStoreElimination.cpp.
References llvm::BatchAAResults::isMustAlias(), and llvm::Value::stripPointerCasts().
|
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 284 of file DeadStoreElimination.cpp.
References assert(), llvm::dbgs(), EnablePartialOverwriteTracking, EnablePartialStoreMerging, llvm::LocationSize::getValue(), LLVM_DEBUG, and llvm::MemoryLocation::Size.
|
static |
Returns true if the beginning of this instruction can be safely shortened in length.
Definition at line 205 of file DeadStoreElimination.cpp.
References I.
Referenced by tryToShortenBegin().
|
static |
Returns true if the end of this instruction can be safely shortened in length.
Definition at line 180 of file DeadStoreElimination.cpp.
Referenced by tryToShortenEnd().
|
static |
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.
Definition at line 402 of file DeadStoreElimination.cpp.
References Addr, assert(), B, DL, llvm::SmallVectorBase< Size_T >::empty(), llvm::MemoryLocation::get(), llvm::PHITransAddr::getAddr(), llvm::Function::getEntryBlock(), llvm::MemoryLocation::getForDest(), llvm::BatchAAResults::getModRefInfo(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getParent(), llvm::MemoryLocation::getWithNewPtr(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::isModSet(), llvm::PHITransAddr::isPotentiallyPHITranslatable(), llvm::PHITransAddr::needsPHITranslationFromBlock(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), llvm::MemoryLocation::Ptr, Ptr, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::PHITransAddr::translateValue().
Referenced by tryToMergePartialOverlappingStores().
|
static |
Definition at line 489 of file DeadStoreElimination.cpp.
References llvm::at::calculateFragmentIntersect(), llvm::DIExpression::createFragmentExpression(), DL, llvm::for_each(), llvm::at::getAssignmentMarkers(), llvm::Value::getContext(), llvm::Instruction::getDataLayout(), llvm::DIAssignID::getDistinct(), and llvm::at::getDVRAssignmentMarkers().
Referenced by tryToShorten().
STATISTIC | ( | NumCFGChecks | , |
"Number of stores modified" | |||
) |
STATISTIC | ( | NumCFGSuccess | , |
"Number of stores modified" | |||
) |
STATISTIC | ( | NumCFGTries | , |
"Number of stores modified" | |||
) |
STATISTIC | ( | NumCompletePartials | , |
"Number of stores dead by later partials" | |||
) |
STATISTIC | ( | NumDomMemDefChecks | , |
"Number iterations check for reads in getDomMemoryDef" | |||
) |
STATISTIC | ( | NumFastOther | , |
"Number of other instrs removed" | |||
) |
STATISTIC | ( | NumFastStores | , |
"Number of stores deleted" | |||
) |
STATISTIC | ( | NumGetDomMemoryDefPassed | , |
"Number of times a valid candidate is returned from getDomMemoryDef" | |||
) |
STATISTIC | ( | NumModifiedStores | , |
"Number of stores modified" | |||
) |
STATISTIC | ( | NumRedundantStores | , |
"Number of redundant stores deleted" | |||
) |
STATISTIC | ( | NumRemainingStores | , |
"Number of stores remaining after DSE" | |||
) |
|
static |
Definition at line 718 of file DeadStoreElimination.cpp.
References assert(), llvm::dbgs(), DL, llvm::APInt::getBitsSet(), llvm::APInt::getBitWidth(), llvm::Value::getType(), llvm::StoreInst::getValueOperand(), LLVM_DEBUG, memoryIsNotModifiedBetween(), and llvm::APInt::zext().
|
static |
Definition at line 566 of file DeadStoreElimination.cpp.
References assert(), llvm::GetElementPtrInst::CreateInBounds(), llvm::dbgs(), llvm::Type::getInt8Ty(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getType(), llvm::isAligned(), LLVM_DEBUG, llvm::offsetToAlignment(), llvm::Instruction::setDebugLoc(), shortenAssignment(), and llvm::Align::value().
Referenced by tryToShortenBegin(), and tryToShortenEnd().
|
static |
Definition at line 688 of file DeadStoreElimination.cpp.
References assert(), llvm::IntervalMap< KeyT, ValT, N, Traits >::begin(), llvm::IntervalMap< KeyT, ValT, N, Traits >::empty(), isShortenableAtTheBeginning(), and tryToShorten().
|
static |
Definition at line 661 of file DeadStoreElimination.cpp.
References assert(), llvm::IntervalMap< KeyT, ValT, N, Traits >::empty(), llvm::IntervalMap< KeyT, ValT, N, Traits >::end(), isShortenableAtTheEnd(), and tryToShorten().
|
static |
|
static |
Referenced by isPartialOverwrite().
|
static |
Referenced by isPartialOverwrite().
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |