1 //===- LoadStoreVectorizer.cpp - GPU Load & Store Vectorizer --------------===// 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 // 9 // This pass merges loads/stores to/from sequential memory addresses into vector 10 // loads/stores. Although there's nothing GPU-specific in here, this pass is 11 // motivated by the microarchitectural quirks of nVidia and AMD GPUs. 12 // 13 // (For simplicity below we talk about loads only, but everything also applies 14 // to stores.) 15 // 16 // This pass is intended to be run late in the pipeline, after other 17 // vectorization opportunities have been exploited. So the assumption here is 18 // that immediately following our new vector load we'll need to extract out the 19 // individual elements of the load, so we can operate on them individually. 20 // 21 // On CPUs this transformation is usually not beneficial, because extracting the 22 // elements of a vector register is expensive on most architectures. It's 23 // usually better just to load each element individually into its own scalar 24 // register. 25 // 26 // However, nVidia and AMD GPUs don't have proper vector registers. Instead, a 27 // "vector load" loads directly into a series of scalar registers. In effect, 28 // extracting the elements of the vector is free. It's therefore always 29 // beneficial to vectorize a sequence of loads on these architectures. 30 // 31 // Vectorizing (perhaps a better name might be "coalescing") loads can have 32 // large performance impacts on GPU kernels, and opportunities for vectorizing 33 // are common in GPU code. This pass tries very hard to find such 34 // opportunities; its runtime is quadratic in the number of loads in a BB. 35 // 36 // Some CPU architectures, such as ARM, have instructions that load into 37 // multiple scalar registers, similar to a GPU vectorized load. In theory ARM 38 // could use this pass (with some modifications), but currently it implements 39 // its own pass to do something similar to what we do here. 40 // 41 // Overview of the algorithm and terminology in this pass: 42 // 43 // - Break up each basic block into pseudo-BBs, composed of instructions which 44 // are guaranteed to transfer control to their successors. 45 // - Within a single pseudo-BB, find all loads, and group them into 46 // "equivalence classes" according to getUnderlyingObject() and loaded 47 // element size. Do the same for stores. 48 // - For each equivalence class, greedily build "chains". Each chain has a 49 // leader instruction, and every other member of the chain has a known 50 // constant offset from the first instr in the chain. 51 // - Break up chains so that they contain only contiguous accesses of legal 52 // size with no intervening may-alias instrs. 53 // - Convert each chain to vector instructions. 54 // 55 // The O(n^2) behavior of this pass comes from initially building the chains. 56 // In the worst case we have to compare each new instruction to all of those 57 // that came before. To limit this, we only calculate the offset to the leaders 58 // of the N most recently-used chains. 59 60 #include "llvm/Transforms/Vectorize/LoadStoreVectorizer.h" 61 #include "llvm/ADT/APInt.h" 62 #include "llvm/ADT/ArrayRef.h" 63 #include "llvm/ADT/DenseMap.h" 64 #include "llvm/ADT/MapVector.h" 65 #include "llvm/ADT/PostOrderIterator.h" 66 #include "llvm/ADT/STLExtras.h" 67 #include "llvm/ADT/Sequence.h" 68 #include "llvm/ADT/SmallPtrSet.h" 69 #include "llvm/ADT/SmallVector.h" 70 #include "llvm/ADT/Statistic.h" 71 #include "llvm/ADT/iterator_range.h" 72 #include "llvm/Analysis/AliasAnalysis.h" 73 #include "llvm/Analysis/AssumptionCache.h" 74 #include "llvm/Analysis/MemoryLocation.h" 75 #include "llvm/Analysis/ScalarEvolution.h" 76 #include "llvm/Analysis/TargetTransformInfo.h" 77 #include "llvm/Analysis/ValueTracking.h" 78 #include "llvm/Analysis/VectorUtils.h" 79 #include "llvm/IR/Attributes.h" 80 #include "llvm/IR/BasicBlock.h" 81 #include "llvm/IR/ConstantRange.h" 82 #include "llvm/IR/Constants.h" 83 #include "llvm/IR/DataLayout.h" 84 #include "llvm/IR/DerivedTypes.h" 85 #include "llvm/IR/Dominators.h" 86 #include "llvm/IR/Function.h" 87 #include "llvm/IR/GetElementPtrTypeIterator.h" 88 #include "llvm/IR/IRBuilder.h" 89 #include "llvm/IR/InstrTypes.h" 90 #include "llvm/IR/Instruction.h" 91 #include "llvm/IR/Instructions.h" 92 #include "llvm/IR/LLVMContext.h" 93 #include "llvm/IR/Module.h" 94 #include "llvm/IR/Type.h" 95 #include "llvm/IR/Value.h" 96 #include "llvm/InitializePasses.h" 97 #include "llvm/Pass.h" 98 #include "llvm/Support/Alignment.h" 99 #include "llvm/Support/Casting.h" 100 #include "llvm/Support/Debug.h" 101 #include "llvm/Support/KnownBits.h" 102 #include "llvm/Support/MathExtras.h" 103 #include "llvm/Support/ModRef.h" 104 #include "llvm/Support/raw_ostream.h" 105 #include "llvm/Transforms/Utils/Local.h" 106 #include "llvm/Transforms/Vectorize.h" 107 #include <algorithm> 108 #include <cassert> 109 #include <cstdint> 110 #include <cstdlib> 111 #include <iterator> 112 #include <limits> 113 #include <numeric> 114 #include <optional> 115 #include <tuple> 116 #include <type_traits> 117 #include <utility> 118 #include <vector> 119 120 using namespace llvm; 121 122 #define DEBUG_TYPE "load-store-vectorizer" 123 124 STATISTIC(NumVectorInstructions, "Number of vector accesses generated"); 125 STATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized"); 126 127 namespace { 128 129 // Equivalence class key, the initial tuple by which we group loads/stores. 130 // Loads/stores with different EqClassKeys are never merged. 131 // 132 // (We could in theory remove element-size from the this tuple. We'd just need 133 // to fix up the vector packing/unpacking code.) 134 using EqClassKey = 135 std::tuple<const Value * /* result of getUnderlyingObject() */, 136 unsigned /* AddrSpace */, 137 unsigned /* Load/Store element size bits */, 138 char /* IsLoad; char b/c bool can't be a DenseMap key */ 139 >; 140 [[maybe_unused]] llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, 141 const EqClassKey &K) { 142 const auto &[UnderlyingObject, AddrSpace, ElementSize, IsLoad] = K; 143 return OS << (IsLoad ? "load" : "store") << " of " << *UnderlyingObject 144 << " of element size " << ElementSize << " bits in addrspace " 145 << AddrSpace; 146 } 147 148 // A Chain is a set of instructions such that: 149 // - All instructions have the same equivalence class, so in particular all are 150 // loads, or all are stores. 151 // - We know the address accessed by the i'th chain elem relative to the 152 // chain's leader instruction, which is the first instr of the chain in BB 153 // order. 154 // 155 // Chains have two canonical orderings: 156 // - BB order, sorted by Instr->comesBefore. 157 // - Offset order, sorted by OffsetFromLeader. 158 // This pass switches back and forth between these orders. 159 struct ChainElem { 160 Instruction *Inst; 161 APInt OffsetFromLeader; 162 }; 163 using Chain = SmallVector<ChainElem, 1>; 164 165 void sortChainInBBOrder(Chain &C) { 166 sort(C, [](auto &A, auto &B) { return A.Inst->comesBefore(B.Inst); }); 167 } 168 169 void sortChainInOffsetOrder(Chain &C) { 170 sort(C, [](const auto &A, const auto &B) { 171 if (A.OffsetFromLeader != B.OffsetFromLeader) 172 return A.OffsetFromLeader.slt(B.OffsetFromLeader); 173 return A.Inst->comesBefore(B.Inst); // stable tiebreaker 174 }); 175 } 176 177 [[maybe_unused]] void dumpChain(ArrayRef<ChainElem> C) { 178 for (const auto &E : C) { 179 dbgs() << " " << *E.Inst << " (offset " << E.OffsetFromLeader << ")\n"; 180 } 181 } 182 183 using EquivalenceClassMap = 184 MapVector<EqClassKey, SmallVector<Instruction *, 8>>; 185 186 // FIXME: Assuming stack alignment of 4 is always good enough 187 constexpr unsigned StackAdjustedAlignment = 4; 188 189 Instruction *propagateMetadata(Instruction *I, const Chain &C) { 190 SmallVector<Value *, 8> Values; 191 for (const ChainElem &E : C) 192 Values.push_back(E.Inst); 193 return propagateMetadata(I, Values); 194 } 195 196 bool isInvariantLoad(const Instruction *I) { 197 const LoadInst *LI = dyn_cast<LoadInst>(I); 198 return LI != nullptr && LI->hasMetadata(LLVMContext::MD_invariant_load); 199 } 200 201 /// Reorders the instructions that I depends on (the instructions defining its 202 /// operands), to ensure they dominate I. 203 void reorder(Instruction *I) { 204 SmallPtrSet<Instruction *, 16> InstructionsToMove; 205 SmallVector<Instruction *, 16> Worklist; 206 207 Worklist.push_back(I); 208 while (!Worklist.empty()) { 209 Instruction *IW = Worklist.pop_back_val(); 210 int NumOperands = IW->getNumOperands(); 211 for (int i = 0; i < NumOperands; i++) { 212 Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i)); 213 if (!IM || IM->getOpcode() == Instruction::PHI) 214 continue; 215 216 // If IM is in another BB, no need to move it, because this pass only 217 // vectorizes instructions within one BB. 218 if (IM->getParent() != I->getParent()) 219 continue; 220 221 if (!IM->comesBefore(I)) { 222 InstructionsToMove.insert(IM); 223 Worklist.push_back(IM); 224 } 225 } 226 } 227 228 // All instructions to move should follow I. Start from I, not from begin(). 229 for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;) { 230 Instruction *IM = &*(BBI++); 231 if (!InstructionsToMove.count(IM)) 232 continue; 233 IM->moveBefore(I); 234 } 235 } 236 237 class Vectorizer { 238 Function &F; 239 AliasAnalysis &AA; 240 AssumptionCache &AC; 241 DominatorTree &DT; 242 ScalarEvolution &SE; 243 TargetTransformInfo &TTI; 244 const DataLayout &DL; 245 IRBuilder<> Builder; 246 247 // We could erase instrs right after vectorizing them, but that can mess up 248 // our BB iterators, and also can make the equivalence class keys point to 249 // freed memory. This is fixable, but it's simpler just to wait until we're 250 // done with the BB and erase all at once. 251 SmallVector<Instruction *, 128> ToErase; 252 253 public: 254 Vectorizer(Function &F, AliasAnalysis &AA, AssumptionCache &AC, 255 DominatorTree &DT, ScalarEvolution &SE, TargetTransformInfo &TTI) 256 : F(F), AA(AA), AC(AC), DT(DT), SE(SE), TTI(TTI), 257 DL(F.getParent()->getDataLayout()), Builder(SE.getContext()) {} 258 259 bool run(); 260 261 private: 262 static const unsigned MaxDepth = 3; 263 264 /// Runs the vectorizer on a "pseudo basic block", which is a range of 265 /// instructions [Begin, End) within one BB all of which have 266 /// isGuaranteedToTransferExecutionToSuccessor(I) == true. 267 bool runOnPseudoBB(BasicBlock::iterator Begin, BasicBlock::iterator End); 268 269 /// Runs the vectorizer on one equivalence class, i.e. one set of loads/stores 270 /// in the same BB with the same value for getUnderlyingObject() etc. 271 bool runOnEquivalenceClass(const EqClassKey &EqClassKey, 272 ArrayRef<Instruction *> EqClass); 273 274 /// Runs the vectorizer on one chain, i.e. a subset of an equivalence class 275 /// where all instructions access a known, constant offset from the first 276 /// instruction. 277 bool runOnChain(Chain &C); 278 279 /// Splits the chain into subchains of instructions which read/write a 280 /// contiguous block of memory. Discards any length-1 subchains (because 281 /// there's nothing to vectorize in there). 282 std::vector<Chain> splitChainByContiguity(Chain &C); 283 284 /// Splits the chain into subchains where it's safe to hoist loads up to the 285 /// beginning of the sub-chain and it's safe to sink loads up to the end of 286 /// the sub-chain. Discards any length-1 subchains. 287 std::vector<Chain> splitChainByMayAliasInstrs(Chain &C); 288 289 /// Splits the chain into subchains that make legal, aligned accesses. 290 /// Discards any length-1 subchains. 291 std::vector<Chain> splitChainByAlignment(Chain &C); 292 293 /// Converts the instrs in the chain into a single vectorized load or store. 294 /// Adds the old scalar loads/stores to ToErase. 295 bool vectorizeChain(Chain &C); 296 297 /// Tries to compute the offset in bytes PtrB - PtrA. 298 std::optional<APInt> getConstantOffset(Value *PtrA, Value *PtrB, 299 Instruction *ContextInst, 300 unsigned Depth = 0); 301 std::optional<APInt> getConstantOffsetComplexAddrs(Value *PtrA, Value *PtrB, 302 Instruction *ContextInst, 303 unsigned Depth); 304 std::optional<APInt> getConstantOffsetSelects(Value *PtrA, Value *PtrB, 305 Instruction *ContextInst, 306 unsigned Depth); 307 308 /// Gets the element type of the vector that the chain will load or store. 309 /// This is nontrivial because the chain may contain elements of different 310 /// types; e.g. it's legal to have a chain that contains both i32 and float. 311 Type *getChainElemTy(const Chain &C); 312 313 /// Determines whether ChainElem can be moved up (if IsLoad) or down (if 314 /// !IsLoad) to ChainBegin -- i.e. there are no intervening may-alias 315 /// instructions. 316 /// 317 /// The map ChainElemOffsets must contain all of the elements in 318 /// [ChainBegin, ChainElem] and their offsets from some arbitrary base 319 /// address. It's ok if it contains additional entries. 320 template <bool IsLoadChain> 321 bool isSafeToMove( 322 Instruction *ChainElem, Instruction *ChainBegin, 323 const DenseMap<Instruction *, APInt /*OffsetFromLeader*/> &ChainOffsets); 324 325 /// Collects loads and stores grouped by "equivalence class", where: 326 /// - all elements in an eq class are a load or all are a store, 327 /// - they all load/store the same element size (it's OK to have e.g. i8 and 328 /// <4 x i8> in the same class, but not i32 and <4 x i8>), and 329 /// - they all have the same value for getUnderlyingObject(). 330 EquivalenceClassMap collectEquivalenceClasses(BasicBlock::iterator Begin, 331 BasicBlock::iterator End); 332 333 /// Partitions Instrs into "chains" where every instruction has a known 334 /// constant offset from the first instr in the chain. 335 /// 336 /// Postcondition: For all i, ret[i][0].second == 0, because the first instr 337 /// in the chain is the leader, and an instr touches distance 0 from itself. 338 std::vector<Chain> gatherChains(ArrayRef<Instruction *> Instrs); 339 }; 340 341 class LoadStoreVectorizerLegacyPass : public FunctionPass { 342 public: 343 static char ID; 344 345 LoadStoreVectorizerLegacyPass() : FunctionPass(ID) { 346 initializeLoadStoreVectorizerLegacyPassPass( 347 *PassRegistry::getPassRegistry()); 348 } 349 350 bool runOnFunction(Function &F) override; 351 352 StringRef getPassName() const override { 353 return "GPU Load and Store Vectorizer"; 354 } 355 356 void getAnalysisUsage(AnalysisUsage &AU) const override { 357 AU.addRequired<AAResultsWrapperPass>(); 358 AU.addRequired<AssumptionCacheTracker>(); 359 AU.addRequired<ScalarEvolutionWrapperPass>(); 360 AU.addRequired<DominatorTreeWrapperPass>(); 361 AU.addRequired<TargetTransformInfoWrapperPass>(); 362 AU.setPreservesCFG(); 363 } 364 }; 365 366 } // end anonymous namespace 367 368 char LoadStoreVectorizerLegacyPass::ID = 0; 369 370 INITIALIZE_PASS_BEGIN(LoadStoreVectorizerLegacyPass, DEBUG_TYPE, 371 "Vectorize load and Store instructions", false, false) 372 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass) 373 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker); 374 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 375 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 376 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) 377 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 378 INITIALIZE_PASS_END(LoadStoreVectorizerLegacyPass, DEBUG_TYPE, 379 "Vectorize load and store instructions", false, false) 380 381 Pass *llvm::createLoadStoreVectorizerPass() { 382 return new LoadStoreVectorizerLegacyPass(); 383 } 384 385 bool LoadStoreVectorizerLegacyPass::runOnFunction(Function &F) { 386 // Don't vectorize when the attribute NoImplicitFloat is used. 387 if (skipFunction(F) || F.hasFnAttribute(Attribute::NoImplicitFloat)) 388 return false; 389 390 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); 391 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 392 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 393 TargetTransformInfo &TTI = 394 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 395 396 AssumptionCache &AC = 397 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 398 399 return Vectorizer(F, AA, AC, DT, SE, TTI).run(); 400 } 401 402 PreservedAnalyses LoadStoreVectorizerPass::run(Function &F, 403 FunctionAnalysisManager &AM) { 404 // Don't vectorize when the attribute NoImplicitFloat is used. 405 if (F.hasFnAttribute(Attribute::NoImplicitFloat)) 406 return PreservedAnalyses::all(); 407 408 AliasAnalysis &AA = AM.getResult<AAManager>(F); 409 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F); 410 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 411 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F); 412 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F); 413 414 bool Changed = Vectorizer(F, AA, AC, DT, SE, TTI).run(); 415 PreservedAnalyses PA; 416 PA.preserveSet<CFGAnalyses>(); 417 return Changed ? PA : PreservedAnalyses::all(); 418 } 419 420 bool Vectorizer::run() { 421 bool Changed = false; 422 // Break up the BB if there are any instrs which aren't guaranteed to transfer 423 // execution to their successor. 424 // 425 // Consider, for example: 426 // 427 // def assert_arr_len(int n) { if (n < 2) exit(); } 428 // 429 // load arr[0] 430 // call assert_array_len(arr.length) 431 // load arr[1] 432 // 433 // Even though assert_arr_len does not read or write any memory, we can't 434 // speculate the second load before the call. More info at 435 // https://github.com/llvm/llvm-project/issues/52950. 436 for (BasicBlock *BB : post_order(&F)) { 437 // BB must at least have a terminator. 438 assert(!BB->empty()); 439 440 SmallVector<BasicBlock::iterator, 8> Barriers; 441 Barriers.push_back(BB->begin()); 442 for (Instruction &I : *BB) 443 if (!isGuaranteedToTransferExecutionToSuccessor(&I)) 444 Barriers.push_back(I.getIterator()); 445 Barriers.push_back(BB->end()); 446 447 for (auto It = Barriers.begin(), End = std::prev(Barriers.end()); It != End; 448 ++It) 449 Changed |= runOnPseudoBB(*It, *std::next(It)); 450 451 for (Instruction *I : ToErase) { 452 auto *PtrOperand = getLoadStorePointerOperand(I); 453 if (I->use_empty()) 454 I->eraseFromParent(); 455 RecursivelyDeleteTriviallyDeadInstructions(PtrOperand); 456 } 457 ToErase.clear(); 458 } 459 460 return Changed; 461 } 462 463 bool Vectorizer::runOnPseudoBB(BasicBlock::iterator Begin, 464 BasicBlock::iterator End) { 465 LLVM_DEBUG({ 466 dbgs() << "LSV: Running on pseudo-BB [" << *Begin << " ... "; 467 if (End != Begin->getParent()->end()) 468 dbgs() << *End; 469 else 470 dbgs() << "<BB end>"; 471 dbgs() << ")\n"; 472 }); 473 474 bool Changed = false; 475 for (const auto &[EqClassKey, EqClass] : 476 collectEquivalenceClasses(Begin, End)) 477 Changed |= runOnEquivalenceClass(EqClassKey, EqClass); 478 479 return Changed; 480 } 481 482 bool Vectorizer::runOnEquivalenceClass(const EqClassKey &EqClassKey, 483 ArrayRef<Instruction *> EqClass) { 484 bool Changed = false; 485 486 LLVM_DEBUG({ 487 dbgs() << "LSV: Running on equivalence class of size " << EqClass.size() 488 << " keyed on " << EqClassKey << ":\n"; 489 for (Instruction *I : EqClass) 490 dbgs() << " " << *I << "\n"; 491 }); 492 493 std::vector<Chain> Chains = gatherChains(EqClass); 494 LLVM_DEBUG(dbgs() << "LSV: Got " << Chains.size() 495 << " nontrivial chains.\n";); 496 for (Chain &C : Chains) 497 Changed |= runOnChain(C); 498 return Changed; 499 } 500 501 bool Vectorizer::runOnChain(Chain &C) { 502 LLVM_DEBUG({ 503 dbgs() << "LSV: Running on chain with " << C.size() << " instructions:\n"; 504 dumpChain(C); 505 }); 506 507 // Split up the chain into increasingly smaller chains, until we can finally 508 // vectorize the chains. 509 // 510 // (Don't be scared by the depth of the loop nest here. These operations are 511 // all at worst O(n lg n) in the number of instructions, and splitting chains 512 // doesn't change the number of instrs. So the whole loop nest is O(n lg n).) 513 bool Changed = false; 514 for (auto &C : splitChainByMayAliasInstrs(C)) 515 for (auto &C : splitChainByContiguity(C)) 516 for (auto &C : splitChainByAlignment(C)) 517 Changed |= vectorizeChain(C); 518 return Changed; 519 } 520 521 std::vector<Chain> Vectorizer::splitChainByMayAliasInstrs(Chain &C) { 522 if (C.empty()) 523 return {}; 524 525 sortChainInBBOrder(C); 526 527 LLVM_DEBUG({ 528 dbgs() << "LSV: splitChainByMayAliasInstrs considering chain:\n"; 529 dumpChain(C); 530 }); 531 532 // We know that elements in the chain with nonverlapping offsets can't 533 // alias, but AA may not be smart enough to figure this out. Use a 534 // hashtable. 535 DenseMap<Instruction *, APInt /*OffsetFromLeader*/> ChainOffsets; 536 for (const auto &E : C) 537 ChainOffsets.insert({&*E.Inst, E.OffsetFromLeader}); 538 539 // Loads get hoisted up to the first load in the chain. Stores get sunk 540 // down to the last store in the chain. Our algorithm for loads is: 541 // 542 // - Take the first element of the chain. This is the start of a new chain. 543 // - Take the next element of `Chain` and check for may-alias instructions 544 // up to the start of NewChain. If no may-alias instrs, add it to 545 // NewChain. Otherwise, start a new NewChain. 546 // 547 // For stores it's the same except in the reverse direction. 548 // 549 // We expect IsLoad to be an std::bool_constant. 550 auto Impl = [&](auto IsLoad) { 551 // MSVC is unhappy if IsLoad is a capture, so pass it as an arg. 552 auto [ChainBegin, ChainEnd] = [&](auto IsLoad) { 553 if constexpr (IsLoad()) 554 return std::make_pair(C.begin(), C.end()); 555 else 556 return std::make_pair(C.rbegin(), C.rend()); 557 }(IsLoad); 558 assert(ChainBegin != ChainEnd); 559 560 std::vector<Chain> Chains; 561 SmallVector<ChainElem, 1> NewChain; 562 NewChain.push_back(*ChainBegin); 563 for (auto ChainIt = std::next(ChainBegin); ChainIt != ChainEnd; ++ChainIt) { 564 if (isSafeToMove<IsLoad>(ChainIt->Inst, NewChain.front().Inst, 565 ChainOffsets)) { 566 LLVM_DEBUG(dbgs() << "LSV: No intervening may-alias instrs; can merge " 567 << *ChainIt->Inst << " into " << *ChainBegin->Inst 568 << "\n"); 569 NewChain.push_back(*ChainIt); 570 } else { 571 LLVM_DEBUG( 572 dbgs() << "LSV: Found intervening may-alias instrs; cannot merge " 573 << *ChainIt->Inst << " into " << *ChainBegin->Inst << "\n"); 574 if (NewChain.size() > 1) { 575 LLVM_DEBUG({ 576 dbgs() << "LSV: got nontrivial chain without aliasing instrs:\n"; 577 dumpChain(NewChain); 578 }); 579 Chains.push_back(std::move(NewChain)); 580 } 581 582 // Start a new chain. 583 NewChain = SmallVector<ChainElem, 1>({*ChainIt}); 584 } 585 } 586 if (NewChain.size() > 1) { 587 LLVM_DEBUG({ 588 dbgs() << "LSV: got nontrivial chain without aliasing instrs:\n"; 589 dumpChain(NewChain); 590 }); 591 Chains.push_back(std::move(NewChain)); 592 } 593 return Chains; 594 }; 595 596 if (isa<LoadInst>(C[0].Inst)) 597 return Impl(/*IsLoad=*/std::bool_constant<true>()); 598 599 assert(isa<StoreInst>(C[0].Inst)); 600 return Impl(/*IsLoad=*/std::bool_constant<false>()); 601 } 602 603 std::vector<Chain> Vectorizer::splitChainByContiguity(Chain &C) { 604 if (C.empty()) 605 return {}; 606 607 sortChainInOffsetOrder(C); 608 609 LLVM_DEBUG({ 610 dbgs() << "LSV: splitChainByContiguity considering chain:\n"; 611 dumpChain(C); 612 }); 613 614 std::vector<Chain> Ret; 615 Ret.push_back({C.front()}); 616 617 for (auto It = std::next(C.begin()), End = C.end(); It != End; ++It) { 618 // `prev` accesses offsets [PrevDistFromBase, PrevReadEnd). 619 auto &CurChain = Ret.back(); 620 const ChainElem &Prev = CurChain.back(); 621 unsigned SzBits = DL.getTypeSizeInBits(getLoadStoreType(&*Prev.Inst)); 622 assert(SzBits % 8 == 0 && "Non-byte sizes should have been filtered out by " 623 "collectEquivalenceClass"); 624 APInt PrevReadEnd = Prev.OffsetFromLeader + SzBits / 8; 625 626 // Add this instruction to the end of the current chain, or start a new one. 627 bool AreContiguous = It->OffsetFromLeader == PrevReadEnd; 628 LLVM_DEBUG(dbgs() << "LSV: Instructions are " 629 << (AreContiguous ? "" : "not ") << "contiguous: " 630 << *Prev.Inst << " (ends at offset " << PrevReadEnd 631 << ") -> " << *It->Inst << " (starts at offset " 632 << It->OffsetFromLeader << ")\n"); 633 if (AreContiguous) 634 CurChain.push_back(*It); 635 else 636 Ret.push_back({*It}); 637 } 638 639 // Filter out length-1 chains, these are uninteresting. 640 llvm::erase_if(Ret, [](const auto &Chain) { return Chain.size() <= 1; }); 641 return Ret; 642 } 643 644 Type *Vectorizer::getChainElemTy(const Chain &C) { 645 assert(!C.empty()); 646 // The rules are: 647 // - If there are any pointer types in the chain, use an integer type. 648 // - Prefer an integer type if it appears in the chain. 649 // - Otherwise, use the first type in the chain. 650 // 651 // The rule about pointer types is a simplification when we merge e.g. a load 652 // of a ptr and a double. There's no direct conversion from a ptr to a 653 // double; it requires a ptrtoint followed by a bitcast. 654 // 655 // It's unclear to me if the other rules have any practical effect, but we do 656 // it to match this pass's previous behavior. 657 if (any_of(C, [](const ChainElem &E) { 658 return getLoadStoreType(E.Inst)->getScalarType()->isPointerTy(); 659 })) { 660 return Type::getIntNTy( 661 F.getContext(), 662 DL.getTypeSizeInBits(getLoadStoreType(C[0].Inst)->getScalarType())); 663 } 664 665 for (const ChainElem &E : C) 666 if (Type *T = getLoadStoreType(E.Inst)->getScalarType(); T->isIntegerTy()) 667 return T; 668 return getLoadStoreType(C[0].Inst)->getScalarType(); 669 } 670 671 std::vector<Chain> Vectorizer::splitChainByAlignment(Chain &C) { 672 // We use a simple greedy algorithm. 673 // - Given a chain of length N, find all prefixes that 674 // (a) are not longer than the max register length, and 675 // (b) are a power of 2. 676 // - Starting from the longest prefix, try to create a vector of that length. 677 // - If one of them works, great. Repeat the algorithm on any remaining 678 // elements in the chain. 679 // - If none of them work, discard the first element and repeat on a chain 680 // of length N-1. 681 if (C.empty()) 682 return {}; 683 684 sortChainInOffsetOrder(C); 685 686 LLVM_DEBUG({ 687 dbgs() << "LSV: splitChainByAlignment considering chain:\n"; 688 dumpChain(C); 689 }); 690 691 bool IsLoadChain = isa<LoadInst>(C[0].Inst); 692 auto getVectorFactor = [&](unsigned VF, unsigned LoadStoreSize, 693 unsigned ChainSizeBytes, VectorType *VecTy) { 694 return IsLoadChain ? TTI.getLoadVectorFactor(VF, LoadStoreSize, 695 ChainSizeBytes, VecTy) 696 : TTI.getStoreVectorFactor(VF, LoadStoreSize, 697 ChainSizeBytes, VecTy); 698 }; 699 700 #ifndef NDEBUG 701 for (const auto &E : C) { 702 Type *Ty = getLoadStoreType(E.Inst)->getScalarType(); 703 assert(isPowerOf2_32(DL.getTypeSizeInBits(Ty)) && 704 "Should have filtered out non-power-of-two elements in " 705 "collectEquivalenceClasses."); 706 } 707 #endif 708 709 unsigned AS = getLoadStoreAddressSpace(C[0].Inst); 710 unsigned VecRegBytes = TTI.getLoadStoreVecRegBitWidth(AS) / 8; 711 712 std::vector<Chain> Ret; 713 for (unsigned CBegin = 0; CBegin < C.size(); ++CBegin) { 714 // Find candidate chains of size not greater than the largest vector reg. 715 // These chains are over the closed interval [CBegin, CEnd]. 716 SmallVector<std::pair<unsigned /*CEnd*/, unsigned /*SizeBytes*/>, 8> 717 CandidateChains; 718 for (unsigned CEnd = CBegin + 1, Size = C.size(); CEnd < Size; ++CEnd) { 719 APInt Sz = C[CEnd].OffsetFromLeader + 720 DL.getTypeStoreSize(getLoadStoreType(C[CEnd].Inst)) - 721 C[CBegin].OffsetFromLeader; 722 if (Sz.sgt(VecRegBytes)) 723 break; 724 CandidateChains.push_back( 725 {CEnd, static_cast<unsigned>(Sz.getLimitedValue())}); 726 } 727 728 // Consider the longest chain first. 729 for (auto It = CandidateChains.rbegin(), End = CandidateChains.rend(); 730 It != End; ++It) { 731 auto [CEnd, SizeBytes] = *It; 732 LLVM_DEBUG( 733 dbgs() << "LSV: splitChainByAlignment considering candidate chain [" 734 << *C[CBegin].Inst << " ... " << *C[CEnd].Inst << "]\n"); 735 736 Type *VecElemTy = getChainElemTy(C); 737 // Note, VecElemTy is a power of 2, but might be less than one byte. For 738 // example, we can vectorize 2 x <2 x i4> to <4 x i4>, and in this case 739 // VecElemTy would be i4. 740 unsigned VecElemBits = DL.getTypeSizeInBits(VecElemTy); 741 742 // SizeBytes and VecElemBits are powers of 2, so they divide evenly. 743 assert((8 * SizeBytes) % VecElemBits == 0); 744 unsigned NumVecElems = 8 * SizeBytes / VecElemBits; 745 FixedVectorType *VecTy = FixedVectorType::get(VecElemTy, NumVecElems); 746 unsigned VF = 8 * VecRegBytes / VecElemBits; 747 748 // Check that TTI is happy with this vectorization factor. 749 unsigned TargetVF = getVectorFactor(VF, VecElemBits, 750 VecElemBits * NumVecElems / 8, VecTy); 751 if (TargetVF != VF && TargetVF < NumVecElems) { 752 LLVM_DEBUG( 753 dbgs() << "LSV: splitChainByAlignment discarding candidate chain " 754 "because TargetVF=" 755 << TargetVF << " != VF=" << VF 756 << " and TargetVF < NumVecElems=" << NumVecElems << "\n"); 757 continue; 758 } 759 760 // Is a load/store with this alignment allowed by TTI and at least as fast 761 // as an unvectorized load/store? 762 // 763 // TTI and F are passed as explicit captures to WAR an MSVC misparse (??). 764 auto IsAllowedAndFast = [&, SizeBytes = SizeBytes, &TTI = TTI, 765 &F = F](Align Alignment) { 766 if (Alignment.value() % SizeBytes == 0) 767 return true; 768 unsigned VectorizedSpeed = 0; 769 bool AllowsMisaligned = TTI.allowsMisalignedMemoryAccesses( 770 F.getContext(), SizeBytes * 8, AS, Alignment, &VectorizedSpeed); 771 if (!AllowsMisaligned) { 772 LLVM_DEBUG(dbgs() 773 << "LSV: Access of " << SizeBytes << "B in addrspace " 774 << AS << " with alignment " << Alignment.value() 775 << " is misaligned, and therefore can't be vectorized.\n"); 776 return false; 777 } 778 779 unsigned ElementwiseSpeed = 0; 780 (TTI).allowsMisalignedMemoryAccesses((F).getContext(), VecElemBits, AS, 781 Alignment, &ElementwiseSpeed); 782 if (VectorizedSpeed < ElementwiseSpeed) { 783 LLVM_DEBUG(dbgs() 784 << "LSV: Access of " << SizeBytes << "B in addrspace " 785 << AS << " with alignment " << Alignment.value() 786 << " has relative speed " << VectorizedSpeed 787 << ", which is lower than the elementwise speed of " 788 << ElementwiseSpeed 789 << ". Therefore this access won't be vectorized.\n"); 790 return false; 791 } 792 return true; 793 }; 794 795 // If we're loading/storing from an alloca, align it if possible. 796 // 797 // FIXME: We eagerly upgrade the alignment, regardless of whether TTI 798 // tells us this is beneficial. This feels a bit odd, but it matches 799 // existing tests. This isn't *so* bad, because at most we align to 4 800 // bytes (current value of StackAdjustedAlignment). 801 // 802 // FIXME: We will upgrade the alignment of the alloca even if it turns out 803 // we can't vectorize for some other reason. 804 Value *PtrOperand = getLoadStorePointerOperand(C[CBegin].Inst); 805 bool IsAllocaAccess = AS == DL.getAllocaAddrSpace() && 806 isa<AllocaInst>(PtrOperand->stripPointerCasts()); 807 Align Alignment = getLoadStoreAlignment(C[CBegin].Inst); 808 Align PrefAlign = Align(StackAdjustedAlignment); 809 if (IsAllocaAccess && Alignment.value() % SizeBytes != 0 && 810 IsAllowedAndFast(PrefAlign)) { 811 Align NewAlign = getOrEnforceKnownAlignment( 812 PtrOperand, PrefAlign, DL, C[CBegin].Inst, nullptr, &DT); 813 if (NewAlign >= Alignment) { 814 LLVM_DEBUG(dbgs() 815 << "LSV: splitByChain upgrading alloca alignment from " 816 << Alignment.value() << " to " << NewAlign.value() 817 << "\n"); 818 Alignment = NewAlign; 819 } 820 } 821 822 if (!IsAllowedAndFast(Alignment)) { 823 LLVM_DEBUG( 824 dbgs() << "LSV: splitChainByAlignment discarding candidate chain " 825 "because its alignment is not AllowedAndFast: " 826 << Alignment.value() << "\n"); 827 continue; 828 } 829 830 if ((IsLoadChain && 831 !TTI.isLegalToVectorizeLoadChain(SizeBytes, Alignment, AS)) || 832 (!IsLoadChain && 833 !TTI.isLegalToVectorizeStoreChain(SizeBytes, Alignment, AS))) { 834 LLVM_DEBUG( 835 dbgs() << "LSV: splitChainByAlignment discarding candidate chain " 836 "because !isLegalToVectorizeLoad/StoreChain."); 837 continue; 838 } 839 840 // Hooray, we can vectorize this chain! 841 Chain &NewChain = Ret.emplace_back(); 842 for (unsigned I = CBegin; I <= CEnd; ++I) 843 NewChain.push_back(C[I]); 844 CBegin = CEnd; // Skip over the instructions we've added to the chain. 845 break; 846 } 847 } 848 return Ret; 849 } 850 851 bool Vectorizer::vectorizeChain(Chain &C) { 852 if (C.size() < 2) 853 return false; 854 855 sortChainInOffsetOrder(C); 856 857 LLVM_DEBUG({ 858 dbgs() << "LSV: Vectorizing chain of " << C.size() << " instructions:\n"; 859 dumpChain(C); 860 }); 861 862 Type *VecElemTy = getChainElemTy(C); 863 bool IsLoadChain = isa<LoadInst>(C[0].Inst); 864 unsigned AS = getLoadStoreAddressSpace(C[0].Inst); 865 unsigned ChainBytes = std::accumulate( 866 C.begin(), C.end(), 0u, [&](unsigned Bytes, const ChainElem &E) { 867 return Bytes + DL.getTypeStoreSize(getLoadStoreType(E.Inst)); 868 }); 869 assert(ChainBytes % DL.getTypeStoreSize(VecElemTy) == 0); 870 // VecTy is a power of 2 and 1 byte at smallest, but VecElemTy may be smaller 871 // than 1 byte (e.g. VecTy == <32 x i1>). 872 Type *VecTy = FixedVectorType::get( 873 VecElemTy, 8 * ChainBytes / DL.getTypeSizeInBits(VecElemTy)); 874 875 Align Alignment = getLoadStoreAlignment(C[0].Inst); 876 // If this is a load/store of an alloca, we might have upgraded the alloca's 877 // alignment earlier. Get the new alignment. 878 if (AS == DL.getAllocaAddrSpace()) { 879 Alignment = std::max( 880 Alignment, 881 getOrEnforceKnownAlignment(getLoadStorePointerOperand(C[0].Inst), 882 MaybeAlign(), DL, C[0].Inst, nullptr, &DT)); 883 } 884 885 // All elements of the chain must have the same scalar-type size. 886 #ifndef NDEBUG 887 for (const ChainElem &E : C) 888 assert(DL.getTypeStoreSize(getLoadStoreType(E.Inst)->getScalarType()) == 889 DL.getTypeStoreSize(VecElemTy)); 890 #endif 891 892 Instruction *VecInst; 893 if (IsLoadChain) { 894 // Loads get hoisted to the location of the first load in the chain. We may 895 // also need to hoist the (transitive) operands of the loads. 896 Builder.SetInsertPoint( 897 std::min_element(C.begin(), C.end(), [](const auto &A, const auto &B) { 898 return A.Inst->comesBefore(B.Inst); 899 })->Inst); 900 901 // Chain is in offset order, so C[0] is the instr with the lowest offset, 902 // i.e. the root of the vector. 903 Value *Bitcast = Builder.CreateBitCast( 904 getLoadStorePointerOperand(C[0].Inst), VecTy->getPointerTo(AS)); 905 VecInst = Builder.CreateAlignedLoad(VecTy, Bitcast, Alignment); 906 907 unsigned VecIdx = 0; 908 for (const ChainElem &E : C) { 909 Instruction *I = E.Inst; 910 Value *V; 911 Type *T = getLoadStoreType(I); 912 if (auto *VT = dyn_cast<FixedVectorType>(T)) { 913 auto Mask = llvm::to_vector<8>( 914 llvm::seq<int>(VecIdx, VecIdx + VT->getNumElements())); 915 V = Builder.CreateShuffleVector(VecInst, Mask, I->getName()); 916 VecIdx += VT->getNumElements(); 917 } else { 918 V = Builder.CreateExtractElement(VecInst, Builder.getInt32(VecIdx), 919 I->getName()); 920 ++VecIdx; 921 } 922 if (V->getType() != I->getType()) 923 V = Builder.CreateBitOrPointerCast(V, I->getType()); 924 I->replaceAllUsesWith(V); 925 } 926 927 // Finally, we need to reorder the instrs in the BB so that the (transitive) 928 // operands of VecInst appear before it. To see why, suppose we have 929 // vectorized the following code: 930 // 931 // ptr1 = gep a, 1 932 // load1 = load i32 ptr1 933 // ptr0 = gep a, 0 934 // load0 = load i32 ptr0 935 // 936 // We will put the vectorized load at the location of the earliest load in 937 // the BB, i.e. load1. We get: 938 // 939 // ptr1 = gep a, 1 940 // loadv = load <2 x i32> ptr0 941 // load0 = extractelement loadv, 0 942 // load1 = extractelement loadv, 1 943 // ptr0 = gep a, 0 944 // 945 // Notice that loadv uses ptr0, which is defined *after* it! 946 reorder(VecInst); 947 } else { 948 // Stores get sunk to the location of the last store in the chain. 949 Builder.SetInsertPoint( 950 std::max_element(C.begin(), C.end(), [](auto &A, auto &B) { 951 return A.Inst->comesBefore(B.Inst); 952 })->Inst); 953 954 // Build the vector to store. 955 Value *Vec = PoisonValue::get(VecTy); 956 unsigned VecIdx = 0; 957 auto InsertElem = [&](Value *V) { 958 if (V->getType() != VecElemTy) 959 V = Builder.CreateBitOrPointerCast(V, VecElemTy); 960 Vec = Builder.CreateInsertElement(Vec, V, Builder.getInt32(VecIdx++)); 961 }; 962 for (const ChainElem &E : C) { 963 auto I = cast<StoreInst>(E.Inst); 964 if (FixedVectorType *VT = 965 dyn_cast<FixedVectorType>(getLoadStoreType(I))) { 966 for (int J = 0, JE = VT->getNumElements(); J < JE; ++J) { 967 InsertElem(Builder.CreateExtractElement(I->getValueOperand(), 968 Builder.getInt32(J))); 969 } 970 } else { 971 InsertElem(I->getValueOperand()); 972 } 973 } 974 975 // Chain is in offset order, so C[0] is the instr with the lowest offset, 976 // i.e. the root of the vector. 977 VecInst = Builder.CreateAlignedStore( 978 Vec, 979 Builder.CreateBitCast(getLoadStorePointerOperand(C[0].Inst), 980 VecTy->getPointerTo(AS)), 981 Alignment); 982 } 983 984 propagateMetadata(VecInst, C); 985 986 for (const ChainElem &E : C) 987 ToErase.push_back(E.Inst); 988 989 ++NumVectorInstructions; 990 NumScalarsVectorized += C.size(); 991 return true; 992 } 993 994 template <bool IsLoadChain> 995 bool Vectorizer::isSafeToMove( 996 Instruction *ChainElem, Instruction *ChainBegin, 997 const DenseMap<Instruction *, APInt /*OffsetFromLeader*/> &ChainOffsets) { 998 LLVM_DEBUG(dbgs() << "LSV: isSafeToMove(" << *ChainElem << " -> " 999 << *ChainBegin << ")\n"); 1000 1001 assert(isa<LoadInst>(ChainElem) == IsLoadChain); 1002 if (ChainElem == ChainBegin) 1003 return true; 1004 1005 // Invariant loads can always be reordered; by definition they are not 1006 // clobbered by stores. 1007 if (isInvariantLoad(ChainElem)) 1008 return true; 1009 1010 auto BBIt = std::next([&] { 1011 if constexpr (IsLoadChain) 1012 return BasicBlock::reverse_iterator(ChainElem); 1013 else 1014 return BasicBlock::iterator(ChainElem); 1015 }()); 1016 auto BBItEnd = std::next([&] { 1017 if constexpr (IsLoadChain) 1018 return BasicBlock::reverse_iterator(ChainBegin); 1019 else 1020 return BasicBlock::iterator(ChainBegin); 1021 }()); 1022 1023 const APInt &ChainElemOffset = ChainOffsets.at(ChainElem); 1024 const unsigned ChainElemSize = 1025 DL.getTypeStoreSize(getLoadStoreType(ChainElem)); 1026 1027 for (; BBIt != BBItEnd; ++BBIt) { 1028 Instruction *I = &*BBIt; 1029 1030 if (!I->mayReadOrWriteMemory()) 1031 continue; 1032 1033 // Loads can be reordered with other loads. 1034 if (IsLoadChain && isa<LoadInst>(I)) 1035 continue; 1036 1037 // Stores can be sunk below invariant loads. 1038 if (!IsLoadChain && isInvariantLoad(I)) 1039 continue; 1040 1041 // If I is in the chain, we can tell whether it aliases ChainIt by checking 1042 // what offset ChainIt accesses. This may be better than AA is able to do. 1043 // 1044 // We should really only have duplicate offsets for stores (the duplicate 1045 // loads should be CSE'ed), but in case we have a duplicate load, we'll 1046 // split the chain so we don't have to handle this case specially. 1047 if (auto OffsetIt = ChainOffsets.find(I); OffsetIt != ChainOffsets.end()) { 1048 // I and ChainElem overlap if: 1049 // - I and ChainElem have the same offset, OR 1050 // - I's offset is less than ChainElem's, but I touches past the 1051 // beginning of ChainElem, OR 1052 // - ChainElem's offset is less than I's, but ChainElem touches past the 1053 // beginning of I. 1054 const APInt &IOffset = OffsetIt->second; 1055 unsigned IElemSize = DL.getTypeStoreSize(getLoadStoreType(I)); 1056 if (IOffset == ChainElemOffset || 1057 (IOffset.sle(ChainElemOffset) && 1058 (IOffset + IElemSize).sgt(ChainElemOffset)) || 1059 (ChainElemOffset.sle(IOffset) && 1060 (ChainElemOffset + ChainElemSize).sgt(OffsetIt->second))) { 1061 LLVM_DEBUG({ 1062 // Double check that AA also sees this alias. If not, we probably 1063 // have a bug. 1064 ModRefInfo MR = AA.getModRefInfo(I, MemoryLocation::get(ChainElem)); 1065 assert(IsLoadChain ? isModSet(MR) : isModOrRefSet(MR)); 1066 dbgs() << "LSV: Found alias in chain: " << *I << "\n"; 1067 }); 1068 return false; // We found an aliasing instruction; bail. 1069 } 1070 1071 continue; // We're confident there's no alias. 1072 } 1073 1074 LLVM_DEBUG(dbgs() << "LSV: Querying AA for " << *I << "\n"); 1075 ModRefInfo MR = AA.getModRefInfo(I, MemoryLocation::get(ChainElem)); 1076 if (IsLoadChain ? isModSet(MR) : isModOrRefSet(MR)) { 1077 LLVM_DEBUG(dbgs() << "LSV: Found alias in chain:\n" 1078 << " Aliasing instruction:\n" 1079 << " " << *I << '\n' 1080 << " Aliased instruction and pointer:\n" 1081 << " " << *ChainElem << '\n' 1082 << " " << *getLoadStorePointerOperand(ChainElem) 1083 << '\n'); 1084 1085 return false; 1086 } 1087 } 1088 return true; 1089 } 1090 1091 static bool checkNoWrapFlags(Instruction *I, bool Signed) { 1092 BinaryOperator *BinOpI = cast<BinaryOperator>(I); 1093 return (Signed && BinOpI->hasNoSignedWrap()) || 1094 (!Signed && BinOpI->hasNoUnsignedWrap()); 1095 } 1096 1097 static bool checkIfSafeAddSequence(const APInt &IdxDiff, Instruction *AddOpA, 1098 unsigned MatchingOpIdxA, Instruction *AddOpB, 1099 unsigned MatchingOpIdxB, bool Signed) { 1100 LLVM_DEBUG(dbgs() << "LSV: checkIfSafeAddSequence IdxDiff=" << IdxDiff 1101 << ", AddOpA=" << *AddOpA << ", MatchingOpIdxA=" 1102 << MatchingOpIdxA << ", AddOpB=" << *AddOpB 1103 << ", MatchingOpIdxB=" << MatchingOpIdxB 1104 << ", Signed=" << Signed << "\n"); 1105 // If both OpA and OpB are adds with NSW/NUW and with one of the operands 1106 // being the same, we can guarantee that the transformation is safe if we can 1107 // prove that OpA won't overflow when Ret added to the other operand of OpA. 1108 // For example: 1109 // %tmp7 = add nsw i32 %tmp2, %v0 1110 // %tmp8 = sext i32 %tmp7 to i64 1111 // ... 1112 // %tmp11 = add nsw i32 %v0, 1 1113 // %tmp12 = add nsw i32 %tmp2, %tmp11 1114 // %tmp13 = sext i32 %tmp12 to i64 1115 // 1116 // Both %tmp7 and %tmp12 have the nsw flag and the first operand is %tmp2. 1117 // It's guaranteed that adding 1 to %tmp7 won't overflow because %tmp11 adds 1118 // 1 to %v0 and both %tmp11 and %tmp12 have the nsw flag. 1119 assert(AddOpA->getOpcode() == Instruction::Add && 1120 AddOpB->getOpcode() == Instruction::Add && 1121 checkNoWrapFlags(AddOpA, Signed) && checkNoWrapFlags(AddOpB, Signed)); 1122 if (AddOpA->getOperand(MatchingOpIdxA) == 1123 AddOpB->getOperand(MatchingOpIdxB)) { 1124 Value *OtherOperandA = AddOpA->getOperand(MatchingOpIdxA == 1 ? 0 : 1); 1125 Value *OtherOperandB = AddOpB->getOperand(MatchingOpIdxB == 1 ? 0 : 1); 1126 Instruction *OtherInstrA = dyn_cast<Instruction>(OtherOperandA); 1127 Instruction *OtherInstrB = dyn_cast<Instruction>(OtherOperandB); 1128 // Match `x +nsw/nuw y` and `x +nsw/nuw (y +nsw/nuw IdxDiff)`. 1129 if (OtherInstrB && OtherInstrB->getOpcode() == Instruction::Add && 1130 checkNoWrapFlags(OtherInstrB, Signed) && 1131 isa<ConstantInt>(OtherInstrB->getOperand(1))) { 1132 int64_t CstVal = 1133 cast<ConstantInt>(OtherInstrB->getOperand(1))->getSExtValue(); 1134 if (OtherInstrB->getOperand(0) == OtherOperandA && 1135 IdxDiff.getSExtValue() == CstVal) 1136 return true; 1137 } 1138 // Match `x +nsw/nuw (y +nsw/nuw -Idx)` and `x +nsw/nuw (y +nsw/nuw x)`. 1139 if (OtherInstrA && OtherInstrA->getOpcode() == Instruction::Add && 1140 checkNoWrapFlags(OtherInstrA, Signed) && 1141 isa<ConstantInt>(OtherInstrA->getOperand(1))) { 1142 int64_t CstVal = 1143 cast<ConstantInt>(OtherInstrA->getOperand(1))->getSExtValue(); 1144 if (OtherInstrA->getOperand(0) == OtherOperandB && 1145 IdxDiff.getSExtValue() == -CstVal) 1146 return true; 1147 } 1148 // Match `x +nsw/nuw (y +nsw/nuw c)` and 1149 // `x +nsw/nuw (y +nsw/nuw (c + IdxDiff))`. 1150 if (OtherInstrA && OtherInstrB && 1151 OtherInstrA->getOpcode() == Instruction::Add && 1152 OtherInstrB->getOpcode() == Instruction::Add && 1153 checkNoWrapFlags(OtherInstrA, Signed) && 1154 checkNoWrapFlags(OtherInstrB, Signed) && 1155 isa<ConstantInt>(OtherInstrA->getOperand(1)) && 1156 isa<ConstantInt>(OtherInstrB->getOperand(1))) { 1157 int64_t CstValA = 1158 cast<ConstantInt>(OtherInstrA->getOperand(1))->getSExtValue(); 1159 int64_t CstValB = 1160 cast<ConstantInt>(OtherInstrB->getOperand(1))->getSExtValue(); 1161 if (OtherInstrA->getOperand(0) == OtherInstrB->getOperand(0) && 1162 IdxDiff.getSExtValue() == (CstValB - CstValA)) 1163 return true; 1164 } 1165 } 1166 return false; 1167 } 1168 1169 std::optional<APInt> Vectorizer::getConstantOffsetComplexAddrs( 1170 Value *PtrA, Value *PtrB, Instruction *ContextInst, unsigned Depth) { 1171 LLVM_DEBUG(dbgs() << "LSV: getConstantOffsetComplexAddrs PtrA=" << *PtrA 1172 << " PtrB=" << *PtrB << " ContextInst=" << *ContextInst 1173 << " Depth=" << Depth << "\n"); 1174 auto *GEPA = dyn_cast<GetElementPtrInst>(PtrA); 1175 auto *GEPB = dyn_cast<GetElementPtrInst>(PtrB); 1176 if (!GEPA || !GEPB) 1177 return getConstantOffsetSelects(PtrA, PtrB, ContextInst, Depth); 1178 1179 // Look through GEPs after checking they're the same except for the last 1180 // index. 1181 if (GEPA->getNumOperands() != GEPB->getNumOperands() || 1182 GEPA->getPointerOperand() != GEPB->getPointerOperand()) 1183 return std::nullopt; 1184 gep_type_iterator GTIA = gep_type_begin(GEPA); 1185 gep_type_iterator GTIB = gep_type_begin(GEPB); 1186 for (unsigned I = 0, E = GEPA->getNumIndices() - 1; I < E; ++I) { 1187 if (GTIA.getOperand() != GTIB.getOperand()) 1188 return std::nullopt; 1189 ++GTIA; 1190 ++GTIB; 1191 } 1192 1193 Instruction *OpA = dyn_cast<Instruction>(GTIA.getOperand()); 1194 Instruction *OpB = dyn_cast<Instruction>(GTIB.getOperand()); 1195 if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() || 1196 OpA->getType() != OpB->getType()) 1197 return std::nullopt; 1198 1199 uint64_t Stride = DL.getTypeAllocSize(GTIA.getIndexedType()); 1200 1201 // Only look through a ZExt/SExt. 1202 if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA)) 1203 return std::nullopt; 1204 1205 bool Signed = isa<SExtInst>(OpA); 1206 1207 // At this point A could be a function parameter, i.e. not an instruction 1208 Value *ValA = OpA->getOperand(0); 1209 OpB = dyn_cast<Instruction>(OpB->getOperand(0)); 1210 if (!OpB || ValA->getType() != OpB->getType()) 1211 return std::nullopt; 1212 1213 const SCEV *OffsetSCEVA = SE.getSCEV(ValA); 1214 const SCEV *OffsetSCEVB = SE.getSCEV(OpB); 1215 const SCEV *IdxDiffSCEV = SE.getMinusSCEV(OffsetSCEVB, OffsetSCEVA); 1216 if (IdxDiffSCEV == SE.getCouldNotCompute()) 1217 return std::nullopt; 1218 1219 ConstantRange IdxDiffRange = SE.getSignedRange(IdxDiffSCEV); 1220 if (!IdxDiffRange.isSingleElement()) 1221 return std::nullopt; 1222 APInt IdxDiff = *IdxDiffRange.getSingleElement(); 1223 1224 LLVM_DEBUG(dbgs() << "LSV: getConstantOffsetComplexAddrs IdxDiff=" << IdxDiff 1225 << "\n"); 1226 1227 // Now we need to prove that adding IdxDiff to ValA won't overflow. 1228 bool Safe = false; 1229 1230 // First attempt: if OpB is an add with NSW/NUW, and OpB is IdxDiff added to 1231 // ValA, we're okay. 1232 if (OpB->getOpcode() == Instruction::Add && 1233 isa<ConstantInt>(OpB->getOperand(1)) && 1234 IdxDiff.sle(cast<ConstantInt>(OpB->getOperand(1))->getSExtValue()) && 1235 checkNoWrapFlags(OpB, Signed)) 1236 Safe = true; 1237 1238 // Second attempt: check if we have eligible add NSW/NUW instruction 1239 // sequences. 1240 OpA = dyn_cast<Instruction>(ValA); 1241 if (!Safe && OpA && OpA->getOpcode() == Instruction::Add && 1242 OpB->getOpcode() == Instruction::Add && checkNoWrapFlags(OpA, Signed) && 1243 checkNoWrapFlags(OpB, Signed)) { 1244 // In the checks below a matching operand in OpA and OpB is an operand which 1245 // is the same in those two instructions. Below we account for possible 1246 // orders of the operands of these add instructions. 1247 for (unsigned MatchingOpIdxA : {0, 1}) 1248 for (unsigned MatchingOpIdxB : {0, 1}) 1249 if (!Safe) 1250 Safe = checkIfSafeAddSequence(IdxDiff, OpA, MatchingOpIdxA, OpB, 1251 MatchingOpIdxB, Signed); 1252 } 1253 1254 unsigned BitWidth = ValA->getType()->getScalarSizeInBits(); 1255 1256 // Third attempt: 1257 // 1258 // Assuming IdxDiff is positive: If all set bits of IdxDiff or any higher 1259 // order bit other than the sign bit are known to be zero in ValA, we can add 1260 // Diff to it while guaranteeing no overflow of any sort. 1261 // 1262 // If IdxDiff is negative, do the same, but swap ValA and ValB. 1263 if (!Safe) { 1264 // When computing known bits, use the GEPs as context instructions, since 1265 // they likely are in the same BB as the load/store. 1266 KnownBits Known(BitWidth); 1267 computeKnownBits((IdxDiff.sge(0) ? ValA : OpB), Known, DL, 0, &AC, 1268 ContextInst, &DT); 1269 APInt BitsAllowedToBeSet = Known.Zero.zext(IdxDiff.getBitWidth()); 1270 if (Signed) 1271 BitsAllowedToBeSet.clearBit(BitWidth - 1); 1272 if (BitsAllowedToBeSet.ult(IdxDiff.abs())) 1273 return std::nullopt; 1274 Safe = true; 1275 } 1276 1277 if (Safe) 1278 return IdxDiff * Stride; 1279 return std::nullopt; 1280 } 1281 1282 std::optional<APInt> Vectorizer::getConstantOffsetSelects( 1283 Value *PtrA, Value *PtrB, Instruction *ContextInst, unsigned Depth) { 1284 if (Depth++ == MaxDepth) 1285 return std::nullopt; 1286 1287 if (auto *SelectA = dyn_cast<SelectInst>(PtrA)) { 1288 if (auto *SelectB = dyn_cast<SelectInst>(PtrB)) { 1289 if (SelectA->getCondition() != SelectB->getCondition()) 1290 return std::nullopt; 1291 LLVM_DEBUG(dbgs() << "LSV: getConstantOffsetSelects, PtrA=" << *PtrA 1292 << ", PtrB=" << *PtrB << ", ContextInst=" 1293 << *ContextInst << ", Depth=" << Depth << "\n"); 1294 std::optional<APInt> TrueDiff = getConstantOffset( 1295 SelectA->getTrueValue(), SelectB->getTrueValue(), ContextInst, Depth); 1296 if (!TrueDiff.has_value()) 1297 return std::nullopt; 1298 std::optional<APInt> FalseDiff = 1299 getConstantOffset(SelectA->getFalseValue(), SelectB->getFalseValue(), 1300 ContextInst, Depth); 1301 if (TrueDiff == FalseDiff) 1302 return TrueDiff; 1303 } 1304 } 1305 return std::nullopt; 1306 } 1307 1308 EquivalenceClassMap 1309 Vectorizer::collectEquivalenceClasses(BasicBlock::iterator Begin, 1310 BasicBlock::iterator End) { 1311 EquivalenceClassMap Ret; 1312 1313 auto getUnderlyingObject = [](const Value *Ptr) -> const Value * { 1314 const Value *ObjPtr = llvm::getUnderlyingObject(Ptr); 1315 if (const auto *Sel = dyn_cast<SelectInst>(ObjPtr)) { 1316 // The select's themselves are distinct instructions even if they share 1317 // the same condition and evaluate to consecutive pointers for true and 1318 // false values of the condition. Therefore using the select's themselves 1319 // for grouping instructions would put consecutive accesses into different 1320 // lists and they won't be even checked for being consecutive, and won't 1321 // be vectorized. 1322 return Sel->getCondition(); 1323 } 1324 return ObjPtr; 1325 }; 1326 1327 for (Instruction &I : make_range(Begin, End)) { 1328 auto *LI = dyn_cast<LoadInst>(&I); 1329 auto *SI = dyn_cast<StoreInst>(&I); 1330 if (!LI && !SI) 1331 continue; 1332 1333 if ((LI && !LI->isSimple()) || (SI && !SI->isSimple())) 1334 continue; 1335 1336 if ((LI && !TTI.isLegalToVectorizeLoad(LI)) || 1337 (SI && !TTI.isLegalToVectorizeStore(SI))) 1338 continue; 1339 1340 Type *Ty = getLoadStoreType(&I); 1341 if (!VectorType::isValidElementType(Ty->getScalarType())) 1342 continue; 1343 1344 // Skip weird non-byte sizes. They probably aren't worth the effort of 1345 // handling correctly. 1346 unsigned TySize = DL.getTypeSizeInBits(Ty); 1347 if ((TySize % 8) != 0) 1348 continue; 1349 1350 // Skip vectors of pointers. The vectorizeLoadChain/vectorizeStoreChain 1351 // functions are currently using an integer type for the vectorized 1352 // load/store, and does not support casting between the integer type and a 1353 // vector of pointers (e.g. i64 to <2 x i16*>) 1354 if (Ty->isVectorTy() && Ty->isPtrOrPtrVectorTy()) 1355 continue; 1356 1357 Value *Ptr = getLoadStorePointerOperand(&I); 1358 unsigned AS = Ptr->getType()->getPointerAddressSpace(); 1359 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 1360 1361 unsigned VF = VecRegSize / TySize; 1362 VectorType *VecTy = dyn_cast<VectorType>(Ty); 1363 1364 // Only handle power-of-two sized elements. 1365 if ((!VecTy && !isPowerOf2_32(DL.getTypeSizeInBits(Ty))) || 1366 (VecTy && !isPowerOf2_32(DL.getTypeSizeInBits(VecTy->getScalarType())))) 1367 continue; 1368 1369 // No point in looking at these if they're too big to vectorize. 1370 if (TySize > VecRegSize / 2 || 1371 (VecTy && TTI.getLoadVectorFactor(VF, TySize, TySize / 8, VecTy) == 0)) 1372 continue; 1373 1374 Ret[{getUnderlyingObject(Ptr), AS, 1375 DL.getTypeSizeInBits(getLoadStoreType(&I)->getScalarType()), 1376 /*IsLoad=*/LI != nullptr}] 1377 .push_back(&I); 1378 } 1379 1380 return Ret; 1381 } 1382 1383 std::vector<Chain> Vectorizer::gatherChains(ArrayRef<Instruction *> Instrs) { 1384 if (Instrs.empty()) 1385 return {}; 1386 1387 unsigned AS = getLoadStoreAddressSpace(Instrs[0]); 1388 unsigned ASPtrBits = DL.getIndexSizeInBits(AS); 1389 1390 #ifndef NDEBUG 1391 // Check that Instrs is in BB order and all have the same addr space. 1392 for (size_t I = 1; I < Instrs.size(); ++I) { 1393 assert(Instrs[I - 1]->comesBefore(Instrs[I])); 1394 assert(getLoadStoreAddressSpace(Instrs[I]) == AS); 1395 } 1396 #endif 1397 1398 // Machinery to build an MRU-hashtable of Chains. 1399 // 1400 // (Ideally this could be done with MapVector, but as currently implemented, 1401 // moving an element to the front of a MapVector is O(n).) 1402 struct InstrListElem : ilist_node<InstrListElem>, 1403 std::pair<Instruction *, Chain> { 1404 explicit InstrListElem(Instruction *I) 1405 : std::pair<Instruction *, Chain>(I, {}) {} 1406 }; 1407 struct InstrListElemDenseMapInfo { 1408 using PtrInfo = DenseMapInfo<InstrListElem *>; 1409 using IInfo = DenseMapInfo<Instruction *>; 1410 static InstrListElem *getEmptyKey() { return PtrInfo::getEmptyKey(); } 1411 static InstrListElem *getTombstoneKey() { 1412 return PtrInfo::getTombstoneKey(); 1413 } 1414 static unsigned getHashValue(const InstrListElem *E) { 1415 return IInfo::getHashValue(E->first); 1416 } 1417 static bool isEqual(const InstrListElem *A, const InstrListElem *B) { 1418 if (A == getEmptyKey() || B == getEmptyKey()) 1419 return A == getEmptyKey() && B == getEmptyKey(); 1420 if (A == getTombstoneKey() || B == getTombstoneKey()) 1421 return A == getTombstoneKey() && B == getTombstoneKey(); 1422 return IInfo::isEqual(A->first, B->first); 1423 } 1424 }; 1425 SpecificBumpPtrAllocator<InstrListElem> Allocator; 1426 simple_ilist<InstrListElem> MRU; 1427 DenseSet<InstrListElem *, InstrListElemDenseMapInfo> Chains; 1428 1429 // Compare each instruction in `instrs` to leader of the N most recently-used 1430 // chains. This limits the O(n^2) behavior of this pass while also allowing 1431 // us to build arbitrarily long chains. 1432 for (Instruction *I : Instrs) { 1433 constexpr int MaxChainsToTry = 64; 1434 1435 bool MatchFound = false; 1436 auto ChainIter = MRU.begin(); 1437 for (size_t J = 0; J < MaxChainsToTry && ChainIter != MRU.end(); 1438 ++J, ++ChainIter) { 1439 std::optional<APInt> Offset = getConstantOffset( 1440 getLoadStorePointerOperand(ChainIter->first), 1441 getLoadStorePointerOperand(I), 1442 /*ContextInst=*/ 1443 (ChainIter->first->comesBefore(I) ? I : ChainIter->first)); 1444 if (Offset.has_value()) { 1445 // `Offset` might not have the expected number of bits, if e.g. AS has a 1446 // different number of bits than opaque pointers. 1447 ChainIter->second.push_back(ChainElem{I, Offset.value()}); 1448 // Move ChainIter to the front of the MRU list. 1449 MRU.remove(*ChainIter); 1450 MRU.push_front(*ChainIter); 1451 MatchFound = true; 1452 break; 1453 } 1454 } 1455 1456 if (!MatchFound) { 1457 APInt ZeroOffset(ASPtrBits, 0); 1458 InstrListElem *E = new (Allocator.Allocate()) InstrListElem(I); 1459 E->second.push_back(ChainElem{I, ZeroOffset}); 1460 MRU.push_front(*E); 1461 Chains.insert(E); 1462 } 1463 } 1464 1465 std::vector<Chain> Ret; 1466 Ret.reserve(Chains.size()); 1467 // Iterate over MRU rather than Chains so the order is deterministic. 1468 for (auto &E : MRU) 1469 if (E.second.size() > 1) 1470 Ret.push_back(std::move(E.second)); 1471 return Ret; 1472 } 1473 1474 std::optional<APInt> Vectorizer::getConstantOffset(Value *PtrA, Value *PtrB, 1475 Instruction *ContextInst, 1476 unsigned Depth) { 1477 LLVM_DEBUG(dbgs() << "LSV: getConstantOffset, PtrA=" << *PtrA 1478 << ", PtrB=" << *PtrB << ", ContextInst= " << *ContextInst 1479 << ", Depth=" << Depth << "\n"); 1480 // We'll ultimately return a value of this bit width, even if computations 1481 // happen in a different width. 1482 unsigned OrigBitWidth = DL.getIndexTypeSizeInBits(PtrA->getType()); 1483 APInt OffsetA(OrigBitWidth, 0); 1484 APInt OffsetB(OrigBitWidth, 0); 1485 PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA); 1486 PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB); 1487 unsigned NewPtrBitWidth = DL.getTypeStoreSizeInBits(PtrA->getType()); 1488 if (NewPtrBitWidth != DL.getTypeStoreSizeInBits(PtrB->getType())) 1489 return std::nullopt; 1490 1491 // If we have to shrink the pointer, stripAndAccumulateInBoundsConstantOffsets 1492 // should properly handle a possible overflow and the value should fit into 1493 // the smallest data type used in the cast/gep chain. 1494 assert(OffsetA.getSignificantBits() <= NewPtrBitWidth && 1495 OffsetB.getSignificantBits() <= NewPtrBitWidth); 1496 1497 OffsetA = OffsetA.sextOrTrunc(NewPtrBitWidth); 1498 OffsetB = OffsetB.sextOrTrunc(NewPtrBitWidth); 1499 if (PtrA == PtrB) 1500 return (OffsetB - OffsetA).sextOrTrunc(OrigBitWidth); 1501 1502 // Try to compute B - A. 1503 const SCEV *DistScev = SE.getMinusSCEV(SE.getSCEV(PtrB), SE.getSCEV(PtrA)); 1504 if (DistScev != SE.getCouldNotCompute()) { 1505 LLVM_DEBUG(dbgs() << "LSV: SCEV PtrB - PtrA =" << *DistScev << "\n"); 1506 ConstantRange DistRange = SE.getSignedRange(DistScev); 1507 if (DistRange.isSingleElement()) { 1508 // Handle index width (the width of Dist) != pointer width (the width of 1509 // the Offset*s at this point). 1510 APInt Dist = DistRange.getSingleElement()->sextOrTrunc(NewPtrBitWidth); 1511 return (OffsetB - OffsetA + Dist).sextOrTrunc(OrigBitWidth); 1512 } 1513 } 1514 std::optional<APInt> Diff = 1515 getConstantOffsetComplexAddrs(PtrA, PtrB, ContextInst, Depth); 1516 if (Diff.has_value()) 1517 return (OffsetB - OffsetA + Diff->sext(OffsetB.getBitWidth())) 1518 .sextOrTrunc(OrigBitWidth); 1519 return std::nullopt; 1520 } 1521