xref: /llvm-project/llvm/lib/CodeGen/GlobalISel/LoadStoreOpt.cpp (revision dc84770d559b3305524fc86b945a697a803fc5c7)
1 //===- LoadStoreOpt.cpp ----------- Generic memory optimizations -*- C++ -*-==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 /// This file implements the LoadStoreOpt optimization pass.
10 //===----------------------------------------------------------------------===//
11 
12 #include "llvm/CodeGen/GlobalISel/LoadStoreOpt.h"
13 #include "llvm/ADT/Statistic.h"
14 #include "llvm/Analysis/AliasAnalysis.h"
15 #include "llvm/Analysis/MemoryLocation.h"
16 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
17 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
18 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
19 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
20 #include "llvm/CodeGen/GlobalISel/Utils.h"
21 #include "llvm/CodeGen/LowLevelType.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineFrameInfo.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/CodeGen/MachineInstr.h"
26 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/CodeGen/Register.h"
29 #include "llvm/CodeGen/TargetLowering.h"
30 #include "llvm/CodeGen/TargetOpcodes.h"
31 #include "llvm/IR/DebugInfoMetadata.h"
32 #include "llvm/InitializePasses.h"
33 #include "llvm/Support/AtomicOrdering.h"
34 #include "llvm/Support/Casting.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/ErrorHandling.h"
37 #include "llvm/Support/MathExtras.h"
38 #include <algorithm>
39 #include <any>
40 
41 #define DEBUG_TYPE "loadstore-opt"
42 
43 using namespace llvm;
44 using namespace ore;
45 using namespace MIPatternMatch;
46 
47 STATISTIC(NumStoresMerged, "Number of stores merged");
48 
49 const unsigned MaxStoreSizeToForm = 128;
50 
51 char LoadStoreOpt::ID = 0;
52 INITIALIZE_PASS_BEGIN(LoadStoreOpt, DEBUG_TYPE, "Generic memory optimizations",
53                       false, false)
54 INITIALIZE_PASS_END(LoadStoreOpt, DEBUG_TYPE, "Generic memory optimizations",
55                     false, false)
56 
57 LoadStoreOpt::LoadStoreOpt(std::function<bool(const MachineFunction &)> F)
58     : MachineFunctionPass(ID), DoNotRunPass(F) {}
59 
60 LoadStoreOpt::LoadStoreOpt()
61     : LoadStoreOpt([](const MachineFunction &) { return false; }) {}
62 
63 void LoadStoreOpt::init(MachineFunction &MF) {
64   this->MF = &MF;
65   MRI = &MF.getRegInfo();
66   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
67   TLI = MF.getSubtarget().getTargetLowering();
68   LI = MF.getSubtarget().getLegalizerInfo();
69   Builder.setMF(MF);
70   IsPreLegalizer = !MF.getProperties().hasProperty(
71       MachineFunctionProperties::Property::Legalized);
72   InstsToErase.clear();
73 }
74 
75 void LoadStoreOpt::getAnalysisUsage(AnalysisUsage &AU) const {
76   AU.addRequired<AAResultsWrapperPass>();
77   getSelectionDAGFallbackAnalysisUsage(AU);
78   MachineFunctionPass::getAnalysisUsage(AU);
79 }
80 
81 BaseIndexOffset GISelAddressing::getPointerInfo(Register Ptr,
82                                                 MachineRegisterInfo &MRI) {
83   BaseIndexOffset Info;
84   Register PtrAddRHS;
85   if (!mi_match(Ptr, MRI, m_GPtrAdd(m_Reg(Info.BaseReg), m_Reg(PtrAddRHS)))) {
86     Info.BaseReg = Ptr;
87     Info.IndexReg = Register();
88     Info.IsIndexSignExt = false;
89     return Info;
90   }
91 
92   auto RHSCst = getIConstantVRegValWithLookThrough(PtrAddRHS, MRI);
93   if (RHSCst)
94     Info.Offset = RHSCst->Value.getSExtValue();
95 
96   // Just recognize a simple case for now. In future we'll need to match
97   // indexing patterns for base + index + constant.
98   Info.IndexReg = PtrAddRHS;
99   Info.IsIndexSignExt = false;
100   return Info;
101 }
102 
103 bool GISelAddressing::aliasIsKnownForLoadStore(const MachineInstr &MI1,
104                                                const MachineInstr &MI2,
105                                                bool &IsAlias,
106                                                MachineRegisterInfo &MRI) {
107   auto *LdSt1 = dyn_cast<GLoadStore>(&MI1);
108   auto *LdSt2 = dyn_cast<GLoadStore>(&MI2);
109   if (!LdSt1 || !LdSt2)
110     return false;
111 
112   BaseIndexOffset BasePtr0 = getPointerInfo(LdSt1->getPointerReg(), MRI);
113   BaseIndexOffset BasePtr1 = getPointerInfo(LdSt2->getPointerReg(), MRI);
114 
115   if (!BasePtr0.BaseReg.isValid() || !BasePtr1.BaseReg.isValid())
116     return false;
117 
118   int64_t Size1 = LdSt1->getMemSize();
119   int64_t Size2 = LdSt2->getMemSize();
120 
121   int64_t PtrDiff;
122   if (BasePtr0.BaseReg == BasePtr1.BaseReg) {
123     PtrDiff = BasePtr1.Offset - BasePtr0.Offset;
124     // If the size of memory access is unknown, do not use it to do analysis.
125     // One example of unknown size memory access is to load/store scalable
126     // vector objects on the stack.
127     // BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the
128     // following situations arise:
129     if (PtrDiff >= 0 &&
130         Size1 != static_cast<int64_t>(MemoryLocation::UnknownSize)) {
131       // [----BasePtr0----]
132       //                         [---BasePtr1--]
133       // ========PtrDiff========>
134       IsAlias = !(Size1 <= PtrDiff);
135       return true;
136     }
137     if (PtrDiff < 0 &&
138         Size2 != static_cast<int64_t>(MemoryLocation::UnknownSize)) {
139       //                     [----BasePtr0----]
140       // [---BasePtr1--]
141       // =====(-PtrDiff)====>
142       IsAlias = !((PtrDiff + Size2) <= 0);
143       return true;
144     }
145     return false;
146   }
147 
148   // If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be
149   // able to calculate their relative offset if at least one arises
150   // from an alloca. However, these allocas cannot overlap and we
151   // can infer there is no alias.
152   auto *Base0Def = getDefIgnoringCopies(BasePtr0.BaseReg, MRI);
153   auto *Base1Def = getDefIgnoringCopies(BasePtr1.BaseReg, MRI);
154   if (!Base0Def || !Base1Def)
155     return false; // Couldn't tell anything.
156 
157 
158   if (Base0Def->getOpcode() != Base1Def->getOpcode())
159     return false;
160 
161   if (Base0Def->getOpcode() == TargetOpcode::G_FRAME_INDEX) {
162     MachineFrameInfo &MFI = Base0Def->getMF()->getFrameInfo();
163     // If the bases have the same frame index but we couldn't find a
164     // constant offset, (indices are different) be conservative.
165     if (Base0Def != Base1Def &&
166         (!MFI.isFixedObjectIndex(Base0Def->getOperand(1).getIndex()) ||
167          !MFI.isFixedObjectIndex(Base1Def->getOperand(1).getIndex()))) {
168       IsAlias = false;
169       return true;
170     }
171   }
172 
173   // This implementation is a lot more primitive than the SDAG one for now.
174   // FIXME: what about constant pools?
175   if (Base0Def->getOpcode() == TargetOpcode::G_GLOBAL_VALUE) {
176     auto GV0 = Base0Def->getOperand(1).getGlobal();
177     auto GV1 = Base1Def->getOperand(1).getGlobal();
178     if (GV0 != GV1) {
179       IsAlias = false;
180       return true;
181     }
182   }
183 
184   // Can't tell anything about aliasing.
185   return false;
186 }
187 
188 bool GISelAddressing::instMayAlias(const MachineInstr &MI,
189                                    const MachineInstr &Other,
190                                    MachineRegisterInfo &MRI,
191                                    AliasAnalysis *AA) {
192   struct MemUseCharacteristics {
193     bool IsVolatile;
194     bool IsAtomic;
195     Register BasePtr;
196     int64_t Offset;
197     uint64_t NumBytes;
198     MachineMemOperand *MMO;
199   };
200 
201   auto getCharacteristics =
202       [&](const MachineInstr *MI) -> MemUseCharacteristics {
203     if (const auto *LS = dyn_cast<GLoadStore>(MI)) {
204       Register BaseReg;
205       int64_t Offset = 0;
206       // No pre/post-inc addressing modes are considered here, unlike in SDAG.
207       if (!mi_match(LS->getPointerReg(), MRI,
208                     m_GPtrAdd(m_Reg(BaseReg), m_ICst(Offset)))) {
209         BaseReg = LS->getPointerReg();
210         Offset = 0;
211       }
212 
213       uint64_t Size = MemoryLocation::getSizeOrUnknown(
214           LS->getMMO().getMemoryType().getSizeInBytes());
215       return {LS->isVolatile(),       LS->isAtomic(),          BaseReg,
216               Offset /*base offset*/, Size, &LS->getMMO()};
217     }
218     // FIXME: support recognizing lifetime instructions.
219     // Default.
220     return {false /*isvolatile*/,
221             /*isAtomic*/ false,          Register(),
222             (int64_t)0 /*offset*/,       0 /*size*/,
223             (MachineMemOperand *)nullptr};
224   };
225   MemUseCharacteristics MUC0 = getCharacteristics(&MI),
226                         MUC1 = getCharacteristics(&Other);
227 
228   // If they are to the same address, then they must be aliases.
229   if (MUC0.BasePtr.isValid() && MUC0.BasePtr == MUC1.BasePtr &&
230       MUC0.Offset == MUC1.Offset)
231     return true;
232 
233   // If they are both volatile then they cannot be reordered.
234   if (MUC0.IsVolatile && MUC1.IsVolatile)
235     return true;
236 
237   // Be conservative about atomics for the moment
238   // TODO: This is way overconservative for unordered atomics (see D66309)
239   if (MUC0.IsAtomic && MUC1.IsAtomic)
240     return true;
241 
242   // If one operation reads from invariant memory, and the other may store, they
243   // cannot alias.
244   if (MUC0.MMO && MUC1.MMO) {
245     if ((MUC0.MMO->isInvariant() && MUC1.MMO->isStore()) ||
246         (MUC1.MMO->isInvariant() && MUC0.MMO->isStore()))
247       return false;
248   }
249 
250   // Try to prove that there is aliasing, or that there is no aliasing. Either
251   // way, we can return now. If nothing can be proved, proceed with more tests.
252   bool IsAlias;
253   if (GISelAddressing::aliasIsKnownForLoadStore(MI, Other, IsAlias, MRI))
254     return IsAlias;
255 
256   // The following all rely on MMO0 and MMO1 being valid.
257   if (!MUC0.MMO || !MUC1.MMO)
258     return true;
259 
260   // FIXME: port the alignment based alias analysis from SDAG's isAlias().
261   int64_t SrcValOffset0 = MUC0.MMO->getOffset();
262   int64_t SrcValOffset1 = MUC1.MMO->getOffset();
263   uint64_t Size0 = MUC0.NumBytes;
264   uint64_t Size1 = MUC1.NumBytes;
265   if (AA && MUC0.MMO->getValue() && MUC1.MMO->getValue() &&
266       Size0 != MemoryLocation::UnknownSize &&
267       Size1 != MemoryLocation::UnknownSize) {
268     // Use alias analysis information.
269     int64_t MinOffset = std::min(SrcValOffset0, SrcValOffset1);
270     int64_t Overlap0 = Size0 + SrcValOffset0 - MinOffset;
271     int64_t Overlap1 = Size1 + SrcValOffset1 - MinOffset;
272     if (AA->isNoAlias(MemoryLocation(MUC0.MMO->getValue(), Overlap0,
273                                      MUC0.MMO->getAAInfo()),
274                       MemoryLocation(MUC1.MMO->getValue(), Overlap1,
275                                      MUC1.MMO->getAAInfo())))
276       return false;
277   }
278 
279   // Otherwise we have to assume they alias.
280   return true;
281 }
282 
283 /// Returns true if the instruction creates an unavoidable hazard that
284 /// forces a boundary between store merge candidates.
285 static bool isInstHardMergeHazard(MachineInstr &MI) {
286   return MI.hasUnmodeledSideEffects() || MI.hasOrderedMemoryRef();
287 }
288 
289 bool LoadStoreOpt::mergeStores(SmallVectorImpl<GStore *> &StoresToMerge) {
290   // Try to merge all the stores in the vector, splitting into separate segments
291   // as necessary.
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());
295   unsigned AS = PtrTy.getAddressSpace();
296   // Ensure the legal store info is computed for this address space.
297   initializeStoreMergeTargetInfo(AS);
298   const auto &LegalSizes = LegalStoreSizes[AS];
299 
300 #ifndef NDEBUG
301   for (auto StoreMI : StoresToMerge)
302     assert(MRI->getType(StoreMI->getValueReg()) == OrigTy);
303 #endif
304 
305   const auto &DL = MF->getFunction().getParent()->getDataLayout();
306   bool AnyMerged = false;
307   do {
308     unsigned NumPow2 = PowerOf2Floor(StoresToMerge.size());
309     unsigned MaxSizeBits = NumPow2 * OrigTy.getSizeInBits().getFixedSize();
310     // Compute the biggest store we can generate to handle the number of stores.
311     unsigned MergeSizeBits;
312     for (MergeSizeBits = MaxSizeBits; MergeSizeBits > 1; MergeSizeBits /= 2) {
313       LLT StoreTy = LLT::scalar(MergeSizeBits);
314       EVT StoreEVT =
315           getApproximateEVTForLLT(StoreTy, DL, MF->getFunction().getContext());
316       if (LegalSizes.size() > MergeSizeBits && LegalSizes[MergeSizeBits] &&
317           TLI->canMergeStoresTo(AS, StoreEVT, *MF) &&
318           (TLI->isTypeLegal(StoreEVT)))
319         break; // We can generate a MergeSize bits store.
320     }
321     if (MergeSizeBits <= OrigTy.getSizeInBits())
322       return AnyMerged; // No greater merge.
323 
324     unsigned NumStoresToMerge = MergeSizeBits / OrigTy.getSizeInBits();
325     // Perform the actual merging.
326     SmallVector<GStore *, 8> SingleMergeStores(
327         StoresToMerge.begin(), StoresToMerge.begin() + NumStoresToMerge);
328     AnyMerged |= doSingleStoreMerge(SingleMergeStores);
329     StoresToMerge.erase(StoresToMerge.begin(),
330                         StoresToMerge.begin() + NumStoresToMerge);
331   } while (StoresToMerge.size() > 1);
332   return AnyMerged;
333 }
334 
335 bool LoadStoreOpt::isLegalOrBeforeLegalizer(const LegalityQuery &Query,
336                                             MachineFunction &MF) const {
337   auto Action = LI->getAction(Query).Action;
338   // If the instruction is unsupported, it can't be legalized at all.
339   if (Action == LegalizeActions::Unsupported)
340     return false;
341   return IsPreLegalizer || Action == LegalizeAction::Legal;
342 }
343 
344 bool LoadStoreOpt::doSingleStoreMerge(SmallVectorImpl<GStore *> &Stores) {
345   assert(Stores.size() > 1);
346   // We know that all the stores are consecutive and there are no aliasing
347   // operations in the range. However, the values that are being stored may be
348   // generated anywhere before each store. To ensure we have the values
349   // available, we materialize the wide value and new store at the place of the
350   // final store in the merge sequence.
351   GStore *FirstStore = Stores[0];
352   const unsigned NumStores = Stores.size();
353   LLT SmallTy = MRI->getType(FirstStore->getValueReg());
354   LLT WideValueTy =
355       LLT::scalar(NumStores * SmallTy.getSizeInBits().getFixedSize());
356 
357   // For each store, compute pairwise merged debug locs.
358   DebugLoc MergedLoc;
359   for (unsigned AIdx = 0, BIdx = 1; BIdx < NumStores; ++AIdx, ++BIdx)
360     MergedLoc = DILocation::getMergedLocation(Stores[AIdx]->getDebugLoc(),
361                                               Stores[BIdx]->getDebugLoc());
362   Builder.setInstr(*Stores.back());
363   Builder.setDebugLoc(MergedLoc);
364 
365   // If all of the store values are constants, then create a wide constant
366   // directly. Otherwise, we need to generate some instructions to merge the
367   // existing values together into a wider type.
368   SmallVector<APInt, 8> ConstantVals;
369   for (auto Store : Stores) {
370     auto MaybeCst =
371         getIConstantVRegValWithLookThrough(Store->getValueReg(), *MRI);
372     if (!MaybeCst) {
373       ConstantVals.clear();
374       break;
375     }
376     ConstantVals.emplace_back(MaybeCst->Value);
377   }
378 
379   Register WideReg;
380   auto *WideMMO =
381       MF->getMachineMemOperand(&FirstStore->getMMO(), 0, WideValueTy);
382   if (ConstantVals.empty()) {
383     // Mimic the SDAG behaviour here and don't try to do anything for unknown
384     // values. In future, we should also support the cases of loads and
385     // extracted vector elements.
386     return false;
387   }
388 
389   assert(ConstantVals.size() == NumStores);
390   // Check if our wide constant is legal.
391   if (!isLegalOrBeforeLegalizer({TargetOpcode::G_CONSTANT, {WideValueTy}}, *MF))
392     return false;
393   APInt WideConst(WideValueTy.getSizeInBits(), 0);
394   for (unsigned Idx = 0; Idx < ConstantVals.size(); ++Idx) {
395     // Insert the smaller constant into the corresponding position in the
396     // wider one.
397     WideConst.insertBits(ConstantVals[Idx], Idx * SmallTy.getSizeInBits());
398   }
399   WideReg = Builder.buildConstant(WideValueTy, WideConst).getReg(0);
400   auto NewStore =
401       Builder.buildStore(WideReg, FirstStore->getPointerReg(), *WideMMO);
402   LLVM_DEBUG(dbgs() << "Created merged store: " << *NewStore);
403   NumStoresMerged += Stores.size();
404 
405   MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
406   MORE.emit([&]() {
407     MachineOptimizationRemark R(DEBUG_TYPE, "MergedStore",
408                                 FirstStore->getDebugLoc(),
409                                 FirstStore->getParent());
410     R << "Merged " << NV("NumMerged", Stores.size()) << " stores of "
411       << NV("OrigWidth", SmallTy.getSizeInBytes())
412       << " bytes into a single store of "
413       << NV("NewWidth", WideValueTy.getSizeInBytes()) << " bytes";
414     return R;
415   });
416 
417   for (auto MI : Stores)
418     InstsToErase.insert(MI);
419   return true;
420 }
421 
422 bool LoadStoreOpt::processMergeCandidate(StoreMergeCandidate &C) {
423   if (C.Stores.size() < 2) {
424     C.reset();
425     return false;
426   }
427 
428   LLVM_DEBUG(dbgs() << "Checking store merge candidate with " << C.Stores.size()
429                     << " stores, starting with " << *C.Stores[0]);
430   // We know that the stores in the candidate are adjacent.
431   // Now we need to check if any potential aliasing instructions recorded
432   // during the search alias with load/stores added to the candidate after.
433   // For example, if we have the candidate:
434   //   C.Stores = [ST1, ST2, ST3, ST4]
435   // and after seeing ST2 we saw a load LD1, which did not alias with ST1 or
436   // ST2, then we would have recorded it into the PotentialAliases structure
437   // with the associated index value of "1". Then we see ST3 and ST4 and add
438   // them to the candidate group. We know that LD1 does not alias with ST1 or
439   // ST2, since we already did that check. However we don't yet know if it
440   // may alias ST3 and ST4, so we perform those checks now.
441   SmallVector<GStore *> StoresToMerge;
442 
443   auto DoesStoreAliasWithPotential = [&](unsigned Idx, GStore &CheckStore) {
444     for (auto AliasInfo : reverse(C.PotentialAliases)) {
445       MachineInstr *PotentialAliasOp = AliasInfo.first;
446       unsigned PreCheckedIdx = AliasInfo.second;
447       if (static_cast<unsigned>(Idx) > PreCheckedIdx) {
448         // Need to check this alias.
449         if (GISelAddressing::instMayAlias(CheckStore, *PotentialAliasOp, *MRI,
450                                           AA)) {
451           LLVM_DEBUG(dbgs() << "Potential alias " << *PotentialAliasOp
452                             << " detected\n");
453           return true;
454         }
455       } else {
456         // Once our store index is lower than the index associated with the
457         // potential alias, we know that we've already checked for this alias
458         // and all of the earlier potential aliases too.
459         return false;
460       }
461     }
462     return false;
463   };
464   // Start from the last store in the group, and check if it aliases with any
465   // of the potential aliasing operations in the list.
466   for (int StoreIdx = C.Stores.size() - 1; StoreIdx >= 0; --StoreIdx) {
467     auto *CheckStore = C.Stores[StoreIdx];
468     if (DoesStoreAliasWithPotential(StoreIdx, *CheckStore))
469       continue;
470     StoresToMerge.emplace_back(CheckStore);
471   }
472 
473   LLVM_DEBUG(dbgs() << StoresToMerge.size()
474                     << " stores remaining after alias checks. Merging...\n");
475 
476   // Now we've checked for aliasing hazards, merge any stores left.
477   C.reset();
478   if (StoresToMerge.size() < 2)
479     return false;
480   return mergeStores(StoresToMerge);
481 }
482 
483 bool LoadStoreOpt::operationAliasesWithCandidate(MachineInstr &MI,
484                                                  StoreMergeCandidate &C) {
485   if (C.Stores.empty())
486     return false;
487   return llvm::any_of(C.Stores, [&](MachineInstr *OtherMI) {
488     return instMayAlias(MI, *OtherMI, *MRI, AA);
489   });
490 }
491 
492 void LoadStoreOpt::StoreMergeCandidate::addPotentialAlias(MachineInstr &MI) {
493   PotentialAliases.emplace_back(std::make_pair(&MI, Stores.size() - 1));
494 }
495 
496 bool LoadStoreOpt::addStoreToCandidate(GStore &StoreMI,
497                                        StoreMergeCandidate &C) {
498   // Check if the given store writes to an adjacent address, and other
499   // requirements.
500   LLT ValueTy = MRI->getType(StoreMI.getValueReg());
501   LLT PtrTy = MRI->getType(StoreMI.getPointerReg());
502 
503   // Only handle scalars.
504   if (!ValueTy.isScalar())
505     return false;
506 
507   // Don't allow truncating stores for now.
508   if (StoreMI.getMemSizeInBits() != ValueTy.getSizeInBits())
509     return false;
510 
511   Register StoreAddr = StoreMI.getPointerReg();
512   auto BIO = getPointerInfo(StoreAddr, *MRI);
513   Register StoreBase = BIO.BaseReg;
514   uint64_t StoreOffCst = BIO.Offset;
515   if (C.Stores.empty()) {
516     // This is the first store of the candidate.
517     // If the offset can't possibly allow for a lower addressed store with the
518     // same base, don't bother adding it.
519     if (StoreOffCst < ValueTy.getSizeInBytes())
520       return false;
521     C.BasePtr = StoreBase;
522     C.CurrentLowestOffset = StoreOffCst;
523     C.Stores.emplace_back(&StoreMI);
524     LLVM_DEBUG(dbgs() << "Starting a new merge candidate group with: "
525                       << StoreMI);
526     return true;
527   }
528 
529   // Check the store is the same size as the existing ones in the candidate.
530   if (MRI->getType(C.Stores[0]->getValueReg()).getSizeInBits() !=
531       ValueTy.getSizeInBits())
532     return false;
533 
534   if (MRI->getType(C.Stores[0]->getPointerReg()).getAddressSpace() !=
535       PtrTy.getAddressSpace())
536     return false;
537 
538   // There are other stores in the candidate. Check that the store address
539   // writes to the next lowest adjacent address.
540   if (C.BasePtr != StoreBase)
541     return false;
542   if ((C.CurrentLowestOffset - ValueTy.getSizeInBytes()) !=
543       static_cast<uint64_t>(StoreOffCst))
544     return false;
545 
546   // This writes to an adjacent address. Allow it.
547   C.Stores.emplace_back(&StoreMI);
548   C.CurrentLowestOffset = C.CurrentLowestOffset - ValueTy.getSizeInBytes();
549   LLVM_DEBUG(dbgs() << "Candidate added store: " << StoreMI);
550   return true;
551 }
552 
553 bool LoadStoreOpt::mergeBlockStores(MachineBasicBlock &MBB) {
554   bool Changed = false;
555   // Walk through the block bottom-up, looking for merging candidates.
556   StoreMergeCandidate Candidate;
557   for (auto II = MBB.rbegin(), IE = MBB.rend(); II != IE; ++II) {
558     MachineInstr &MI = *II;
559     if (InstsToErase.contains(&MI))
560       continue;
561 
562     if (auto StoreMI = dyn_cast<GStore>(&*II)) {
563       // We have a G_STORE. Add it to the candidate if it writes to an adjacent
564       // address.
565       if (!addStoreToCandidate(*StoreMI, Candidate)) {
566         // Store wasn't eligible to be added. May need to record it as a
567         // potential alias.
568         if (operationAliasesWithCandidate(*StoreMI, Candidate)) {
569           Changed |= processMergeCandidate(Candidate);
570           continue;
571         }
572         Candidate.addPotentialAlias(*StoreMI);
573       }
574       continue;
575     }
576 
577     // If we don't have any stores yet, this instruction can't pose a problem.
578     if (Candidate.Stores.empty())
579       continue;
580 
581     // We're dealing with some other kind of instruction.
582     if (isInstHardMergeHazard(MI)) {
583       Changed |= processMergeCandidate(Candidate);
584       Candidate.Stores.clear();
585       continue;
586     }
587 
588     if (!MI.mayLoadOrStore())
589       continue;
590 
591     if (operationAliasesWithCandidate(MI, Candidate)) {
592       // We have a potential alias, so process the current candidate if we can
593       // and then continue looking for a new candidate.
594       Changed |= processMergeCandidate(Candidate);
595       continue;
596     }
597 
598     // Record this instruction as a potential alias for future stores that are
599     // added to the candidate.
600     Candidate.addPotentialAlias(MI);
601   }
602 
603   // Process any candidate left after finishing searching the entire block.
604   Changed |= processMergeCandidate(Candidate);
605 
606   // Erase instructions now that we're no longer iterating over the block.
607   for (auto *MI : InstsToErase)
608     MI->eraseFromParent();
609   InstsToErase.clear();
610   return Changed;
611 }
612 
613 bool LoadStoreOpt::mergeFunctionStores(MachineFunction &MF) {
614   bool Changed = false;
615   for (auto &BB : MF) {
616     Changed |= mergeBlockStores(BB);
617   }
618   return Changed;
619 }
620 
621 void LoadStoreOpt::initializeStoreMergeTargetInfo(unsigned AddrSpace) {
622   // Query the legalizer info to record what store types are legal.
623   // We record this because we don't want to bother trying to merge stores into
624   // illegal ones, which would just result in being split again.
625 
626   if (LegalStoreSizes.count(AddrSpace)) {
627     assert(LegalStoreSizes[AddrSpace].any());
628     return; // Already cached sizes for this address space.
629   }
630 
631   // Need to reserve at least MaxStoreSizeToForm + 1 bits.
632   BitVector LegalSizes(MaxStoreSizeToForm * 2);
633   const auto &LI = *MF->getSubtarget().getLegalizerInfo();
634   const auto &DL = MF->getFunction().getParent()->getDataLayout();
635   Type *IntPtrIRTy =
636       DL.getIntPtrType(MF->getFunction().getContext(), AddrSpace);
637   LLT PtrTy = getLLTForType(*IntPtrIRTy->getPointerTo(AddrSpace), DL);
638   // We assume that we're not going to be generating any stores wider than
639   // MaxStoreSizeToForm bits for now.
640   for (unsigned Size = 2; Size <= MaxStoreSizeToForm; Size *= 2) {
641     LLT Ty = LLT::scalar(Size);
642     SmallVector<LegalityQuery::MemDesc, 2> MemDescrs(
643         {{Ty, Ty.getSizeInBits(), AtomicOrdering::NotAtomic}});
644     SmallVector<LLT> StoreTys({Ty, PtrTy});
645     LegalityQuery Q(TargetOpcode::G_STORE, StoreTys, MemDescrs);
646     LegalizeActionStep ActionStep = LI.getAction(Q);
647     if (ActionStep.Action == LegalizeActions::Legal)
648       LegalSizes.set(Size);
649   }
650   assert(LegalSizes.any() && "Expected some store sizes to be legal!");
651   LegalStoreSizes[AddrSpace] = LegalSizes;
652 }
653 
654 bool LoadStoreOpt::runOnMachineFunction(MachineFunction &MF) {
655   // If the ISel pipeline failed, do not bother running that pass.
656   if (MF.getProperties().hasProperty(
657           MachineFunctionProperties::Property::FailedISel))
658     return false;
659 
660   LLVM_DEBUG(dbgs() << "Begin memory optimizations for: " << MF.getName()
661                     << '\n');
662 
663   init(MF);
664   bool Changed = false;
665   Changed |= mergeFunctionStores(MF);
666 
667   LegalStoreSizes.clear();
668   return Changed;
669 }
670