1 //===----- LoadStoreVectorizer.cpp - GPU Load & Store Vectorizer ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 //===----------------------------------------------------------------------===//
12 #include "llvm/ADT/MapVector.h"
13 #include "llvm/ADT/PostOrderIterator.h"
14 #include "llvm/ADT/SetVector.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/ADT/Triple.h"
17 #include "llvm/Analysis/AliasAnalysis.h"
18 #include "llvm/Analysis/ScalarEvolution.h"
19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
20 #include "llvm/Analysis/TargetTransformInfo.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/Analysis/VectorUtils.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/IR/Type.h"
29 #include "llvm/IR/Value.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include "llvm/Transforms/Vectorize.h"
37 #define DEBUG_TYPE "load-store-vectorizer"
38 STATISTIC(NumVectorInstructions, "Number of vector accesses generated");
39 STATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized");
44 static const unsigned TargetBaseAlign = 4;
47 typedef SmallVector<Value *, 8> ValueList;
48 typedef MapVector<Value *, ValueList> ValueListMap;
54 TargetTransformInfo &TTI;
57 ValueListMap StoreRefs;
58 ValueListMap LoadRefs;
61 Vectorizer(Function &F, AliasAnalysis &AA, DominatorTree &DT,
62 ScalarEvolution &SE, TargetTransformInfo &TTI)
63 : F(F), AA(AA), DT(DT), SE(SE), TTI(TTI),
64 DL(F.getParent()->getDataLayout()), Builder(SE.getContext()) {}
69 Value *getPointerOperand(Value *I);
71 unsigned getPointerAddressSpace(Value *I);
73 unsigned getAlignment(LoadInst *LI) const {
74 unsigned Align = LI->getAlignment();
78 return DL.getABITypeAlignment(LI->getType());
81 unsigned getAlignment(StoreInst *SI) const {
82 unsigned Align = SI->getAlignment();
86 return DL.getABITypeAlignment(SI->getValueOperand()->getType());
89 bool isConsecutiveAccess(Value *A, Value *B);
91 /// After vectorization, reorder the instructions that I depends on
92 /// (the instructions defining its operands), to ensure they dominate I.
93 void reorder(Instruction *I);
95 /// Returns the first and the last instructions in Chain.
96 std::pair<BasicBlock::iterator, BasicBlock::iterator>
97 getBoundaryInstrs(ArrayRef<Value *> Chain);
99 /// Erases the original instructions after vectorizing.
100 void eraseInstructions(ArrayRef<Value *> Chain);
102 /// "Legalize" the vector type that would be produced by combining \p
103 /// ElementSizeBits elements in \p Chain. Break into two pieces such that the
104 /// total size of each piece is 1, 2 or a multiple of 4 bytes. \p Chain is
105 /// expected to have more than 4 elements.
106 std::pair<ArrayRef<Value *>, ArrayRef<Value *>>
107 splitOddVectorElts(ArrayRef<Value *> Chain, unsigned ElementSizeBits);
109 /// Checks for instructions which may affect the memory accessed
110 /// in the chain between \p From and \p To. Returns Index, where
111 /// \p Chain[0, Index) is the largest vectorizable chain prefix.
112 /// The elements of \p Chain should be all loads or all stores.
113 unsigned getVectorizablePrefixEndIdx(ArrayRef<Value *> Chain,
114 BasicBlock::iterator From,
115 BasicBlock::iterator To);
117 /// Collects load and store instructions to vectorize.
118 void collectInstructions(BasicBlock *BB);
120 /// Processes the collected instructions, the \p Map. The elements of \p Map
121 /// should be all loads or all stores.
122 bool vectorizeChains(ValueListMap &Map);
124 /// Finds the load/stores to consecutive memory addresses and vectorizes them.
125 bool vectorizeInstructions(ArrayRef<Value *> Instrs);
127 /// Vectorizes the load instructions in Chain.
128 bool vectorizeLoadChain(ArrayRef<Value *> Chain,
129 SmallPtrSet<Value *, 16> *InstructionsProcessed);
131 /// Vectorizes the store instructions in Chain.
132 bool vectorizeStoreChain(ArrayRef<Value *> Chain,
133 SmallPtrSet<Value *, 16> *InstructionsProcessed);
135 /// Check if this load/store access is misaligned accesses
136 bool accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
140 class LoadStoreVectorizer : public FunctionPass {
144 LoadStoreVectorizer() : FunctionPass(ID) {
145 initializeLoadStoreVectorizerPass(*PassRegistry::getPassRegistry());
148 bool runOnFunction(Function &F) override;
150 const char *getPassName() const override {
151 return "GPU Load and Store Vectorizer";
154 void getAnalysisUsage(AnalysisUsage &AU) const override {
155 AU.addRequired<AAResultsWrapperPass>();
156 AU.addRequired<ScalarEvolutionWrapperPass>();
157 AU.addRequired<DominatorTreeWrapperPass>();
158 AU.addRequired<TargetTransformInfoWrapperPass>();
159 AU.setPreservesCFG();
164 INITIALIZE_PASS_BEGIN(LoadStoreVectorizer, DEBUG_TYPE,
165 "Vectorize load and Store instructions", false, false)
166 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
167 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
168 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
169 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
170 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
171 INITIALIZE_PASS_END(LoadStoreVectorizer, DEBUG_TYPE,
172 "Vectorize load and store instructions", false, false)
174 char LoadStoreVectorizer::ID = 0;
176 Pass *llvm::createLoadStoreVectorizerPass() {
177 return new LoadStoreVectorizer();
180 bool LoadStoreVectorizer::runOnFunction(Function &F) {
181 // Don't vectorize when the attribute NoImplicitFloat is used.
182 if (skipFunction(F) || F.hasFnAttribute(Attribute::NoImplicitFloat))
185 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
186 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
187 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
188 TargetTransformInfo &TTI =
189 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
191 Vectorizer V(F, AA, DT, SE, TTI);
195 // Vectorizer Implementation
196 bool Vectorizer::run() {
197 bool Changed = false;
199 // Scan the blocks in the function in post order.
200 for (BasicBlock *BB : post_order(&F)) {
201 collectInstructions(BB);
202 Changed |= vectorizeChains(LoadRefs);
203 Changed |= vectorizeChains(StoreRefs);
209 Value *Vectorizer::getPointerOperand(Value *I) {
210 if (LoadInst *LI = dyn_cast<LoadInst>(I))
211 return LI->getPointerOperand();
212 if (StoreInst *SI = dyn_cast<StoreInst>(I))
213 return SI->getPointerOperand();
217 unsigned Vectorizer::getPointerAddressSpace(Value *I) {
218 if (LoadInst *L = dyn_cast<LoadInst>(I))
219 return L->getPointerAddressSpace();
220 if (StoreInst *S = dyn_cast<StoreInst>(I))
221 return S->getPointerAddressSpace();
225 // FIXME: Merge with llvm::isConsecutiveAccess
226 bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) {
227 Value *PtrA = getPointerOperand(A);
228 Value *PtrB = getPointerOperand(B);
229 unsigned ASA = getPointerAddressSpace(A);
230 unsigned ASB = getPointerAddressSpace(B);
232 // Check that the address spaces match and that the pointers are valid.
233 if (!PtrA || !PtrB || (ASA != ASB))
236 // Make sure that A and B are different pointers of the same size type.
237 unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
238 Type *PtrATy = PtrA->getType()->getPointerElementType();
239 Type *PtrBTy = PtrB->getType()->getPointerElementType();
241 DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) ||
242 DL.getTypeStoreSize(PtrATy->getScalarType()) !=
243 DL.getTypeStoreSize(PtrBTy->getScalarType()))
246 APInt Size(PtrBitWidth, DL.getTypeStoreSize(PtrATy));
248 APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0);
249 PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
250 PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
252 APInt OffsetDelta = OffsetB - OffsetA;
254 // Check if they are based on the same pointer. That makes the offsets
257 return OffsetDelta == Size;
259 // Compute the necessary base pointer delta to have the necessary final delta
260 // equal to the size.
261 APInt BaseDelta = Size - OffsetDelta;
263 // Compute the distance with SCEV between the base pointers.
264 const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
265 const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
266 const SCEV *C = SE.getConstant(BaseDelta);
267 const SCEV *X = SE.getAddExpr(PtrSCEVA, C);
271 // Sometimes even this doesn't work, because SCEV can't always see through
272 // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking
273 // things the hard way.
275 // Look through GEPs after checking they're the same except for the last
277 GetElementPtrInst *GEPA = dyn_cast<GetElementPtrInst>(getPointerOperand(A));
278 GetElementPtrInst *GEPB = dyn_cast<GetElementPtrInst>(getPointerOperand(B));
279 if (!GEPA || !GEPB || GEPA->getNumOperands() != GEPB->getNumOperands())
281 unsigned FinalIndex = GEPA->getNumOperands() - 1;
282 for (unsigned i = 0; i < FinalIndex; i++)
283 if (GEPA->getOperand(i) != GEPB->getOperand(i))
286 Instruction *OpA = dyn_cast<Instruction>(GEPA->getOperand(FinalIndex));
287 Instruction *OpB = dyn_cast<Instruction>(GEPB->getOperand(FinalIndex));
288 if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() ||
289 OpA->getType() != OpB->getType())
292 // Only look through a ZExt/SExt.
293 if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA))
296 bool Signed = isa<SExtInst>(OpA);
298 OpA = dyn_cast<Instruction>(OpA->getOperand(0));
299 OpB = dyn_cast<Instruction>(OpB->getOperand(0));
300 if (!OpA || !OpB || OpA->getType() != OpB->getType())
303 // Now we need to prove that adding 1 to OpA won't overflow.
305 // First attempt: if OpB is an add with NSW/NUW, and OpB is 1 added to OpA,
307 if (OpB->getOpcode() == Instruction::Add &&
308 isa<ConstantInt>(OpB->getOperand(1)) &&
309 cast<ConstantInt>(OpB->getOperand(1))->getSExtValue() > 0) {
311 Safe = cast<BinaryOperator>(OpB)->hasNoSignedWrap();
313 Safe = cast<BinaryOperator>(OpB)->hasNoUnsignedWrap();
316 unsigned BitWidth = OpA->getType()->getScalarSizeInBits();
319 // If any bits are known to be zero other than the sign bit in OpA, we can
320 // add 1 to it while guaranteeing no overflow of any sort.
322 APInt KnownZero(BitWidth, 0);
323 APInt KnownOne(BitWidth, 0);
324 computeKnownBits(OpA, KnownZero, KnownOne, DL, 0, nullptr, OpA, &DT);
325 KnownZero &= ~APInt::getHighBitsSet(BitWidth, 1);
333 const SCEV *OffsetSCEVA = SE.getSCEV(OpA);
334 const SCEV *OffsetSCEVB = SE.getSCEV(OpB);
335 const SCEV *One = SE.getConstant(APInt(BitWidth, 1));
336 const SCEV *X2 = SE.getAddExpr(OffsetSCEVA, One);
337 return X2 == OffsetSCEVB;
340 void Vectorizer::reorder(Instruction *I) {
341 SmallPtrSet<Instruction *, 16> InstructionsToMove;
342 SmallVector<Instruction *, 16> Worklist;
344 Worklist.push_back(I);
345 while (!Worklist.empty()) {
346 Instruction *IW = Worklist.pop_back_val();
347 int NumOperands = IW->getNumOperands();
348 for (int i = 0; i < NumOperands; i++) {
349 Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i));
350 if (!IM || IM->getOpcode() == Instruction::PHI)
353 if (!DT.dominates(IM, I)) {
354 InstructionsToMove.insert(IM);
355 Worklist.push_back(IM);
356 assert(IM->getParent() == IW->getParent() &&
357 "Instructions to move should be in the same basic block");
362 // All instructions to move should follow I. Start from I, not from begin().
363 for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;
365 if (!is_contained(InstructionsToMove, &*BBI))
367 Instruction *IM = &*BBI;
369 IM->removeFromParent();
374 std::pair<BasicBlock::iterator, BasicBlock::iterator>
375 Vectorizer::getBoundaryInstrs(ArrayRef<Value *> Chain) {
376 Instruction *C0 = cast<Instruction>(Chain[0]);
377 BasicBlock::iterator FirstInstr = C0->getIterator();
378 BasicBlock::iterator LastInstr = C0->getIterator();
380 BasicBlock *BB = C0->getParent();
381 unsigned NumFound = 0;
382 for (Instruction &I : *BB) {
383 if (!is_contained(Chain, &I))
388 FirstInstr = I.getIterator();
390 if (NumFound == Chain.size()) {
391 LastInstr = I.getIterator();
396 // Range is [first, last).
397 return std::make_pair(FirstInstr, ++LastInstr);
400 void Vectorizer::eraseInstructions(ArrayRef<Value *> Chain) {
401 SmallVector<Instruction *, 16> Instrs;
402 for (Value *V : Chain) {
403 Value *PtrOperand = getPointerOperand(V);
404 assert(PtrOperand && "Instruction must have a pointer operand.");
405 Instrs.push_back(cast<Instruction>(V));
406 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(PtrOperand))
407 Instrs.push_back(GEP);
410 // Erase instructions.
411 for (Value *V : Instrs) {
412 Instruction *Instr = cast<Instruction>(V);
413 if (Instr->use_empty())
414 Instr->eraseFromParent();
418 std::pair<ArrayRef<Value *>, ArrayRef<Value *>>
419 Vectorizer::splitOddVectorElts(ArrayRef<Value *> Chain,
420 unsigned ElementSizeBits) {
421 unsigned ElemSizeInBytes = ElementSizeBits / 8;
422 unsigned SizeInBytes = ElemSizeInBytes * Chain.size();
423 unsigned NumRight = (SizeInBytes % 4) / ElemSizeInBytes;
424 unsigned NumLeft = Chain.size() - NumRight;
425 return std::make_pair(Chain.slice(0, NumLeft), Chain.slice(NumLeft));
428 unsigned Vectorizer::getVectorizablePrefixEndIdx(ArrayRef<Value *> Chain,
429 BasicBlock::iterator From,
430 BasicBlock::iterator To) {
431 SmallVector<std::pair<Value *, unsigned>, 16> MemoryInstrs;
432 SmallVector<std::pair<Value *, unsigned>, 16> ChainInstrs;
434 unsigned InstrIdx = 0;
435 for (auto I = From; I != To; ++I, ++InstrIdx) {
436 if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
437 if (!is_contained(Chain, &*I))
438 MemoryInstrs.push_back({&*I, InstrIdx});
440 ChainInstrs.push_back({&*I, InstrIdx});
441 } else if (I->mayHaveSideEffects()) {
442 DEBUG(dbgs() << "LSV: Found side-effecting operation: " << *I << '\n');
447 assert(Chain.size() == ChainInstrs.size() &&
448 "All instructions in the Chain must exist in [From, To).");
450 unsigned ChainIdx = 0;
451 for (auto EntryChain : ChainInstrs) {
452 Value *ChainInstrValue = EntryChain.first;
453 unsigned ChainInstrIdx = EntryChain.second;
454 for (auto EntryMem : MemoryInstrs) {
455 Value *MemInstrValue = EntryMem.first;
456 unsigned MemInstrIdx = EntryMem.second;
457 if (isa<LoadInst>(MemInstrValue) && isa<LoadInst>(ChainInstrValue))
460 // We can ignore the alias as long as the load comes before the store,
461 // because that means we won't be moving the load past the store to
462 // vectorize it (the vectorized load is inserted at the location of the
463 // first load in the chain).
464 if (isa<StoreInst>(MemInstrValue) && isa<LoadInst>(ChainInstrValue) &&
465 ChainInstrIdx < MemInstrIdx)
468 // Same case, but in reverse.
469 if (isa<LoadInst>(MemInstrValue) && isa<StoreInst>(ChainInstrValue) &&
470 ChainInstrIdx > MemInstrIdx)
473 Instruction *M0 = cast<Instruction>(MemInstrValue);
474 Instruction *M1 = cast<Instruction>(ChainInstrValue);
476 if (!AA.isNoAlias(MemoryLocation::get(M0), MemoryLocation::get(M1))) {
478 Value *Ptr0 = getPointerOperand(M0);
479 Value *Ptr1 = getPointerOperand(M1);
481 dbgs() << "LSV: Found alias.\n"
482 " Aliasing instruction and pointer:\n"
483 << *MemInstrValue << " aliases " << *Ptr0 << '\n'
484 << " Aliased instruction and pointer:\n"
485 << *ChainInstrValue << " aliases " << *Ptr1 << '\n';
496 void Vectorizer::collectInstructions(BasicBlock *BB) {
500 for (Instruction &I : *BB) {
501 if (!I.mayReadOrWriteMemory())
504 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
508 Type *Ty = LI->getType();
509 if (!VectorType::isValidElementType(Ty->getScalarType()))
512 // Skip weird non-byte sizes. They probably aren't worth the effort of
513 // handling correctly.
514 unsigned TySize = DL.getTypeSizeInBits(Ty);
518 Value *Ptr = LI->getPointerOperand();
519 unsigned AS = Ptr->getType()->getPointerAddressSpace();
520 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
522 // No point in looking at these if they're too big to vectorize.
523 if (TySize > VecRegSize / 2)
526 // Make sure all the users of a vector are constant-index extracts.
527 if (isa<VectorType>(Ty) && !all_of(LI->users(), [LI](const User *U) {
528 const Instruction *UI = cast<Instruction>(U);
529 return isa<ExtractElementInst>(UI) &&
530 isa<ConstantInt>(UI->getOperand(1));
534 // TODO: Target hook to filter types.
536 // Save the load locations.
537 Value *ObjPtr = GetUnderlyingObject(Ptr, DL);
538 LoadRefs[ObjPtr].push_back(LI);
540 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
544 Type *Ty = SI->getValueOperand()->getType();
545 if (!VectorType::isValidElementType(Ty->getScalarType()))
548 // Skip weird non-byte sizes. They probably aren't worth the effort of
549 // handling correctly.
550 unsigned TySize = DL.getTypeSizeInBits(Ty);
554 Value *Ptr = SI->getPointerOperand();
555 unsigned AS = Ptr->getType()->getPointerAddressSpace();
556 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
557 if (TySize > VecRegSize / 2)
560 if (isa<VectorType>(Ty) && !all_of(SI->users(), [SI](const User *U) {
561 const Instruction *UI = cast<Instruction>(U);
562 return isa<ExtractElementInst>(UI) &&
563 isa<ConstantInt>(UI->getOperand(1));
567 // Save store location.
568 Value *ObjPtr = GetUnderlyingObject(Ptr, DL);
569 StoreRefs[ObjPtr].push_back(SI);
574 bool Vectorizer::vectorizeChains(ValueListMap &Map) {
575 bool Changed = false;
577 for (const std::pair<Value *, ValueList> &Chain : Map) {
578 unsigned Size = Chain.second.size();
582 DEBUG(dbgs() << "LSV: Analyzing a chain of length " << Size << ".\n");
584 // Process the stores in chunks of 64.
585 for (unsigned CI = 0, CE = Size; CI < CE; CI += 64) {
586 unsigned Len = std::min<unsigned>(CE - CI, 64);
587 ArrayRef<Value *> Chunk(&Chain.second[CI], Len);
588 Changed |= vectorizeInstructions(Chunk);
595 bool Vectorizer::vectorizeInstructions(ArrayRef<Value *> Instrs) {
596 DEBUG(dbgs() << "LSV: Vectorizing " << Instrs.size() << " instructions.\n");
597 SmallSetVector<int, 16> Heads, Tails;
598 int ConsecutiveChain[64];
600 // Do a quadratic search on all of the given stores and find all of the pairs
601 // of stores that follow each other.
602 for (int i = 0, e = Instrs.size(); i < e; ++i) {
603 ConsecutiveChain[i] = -1;
604 for (int j = e - 1; j >= 0; --j) {
608 if (isConsecutiveAccess(Instrs[i], Instrs[j])) {
609 if (ConsecutiveChain[i] != -1) {
610 int CurDistance = std::abs(ConsecutiveChain[i] - i);
611 int NewDistance = std::abs(ConsecutiveChain[i] - j);
612 if (j < i || NewDistance > CurDistance)
613 continue; // Should not insert.
618 ConsecutiveChain[i] = j;
623 bool Changed = false;
624 SmallPtrSet<Value *, 16> InstructionsProcessed;
626 for (int Head : Heads) {
627 if (InstructionsProcessed.count(Instrs[Head]))
629 bool longerChainExists = false;
630 for (unsigned TIt = 0; TIt < Tails.size(); TIt++)
631 if (Head == Tails[TIt] &&
632 !InstructionsProcessed.count(Instrs[Heads[TIt]])) {
633 longerChainExists = true;
636 if (longerChainExists)
639 // We found an instr that starts a chain. Now follow the chain and try to
641 SmallVector<Value *, 16> Operands;
643 while (I != -1 && (Tails.count(I) || Heads.count(I))) {
644 if (InstructionsProcessed.count(Instrs[I]))
647 Operands.push_back(Instrs[I]);
648 I = ConsecutiveChain[I];
651 bool Vectorized = false;
652 if (isa<LoadInst>(*Operands.begin()))
653 Vectorized = vectorizeLoadChain(Operands, &InstructionsProcessed);
655 Vectorized = vectorizeStoreChain(Operands, &InstructionsProcessed);
657 Changed |= Vectorized;
663 bool Vectorizer::vectorizeStoreChain(
664 ArrayRef<Value *> Chain, SmallPtrSet<Value *, 16> *InstructionsProcessed) {
665 StoreInst *S0 = cast<StoreInst>(Chain[0]);
667 // If the vector has an int element, default to int for the whole load.
669 for (const auto &V : Chain) {
670 StoreTy = cast<StoreInst>(V)->getValueOperand()->getType();
671 if (StoreTy->isIntOrIntVectorTy())
674 if (StoreTy->isPtrOrPtrVectorTy()) {
675 StoreTy = Type::getIntNTy(F.getParent()->getContext(),
676 DL.getTypeSizeInBits(StoreTy));
681 unsigned Sz = DL.getTypeSizeInBits(StoreTy);
682 unsigned AS = S0->getPointerAddressSpace();
683 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
684 unsigned VF = VecRegSize / Sz;
685 unsigned ChainSize = Chain.size();
687 if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
688 InstructionsProcessed->insert(Chain.begin(), Chain.end());
692 BasicBlock::iterator First, Last;
693 std::tie(First, Last) = getBoundaryInstrs(Chain);
694 unsigned StopChain = getVectorizablePrefixEndIdx(Chain, First, Last);
695 if (StopChain == 0) {
696 // There exists a side effect instruction, no vectorization possible.
697 InstructionsProcessed->insert(Chain.begin(), Chain.end());
700 if (StopChain == 1) {
701 // Failed after the first instruction. Discard it and try the smaller chain.
702 InstructionsProcessed->insert(Chain.front());
706 // Update Chain to the valid vectorizable subchain.
707 Chain = Chain.slice(0, StopChain);
708 ChainSize = Chain.size();
710 // Store size should be 1B, 2B or multiple of 4B.
711 // TODO: Target hook for size constraint?
712 unsigned SzInBytes = (Sz / 8) * ChainSize;
713 if (SzInBytes > 2 && SzInBytes % 4 != 0) {
714 DEBUG(dbgs() << "LSV: Size should be 1B, 2B "
715 "or multiple of 4B. Splitting.\n");
717 return vectorizeStoreChain(Chain.slice(0, ChainSize - 1),
718 InstructionsProcessed);
720 auto Chains = splitOddVectorElts(Chain, Sz);
721 return vectorizeStoreChain(Chains.first, InstructionsProcessed) |
722 vectorizeStoreChain(Chains.second, InstructionsProcessed);
726 VectorType *VecStoreTy = dyn_cast<VectorType>(StoreTy);
728 VecTy = VectorType::get(StoreTy->getScalarType(),
729 Chain.size() * VecStoreTy->getNumElements());
731 VecTy = VectorType::get(StoreTy, Chain.size());
733 // If it's more than the max vector size, break it into two pieces.
734 // TODO: Target hook to control types to split to.
735 if (ChainSize > VF) {
736 DEBUG(dbgs() << "LSV: Vector factor is too big."
737 " Creating two separate arrays.\n");
738 return vectorizeStoreChain(Chain.slice(0, VF), InstructionsProcessed) |
739 vectorizeStoreChain(Chain.slice(VF), InstructionsProcessed);
743 dbgs() << "LSV: Stores to vectorize:\n";
744 for (Value *V : Chain)
748 // We won't try again to vectorize the elements of the chain, regardless of
749 // whether we succeed below.
750 InstructionsProcessed->insert(Chain.begin(), Chain.end());
752 // Check alignment restrictions.
753 unsigned Alignment = getAlignment(S0);
755 // If the store is going to be misaligned, don't vectorize it.
756 if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
757 if (S0->getPointerAddressSpace() != 0)
760 // If we're storing to an object on the stack, we control its alignment,
761 // so we can cheat and change it!
762 Value *V = GetUnderlyingObject(S0->getPointerOperand(), DL);
763 if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V)) {
764 AI->setAlignment(TargetBaseAlign);
765 Alignment = TargetBaseAlign;
772 Builder.SetInsertPoint(&*Last);
774 Value *Vec = UndefValue::get(VecTy);
777 unsigned VecWidth = VecStoreTy->getNumElements();
778 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
779 StoreInst *Store = cast<StoreInst>(Chain[I]);
780 for (unsigned J = 0, NE = VecStoreTy->getNumElements(); J != NE; ++J) {
781 unsigned NewIdx = J + I * VecWidth;
782 Value *Extract = Builder.CreateExtractElement(Store->getValueOperand(),
783 Builder.getInt32(J));
784 if (Extract->getType() != StoreTy->getScalarType())
785 Extract = Builder.CreateBitCast(Extract, StoreTy->getScalarType());
788 Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(NewIdx));
793 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
794 StoreInst *Store = cast<StoreInst>(Chain[I]);
795 Value *Extract = Store->getValueOperand();
796 if (Extract->getType() != StoreTy->getScalarType())
798 Builder.CreateBitOrPointerCast(Extract, StoreTy->getScalarType());
801 Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(I));
807 Builder.CreateBitCast(S0->getPointerOperand(), VecTy->getPointerTo(AS));
808 StoreInst *SI = cast<StoreInst>(Builder.CreateStore(Vec, Bitcast));
809 propagateMetadata(SI, Chain);
810 SI->setAlignment(Alignment);
812 eraseInstructions(Chain);
813 ++NumVectorInstructions;
814 NumScalarsVectorized += Chain.size();
818 bool Vectorizer::vectorizeLoadChain(
819 ArrayRef<Value *> Chain, SmallPtrSet<Value *, 16> *InstructionsProcessed) {
820 LoadInst *L0 = cast<LoadInst>(Chain[0]);
822 // If the vector has an int element, default to int for the whole load.
824 for (const auto &V : Chain) {
825 LoadTy = cast<LoadInst>(V)->getType();
826 if (LoadTy->isIntOrIntVectorTy())
829 if (LoadTy->isPtrOrPtrVectorTy()) {
830 LoadTy = Type::getIntNTy(F.getParent()->getContext(),
831 DL.getTypeSizeInBits(LoadTy));
836 unsigned Sz = DL.getTypeSizeInBits(LoadTy);
837 unsigned AS = L0->getPointerAddressSpace();
838 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
839 unsigned VF = VecRegSize / Sz;
840 unsigned ChainSize = Chain.size();
842 if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
843 InstructionsProcessed->insert(Chain.begin(), Chain.end());
847 BasicBlock::iterator First, Last;
848 std::tie(First, Last) = getBoundaryInstrs(Chain);
849 unsigned StopChain = getVectorizablePrefixEndIdx(Chain, First, Last);
850 if (StopChain == 0) {
851 // There exists a side effect instruction, no vectorization possible.
852 InstructionsProcessed->insert(Chain.begin(), Chain.end());
855 if (StopChain == 1) {
856 // Failed after the first instruction. Discard it and try the smaller chain.
857 InstructionsProcessed->insert(Chain.front());
861 // Update Chain to the valid vectorizable subchain.
862 Chain = Chain.slice(0, StopChain);
863 ChainSize = Chain.size();
865 // Load size should be 1B, 2B or multiple of 4B.
866 // TODO: Should size constraint be a target hook?
867 unsigned SzInBytes = (Sz / 8) * ChainSize;
868 if (SzInBytes > 2 && SzInBytes % 4 != 0) {
869 DEBUG(dbgs() << "LSV: Size should be 1B, 2B "
870 "or multiple of 4B. Splitting.\n");
872 return vectorizeLoadChain(Chain.slice(0, ChainSize - 1),
873 InstructionsProcessed);
874 auto Chains = splitOddVectorElts(Chain, Sz);
875 return vectorizeLoadChain(Chains.first, InstructionsProcessed) |
876 vectorizeLoadChain(Chains.second, InstructionsProcessed);
880 VectorType *VecLoadTy = dyn_cast<VectorType>(LoadTy);
882 VecTy = VectorType::get(LoadTy->getScalarType(),
883 Chain.size() * VecLoadTy->getNumElements());
885 VecTy = VectorType::get(LoadTy, Chain.size());
887 // If it's more than the max vector size, break it into two pieces.
888 // TODO: Target hook to control types to split to.
889 if (ChainSize > VF) {
890 DEBUG(dbgs() << "LSV: Vector factor is too big. "
891 "Creating two separate arrays.\n");
892 return vectorizeLoadChain(Chain.slice(0, VF), InstructionsProcessed) |
893 vectorizeLoadChain(Chain.slice(VF), InstructionsProcessed);
896 // We won't try again to vectorize the elements of the chain, regardless of
897 // whether we succeed below.
898 InstructionsProcessed->insert(Chain.begin(), Chain.end());
900 // Check alignment restrictions.
901 unsigned Alignment = getAlignment(L0);
903 // If the load is going to be misaligned, don't vectorize it.
904 if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
905 if (L0->getPointerAddressSpace() != 0)
908 // If we're loading from an object on the stack, we control its alignment,
909 // so we can cheat and change it!
910 Value *V = GetUnderlyingObject(L0->getPointerOperand(), DL);
911 if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V)) {
912 AI->setAlignment(TargetBaseAlign);
913 Alignment = TargetBaseAlign;
920 dbgs() << "LSV: Loads to vectorize:\n";
921 for (Value *V : Chain)
926 Builder.SetInsertPoint(&*First);
929 Builder.CreateBitCast(L0->getPointerOperand(), VecTy->getPointerTo(AS));
931 LoadInst *LI = cast<LoadInst>(Builder.CreateLoad(Bitcast));
932 propagateMetadata(LI, Chain);
933 LI->setAlignment(Alignment);
936 SmallVector<Instruction *, 16> InstrsToErase;
937 SmallVector<Instruction *, 16> InstrsToReorder;
938 InstrsToReorder.push_back(cast<Instruction>(Bitcast));
940 unsigned VecWidth = VecLoadTy->getNumElements();
941 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
942 for (auto Use : Chain[I]->users()) {
943 Instruction *UI = cast<Instruction>(Use);
944 unsigned Idx = cast<ConstantInt>(UI->getOperand(1))->getZExtValue();
945 unsigned NewIdx = Idx + I * VecWidth;
946 Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(NewIdx));
947 Instruction *Extracted = cast<Instruction>(V);
948 if (Extracted->getType() != UI->getType())
949 Extracted = cast<Instruction>(
950 Builder.CreateBitCast(Extracted, UI->getType()));
952 // Replace the old instruction.
953 UI->replaceAllUsesWith(Extracted);
954 InstrsToErase.push_back(UI);
958 for (Instruction *ModUser : InstrsToReorder)
961 for (auto I : InstrsToErase)
962 I->eraseFromParent();
964 SmallVector<Instruction *, 16> InstrsToReorder;
965 InstrsToReorder.push_back(cast<Instruction>(Bitcast));
967 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
968 Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(I));
969 Instruction *Extracted = cast<Instruction>(V);
970 Instruction *UI = cast<Instruction>(Chain[I]);
971 if (Extracted->getType() != UI->getType()) {
972 Extracted = cast<Instruction>(
973 Builder.CreateBitOrPointerCast(Extracted, UI->getType()));
976 // Replace the old instruction.
977 UI->replaceAllUsesWith(Extracted);
980 for (Instruction *ModUser : InstrsToReorder)
984 eraseInstructions(Chain);
986 ++NumVectorInstructions;
987 NumScalarsVectorized += Chain.size();
991 bool Vectorizer::accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
992 unsigned Alignment) {
994 bool Allows = TTI.allowsMisalignedMemoryAccesses(SzInBytes * 8, AddressSpace,
996 // TODO: Remove TargetBaseAlign
997 return !(Allows && Fast) && (Alignment % SzInBytes) != 0 &&
998 (Alignment % TargetBaseAlign) != 0;