Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoadStoreVectorizer.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-config-compatibility-mode=true -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/lib/Transforms/Vectorize -I /build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn348900/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-command-line-argument -Wno-unknown-warning-option -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/lib/Transforms/Vectorize -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-12-12-042652-12204-1 -x c++ /build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp -faddrsig
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// This pass merges loads/stores to/from sequential memory addresses into vector
11// loads/stores. Although there's nothing GPU-specific in here, this pass is
12// motivated by the microarchitectural quirks of nVidia and AMD GPUs.
13//
14// (For simplicity below we talk about loads only, but everything also applies
15// to stores.)
16//
17// This pass is intended to be run late in the pipeline, after other
18// vectorization opportunities have been exploited. So the assumption here is
19// that immediately following our new vector load we'll need to extract out the
20// individual elements of the load, so we can operate on them individually.
21//
22// On CPUs this transformation is usually not beneficial, because extracting the
23// elements of a vector register is expensive on most architectures. It's
24// usually better just to load each element individually into its own scalar
25// register.
26//
27// However, nVidia and AMD GPUs don't have proper vector registers. Instead, a
28// "vector load" loads directly into a series of scalar registers. In effect,
29// extracting the elements of the vector is free. It's therefore always
30// beneficial to vectorize a sequence of loads on these architectures.
31//
32// Vectorizing (perhaps a better name might be "coalescing") loads can have
33// large performance impacts on GPU kernels, and opportunities for vectorizing
34// are common in GPU code. This pass tries very hard to find such
35// opportunities; its runtime is quadratic in the number of loads in a BB.
36//
37// Some CPU architectures, such as ARM, have instructions that load into
38// multiple scalar registers, similar to a GPU vectorized load. In theory ARM
39// could use this pass (with some modifications), but currently it implements
40// its own pass to do something similar to what we do here.
41
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/MemoryLocation.h"
53#include "llvm/Analysis/OrderedBasicBlock.h"
54#include "llvm/Analysis/ScalarEvolution.h"
55#include "llvm/Analysis/TargetTransformInfo.h"
56#include "llvm/Transforms/Utils/Local.h"
57#include "llvm/Analysis/ValueTracking.h"
58#include "llvm/Analysis/VectorUtils.h"
59#include "llvm/IR/Attributes.h"
60#include "llvm/IR/BasicBlock.h"
61#include "llvm/IR/Constants.h"
62#include "llvm/IR/DataLayout.h"
63#include "llvm/IR/DerivedTypes.h"
64#include "llvm/IR/Dominators.h"
65#include "llvm/IR/Function.h"
66#include "llvm/IR/IRBuilder.h"
67#include "llvm/IR/InstrTypes.h"
68#include "llvm/IR/Instruction.h"
69#include "llvm/IR/Instructions.h"
70#include "llvm/IR/IntrinsicInst.h"
71#include "llvm/IR/Module.h"
72#include "llvm/IR/Type.h"
73#include "llvm/IR/User.h"
74#include "llvm/IR/Value.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/Vectorize.h"
82#include "llvm/Transforms/Vectorize/LoadStoreVectorizer.h"
83#include <algorithm>
84#include <cassert>
85#include <cstdlib>
86#include <tuple>
87#include <utility>
88
89using namespace llvm;
90
91#define DEBUG_TYPE"load-store-vectorizer" "load-store-vectorizer"
92
93STATISTIC(NumVectorInstructions, "Number of vector accesses generated")static llvm::Statistic NumVectorInstructions = {"load-store-vectorizer"
, "NumVectorInstructions", "Number of vector accesses generated"
, {0}, {false}}
;
94STATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized")static llvm::Statistic NumScalarsVectorized = {"load-store-vectorizer"
, "NumScalarsVectorized", "Number of scalar accesses vectorized"
, {0}, {false}}
;
95
96// FIXME: Assuming stack alignment of 4 is always good enough
97static const unsigned StackAdjustedAlignment = 4;
98
99namespace {
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.
108using ChainID = const Value *;
109using InstrList = SmallVector<Instruction *, 8>;
110using InstrListMap = MapVector<ChainID, InstrList>;
111
112class Vectorizer {
113 Function &F;
114 AliasAnalysis &AA;
115 DominatorTree &DT;
116 ScalarEvolution &SE;
117 TargetTransformInfo &TTI;
118 const DataLayout &DL;
119 IRBuilder<> Builder;
120
121public:
122 Vectorizer(Function &F, AliasAnalysis &AA, DominatorTree &DT,
123 ScalarEvolution &SE, TargetTransformInfo &TTI)
124 : F(F), AA(AA), DT(DT), SE(SE), TTI(TTI),
125 DL(F.getParent()->getDataLayout()), Builder(SE.getContext()) {}
126
127 bool run();
128
129private:
130 unsigned getPointerAddressSpace(Value *I);
131
132 unsigned getAlignment(LoadInst *LI) const {
133 unsigned Align = LI->getAlignment();
134 if (Align != 0)
135 return Align;
136
137 return DL.getABITypeAlignment(LI->getType());
138 }
139
140 unsigned getAlignment(StoreInst *SI) const {
141 unsigned Align = SI->getAlignment();
142 if (Align != 0)
143 return Align;
144
145 return DL.getABITypeAlignment(SI->getValueOperand()->getType());
146 }
147
148 static const unsigned MaxDepth = 3;
149
150 bool isConsecutiveAccess(Value *A, Value *B);
151 bool areConsecutivePointers(Value *PtrA, Value *PtrB, const APInt &PtrDelta,
152 unsigned Depth = 0) const;
153 bool lookThroughComplexAddresses(Value *PtrA, Value *PtrB, APInt PtrDelta,
154 unsigned Depth) const;
155 bool lookThroughSelects(Value *PtrA, Value *PtrB, const APInt &PtrDelta,
156 unsigned Depth) const;
157
158 /// After vectorization, reorder the instructions that I depends on
159 /// (the instructions defining its operands), to ensure they dominate I.
160 void reorder(Instruction *I);
161
162 /// Returns the first and the last instructions in Chain.
163 std::pair<BasicBlock::iterator, BasicBlock::iterator>
164 getBoundaryInstrs(ArrayRef<Instruction *> Chain);
165
166 /// Erases the original instructions after vectorizing.
167 void eraseInstructions(ArrayRef<Instruction *> Chain);
168
169 /// "Legalize" the vector type that would be produced by combining \p
170 /// ElementSizeBits elements in \p Chain. Break into two pieces such that the
171 /// total size of each piece is 1, 2 or a multiple of 4 bytes. \p Chain is
172 /// expected to have more than 4 elements.
173 std::pair<ArrayRef<Instruction *>, ArrayRef<Instruction *>>
174 splitOddVectorElts(ArrayRef<Instruction *> Chain, unsigned ElementSizeBits);
175
176 /// Finds the largest prefix of Chain that's vectorizable, checking for
177 /// intervening instructions which may affect the memory accessed by the
178 /// instructions within Chain.
179 ///
180 /// The elements of \p Chain must be all loads or all stores and must be in
181 /// address order.
182 ArrayRef<Instruction *> getVectorizablePrefix(ArrayRef<Instruction *> Chain);
183
184 /// Collects load and store instructions to vectorize.
185 std::pair<InstrListMap, InstrListMap> collectInstructions(BasicBlock *BB);
186
187 /// Processes the collected instructions, the \p Map. The values of \p Map
188 /// should be all loads or all stores.
189 bool vectorizeChains(InstrListMap &Map);
190
191 /// Finds the load/stores to consecutive memory addresses and vectorizes them.
192 bool vectorizeInstructions(ArrayRef<Instruction *> Instrs);
193
194 /// Vectorizes the load instructions in Chain.
195 bool
196 vectorizeLoadChain(ArrayRef<Instruction *> Chain,
197 SmallPtrSet<Instruction *, 16> *InstructionsProcessed);
198
199 /// Vectorizes the store instructions in Chain.
200 bool
201 vectorizeStoreChain(ArrayRef<Instruction *> Chain,
202 SmallPtrSet<Instruction *, 16> *InstructionsProcessed);
203
204 /// Check if this load/store access is misaligned accesses.
205 bool accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
206 unsigned Alignment);
207};
208
209class LoadStoreVectorizerLegacyPass : public FunctionPass {
210public:
211 static char ID;
212
213 LoadStoreVectorizerLegacyPass() : FunctionPass(ID) {
214 initializeLoadStoreVectorizerLegacyPassPass(*PassRegistry::getPassRegistry());
215 }
216
217 bool runOnFunction(Function &F) override;
218
219 StringRef getPassName() const override {
220 return "GPU Load and Store Vectorizer";
221 }
222
223 void getAnalysisUsage(AnalysisUsage &AU) const override {
224 AU.addRequired<AAResultsWrapperPass>();
225 AU.addRequired<ScalarEvolutionWrapperPass>();
226 AU.addRequired<DominatorTreeWrapperPass>();
227 AU.addRequired<TargetTransformInfoWrapperPass>();
228 AU.setPreservesCFG();
229 }
230};
231
232} // end anonymous namespace
233
234char LoadStoreVectorizerLegacyPass::ID = 0;
235
236INITIALIZE_PASS_BEGIN(LoadStoreVectorizerLegacyPass, DEBUG_TYPE,static void *initializeLoadStoreVectorizerLegacyPassPassOnce(
PassRegistry &Registry) {
237 "Vectorize load and Store instructions", false, false)static void *initializeLoadStoreVectorizerLegacyPassPassOnce(
PassRegistry &Registry) {
238INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)initializeSCEVAAWrapperPassPass(Registry);
239INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
240INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
241INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
242INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
243INITIALIZE_PASS_END(LoadStoreVectorizerLegacyPass, DEBUG_TYPE,PassInfo *PI = new PassInfo( "Vectorize load and store instructions"
, "load-store-vectorizer", &LoadStoreVectorizerLegacyPass
::ID, PassInfo::NormalCtor_t(callDefaultCtor<LoadStoreVectorizerLegacyPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeLoadStoreVectorizerLegacyPassPassFlag
; void llvm::initializeLoadStoreVectorizerLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeLoadStoreVectorizerLegacyPassPassFlag
, initializeLoadStoreVectorizerLegacyPassPassOnce, std::ref(Registry
)); }
244 "Vectorize load and store instructions", false, false)PassInfo *PI = new PassInfo( "Vectorize load and store instructions"
, "load-store-vectorizer", &LoadStoreVectorizerLegacyPass
::ID, PassInfo::NormalCtor_t(callDefaultCtor<LoadStoreVectorizerLegacyPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeLoadStoreVectorizerLegacyPassPassFlag
; void llvm::initializeLoadStoreVectorizerLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeLoadStoreVectorizerLegacyPassPassFlag
, initializeLoadStoreVectorizerLegacyPassPassOnce, std::ref(Registry
)); }
245
246Pass *llvm::createLoadStoreVectorizerPass() {
247 return new LoadStoreVectorizerLegacyPass();
248}
249
250bool LoadStoreVectorizerLegacyPass::runOnFunction(Function &F) {
251 // Don't vectorize when the attribute NoImplicitFloat is used.
252 if (skipFunction(F) || F.hasFnAttribute(Attribute::NoImplicitFloat))
253 return false;
254
255 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
256 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
257 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
258 TargetTransformInfo &TTI =
259 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
260
261 Vectorizer V(F, AA, DT, SE, TTI);
262 return V.run();
263}
264
265PreservedAnalyses LoadStoreVectorizerPass::run(Function &F, FunctionAnalysisManager &AM) {
266 // Don't vectorize when the attribute NoImplicitFloat is used.
267 if (F.hasFnAttribute(Attribute::NoImplicitFloat))
268 return PreservedAnalyses::all();
269
270 AliasAnalysis &AA = AM.getResult<AAManager>(F);
271 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
272 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
273 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
274
275 Vectorizer V(F, AA, DT, SE, TTI);
276 bool Changed = V.run();
277 PreservedAnalyses PA;
278 PA.preserveSet<CFGAnalyses>();
279 return Changed ? PA : PreservedAnalyses::all();
280}
281
282// The real propagateMetadata expects a SmallVector<Value*>, but we deal in
283// vectors of Instructions.
284static void propagateMetadata(Instruction *I, ArrayRef<Instruction *> IL) {
285 SmallVector<Value *, 8> VL(IL.begin(), IL.end());
286 propagateMetadata(I, VL);
287}
288
289// Vectorizer Implementation
290bool Vectorizer::run() {
291 bool Changed = false;
292
293 // Scan the blocks in the function in post order.
294 for (BasicBlock *BB : post_order(&F)) {
295 InstrListMap LoadRefs, StoreRefs;
296 std::tie(LoadRefs, StoreRefs) = collectInstructions(BB);
297 Changed |= vectorizeChains(LoadRefs);
298 Changed |= vectorizeChains(StoreRefs);
299 }
300
301 return Changed;
302}
303
304unsigned Vectorizer::getPointerAddressSpace(Value *I) {
305 if (LoadInst *L = dyn_cast<LoadInst>(I))
306 return L->getPointerAddressSpace();
307 if (StoreInst *S = dyn_cast<StoreInst>(I))
308 return S->getPointerAddressSpace();
309 return -1;
310}
311
312// FIXME: Merge with llvm::isConsecutiveAccess
313bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) {
314 Value *PtrA = getLoadStorePointerOperand(A);
315 Value *PtrB = getLoadStorePointerOperand(B);
316 unsigned ASA = getPointerAddressSpace(A);
317 unsigned ASB = getPointerAddressSpace(B);
318
319 // Check that the address spaces match and that the pointers are valid.
320 if (!PtrA || !PtrB || (ASA != ASB))
321 return false;
322
323 // Make sure that A and B are different pointers of the same size type.
324 Type *PtrATy = PtrA->getType()->getPointerElementType();
325 Type *PtrBTy = PtrB->getType()->getPointerElementType();
326 if (PtrA == PtrB ||
327 PtrATy->isVectorTy() != PtrBTy->isVectorTy() ||
328 DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) ||
329 DL.getTypeStoreSize(PtrATy->getScalarType()) !=
330 DL.getTypeStoreSize(PtrBTy->getScalarType()))
331 return false;
332
333 unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
334 APInt Size(PtrBitWidth, DL.getTypeStoreSize(PtrATy));
335
336 return areConsecutivePointers(PtrA, PtrB, Size);
337}
338
339bool Vectorizer::areConsecutivePointers(Value *PtrA, Value *PtrB,
340 const APInt &PtrDelta,
341 unsigned Depth) const {
342 unsigned PtrBitWidth = DL.getPointerTypeSizeInBits(PtrA->getType());
343 APInt OffsetA(PtrBitWidth, 0);
344 APInt OffsetB(PtrBitWidth, 0);
345 PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
346 PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
347
348 APInt OffsetDelta = OffsetB - OffsetA;
349
350 // Check if they are based on the same pointer. That makes the offsets
351 // sufficient.
352 if (PtrA == PtrB)
353 return OffsetDelta == PtrDelta;
354
355 // Compute the necessary base pointer delta to have the necessary final delta
356 // equal to the pointer delta requested.
357 APInt BaseDelta = PtrDelta - OffsetDelta;
358
359 // Compute the distance with SCEV between the base pointers.
360 const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
361 const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
362 const SCEV *C = SE.getConstant(BaseDelta);
363 const SCEV *X = SE.getAddExpr(PtrSCEVA, C);
364 if (X == PtrSCEVB)
365 return true;
366
367 // The above check will not catch the cases where one of the pointers is
368 // factorized but the other one is not, such as (C + (S * (A + B))) vs
369 // (AS + BS). Get the minus scev. That will allow re-combining the expresions
370 // and getting the simplified difference.
371 const SCEV *Dist = SE.getMinusSCEV(PtrSCEVB, PtrSCEVA);
372 if (C == Dist)
373 return true;
374
375 // Sometimes even this doesn't work, because SCEV can't always see through
376 // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking
377 // things the hard way.
378 return lookThroughComplexAddresses(PtrA, PtrB, BaseDelta, Depth);
379}
380
381bool Vectorizer::lookThroughComplexAddresses(Value *PtrA, Value *PtrB,
382 APInt PtrDelta,
383 unsigned Depth) const {
384 auto *GEPA = dyn_cast<GetElementPtrInst>(PtrA);
385 auto *GEPB = dyn_cast<GetElementPtrInst>(PtrB);
386 if (!GEPA || !GEPB)
387 return lookThroughSelects(PtrA, PtrB, PtrDelta, Depth);
388
389 // Look through GEPs after checking they're the same except for the last
390 // index.
391 if (GEPA->getNumOperands() != GEPB->getNumOperands() ||
392 GEPA->getPointerOperand() != GEPB->getPointerOperand())
393 return false;
394 gep_type_iterator GTIA = gep_type_begin(GEPA);
395 gep_type_iterator GTIB = gep_type_begin(GEPB);
396 for (unsigned I = 0, E = GEPA->getNumIndices() - 1; I < E; ++I) {
397 if (GTIA.getOperand() != GTIB.getOperand())
398 return false;
399 ++GTIA;
400 ++GTIB;
401 }
402
403 Instruction *OpA = dyn_cast<Instruction>(GTIA.getOperand());
404 Instruction *OpB = dyn_cast<Instruction>(GTIB.getOperand());
405 if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() ||
406 OpA->getType() != OpB->getType())
407 return false;
408
409 if (PtrDelta.isNegative()) {
410 if (PtrDelta.isMinSignedValue())
411 return false;
412 PtrDelta.negate();
413 std::swap(OpA, OpB);
414 }
415 uint64_t Stride = DL.getTypeAllocSize(GTIA.getIndexedType());
416 if (PtrDelta.urem(Stride) != 0)
417 return false;
418 unsigned IdxBitWidth = OpA->getType()->getScalarSizeInBits();
419 APInt IdxDiff = PtrDelta.udiv(Stride).zextOrSelf(IdxBitWidth);
420
421 // Only look through a ZExt/SExt.
422 if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA))
423 return false;
424
425 bool Signed = isa<SExtInst>(OpA);
426
427 // At this point A could be a function parameter, i.e. not an instruction
428 Value *ValA = OpA->getOperand(0);
429 OpB = dyn_cast<Instruction>(OpB->getOperand(0));
430 if (!OpB || ValA->getType() != OpB->getType())
431 return false;
432
433 // Now we need to prove that adding IdxDiff to ValA won't overflow.
434 bool Safe = false;
435 // First attempt: if OpB is an add with NSW/NUW, and OpB is IdxDiff added to
436 // ValA, we're okay.
437 if (OpB->getOpcode() == Instruction::Add &&
438 isa<ConstantInt>(OpB->getOperand(1)) &&
439 IdxDiff.sle(cast<ConstantInt>(OpB->getOperand(1))->getSExtValue())) {
440 if (Signed)
441 Safe = cast<BinaryOperator>(OpB)->hasNoSignedWrap();
442 else
443 Safe = cast<BinaryOperator>(OpB)->hasNoUnsignedWrap();
444 }
445
446 unsigned BitWidth = ValA->getType()->getScalarSizeInBits();
447
448 // Second attempt:
449 // If all set bits of IdxDiff or any higher order bit other than the sign bit
450 // are known to be zero in ValA, we can add Diff to it while guaranteeing no
451 // overflow of any sort.
452 if (!Safe) {
453 OpA = dyn_cast<Instruction>(ValA);
454 if (!OpA)
455 return false;
456 KnownBits Known(BitWidth);
457 computeKnownBits(OpA, Known, DL, 0, nullptr, OpA, &DT);
458 APInt BitsAllowedToBeSet = Known.Zero.zext(IdxDiff.getBitWidth());
459 if (Signed)
460 BitsAllowedToBeSet.clearBit(BitWidth - 1);
461 if (BitsAllowedToBeSet.ult(IdxDiff))
462 return false;
463 }
464
465 const SCEV *OffsetSCEVA = SE.getSCEV(ValA);
466 const SCEV *OffsetSCEVB = SE.getSCEV(OpB);
467 const SCEV *C = SE.getConstant(IdxDiff.trunc(BitWidth));
468 const SCEV *X = SE.getAddExpr(OffsetSCEVA, C);
469 return X == OffsetSCEVB;
470}
471
472bool Vectorizer::lookThroughSelects(Value *PtrA, Value *PtrB,
473 const APInt &PtrDelta,
474 unsigned Depth) const {
475 if (Depth++ == MaxDepth)
476 return false;
477
478 if (auto *SelectA = dyn_cast<SelectInst>(PtrA)) {
479 if (auto *SelectB = dyn_cast<SelectInst>(PtrB)) {
480 return SelectA->getCondition() == SelectB->getCondition() &&
481 areConsecutivePointers(SelectA->getTrueValue(),
482 SelectB->getTrueValue(), PtrDelta, Depth) &&
483 areConsecutivePointers(SelectA->getFalseValue(),
484 SelectB->getFalseValue(), PtrDelta, Depth);
485 }
486 }
487 return false;
488}
489
490void Vectorizer::reorder(Instruction *I) {
491 OrderedBasicBlock OBB(I->getParent());
492 SmallPtrSet<Instruction *, 16> InstructionsToMove;
493 SmallVector<Instruction *, 16> Worklist;
494
495 Worklist.push_back(I);
496 while (!Worklist.empty()) {
497 Instruction *IW = Worklist.pop_back_val();
498 int NumOperands = IW->getNumOperands();
499 for (int i = 0; i < NumOperands; i++) {
500 Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i));
501 if (!IM || IM->getOpcode() == Instruction::PHI)
502 continue;
503
504 // If IM is in another BB, no need to move it, because this pass only
505 // vectorizes instructions within one BB.
506 if (IM->getParent() != I->getParent())
507 continue;
508
509 if (!OBB.dominates(IM, I)) {
510 InstructionsToMove.insert(IM);
511 Worklist.push_back(IM);
512 }
513 }
514 }
515
516 // All instructions to move should follow I. Start from I, not from begin().
517 for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;
518 ++BBI) {
519 if (!InstructionsToMove.count(&*BBI))
520 continue;
521 Instruction *IM = &*BBI;
522 --BBI;
523 IM->removeFromParent();
524 IM->insertBefore(I);
525 }
526}
527
528std::pair<BasicBlock::iterator, BasicBlock::iterator>
529Vectorizer::getBoundaryInstrs(ArrayRef<Instruction *> Chain) {
530 Instruction *C0 = Chain[0];
531 BasicBlock::iterator FirstInstr = C0->getIterator();
532 BasicBlock::iterator LastInstr = C0->getIterator();
533
534 BasicBlock *BB = C0->getParent();
535 unsigned NumFound = 0;
536 for (Instruction &I : *BB) {
537 if (!is_contained(Chain, &I))
538 continue;
539
540 ++NumFound;
541 if (NumFound == 1) {
542 FirstInstr = I.getIterator();
543 }
544 if (NumFound == Chain.size()) {
545 LastInstr = I.getIterator();
546 break;
547 }
548 }
549
550 // Range is [first, last).
551 return std::make_pair(FirstInstr, ++LastInstr);
552}
553
554void Vectorizer::eraseInstructions(ArrayRef<Instruction *> Chain) {
555 SmallVector<Instruction *, 16> Instrs;
556 for (Instruction *I : Chain) {
557 Value *PtrOperand = getLoadStorePointerOperand(I);
558 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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 558, __PRETTY_FUNCTION__))
;
559 Instrs.push_back(I);
560 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(PtrOperand))
561 Instrs.push_back(GEP);
562 }
563
564 // Erase instructions.
565 for (Instruction *I : Instrs)
566 if (I->use_empty())
567 I->eraseFromParent();
568}
569
570std::pair<ArrayRef<Instruction *>, ArrayRef<Instruction *>>
571Vectorizer::splitOddVectorElts(ArrayRef<Instruction *> Chain,
572 unsigned ElementSizeBits) {
573 unsigned ElementSizeBytes = ElementSizeBits / 8;
574 unsigned SizeBytes = ElementSizeBytes * Chain.size();
575 unsigned NumLeft = (SizeBytes - (SizeBytes % 4)) / ElementSizeBytes;
576 if (NumLeft == Chain.size()) {
577 if ((NumLeft & 1) == 0)
578 NumLeft /= 2; // Split even in half
579 else
580 --NumLeft; // Split off last element
581 } else if (NumLeft == 0)
582 NumLeft = 1;
583 return std::make_pair(Chain.slice(0, NumLeft), Chain.slice(NumLeft));
584}
585
586ArrayRef<Instruction *>
587Vectorizer::getVectorizablePrefix(ArrayRef<Instruction *> Chain) {
588 // These are in BB order, unlike Chain, which is in address order.
589 SmallVector<Instruction *, 16> MemoryInstrs;
590 SmallVector<Instruction *, 16> ChainInstrs;
591
592 bool IsLoadChain = isa<LoadInst>(Chain[0]);
593 LLVM_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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
594 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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
595 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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
596 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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
597 "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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
598 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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
599 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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
600 "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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
601 }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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
602 })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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 597, __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.\""
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 600, __PRETTY_FUNCTION__)); } }; } } while (false)
;
603
604 for (Instruction &I : make_range(getBoundaryInstrs(Chain))) {
605 if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
606 if (!is_contained(Chain, &I))
607 MemoryInstrs.push_back(&I);
608 else
609 ChainInstrs.push_back(&I);
610 } else if (isa<IntrinsicInst>(&I) &&
611 cast<IntrinsicInst>(&I)->getIntrinsicID() ==
612 Intrinsic::sideeffect) {
613 // Ignore llvm.sideeffect calls.
614 } else if (IsLoadChain && (I.mayWriteToMemory() || I.mayThrow())) {
615 LLVM_DEBUG(dbgs() << "LSV: Found may-write/throw operation: " << Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Found may-write/throw operation: "
<< I << '\n'; } } while (false)
616 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Found may-write/throw operation: "
<< I << '\n'; } } while (false)
;
617 break;
618 } else if (!IsLoadChain && (I.mayReadOrWriteMemory() || I.mayThrow())) {
619 LLVM_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)
620 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Found may-read/write/throw operation: "
<< I << '\n'; } } while (false)
;
621 break;
622 }
623 }
624
625 OrderedBasicBlock OBB(Chain[0]->getParent());
626
627 // Loop until we find an instruction in ChainInstrs that we can't vectorize.
628 unsigned ChainInstrIdx = 0;
629 Instruction *BarrierMemoryInstr = nullptr;
630
631 for (unsigned E = ChainInstrs.size(); ChainInstrIdx < E; ++ChainInstrIdx) {
632 Instruction *ChainInstr = ChainInstrs[ChainInstrIdx];
633
634 // If a barrier memory instruction was found, chain instructions that follow
635 // will not be added to the valid prefix.
636 if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, ChainInstr))
637 break;
638
639 // Check (in BB order) if any instruction prevents ChainInstr from being
640 // vectorized. Find and store the first such "conflicting" instruction.
641 for (Instruction *MemInstr : MemoryInstrs) {
642 // If a barrier memory instruction was found, do not check past it.
643 if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, MemInstr))
644 break;
645
646 auto *MemLoad = dyn_cast<LoadInst>(MemInstr);
647 auto *ChainLoad = dyn_cast<LoadInst>(ChainInstr);
648 if (MemLoad && ChainLoad)
649 continue;
650
651 // We can ignore the alias if the we have a load store pair and the load
652 // is known to be invariant. The load cannot be clobbered by the store.
653 auto IsInvariantLoad = [](const LoadInst *LI) -> bool {
654 return LI->getMetadata(LLVMContext::MD_invariant_load);
655 };
656
657 // We can ignore the alias as long as the load comes before the store,
658 // because that means we won't be moving the load past the store to
659 // vectorize it (the vectorized load is inserted at the location of the
660 // first load in the chain).
661 if (isa<StoreInst>(MemInstr) && ChainLoad &&
662 (IsInvariantLoad(ChainLoad) || OBB.dominates(ChainLoad, MemInstr)))
663 continue;
664
665 // Same case, but in reverse.
666 if (MemLoad && isa<StoreInst>(ChainInstr) &&
667 (IsInvariantLoad(MemLoad) || OBB.dominates(MemLoad, ChainInstr)))
668 continue;
669
670 if (!AA.isNoAlias(MemoryLocation::get(MemInstr),
671 MemoryLocation::get(ChainInstr))) {
672 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
673 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' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
674 " 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' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
675 << " " << *MemInstr << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
676 << " " << *getLoadStorePointerOperand(MemInstr) << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
677 << " 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' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
678 << " " << *ChainInstr << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
679 << " " << *getLoadStorePointerOperand(ChainInstr) << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
680 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Found alias:\n"
" Aliasing instruction and pointer:\n" << " " <<
*MemInstr << '\n' << " " << *getLoadStorePointerOperand
(MemInstr) << '\n' << " Aliased instruction and pointer:\n"
<< " " << *ChainInstr << '\n' << " "
<< *getLoadStorePointerOperand(ChainInstr) << '\n'
; }; } } while (false)
;
681 // Save this aliasing memory instruction as a barrier, but allow other
682 // instructions that precede the barrier to be vectorized with this one.
683 BarrierMemoryInstr = MemInstr;
684 break;
685 }
686 }
687 // Continue the search only for store chains, since vectorizing stores that
688 // precede an aliasing load is valid. Conversely, vectorizing loads is valid
689 // up to an aliasing store, but should not pull loads from further down in
690 // the basic block.
691 if (IsLoadChain && BarrierMemoryInstr) {
692 // The BarrierMemoryInstr is a store that precedes ChainInstr.
693 assert(OBB.dominates(BarrierMemoryInstr, ChainInstr))((OBB.dominates(BarrierMemoryInstr, ChainInstr)) ? static_cast
<void> (0) : __assert_fail ("OBB.dominates(BarrierMemoryInstr, ChainInstr)"
, "/build/llvm-toolchain-snapshot-8~svn348900/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp"
, 693, __PRETTY_FUNCTION__))
;
694 break;
695 }
696 }
697
698 // Find the largest prefix of Chain whose elements are all in
699 // ChainInstrs[0, ChainInstrIdx). This is the largest vectorizable prefix of
700 // Chain. (Recall that Chain is in address order, but ChainInstrs is in BB
701 // order.)
702 SmallPtrSet<Instruction *, 8> VectorizableChainInstrs(
703 ChainInstrs.begin(), ChainInstrs.begin() + ChainInstrIdx);
704 unsigned ChainIdx = 0;
705 for (unsigned ChainLen = Chain.size(); ChainIdx < ChainLen; ++ChainIdx) {
706 if (!VectorizableChainInstrs.count(Chain[ChainIdx]))
707 break;
708 }
709 return Chain.slice(0, ChainIdx);
710}
711
712static ChainID getChainID(const Value *Ptr, const DataLayout &DL) {
713 const Value *ObjPtr = GetUnderlyingObject(Ptr, DL);
714 if (const auto *Sel = dyn_cast<SelectInst>(ObjPtr)) {
715 // The select's themselves are distinct instructions even if they share the
716 // same condition and evaluate to consecutive pointers for true and false
717 // values of the condition. Therefore using the select's themselves for
718 // grouping instructions would put consecutive accesses into different lists
719 // and they won't be even checked for being consecutive, and won't be
720 // vectorized.
721 return Sel->getCondition();
722 }
723 return ObjPtr;
724}
725
726std::pair<InstrListMap, InstrListMap>
727Vectorizer::collectInstructions(BasicBlock *BB) {
728 InstrListMap LoadRefs;
729 InstrListMap StoreRefs;
730
731 for (Instruction &I : *BB) {
732 if (!I.mayReadOrWriteMemory())
733 continue;
734
735 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
736 if (!LI->isSimple())
737 continue;
738
739 // Skip if it's not legal.
740 if (!TTI.isLegalToVectorizeLoad(LI))
741 continue;
742
743 Type *Ty = LI->getType();
744 if (!VectorType::isValidElementType(Ty->getScalarType()))
745 continue;
746
747 // Skip weird non-byte sizes. They probably aren't worth the effort of
748 // handling correctly.
749 unsigned TySize = DL.getTypeSizeInBits(Ty);
750 if ((TySize % 8) != 0)
751 continue;
752
753 // Skip vectors of pointers. The vectorizeLoadChain/vectorizeStoreChain
754 // functions are currently using an integer type for the vectorized
755 // load/store, and does not support casting between the integer type and a
756 // vector of pointers (e.g. i64 to <2 x i16*>)
757 if (Ty->isVectorTy() && Ty->isPtrOrPtrVectorTy())
758 continue;
759
760 Value *Ptr = LI->getPointerOperand();
761 unsigned AS = Ptr->getType()->getPointerAddressSpace();
762 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
763
764 unsigned VF = VecRegSize / TySize;
765 VectorType *VecTy = dyn_cast<VectorType>(Ty);
766
767 // No point in looking at these if they're too big to vectorize.
768 if (TySize > VecRegSize / 2 ||
769 (VecTy && TTI.getLoadVectorFactor(VF, TySize, TySize / 8, VecTy) == 0))
770 continue;
771
772 // Make sure all the users of a vector are constant-index extracts.
773 if (isa<VectorType>(Ty) && !llvm::all_of(LI->users(), [](const User *U) {
774 const ExtractElementInst *EEI = dyn_cast<ExtractElementInst>(U);
775 return EEI && isa<ConstantInt>(EEI->getOperand(1));
776 }))
777 continue;
778
779 // Save the load locations.
780 const ChainID ID = getChainID(Ptr, DL);
781 LoadRefs[ID].push_back(LI);
782 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
783 if (!SI->isSimple())
784 continue;
785
786 // Skip if it's not legal.
787 if (!TTI.isLegalToVectorizeStore(SI))
788 continue;
789
790 Type *Ty = SI->getValueOperand()->getType();
791 if (!VectorType::isValidElementType(Ty->getScalarType()))
792 continue;
793
794 // Skip vectors of pointers. The vectorizeLoadChain/vectorizeStoreChain
795 // functions are currently using an integer type for the vectorized
796 // load/store, and does not support casting between the integer type and a
797 // vector of pointers (e.g. i64 to <2 x i16*>)
798 if (Ty->isVectorTy() && Ty->isPtrOrPtrVectorTy())
799 continue;
800
801 // Skip weird non-byte sizes. They probably aren't worth the effort of
802 // handling correctly.
803 unsigned TySize = DL.getTypeSizeInBits(Ty);
804 if ((TySize % 8) != 0)
805 continue;
806
807 Value *Ptr = SI->getPointerOperand();
808 unsigned AS = Ptr->getType()->getPointerAddressSpace();
809 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
810
811 unsigned VF = VecRegSize / TySize;
812 VectorType *VecTy = dyn_cast<VectorType>(Ty);
813
814 // No point in looking at these if they're too big to vectorize.
815 if (TySize > VecRegSize / 2 ||
816 (VecTy && TTI.getStoreVectorFactor(VF, TySize, TySize / 8, VecTy) == 0))
817 continue;
818
819 if (isa<VectorType>(Ty) && !llvm::all_of(SI->users(), [](const User *U) {
820 const ExtractElementInst *EEI = dyn_cast<ExtractElementInst>(U);
821 return EEI && isa<ConstantInt>(EEI->getOperand(1));
822 }))
823 continue;
824
825 // Save store location.
826 const ChainID ID = getChainID(Ptr, DL);
827 StoreRefs[ID].push_back(SI);
828 }
829 }
830
831 return {LoadRefs, StoreRefs};
832}
833
834bool Vectorizer::vectorizeChains(InstrListMap &Map) {
835 bool Changed = false;
836
837 for (const std::pair<ChainID, InstrList> &Chain : Map) {
838 unsigned Size = Chain.second.size();
839 if (Size < 2)
1
Assuming 'Size' is >= 2
2
Taking false branch
840 continue;
841
842 LLVM_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)
;
3
Assuming 'DebugFlag' is 0
4
Loop condition is false. Exiting loop
843
844 // Process the stores in chunks of 64.
845 for (unsigned CI = 0, CE = Size; CI < CE; CI += 64) {
5
Loop condition is true. Entering loop body
846 unsigned Len = std::min<unsigned>(CE - CI, 64);
847 ArrayRef<Instruction *> Chunk(&Chain.second[CI], Len);
848 Changed |= vectorizeInstructions(Chunk);
6
Calling 'Vectorizer::vectorizeInstructions'
849 }
850 }
851
852 return Changed;
853}
854
855bool Vectorizer::vectorizeInstructions(ArrayRef<Instruction *> Instrs) {
856 LLVM_DEBUG(dbgs() << "LSV: Vectorizing " << Instrs.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Vectorizing "
<< Instrs.size() << " instructions.\n"; } } while
(false)
7
Assuming 'DebugFlag' is 0
8
Loop condition is false. Exiting loop
857 << " instructions.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { dbgs() << "LSV: Vectorizing "
<< Instrs.size() << " instructions.\n"; } } while
(false)
;
858 SmallVector<int, 16> Heads, Tails;
859 int ConsecutiveChain[64];
860
861 // Do a quadratic search on all of the given loads/stores and find all of the
862 // pairs of loads/stores that follow each other.
863 for (int i = 0, e = Instrs.size(); i < e; ++i) {
9
Assuming 'i' is >= 'e'
10
Loop condition is false. Execution continues on line 884
864 ConsecutiveChain[i] = -1;
865 for (int j = e - 1; j >= 0; --j) {
866 if (i == j)
867 continue;
868
869 if (isConsecutiveAccess(Instrs[i], Instrs[j])) {
870 if (ConsecutiveChain[i] != -1) {
871 int CurDistance = std::abs(ConsecutiveChain[i] - i);
872 int NewDistance = std::abs(ConsecutiveChain[i] - j);
873 if (j < i || NewDistance > CurDistance)
874 continue; // Should not insert.
875 }
876
877 Tails.push_back(j);
878 Heads.push_back(i);
879 ConsecutiveChain[i] = j;
880 }
881 }
882 }
883
884 bool Changed = false;
885 SmallPtrSet<Instruction *, 16> InstructionsProcessed;
886
887 for (int Head : Heads) {
11
Assuming '__begin1' is not equal to '__end1'
888 if (InstructionsProcessed.count(Instrs[Head]))
12
Assuming the condition is false
13
Taking false branch
889 continue;
890 bool LongerChainExists = false;
891 for (unsigned TIt = 0; TIt < Tails.size(); TIt++)
14
Assuming the condition is false
15
Loop condition is false. Execution continues on line 897
892 if (Head == Tails[TIt] &&
893 !InstructionsProcessed.count(Instrs[Heads[TIt]])) {
894 LongerChainExists = true;
895 break;
896 }
897 if (LongerChainExists)
16
Taking false branch
898 continue;
899
900 // We found an instr that starts a chain. Now follow the chain and try to
901 // vectorize it.
902 SmallVector<Instruction *, 16> Operands;
903 int I = Head;
904 while (I != -1 && (is_contained(Tails, I) || is_contained(Heads, I))) {
17
Assuming the condition is false
905 if (InstructionsProcessed.count(Instrs[I]))
906 break;
907
908 Operands.push_back(Instrs[I]);
909 I = ConsecutiveChain[I];
910 }
911
912 bool Vectorized = false;
913 if (isa<LoadInst>(*Operands.begin()))
18
Taking true branch
914 Vectorized = vectorizeLoadChain(Operands, &InstructionsProcessed);
19
Calling 'Vectorizer::vectorizeLoadChain'
915 else
916 Vectorized = vectorizeStoreChain(Operands, &InstructionsProcessed);
917
918 Changed |= Vectorized;
919 }
920
921 return Changed;
922}
923
924bool Vectorizer::vectorizeStoreChain(
925 ArrayRef<Instruction *> Chain,
926 SmallPtrSet<Instruction *, 16> *InstructionsProcessed) {
927 StoreInst *S0 = cast<StoreInst>(Chain[0]);
928
929 // If the vector has an int element, default to int for the whole store.
930 Type *StoreTy;
931 for (Instruction *I : Chain) {
932 StoreTy = cast<StoreInst>(I)->getValueOperand()->getType();
933 if (StoreTy->isIntOrIntVectorTy())
934 break;
935
936 if (StoreTy->isPtrOrPtrVectorTy()) {
937 StoreTy = Type::getIntNTy(F.getParent()->getContext(),
938 DL.getTypeSizeInBits(StoreTy));
939 break;
940 }
941 }
942
943 unsigned Sz = DL.getTypeSizeInBits(StoreTy);
944 unsigned AS = S0->getPointerAddressSpace();
945 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
946 unsigned VF = VecRegSize / Sz;
947 unsigned ChainSize = Chain.size();
948 unsigned Alignment = getAlignment(S0);
949
950 if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
951 InstructionsProcessed->insert(Chain.begin(), Chain.end());
952 return false;
953 }
954
955 ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain);
956 if (NewChain.empty()) {
957 // No vectorization possible.
958 InstructionsProcessed->insert(Chain.begin(), Chain.end());
959 return false;
960 }
961 if (NewChain.size() == 1) {
962 // Failed after the first instruction. Discard it and try the smaller chain.
963 InstructionsProcessed->insert(NewChain.front());
964 return false;
965 }
966
967 // Update Chain to the valid vectorizable subchain.
968 Chain = NewChain;
969 ChainSize = Chain.size();
970
971 // Check if it's legal to vectorize this chain. If not, split the chain and
972 // try again.
973 unsigned EltSzInBytes = Sz / 8;
974 unsigned SzInBytes = EltSzInBytes * ChainSize;
975
976 VectorType *VecTy;
977 VectorType *VecStoreTy = dyn_cast<VectorType>(StoreTy);
978 if (VecStoreTy)
979 VecTy = VectorType::get(StoreTy->getScalarType(),
980 Chain.size() * VecStoreTy->getNumElements());
981 else
982 VecTy = VectorType::get(StoreTy, Chain.size());
983
984 // If it's more than the max vector size or the target has a better
985 // vector factor, break it into two pieces.
986 unsigned TargetVF = TTI.getStoreVectorFactor(VF, Sz, SzInBytes, VecTy);
987 if (ChainSize > VF || (VF != TargetVF && TargetVF < ChainSize)) {
988 LLVM_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)
989 " 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)
;
990 return vectorizeStoreChain(Chain.slice(0, TargetVF),
991 InstructionsProcessed) |
992 vectorizeStoreChain(Chain.slice(TargetVF), InstructionsProcessed);
993 }
994
995 LLVM_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)
996 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)
997 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)
998 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)
999 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Stores to vectorize:\n"
; for (Instruction *I : Chain) dbgs() << " " << *
I << "\n"; }; } } while (false)
;
1000
1001 // We won't try again to vectorize the elements of the chain, regardless of
1002 // whether we succeed below.
1003 InstructionsProcessed->insert(Chain.begin(), Chain.end());
1004
1005 // If the store is going to be misaligned, don't vectorize it.
1006 if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
1007 if (S0->getPointerAddressSpace() != DL.getAllocaAddrSpace()) {
1008 auto Chains = splitOddVectorElts(Chain, Sz);
1009 return vectorizeStoreChain(Chains.first, InstructionsProcessed) |
1010 vectorizeStoreChain(Chains.second, InstructionsProcessed);
1011 }
1012
1013 unsigned NewAlign = getOrEnforceKnownAlignment(S0->getPointerOperand(),
1014 StackAdjustedAlignment,
1015 DL, S0, nullptr, &DT);
1016 if (NewAlign != 0)
1017 Alignment = NewAlign;
1018 }
1019
1020 if (!TTI.isLegalToVectorizeStoreChain(SzInBytes, Alignment, AS)) {
1021 auto Chains = splitOddVectorElts(Chain, Sz);
1022 return vectorizeStoreChain(Chains.first, InstructionsProcessed) |
1023 vectorizeStoreChain(Chains.second, InstructionsProcessed);
1024 }
1025
1026 BasicBlock::iterator First, Last;
1027 std::tie(First, Last) = getBoundaryInstrs(Chain);
1028 Builder.SetInsertPoint(&*Last);
1029
1030 Value *Vec = UndefValue::get(VecTy);
1031
1032 if (VecStoreTy) {
1033 unsigned VecWidth = VecStoreTy->getNumElements();
1034 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1035 StoreInst *Store = cast<StoreInst>(Chain[I]);
1036 for (unsigned J = 0, NE = VecStoreTy->getNumElements(); J != NE; ++J) {
1037 unsigned NewIdx = J + I * VecWidth;
1038 Value *Extract = Builder.CreateExtractElement(Store->getValueOperand(),
1039 Builder.getInt32(J));
1040 if (Extract->getType() != StoreTy->getScalarType())
1041 Extract = Builder.CreateBitCast(Extract, StoreTy->getScalarType());
1042
1043 Value *Insert =
1044 Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(NewIdx));
1045 Vec = Insert;
1046 }
1047 }
1048 } else {
1049 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1050 StoreInst *Store = cast<StoreInst>(Chain[I]);
1051 Value *Extract = Store->getValueOperand();
1052 if (Extract->getType() != StoreTy->getScalarType())
1053 Extract =
1054 Builder.CreateBitOrPointerCast(Extract, StoreTy->getScalarType());
1055
1056 Value *Insert =
1057 Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(I));
1058 Vec = Insert;
1059 }
1060 }
1061
1062 StoreInst *SI = Builder.CreateAlignedStore(
1063 Vec,
1064 Builder.CreateBitCast(S0->getPointerOperand(), VecTy->getPointerTo(AS)),
1065 Alignment);
1066 propagateMetadata(SI, Chain);
1067
1068 eraseInstructions(Chain);
1069 ++NumVectorInstructions;
1070 NumScalarsVectorized += Chain.size();
1071 return true;
1072}
1073
1074bool Vectorizer::vectorizeLoadChain(
1075 ArrayRef<Instruction *> Chain,
1076 SmallPtrSet<Instruction *, 16> *InstructionsProcessed) {
1077 LoadInst *L0 = cast<LoadInst>(Chain[0]);
1078
1079 // If the vector has an int element, default to int for the whole load.
1080 Type *LoadTy;
20
'LoadTy' declared without an initial value
1081 for (const auto &V : Chain) {
21
Assuming '__begin1' is equal to '__end1'
1082 LoadTy = cast<LoadInst>(V)->getType();
1083 if (LoadTy->isIntOrIntVectorTy())
1084 break;
1085
1086 if (LoadTy->isPtrOrPtrVectorTy()) {
1087 LoadTy = Type::getIntNTy(F.getParent()->getContext(),
1088 DL.getTypeSizeInBits(LoadTy));
1089 break;
1090 }
1091 }
1092
1093 unsigned Sz = DL.getTypeSizeInBits(LoadTy);
22
1st function call argument is an uninitialized value
1094 unsigned AS = L0->getPointerAddressSpace();
1095 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
1096 unsigned VF = VecRegSize / Sz;
1097 unsigned ChainSize = Chain.size();
1098 unsigned Alignment = getAlignment(L0);
1099
1100 if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
1101 InstructionsProcessed->insert(Chain.begin(), Chain.end());
1102 return false;
1103 }
1104
1105 ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain);
1106 if (NewChain.empty()) {
1107 // No vectorization possible.
1108 InstructionsProcessed->insert(Chain.begin(), Chain.end());
1109 return false;
1110 }
1111 if (NewChain.size() == 1) {
1112 // Failed after the first instruction. Discard it and try the smaller chain.
1113 InstructionsProcessed->insert(NewChain.front());
1114 return false;
1115 }
1116
1117 // Update Chain to the valid vectorizable subchain.
1118 Chain = NewChain;
1119 ChainSize = Chain.size();
1120
1121 // Check if it's legal to vectorize this chain. If not, split the chain and
1122 // try again.
1123 unsigned EltSzInBytes = Sz / 8;
1124 unsigned SzInBytes = EltSzInBytes * ChainSize;
1125 VectorType *VecTy;
1126 VectorType *VecLoadTy = dyn_cast<VectorType>(LoadTy);
1127 if (VecLoadTy)
1128 VecTy = VectorType::get(LoadTy->getScalarType(),
1129 Chain.size() * VecLoadTy->getNumElements());
1130 else
1131 VecTy = VectorType::get(LoadTy, Chain.size());
1132
1133 // If it's more than the max vector size or the target has a better
1134 // vector factor, break it into two pieces.
1135 unsigned TargetVF = TTI.getLoadVectorFactor(VF, Sz, SzInBytes, VecTy);
1136 if (ChainSize > VF || (VF != TargetVF && TargetVF < ChainSize)) {
1137 LLVM_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)
1138 " 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)
;
1139 return vectorizeLoadChain(Chain.slice(0, TargetVF), InstructionsProcessed) |
1140 vectorizeLoadChain(Chain.slice(TargetVF), InstructionsProcessed);
1141 }
1142
1143 // We won't try again to vectorize the elements of the chain, regardless of
1144 // whether we succeed below.
1145 InstructionsProcessed->insert(Chain.begin(), Chain.end());
1146
1147 // If the load is going to be misaligned, don't vectorize it.
1148 if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
1149 if (L0->getPointerAddressSpace() != DL.getAllocaAddrSpace()) {
1150 auto Chains = splitOddVectorElts(Chain, Sz);
1151 return vectorizeLoadChain(Chains.first, InstructionsProcessed) |
1152 vectorizeLoadChain(Chains.second, InstructionsProcessed);
1153 }
1154
1155 unsigned NewAlign = getOrEnforceKnownAlignment(L0->getPointerOperand(),
1156 StackAdjustedAlignment,
1157 DL, L0, nullptr, &DT);
1158 if (NewAlign != 0)
1159 Alignment = NewAlign;
1160
1161 Alignment = NewAlign;
1162 }
1163
1164 if (!TTI.isLegalToVectorizeLoadChain(SzInBytes, Alignment, AS)) {
1165 auto Chains = splitOddVectorElts(Chain, Sz);
1166 return vectorizeLoadChain(Chains.first, InstructionsProcessed) |
1167 vectorizeLoadChain(Chains.second, InstructionsProcessed);
1168 }
1169
1170 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Loads to vectorize:\n"
; for (Instruction *I : Chain) I->dump(); }; } } while (false
)
1171 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
)
1172 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
)
1173 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
)
1174 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("load-store-vectorizer")) { { dbgs() << "LSV: Loads to vectorize:\n"
; for (Instruction *I : Chain) I->dump(); }; } } while (false
)
;
1175
1176 // getVectorizablePrefix already computed getBoundaryInstrs. The value of
1177 // Last may have changed since then, but the value of First won't have. If it
1178 // matters, we could compute getBoundaryInstrs only once and reuse it here.
1179 BasicBlock::iterator First, Last;
1180 std::tie(First, Last) = getBoundaryInstrs(Chain);
1181 Builder.SetInsertPoint(&*First);
1182
1183 Value *Bitcast =
1184 Builder.CreateBitCast(L0->getPointerOperand(), VecTy->getPointerTo(AS));
1185 LoadInst *LI = Builder.CreateAlignedLoad(Bitcast, Alignment);
1186 propagateMetadata(LI, Chain);
1187
1188 if (VecLoadTy) {
1189 SmallVector<Instruction *, 16> InstrsToErase;
1190
1191 unsigned VecWidth = VecLoadTy->getNumElements();
1192 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1193 for (auto Use : Chain[I]->users()) {
1194 // All users of vector loads are ExtractElement instructions with
1195 // constant indices, otherwise we would have bailed before now.
1196 Instruction *UI = cast<Instruction>(Use);
1197 unsigned Idx = cast<ConstantInt>(UI->getOperand(1))->getZExtValue();
1198 unsigned NewIdx = Idx + I * VecWidth;
1199 Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(NewIdx),
1200 UI->getName());
1201 if (V->getType() != UI->getType())
1202 V = Builder.CreateBitCast(V, UI->getType());
1203
1204 // Replace the old instruction.
1205 UI->replaceAllUsesWith(V);
1206 InstrsToErase.push_back(UI);
1207 }
1208 }
1209
1210 // Bitcast might not be an Instruction, if the value being loaded is a
1211 // constant. In that case, no need to reorder anything.
1212 if (Instruction *BitcastInst = dyn_cast<Instruction>(Bitcast))
1213 reorder(BitcastInst);
1214
1215 for (auto I : InstrsToErase)
1216 I->eraseFromParent();
1217 } else {
1218 for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1219 Value *CV = Chain[I];
1220 Value *V =
1221 Builder.CreateExtractElement(LI, Builder.getInt32(I), CV->getName());
1222 if (V->getType() != CV->getType()) {
1223 V = Builder.CreateBitOrPointerCast(V, CV->getType());
1224 }
1225
1226 // Replace the old instruction.
1227 CV->replaceAllUsesWith(V);
1228 }
1229
1230 if (Instruction *BitcastInst = dyn_cast<Instruction>(Bitcast))
1231 reorder(BitcastInst);
1232 }
1233
1234 eraseInstructions(Chain);
1235
1236 ++NumVectorInstructions;
1237 NumScalarsVectorized += Chain.size();
1238 return true;
1239}
1240
1241bool Vectorizer::accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
1242 unsigned Alignment) {
1243 if (Alignment % SzInBytes == 0)
1244 return false;
1245
1246 bool Fast = false;
1247 bool Allows = TTI.allowsMisalignedMemoryAccesses(F.getParent()->getContext(),
1248 SzInBytes * 8, AddressSpace,
1249 Alignment, &Fast);
1250 LLVM_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)
1251 << " 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)
;
1252 return !Allows || !Fast;
1253}