Bug Summary

File:lib/Transforms/Vectorize/LoadStoreVectorizer.cpp
Warning:line 913, column 17
1st function call argument is an uninitialized value

Annotated Source Code

1//===----- LoadStoreVectorizer.cpp - GPU Load & Store Vectorizer ----------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//===----------------------------------------------------------------------===//
11
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/OrderedBasicBlock.h"
19#include "llvm/Analysis/ScalarEvolution.h"
20#include "llvm/Analysis/ScalarEvolutionExpressions.h"
21#include "llvm/Analysis/TargetTransformInfo.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/Analysis/VectorUtils.h"
24#include "llvm/IR/DataLayout.h"
25#include "llvm/IR/Dominators.h"
26#include "llvm/IR/IRBuilder.h"
27#include "llvm/IR/Instructions.h"
28#include "llvm/IR/Module.h"
29#include "llvm/IR/Type.h"
30#include "llvm/IR/Value.h"
31#include "llvm/Support/CommandLine.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/KnownBits.h"
34#include "llvm/Support/raw_ostream.h"
35#include "llvm/Transforms/Utils/Local.h"
36#include "llvm/Transforms/Vectorize.h"
37
38using namespace llvm;
39
40#define DEBUG_TYPE"load-store-vectorizer" "load-store-vectorizer"
41STATISTIC(NumVectorInstructions, "Number of vector accesses generated")static llvm::Statistic NumVectorInstructions = {"load-store-vectorizer"
, "NumVectorInstructions", "Number of vector accesses generated"
, {0}, false}
;
42STATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized")static llvm::Statistic NumScalarsVectorized = {"load-store-vectorizer"
, "NumScalarsVectorized", "Number of scalar accesses vectorized"
, {0}, false}
;
43
44namespace {
45
46// FIXME: Assuming stack alignment of 4 is always good enough
47static const unsigned StackAdjustedAlignment = 4;
48typedef SmallVector<Instruction *, 8> InstrList;
49typedef MapVector<Value *, InstrList> InstrListMap;
50
51class Vectorizer {
52 Function &F;
53 AliasAnalysis &AA;
54 DominatorTree &DT;
55 ScalarEvolution &SE;
56 TargetTransformInfo &TTI;
57 const DataLayout &DL;
58 IRBuilder<> Builder;
59
60public:
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()) {}
65
66 bool run();
67
68private:
69 Value *getPointerOperand(Value *I) const;
70
71 GetElementPtrInst *getSourceGEP(Value *Src) const;
72
73 unsigned getPointerAddressSpace(Value *I);
74
75 unsigned getAlignment(LoadInst *LI) const {
76 unsigned Align = LI->getAlignment();
77 if (Align != 0)
78 return Align;
79
80 return DL.getABITypeAlignment(LI->getType());
81 }
82
83 unsigned getAlignment(StoreInst *SI) const {
84 unsigned Align = SI->getAlignment();
85 if (Align != 0)
86 return Align;
87
88 return DL.getABITypeAlignment(SI->getValueOperand()->getType());
89 }
90
91 bool isConsecutiveAccess(Value *A, Value *B);
92
93 /// After vectorization, reorder the instructions that I depends on
94 /// (the instructions defining its operands), to ensure they dominate I.
95 void reorder(Instruction *I);
96
97 /// Returns the first and the last instructions in Chain.
98 std::pair<BasicBlock::iterator, BasicBlock::iterator>
99 getBoundaryInstrs(ArrayRef<Instruction *> Chain);
100
101 /// Erases the original instructions after vectorizing.
102 void eraseInstructions(ArrayRef<Instruction *> Chain);
103
104 /// "Legalize" the vector type that would be produced by combining \p
105 /// ElementSizeBits elements in \p Chain. Break into two pieces such that the
106 /// total size of each piece is 1, 2 or a multiple of 4 bytes. \p Chain is
107 /// expected to have more than 4 elements.
108 std::pair<ArrayRef<Instruction *>, ArrayRef<Instruction *>>
109 splitOddVectorElts(ArrayRef<Instruction *> Chain, unsigned ElementSizeBits);
110
111 /// Finds the largest prefix of Chain that's vectorizable, checking for
112 /// intervening instructions which may affect the memory accessed by the
113 /// instructions within Chain.
114 ///
115 /// The elements of \p Chain must be all loads or all stores and must be in
116 /// address order.
117 ArrayRef<Instruction *> getVectorizablePrefix(ArrayRef<Instruction *> Chain);
118
119 /// Collects load and store instructions to vectorize.
120 std::pair<InstrListMap, InstrListMap> collectInstructions(BasicBlock *BB);
121
122 /// Processes the collected instructions, the \p Map. The values of \p Map
123 /// should be all loads or all stores.
124 bool vectorizeChains(InstrListMap &Map);
125
126 /// Finds the load/stores to consecutive memory addresses and vectorizes them.
127 bool vectorizeInstructions(ArrayRef<Instruction *> Instrs);
128
129 /// Vectorizes the load instructions in Chain.
130 bool
131 vectorizeLoadChain(ArrayRef<Instruction *> Chain,
132 SmallPtrSet<Instruction *, 16> *InstructionsProcessed);
133
134 /// Vectorizes the store instructions in Chain.
135 bool
136 vectorizeStoreChain(ArrayRef<Instruction *> Chain,
137 SmallPtrSet<Instruction *, 16> *InstructionsProcessed);
138
139 /// Check if this load/store access is misaligned accesses.
140 bool accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
141 unsigned Alignment);
142};
143
144class LoadStoreVectorizer : public FunctionPass {
145public:
146 static char ID;
147
148 LoadStoreVectorizer() : FunctionPass(ID) {
149 initializeLoadStoreVectorizerPass(*PassRegistry::getPassRegistry());
150 }
151
152 bool runOnFunction(Function &F) override;
153
154 StringRef getPassName() const override {
155 return "GPU Load and Store Vectorizer";
156 }
157
158 void getAnalysisUsage(AnalysisUsage &AU) const override {
159 AU.addRequired<AAResultsWrapperPass>();
160 AU.addRequired<ScalarEvolutionWrapperPass>();
161 AU.addRequired<DominatorTreeWrapperPass>();
162 AU.addRequired<TargetTransformInfoWrapperPass>();
163 AU.setPreservesCFG();
164 }
165};
166}
167
168INITIALIZE_PASS_BEGIN(LoadStoreVectorizer, DEBUG_TYPE,static void *initializeLoadStoreVectorizerPassOnce(PassRegistry
&Registry) {
169 "Vectorize load and Store instructions", false, false)static void *initializeLoadStoreVectorizerPassOnce(PassRegistry
&Registry) {
170INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)initializeSCEVAAWrapperPassPass(Registry);
171INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
172INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
173INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
174INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
175INITIALIZE_PASS_END(LoadStoreVectorizer, DEBUG_TYPE,PassInfo *PI = new PassInfo( "Vectorize load and store instructions"
, "load-store-vectorizer", &LoadStoreVectorizer::ID, PassInfo
::NormalCtor_t(callDefaultCtor<LoadStoreVectorizer>), false
, false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeLoadStoreVectorizerPassFlag; void llvm
::initializeLoadStoreVectorizerPass(PassRegistry &Registry
) { llvm::call_once(InitializeLoadStoreVectorizerPassFlag, initializeLoadStoreVectorizerPassOnce
, std::ref(Registry)); }
176 "Vectorize load and store instructions", false, false)PassInfo *PI = new PassInfo( "Vectorize load and store instructions"
, "load-store-vectorizer", &LoadStoreVectorizer::ID, PassInfo
::NormalCtor_t(callDefaultCtor<LoadStoreVectorizer>), false
, false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeLoadStoreVectorizerPassFlag; void llvm
::initializeLoadStoreVectorizerPass(PassRegistry &Registry
) { llvm::call_once(InitializeLoadStoreVectorizerPassFlag, initializeLoadStoreVectorizerPassOnce
, std::ref(Registry)); }
177
178char LoadStoreVectorizer::ID = 0;
179
180Pass *llvm::createLoadStoreVectorizerPass() {
181 return new LoadStoreVectorizer();
182}
183
184// The real propagateMetadata expects a SmallVector<Value*>, but we deal in
185// vectors of Instructions.
186static void propagateMetadata(Instruction *I, ArrayRef<Instruction *> IL) {
187 SmallVector<Value *, 8> VL(IL.begin(), IL.end());
188 propagateMetadata(I, VL);
189}
190
191bool LoadStoreVectorizer::runOnFunction(Function &F) {
192 // Don't vectorize when the attribute NoImplicitFloat is used.
193 if (skipFunction(F) || F.hasFnAttribute(Attribute::NoImplicitFloat))
1
Assuming the condition is false
2
Assuming the condition is false
3
Taking false branch
194 return false;
195
196 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
197 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
198 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
199 TargetTransformInfo &TTI =
200 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
201
202 Vectorizer V(F, AA, DT, SE, TTI);
203 return V.run();
4
Calling 'Vectorizer::run'
204}
205
206// Vectorizer Implementation
207bool Vectorizer::run() {
208 bool Changed = false;
209
210 // Scan the blocks in the function in post order.
211 for (BasicBlock *BB : post_order(&F)) {
212 InstrListMap LoadRefs, StoreRefs;
213 std::tie(LoadRefs, StoreRefs) = collectInstructions(BB);
214 Changed |= vectorizeChains(LoadRefs);
215 Changed |= vectorizeChains(StoreRefs);
5
Calling 'Vectorizer::vectorizeChains'
216 }
217
218 return Changed;
219}
220
221Value *Vectorizer::getPointerOperand(Value *I) const {
222 if (LoadInst *LI = dyn_cast<LoadInst>(I))
223 return LI->getPointerOperand();
224 if (StoreInst *SI = dyn_cast<StoreInst>(I))
225 return SI->getPointerOperand();
226 return nullptr;
227}
228
229unsigned Vectorizer::getPointerAddressSpace(Value *I) {
230 if (LoadInst *L = dyn_cast<LoadInst>(I))
231 return L->getPointerAddressSpace();
232 if (StoreInst *S = dyn_cast<StoreInst>(I))
233 return S->getPointerAddressSpace();
234 return -1;
235}
236
237GetElementPtrInst *Vectorizer::getSourceGEP(Value *Src) const {
238 // First strip pointer bitcasts. Make sure pointee size is the same with
239 // and without casts.
240 // TODO: a stride set by the add instruction below can match the difference
241 // in pointee type size here. Currently it will not be vectorized.
242 Value *SrcPtr = getPointerOperand(Src);
243 Value *SrcBase = SrcPtr->stripPointerCasts();
244 if (DL.getTypeStoreSize(SrcPtr->getType()->getPointerElementType()) ==
245 DL.getTypeStoreSize(SrcBase->getType()->getPointerElementType()))
246 SrcPtr = SrcBase;
247 return dyn_cast<GetElementPtrInst>(SrcPtr);
248}
249
250// FIXME: Merge with llvm::isConsecutiveAccess
251bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) {
252 Value *PtrA = getPointerOperand(A);
253 Value *PtrB = getPointerOperand(B);
254 unsigned ASA = getPointerAddressSpace(A);
255 unsigned ASB = getPointerAddressSpace(B);
256
257 // Check that the address spaces match and that the pointers are valid.
258 if (!PtrA || !PtrB || (ASA != ASB))
259 return false;
260
261 // Make sure that A and B are different pointers of the same size type.
262 unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
263 Type *PtrATy = PtrA->getType()->getPointerElementType();
264 Type *PtrBTy = PtrB->getType()->getPointerElementType();
265 if (PtrA == PtrB ||
266 DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) ||
267 DL.getTypeStoreSize(PtrATy->getScalarType()) !=
268 DL.getTypeStoreSize(PtrBTy->getScalarType()))
269 return false;
270
271 APInt Size(PtrBitWidth, DL.getTypeStoreSize(PtrATy));
272
273 APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0);
274 PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
275 PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
276
277 APInt OffsetDelta = OffsetB - OffsetA;
278
279 // Check if they are based on the same pointer. That makes the offsets
280 // sufficient.
281 if (PtrA == PtrB)
282 return OffsetDelta == Size;
283
284 // Compute the necessary base pointer delta to have the necessary final delta
285 // equal to the size.
286 APInt BaseDelta = Size - OffsetDelta;
287
288 // Compute the distance with SCEV between the base pointers.
289 const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
290 const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
291 const SCEV *C = SE.getConstant(BaseDelta);
292 const SCEV *X = SE.getAddExpr(PtrSCEVA, C);
293 if (X == PtrSCEVB)
294 return true;
295
296 // Sometimes even this doesn't work, because SCEV can't always see through
297 // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking
298 // things the hard way.
299
300 // Look through GEPs after checking they're the same except for the last
301 // index.
302 GetElementPtrInst *GEPA = getSourceGEP(A);
303 GetElementPtrInst *GEPB = getSourceGEP(B);
304 if (!GEPA || !GEPB || GEPA->getNumOperands() != GEPB->getNumOperands())
305 return false;
306 unsigned FinalIndex = GEPA->getNumOperands() - 1;
307 for (unsigned i = 0; i < FinalIndex; i++)
308 if (GEPA->getOperand(i) != GEPB->getOperand(i))
309 return false;
310
311 Instruction *OpA = dyn_cast<Instruction>(GEPA->getOperand(FinalIndex));
312 Instruction *OpB = dyn_cast<Instruction>(GEPB->getOperand(FinalIndex));
313 if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() ||
314 OpA->getType() != OpB->getType())
315 return false;
316
317 // Only look through a ZExt/SExt.
318 if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA))
319 return false;
320
321 bool Signed = isa<SExtInst>(OpA);
322
323 OpA = dyn_cast<Instruction>(OpA->getOperand(0));
324 OpB = dyn_cast<Instruction>(OpB->getOperand(0));
325 if (!OpA || !OpB || OpA->getType() != OpB->getType())
326 return false;
327
328 // Now we need to prove that adding 1 to OpA won't overflow.
329 bool Safe = false;
330 // First attempt: if OpB is an add with NSW/NUW, and OpB is 1 added to OpA,
331 // we're okay.
332 if (OpB->getOpcode() == Instruction::Add &&
333 isa<ConstantInt>(OpB->getOperand(1)) &&
334 cast<ConstantInt>(OpB->getOperand(1))->getSExtValue() > 0) {
335 if (Signed)
336 Safe = cast<BinaryOperator>(OpB)->hasNoSignedWrap();
337 else
338 Safe = cast<BinaryOperator>(OpB)->hasNoUnsignedWrap();
339 }
340
341 unsigned BitWidth = OpA->getType()->getScalarSizeInBits();
342
343 // Second attempt:
344 // If any bits are known to be zero other than the sign bit in OpA, we can
345 // add 1 to it while guaranteeing no overflow of any sort.
346 if (!Safe) {
347 KnownBits Known(BitWidth);
348 computeKnownBits(OpA, Known, DL, 0, nullptr, OpA, &DT);
349 if (Known.countMaxTrailingOnes() < (BitWidth - 1))
350 Safe = true;
351 }
352
353 if (!Safe)
354 return false;
355
356 const SCEV *OffsetSCEVA = SE.getSCEV(OpA);
357 const SCEV *OffsetSCEVB = SE.getSCEV(OpB);
358 const SCEV *One = SE.getConstant(APInt(BitWidth, 1));
359 const SCEV *X2 = SE.getAddExpr(OffsetSCEVA, One);
360 return X2 == OffsetSCEVB;
361}
362
363void Vectorizer::reorder(Instruction *I) {
364 OrderedBasicBlock OBB(I->getParent());
365 SmallPtrSet<Instruction *, 16> InstructionsToMove;
366 SmallVector<Instruction *, 16> Worklist;
367
368 Worklist.push_back(I);
369 while (!Worklist.empty()) {
370 Instruction *IW = Worklist.pop_back_val();
371 int NumOperands = IW->getNumOperands();
372 for (int i = 0; i < NumOperands; i++) {
373 Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i));
374 if (!IM || IM->getOpcode() == Instruction::PHI)
375 continue;
376
377 // If IM is in another BB, no need to move it, because this pass only
378 // vectorizes instructions within one BB.
379 if (IM->getParent() != I->getParent())
380 continue;
381
382 if (!OBB.dominates(IM, I)) {
383 InstructionsToMove.insert(IM);
384 Worklist.push_back(IM);
385 }
386 }
387 }
388
389 // All instructions to move should follow I. Start from I, not from begin().
390 for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;
391 ++BBI) {
392 if (!InstructionsToMove.count(&*BBI))
393 continue;
394 Instruction *IM = &*BBI;
395 --BBI;
396 IM->removeFromParent();
397 IM->insertBefore(I);
398 }
399}
400
401std::pair<BasicBlock::iterator, BasicBlock::iterator>
402Vectorizer::getBoundaryInstrs(ArrayRef<Instruction *> Chain) {
403 Instruction *C0 = Chain[0];
404 BasicBlock::iterator FirstInstr = C0->getIterator();
405 BasicBlock::iterator LastInstr = C0->getIterator();
406
407 BasicBlock *BB = C0->getParent();
408 unsigned NumFound = 0;
409 for (Instruction &I : *BB) {
410 if (!is_contained(Chain, &I))
411 continue;
412
413 ++NumFound;
414 if (NumFound == 1) {
415 FirstInstr = I.getIterator();
416 }
417 if (NumFound == Chain.size()) {
418 LastInstr = I.getIterator();
419 break;
420 }
421 }
422
423 // Range is [first, last).
424 return std::make_pair(FirstInstr, ++LastInstr);
425}
426
427void Vectorizer::eraseInstructions(ArrayRef<Instruction *> Chain) {
428 SmallVector<Instruction *, 16> Instrs;
429 for (Instruction *I : Chain) {
430 Value *PtrOperand = getPointerOperand(I);
431 assert(PtrOperand && "Instruction must have a pointer operand.")((PtrOperand && "Instruction must have a pointer operand."
) ? static_cast<void> (0) : __assert_fail ("PtrOperand && \"Instruction must have a pointer operand.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 431, __PRETTY_FUNCTION__))
;
432 Instrs.push_back(I);
433 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(PtrOperand))
434 Instrs.push_back(GEP);
435 }
436
437 // Erase instructions.
438 for (Instruction *I : Instrs)
439 if (I->use_empty())
440 I->eraseFromParent();
441}
442
443std::pair<ArrayRef<Instruction *>, ArrayRef<Instruction *>>
444Vectorizer::splitOddVectorElts(ArrayRef<Instruction *> Chain,
445 unsigned ElementSizeBits) {
446 unsigned ElementSizeBytes = ElementSizeBits / 8;
447 unsigned SizeBytes = ElementSizeBytes * Chain.size();
448 unsigned NumLeft = (SizeBytes - (SizeBytes % 4)) / ElementSizeBytes;
449 if (NumLeft == Chain.size()) {
450 if ((NumLeft & 1) == 0)
451 NumLeft /= 2; // Split even in half
452 else
453 --NumLeft; // Split off last element
454 } else if (NumLeft == 0)
455 NumLeft = 1;
456 return std::make_pair(Chain.slice(0, NumLeft), Chain.slice(NumLeft));
457}
458
459ArrayRef<Instruction *>
460Vectorizer::getVectorizablePrefix(ArrayRef<Instruction *> Chain) {
461 // These are in BB order, unlike Chain, which is in address order.
462 SmallVector<Instruction *, 16> MemoryInstrs;
463 SmallVector<Instruction *, 16> ChainInstrs;
464
465 bool IsLoadChain = isa<LoadInst>(Chain[0]);
466 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
467 for (Instruction *I : Chain) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
468 if (IsLoadChain)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
469 assert(isa<LoadInst>(I) &&do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
470 "All elements of Chain must be loads, or all must be stores.");do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
471 elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
472 assert(isa<StoreInst>(I) &&do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
473 "All elements of Chain must be loads, or all must be stores.");do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
474 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
475 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { for (Instruction *I : Chain) {
if (IsLoadChain) ((isa<LoadInst>(I) && "All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 470, __PRETTY_FUNCTION__)); else ((isa<StoreInst>(I) &&
"All elements of Chain must be loads, or all must be stores."
) ? static_cast<void> (0) : __assert_fail ("isa<StoreInst>(I) && \"All elements of Chain must be loads, or all must be stores.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 473, __PRETTY_FUNCTION__)); } }; } } while (false)
;
476
477 for (Instruction &I : make_range(getBoundaryInstrs(Chain))) {
478 if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
479 if (!is_contained(Chain, &I))
480 MemoryInstrs.push_back(&I);
481 else
482 ChainInstrs.push_back(&I);
483 } else if (IsLoadChain && (I.mayWriteToMemory() || I.mayThrow())) {
484 DEBUG(dbgs() << "LSV: Found may-write/throw operation: " << I << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Found may-write/throw operation: "
<< I << '\n'; } } while (false)
;
485 break;
486 } else if (!IsLoadChain && (I.mayReadOrWriteMemory() || I.mayThrow())) {
487 DEBUG(dbgs() << "LSV: Found may-read/write/throw operation: " << Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Found may-read/write/throw operation: "
<< I << '\n'; } } while (false)
488 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Found may-read/write/throw operation: "
<< I << '\n'; } } while (false)
;
489 break;
490 }
491 }
492
493 OrderedBasicBlock OBB(Chain[0]->getParent());
494
495 // Loop until we find an instruction in ChainInstrs that we can't vectorize.
496 unsigned ChainInstrIdx = 0;
497 Instruction *BarrierMemoryInstr = nullptr;
498
499 for (unsigned E = ChainInstrs.size(); ChainInstrIdx < E; ++ChainInstrIdx) {
500 Instruction *ChainInstr = ChainInstrs[ChainInstrIdx];
501
502 // If a barrier memory instruction was found, chain instructions that follow
503 // will not be added to the valid prefix.
504 if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, ChainInstr))
505 break;
506
507 // Check (in BB order) if any instruction prevents ChainInstr from being
508 // vectorized. Find and store the first such "conflicting" instruction.
509 for (Instruction *MemInstr : MemoryInstrs) {
510 // If a barrier memory instruction was found, do not check past it.
511 if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, MemInstr))
512 break;
513
514 if (isa<LoadInst>(MemInstr) && isa<LoadInst>(ChainInstr))
515 continue;
516
517 // We can ignore the alias as long as the load comes before the store,
518 // because that means we won't be moving the load past the store to
519 // vectorize it (the vectorized load is inserted at the location of the
520 // first load in the chain).
521 if (isa<StoreInst>(MemInstr) && isa<LoadInst>(ChainInstr) &&
522 OBB.dominates(ChainInstr, MemInstr))
523 continue;
524
525 // Same case, but in reverse.
526 if (isa<LoadInst>(MemInstr) && isa<StoreInst>(ChainInstr) &&
527 OBB.dominates(MemInstr, ChainInstr))
528 continue;
529
530 if (!AA.isNoAlias(MemoryLocation::get(MemInstr),
531 MemoryLocation::get(ChainInstr))) {
532 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
533 dbgs() << "LSV: Found alias:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
534 " Aliasing instruction and pointer:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
535 << " " << *MemInstr << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
536 << " " << *getPointerOperand(MemInstr) << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
537 << " Aliased instruction and pointer:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
538 << " " << *ChainInstr << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
539 << " " << *getPointerOperand(ChainInstr) << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
540 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getPointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getPointerOperand(ChainInstr) << '\n'; }; } }
while (false)
;
541 // Save this aliasing memory instruction as a barrier, but allow other
542 // instructions that precede the barrier to be vectorized with this one.
543 BarrierMemoryInstr = MemInstr;
544 break;
545 }
546 }
547 // Continue the search only for store chains, since vectorizing stores that
548 // precede an aliasing load is valid. Conversely, vectorizing loads is valid
549 // up to an aliasing store, but should not pull loads from further down in
550 // the basic block.
551 if (IsLoadChain && BarrierMemoryInstr) {
552 // The BarrierMemoryInstr is a store that precedes ChainInstr.
553 assert(OBB.dominates(BarrierMemoryInstr, ChainInstr))((OBB.dominates(BarrierMemoryInstr, ChainInstr)) ? static_cast
<void> (0) : __assert_fail ("OBB.dominates(BarrierMemoryInstr, ChainInstr)"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 553, __PRETTY_FUNCTION__))
;
554 break;
555 }
556 }
557
558 // Find the largest prefix of Chain whose elements are all in
559 // ChainInstrs[0, ChainInstrIdx). This is the largest vectorizable prefix of
560 // Chain. (Recall that Chain is in address order, but ChainInstrs is in BB
561 // order.)
562 SmallPtrSet<Instruction *, 8> VectorizableChainInstrs(
563 ChainInstrs.begin(), ChainInstrs.begin() + ChainInstrIdx);
564 unsigned ChainIdx = 0;
565 for (unsigned ChainLen = Chain.size(); ChainIdx < ChainLen; ++ChainIdx) {
566 if (!VectorizableChainInstrs.count(Chain[ChainIdx]))
567 break;
568 }
569 return Chain.slice(0, ChainIdx);
570}
571
572std::pair<InstrListMap, InstrListMap>
573Vectorizer::collectInstructions(BasicBlock *BB) {
574 InstrListMap LoadRefs;
575 InstrListMap StoreRefs;
576
577 for (Instruction &I : *BB) {
578 if (!I.mayReadOrWriteMemory())
579 continue;
580
581 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
582 if (!LI->isSimple())
583 continue;
584
585 // Skip if it's not legal.
586 if (!TTI.isLegalToVectorizeLoad(LI))
587 continue;
588
589 Type *Ty = LI->getType();
590 if (!VectorType::isValidElementType(Ty->getScalarType()))
591 continue;
592
593 // Skip weird non-byte sizes. They probably aren't worth the effort of
594 // handling correctly.
595 unsigned TySize = DL.getTypeSizeInBits(Ty);
596 if (TySize < 8)
597 continue;
598
599 Value *Ptr = LI->getPointerOperand();
600 unsigned AS = Ptr->getType()->getPointerAddressSpace();
601 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
602
603 // No point in looking at these if they're too big to vectorize.
604 if (TySize > VecRegSize / 2)
605 continue;
606
607 // Make sure all the users of a vector are constant-index extracts.
608 if (isa<VectorType>(Ty) && !all_of(LI->users(), [](const User *U) {
609 const ExtractElementInst *EEI = dyn_cast<ExtractElementInst>(U);
610 return EEI && isa<ConstantInt>(EEI->getOperand(1));
611 }))
612 continue;
613
614 // Save the load locations.
615 Value *ObjPtr = GetUnderlyingObject(Ptr, DL);
616 LoadRefs[ObjPtr].push_back(LI);
617
618 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
619 if (!SI->isSimple())
620 continue;
621
622 // Skip if it's not legal.
623 if (!TTI.isLegalToVectorizeStore(SI))
624 continue;
625
626 Type *Ty = SI->getValueOperand()->getType();
627 if (!VectorType::isValidElementType(Ty->getScalarType()))
628 continue;
629
630 // Skip weird non-byte sizes. They probably aren't worth the effort of
631 // handling correctly.
632 unsigned TySize = DL.getTypeSizeInBits(Ty);
633 if (TySize < 8)
634 continue;
635
636 Value *Ptr = SI->getPointerOperand();
637 unsigned AS = Ptr->getType()->getPointerAddressSpace();
638 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
639 if (TySize > VecRegSize / 2)
640 continue;
641
642 if (isa<VectorType>(Ty) && !all_of(SI->users(), [](const User *U) {
643 const ExtractElementInst *EEI = dyn_cast<ExtractElementInst>(U);
644 return EEI && isa<ConstantInt>(EEI->getOperand(1));
645 }))
646 continue;
647
648 // Save store location.
649 Value *ObjPtr = GetUnderlyingObject(Ptr, DL);
650 StoreRefs[ObjPtr].push_back(SI);
651 }
652 }
653
654 return {LoadRefs, StoreRefs};
655}
656
657bool Vectorizer::vectorizeChains(InstrListMap &Map) {
658 bool Changed = false;
659
660 for (const std::pair<Value *, InstrList> &Chain : Map) {
661 unsigned Size = Chain.second.size();
662 if (Size < 2)
6
Assuming 'Size' is >= 2
7
Taking false branch
663 continue;
664
665 DEBUG(dbgs() << "LSV: Analyzing a chain of length " << Size << ".\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Analyzing a chain of length "
<< Size << ".\n"; } } while (false)
;
666
667 // Process the stores in chunks of 64.
668 for (unsigned CI = 0, CE = Size; CI < CE; CI += 64) {
8
Loop condition is true. Entering loop body
669 unsigned Len = std::min<unsigned>(CE - CI, 64);
670 ArrayRef<Instruction *> Chunk(&Chain.second[CI], Len);
671 Changed |= vectorizeInstructions(Chunk);
9
Calling 'Vectorizer::vectorizeInstructions'
672 }
673 }
674
675 return Changed;
676}
677
678bool Vectorizer::vectorizeInstructions(ArrayRef<Instruction *> Instrs) {
679 DEBUG(dbgs() << "LSV: Vectorizing " << Instrs.size() << " instructions.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Vectorizing "
<< Instrs.size() << " instructions.\n"; } } while
(false)
;
680 SmallVector<int, 16> Heads, Tails;
681 int ConsecutiveChain[64];
682
683 // Do a quadratic search on all of the given stores and find all of the pairs
684 // of stores that follow each other.
685 for (int i = 0, e = Instrs.size(); i < e; ++i) {
10
Assuming 'i' is >= 'e'
11
Loop condition is false. Execution continues on line 706
686 ConsecutiveChain[i] = -1;
687 for (int j = e - 1; j >= 0; --j) {
688 if (i == j)
689 continue;
690
691 if (isConsecutiveAccess(Instrs[i], Instrs[j])) {
692 if (ConsecutiveChain[i] != -1) {
693 int CurDistance = std::abs(ConsecutiveChain[i] - i);
694 int NewDistance = std::abs(ConsecutiveChain[i] - j);
695 if (j < i || NewDistance > CurDistance)
696 continue; // Should not insert.
697 }
698
699 Tails.push_back(j);
700 Heads.push_back(i);
701 ConsecutiveChain[i] = j;
702 }
703 }
704 }
705
706 bool Changed = false;
707 SmallPtrSet<Instruction *, 16> InstructionsProcessed;
708
709 for (int Head : Heads) {
12
Assuming '__begin' is not equal to '__end'
710 if (InstructionsProcessed.count(Instrs[Head]))
13
Assuming the condition is false
14
Taking false branch
20
Assuming the condition is false
21
Taking false branch
27
Assuming the condition is false
28
Taking false branch
34
Assuming the condition is false
35
Taking false branch
711 continue;
712 bool LongerChainExists = false;
713 for (unsigned TIt = 0; TIt < Tails.size(); TIt++)
15
Assuming the condition is false
16
Loop condition is false. Execution continues on line 719
22
Assuming the condition is false
23
Loop condition is false. Execution continues on line 719
29
Assuming the condition is false
30
Loop condition is false. Execution continues on line 719
36
Assuming the condition is false
37
Loop condition is false. Execution continues on line 719
714 if (Head == Tails[TIt] &&
715 !InstructionsProcessed.count(Instrs[Heads[TIt]])) {
716 LongerChainExists = true;
717 break;
718 }
719 if (LongerChainExists)
17
Taking false branch
24
Taking false branch
31
Taking false branch
38
Taking false branch
720 continue;
721
722 // We found an instr that starts a chain. Now follow the chain and try to
723 // vectorize it.
724 SmallVector<Instruction *, 16> Operands;
725 int I = Head;
726 while (I != -1 && (is_contained(Tails, I) || is_contained(Heads, I))) {
18
Assuming the condition is false
25
Assuming the condition is false
32
Assuming the condition is false
39
Assuming the condition is false
727 if (InstructionsProcessed.count(Instrs[I]))
728 break;
729
730 Operands.push_back(Instrs[I]);
731 I = ConsecutiveChain[I];
732 }
733
734 bool Vectorized = false;
735 if (isa<LoadInst>(*Operands.begin()))
19
Taking false branch
26
Taking false branch
33
Taking false branch
40
Taking true branch
736 Vectorized = vectorizeLoadChain(Operands, &InstructionsProcessed);
41
Calling 'Vectorizer::vectorizeLoadChain'
737 else
738 Vectorized = vectorizeStoreChain(Operands, &InstructionsProcessed);
739
740 Changed |= Vectorized;
741 }
742
743 return Changed;
744}
745
746bool Vectorizer::vectorizeStoreChain(
747 ArrayRef<Instruction *> Chain,
748 SmallPtrSet<Instruction *, 16> *InstructionsProcessed) {
749 StoreInst *S0 = cast<StoreInst>(Chain[0]);
750
751 // If the vector has an int element, default to int for the whole load.
752 Type *StoreTy;
753 for (Instruction *I : Chain) {
754 StoreTy = cast<StoreInst>(I)->getValueOperand()->getType();
755 if (StoreTy->isIntOrIntVectorTy())
756 break;
757
758 if (StoreTy->isPtrOrPtrVectorTy()) {
759 StoreTy = Type::getIntNTy(F.getParent()->getContext(),
760 DL.getTypeSizeInBits(StoreTy));
761 break;
762 }
763 }
764
765 unsigned Sz = DL.getTypeSizeInBits(StoreTy);
766 unsigned AS = S0->getPointerAddressSpace();
767 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
768 unsigned VF = VecRegSize / Sz;
769 unsigned ChainSize = Chain.size();
770 unsigned Alignment = getAlignment(S0);
771
772 if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
773 InstructionsProcessed->insert(Chain.begin(), Chain.end());
774 return false;
775 }
776
777 ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain);
778 if (NewChain.empty()) {
779 // No vectorization possible.
780 InstructionsProcessed->insert(Chain.begin(), Chain.end());
781 return false;
782 }
783 if (NewChain.size() == 1) {
784 // Failed after the first instruction. Discard it and try the smaller chain.
785 InstructionsProcessed->insert(NewChain.front());
786 return false;
787 }
788
789 // Update Chain to the valid vectorizable subchain.
790 Chain = NewChain;
791 ChainSize = Chain.size();
792
793 // Check if it's legal to vectorize this chain. If not, split the chain and
794 // try again.
795 unsigned EltSzInBytes = Sz / 8;
796 unsigned SzInBytes = EltSzInBytes * ChainSize;
797 if (!TTI.isLegalToVectorizeStoreChain(SzInBytes, Alignment, AS)) {
798 auto Chains = splitOddVectorElts(Chain, Sz);
799 return vectorizeStoreChain(Chains.first, InstructionsProcessed) |
800 vectorizeStoreChain(Chains.second, InstructionsProcessed);
801 }
802
803 VectorType *VecTy;
804 VectorType *VecStoreTy = dyn_cast<VectorType>(StoreTy);
805 if (VecStoreTy)
806 VecTy = VectorType::get(StoreTy->getScalarType(),
807 Chain.size() * VecStoreTy->getNumElements());
808 else
809 VecTy = VectorType::get(StoreTy, Chain.size());
810
811 // If it's more than the max vector size or the target has a better
812 // vector factor, break it into two pieces.
813 unsigned TargetVF = TTI.getStoreVectorFactor(VF, Sz, SzInBytes, VecTy);
814 if (ChainSize > VF || (VF != TargetVF && TargetVF < ChainSize)) {
815 DEBUG(dbgs() << "LSV: Chain doesn't match with the vector factor."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Chain doesn't match with the vector factor."
" Creating two separate arrays.\n"; } } while (false)
816 " Creating two separate arrays.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Chain doesn't match with the vector factor."
" Creating two separate arrays.\n"; } } while (false)
;
817 return vectorizeStoreChain(Chain.slice(0, TargetVF),
818 InstructionsProcessed) |
819 vectorizeStoreChain(Chain.slice(TargetVF), InstructionsProcessed);
820 }
821
822 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Stores to vectorize:\n"
; for (Instruction *I : Chain) dbgs() << " " << *
I << "\n"; }; } } while (false)
823 dbgs() << "LSV: Stores to vectorize:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Stores to vectorize:\n"
; for (Instruction *I : Chain) dbgs() << " " << *
I << "\n"; }; } } while (false)
824 for (Instruction *I : Chain)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Stores to vectorize:\n"
; for (Instruction *I : Chain) dbgs() << " " << *
I << "\n"; }; } } while (false)
825 dbgs() << " " << *I << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Stores to vectorize:\n"
; for (Instruction *I : Chain) dbgs() << " " << *
I << "\n"; }; } } while (false)
826 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Stores to vectorize:\n"
; for (Instruction *I : Chain) dbgs() << " " << *
I << "\n"; }; } } while (false)
;
827
828 // We won't try again to vectorize the elements of the chain, regardless of
829 // whether we succeed below.
830 InstructionsProcessed->insert(Chain.begin(), Chain.end());
831
832 // If the store is going to be misaligned, don't vectorize it.
833 if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
834 if (S0->getPointerAddressSpace() != 0)
835 return false;
836
837 unsigned NewAlign = getOrEnforceKnownAlignment(S0->getPointerOperand(),
838 StackAdjustedAlignment,
839 DL, S0, nullptr, &DT);
840 if (NewAlign < StackAdjustedAlignment)
841 return false;
842 }
843
844 BasicBlock::iterator First, Last;
845 std::tie(First, Last) = getBoundaryInstrs(Chain);
846 Builder.SetInsertPoint(&*Last);
847
848 Value *Vec = UndefValue::get(VecTy);
849
850 if (VecStoreTy) {
851 unsigned VecWidth = VecStoreTy->getNumElements();
852 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
853 StoreInst *Store = cast<StoreInst>(Chain[I]);
854 for (unsigned J = 0, NE = VecStoreTy->getNumElements(); J != NE; ++J) {
855 unsigned NewIdx = J + I * VecWidth;
856 Value *Extract = Builder.CreateExtractElement(Store->getValueOperand(),
857 Builder.getInt32(J));
858 if (Extract->getType() != StoreTy->getScalarType())
859 Extract = Builder.CreateBitCast(Extract, StoreTy->getScalarType());
860
861 Value *Insert =
862 Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(NewIdx));
863 Vec = Insert;
864 }
865 }
866 } else {
867 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
868 StoreInst *Store = cast<StoreInst>(Chain[I]);
869 Value *Extract = Store->getValueOperand();
870 if (Extract->getType() != StoreTy->getScalarType())
871 Extract =
872 Builder.CreateBitOrPointerCast(Extract, StoreTy->getScalarType());
873
874 Value *Insert =
875 Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(I));
876 Vec = Insert;
877 }
878 }
879
880 // This cast is safe because Builder.CreateStore() always creates a bona fide
881 // StoreInst.
882 StoreInst *SI = cast<StoreInst>(
883 Builder.CreateStore(Vec, Builder.CreateBitCast(S0->getPointerOperand(),
884 VecTy->getPointerTo(AS))));
885 propagateMetadata(SI, Chain);
886 SI->setAlignment(Alignment);
887
888 eraseInstructions(Chain);
889 ++NumVectorInstructions;
890 NumScalarsVectorized += Chain.size();
891 return true;
892}
893
894bool Vectorizer::vectorizeLoadChain(
895 ArrayRef<Instruction *> Chain,
896 SmallPtrSet<Instruction *, 16> *InstructionsProcessed) {
897 LoadInst *L0 = cast<LoadInst>(Chain[0]);
898
899 // If the vector has an int element, default to int for the whole load.
900 Type *LoadTy;
42
'LoadTy' declared without an initial value
901 for (const auto &V : Chain) {
43
Assuming '__begin' is equal to '__end'
902 LoadTy = cast<LoadInst>(V)->getType();
903 if (LoadTy->isIntOrIntVectorTy())
904 break;
905
906 if (LoadTy->isPtrOrPtrVectorTy()) {
907 LoadTy = Type::getIntNTy(F.getParent()->getContext(),
908 DL.getTypeSizeInBits(LoadTy));
909 break;
910 }
911 }
912
913 unsigned Sz = DL.getTypeSizeInBits(LoadTy);
44
1st function call argument is an uninitialized value
914 unsigned AS = L0->getPointerAddressSpace();
915 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
916 unsigned VF = VecRegSize / Sz;
917 unsigned ChainSize = Chain.size();
918 unsigned Alignment = getAlignment(L0);
919
920 if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
921 InstructionsProcessed->insert(Chain.begin(), Chain.end());
922 return false;
923 }
924
925 ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain);
926 if (NewChain.empty()) {
927 // No vectorization possible.
928 InstructionsProcessed->insert(Chain.begin(), Chain.end());
929 return false;
930 }
931 if (NewChain.size() == 1) {
932 // Failed after the first instruction. Discard it and try the smaller chain.
933 InstructionsProcessed->insert(NewChain.front());
934 return false;
935 }
936
937 // Update Chain to the valid vectorizable subchain.
938 Chain = NewChain;
939 ChainSize = Chain.size();
940
941 // Check if it's legal to vectorize this chain. If not, split the chain and
942 // try again.
943 unsigned EltSzInBytes = Sz / 8;
944 unsigned SzInBytes = EltSzInBytes * ChainSize;
945 if (!TTI.isLegalToVectorizeLoadChain(SzInBytes, Alignment, AS)) {
946 auto Chains = splitOddVectorElts(Chain, Sz);
947 return vectorizeLoadChain(Chains.first, InstructionsProcessed) |
948 vectorizeLoadChain(Chains.second, InstructionsProcessed);
949 }
950
951 VectorType *VecTy;
952 VectorType *VecLoadTy = dyn_cast<VectorType>(LoadTy);
953 if (VecLoadTy)
954 VecTy = VectorType::get(LoadTy->getScalarType(),
955 Chain.size() * VecLoadTy->getNumElements());
956 else
957 VecTy = VectorType::get(LoadTy, Chain.size());
958
959 // If it's more than the max vector size or the target has a better
960 // vector factor, break it into two pieces.
961 unsigned TargetVF = TTI.getLoadVectorFactor(VF, Sz, SzInBytes, VecTy);
962 if (ChainSize > VF || (VF != TargetVF && TargetVF < ChainSize)) {
963 DEBUG(dbgs() << "LSV: Chain doesn't match with the vector factor."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Chain doesn't match with the vector factor."
" Creating two separate arrays.\n"; } } while (false)
964 " Creating two separate arrays.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Chain doesn't match with the vector factor."
" Creating two separate arrays.\n"; } } while (false)
;
965 return vectorizeLoadChain(Chain.slice(0, TargetVF), InstructionsProcessed) |
966 vectorizeLoadChain(Chain.slice(TargetVF), InstructionsProcessed);
967 }
968
969 // We won't try again to vectorize the elements of the chain, regardless of
970 // whether we succeed below.
971 InstructionsProcessed->insert(Chain.begin(), Chain.end());
972
973 // If the load is going to be misaligned, don't vectorize it.
974 if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
975 if (L0->getPointerAddressSpace() != 0)
976 return false;
977
978 unsigned NewAlign = getOrEnforceKnownAlignment(L0->getPointerOperand(),
979 StackAdjustedAlignment,
980 DL, L0, nullptr, &DT);
981 if (NewAlign < StackAdjustedAlignment)
982 return false;
983
984 Alignment = NewAlign;
985 }
986
987 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Loads to vectorize:\n"
; for (Instruction *I : Chain) I->dump(); }; } } while (false
)
988 dbgs() << "LSV: Loads to vectorize:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Loads to vectorize:\n"
; for (Instruction *I : Chain) I->dump(); }; } } while (false
)
989 for (Instruction *I : Chain)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Loads to vectorize:\n"
; for (Instruction *I : Chain) I->dump(); }; } } while (false
)
990 I->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Loads to vectorize:\n"
; for (Instruction *I : Chain) I->dump(); }; } } while (false
)
991 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Loads to vectorize:\n"
; for (Instruction *I : Chain) I->dump(); }; } } while (false
)
;
992
993 // getVectorizablePrefix already computed getBoundaryInstrs. The value of
994 // Last may have changed since then, but the value of First won't have. If it
995 // matters, we could compute getBoundaryInstrs only once and reuse it here.
996 BasicBlock::iterator First, Last;
997 std::tie(First, Last) = getBoundaryInstrs(Chain);
998 Builder.SetInsertPoint(&*First);
999
1000 Value *Bitcast =
1001 Builder.CreateBitCast(L0->getPointerOperand(), VecTy->getPointerTo(AS));
1002 // This cast is safe because Builder.CreateLoad always creates a bona fide
1003 // LoadInst.
1004 LoadInst *LI = cast<LoadInst>(Builder.CreateLoad(Bitcast));
1005 propagateMetadata(LI, Chain);
1006 LI->setAlignment(Alignment);
1007
1008 if (VecLoadTy) {
1009 SmallVector<Instruction *, 16> InstrsToErase;
1010
1011 unsigned VecWidth = VecLoadTy->getNumElements();
1012 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1013 for (auto Use : Chain[I]->users()) {
1014 // All users of vector loads are ExtractElement instructions with
1015 // constant indices, otherwise we would have bailed before now.
1016 Instruction *UI = cast<Instruction>(Use);
1017 unsigned Idx = cast<ConstantInt>(UI->getOperand(1))->getZExtValue();
1018 unsigned NewIdx = Idx + I * VecWidth;
1019 Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(NewIdx),
1020 UI->getName());
1021 if (V->getType() != UI->getType())
1022 V = Builder.CreateBitCast(V, UI->getType());
1023
1024 // Replace the old instruction.
1025 UI->replaceAllUsesWith(V);
1026 InstrsToErase.push_back(UI);
1027 }
1028 }
1029
1030 // Bitcast might not be an Instruction, if the value being loaded is a
1031 // constant. In that case, no need to reorder anything.
1032 if (Instruction *BitcastInst = dyn_cast<Instruction>(Bitcast))
1033 reorder(BitcastInst);
1034
1035 for (auto I : InstrsToErase)
1036 I->eraseFromParent();
1037 } else {
1038 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1039 Value *CV = Chain[I];
1040 Value *V =
1041 Builder.CreateExtractElement(LI, Builder.getInt32(I), CV->getName());
1042 if (V->getType() != CV->getType()) {
1043 V = Builder.CreateBitOrPointerCast(V, CV->getType());
1044 }
1045
1046 // Replace the old instruction.
1047 CV->replaceAllUsesWith(V);
1048 }
1049
1050 if (Instruction *BitcastInst = dyn_cast<Instruction>(Bitcast))
1051 reorder(BitcastInst);
1052 }
1053
1054 eraseInstructions(Chain);
1055
1056 ++NumVectorInstructions;
1057 NumScalarsVectorized += Chain.size();
1058 return true;
1059}
1060
1061bool Vectorizer::accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
1062 unsigned Alignment) {
1063 if (Alignment % SzInBytes == 0)
1064 return false;
1065
1066 bool Fast = false;
1067 bool Allows = TTI.allowsMisalignedMemoryAccesses(F.getParent()->getContext(),
1068 SzInBytes * 8, AddressSpace,
1069 Alignment, &Fast);
1070 DEBUG(dbgs() << "LSV: Target said misaligned is allowed? " << Allowsdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Target said misaligned is allowed? "
<< Allows << " and fast? " << Fast <<
"\n";; } } while (false)
1071 << " and fast? " << Fast << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Target said misaligned is allowed? "
<< Allows << " and fast? " << Fast <<
"\n";; } } while (false)
;
1072 return !Allows || !Fast;
1073}