Go to the documentation of this file.
40 #define DEBUG_TYPE "loadstore-opt"
44 using namespace MIPatternMatch;
46 STATISTIC(NumStoresMerged,
"Number of stores merged");
65 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
88 Info.IsIndexSignExt =
false;
94 Info.Offset = RHSCst->Value.getSExtValue();
98 Info.IndexReg = PtrAddRHS;
99 Info.IsIndexSignExt =
false;
107 auto *LdSt1 = dyn_cast<GLoadStore>(&MI1);
108 auto *LdSt2 = dyn_cast<GLoadStore>(&MI2);
109 if (!LdSt1 || !LdSt2)
118 int64_t Size1 = LdSt1->getMemSize();
119 int64_t Size2 = LdSt2->getMemSize();
134 IsAlias = !(Size1 <= PtrDiff);
142 IsAlias = !((PtrDiff + Size2) <= 0);
154 if (!Base0Def || !Base1Def)
158 if (Base0Def->getOpcode() != Base1Def->getOpcode())
161 if (Base0Def->getOpcode() == TargetOpcode::G_FRAME_INDEX) {
165 if (Base0Def != Base1Def &&
175 if (Base0Def->getOpcode() == TargetOpcode::G_GLOBAL_VALUE) {
176 auto GV0 = Base0Def->getOperand(1).getGlobal();
177 auto GV1 = Base1Def->getOperand(1).getGlobal();
192 struct MemUseCharacteristics {
201 auto getCharacteristics =
203 if (
const auto *
LS = dyn_cast<GLoadStore>(
MI)) {
209 BaseReg =
LS->getPointerReg();
214 LS->getMMO().getMemoryType().getSizeInBytes());
215 return {
LS->isVolatile(),
LS->isAtomic(), BaseReg,
225 MemUseCharacteristics MUC0 = getCharacteristics(&
MI),
226 MUC1 = getCharacteristics(&
Other);
229 if (MUC0.BasePtr.isValid() && MUC0.BasePtr == MUC1.BasePtr &&
230 MUC0.Offset == MUC1.Offset)
234 if (MUC0.IsVolatile && MUC1.IsVolatile)
239 if (MUC0.IsAtomic && MUC1.IsAtomic)
244 if (MUC0.MMO && MUC1.MMO) {
245 if ((MUC0.MMO->isInvariant() && MUC1.MMO->isStore()) ||
246 (MUC1.MMO->isInvariant() && MUC0.MMO->isStore()))
257 if (!MUC0.MMO || !MUC1.MMO)
261 int64_t SrcValOffset0 = MUC0.MMO->getOffset();
262 int64_t SrcValOffset1 = MUC1.MMO->getOffset();
265 if (AA && MUC0.MMO->getValue() && MUC1.MMO->getValue() &&
269 int64_t MinOffset =
std::min(SrcValOffset0, SrcValOffset1);
270 int64_t Overlap0 = Size0 + SrcValOffset0 - MinOffset;
271 int64_t Overlap1 = Size1 + SrcValOffset1 - MinOffset;
273 MUC0.MMO->getAAInfo()),
275 MUC1.MMO->getAAInfo())))
286 return MI.hasUnmodeledSideEffects() ||
MI.hasOrderedMemoryRef();
292 assert(StoresToMerge.size() > 1 &&
"Expected multiple stores to merge");
293 LLT OrigTy = MRI->
getType(StoresToMerge[0]->getValueReg());
294 LLT PtrTy = MRI->
getType(StoresToMerge[0]->getPointerReg());
297 initializeStoreMergeTargetInfo(AS);
298 const auto &LegalSizes = LegalStoreSizes[AS];
301 for (
auto *StoreMI : StoresToMerge)
306 bool AnyMerged =
false;
311 unsigned MergeSizeBits;
312 for (MergeSizeBits = MaxSizeBits; MergeSizeBits > 1; MergeSizeBits /= 2) {
316 if (LegalSizes.size() > MergeSizeBits && LegalSizes[MergeSizeBits] &&
324 unsigned NumStoresToMerge = MergeSizeBits / OrigTy.
getSizeInBits();
327 StoresToMerge.begin(), StoresToMerge.begin() + NumStoresToMerge);
328 AnyMerged |= doSingleStoreMerge(SingleMergeStores);
329 StoresToMerge.erase(StoresToMerge.begin(),
330 StoresToMerge.begin() + NumStoresToMerge);
331 }
while (StoresToMerge.size() > 1);
335 bool LoadStoreOpt::isLegalOrBeforeLegalizer(
const LegalityQuery &Query,
345 assert(Stores.size() > 1);
351 GStore *FirstStore = Stores[0];
352 const unsigned NumStores = Stores.size();
358 DebugLoc MergedLoc = Stores.front()->getDebugLoc();
369 for (
auto *
Store : Stores) {
373 ConstantVals.
clear();
382 if (ConstantVals.empty()) {
389 assert(ConstantVals.size() == NumStores);
391 if (!isLegalOrBeforeLegalizer({TargetOpcode::G_CONSTANT, {WideValueTy}}, *MF))
394 for (
unsigned Idx = 0; Idx < ConstantVals.size(); ++Idx) {
397 WideConst.insertBits(ConstantVals[Idx], Idx * SmallTy.
getSizeInBits());
404 NumStoresMerged += Stores.size();
411 R <<
"Merged " <<
NV(
"NumMerged", Stores.size()) <<
" stores of "
413 <<
" bytes into a single store of "
418 for (
auto *
MI : Stores)
419 InstsToErase.insert(
MI);
423 bool LoadStoreOpt::processMergeCandidate(StoreMergeCandidate &
C) {
424 if (
C.Stores.size() < 2) {
429 LLVM_DEBUG(
dbgs() <<
"Checking store merge candidate with " <<
C.Stores.size()
430 <<
" stores, starting with " << *
C.Stores[0]);
444 auto DoesStoreAliasWithPotential = [&](
unsigned Idx,
GStore &CheckStore) {
445 for (
auto AliasInfo :
reverse(
C.PotentialAliases)) {
447 unsigned PreCheckedIdx = AliasInfo.second;
448 if (
static_cast<unsigned>(Idx) > PreCheckedIdx) {
467 for (
int StoreIdx =
C.Stores.size() - 1; StoreIdx >= 0; --StoreIdx) {
468 auto *CheckStore =
C.Stores[StoreIdx];
469 if (DoesStoreAliasWithPotential(StoreIdx, *CheckStore))
475 <<
" stores remaining after alias checks. Merging...\n");
479 if (StoresToMerge.size() < 2)
481 return mergeStores(StoresToMerge);
484 bool LoadStoreOpt::operationAliasesWithCandidate(
MachineInstr &
MI,
485 StoreMergeCandidate &
C) {
486 if (
C.Stores.empty())
489 return instMayAlias(MI, *OtherMI, *MRI, AA);
493 void LoadStoreOpt::StoreMergeCandidate::addPotentialAlias(
MachineInstr &
MI) {
494 PotentialAliases.emplace_back(std::make_pair(&
MI, Stores.size() - 1));
497 bool LoadStoreOpt::addStoreToCandidate(
GStore &StoreMI,
498 StoreMergeCandidate &
C) {
522 if (
C.Stores.empty()) {
528 C.BasePtr = StoreBase;
529 C.CurrentLowestOffset = StoreOffCst;
530 C.Stores.emplace_back(&StoreMI);
531 LLVM_DEBUG(
dbgs() <<
"Starting a new merge candidate group with: "
547 if (
C.BasePtr != StoreBase)
554 C.Stores.emplace_back(&StoreMI);
561 bool Changed =
false;
563 StoreMergeCandidate Candidate;
565 if (InstsToErase.contains(&
MI))
568 if (
auto *StoreMI = dyn_cast<GStore>(&
MI)) {
571 if (!addStoreToCandidate(*StoreMI, Candidate)) {
574 if (operationAliasesWithCandidate(*StoreMI, Candidate)) {
575 Changed |= processMergeCandidate(Candidate);
578 Candidate.addPotentialAlias(*StoreMI);
584 if (Candidate.Stores.empty())
589 Changed |= processMergeCandidate(Candidate);
590 Candidate.Stores.clear();
594 if (!
MI.mayLoadOrStore())
597 if (operationAliasesWithCandidate(
MI, Candidate)) {
600 Changed |= processMergeCandidate(Candidate);
606 Candidate.addPotentialAlias(
MI);
610 Changed |= processMergeCandidate(Candidate);
613 for (
auto *
MI : InstsToErase)
614 MI->eraseFromParent();
615 InstsToErase.clear();
620 bool Changed =
false;
621 for (
auto &
BB : MF) {
622 Changed |= mergeBlockStores(
BB);
627 void LoadStoreOpt::initializeStoreMergeTargetInfo(
unsigned AddrSpace) {
632 if (LegalStoreSizes.count(AddrSpace)) {
633 assert(LegalStoreSizes[AddrSpace].
any());
654 LegalSizes.set(Size);
656 assert(LegalSizes.any() &&
"Expected some store sizes to be legal!");
657 LegalStoreSizes[AddrSpace] = LegalSizes;
670 bool Changed =
false;
671 Changed |= mergeFunctionStores(MF);
673 LegalStoreSizes.clear();
Helper struct to store a base, index and offset that forms an address.
void setMF(MachineFunction &MF)
bool hasProperty(Property P) const
MachineInstr * getDefIgnoringCopies(Register Reg, const MachineRegisterInfo &MRI)
Find the def instruction for Reg, folding away any trivial copies.
This is an optimization pass for GlobalISel generic memory operations.
void setDebugLoc(const DebugLoc &DL)
Set the debug location to DL for all the next build instructions.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
operand_type_match m_Reg()
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
LegalizeAction Action
The action to take or the final answer.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
std::optional< ValueAndVReg > getIConstantVRegValWithLookThrough(Register VReg, const MachineRegisterInfo &MRI, bool LookThroughInstrs=true)
If VReg is defined by a statically evaluable chain of instructions rooted on a G_CONSTANT returns its...
MachineMemOperand * getMachineMemOperand(MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, uint64_t s, Align base_alignment, const AAMDNodes &AAInfo=AAMDNodes(), const MDNode *Ranges=nullptr, SyncScope::ID SSID=SyncScope::System, AtomicOrdering Ordering=AtomicOrdering::NotAtomic, AtomicOrdering FailureOrdering=AtomicOrdering::NotAtomic)
getMachineMemOperand - Allocate a new MachineMemOperand.
Register getValueReg() const
Get the stored value register.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias.
static constexpr LLT scalar(unsigned SizeInBits)
Get a low-level scalar or aggregate "bag of bits".
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
BaseIndexOffset getPointerInfo(Register Ptr, MachineRegisterInfo &MRI)
Returns a BaseIndexOffset which describes the pointer in Ptr.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
The instances of the Type class are immutable: once they are created, they are never changed.
uint64_t getMemSizeInBits() const
Returns the size in bits of the memory access.
A description of a memory reference used in the backend.
DiagnosticInfoOptimizationBase::Argument NV
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
void setInstr(MachineInstr &MI)
Set the insertion point to before MI.
virtual bool canMergeStoresTo(unsigned AS, EVT MemVT, const MachineFunction &MF) const
Returns if it's reasonable to merge stores to MemVT size.
static uint64_t getSizeOrUnknown(const TypeSize &T)
Predicate any(Predicate P0, Predicate P1)
True iff P0 or P1 are true.
BinaryOp_match< LHS, RHS, TargetOpcode::G_PTR_ADD, false > m_GPtrAdd(const LHS &L, const RHS &R)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val)
Build and insert Res = G_CONSTANT Val.
INITIALIZE_PASS_BEGIN(LoadStoreOpt, DEBUG_TYPE, "Generic memory optimizations", false, false) INITIALIZE_PASS_END(LoadStoreOpt
LLT getLLTForType(Type &Ty, const DataLayout &DL)
Construct a low-level type based on an LLVM type.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
uint64_t PowerOf2Floor(uint64_t A)
Returns the power of two which is less than or equal to the given value.
(vector float) vec_cmpeq(*A, *B) C
Represent the analysis usage information of a pass.
const MachineFunctionProperties & getProperties() const
Get the function properties.
bool isSimple() const
Returns true if the memory operation is neither atomic or volatile.
constexpr bool isScalar() const
STATISTIC(NumFunctions, "Total number of functions")
Analysis containing CSE Info
bool isFixedObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a fixed stack object.
Register getPointerReg() const
Get the source register of the pointer value.
@ Legal
The operation is expected to be selectable directly by the target, and no transformation is necessary...
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Register getReg(unsigned Idx) const
Get the register for the operand index.
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Generic memory optimizations
Representation of each machine instruction.
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
Module * getParent()
Get the module that this global value is contained inside of...
constexpr ScalarTy getFixedValue() const
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isInstHardMergeHazard(MachineInstr &MI)
Returns true if the instruction creates an unavoidable hazard that forces a boundary between store me...
LegalizeActionStep getAction(const LegalityQuery &Query) const
Determine what action should be taken to legalize the described instruction.
print Print MemDeps of function
Class for arbitrary precision integers.
The LegalityQuery object bundles together all the information that's needed to decide whether a given...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
const MachineBasicBlock * getParent() const
EVT getApproximateEVTForLLT(LLT Ty, const DataLayout &DL, LLVMContext &Ctx)
bool instMayAlias(const MachineInstr &MI, const MachineInstr &Other, MachineRegisterInfo &MRI, AliasAnalysis *AA)
Returns true if the instruction MI may alias Other.
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual const LegalizerInfo * getLegalizerInfo() const
Function & getFunction()
Return the LLVM function that this machine code represents.
ConstantMatch< APInt > m_ICst(APInt &Cst)
void setPreservesAll()
Set by analyses that do not transform their input at all.
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
bool aliasIsKnownForLoadStore(const MachineInstr &MI1, const MachineInstr &MI2, bool &IsAlias, MachineRegisterInfo &MRI)
Compute whether or not a memory access at MI1 aliases with an access at MI2.
constexpr unsigned getAddressSpace() const
const unsigned MaxStoreSizeToForm
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
std::optional< std::vector< StOtherPiece > > Other
virtual const TargetLowering * getTargetLowering() const
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
constexpr TypeSize getSizeInBytes() const
Returns the total size of the type in bytes, i.e.
MachineMemOperand & getMMO() const
Get the MachineMemOperand on this instruction.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
@ Unsupported
This operation is completely unsupported on the target.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
auto reverse(ContainerTy &&C)
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
bool mi_match(Reg R, const MachineRegisterInfo &MRI, Pattern &&P)
AnalysisUsage & addRequired()
MachineInstrBuilder buildStore(const SrcOp &Val, const SrcOp &Addr, MachineMemOperand &MMO)
Build and insert G_STORE Val, Addr, MMO.
Representation for a specific memory location.
reference emplace_back(ArgTypes &&... Args)