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