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 #include "llvm/Transforms/Vectorize/LoadStoreVectorizer.h" 42 #include "llvm/ADT/APInt.h" 43 #include "llvm/ADT/ArrayRef.h" 44 #include "llvm/ADT/MapVector.h" 45 #include "llvm/ADT/PostOrderIterator.h" 46 #include "llvm/ADT/STLExtras.h" 47 #include "llvm/ADT/SmallPtrSet.h" 48 #include "llvm/ADT/SmallVector.h" 49 #include "llvm/ADT/Statistic.h" 50 #include "llvm/ADT/iterator_range.h" 51 #include "llvm/Analysis/AliasAnalysis.h" 52 #include "llvm/Analysis/AssumptionCache.h" 53 #include "llvm/Analysis/MemoryLocation.h" 54 #include "llvm/Analysis/ScalarEvolution.h" 55 #include "llvm/Analysis/TargetTransformInfo.h" 56 #include "llvm/Analysis/ValueTracking.h" 57 #include "llvm/Analysis/VectorUtils.h" 58 #include "llvm/IR/Attributes.h" 59 #include "llvm/IR/BasicBlock.h" 60 #include "llvm/IR/Constants.h" 61 #include "llvm/IR/DataLayout.h" 62 #include "llvm/IR/DerivedTypes.h" 63 #include "llvm/IR/Dominators.h" 64 #include "llvm/IR/Function.h" 65 #include "llvm/IR/IRBuilder.h" 66 #include "llvm/IR/InstrTypes.h" 67 #include "llvm/IR/Instruction.h" 68 #include "llvm/IR/Instructions.h" 69 #include "llvm/IR/IntrinsicInst.h" 70 #include "llvm/IR/Module.h" 71 #include "llvm/IR/Type.h" 72 #include "llvm/IR/User.h" 73 #include "llvm/IR/Value.h" 74 #include "llvm/InitializePasses.h" 75 #include "llvm/Pass.h" 76 #include "llvm/Support/Casting.h" 77 #include "llvm/Support/Debug.h" 78 #include "llvm/Support/KnownBits.h" 79 #include "llvm/Support/MathExtras.h" 80 #include "llvm/Support/raw_ostream.h" 81 #include "llvm/Transforms/Utils/Local.h" 82 #include "llvm/Transforms/Vectorize.h" 83 #include <algorithm> 84 #include <cassert> 85 #include <cstdlib> 86 #include <tuple> 87 #include <utility> 88 89 using namespace llvm; 90 91 #define DEBUG_TYPE "load-store-vectorizer" 92 93 STATISTIC(NumVectorInstructions, "Number of vector accesses generated"); 94 STATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized"); 95 96 // FIXME: Assuming stack alignment of 4 is always good enough 97 static const unsigned StackAdjustedAlignment = 4; 98 99 namespace { 100 101 /// ChainID is an arbitrary token that is allowed to be different only for the 102 /// accesses that are guaranteed to be considered non-consecutive by 103 /// Vectorizer::isConsecutiveAccess. It's used for grouping instructions 104 /// together and reducing the number of instructions the main search operates on 105 /// at a time, i.e. this is to reduce compile time and nothing else as the main 106 /// search has O(n^2) time complexity. The underlying type of ChainID should not 107 /// be relied upon. 108 using ChainID = const Value *; 109 using InstrList = SmallVector<Instruction *, 8>; 110 using InstrListMap = MapVector<ChainID, InstrList>; 111 112 class Vectorizer { 113 Function &F; 114 AliasAnalysis &AA; 115 AssumptionCache &AC; 116 DominatorTree &DT; 117 ScalarEvolution &SE; 118 TargetTransformInfo &TTI; 119 const DataLayout &DL; 120 IRBuilder<> Builder; 121 122 public: 123 Vectorizer(Function &F, AliasAnalysis &AA, AssumptionCache &AC, 124 DominatorTree &DT, ScalarEvolution &SE, TargetTransformInfo &TTI) 125 : F(F), AA(AA), AC(AC), DT(DT), SE(SE), TTI(TTI), 126 DL(F.getParent()->getDataLayout()), Builder(SE.getContext()) {} 127 128 bool run(); 129 130 private: 131 unsigned getPointerAddressSpace(Value *I); 132 133 static const unsigned MaxDepth = 3; 134 135 bool isConsecutiveAccess(Value *A, Value *B); 136 bool areConsecutivePointers(Value *PtrA, Value *PtrB, APInt PtrDelta, 137 unsigned Depth = 0) const; 138 bool lookThroughComplexAddresses(Value *PtrA, Value *PtrB, APInt PtrDelta, 139 unsigned Depth) const; 140 bool lookThroughSelects(Value *PtrA, Value *PtrB, const APInt &PtrDelta, 141 unsigned Depth) const; 142 143 /// After vectorization, reorder the instructions that I depends on 144 /// (the instructions defining its operands), to ensure they dominate I. 145 void reorder(Instruction *I); 146 147 /// Returns the first and the last instructions in Chain. 148 std::pair<BasicBlock::iterator, BasicBlock::iterator> 149 getBoundaryInstrs(ArrayRef<Instruction *> Chain); 150 151 /// Erases the original instructions after vectorizing. 152 void eraseInstructions(ArrayRef<Instruction *> Chain); 153 154 /// "Legalize" the vector type that would be produced by combining \p 155 /// ElementSizeBits elements in \p Chain. Break into two pieces such that the 156 /// total size of each piece is 1, 2 or a multiple of 4 bytes. \p Chain is 157 /// expected to have more than 4 elements. 158 std::pair<ArrayRef<Instruction *>, ArrayRef<Instruction *>> 159 splitOddVectorElts(ArrayRef<Instruction *> Chain, unsigned ElementSizeBits); 160 161 /// Finds the largest prefix of Chain that's vectorizable, checking for 162 /// intervening instructions which may affect the memory accessed by the 163 /// instructions within Chain. 164 /// 165 /// The elements of \p Chain must be all loads or all stores and must be in 166 /// address order. 167 ArrayRef<Instruction *> getVectorizablePrefix(ArrayRef<Instruction *> Chain); 168 169 /// Collects load and store instructions to vectorize. 170 std::pair<InstrListMap, InstrListMap> collectInstructions(BasicBlock *BB); 171 172 /// Processes the collected instructions, the \p Map. The values of \p Map 173 /// should be all loads or all stores. 174 bool vectorizeChains(InstrListMap &Map); 175 176 /// Finds the load/stores to consecutive memory addresses and vectorizes them. 177 bool vectorizeInstructions(ArrayRef<Instruction *> Instrs); 178 179 /// Vectorizes the load instructions in Chain. 180 bool 181 vectorizeLoadChain(ArrayRef<Instruction *> Chain, 182 SmallPtrSet<Instruction *, 16> *InstructionsProcessed); 183 184 /// Vectorizes the store instructions in Chain. 185 bool 186 vectorizeStoreChain(ArrayRef<Instruction *> Chain, 187 SmallPtrSet<Instruction *, 16> *InstructionsProcessed); 188 189 /// Check if this load/store access is misaligned accesses. 190 bool accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace, 191 Align Alignment); 192 }; 193 194 class LoadStoreVectorizerLegacyPass : public FunctionPass { 195 public: 196 static char ID; 197 198 LoadStoreVectorizerLegacyPass() : FunctionPass(ID) { 199 initializeLoadStoreVectorizerLegacyPassPass(*PassRegistry::getPassRegistry()); 200 } 201 202 bool runOnFunction(Function &F) override; 203 204 StringRef getPassName() const override { 205 return "GPU Load and Store Vectorizer"; 206 } 207 208 void getAnalysisUsage(AnalysisUsage &AU) const override { 209 AU.addRequired<AAResultsWrapperPass>(); 210 AU.addRequired<AssumptionCacheTracker>(); 211 AU.addRequired<ScalarEvolutionWrapperPass>(); 212 AU.addRequired<DominatorTreeWrapperPass>(); 213 AU.addRequired<TargetTransformInfoWrapperPass>(); 214 AU.setPreservesCFG(); 215 } 216 }; 217 218 } // end anonymous namespace 219 220 char LoadStoreVectorizerLegacyPass::ID = 0; 221 222 INITIALIZE_PASS_BEGIN(LoadStoreVectorizerLegacyPass, DEBUG_TYPE, 223 "Vectorize load and Store instructions", false, false) 224 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass) 225 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker); 226 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 227 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 228 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) 229 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 230 INITIALIZE_PASS_END(LoadStoreVectorizerLegacyPass, DEBUG_TYPE, 231 "Vectorize load and store instructions", false, false) 232 233 Pass *llvm::createLoadStoreVectorizerPass() { 234 return new LoadStoreVectorizerLegacyPass(); 235 } 236 237 bool LoadStoreVectorizerLegacyPass::runOnFunction(Function &F) { 238 // Don't vectorize when the attribute NoImplicitFloat is used. 239 if (skipFunction(F) || F.hasFnAttribute(Attribute::NoImplicitFloat)) 240 return false; 241 242 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); 243 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 244 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 245 TargetTransformInfo &TTI = 246 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 247 248 AssumptionCache &AC = 249 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 250 251 Vectorizer V(F, AA, AC, DT, SE, TTI); 252 return V.run(); 253 } 254 255 PreservedAnalyses LoadStoreVectorizerPass::run(Function &F, FunctionAnalysisManager &AM) { 256 // Don't vectorize when the attribute NoImplicitFloat is used. 257 if (F.hasFnAttribute(Attribute::NoImplicitFloat)) 258 return PreservedAnalyses::all(); 259 260 AliasAnalysis &AA = AM.getResult<AAManager>(F); 261 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F); 262 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 263 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F); 264 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F); 265 266 Vectorizer V(F, AA, AC, DT, SE, TTI); 267 bool Changed = V.run(); 268 PreservedAnalyses PA; 269 PA.preserveSet<CFGAnalyses>(); 270 return Changed ? PA : PreservedAnalyses::all(); 271 } 272 273 // The real propagateMetadata expects a SmallVector<Value*>, but we deal in 274 // vectors of Instructions. 275 static void propagateMetadata(Instruction *I, ArrayRef<Instruction *> IL) { 276 SmallVector<Value *, 8> VL(IL.begin(), IL.end()); 277 propagateMetadata(I, VL); 278 } 279 280 // Vectorizer Implementation 281 bool Vectorizer::run() { 282 bool Changed = false; 283 284 // Scan the blocks in the function in post order. 285 for (BasicBlock *BB : post_order(&F)) { 286 InstrListMap LoadRefs, StoreRefs; 287 std::tie(LoadRefs, StoreRefs) = collectInstructions(BB); 288 Changed |= vectorizeChains(LoadRefs); 289 Changed |= vectorizeChains(StoreRefs); 290 } 291 292 return Changed; 293 } 294 295 unsigned Vectorizer::getPointerAddressSpace(Value *I) { 296 if (LoadInst *L = dyn_cast<LoadInst>(I)) 297 return L->getPointerAddressSpace(); 298 if (StoreInst *S = dyn_cast<StoreInst>(I)) 299 return S->getPointerAddressSpace(); 300 return -1; 301 } 302 303 // FIXME: Merge with llvm::isConsecutiveAccess 304 bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) { 305 Value *PtrA = getLoadStorePointerOperand(A); 306 Value *PtrB = getLoadStorePointerOperand(B); 307 unsigned ASA = getPointerAddressSpace(A); 308 unsigned ASB = getPointerAddressSpace(B); 309 310 // Check that the address spaces match and that the pointers are valid. 311 if (!PtrA || !PtrB || (ASA != ASB)) 312 return false; 313 314 // Make sure that A and B are different pointers of the same size type. 315 Type *PtrATy = getLoadStoreType(A); 316 Type *PtrBTy = getLoadStoreType(B); 317 if (PtrA == PtrB || 318 PtrATy->isVectorTy() != PtrBTy->isVectorTy() || 319 DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) || 320 DL.getTypeStoreSize(PtrATy->getScalarType()) != 321 DL.getTypeStoreSize(PtrBTy->getScalarType())) 322 return false; 323 324 unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA); 325 APInt Size(PtrBitWidth, DL.getTypeStoreSize(PtrATy)); 326 327 return areConsecutivePointers(PtrA, PtrB, Size); 328 } 329 330 bool Vectorizer::areConsecutivePointers(Value *PtrA, Value *PtrB, 331 APInt PtrDelta, unsigned Depth) const { 332 unsigned PtrBitWidth = DL.getPointerTypeSizeInBits(PtrA->getType()); 333 APInt OffsetA(PtrBitWidth, 0); 334 APInt OffsetB(PtrBitWidth, 0); 335 PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA); 336 PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB); 337 338 unsigned NewPtrBitWidth = DL.getTypeStoreSizeInBits(PtrA->getType()); 339 340 if (NewPtrBitWidth != DL.getTypeStoreSizeInBits(PtrB->getType())) 341 return false; 342 343 // In case if we have to shrink the pointer 344 // stripAndAccumulateInBoundsConstantOffsets should properly handle a 345 // possible overflow and the value should fit into a smallest data type 346 // used in the cast/gep chain. 347 assert(OffsetA.getMinSignedBits() <= NewPtrBitWidth && 348 OffsetB.getMinSignedBits() <= NewPtrBitWidth); 349 350 OffsetA = OffsetA.sextOrTrunc(NewPtrBitWidth); 351 OffsetB = OffsetB.sextOrTrunc(NewPtrBitWidth); 352 PtrDelta = PtrDelta.sextOrTrunc(NewPtrBitWidth); 353 354 APInt OffsetDelta = OffsetB - OffsetA; 355 356 // Check if they are based on the same pointer. That makes the offsets 357 // sufficient. 358 if (PtrA == PtrB) 359 return OffsetDelta == PtrDelta; 360 361 // Compute the necessary base pointer delta to have the necessary final delta 362 // equal to the pointer delta requested. 363 APInt BaseDelta = PtrDelta - OffsetDelta; 364 365 // Compute the distance with SCEV between the base pointers. 366 const SCEV *PtrSCEVA = SE.getSCEV(PtrA); 367 const SCEV *PtrSCEVB = SE.getSCEV(PtrB); 368 const SCEV *C = SE.getConstant(BaseDelta); 369 const SCEV *X = SE.getAddExpr(PtrSCEVA, C); 370 if (X == PtrSCEVB) 371 return true; 372 373 // The above check will not catch the cases where one of the pointers is 374 // factorized but the other one is not, such as (C + (S * (A + B))) vs 375 // (AS + BS). Get the minus scev. That will allow re-combining the expresions 376 // and getting the simplified difference. 377 const SCEV *Dist = SE.getMinusSCEV(PtrSCEVB, PtrSCEVA); 378 if (C == Dist) 379 return true; 380 381 // Sometimes even this doesn't work, because SCEV can't always see through 382 // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking 383 // things the hard way. 384 return lookThroughComplexAddresses(PtrA, PtrB, BaseDelta, Depth); 385 } 386 387 static bool checkNoWrapFlags(Instruction *I, bool Signed) { 388 BinaryOperator *BinOpI = cast<BinaryOperator>(I); 389 return (Signed && BinOpI->hasNoSignedWrap()) || 390 (!Signed && BinOpI->hasNoUnsignedWrap()); 391 } 392 393 static bool checkIfSafeAddSequence(const APInt &IdxDiff, Instruction *AddOpA, 394 unsigned MatchingOpIdxA, Instruction *AddOpB, 395 unsigned MatchingOpIdxB, bool Signed) { 396 // If both OpA and OpB is an add with NSW/NUW and with 397 // one of the operands being the same, we can guarantee that the 398 // transformation is safe if we can prove that OpA won't overflow when 399 // IdxDiff added to the other operand of OpA. 400 // For example: 401 // %tmp7 = add nsw i32 %tmp2, %v0 402 // %tmp8 = sext i32 %tmp7 to i64 403 // ... 404 // %tmp11 = add nsw i32 %v0, 1 405 // %tmp12 = add nsw i32 %tmp2, %tmp11 406 // %tmp13 = sext i32 %tmp12 to i64 407 // 408 // Both %tmp7 and %tmp2 has the nsw flag and the first operand 409 // is %tmp2. It's guaranteed that adding 1 to %tmp7 won't overflow 410 // because %tmp11 adds 1 to %v0 and both %tmp11 and %tmp12 has the 411 // nsw flag. 412 assert(AddOpA->getOpcode() == Instruction::Add && 413 AddOpB->getOpcode() == Instruction::Add && 414 checkNoWrapFlags(AddOpA, Signed) && checkNoWrapFlags(AddOpB, Signed)); 415 if (AddOpA->getOperand(MatchingOpIdxA) == 416 AddOpB->getOperand(MatchingOpIdxB)) { 417 Value *OtherOperandA = AddOpA->getOperand(MatchingOpIdxA == 1 ? 0 : 1); 418 Value *OtherOperandB = AddOpB->getOperand(MatchingOpIdxB == 1 ? 0 : 1); 419 Instruction *OtherInstrA = dyn_cast<Instruction>(OtherOperandA); 420 Instruction *OtherInstrB = dyn_cast<Instruction>(OtherOperandB); 421 // Match `x +nsw/nuw y` and `x +nsw/nuw (y +nsw/nuw IdxDiff)`. 422 if (OtherInstrB && OtherInstrB->getOpcode() == Instruction::Add && 423 checkNoWrapFlags(OtherInstrB, Signed) && 424 isa<ConstantInt>(OtherInstrB->getOperand(1))) { 425 int64_t CstVal = 426 cast<ConstantInt>(OtherInstrB->getOperand(1))->getSExtValue(); 427 if (OtherInstrB->getOperand(0) == OtherOperandA && 428 IdxDiff.getSExtValue() == CstVal) 429 return true; 430 } 431 // Match `x +nsw/nuw (y +nsw/nuw -Idx)` and `x +nsw/nuw (y +nsw/nuw x)`. 432 if (OtherInstrA && OtherInstrA->getOpcode() == Instruction::Add && 433 checkNoWrapFlags(OtherInstrA, Signed) && 434 isa<ConstantInt>(OtherInstrA->getOperand(1))) { 435 int64_t CstVal = 436 cast<ConstantInt>(OtherInstrA->getOperand(1))->getSExtValue(); 437 if (OtherInstrA->getOperand(0) == OtherOperandB && 438 IdxDiff.getSExtValue() == -CstVal) 439 return true; 440 } 441 // Match `x +nsw/nuw (y +nsw/nuw c)` and 442 // `x +nsw/nuw (y +nsw/nuw (c + IdxDiff))`. 443 if (OtherInstrA && OtherInstrB && 444 OtherInstrA->getOpcode() == Instruction::Add && 445 OtherInstrB->getOpcode() == Instruction::Add && 446 checkNoWrapFlags(OtherInstrA, Signed) && 447 checkNoWrapFlags(OtherInstrB, Signed) && 448 isa<ConstantInt>(OtherInstrA->getOperand(1)) && 449 isa<ConstantInt>(OtherInstrB->getOperand(1))) { 450 int64_t CstValA = 451 cast<ConstantInt>(OtherInstrA->getOperand(1))->getSExtValue(); 452 int64_t CstValB = 453 cast<ConstantInt>(OtherInstrB->getOperand(1))->getSExtValue(); 454 if (OtherInstrA->getOperand(0) == OtherInstrB->getOperand(0) && 455 IdxDiff.getSExtValue() == (CstValB - CstValA)) 456 return true; 457 } 458 } 459 return false; 460 } 461 462 bool Vectorizer::lookThroughComplexAddresses(Value *PtrA, Value *PtrB, 463 APInt PtrDelta, 464 unsigned Depth) const { 465 auto *GEPA = dyn_cast<GetElementPtrInst>(PtrA); 466 auto *GEPB = dyn_cast<GetElementPtrInst>(PtrB); 467 if (!GEPA || !GEPB) 468 return lookThroughSelects(PtrA, PtrB, PtrDelta, Depth); 469 470 // Look through GEPs after checking they're the same except for the last 471 // index. 472 if (GEPA->getNumOperands() != GEPB->getNumOperands() || 473 GEPA->getPointerOperand() != GEPB->getPointerOperand()) 474 return false; 475 gep_type_iterator GTIA = gep_type_begin(GEPA); 476 gep_type_iterator GTIB = gep_type_begin(GEPB); 477 for (unsigned I = 0, E = GEPA->getNumIndices() - 1; I < E; ++I) { 478 if (GTIA.getOperand() != GTIB.getOperand()) 479 return false; 480 ++GTIA; 481 ++GTIB; 482 } 483 484 Instruction *OpA = dyn_cast<Instruction>(GTIA.getOperand()); 485 Instruction *OpB = dyn_cast<Instruction>(GTIB.getOperand()); 486 if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() || 487 OpA->getType() != OpB->getType()) 488 return false; 489 490 if (PtrDelta.isNegative()) { 491 if (PtrDelta.isMinSignedValue()) 492 return false; 493 PtrDelta.negate(); 494 std::swap(OpA, OpB); 495 } 496 uint64_t Stride = DL.getTypeAllocSize(GTIA.getIndexedType()); 497 if (PtrDelta.urem(Stride) != 0) 498 return false; 499 unsigned IdxBitWidth = OpA->getType()->getScalarSizeInBits(); 500 APInt IdxDiff = PtrDelta.udiv(Stride).zextOrSelf(IdxBitWidth); 501 502 // Only look through a ZExt/SExt. 503 if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA)) 504 return false; 505 506 bool Signed = isa<SExtInst>(OpA); 507 508 // At this point A could be a function parameter, i.e. not an instruction 509 Value *ValA = OpA->getOperand(0); 510 OpB = dyn_cast<Instruction>(OpB->getOperand(0)); 511 if (!OpB || ValA->getType() != OpB->getType()) 512 return false; 513 514 // Now we need to prove that adding IdxDiff to ValA won't overflow. 515 bool Safe = false; 516 517 // First attempt: if OpB is an add with NSW/NUW, and OpB is IdxDiff added to 518 // ValA, we're okay. 519 if (OpB->getOpcode() == Instruction::Add && 520 isa<ConstantInt>(OpB->getOperand(1)) && 521 IdxDiff.sle(cast<ConstantInt>(OpB->getOperand(1))->getSExtValue()) && 522 checkNoWrapFlags(OpB, Signed)) 523 Safe = true; 524 525 // Second attempt: check if we have eligible add NSW/NUW instruction 526 // sequences. 527 OpA = dyn_cast<Instruction>(ValA); 528 if (!Safe && OpA && OpA->getOpcode() == Instruction::Add && 529 OpB->getOpcode() == Instruction::Add && checkNoWrapFlags(OpA, Signed) && 530 checkNoWrapFlags(OpB, Signed)) { 531 // In the checks below a matching operand in OpA and OpB is 532 // an operand which is the same in those two instructions. 533 // Below we account for possible orders of the operands of 534 // these add instructions. 535 for (unsigned MatchingOpIdxA : {0, 1}) 536 for (unsigned MatchingOpIdxB : {0, 1}) 537 if (!Safe) 538 Safe = checkIfSafeAddSequence(IdxDiff, OpA, MatchingOpIdxA, OpB, 539 MatchingOpIdxB, Signed); 540 } 541 542 unsigned BitWidth = ValA->getType()->getScalarSizeInBits(); 543 544 // Third attempt: 545 // If all set bits of IdxDiff or any higher order bit other than the sign bit 546 // are known to be zero in ValA, we can add Diff to it while guaranteeing no 547 // overflow of any sort. 548 if (!Safe) { 549 KnownBits Known(BitWidth); 550 computeKnownBits(ValA, Known, DL, 0, &AC, OpB, &DT); 551 APInt BitsAllowedToBeSet = Known.Zero.zext(IdxDiff.getBitWidth()); 552 if (Signed) 553 BitsAllowedToBeSet.clearBit(BitWidth - 1); 554 if (BitsAllowedToBeSet.ult(IdxDiff)) 555 return false; 556 } 557 558 const SCEV *OffsetSCEVA = SE.getSCEV(ValA); 559 const SCEV *OffsetSCEVB = SE.getSCEV(OpB); 560 const SCEV *C = SE.getConstant(IdxDiff.trunc(BitWidth)); 561 const SCEV *X = SE.getAddExpr(OffsetSCEVA, C); 562 return X == OffsetSCEVB; 563 } 564 565 bool Vectorizer::lookThroughSelects(Value *PtrA, Value *PtrB, 566 const APInt &PtrDelta, 567 unsigned Depth) const { 568 if (Depth++ == MaxDepth) 569 return false; 570 571 if (auto *SelectA = dyn_cast<SelectInst>(PtrA)) { 572 if (auto *SelectB = dyn_cast<SelectInst>(PtrB)) { 573 return SelectA->getCondition() == SelectB->getCondition() && 574 areConsecutivePointers(SelectA->getTrueValue(), 575 SelectB->getTrueValue(), PtrDelta, Depth) && 576 areConsecutivePointers(SelectA->getFalseValue(), 577 SelectB->getFalseValue(), PtrDelta, Depth); 578 } 579 } 580 return false; 581 } 582 583 void Vectorizer::reorder(Instruction *I) { 584 SmallPtrSet<Instruction *, 16> InstructionsToMove; 585 SmallVector<Instruction *, 16> Worklist; 586 587 Worklist.push_back(I); 588 while (!Worklist.empty()) { 589 Instruction *IW = Worklist.pop_back_val(); 590 int NumOperands = IW->getNumOperands(); 591 for (int i = 0; i < NumOperands; i++) { 592 Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i)); 593 if (!IM || IM->getOpcode() == Instruction::PHI) 594 continue; 595 596 // If IM is in another BB, no need to move it, because this pass only 597 // vectorizes instructions within one BB. 598 if (IM->getParent() != I->getParent()) 599 continue; 600 601 if (!IM->comesBefore(I)) { 602 InstructionsToMove.insert(IM); 603 Worklist.push_back(IM); 604 } 605 } 606 } 607 608 // All instructions to move should follow I. Start from I, not from begin(). 609 for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E; 610 ++BBI) { 611 if (!InstructionsToMove.count(&*BBI)) 612 continue; 613 Instruction *IM = &*BBI; 614 --BBI; 615 IM->removeFromParent(); 616 IM->insertBefore(I); 617 } 618 } 619 620 std::pair<BasicBlock::iterator, BasicBlock::iterator> 621 Vectorizer::getBoundaryInstrs(ArrayRef<Instruction *> Chain) { 622 Instruction *C0 = Chain[0]; 623 BasicBlock::iterator FirstInstr = C0->getIterator(); 624 BasicBlock::iterator LastInstr = C0->getIterator(); 625 626 BasicBlock *BB = C0->getParent(); 627 unsigned NumFound = 0; 628 for (Instruction &I : *BB) { 629 if (!is_contained(Chain, &I)) 630 continue; 631 632 ++NumFound; 633 if (NumFound == 1) { 634 FirstInstr = I.getIterator(); 635 } 636 if (NumFound == Chain.size()) { 637 LastInstr = I.getIterator(); 638 break; 639 } 640 } 641 642 // Range is [first, last). 643 return std::make_pair(FirstInstr, ++LastInstr); 644 } 645 646 void Vectorizer::eraseInstructions(ArrayRef<Instruction *> Chain) { 647 SmallVector<Instruction *, 16> Instrs; 648 for (Instruction *I : Chain) { 649 Value *PtrOperand = getLoadStorePointerOperand(I); 650 assert(PtrOperand && "Instruction must have a pointer operand."); 651 Instrs.push_back(I); 652 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(PtrOperand)) 653 Instrs.push_back(GEP); 654 } 655 656 // Erase instructions. 657 for (Instruction *I : Instrs) 658 if (I->use_empty()) 659 I->eraseFromParent(); 660 } 661 662 std::pair<ArrayRef<Instruction *>, ArrayRef<Instruction *>> 663 Vectorizer::splitOddVectorElts(ArrayRef<Instruction *> Chain, 664 unsigned ElementSizeBits) { 665 unsigned ElementSizeBytes = ElementSizeBits / 8; 666 unsigned SizeBytes = ElementSizeBytes * Chain.size(); 667 unsigned NumLeft = (SizeBytes - (SizeBytes % 4)) / ElementSizeBytes; 668 if (NumLeft == Chain.size()) { 669 if ((NumLeft & 1) == 0) 670 NumLeft /= 2; // Split even in half 671 else 672 --NumLeft; // Split off last element 673 } else if (NumLeft == 0) 674 NumLeft = 1; 675 return std::make_pair(Chain.slice(0, NumLeft), Chain.slice(NumLeft)); 676 } 677 678 ArrayRef<Instruction *> 679 Vectorizer::getVectorizablePrefix(ArrayRef<Instruction *> Chain) { 680 // These are in BB order, unlike Chain, which is in address order. 681 SmallVector<Instruction *, 16> MemoryInstrs; 682 SmallVector<Instruction *, 16> ChainInstrs; 683 684 bool IsLoadChain = isa<LoadInst>(Chain[0]); 685 LLVM_DEBUG({ 686 for (Instruction *I : Chain) { 687 if (IsLoadChain) 688 assert(isa<LoadInst>(I) && 689 "All elements of Chain must be loads, or all must be stores."); 690 else 691 assert(isa<StoreInst>(I) && 692 "All elements of Chain must be loads, or all must be stores."); 693 } 694 }); 695 696 for (Instruction &I : make_range(getBoundaryInstrs(Chain))) { 697 if ((isa<LoadInst>(I) || isa<StoreInst>(I)) && is_contained(Chain, &I)) { 698 ChainInstrs.push_back(&I); 699 continue; 700 } 701 if (!isGuaranteedToTransferExecutionToSuccessor(&I)) { 702 LLVM_DEBUG(dbgs() << "LSV: Found instruction may not transfer execution: " 703 << I << '\n'); 704 break; 705 } 706 if (I.mayReadOrWriteMemory()) 707 MemoryInstrs.push_back(&I); 708 } 709 710 // Loop until we find an instruction in ChainInstrs that we can't vectorize. 711 unsigned ChainInstrIdx = 0; 712 Instruction *BarrierMemoryInstr = nullptr; 713 714 for (unsigned E = ChainInstrs.size(); ChainInstrIdx < E; ++ChainInstrIdx) { 715 Instruction *ChainInstr = ChainInstrs[ChainInstrIdx]; 716 717 // If a barrier memory instruction was found, chain instructions that follow 718 // will not be added to the valid prefix. 719 if (BarrierMemoryInstr && BarrierMemoryInstr->comesBefore(ChainInstr)) 720 break; 721 722 // Check (in BB order) if any instruction prevents ChainInstr from being 723 // vectorized. Find and store the first such "conflicting" instruction. 724 for (Instruction *MemInstr : MemoryInstrs) { 725 // If a barrier memory instruction was found, do not check past it. 726 if (BarrierMemoryInstr && BarrierMemoryInstr->comesBefore(MemInstr)) 727 break; 728 729 auto *MemLoad = dyn_cast<LoadInst>(MemInstr); 730 auto *ChainLoad = dyn_cast<LoadInst>(ChainInstr); 731 if (MemLoad && ChainLoad) 732 continue; 733 734 // We can ignore the alias if the we have a load store pair and the load 735 // is known to be invariant. The load cannot be clobbered by the store. 736 auto IsInvariantLoad = [](const LoadInst *LI) -> bool { 737 return LI->hasMetadata(LLVMContext::MD_invariant_load); 738 }; 739 740 if (IsLoadChain) { 741 // We can ignore the alias as long as the load comes before the store, 742 // because that means we won't be moving the load past the store to 743 // vectorize it (the vectorized load is inserted at the location of the 744 // first load in the chain). 745 if (ChainInstr->comesBefore(MemInstr) || 746 (ChainLoad && IsInvariantLoad(ChainLoad))) 747 continue; 748 } else { 749 // Same case, but in reverse. 750 if (MemInstr->comesBefore(ChainInstr) || 751 (MemLoad && IsInvariantLoad(MemLoad))) 752 continue; 753 } 754 755 ModRefInfo MR = 756 AA.getModRefInfo(MemInstr, MemoryLocation::get(ChainInstr)); 757 if (IsLoadChain ? isModSet(MR) : isModOrRefSet(MR)) { 758 LLVM_DEBUG({ 759 dbgs() << "LSV: Found alias:\n" 760 " Aliasing instruction:\n" 761 << " " << *MemInstr << '\n' 762 << " Aliased instruction and pointer:\n" 763 << " " << *ChainInstr << '\n' 764 << " " << *getLoadStorePointerOperand(ChainInstr) << '\n'; 765 }); 766 // Save this aliasing memory instruction as a barrier, but allow other 767 // instructions that precede the barrier to be vectorized with this one. 768 BarrierMemoryInstr = MemInstr; 769 break; 770 } 771 } 772 // Continue the search only for store chains, since vectorizing stores that 773 // precede an aliasing load is valid. Conversely, vectorizing loads is valid 774 // up to an aliasing store, but should not pull loads from further down in 775 // the basic block. 776 if (IsLoadChain && BarrierMemoryInstr) { 777 // The BarrierMemoryInstr is a store that precedes ChainInstr. 778 assert(BarrierMemoryInstr->comesBefore(ChainInstr)); 779 break; 780 } 781 } 782 783 // Find the largest prefix of Chain whose elements are all in 784 // ChainInstrs[0, ChainInstrIdx). This is the largest vectorizable prefix of 785 // Chain. (Recall that Chain is in address order, but ChainInstrs is in BB 786 // order.) 787 SmallPtrSet<Instruction *, 8> VectorizableChainInstrs( 788 ChainInstrs.begin(), ChainInstrs.begin() + ChainInstrIdx); 789 unsigned ChainIdx = 0; 790 for (unsigned ChainLen = Chain.size(); ChainIdx < ChainLen; ++ChainIdx) { 791 if (!VectorizableChainInstrs.count(Chain[ChainIdx])) 792 break; 793 } 794 return Chain.slice(0, ChainIdx); 795 } 796 797 static ChainID getChainID(const Value *Ptr) { 798 const Value *ObjPtr = getUnderlyingObject(Ptr); 799 if (const auto *Sel = dyn_cast<SelectInst>(ObjPtr)) { 800 // The select's themselves are distinct instructions even if they share the 801 // same condition and evaluate to consecutive pointers for true and false 802 // values of the condition. Therefore using the select's themselves for 803 // grouping instructions would put consecutive accesses into different lists 804 // and they won't be even checked for being consecutive, and won't be 805 // vectorized. 806 return Sel->getCondition(); 807 } 808 return ObjPtr; 809 } 810 811 std::pair<InstrListMap, InstrListMap> 812 Vectorizer::collectInstructions(BasicBlock *BB) { 813 InstrListMap LoadRefs; 814 InstrListMap StoreRefs; 815 816 for (Instruction &I : *BB) { 817 if (!I.mayReadOrWriteMemory()) 818 continue; 819 820 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 821 if (!LI->isSimple()) 822 continue; 823 824 // Skip if it's not legal. 825 if (!TTI.isLegalToVectorizeLoad(LI)) 826 continue; 827 828 Type *Ty = LI->getType(); 829 if (!VectorType::isValidElementType(Ty->getScalarType())) 830 continue; 831 832 // Skip weird non-byte sizes. They probably aren't worth the effort of 833 // handling correctly. 834 unsigned TySize = DL.getTypeSizeInBits(Ty); 835 if ((TySize % 8) != 0) 836 continue; 837 838 // Skip vectors of pointers. The vectorizeLoadChain/vectorizeStoreChain 839 // functions are currently using an integer type for the vectorized 840 // load/store, and does not support casting between the integer type and a 841 // vector of pointers (e.g. i64 to <2 x i16*>) 842 if (Ty->isVectorTy() && Ty->isPtrOrPtrVectorTy()) 843 continue; 844 845 Value *Ptr = LI->getPointerOperand(); 846 unsigned AS = Ptr->getType()->getPointerAddressSpace(); 847 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 848 849 unsigned VF = VecRegSize / TySize; 850 VectorType *VecTy = dyn_cast<VectorType>(Ty); 851 852 // No point in looking at these if they're too big to vectorize. 853 if (TySize > VecRegSize / 2 || 854 (VecTy && TTI.getLoadVectorFactor(VF, TySize, TySize / 8, VecTy) == 0)) 855 continue; 856 857 // Save the load locations. 858 const ChainID ID = getChainID(Ptr); 859 LoadRefs[ID].push_back(LI); 860 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) { 861 if (!SI->isSimple()) 862 continue; 863 864 // Skip if it's not legal. 865 if (!TTI.isLegalToVectorizeStore(SI)) 866 continue; 867 868 Type *Ty = SI->getValueOperand()->getType(); 869 if (!VectorType::isValidElementType(Ty->getScalarType())) 870 continue; 871 872 // Skip vectors of pointers. The vectorizeLoadChain/vectorizeStoreChain 873 // functions are currently using an integer type for the vectorized 874 // load/store, and does not support casting between the integer type and a 875 // vector of pointers (e.g. i64 to <2 x i16*>) 876 if (Ty->isVectorTy() && Ty->isPtrOrPtrVectorTy()) 877 continue; 878 879 // Skip weird non-byte sizes. They probably aren't worth the effort of 880 // handling correctly. 881 unsigned TySize = DL.getTypeSizeInBits(Ty); 882 if ((TySize % 8) != 0) 883 continue; 884 885 Value *Ptr = SI->getPointerOperand(); 886 unsigned AS = Ptr->getType()->getPointerAddressSpace(); 887 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 888 889 unsigned VF = VecRegSize / TySize; 890 VectorType *VecTy = dyn_cast<VectorType>(Ty); 891 892 // No point in looking at these if they're too big to vectorize. 893 if (TySize > VecRegSize / 2 || 894 (VecTy && TTI.getStoreVectorFactor(VF, TySize, TySize / 8, VecTy) == 0)) 895 continue; 896 897 // Save store location. 898 const ChainID ID = getChainID(Ptr); 899 StoreRefs[ID].push_back(SI); 900 } 901 } 902 903 return {LoadRefs, StoreRefs}; 904 } 905 906 bool Vectorizer::vectorizeChains(InstrListMap &Map) { 907 bool Changed = false; 908 909 for (const std::pair<ChainID, InstrList> &Chain : Map) { 910 unsigned Size = Chain.second.size(); 911 if (Size < 2) 912 continue; 913 914 LLVM_DEBUG(dbgs() << "LSV: Analyzing a chain of length " << Size << ".\n"); 915 916 // Process the stores in chunks of 64. 917 for (unsigned CI = 0, CE = Size; CI < CE; CI += 64) { 918 unsigned Len = std::min<unsigned>(CE - CI, 64); 919 ArrayRef<Instruction *> Chunk(&Chain.second[CI], Len); 920 Changed |= vectorizeInstructions(Chunk); 921 } 922 } 923 924 return Changed; 925 } 926 927 bool Vectorizer::vectorizeInstructions(ArrayRef<Instruction *> Instrs) { 928 LLVM_DEBUG(dbgs() << "LSV: Vectorizing " << Instrs.size() 929 << " instructions.\n"); 930 SmallVector<int, 16> Heads, Tails; 931 int ConsecutiveChain[64]; 932 933 // Do a quadratic search on all of the given loads/stores and find all of the 934 // pairs of loads/stores that follow each other. 935 for (int i = 0, e = Instrs.size(); i < e; ++i) { 936 ConsecutiveChain[i] = -1; 937 for (int j = e - 1; j >= 0; --j) { 938 if (i == j) 939 continue; 940 941 if (isConsecutiveAccess(Instrs[i], Instrs[j])) { 942 if (ConsecutiveChain[i] != -1) { 943 int CurDistance = std::abs(ConsecutiveChain[i] - i); 944 int NewDistance = std::abs(ConsecutiveChain[i] - j); 945 if (j < i || NewDistance > CurDistance) 946 continue; // Should not insert. 947 } 948 949 Tails.push_back(j); 950 Heads.push_back(i); 951 ConsecutiveChain[i] = j; 952 } 953 } 954 } 955 956 bool Changed = false; 957 SmallPtrSet<Instruction *, 16> InstructionsProcessed; 958 959 for (int Head : Heads) { 960 if (InstructionsProcessed.count(Instrs[Head])) 961 continue; 962 bool LongerChainExists = false; 963 for (unsigned TIt = 0; TIt < Tails.size(); TIt++) 964 if (Head == Tails[TIt] && 965 !InstructionsProcessed.count(Instrs[Heads[TIt]])) { 966 LongerChainExists = true; 967 break; 968 } 969 if (LongerChainExists) 970 continue; 971 972 // We found an instr that starts a chain. Now follow the chain and try to 973 // vectorize it. 974 SmallVector<Instruction *, 16> Operands; 975 int I = Head; 976 while (I != -1 && (is_contained(Tails, I) || is_contained(Heads, I))) { 977 if (InstructionsProcessed.count(Instrs[I])) 978 break; 979 980 Operands.push_back(Instrs[I]); 981 I = ConsecutiveChain[I]; 982 } 983 984 bool Vectorized = false; 985 if (isa<LoadInst>(*Operands.begin())) 986 Vectorized = vectorizeLoadChain(Operands, &InstructionsProcessed); 987 else 988 Vectorized = vectorizeStoreChain(Operands, &InstructionsProcessed); 989 990 Changed |= Vectorized; 991 } 992 993 return Changed; 994 } 995 996 bool Vectorizer::vectorizeStoreChain( 997 ArrayRef<Instruction *> Chain, 998 SmallPtrSet<Instruction *, 16> *InstructionsProcessed) { 999 StoreInst *S0 = cast<StoreInst>(Chain[0]); 1000 1001 // If the vector has an int element, default to int for the whole store. 1002 Type *StoreTy = nullptr; 1003 for (Instruction *I : Chain) { 1004 StoreTy = cast<StoreInst>(I)->getValueOperand()->getType(); 1005 if (StoreTy->isIntOrIntVectorTy()) 1006 break; 1007 1008 if (StoreTy->isPtrOrPtrVectorTy()) { 1009 StoreTy = Type::getIntNTy(F.getParent()->getContext(), 1010 DL.getTypeSizeInBits(StoreTy)); 1011 break; 1012 } 1013 } 1014 assert(StoreTy && "Failed to find store type"); 1015 1016 unsigned Sz = DL.getTypeSizeInBits(StoreTy); 1017 unsigned AS = S0->getPointerAddressSpace(); 1018 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 1019 unsigned VF = VecRegSize / Sz; 1020 unsigned ChainSize = Chain.size(); 1021 Align Alignment = S0->getAlign(); 1022 1023 if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) { 1024 InstructionsProcessed->insert(Chain.begin(), Chain.end()); 1025 return false; 1026 } 1027 1028 ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain); 1029 if (NewChain.empty()) { 1030 // No vectorization possible. 1031 InstructionsProcessed->insert(Chain.begin(), Chain.end()); 1032 return false; 1033 } 1034 if (NewChain.size() == 1) { 1035 // Failed after the first instruction. Discard it and try the smaller chain. 1036 InstructionsProcessed->insert(NewChain.front()); 1037 return false; 1038 } 1039 1040 // Update Chain to the valid vectorizable subchain. 1041 Chain = NewChain; 1042 ChainSize = Chain.size(); 1043 1044 // Check if it's legal to vectorize this chain. If not, split the chain and 1045 // try again. 1046 unsigned EltSzInBytes = Sz / 8; 1047 unsigned SzInBytes = EltSzInBytes * ChainSize; 1048 1049 FixedVectorType *VecTy; 1050 auto *VecStoreTy = dyn_cast<FixedVectorType>(StoreTy); 1051 if (VecStoreTy) 1052 VecTy = FixedVectorType::get(StoreTy->getScalarType(), 1053 Chain.size() * VecStoreTy->getNumElements()); 1054 else 1055 VecTy = FixedVectorType::get(StoreTy, Chain.size()); 1056 1057 // If it's more than the max vector size or the target has a better 1058 // vector factor, break it into two pieces. 1059 unsigned TargetVF = TTI.getStoreVectorFactor(VF, Sz, SzInBytes, VecTy); 1060 if (ChainSize > VF || (VF != TargetVF && TargetVF < ChainSize)) { 1061 LLVM_DEBUG(dbgs() << "LSV: Chain doesn't match with the vector factor." 1062 " Creating two separate arrays.\n"); 1063 bool Vectorized = false; 1064 Vectorized |= 1065 vectorizeStoreChain(Chain.slice(0, TargetVF), InstructionsProcessed); 1066 Vectorized |= 1067 vectorizeStoreChain(Chain.slice(TargetVF), InstructionsProcessed); 1068 return Vectorized; 1069 } 1070 1071 LLVM_DEBUG({ 1072 dbgs() << "LSV: Stores to vectorize:\n"; 1073 for (Instruction *I : Chain) 1074 dbgs() << " " << *I << "\n"; 1075 }); 1076 1077 // We won't try again to vectorize the elements of the chain, regardless of 1078 // whether we succeed below. 1079 InstructionsProcessed->insert(Chain.begin(), Chain.end()); 1080 1081 // If the store is going to be misaligned, don't vectorize it. 1082 if (accessIsMisaligned(SzInBytes, AS, Alignment)) { 1083 if (S0->getPointerAddressSpace() != DL.getAllocaAddrSpace()) { 1084 auto Chains = splitOddVectorElts(Chain, Sz); 1085 bool Vectorized = false; 1086 Vectorized |= vectorizeStoreChain(Chains.first, InstructionsProcessed); 1087 Vectorized |= vectorizeStoreChain(Chains.second, InstructionsProcessed); 1088 return Vectorized; 1089 } 1090 1091 Align NewAlign = getOrEnforceKnownAlignment(S0->getPointerOperand(), 1092 Align(StackAdjustedAlignment), 1093 DL, S0, nullptr, &DT); 1094 if (NewAlign >= Alignment) 1095 Alignment = NewAlign; 1096 else 1097 return false; 1098 } 1099 1100 if (!TTI.isLegalToVectorizeStoreChain(SzInBytes, Alignment, AS)) { 1101 auto Chains = splitOddVectorElts(Chain, Sz); 1102 bool Vectorized = false; 1103 Vectorized |= vectorizeStoreChain(Chains.first, InstructionsProcessed); 1104 Vectorized |= vectorizeStoreChain(Chains.second, InstructionsProcessed); 1105 return Vectorized; 1106 } 1107 1108 BasicBlock::iterator First, Last; 1109 std::tie(First, Last) = getBoundaryInstrs(Chain); 1110 Builder.SetInsertPoint(&*Last); 1111 1112 Value *Vec = PoisonValue::get(VecTy); 1113 1114 if (VecStoreTy) { 1115 unsigned VecWidth = VecStoreTy->getNumElements(); 1116 for (unsigned I = 0, E = Chain.size(); I != E; ++I) { 1117 StoreInst *Store = cast<StoreInst>(Chain[I]); 1118 for (unsigned J = 0, NE = VecStoreTy->getNumElements(); J != NE; ++J) { 1119 unsigned NewIdx = J + I * VecWidth; 1120 Value *Extract = Builder.CreateExtractElement(Store->getValueOperand(), 1121 Builder.getInt32(J)); 1122 if (Extract->getType() != StoreTy->getScalarType()) 1123 Extract = Builder.CreateBitCast(Extract, StoreTy->getScalarType()); 1124 1125 Value *Insert = 1126 Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(NewIdx)); 1127 Vec = Insert; 1128 } 1129 } 1130 } else { 1131 for (unsigned I = 0, E = Chain.size(); I != E; ++I) { 1132 StoreInst *Store = cast<StoreInst>(Chain[I]); 1133 Value *Extract = Store->getValueOperand(); 1134 if (Extract->getType() != StoreTy->getScalarType()) 1135 Extract = 1136 Builder.CreateBitOrPointerCast(Extract, StoreTy->getScalarType()); 1137 1138 Value *Insert = 1139 Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(I)); 1140 Vec = Insert; 1141 } 1142 } 1143 1144 StoreInst *SI = Builder.CreateAlignedStore( 1145 Vec, 1146 Builder.CreateBitCast(S0->getPointerOperand(), VecTy->getPointerTo(AS)), 1147 Alignment); 1148 propagateMetadata(SI, Chain); 1149 1150 eraseInstructions(Chain); 1151 ++NumVectorInstructions; 1152 NumScalarsVectorized += Chain.size(); 1153 return true; 1154 } 1155 1156 bool Vectorizer::vectorizeLoadChain( 1157 ArrayRef<Instruction *> Chain, 1158 SmallPtrSet<Instruction *, 16> *InstructionsProcessed) { 1159 LoadInst *L0 = cast<LoadInst>(Chain[0]); 1160 1161 // If the vector has an int element, default to int for the whole load. 1162 Type *LoadTy = nullptr; 1163 for (const auto &V : Chain) { 1164 LoadTy = cast<LoadInst>(V)->getType(); 1165 if (LoadTy->isIntOrIntVectorTy()) 1166 break; 1167 1168 if (LoadTy->isPtrOrPtrVectorTy()) { 1169 LoadTy = Type::getIntNTy(F.getParent()->getContext(), 1170 DL.getTypeSizeInBits(LoadTy)); 1171 break; 1172 } 1173 } 1174 assert(LoadTy && "Can't determine LoadInst type from chain"); 1175 1176 unsigned Sz = DL.getTypeSizeInBits(LoadTy); 1177 unsigned AS = L0->getPointerAddressSpace(); 1178 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 1179 unsigned VF = VecRegSize / Sz; 1180 unsigned ChainSize = Chain.size(); 1181 Align Alignment = L0->getAlign(); 1182 1183 if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) { 1184 InstructionsProcessed->insert(Chain.begin(), Chain.end()); 1185 return false; 1186 } 1187 1188 ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain); 1189 if (NewChain.empty()) { 1190 // No vectorization possible. 1191 InstructionsProcessed->insert(Chain.begin(), Chain.end()); 1192 return false; 1193 } 1194 if (NewChain.size() == 1) { 1195 // Failed after the first instruction. Discard it and try the smaller chain. 1196 InstructionsProcessed->insert(NewChain.front()); 1197 return false; 1198 } 1199 1200 // Update Chain to the valid vectorizable subchain. 1201 Chain = NewChain; 1202 ChainSize = Chain.size(); 1203 1204 // Check if it's legal to vectorize this chain. If not, split the chain and 1205 // try again. 1206 unsigned EltSzInBytes = Sz / 8; 1207 unsigned SzInBytes = EltSzInBytes * ChainSize; 1208 VectorType *VecTy; 1209 auto *VecLoadTy = dyn_cast<FixedVectorType>(LoadTy); 1210 if (VecLoadTy) 1211 VecTy = FixedVectorType::get(LoadTy->getScalarType(), 1212 Chain.size() * VecLoadTy->getNumElements()); 1213 else 1214 VecTy = FixedVectorType::get(LoadTy, Chain.size()); 1215 1216 // If it's more than the max vector size or the target has a better 1217 // vector factor, break it into two pieces. 1218 unsigned TargetVF = TTI.getLoadVectorFactor(VF, Sz, SzInBytes, VecTy); 1219 if (ChainSize > VF || (VF != TargetVF && TargetVF < ChainSize)) { 1220 LLVM_DEBUG(dbgs() << "LSV: Chain doesn't match with the vector factor." 1221 " Creating two separate arrays.\n"); 1222 bool Vectorized = false; 1223 Vectorized |= 1224 vectorizeLoadChain(Chain.slice(0, TargetVF), InstructionsProcessed); 1225 Vectorized |= 1226 vectorizeLoadChain(Chain.slice(TargetVF), InstructionsProcessed); 1227 return Vectorized; 1228 } 1229 1230 // We won't try again to vectorize the elements of the chain, regardless of 1231 // whether we succeed below. 1232 InstructionsProcessed->insert(Chain.begin(), Chain.end()); 1233 1234 // If the load is going to be misaligned, don't vectorize it. 1235 if (accessIsMisaligned(SzInBytes, AS, Alignment)) { 1236 if (L0->getPointerAddressSpace() != DL.getAllocaAddrSpace()) { 1237 auto Chains = splitOddVectorElts(Chain, Sz); 1238 bool Vectorized = false; 1239 Vectorized |= vectorizeLoadChain(Chains.first, InstructionsProcessed); 1240 Vectorized |= vectorizeLoadChain(Chains.second, InstructionsProcessed); 1241 return Vectorized; 1242 } 1243 1244 Align NewAlign = getOrEnforceKnownAlignment(L0->getPointerOperand(), 1245 Align(StackAdjustedAlignment), 1246 DL, L0, nullptr, &DT); 1247 if (NewAlign >= Alignment) 1248 Alignment = NewAlign; 1249 else 1250 return false; 1251 } 1252 1253 if (!TTI.isLegalToVectorizeLoadChain(SzInBytes, Alignment, AS)) { 1254 auto Chains = splitOddVectorElts(Chain, Sz); 1255 bool Vectorized = false; 1256 Vectorized |= vectorizeLoadChain(Chains.first, InstructionsProcessed); 1257 Vectorized |= vectorizeLoadChain(Chains.second, InstructionsProcessed); 1258 return Vectorized; 1259 } 1260 1261 LLVM_DEBUG({ 1262 dbgs() << "LSV: Loads to vectorize:\n"; 1263 for (Instruction *I : Chain) 1264 I->dump(); 1265 }); 1266 1267 // getVectorizablePrefix already computed getBoundaryInstrs. The value of 1268 // Last may have changed since then, but the value of First won't have. If it 1269 // matters, we could compute getBoundaryInstrs only once and reuse it here. 1270 BasicBlock::iterator First, Last; 1271 std::tie(First, Last) = getBoundaryInstrs(Chain); 1272 Builder.SetInsertPoint(&*First); 1273 1274 Value *Bitcast = 1275 Builder.CreateBitCast(L0->getPointerOperand(), VecTy->getPointerTo(AS)); 1276 LoadInst *LI = 1277 Builder.CreateAlignedLoad(VecTy, Bitcast, MaybeAlign(Alignment)); 1278 propagateMetadata(LI, Chain); 1279 1280 for (unsigned I = 0, E = Chain.size(); I != E; ++I) { 1281 Value *CV = Chain[I]; 1282 Value *V; 1283 if (VecLoadTy) { 1284 // Extract a subvector using shufflevector. 1285 unsigned VecWidth = VecLoadTy->getNumElements(); 1286 auto Mask = 1287 llvm::to_vector<8>(llvm::seq<int>(I * VecWidth, (I + 1) * VecWidth)); 1288 V = Builder.CreateShuffleVector(LI, Mask, CV->getName()); 1289 } else { 1290 V = Builder.CreateExtractElement(LI, Builder.getInt32(I), CV->getName()); 1291 } 1292 1293 if (V->getType() != CV->getType()) { 1294 V = Builder.CreateBitOrPointerCast(V, CV->getType()); 1295 } 1296 1297 // Replace the old instruction. 1298 CV->replaceAllUsesWith(V); 1299 } 1300 1301 // Bitcast might not be an Instruction, if the value being loaded is a 1302 // constant. In that case, no need to reorder anything. 1303 if (Instruction *BitcastInst = dyn_cast<Instruction>(Bitcast)) 1304 reorder(BitcastInst); 1305 1306 eraseInstructions(Chain); 1307 1308 ++NumVectorInstructions; 1309 NumScalarsVectorized += Chain.size(); 1310 return true; 1311 } 1312 1313 bool Vectorizer::accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace, 1314 Align Alignment) { 1315 if (Alignment.value() % SzInBytes == 0) 1316 return false; 1317 1318 bool Fast = false; 1319 bool Allows = TTI.allowsMisalignedMemoryAccesses(F.getParent()->getContext(), 1320 SzInBytes * 8, AddressSpace, 1321 Alignment, &Fast); 1322 LLVM_DEBUG(dbgs() << "LSV: Target said misaligned is allowed? " << Allows 1323 << " and fast? " << Fast << "\n";); 1324 return !Allows || !Fast; 1325 } 1326