1//===- LoadStoreVectorizer.cpp - GPU Load & Store Vectorizer --------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass merges loads/stores to/from sequential memory addresses into vector
10// loads/stores. Although there's nothing GPU-specific in here, this pass is
11// motivated by the microarchitectural quirks of nVidia and AMD GPUs.
12//
13// (For simplicity below we talk about loads only, but everything also applies
14// to stores.)
15//
16// This pass is intended to be run late in the pipeline, after other
17// vectorization opportunities have been exploited. So the assumption here is
18// that immediately following our new vector load we'll need to extract out the
19// individual elements of the load, so we can operate on them individually.
20//
21// On CPUs this transformation is usually not beneficial, because extracting the
22// elements of a vector register is expensive on most architectures. It's
23// usually better just to load each element individually into its own scalar
24// register.
25//
26// However, nVidia and AMD GPUs don't have proper vector registers. Instead, a
27// "vector load" loads directly into a series of scalar registers. In effect,
28// extracting the elements of the vector is free. It's therefore always
29// beneficial to vectorize a sequence of loads on these architectures.
30//
31// Vectorizing (perhaps a better name might be "coalescing") loads can have
32// large performance impacts on GPU kernels, and opportunities for vectorizing
33// are common in GPU code. This pass tries very hard to find such
34// opportunities; its runtime is quadratic in the number of loads in a BB.
35//
36// Some CPU architectures, such as ARM, have instructions that load into
37// multiple scalar registers, similar to a GPU vectorized load. In theory ARM
38// could use this pass (with some modifications), but currently it implements
39// its own pass to do something similar to what we do here.
40//
41// Overview of the algorithm and terminology in this pass:
42//
43// - Break up each basic block into pseudo-BBs, composed of instructions which
44// are guaranteed to transfer control to their successors.
45// - Within a single pseudo-BB, find all loads, and group them into
46// "equivalence classes" according to getUnderlyingObject() and loaded
47// element size. Do the same for stores.
48// - For each equivalence class, greedily build "chains". Each chain has a
49// leader instruction, and every other member of the chain has a known
50// constant offset from the first instr in the chain.
51// - Break up chains so that they contain only contiguous accesses of legal
52// size with no intervening may-alias instrs.
53// - Convert each chain to vector instructions.
54//
55// The O(n^2) behavior of this pass comes from initially building the chains.
56// In the worst case we have to compare each new instruction to all of those
57// that came before. To limit this, we only calculate the offset to the leaders
58// of the N most recently-used chains.
59
60#include "llvm/Transforms/Vectorize/LoadStoreVectorizer.h"
61#include "llvm/ADT/APInt.h"
62#include "llvm/ADT/ArrayRef.h"
63#include "llvm/ADT/DenseMap.h"
64#include "llvm/ADT/MapVector.h"
65#include "llvm/ADT/PostOrderIterator.h"
66#include "llvm/ADT/STLExtras.h"
67#include "llvm/ADT/Sequence.h"
68#include "llvm/ADT/SmallPtrSet.h"
69#include "llvm/ADT/SmallVector.h"
70#include "llvm/ADT/Statistic.h"
71#include "llvm/ADT/iterator_range.h"
72#include "llvm/Analysis/AliasAnalysis.h"
73#include "llvm/Analysis/AssumptionCache.h"
74#include "llvm/Analysis/MemoryLocation.h"
75#include "llvm/Analysis/ScalarEvolution.h"
76#include "llvm/Analysis/TargetTransformInfo.h"
77#include "llvm/Analysis/ValueTracking.h"
78#include "llvm/Analysis/VectorUtils.h"
79#include "llvm/IR/Attributes.h"
80#include "llvm/IR/BasicBlock.h"
81#include "llvm/IR/ConstantRange.h"
82#include "llvm/IR/Constants.h"
83#include "llvm/IR/DataLayout.h"
84#include "llvm/IR/DerivedTypes.h"
85#include "llvm/IR/Dominators.h"
86#include "llvm/IR/Function.h"
87#include "llvm/IR/GetElementPtrTypeIterator.h"
88#include "llvm/IR/IRBuilder.h"
89#include "llvm/IR/InstrTypes.h"
90#include "llvm/IR/Instruction.h"
91#include "llvm/IR/Instructions.h"
92#include "llvm/IR/LLVMContext.h"
93#include "llvm/IR/Module.h"
94#include "llvm/IR/Type.h"
95#include "llvm/IR/Value.h"
96#include "llvm/InitializePasses.h"
97#include "llvm/Pass.h"
98#include "llvm/Support/Alignment.h"
99#include "llvm/Support/Casting.h"
100#include "llvm/Support/Debug.h"
101#include "llvm/Support/KnownBits.h"
102#include "llvm/Support/MathExtras.h"
103#include "llvm/Support/ModRef.h"
104#include "llvm/Support/raw_ostream.h"
105#include "llvm/Transforms/Utils/Local.h"
106#include <algorithm>
107#include <cassert>
108#include <cstdint>
109#include <cstdlib>
110#include <iterator>
111#include <optional>
112#include <tuple>
113#include <type_traits>
114#include <utility>
115#include <vector>
116
117using namespace llvm;
118
119#define DEBUG_TYPE "load-store-vectorizer"
120
121STATISTIC(NumVectorInstructions, "Number of vector accesses generated");
122STATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized");
123
124namespace {
125
126// Equivalence class key, the initial tuple by which we group loads/stores.
127// Loads/stores with different EqClassKeys are never merged.
128//
129// (We could in theory remove element-size from the this tuple. We'd just need
130// to fix up the vector packing/unpacking code.)
131using EqClassKey =
132 std::tuple<const Value * /* result of getUnderlyingObject() */,
133 unsigned /* AddrSpace */,
134 unsigned /* Load/Store element size bits */,
135 char /* IsLoad; char b/c bool can't be a DenseMap key */
136 >;
137[[maybe_unused]] llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
138 const EqClassKey &K) {
139 const auto &[UnderlyingObject, AddrSpace, ElementSize, IsLoad] = K;
140 return OS << (IsLoad ? "load" : "store") << " of " << *UnderlyingObject
141 << " of element size " << ElementSize << " bits in addrspace "
142 << AddrSpace;
143}
144
145// A Chain is a set of instructions such that:
146// - All instructions have the same equivalence class, so in particular all are
147// loads, or all are stores.
148// - We know the address accessed by the i'th chain elem relative to the
149// chain's leader instruction, which is the first instr of the chain in BB
150// order.
151//
152// Chains have two canonical orderings:
153// - BB order, sorted by Instr->comesBefore.
154// - Offset order, sorted by OffsetFromLeader.
155// This pass switches back and forth between these orders.
156struct ChainElem {
157 Instruction *Inst;
158 APInt OffsetFromLeader;
159 ChainElem(Instruction *Inst, APInt OffsetFromLeader)
160 : Inst(std::move(Inst)), OffsetFromLeader(std::move(OffsetFromLeader)) {}
161};
162using Chain = SmallVector<ChainElem, 1>;
163
164void sortChainInBBOrder(Chain &C) {
165 sort(C, Comp: [](auto &A, auto &B) { return A.Inst->comesBefore(B.Inst); });
166}
167
168void sortChainInOffsetOrder(Chain &C) {
169 sort(C, Comp: [](const auto &A, const auto &B) {
170 if (A.OffsetFromLeader != B.OffsetFromLeader)
171 return A.OffsetFromLeader.slt(B.OffsetFromLeader);
172 return A.Inst->comesBefore(B.Inst); // stable tiebreaker
173 });
174}
175
176[[maybe_unused]] void dumpChain(ArrayRef<ChainElem> C) {
177 for (const auto &E : C) {
178 dbgs() << " " << *E.Inst << " (offset " << E.OffsetFromLeader << ")\n";
179 }
180}
181
182using EquivalenceClassMap =
183 MapVector<EqClassKey, SmallVector<Instruction *, 8>>;
184
185// FIXME: Assuming stack alignment of 4 is always good enough
186constexpr unsigned StackAdjustedAlignment = 4;
187
188Instruction *propagateMetadata(Instruction *I, const Chain &C) {
189 SmallVector<Value *, 8> Values;
190 for (const ChainElem &E : C)
191 Values.emplace_back(Args: E.Inst);
192 return propagateMetadata(I, VL: Values);
193}
194
195bool isInvariantLoad(const Instruction *I) {
196 const LoadInst *LI = dyn_cast<LoadInst>(Val: I);
197 return LI != nullptr && LI->hasMetadata(KindID: LLVMContext::MD_invariant_load);
198}
199
200/// Reorders the instructions that I depends on (the instructions defining its
201/// operands), to ensure they dominate I.
202void reorder(Instruction *I) {
203 SmallPtrSet<Instruction *, 16> InstructionsToMove;
204 SmallVector<Instruction *, 16> Worklist;
205
206 Worklist.emplace_back(Args&: I);
207 while (!Worklist.empty()) {
208 Instruction *IW = Worklist.pop_back_val();
209 int NumOperands = IW->getNumOperands();
210 for (int Idx = 0; Idx < NumOperands; Idx++) {
211 Instruction *IM = dyn_cast<Instruction>(Val: IW->getOperand(i: Idx));
212 if (!IM || IM->getOpcode() == Instruction::PHI)
213 continue;
214
215 // If IM is in another BB, no need to move it, because this pass only
216 // vectorizes instructions within one BB.
217 if (IM->getParent() != I->getParent())
218 continue;
219
220 assert(IM != I && "Unexpected cycle while re-ordering instructions");
221
222 if (!IM->comesBefore(Other: I)) {
223 InstructionsToMove.insert(Ptr: IM);
224 Worklist.emplace_back(Args&: IM);
225 }
226 }
227 }
228
229 // All instructions to move should follow I. Start from I, not from begin().
230 for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;) {
231 Instruction *IM = &*(BBI++);
232 if (!InstructionsToMove.contains(Ptr: IM))
233 continue;
234 IM->moveBefore(InsertPos: I->getIterator());
235 }
236}
237
238class Vectorizer {
239 Function &F;
240 AliasAnalysis &AA;
241 AssumptionCache &AC;
242 DominatorTree &DT;
243 ScalarEvolution &SE;
244 TargetTransformInfo &TTI;
245 const DataLayout &DL;
246 IRBuilder<> Builder;
247
248 /// We could erase instrs right after vectorizing them, but that can mess up
249 /// our BB iterators, and also can make the equivalence class keys point to
250 /// freed memory. This is fixable, but it's simpler just to wait until we're
251 /// done with the BB and erase all at once.
252 SmallVector<Instruction *, 128> ToErase;
253
254 /// We insert load/store instructions and GEPs to fill gaps and extend chains
255 /// to enable vectorization. Keep track and delete them later.
256 DenseSet<Instruction *> ExtraElements;
257
258public:
259 Vectorizer(Function &F, AliasAnalysis &AA, AssumptionCache &AC,
260 DominatorTree &DT, ScalarEvolution &SE, TargetTransformInfo &TTI)
261 : F(F), AA(AA), AC(AC), DT(DT), SE(SE), TTI(TTI),
262 DL(F.getDataLayout()), Builder(SE.getContext()) {}
263
264 bool run();
265
266private:
267 static const unsigned MaxDepth = 3;
268
269 /// Runs the vectorizer on a "pseudo basic block", which is a range of
270 /// instructions [Begin, End) within one BB all of which have
271 /// isGuaranteedToTransferExecutionToSuccessor(I) == true.
272 bool runOnPseudoBB(BasicBlock::iterator Begin, BasicBlock::iterator End);
273
274 /// Runs the vectorizer on one equivalence class, i.e. one set of loads/stores
275 /// in the same BB with the same value for getUnderlyingObject() etc.
276 bool runOnEquivalenceClass(const EqClassKey &EqClassKey,
277 ArrayRef<Instruction *> EqClass);
278
279 /// Runs the vectorizer on one chain, i.e. a subset of an equivalence class
280 /// where all instructions access a known, constant offset from the first
281 /// instruction.
282 bool runOnChain(Chain &C);
283
284 /// Splits the chain into subchains of instructions which read/write a
285 /// contiguous block of memory. Discards any length-1 subchains (because
286 /// there's nothing to vectorize in there). Also attempts to fill gaps with
287 /// "extra" elements to artificially make chains contiguous in some cases.
288 std::vector<Chain> splitChainByContiguity(Chain &C);
289
290 /// Splits the chain into subchains where it's safe to hoist loads up to the
291 /// beginning of the sub-chain and it's safe to sink loads up to the end of
292 /// the sub-chain. Discards any length-1 subchains. Also attempts to extend
293 /// non-power-of-two chains by adding "extra" elements in some cases.
294 std::vector<Chain> splitChainByMayAliasInstrs(Chain &C);
295
296 /// Splits the chain into subchains that make legal, aligned accesses.
297 /// Discards any length-1 subchains.
298 std::vector<Chain> splitChainByAlignment(Chain &C);
299
300 /// Converts the instrs in the chain into a single vectorized load or store.
301 /// Adds the old scalar loads/stores to ToErase.
302 bool vectorizeChain(Chain &C);
303
304 /// Tries to compute the offset in bytes PtrB - PtrA.
305 std::optional<APInt> getConstantOffset(Value *PtrA, Value *PtrB,
306 Instruction *ContextInst,
307 unsigned Depth = 0);
308 std::optional<APInt> getConstantOffsetComplexAddrs(Value *PtrA, Value *PtrB,
309 Instruction *ContextInst,
310 unsigned Depth);
311 std::optional<APInt> getConstantOffsetSelects(Value *PtrA, Value *PtrB,
312 Instruction *ContextInst,
313 unsigned Depth);
314
315 /// Gets the element type of the vector that the chain will load or store.
316 /// This is nontrivial because the chain may contain elements of different
317 /// types; e.g. it's legal to have a chain that contains both i32 and float.
318 Type *getChainElemTy(const Chain &C);
319
320 /// Determines whether ChainElem can be moved up (if IsLoad) or down (if
321 /// !IsLoad) to ChainBegin -- i.e. there are no intervening may-alias
322 /// instructions.
323 ///
324 /// The map ChainElemOffsets must contain all of the elements in
325 /// [ChainBegin, ChainElem] and their offsets from some arbitrary base
326 /// address. It's ok if it contains additional entries.
327 template <bool IsLoadChain>
328 bool isSafeToMove(
329 Instruction *ChainElem, Instruction *ChainBegin,
330 const DenseMap<Instruction *, APInt /*OffsetFromLeader*/> &ChainOffsets,
331 BatchAAResults &BatchAA);
332
333 /// Merges the equivalence classes if they have underlying objects that differ
334 /// by one level of indirection (i.e., one is a getelementptr and the other is
335 /// the base pointer in that getelementptr).
336 void mergeEquivalenceClasses(EquivalenceClassMap &EQClasses) const;
337
338 /// Collects loads and stores grouped by "equivalence class", where:
339 /// - all elements in an eq class are a load or all are a store,
340 /// - they all load/store the same element size (it's OK to have e.g. i8 and
341 /// <4 x i8> in the same class, but not i32 and <4 x i8>), and
342 /// - they all have the same value for getUnderlyingObject().
343 EquivalenceClassMap collectEquivalenceClasses(BasicBlock::iterator Begin,
344 BasicBlock::iterator End);
345
346 /// Partitions Instrs into "chains" where every instruction has a known
347 /// constant offset from the first instr in the chain.
348 ///
349 /// Postcondition: For all i, ret[i][0].second == 0, because the first instr
350 /// in the chain is the leader, and an instr touches distance 0 from itself.
351 std::vector<Chain> gatherChains(ArrayRef<Instruction *> Instrs);
352
353 /// Checks if a potential vector load/store with a given alignment is allowed
354 /// and fast. Aligned accesses are always allowed and fast, while misaligned
355 /// accesses depend on TTI checks to determine whether they can and should be
356 /// vectorized or kept as element-wise accesses.
357 bool accessIsAllowedAndFast(unsigned SizeBytes, unsigned AS, Align Alignment,
358 unsigned VecElemBits) const;
359
360 /// Create a new GEP and a new Load/Store instruction such that the GEP
361 /// is pointing at PrevElem + Offset. In the case of stores, store poison.
362 /// Extra elements will either be combined into a masked load/store or
363 /// deleted before the end of the pass.
364 ChainElem createExtraElementAfter(const ChainElem &PrevElem, Type *Ty,
365 APInt Offset, StringRef Prefix,
366 Align Alignment = Align());
367
368 /// Create a mask that masks off the extra elements in the chain, to be used
369 /// for the creation of a masked load/store vector.
370 Value *createMaskForExtraElements(const ArrayRef<ChainElem> C,
371 FixedVectorType *VecTy);
372
373 /// Delete dead GEPs and extra Load/Store instructions created by
374 /// createExtraElementAfter
375 void deleteExtraElements();
376};
377
378class LoadStoreVectorizerLegacyPass : public FunctionPass {
379public:
380 static char ID;
381
382 LoadStoreVectorizerLegacyPass() : FunctionPass(ID) {}
383
384 bool runOnFunction(Function &F) override;
385
386 StringRef getPassName() const override {
387 return "GPU Load and Store Vectorizer";
388 }
389
390 void getAnalysisUsage(AnalysisUsage &AU) const override {
391 AU.addRequired<AAResultsWrapperPass>();
392 AU.addRequired<AssumptionCacheTracker>();
393 AU.addRequired<ScalarEvolutionWrapperPass>();
394 AU.addRequired<DominatorTreeWrapperPass>();
395 AU.addRequired<TargetTransformInfoWrapperPass>();
396 AU.setPreservesCFG();
397 }
398};
399
400} // end anonymous namespace
401
402char LoadStoreVectorizerLegacyPass::ID = 0;
403
404INITIALIZE_PASS_BEGIN(LoadStoreVectorizerLegacyPass, DEBUG_TYPE,
405 "Vectorize load and Store instructions", false, false)
406INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
407INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
408INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
409INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
410INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
411INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
412INITIALIZE_PASS_END(LoadStoreVectorizerLegacyPass, DEBUG_TYPE,
413 "Vectorize load and store instructions", false, false)
414
415Pass *llvm::createLoadStoreVectorizerPass() {
416 return new LoadStoreVectorizerLegacyPass();
417}
418
419bool LoadStoreVectorizerLegacyPass::runOnFunction(Function &F) {
420 // Don't vectorize when the attribute NoImplicitFloat is used.
421 if (skipFunction(F) || F.hasFnAttribute(Kind: Attribute::NoImplicitFloat))
422 return false;
423
424 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
425 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
426 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
427 TargetTransformInfo &TTI =
428 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
429
430 AssumptionCache &AC =
431 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
432
433 return Vectorizer(F, AA, AC, DT, SE, TTI).run();
434}
435
436PreservedAnalyses LoadStoreVectorizerPass::run(Function &F,
437 FunctionAnalysisManager &AM) {
438 // Don't vectorize when the attribute NoImplicitFloat is used.
439 if (F.hasFnAttribute(Kind: Attribute::NoImplicitFloat))
440 return PreservedAnalyses::all();
441
442 AliasAnalysis &AA = AM.getResult<AAManager>(IR&: F);
443 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
444 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
445 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
446 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
447
448 bool Changed = Vectorizer(F, AA, AC, DT, SE, TTI).run();
449 PreservedAnalyses PA;
450 PA.preserveSet<CFGAnalyses>();
451 return Changed ? PA : PreservedAnalyses::all();
452}
453
454bool Vectorizer::run() {
455 bool Changed = false;
456 // Break up the BB if there are any instrs which aren't guaranteed to transfer
457 // execution to their successor.
458 //
459 // Consider, for example:
460 //
461 // def assert_arr_len(int n) { if (n < 2) exit(); }
462 //
463 // load arr[0]
464 // call assert_array_len(arr.length)
465 // load arr[1]
466 //
467 // Even though assert_arr_len does not read or write any memory, we can't
468 // speculate the second load before the call. More info at
469 // https://github.com/llvm/llvm-project/issues/52950.
470 for (BasicBlock *BB : post_order(G: &F)) {
471 // BB must at least have a terminator.
472 assert(!BB->empty());
473
474 SmallVector<BasicBlock::iterator, 8> Barriers;
475 Barriers.emplace_back(Args: BB->begin());
476 for (Instruction &I : *BB)
477 if (!isGuaranteedToTransferExecutionToSuccessor(I: &I))
478 Barriers.emplace_back(Args: I.getIterator());
479 Barriers.emplace_back(Args: BB->end());
480
481 for (auto It = Barriers.begin(), End = std::prev(x: Barriers.end()); It != End;
482 ++It)
483 Changed |= runOnPseudoBB(Begin: *It, End: *std::next(x: It));
484
485 for (Instruction *I : ToErase) {
486 // These will get deleted in deleteExtraElements.
487 // This is because ExtraElements will include both extra elements
488 // that *were* vectorized and extra elements that *were not*
489 // vectorized. ToErase will only include extra elements that *were*
490 // vectorized, so in order to avoid double deletion we skip them here and
491 // handle them in deleteExtraElements.
492 if (ExtraElements.contains(V: I))
493 continue;
494 auto *PtrOperand = getLoadStorePointerOperand(V: I);
495 if (I->use_empty())
496 I->eraseFromParent();
497 RecursivelyDeleteTriviallyDeadInstructions(V: PtrOperand);
498 }
499 ToErase.clear();
500 deleteExtraElements();
501 }
502
503 return Changed;
504}
505
506bool Vectorizer::runOnPseudoBB(BasicBlock::iterator Begin,
507 BasicBlock::iterator End) {
508 LLVM_DEBUG({
509 dbgs() << "LSV: Running on pseudo-BB [" << *Begin << " ... ";
510 if (End != Begin->getParent()->end())
511 dbgs() << *End;
512 else
513 dbgs() << "<BB end>";
514 dbgs() << ")\n";
515 });
516
517 bool Changed = false;
518 for (const auto &[EqClassKey, EqClass] :
519 collectEquivalenceClasses(Begin, End))
520 Changed |= runOnEquivalenceClass(EqClassKey, EqClass);
521
522 return Changed;
523}
524
525bool Vectorizer::runOnEquivalenceClass(const EqClassKey &EqClassKey,
526 ArrayRef<Instruction *> EqClass) {
527 bool Changed = false;
528
529 LLVM_DEBUG({
530 dbgs() << "LSV: Running on equivalence class of size " << EqClass.size()
531 << " keyed on " << EqClassKey << ":\n";
532 for (Instruction *I : EqClass)
533 dbgs() << " " << *I << "\n";
534 });
535
536 std::vector<Chain> Chains = gatherChains(Instrs: EqClass);
537 LLVM_DEBUG(dbgs() << "LSV: Got " << Chains.size()
538 << " nontrivial chains.\n";);
539 for (Chain &C : Chains)
540 Changed |= runOnChain(C);
541 return Changed;
542}
543
544bool Vectorizer::runOnChain(Chain &C) {
545 LLVM_DEBUG({
546 dbgs() << "LSV: Running on chain with " << C.size() << " instructions:\n";
547 dumpChain(C);
548 });
549
550 // Split up the chain into increasingly smaller chains, until we can finally
551 // vectorize the chains.
552 //
553 // (Don't be scared by the depth of the loop nest here. These operations are
554 // all at worst O(n lg n) in the number of instructions, and splitting chains
555 // doesn't change the number of instrs. So the whole loop nest is O(n lg n).)
556 bool Changed = false;
557 for (auto &C : splitChainByMayAliasInstrs(C))
558 for (auto &C : splitChainByContiguity(C))
559 for (auto &C : splitChainByAlignment(C))
560 Changed |= vectorizeChain(C);
561 return Changed;
562}
563
564std::vector<Chain> Vectorizer::splitChainByMayAliasInstrs(Chain &C) {
565 if (C.empty())
566 return {};
567
568 sortChainInBBOrder(C);
569
570 LLVM_DEBUG({
571 dbgs() << "LSV: splitChainByMayAliasInstrs considering chain:\n";
572 dumpChain(C);
573 });
574
575 // We know that elements in the chain with nonverlapping offsets can't
576 // alias, but AA may not be smart enough to figure this out. Use a
577 // hashtable.
578 DenseMap<Instruction *, APInt /*OffsetFromLeader*/> ChainOffsets;
579 for (const auto &E : C)
580 ChainOffsets.insert(KV: {&*E.Inst, E.OffsetFromLeader});
581
582 // Across a single invocation of this function the IR is not changing, so
583 // using a batched Alias Analysis is safe and can reduce compile time.
584 BatchAAResults BatchAA(AA);
585
586 // Loads get hoisted up to the first load in the chain. Stores get sunk
587 // down to the last store in the chain. Our algorithm for loads is:
588 //
589 // - Take the first element of the chain. This is the start of a new chain.
590 // - Take the next element of `Chain` and check for may-alias instructions
591 // up to the start of NewChain. If no may-alias instrs, add it to
592 // NewChain. Otherwise, start a new NewChain.
593 //
594 // For stores it's the same except in the reverse direction.
595 //
596 // We expect IsLoad to be an std::bool_constant.
597 auto Impl = [&](auto IsLoad) {
598 // MSVC is unhappy if IsLoad is a capture, so pass it as an arg.
599 auto [ChainBegin, ChainEnd] = [&](auto IsLoad) {
600 if constexpr (IsLoad())
601 return std::make_pair(x: C.begin(), y: C.end());
602 else
603 return std::make_pair(x: C.rbegin(), y: C.rend());
604 }(IsLoad);
605 assert(ChainBegin != ChainEnd);
606
607 std::vector<Chain> Chains;
608 SmallVector<ChainElem, 1> NewChain;
609 NewChain.emplace_back(*ChainBegin);
610 for (auto ChainIt = std::next(ChainBegin); ChainIt != ChainEnd; ++ChainIt) {
611 if (isSafeToMove<IsLoad>(ChainIt->Inst, NewChain.front().Inst,
612 ChainOffsets, BatchAA)) {
613 LLVM_DEBUG(dbgs() << "LSV: No intervening may-alias instrs; can merge "
614 << *ChainIt->Inst << " into " << *ChainBegin->Inst
615 << "\n");
616 NewChain.emplace_back(*ChainIt);
617 } else {
618 LLVM_DEBUG(
619 dbgs() << "LSV: Found intervening may-alias instrs; cannot merge "
620 << *ChainIt->Inst << " into " << *ChainBegin->Inst << "\n");
621 if (NewChain.size() > 1) {
622 LLVM_DEBUG({
623 dbgs() << "LSV: got nontrivial chain without aliasing instrs:\n";
624 dumpChain(NewChain);
625 });
626 Chains.emplace_back(args: std::move(NewChain));
627 }
628
629 // Start a new chain.
630 NewChain = SmallVector<ChainElem, 1>({*ChainIt});
631 }
632 }
633 if (NewChain.size() > 1) {
634 LLVM_DEBUG({
635 dbgs() << "LSV: got nontrivial chain without aliasing instrs:\n";
636 dumpChain(NewChain);
637 });
638 Chains.emplace_back(args: std::move(NewChain));
639 }
640 return Chains;
641 };
642
643 if (isa<LoadInst>(Val: C[0].Inst))
644 return Impl(/*IsLoad=*/std::bool_constant<true>());
645
646 assert(isa<StoreInst>(C[0].Inst));
647 return Impl(/*IsLoad=*/std::bool_constant<false>());
648}
649
650std::vector<Chain> Vectorizer::splitChainByContiguity(Chain &C) {
651 if (C.empty())
652 return {};
653
654 sortChainInOffsetOrder(C);
655
656 LLVM_DEBUG({
657 dbgs() << "LSV: splitChainByContiguity considering chain:\n";
658 dumpChain(C);
659 });
660
661 // If the chain is not contiguous, we try to fill the gap with "extra"
662 // elements to artificially make it contiguous, to try to enable
663 // vectorization. We only fill gaps if there is potential to end up with a
664 // legal masked load/store given the target, address space, and element type.
665 // At this point, when querying the TTI, optimistically assume max alignment
666 // and max vector size, as splitChainByAlignment will ensure the final vector
667 // shape passes the legalization check.
668 unsigned AS = getLoadStoreAddressSpace(I: C[0].Inst);
669 Type *ElementType = getLoadStoreType(I: C[0].Inst)->getScalarType();
670 unsigned MaxVecRegBits = TTI.getLoadStoreVecRegBitWidth(AddrSpace: AS);
671 Align OptimisticAlign = Align(MaxVecRegBits / 8);
672 unsigned int MaxVectorNumElems =
673 MaxVecRegBits / DL.getTypeSizeInBits(Ty: ElementType);
674 // Note: This check decides whether to try to fill gaps based on the masked
675 // legality of the target's maximum vector size (getLoadStoreVecRegBitWidth).
676 // If a target *does not* support a masked load/store with this max vector
677 // size, but *does* support a masked load/store with a *smaller* vector size,
678 // that optimization will be missed. This does not occur in any of the targets
679 // that currently support this API.
680 FixedVectorType *OptimisticVectorType =
681 FixedVectorType::get(ElementType, NumElts: MaxVectorNumElems);
682 bool TryFillGaps =
683 isa<LoadInst>(Val: C[0].Inst)
684 ? TTI.isLegalMaskedLoad(DataType: OptimisticVectorType, Alignment: OptimisticAlign, AddressSpace: AS,
685 MaskKind: TTI::MaskKind::ConstantMask)
686 : TTI.isLegalMaskedStore(DataType: OptimisticVectorType, Alignment: OptimisticAlign, AddressSpace: AS,
687 MaskKind: TTI::MaskKind::ConstantMask);
688
689 // Cache the best aligned element in the chain for use when creating extra
690 // elements.
691 Align BestAlignedElemAlign = getLoadStoreAlignment(I: C[0].Inst);
692 APInt OffsetOfBestAlignedElemFromLeader = C[0].OffsetFromLeader;
693 for (const auto &E : C) {
694 Align ElementAlignment = getLoadStoreAlignment(I: E.Inst);
695 if (ElementAlignment > BestAlignedElemAlign) {
696 BestAlignedElemAlign = ElementAlignment;
697 OffsetOfBestAlignedElemFromLeader = E.OffsetFromLeader;
698 }
699 }
700
701 auto DeriveAlignFromBestAlignedElem = [&](APInt NewElemOffsetFromLeader) {
702 return commonAlignment(
703 A: BestAlignedElemAlign,
704 Offset: (NewElemOffsetFromLeader - OffsetOfBestAlignedElemFromLeader)
705 .abs()
706 .getLimitedValue());
707 };
708
709 unsigned ASPtrBits = DL.getIndexSizeInBits(AS);
710
711 std::vector<Chain> Ret;
712 Ret.push_back(x: {C.front()});
713
714 unsigned ChainElemTyBits = DL.getTypeSizeInBits(Ty: getChainElemTy(C));
715 ChainElem &Prev = C[0];
716 for (auto It = std::next(x: C.begin()), End = C.end(); It != End; ++It) {
717 auto &CurChain = Ret.back();
718
719 APInt PrevSzBytes =
720 APInt(ASPtrBits, DL.getTypeStoreSize(Ty: getLoadStoreType(I: Prev.Inst)));
721 APInt PrevReadEnd = Prev.OffsetFromLeader + PrevSzBytes;
722 unsigned SzBytes = DL.getTypeStoreSize(Ty: getLoadStoreType(I: It->Inst));
723
724 // Add this instruction to the end of the current chain, or start a new one.
725 assert(
726 8 * SzBytes % ChainElemTyBits == 0 &&
727 "Every chain-element size must be a multiple of the element size after "
728 "vectorization.");
729 APInt ReadEnd = It->OffsetFromLeader + SzBytes;
730 // Allow redundancy: partial or full overlap counts as contiguous.
731 bool AreContiguous = false;
732 if (It->OffsetFromLeader.sle(RHS: PrevReadEnd)) {
733 // Check overlap is a multiple of the element size after vectorization.
734 uint64_t Overlap = (PrevReadEnd - It->OffsetFromLeader).getZExtValue();
735 if (8 * Overlap % ChainElemTyBits == 0)
736 AreContiguous = true;
737 }
738
739 LLVM_DEBUG(dbgs() << "LSV: Instruction is "
740 << (AreContiguous ? "contiguous" : "chain-breaker")
741 << *It->Inst << " (starts at offset "
742 << It->OffsetFromLeader << ")\n");
743
744 // If the chain is not contiguous, try to fill in gaps between Prev and
745 // Curr. For now, we aren't filling gaps between load/stores of different
746 // sizes. Additionally, as a conservative heuristic, we only fill gaps of
747 // 1-2 elements. Generating loads/stores with too many unused bytes has a
748 // side effect of increasing register pressure (on NVIDIA targets at least),
749 // which could cancel out the benefits of reducing number of load/stores.
750 bool GapFilled = false;
751 if (!AreContiguous && TryFillGaps && PrevSzBytes == SzBytes) {
752 APInt GapSzBytes = It->OffsetFromLeader - PrevReadEnd;
753 if (GapSzBytes == PrevSzBytes) {
754 // There is a single gap between Prev and Curr, create one extra element
755 ChainElem NewElem = createExtraElementAfter(
756 PrevElem: Prev, Ty: getLoadStoreType(I: Prev.Inst), Offset: PrevSzBytes, Prefix: "GapFill",
757 Alignment: DeriveAlignFromBestAlignedElem(PrevReadEnd));
758 CurChain.push_back(Elt: NewElem);
759 GapFilled = true;
760 }
761 // There are two gaps between Prev and Curr, only create two extra
762 // elements if Prev is the first element in a sequence of four.
763 // This has the highest chance of resulting in a beneficial vectorization.
764 if ((GapSzBytes == 2 * PrevSzBytes) && (CurChain.size() % 4 == 1)) {
765 ChainElem NewElem1 = createExtraElementAfter(
766 PrevElem: Prev, Ty: getLoadStoreType(I: Prev.Inst), Offset: PrevSzBytes, Prefix: "GapFill",
767 Alignment: DeriveAlignFromBestAlignedElem(PrevReadEnd));
768 ChainElem NewElem2 = createExtraElementAfter(
769 PrevElem: NewElem1, Ty: getLoadStoreType(I: Prev.Inst), Offset: PrevSzBytes, Prefix: "GapFill",
770 Alignment: DeriveAlignFromBestAlignedElem(PrevReadEnd + PrevSzBytes));
771 CurChain.push_back(Elt: NewElem1);
772 CurChain.push_back(Elt: NewElem2);
773 GapFilled = true;
774 }
775 }
776
777 if (AreContiguous || GapFilled)
778 CurChain.push_back(Elt: *It);
779 else
780 Ret.push_back(x: {*It});
781 // In certain cases when handling redundant elements with partial overlaps,
782 // the previous element may still extend beyond the current element. Only
783 // update Prev if the current element is the new end of the chain.
784 if (ReadEnd.sge(RHS: PrevReadEnd))
785 Prev = *It;
786 }
787
788 // Filter out length-1 chains, these are uninteresting.
789 llvm::erase_if(C&: Ret, P: [](const auto &Chain) { return Chain.size() <= 1; });
790 return Ret;
791}
792
793Type *Vectorizer::getChainElemTy(const Chain &C) {
794 assert(!C.empty());
795 // The rules are:
796 // - If there are any pointer types in the chain, use an integer type.
797 // - Prefer an integer type if it appears in the chain.
798 // - Otherwise, use the first type in the chain.
799 //
800 // The rule about pointer types is a simplification when we merge e.g. a load
801 // of a ptr and a double. There's no direct conversion from a ptr to a
802 // double; it requires a ptrtoint followed by a bitcast.
803 //
804 // It's unclear to me if the other rules have any practical effect, but we do
805 // it to match this pass's previous behavior.
806 if (any_of(Range: C, P: [](const ChainElem &E) {
807 return getLoadStoreType(I: E.Inst)->getScalarType()->isPointerTy();
808 })) {
809 return Type::getIntNTy(
810 C&: F.getContext(),
811 N: DL.getTypeSizeInBits(Ty: getLoadStoreType(I: C[0].Inst)->getScalarType()));
812 }
813
814 for (const ChainElem &E : C)
815 if (Type *T = getLoadStoreType(I: E.Inst)->getScalarType(); T->isIntegerTy())
816 return T;
817 return getLoadStoreType(I: C[0].Inst)->getScalarType();
818}
819
820std::vector<Chain> Vectorizer::splitChainByAlignment(Chain &C) {
821 // We use a simple greedy algorithm.
822 // - Given a chain of length N, find all prefixes that
823 // (a) are not longer than the max register length, and
824 // (b) are a power of 2.
825 // - Starting from the longest prefix, try to create a vector of that length.
826 // - If one of them works, great. Repeat the algorithm on any remaining
827 // elements in the chain.
828 // - If none of them work, discard the first element and repeat on a chain
829 // of length N-1.
830 if (C.empty())
831 return {};
832
833 sortChainInOffsetOrder(C);
834
835 LLVM_DEBUG({
836 dbgs() << "LSV: splitChainByAlignment considering chain:\n";
837 dumpChain(C);
838 });
839
840 bool IsLoadChain = isa<LoadInst>(Val: C[0].Inst);
841 auto GetVectorFactor = [&](unsigned VF, unsigned LoadStoreSize,
842 unsigned ChainSizeBytes, VectorType *VecTy) {
843 return IsLoadChain ? TTI.getLoadVectorFactor(VF, LoadSize: LoadStoreSize,
844 ChainSizeInBytes: ChainSizeBytes, VecTy)
845 : TTI.getStoreVectorFactor(VF, StoreSize: LoadStoreSize,
846 ChainSizeInBytes: ChainSizeBytes, VecTy);
847 };
848
849#ifndef NDEBUG
850 for (const auto &E : C) {
851 Type *Ty = getLoadStoreType(E.Inst)->getScalarType();
852 assert(isPowerOf2_32(DL.getTypeSizeInBits(Ty)) &&
853 "Should have filtered out non-power-of-two elements in "
854 "collectEquivalenceClasses.");
855 }
856#endif
857
858 unsigned AS = getLoadStoreAddressSpace(I: C[0].Inst);
859 unsigned VecRegBytes = TTI.getLoadStoreVecRegBitWidth(AddrSpace: AS) / 8;
860
861 // For compile time reasons, we cache whether or not the superset
862 // of all candidate chains contains any extra loads/stores from earlier gap
863 // filling.
864 bool CandidateChainsMayContainExtraLoadsStores = any_of(
865 Range&: C, P: [this](const ChainElem &E) { return ExtraElements.contains(V: E.Inst); });
866
867 std::vector<Chain> Ret;
868 for (unsigned CBegin = 0; CBegin < C.size(); ++CBegin) {
869 // Find candidate chains of size not greater than the largest vector reg.
870 // These chains are over the closed interval [CBegin, CEnd].
871 SmallVector<std::pair<unsigned /*CEnd*/, unsigned /*SizeBytes*/>, 8>
872 CandidateChains;
873 // Need to compute the size of every candidate chain from its beginning
874 // because of possible overlapping among chain elements.
875 unsigned Sz = DL.getTypeStoreSize(Ty: getLoadStoreType(I: C[CBegin].Inst));
876 APInt PrevReadEnd = C[CBegin].OffsetFromLeader + Sz;
877 for (unsigned CEnd = CBegin + 1, Size = C.size(); CEnd < Size; ++CEnd) {
878 APInt ReadEnd = C[CEnd].OffsetFromLeader +
879 DL.getTypeStoreSize(Ty: getLoadStoreType(I: C[CEnd].Inst));
880 unsigned BytesAdded =
881 PrevReadEnd.sle(RHS: ReadEnd) ? (ReadEnd - PrevReadEnd).getSExtValue() : 0;
882 Sz += BytesAdded;
883 if (Sz > VecRegBytes)
884 break;
885 CandidateChains.emplace_back(Args&: CEnd, Args&: Sz);
886 PrevReadEnd = APIntOps::smax(A: PrevReadEnd, B: ReadEnd);
887 }
888
889 // Consider the longest chain first.
890 for (auto It = CandidateChains.rbegin(), End = CandidateChains.rend();
891 It != End; ++It) {
892 auto [CEnd, SizeBytes] = *It;
893 LLVM_DEBUG(
894 dbgs() << "LSV: splitChainByAlignment considering candidate chain ["
895 << *C[CBegin].Inst << " ... " << *C[CEnd].Inst << "]\n");
896
897 Type *VecElemTy = getChainElemTy(C);
898 // Note, VecElemTy is a power of 2, but might be less than one byte. For
899 // example, we can vectorize 2 x <2 x i4> to <4 x i4>, and in this case
900 // VecElemTy would be i4.
901 unsigned VecElemBits = DL.getTypeSizeInBits(Ty: VecElemTy);
902
903 // SizeBytes and VecElemBits are powers of 2, so they divide evenly.
904 assert((8 * SizeBytes) % VecElemBits == 0);
905 unsigned NumVecElems = 8 * SizeBytes / VecElemBits;
906 FixedVectorType *VecTy = FixedVectorType::get(ElementType: VecElemTy, NumElts: NumVecElems);
907 unsigned VF = 8 * VecRegBytes / VecElemBits;
908
909 // Check that TTI is happy with this vectorization factor.
910 unsigned TargetVF = GetVectorFactor(VF, VecElemBits,
911 VecElemBits * NumVecElems / 8, VecTy);
912 if (TargetVF != VF && TargetVF < NumVecElems) {
913 LLVM_DEBUG(
914 dbgs() << "LSV: splitChainByAlignment discarding candidate chain "
915 "because TargetVF="
916 << TargetVF << " != VF=" << VF
917 << " and TargetVF < NumVecElems=" << NumVecElems << "\n");
918 continue;
919 }
920
921 // If we're loading/storing from an alloca, align it if possible.
922 //
923 // FIXME: We eagerly upgrade the alignment, regardless of whether TTI
924 // tells us this is beneficial. This feels a bit odd, but it matches
925 // existing tests. This isn't *so* bad, because at most we align to 4
926 // bytes (current value of StackAdjustedAlignment).
927 //
928 // FIXME: We will upgrade the alignment of the alloca even if it turns out
929 // we can't vectorize for some other reason.
930 Value *PtrOperand = getLoadStorePointerOperand(V: C[CBegin].Inst);
931 bool IsAllocaAccess = AS == DL.getAllocaAddrSpace() &&
932 isa<AllocaInst>(Val: PtrOperand->stripPointerCasts());
933 Align Alignment = getLoadStoreAlignment(I: C[CBegin].Inst);
934 Align PrefAlign = Align(StackAdjustedAlignment);
935 if (IsAllocaAccess && Alignment.value() % SizeBytes != 0 &&
936 accessIsAllowedAndFast(SizeBytes, AS, Alignment: PrefAlign, VecElemBits)) {
937 Align NewAlign = getOrEnforceKnownAlignment(
938 V: PtrOperand, PrefAlign, DL, CxtI: C[CBegin].Inst, AC: nullptr, DT: &DT);
939 if (NewAlign >= Alignment) {
940 LLVM_DEBUG(dbgs()
941 << "LSV: splitByChain upgrading alloca alignment from "
942 << Alignment.value() << " to " << NewAlign.value()
943 << "\n");
944 Alignment = NewAlign;
945 }
946 }
947
948 Chain ExtendingLoadsStores;
949 if (!accessIsAllowedAndFast(SizeBytes, AS, Alignment, VecElemBits)) {
950 // If we have a non-power-of-2 element count, attempt to extend the
951 // chain to the next power-of-2 if it makes the access allowed and
952 // fast.
953 bool AllowedAndFast = false;
954 if (NumVecElems < TargetVF && !isPowerOf2_32(Value: NumVecElems) &&
955 VecElemBits >= 8) {
956 // TargetVF may be a lot higher than NumVecElems,
957 // so only extend to the next power of 2.
958 assert(VecElemBits % 8 == 0);
959 unsigned VecElemBytes = VecElemBits / 8;
960 unsigned NewNumVecElems = PowerOf2Ceil(A: NumVecElems);
961 unsigned NewSizeBytes = VecElemBytes * NewNumVecElems;
962
963 assert(isPowerOf2_32(TargetVF) &&
964 "TargetVF expected to be a power of 2");
965 assert(NewNumVecElems <= TargetVF &&
966 "Should not extend past TargetVF");
967
968 LLVM_DEBUG(dbgs()
969 << "LSV: attempting to extend chain of " << NumVecElems
970 << " " << (IsLoadChain ? "loads" : "stores") << " to "
971 << NewNumVecElems << " elements\n");
972 bool IsLegalToExtend =
973 IsLoadChain ? TTI.isLegalMaskedLoad(
974 DataType: FixedVectorType::get(ElementType: VecElemTy, NumElts: NewNumVecElems),
975 Alignment, AddressSpace: AS, MaskKind: TTI::MaskKind::ConstantMask)
976 : TTI.isLegalMaskedStore(
977 DataType: FixedVectorType::get(ElementType: VecElemTy, NumElts: NewNumVecElems),
978 Alignment, AddressSpace: AS, MaskKind: TTI::MaskKind::ConstantMask);
979 // Only artificially increase the chain if it would be AllowedAndFast
980 // and if the resulting masked load/store will be legal for the
981 // target.
982 if (IsLegalToExtend &&
983 accessIsAllowedAndFast(SizeBytes: NewSizeBytes, AS, Alignment,
984 VecElemBits)) {
985 LLVM_DEBUG(dbgs()
986 << "LSV: extending " << (IsLoadChain ? "load" : "store")
987 << " chain of " << NumVecElems << " "
988 << (IsLoadChain ? "loads" : "stores")
989 << " with total byte size of " << SizeBytes << " to "
990 << NewNumVecElems << " "
991 << (IsLoadChain ? "loads" : "stores")
992 << " with total byte size of " << NewSizeBytes
993 << ", TargetVF=" << TargetVF << " \n");
994
995 // Create (NewNumVecElems - NumVecElems) extra elements.
996 // We are basing each extra element on CBegin, which means the
997 // offsets should be based on SizeBytes, which represents the offset
998 // from CBegin to the current end of the chain.
999 unsigned ASPtrBits = DL.getIndexSizeInBits(AS);
1000 for (unsigned I = 0; I < (NewNumVecElems - NumVecElems); I++) {
1001 ChainElem NewElem = createExtraElementAfter(
1002 PrevElem: C[CBegin], Ty: VecElemTy,
1003 Offset: APInt(ASPtrBits, SizeBytes + I * VecElemBytes), Prefix: "Extend");
1004 ExtendingLoadsStores.push_back(Elt: NewElem);
1005 }
1006
1007 // Update the size and number of elements for upcoming checks.
1008 SizeBytes = NewSizeBytes;
1009 NumVecElems = NewNumVecElems;
1010 AllowedAndFast = true;
1011 }
1012 }
1013 if (!AllowedAndFast) {
1014 // We were not able to achieve legality by extending the chain.
1015 LLVM_DEBUG(dbgs()
1016 << "LSV: splitChainByAlignment discarding candidate chain "
1017 "because its alignment is not AllowedAndFast: "
1018 << Alignment.value() << "\n");
1019 continue;
1020 }
1021 }
1022
1023 if ((IsLoadChain &&
1024 !TTI.isLegalToVectorizeLoadChain(ChainSizeInBytes: SizeBytes, Alignment, AddrSpace: AS)) ||
1025 (!IsLoadChain &&
1026 !TTI.isLegalToVectorizeStoreChain(ChainSizeInBytes: SizeBytes, Alignment, AddrSpace: AS))) {
1027 LLVM_DEBUG(
1028 dbgs() << "LSV: splitChainByAlignment discarding candidate chain "
1029 "because !isLegalToVectorizeLoad/StoreChain.");
1030 continue;
1031 }
1032
1033 if (CandidateChainsMayContainExtraLoadsStores) {
1034 // If the candidate chain contains extra loads/stores from an earlier
1035 // optimization, confirm legality now. This filter is essential because
1036 // when filling gaps in splitChainByContiguity, we queried the API to
1037 // check that (for a given element type and address space) there *may*
1038 // have been a legal masked load/store we could possibly create. Now, we
1039 // need to check if the actual chain we ended up with is legal to turn
1040 // into a masked load/store. This is relevant for NVPTX, for example,
1041 // where a masked store is only legal if we have ended up with a 256-bit
1042 // vector.
1043 bool CurrCandContainsExtraLoadsStores = llvm::any_of(
1044 Range: ArrayRef<ChainElem>(C).slice(N: CBegin, M: CEnd - CBegin + 1),
1045 P: [this](const ChainElem &E) {
1046 return ExtraElements.contains(V: E.Inst);
1047 });
1048
1049 if (CurrCandContainsExtraLoadsStores &&
1050 (IsLoadChain ? !TTI.isLegalMaskedLoad(
1051 DataType: FixedVectorType::get(ElementType: VecElemTy, NumElts: NumVecElems),
1052 Alignment, AddressSpace: AS, MaskKind: TTI::MaskKind::ConstantMask)
1053 : !TTI.isLegalMaskedStore(
1054 DataType: FixedVectorType::get(ElementType: VecElemTy, NumElts: NumVecElems),
1055 Alignment, AddressSpace: AS, MaskKind: TTI::MaskKind::ConstantMask))) {
1056 LLVM_DEBUG(dbgs()
1057 << "LSV: splitChainByAlignment discarding candidate chain "
1058 "because it contains extra loads/stores that we cannot "
1059 "legally vectorize into a masked load/store \n");
1060 continue;
1061 }
1062 }
1063
1064 // Hooray, we can vectorize this chain!
1065 Chain &NewChain = Ret.emplace_back();
1066 for (unsigned I = CBegin; I <= CEnd; ++I)
1067 NewChain.emplace_back(Args&: C[I]);
1068 for (ChainElem E : ExtendingLoadsStores)
1069 NewChain.emplace_back(Args&: E);
1070 CBegin = CEnd; // Skip over the instructions we've added to the chain.
1071 break;
1072 }
1073 }
1074 return Ret;
1075}
1076
1077bool Vectorizer::vectorizeChain(Chain &C) {
1078 if (C.size() < 2)
1079 return false;
1080
1081 bool ChainContainsExtraLoadsStores = llvm::any_of(
1082 Range&: C, P: [this](const ChainElem &E) { return ExtraElements.contains(V: E.Inst); });
1083
1084 // If we are left with a two-element chain, and one of the elements is an
1085 // extra element, we don't want to vectorize
1086 if (C.size() == 2 && ChainContainsExtraLoadsStores)
1087 return false;
1088
1089 sortChainInOffsetOrder(C);
1090
1091 LLVM_DEBUG({
1092 dbgs() << "LSV: Vectorizing chain of " << C.size() << " instructions:\n";
1093 dumpChain(C);
1094 });
1095
1096 Type *VecElemTy = getChainElemTy(C);
1097 bool IsLoadChain = isa<LoadInst>(Val: C[0].Inst);
1098 unsigned AS = getLoadStoreAddressSpace(I: C[0].Inst);
1099 unsigned BytesAdded = DL.getTypeStoreSize(Ty: getLoadStoreType(I: &*C[0].Inst));
1100 APInt PrevReadEnd = C[0].OffsetFromLeader + BytesAdded;
1101 unsigned ChainBytes = BytesAdded;
1102 for (auto It = std::next(x: C.begin()), End = C.end(); It != End; ++It) {
1103 unsigned SzBytes = DL.getTypeStoreSize(Ty: getLoadStoreType(I: &*It->Inst));
1104 APInt ReadEnd = It->OffsetFromLeader + SzBytes;
1105 // Update ChainBytes considering possible overlap.
1106 BytesAdded =
1107 PrevReadEnd.sle(RHS: ReadEnd) ? (ReadEnd - PrevReadEnd).getSExtValue() : 0;
1108 ChainBytes += BytesAdded;
1109 PrevReadEnd = APIntOps::smax(A: PrevReadEnd, B: ReadEnd);
1110 }
1111
1112 assert(8 * ChainBytes % DL.getTypeSizeInBits(VecElemTy) == 0);
1113 // VecTy is a power of 2 and 1 byte at smallest, but VecElemTy may be smaller
1114 // than 1 byte (e.g. VecTy == <32 x i1>).
1115 unsigned NumElem = 8 * ChainBytes / DL.getTypeSizeInBits(Ty: VecElemTy);
1116 Type *VecTy = FixedVectorType::get(ElementType: VecElemTy, NumElts: NumElem);
1117
1118 Align Alignment = getLoadStoreAlignment(I: C[0].Inst);
1119 // If this is a load/store of an alloca, we might have upgraded the alloca's
1120 // alignment earlier. Get the new alignment.
1121 if (AS == DL.getAllocaAddrSpace()) {
1122 Alignment = std::max(
1123 a: Alignment,
1124 b: getOrEnforceKnownAlignment(V: getLoadStorePointerOperand(V: C[0].Inst),
1125 PrefAlign: MaybeAlign(), DL, CxtI: C[0].Inst, AC: nullptr, DT: &DT));
1126 }
1127
1128 // All elements of the chain must have the same scalar-type size.
1129#ifndef NDEBUG
1130 for (const ChainElem &E : C)
1131 assert(DL.getTypeStoreSize(getLoadStoreType(E.Inst)->getScalarType()) ==
1132 DL.getTypeStoreSize(VecElemTy));
1133#endif
1134
1135 Instruction *VecInst;
1136 if (IsLoadChain) {
1137 // Loads get hoisted to the location of the first load in the chain. We may
1138 // also need to hoist the (transitive) operands of the loads.
1139 Builder.SetInsertPoint(
1140 llvm::min_element(Range&: C, C: [](const auto &A, const auto &B) {
1141 return A.Inst->comesBefore(B.Inst);
1142 })->Inst);
1143
1144 // If the chain contains extra loads, we need to vectorize into a
1145 // masked load.
1146 if (ChainContainsExtraLoadsStores) {
1147 assert(TTI.isLegalMaskedLoad(VecTy, Alignment, AS,
1148 TTI::MaskKind::ConstantMask));
1149 Value *Mask = createMaskForExtraElements(C, VecTy: cast<FixedVectorType>(Val: VecTy));
1150 VecInst = Builder.CreateMaskedLoad(
1151 Ty: VecTy, Ptr: getLoadStorePointerOperand(V: C[0].Inst), Alignment, Mask);
1152 } else {
1153 // This can happen due to a chain of redundant loads.
1154 // In this case, just use the element-type, and avoid ExtractElement.
1155 if (NumElem == 1)
1156 VecTy = VecElemTy;
1157 // Chain is in offset order, so C[0] is the instr with the lowest offset,
1158 // i.e. the root of the vector.
1159 VecInst = Builder.CreateAlignedLoad(
1160 Ty: VecTy, Ptr: getLoadStorePointerOperand(V: C[0].Inst), Align: Alignment);
1161 }
1162
1163 for (const ChainElem &E : C) {
1164 Instruction *I = E.Inst;
1165 Value *V;
1166 Type *T = getLoadStoreType(I);
1167 unsigned EOffset =
1168 (E.OffsetFromLeader - C[0].OffsetFromLeader).getZExtValue();
1169 unsigned VecIdx = 8 * EOffset / DL.getTypeSizeInBits(Ty: VecElemTy);
1170 if (!VecTy->isVectorTy()) {
1171 V = VecInst;
1172 } else if (auto *VT = dyn_cast<FixedVectorType>(Val: T)) {
1173 auto Mask = llvm::to_vector<8>(
1174 Range: llvm::seq<int>(Begin: VecIdx, End: VecIdx + VT->getNumElements()));
1175 V = Builder.CreateShuffleVector(V: VecInst, Mask, Name: I->getName());
1176 } else {
1177 V = Builder.CreateExtractElement(Vec: VecInst, Idx: VecIdx, Name: I->getName());
1178 }
1179 if (V->getType() != I->getType())
1180 V = Builder.CreateBitOrPointerCast(V, DestTy: I->getType());
1181 I->replaceAllUsesWith(V);
1182 }
1183
1184 // Finally, we need to reorder the instrs in the BB so that the (transitive)
1185 // operands of VecInst appear before it. To see why, suppose we have
1186 // vectorized the following code:
1187 //
1188 // ptr1 = gep a, 1
1189 // load1 = load i32 ptr1
1190 // ptr0 = gep a, 0
1191 // load0 = load i32 ptr0
1192 //
1193 // We will put the vectorized load at the location of the earliest load in
1194 // the BB, i.e. load1. We get:
1195 //
1196 // ptr1 = gep a, 1
1197 // loadv = load <2 x i32> ptr0
1198 // load0 = extractelement loadv, 0
1199 // load1 = extractelement loadv, 1
1200 // ptr0 = gep a, 0
1201 //
1202 // Notice that loadv uses ptr0, which is defined *after* it!
1203 reorder(I: VecInst);
1204 } else {
1205 // Stores get sunk to the location of the last store in the chain.
1206 Builder.SetInsertPoint(llvm::max_element(Range&: C, C: [](auto &A, auto &B) {
1207 return A.Inst->comesBefore(B.Inst);
1208 })->Inst);
1209
1210 // Build the vector to store.
1211 Value *Vec = PoisonValue::get(T: VecTy);
1212 auto InsertElem = [&](Value *V, unsigned VecIdx) {
1213 if (V->getType() != VecElemTy)
1214 V = Builder.CreateBitOrPointerCast(V, DestTy: VecElemTy);
1215 Vec = Builder.CreateInsertElement(Vec, NewElt: V, Idx: VecIdx);
1216 };
1217 for (const ChainElem &E : C) {
1218 auto *I = cast<StoreInst>(Val: E.Inst);
1219 unsigned EOffset =
1220 (E.OffsetFromLeader - C[0].OffsetFromLeader).getZExtValue();
1221 unsigned VecIdx = 8 * EOffset / DL.getTypeSizeInBits(Ty: VecElemTy);
1222 if (FixedVectorType *VT =
1223 dyn_cast<FixedVectorType>(Val: getLoadStoreType(I))) {
1224 for (int J = 0, JE = VT->getNumElements(); J < JE; ++J) {
1225 InsertElem(Builder.CreateExtractElement(Vec: I->getValueOperand(), Idx: J),
1226 VecIdx++);
1227 }
1228 } else {
1229 InsertElem(I->getValueOperand(), VecIdx);
1230 }
1231 }
1232
1233 // If the chain originates from extra stores, we need to vectorize into a
1234 // masked store.
1235 if (ChainContainsExtraLoadsStores) {
1236 assert(TTI.isLegalMaskedStore(Vec->getType(), Alignment, AS,
1237 TTI::MaskKind::ConstantMask));
1238 Value *Mask =
1239 createMaskForExtraElements(C, VecTy: cast<FixedVectorType>(Val: Vec->getType()));
1240 VecInst = Builder.CreateMaskedStore(
1241 Val: Vec, Ptr: getLoadStorePointerOperand(V: C[0].Inst), Alignment, Mask);
1242 } else {
1243 // Chain is in offset order, so C[0] is the instr with the lowest offset,
1244 // i.e. the root of the vector.
1245 VecInst = Builder.CreateAlignedStore(
1246 Val: Vec, Ptr: getLoadStorePointerOperand(V: C[0].Inst), Align: Alignment);
1247 }
1248 }
1249
1250 propagateMetadata(I: VecInst, C);
1251
1252 for (const ChainElem &E : C)
1253 ToErase.emplace_back(Args: E.Inst);
1254
1255 ++NumVectorInstructions;
1256 NumScalarsVectorized += C.size();
1257 return true;
1258}
1259
1260template <bool IsLoadChain>
1261bool Vectorizer::isSafeToMove(
1262 Instruction *ChainElem, Instruction *ChainBegin,
1263 const DenseMap<Instruction *, APInt /*OffsetFromLeader*/> &ChainOffsets,
1264 BatchAAResults &BatchAA) {
1265 LLVM_DEBUG(dbgs() << "LSV: isSafeToMove(" << *ChainElem << " -> "
1266 << *ChainBegin << ")\n");
1267
1268 assert(isa<LoadInst>(ChainElem) == IsLoadChain);
1269 if (ChainElem == ChainBegin)
1270 return true;
1271
1272 // Invariant loads can always be reordered; by definition they are not
1273 // clobbered by stores.
1274 if (isInvariantLoad(I: ChainElem))
1275 return true;
1276
1277 auto BBIt = std::next([&] {
1278 if constexpr (IsLoadChain)
1279 return BasicBlock::reverse_iterator(ChainElem);
1280 else
1281 return BasicBlock::iterator(ChainElem);
1282 }());
1283 auto BBItEnd = std::next([&] {
1284 if constexpr (IsLoadChain)
1285 return BasicBlock::reverse_iterator(ChainBegin);
1286 else
1287 return BasicBlock::iterator(ChainBegin);
1288 }());
1289
1290 const APInt &ChainElemOffset = ChainOffsets.at(Val: ChainElem);
1291 const unsigned ChainElemSize =
1292 DL.getTypeStoreSize(Ty: getLoadStoreType(I: ChainElem));
1293
1294 for (; BBIt != BBItEnd; ++BBIt) {
1295 Instruction *I = &*BBIt;
1296
1297 if (!I->mayReadOrWriteMemory())
1298 continue;
1299
1300 // Loads can be reordered with other unordered loads. Ordered atomics
1301 // act as reordering barriers, via getModRefInfo below.
1302 if (auto *LI = dyn_cast<LoadInst>(Val: I);
1303 IsLoadChain && LI && LI->isUnordered())
1304 continue;
1305
1306 // Stores can be sunk below invariant loads.
1307 if (!IsLoadChain && isInvariantLoad(I))
1308 continue;
1309
1310 // If I is in the chain, we can tell whether it aliases ChainIt by checking
1311 // what offset ChainIt accesses. This may be better than AA is able to do.
1312 //
1313 // We should really only have duplicate offsets for stores (the duplicate
1314 // loads should be CSE'ed), but in case we have a duplicate load, we'll
1315 // split the chain so we don't have to handle this case specially.
1316 if (auto OffsetIt = ChainOffsets.find(Val: I); OffsetIt != ChainOffsets.end()) {
1317 // I and ChainElem overlap if:
1318 // - I and ChainElem have the same offset, OR
1319 // - I's offset is less than ChainElem's, but I touches past the
1320 // beginning of ChainElem, OR
1321 // - ChainElem's offset is less than I's, but ChainElem touches past the
1322 // beginning of I.
1323 const APInt &IOffset = OffsetIt->second;
1324 unsigned IElemSize = DL.getTypeStoreSize(Ty: getLoadStoreType(I));
1325 if (IOffset == ChainElemOffset ||
1326 (IOffset.sle(RHS: ChainElemOffset) &&
1327 (IOffset + IElemSize).sgt(RHS: ChainElemOffset)) ||
1328 (ChainElemOffset.sle(RHS: IOffset) &&
1329 (ChainElemOffset + ChainElemSize).sgt(RHS: OffsetIt->second))) {
1330 LLVM_DEBUG({
1331 // Double check that AA also sees this alias. If not, we probably
1332 // have a bug.
1333 ModRefInfo MR =
1334 BatchAA.getModRefInfo(I, MemoryLocation::get(ChainElem));
1335 assert(IsLoadChain ? isModSet(MR) : isModOrRefSet(MR));
1336 dbgs() << "LSV: Found alias in chain: " << *I << "\n";
1337 });
1338 return false; // We found an aliasing instruction; bail.
1339 }
1340
1341 continue; // We're confident there's no alias.
1342 }
1343
1344 LLVM_DEBUG(dbgs() << "LSV: Querying AA for " << *I << "\n");
1345 ModRefInfo MR = BatchAA.getModRefInfo(I, OptLoc: MemoryLocation::get(Inst: ChainElem));
1346 if (IsLoadChain ? isModSet(MRI: MR) : isModOrRefSet(MRI: MR)) {
1347 LLVM_DEBUG(dbgs() << "LSV: Found alias in chain:\n"
1348 << " Aliasing instruction:\n"
1349 << " " << *I << '\n'
1350 << " Aliased instruction and pointer:\n"
1351 << " " << *ChainElem << '\n'
1352 << " " << *getLoadStorePointerOperand(ChainElem)
1353 << '\n');
1354
1355 return false;
1356 }
1357 }
1358 return true;
1359}
1360
1361static bool checkNoWrapFlags(Instruction *I, bool Signed) {
1362 // or disjoint is equivalent to add nuw nsw, so it never wraps.
1363 if (auto *PDI = dyn_cast<PossiblyDisjointInst>(Val: I); PDI && PDI->isDisjoint())
1364 return true;
1365 BinaryOperator *BinOpI = cast<BinaryOperator>(Val: I);
1366 return (Signed && BinOpI->hasNoSignedWrap()) ||
1367 (!Signed && BinOpI->hasNoUnsignedWrap());
1368}
1369
1370/// Check if instruction is an add or an or-disjoint (which is semantically
1371/// equivalent to add nuw nsw).
1372static bool isAddLike(Instruction *I) {
1373 switch (I->getOpcode()) {
1374 default:
1375 break;
1376 case Instruction::Add:
1377 return true;
1378 case Instruction::Or:
1379 if (auto *PDI = dyn_cast<PossiblyDisjointInst>(Val: I))
1380 return PDI->isDisjoint();
1381 break;
1382 }
1383 return false;
1384}
1385
1386static bool checkIfSafeAddSequence(const APInt &IdxDiff, Instruction *AddOpA,
1387 unsigned MatchingOpIdxA, Instruction *AddOpB,
1388 unsigned MatchingOpIdxB, bool Signed) {
1389 LLVM_DEBUG(dbgs() << "LSV: checkIfSafeAddSequence IdxDiff=" << IdxDiff
1390 << ", AddOpA=" << *AddOpA << ", MatchingOpIdxA="
1391 << MatchingOpIdxA << ", AddOpB=" << *AddOpB
1392 << ", MatchingOpIdxB=" << MatchingOpIdxB
1393 << ", Signed=" << Signed << "\n");
1394 // If both OpA and OpB are adds (or or-disjoint) with NSW/NUW and with one of
1395 // the operands being the same, we can guarantee that the transformation is
1396 // safe if we can prove that OpA won't overflow when Ret added to the other
1397 // operand of OpA.
1398 // For example:
1399 // %tmp7 = add nsw i32 %tmp2, %v0
1400 // %tmp8 = sext i32 %tmp7 to i64
1401 // ...
1402 // %tmp11 = add nsw i32 %v0, 1
1403 // %tmp12 = add nsw i32 %tmp2, %tmp11
1404 // %tmp13 = sext i32 %tmp12 to i64
1405 //
1406 // Both %tmp7 and %tmp12 have the nsw flag and the first operand is %tmp2.
1407 // It's guaranteed that adding 1 to %tmp7 won't overflow because %tmp11 adds
1408 // 1 to %v0 and both %tmp11 and %tmp12 have the nsw flag.
1409 assert(isAddLike(AddOpA) && isAddLike(AddOpB) &&
1410 checkNoWrapFlags(AddOpA, Signed) && checkNoWrapFlags(AddOpB, Signed));
1411 if (AddOpA->getOperand(i: MatchingOpIdxA) ==
1412 AddOpB->getOperand(i: MatchingOpIdxB)) {
1413 Value *OtherOperandA = AddOpA->getOperand(i: MatchingOpIdxA == 1 ? 0 : 1);
1414 Value *OtherOperandB = AddOpB->getOperand(i: MatchingOpIdxB == 1 ? 0 : 1);
1415 Instruction *OtherInstrA = dyn_cast<Instruction>(Val: OtherOperandA);
1416 Instruction *OtherInstrB = dyn_cast<Instruction>(Val: OtherOperandB);
1417 // Match `x +nsw/nuw y` and `x +nsw/nuw (y +nsw/nuw IdxDiff)`.
1418 if (OtherInstrB && isAddLike(I: OtherInstrB) &&
1419 checkNoWrapFlags(I: OtherInstrB, Signed) &&
1420 isa<ConstantInt>(Val: OtherInstrB->getOperand(i: 1))) {
1421 int64_t CstVal =
1422 cast<ConstantInt>(Val: OtherInstrB->getOperand(i: 1))->getSExtValue();
1423 if (OtherInstrB->getOperand(i: 0) == OtherOperandA &&
1424 IdxDiff.getSExtValue() == CstVal)
1425 return true;
1426 }
1427 // Match `x +nsw/nuw (y +nsw/nuw -Idx)` and `x +nsw/nuw (y +nsw/nuw x)`.
1428 if (OtherInstrA && isAddLike(I: OtherInstrA) &&
1429 checkNoWrapFlags(I: OtherInstrA, Signed) &&
1430 isa<ConstantInt>(Val: OtherInstrA->getOperand(i: 1))) {
1431 int64_t CstVal =
1432 cast<ConstantInt>(Val: OtherInstrA->getOperand(i: 1))->getSExtValue();
1433 if (OtherInstrA->getOperand(i: 0) == OtherOperandB &&
1434 IdxDiff.getSExtValue() == -CstVal)
1435 return true;
1436 }
1437 // Match `x +nsw/nuw (y +nsw/nuw c)` and
1438 // `x +nsw/nuw (y +nsw/nuw (c + IdxDiff))`.
1439 if (OtherInstrA && OtherInstrB && isAddLike(I: OtherInstrA) &&
1440 isAddLike(I: OtherInstrB) && checkNoWrapFlags(I: OtherInstrA, Signed) &&
1441 checkNoWrapFlags(I: OtherInstrB, Signed) &&
1442 isa<ConstantInt>(Val: OtherInstrA->getOperand(i: 1)) &&
1443 isa<ConstantInt>(Val: OtherInstrB->getOperand(i: 1))) {
1444 int64_t CstValA =
1445 cast<ConstantInt>(Val: OtherInstrA->getOperand(i: 1))->getSExtValue();
1446 int64_t CstValB =
1447 cast<ConstantInt>(Val: OtherInstrB->getOperand(i: 1))->getSExtValue();
1448 if (OtherInstrA->getOperand(i: 0) == OtherInstrB->getOperand(i: 0) &&
1449 IdxDiff.getSExtValue() == (CstValB - CstValA))
1450 return true;
1451 }
1452 }
1453 return false;
1454}
1455
1456std::optional<APInt> Vectorizer::getConstantOffsetComplexAddrs(
1457 Value *PtrA, Value *PtrB, Instruction *ContextInst, unsigned Depth) {
1458 LLVM_DEBUG(dbgs() << "LSV: getConstantOffsetComplexAddrs PtrA=" << *PtrA
1459 << " PtrB=" << *PtrB << " ContextInst=" << *ContextInst
1460 << " Depth=" << Depth << "\n");
1461 auto *GEPA = dyn_cast<GetElementPtrInst>(Val: PtrA);
1462 auto *GEPB = dyn_cast<GetElementPtrInst>(Val: PtrB);
1463 if (!GEPA || !GEPB)
1464 return getConstantOffsetSelects(PtrA, PtrB, ContextInst, Depth);
1465
1466 // Look through GEPs after checking they're the same except for the last
1467 // index.
1468 if (GEPA->getNumOperands() != GEPB->getNumOperands() ||
1469 GEPA->getPointerOperand() != GEPB->getPointerOperand() ||
1470 GEPA->getSourceElementType() != GEPB->getSourceElementType())
1471 return std::nullopt;
1472 gep_type_iterator GTIA = gep_type_begin(GEP: GEPA);
1473 gep_type_iterator GTIB = gep_type_begin(GEP: GEPB);
1474 for (unsigned I = 0, E = GEPA->getNumIndices() - 1; I < E; ++I) {
1475 if (GTIA.getOperand() != GTIB.getOperand())
1476 return std::nullopt;
1477 ++GTIA;
1478 ++GTIB;
1479 }
1480
1481 Instruction *OpA = dyn_cast<Instruction>(Val: GTIA.getOperand());
1482 Instruction *OpB = dyn_cast<Instruction>(Val: GTIB.getOperand());
1483 if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() ||
1484 OpA->getType() != OpB->getType())
1485 return std::nullopt;
1486
1487 uint64_t Stride = GTIA.getSequentialElementStride(DL);
1488
1489 // Only look through a ZExt/SExt.
1490 if (!isa<SExtInst>(Val: OpA) && !isa<ZExtInst>(Val: OpA))
1491 return std::nullopt;
1492
1493 bool Signed = isa<SExtInst>(Val: OpA);
1494
1495 // At this point A could be a function parameter, i.e. not an instruction
1496 Value *ValA = OpA->getOperand(i: 0);
1497 OpB = dyn_cast<Instruction>(Val: OpB->getOperand(i: 0));
1498 if (!OpB || ValA->getType() != OpB->getType())
1499 return std::nullopt;
1500
1501 const SCEV *OffsetSCEVA = SE.getSCEV(V: ValA);
1502 const SCEV *OffsetSCEVB = SE.getSCEV(V: OpB);
1503 const SCEV *IdxDiffSCEV = SE.getMinusSCEV(LHS: OffsetSCEVB, RHS: OffsetSCEVA);
1504 if (IdxDiffSCEV == SE.getCouldNotCompute())
1505 return std::nullopt;
1506
1507 ConstantRange IdxDiffRange = SE.getSignedRange(S: IdxDiffSCEV);
1508 if (!IdxDiffRange.isSingleElement())
1509 return std::nullopt;
1510 APInt IdxDiff = *IdxDiffRange.getSingleElement();
1511
1512 LLVM_DEBUG(dbgs() << "LSV: getConstantOffsetComplexAddrs IdxDiff=" << IdxDiff
1513 << "\n");
1514
1515 // Now we need to prove that adding IdxDiff to ValA won't overflow.
1516 bool Safe = false;
1517
1518 // First attempt: if OpB is an add (or or-disjoint) with NSW/NUW, and OpB is
1519 // IdxDiff added to ValA, we're okay.
1520 if (isAddLike(I: OpB) && isa<ConstantInt>(Val: OpB->getOperand(i: 1)) &&
1521 IdxDiff.sle(RHS: cast<ConstantInt>(Val: OpB->getOperand(i: 1))->getSExtValue()) &&
1522 checkNoWrapFlags(I: OpB, Signed))
1523 Safe = true;
1524
1525 // Second attempt: check if we have eligible add NSW/NUW instruction
1526 // sequences.
1527 OpA = dyn_cast<Instruction>(Val: ValA);
1528 if (!Safe && OpA && isAddLike(I: OpA) && isAddLike(I: OpB) &&
1529 checkNoWrapFlags(I: OpA, Signed) && checkNoWrapFlags(I: OpB, Signed)) {
1530 // In the checks below a matching operand in OpA and OpB is an operand which
1531 // is the same in those two instructions. Below we account for possible
1532 // orders of the operands of these add instructions.
1533 for (unsigned MatchingOpIdxA : {0, 1})
1534 for (unsigned MatchingOpIdxB : {0, 1})
1535 if (!Safe)
1536 Safe = checkIfSafeAddSequence(IdxDiff, AddOpA: OpA, MatchingOpIdxA, AddOpB: OpB,
1537 MatchingOpIdxB, Signed);
1538 }
1539
1540 unsigned BitWidth = ValA->getType()->getScalarSizeInBits();
1541
1542 // Third attempt:
1543 //
1544 // Assuming IdxDiff is positive: If all set bits of IdxDiff or any higher
1545 // order bit other than the sign bit are known to be zero in ValA, we can add
1546 // Diff to it while guaranteeing no overflow of any sort.
1547 //
1548 // If IdxDiff is negative, do the same, but swap ValA and ValB.
1549 if (!Safe) {
1550 // When computing known bits, use the GEPs as context instructions, since
1551 // they likely are in the same BB as the load/store.
1552 KnownBits Known(BitWidth);
1553 computeKnownBits(V: (IdxDiff.sge(RHS: 0) ? ValA : OpB), Known, DL, AC: &AC, CxtI: ContextInst,
1554 DT: &DT);
1555 APInt BitsAllowedToBeSet = Known.Zero.zext(width: IdxDiff.getBitWidth());
1556 if (Signed)
1557 BitsAllowedToBeSet.clearBit(BitPosition: BitWidth - 1);
1558 Safe = BitsAllowedToBeSet.uge(RHS: IdxDiff.abs());
1559 }
1560
1561 // Fourth attempt: use SCEV unsigned range to prove that adding IdxDiff
1562 // to ValA won't cause unsigned overflow (which would make zext produce
1563 // a different difference). This handles cases where KnownBits analysis
1564 // can't determine safety but SCEV has tighter range information.
1565 if (!Safe && !Signed) {
1566 Value *CheckVal = IdxDiff.sge(RHS: 0) ? ValA : OpB;
1567 ConstantRange CR = SE.getUnsignedRange(S: SE.getSCEV(V: CheckVal));
1568 APInt AbsDiff = IdxDiff.abs().zextOrTrunc(width: BitWidth);
1569 APInt Limit = APInt::getMaxValue(numBits: BitWidth) - AbsDiff;
1570 Safe = CR.getUnsignedMax().ule(RHS: Limit);
1571 }
1572
1573 if (Safe)
1574 return IdxDiff * Stride;
1575 return std::nullopt;
1576}
1577
1578std::optional<APInt> Vectorizer::getConstantOffsetSelects(
1579 Value *PtrA, Value *PtrB, Instruction *ContextInst, unsigned Depth) {
1580 if (Depth++ == MaxDepth)
1581 return std::nullopt;
1582
1583 if (auto *SelectA = dyn_cast<SelectInst>(Val: PtrA)) {
1584 if (auto *SelectB = dyn_cast<SelectInst>(Val: PtrB)) {
1585 if (SelectA->getCondition() != SelectB->getCondition())
1586 return std::nullopt;
1587 LLVM_DEBUG(dbgs() << "LSV: getConstantOffsetSelects, PtrA=" << *PtrA
1588 << ", PtrB=" << *PtrB << ", ContextInst="
1589 << *ContextInst << ", Depth=" << Depth << "\n");
1590 std::optional<APInt> TrueDiff = getConstantOffset(
1591 PtrA: SelectA->getTrueValue(), PtrB: SelectB->getTrueValue(), ContextInst, Depth);
1592 if (!TrueDiff)
1593 return std::nullopt;
1594 std::optional<APInt> FalseDiff =
1595 getConstantOffset(PtrA: SelectA->getFalseValue(), PtrB: SelectB->getFalseValue(),
1596 ContextInst, Depth);
1597 if (TrueDiff == FalseDiff)
1598 return TrueDiff;
1599 }
1600 }
1601 return std::nullopt;
1602}
1603
1604void Vectorizer::mergeEquivalenceClasses(EquivalenceClassMap &EQClasses) const {
1605 if (EQClasses.size() < 2) // There is nothing to merge.
1606 return;
1607
1608 // The reduced key has all elements of the ECClassKey except the underlying
1609 // object. Check that EqClassKey has 4 elements and define the reduced key.
1610 static_assert(std::tuple_size_v<EqClassKey> == 4,
1611 "EqClassKey has changed - EqClassReducedKey needs changes too");
1612 using EqClassReducedKey =
1613 std::tuple<std::tuple_element_t<1, EqClassKey> /* AddrSpace */,
1614 std::tuple_element_t<2, EqClassKey> /* Element size */,
1615 std::tuple_element_t<3, EqClassKey> /* IsLoad; */>;
1616 using ECReducedKeyToUnderlyingObjectMap =
1617 MapVector<EqClassReducedKey,
1618 SmallPtrSet<std::tuple_element_t<0, EqClassKey>, 4>>;
1619
1620 // Form a map from the reduced key (without the underlying object) to the
1621 // underlying objects: 1 reduced key to many underlying objects, to form
1622 // groups of potentially merge-able equivalence classes.
1623 ECReducedKeyToUnderlyingObjectMap RedKeyToUOMap;
1624 bool FoundPotentiallyOptimizableEC = false;
1625 for (const auto &EC : EQClasses) {
1626 const auto &Key = EC.first;
1627 EqClassReducedKey RedKey{std::get<1>(t: Key), std::get<2>(t: Key),
1628 std::get<3>(t: Key)};
1629 auto &UOMap = RedKeyToUOMap[RedKey];
1630 UOMap.insert(Ptr: std::get<0>(t: Key));
1631 if (UOMap.size() > 1)
1632 FoundPotentiallyOptimizableEC = true;
1633 }
1634 if (!FoundPotentiallyOptimizableEC)
1635 return;
1636
1637 LLVM_DEBUG({
1638 dbgs() << "LSV: mergeEquivalenceClasses: before merging:\n";
1639 for (const auto &EC : EQClasses) {
1640 dbgs() << " Key: {" << EC.first << "}\n";
1641 for (const auto &Inst : EC.second)
1642 dbgs() << " Inst: " << *Inst << '\n';
1643 }
1644 });
1645 LLVM_DEBUG({
1646 dbgs() << "LSV: mergeEquivalenceClasses: RedKeyToUOMap:\n";
1647 for (const auto &RedKeyToUO : RedKeyToUOMap) {
1648 dbgs() << " Reduced key: {" << std::get<0>(RedKeyToUO.first) << ", "
1649 << std::get<1>(RedKeyToUO.first) << ", "
1650 << static_cast<int>(std::get<2>(RedKeyToUO.first)) << "} --> "
1651 << RedKeyToUO.second.size() << " underlying objects:\n";
1652 for (auto UObject : RedKeyToUO.second)
1653 dbgs() << " " << *UObject << '\n';
1654 }
1655 });
1656
1657 using UObjectToUObjectMap = DenseMap<const Value *, const Value *>;
1658
1659 // Compute the ultimate targets for a set of underlying objects.
1660 auto GetUltimateTargets =
1661 [](SmallPtrSetImpl<const Value *> &UObjects) -> UObjectToUObjectMap {
1662 UObjectToUObjectMap IndirectionMap;
1663 for (const auto *UObject : UObjects) {
1664 const unsigned MaxLookupDepth = 1; // look for 1-level indirections only
1665 const auto *UltimateTarget = getUnderlyingObject(V: UObject, MaxLookup: MaxLookupDepth);
1666 if (UltimateTarget != UObject)
1667 IndirectionMap[UObject] = UltimateTarget;
1668 }
1669 UObjectToUObjectMap UltimateTargetsMap;
1670 for (const auto *UObject : UObjects) {
1671 auto Target = UObject;
1672 auto It = IndirectionMap.find(Val: Target);
1673 for (; It != IndirectionMap.end(); It = IndirectionMap.find(Val: Target))
1674 Target = It->second;
1675 UltimateTargetsMap[UObject] = Target;
1676 }
1677 return UltimateTargetsMap;
1678 };
1679
1680 // For each item in RedKeyToUOMap, if it has more than one underlying object,
1681 // try to merge the equivalence classes.
1682 for (auto &[RedKey, UObjects] : RedKeyToUOMap) {
1683 if (UObjects.size() < 2)
1684 continue;
1685 auto UTMap = GetUltimateTargets(UObjects);
1686 for (const auto &[UObject, UltimateTarget] : UTMap) {
1687 if (UObject == UltimateTarget)
1688 continue;
1689
1690 EqClassKey KeyFrom{UObject, std::get<0>(t&: RedKey), std::get<1>(t&: RedKey),
1691 std::get<2>(t&: RedKey)};
1692 EqClassKey KeyTo{UltimateTarget, std::get<0>(t&: RedKey), std::get<1>(t&: RedKey),
1693 std::get<2>(t&: RedKey)};
1694 // The entry for KeyFrom is guarantted to exist, unlike KeyTo. Thus,
1695 // request the reference to the instructions vector for KeyTo first.
1696 const auto &VecTo = EQClasses[KeyTo];
1697 const auto &VecFrom = EQClasses[KeyFrom];
1698 SmallVector<Instruction *, 8> MergedVec;
1699 std::merge(first1: VecFrom.begin(), last1: VecFrom.end(), first2: VecTo.begin(), last2: VecTo.end(),
1700 result: std::back_inserter(x&: MergedVec),
1701 comp: [](Instruction *A, Instruction *B) {
1702 return A && B && A->comesBefore(Other: B);
1703 });
1704 EQClasses[KeyTo] = std::move(MergedVec);
1705 EQClasses.erase(Key: KeyFrom);
1706 }
1707 }
1708 LLVM_DEBUG({
1709 dbgs() << "LSV: mergeEquivalenceClasses: after merging:\n";
1710 for (const auto &EC : EQClasses) {
1711 dbgs() << " Key: {" << EC.first << "}\n";
1712 for (const auto &Inst : EC.second)
1713 dbgs() << " Inst: " << *Inst << '\n';
1714 }
1715 });
1716}
1717
1718EquivalenceClassMap
1719Vectorizer::collectEquivalenceClasses(BasicBlock::iterator Begin,
1720 BasicBlock::iterator End) {
1721 EquivalenceClassMap Ret;
1722
1723 auto GetUnderlyingObject = [](const Value *Ptr) -> const Value * {
1724 const Value *ObjPtr = llvm::getUnderlyingObject(V: Ptr);
1725 if (const auto *Sel = dyn_cast<SelectInst>(Val: ObjPtr)) {
1726 // The select's themselves are distinct instructions even if they share
1727 // the same condition and evaluate to consecutive pointers for true and
1728 // false values of the condition. Therefore using the select's themselves
1729 // for grouping instructions would put consecutive accesses into different
1730 // lists and they won't be even checked for being consecutive, and won't
1731 // be vectorized.
1732 return Sel->getCondition();
1733 }
1734 return ObjPtr;
1735 };
1736
1737 for (Instruction &I : make_range(x: Begin, y: End)) {
1738 auto *LI = dyn_cast<LoadInst>(Val: &I);
1739 auto *SI = dyn_cast<StoreInst>(Val: &I);
1740 if (!LI && !SI)
1741 continue;
1742
1743 if ((LI && !LI->isSimple()) || (SI && !SI->isSimple()))
1744 continue;
1745
1746 if ((LI && !TTI.isLegalToVectorizeLoad(LI)) ||
1747 (SI && !TTI.isLegalToVectorizeStore(SI)))
1748 continue;
1749
1750 Type *Ty = getLoadStoreType(I: &I);
1751 if (!VectorType::isValidElementType(ElemTy: Ty->getScalarType()))
1752 continue;
1753
1754 // Pointer loads and stores with external state must retain their pointer
1755 // memory type so the out-of-band state is transferred. Do not vectorize
1756 // these pointers.
1757 if (DL.hasExternalState(Ty))
1758 continue;
1759
1760 // Skip weird non-byte sizes. They probably aren't worth the effort of
1761 // handling correctly.
1762 unsigned TySize = DL.getTypeSizeInBits(Ty);
1763 if ((TySize % 8) != 0)
1764 continue;
1765
1766 // Skip vectors of pointers. The vectorizeLoadChain/vectorizeStoreChain
1767 // functions are currently using an integer type for the vectorized
1768 // load/store, and does not support casting between the integer type and a
1769 // vector of pointers (e.g. i64 to <2 x i16*>)
1770 if (Ty->isVectorTy() && Ty->isPtrOrPtrVectorTy())
1771 continue;
1772
1773 Value *Ptr = getLoadStorePointerOperand(V: &I);
1774 unsigned AS = Ptr->getType()->getPointerAddressSpace();
1775 unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AddrSpace: AS);
1776
1777 unsigned VF = VecRegSize / TySize;
1778 VectorType *VecTy = dyn_cast<VectorType>(Val: Ty);
1779
1780 // Only handle power-of-two sized elements.
1781 if ((!VecTy && !isPowerOf2_32(Value: DL.getTypeSizeInBits(Ty))) ||
1782 (VecTy && !isPowerOf2_32(Value: DL.getTypeSizeInBits(Ty: VecTy->getScalarType()))))
1783 continue;
1784
1785 // No point in looking at these if they're too big to vectorize.
1786 if (TySize > VecRegSize / 2 ||
1787 (VecTy && TTI.getLoadVectorFactor(VF, LoadSize: TySize, ChainSizeInBytes: TySize / 8, VecTy) == 0))
1788 continue;
1789
1790 Ret[{GetUnderlyingObject(Ptr), AS,
1791 DL.getTypeSizeInBits(Ty: getLoadStoreType(I: &I)->getScalarType()),
1792 /*IsLoad=*/LI != nullptr}]
1793 .emplace_back(Args: &I);
1794 }
1795
1796 mergeEquivalenceClasses(EQClasses&: Ret);
1797 return Ret;
1798}
1799
1800std::vector<Chain> Vectorizer::gatherChains(ArrayRef<Instruction *> Instrs) {
1801 if (Instrs.empty())
1802 return {};
1803
1804 unsigned AS = getLoadStoreAddressSpace(I: Instrs[0]);
1805 unsigned ASPtrBits = DL.getIndexSizeInBits(AS);
1806
1807#ifndef NDEBUG
1808 // Check that Instrs is in BB order and all have the same addr space.
1809 for (size_t I = 1; I < Instrs.size(); ++I) {
1810 assert(Instrs[I - 1]->comesBefore(Instrs[I]));
1811 assert(getLoadStoreAddressSpace(Instrs[I]) == AS);
1812 }
1813#endif
1814
1815 // Machinery to build an MRU-hashtable of Chains.
1816 //
1817 // (Ideally this could be done with MapVector, but as currently implemented,
1818 // moving an element to the front of a MapVector is O(n).)
1819 struct InstrListElem : ilist_node<InstrListElem>,
1820 std::pair<Instruction *, Chain> {
1821 explicit InstrListElem(Instruction *I)
1822 : std::pair<Instruction *, Chain>(I, {}) {}
1823 };
1824 struct InstrListElemDenseMapInfo {
1825 using IInfo = DenseMapInfo<Instruction *>;
1826 static unsigned getHashValue(const InstrListElem *E) {
1827 return IInfo::getHashValue(PtrVal: E->first);
1828 }
1829 static bool isEqual(const InstrListElem *A, const InstrListElem *B) {
1830 return IInfo::isEqual(LHS: A->first, RHS: B->first);
1831 }
1832 };
1833 SpecificBumpPtrAllocator<InstrListElem> Allocator;
1834 simple_ilist<InstrListElem> MRU;
1835 DenseSet<InstrListElem *, InstrListElemDenseMapInfo> Chains;
1836
1837 // Compare each instruction in `instrs` to leader of the N most recently-used
1838 // chains. This limits the O(n^2) behavior of this pass while also allowing
1839 // us to build arbitrarily long chains.
1840 for (Instruction *I : Instrs) {
1841 constexpr int MaxChainsToTry = 64;
1842
1843 bool MatchFound = false;
1844 auto ChainIter = MRU.begin();
1845 for (size_t J = 0; J < MaxChainsToTry && ChainIter != MRU.end();
1846 ++J, ++ChainIter) {
1847 if (std::optional<APInt> Offset = getConstantOffset(
1848 PtrA: getLoadStorePointerOperand(V: ChainIter->first),
1849 PtrB: getLoadStorePointerOperand(V: I),
1850 /*ContextInst=*/
1851 (ChainIter->first->comesBefore(Other: I) ? I : ChainIter->first))) {
1852 // `Offset` might not have the expected number of bits, if e.g. AS has a
1853 // different number of bits than opaque pointers.
1854 ChainIter->second.emplace_back(Args&: I, Args&: Offset.value());
1855 // Move ChainIter to the front of the MRU list.
1856 MRU.remove(N&: *ChainIter);
1857 MRU.push_front(Node&: *ChainIter);
1858 MatchFound = true;
1859 break;
1860 }
1861 }
1862
1863 if (!MatchFound) {
1864 APInt ZeroOffset(ASPtrBits, 0);
1865 InstrListElem *E = new (Allocator.Allocate()) InstrListElem(I);
1866 E->second.emplace_back(Args&: I, Args&: ZeroOffset);
1867 MRU.push_front(Node&: *E);
1868 Chains.insert(V: E);
1869 }
1870 }
1871
1872 std::vector<Chain> Ret;
1873 Ret.reserve(n: Chains.size());
1874 // Iterate over MRU rather than Chains so the order is deterministic.
1875 for (auto &E : MRU)
1876 if (E.second.size() > 1)
1877 Ret.emplace_back(args: std::move(E.second));
1878 return Ret;
1879}
1880
1881std::optional<APInt> Vectorizer::getConstantOffset(Value *PtrA, Value *PtrB,
1882 Instruction *ContextInst,
1883 unsigned Depth) {
1884 LLVM_DEBUG(dbgs() << "LSV: getConstantOffset, PtrA=" << *PtrA
1885 << ", PtrB=" << *PtrB << ", ContextInst= " << *ContextInst
1886 << ", Depth=" << Depth << "\n");
1887 // We'll ultimately return a value of this bit width, even if computations
1888 // happen in a different width.
1889 unsigned OrigBitWidth = DL.getIndexTypeSizeInBits(Ty: PtrA->getType());
1890 APInt OffsetA(OrigBitWidth, 0);
1891 APInt OffsetB(OrigBitWidth, 0);
1892 PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, Offset&: OffsetA);
1893 PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, Offset&: OffsetB);
1894 unsigned NewPtrBitWidth = DL.getTypeStoreSizeInBits(Ty: PtrA->getType());
1895 if (NewPtrBitWidth != DL.getTypeStoreSizeInBits(Ty: PtrB->getType()))
1896 return std::nullopt;
1897
1898 // If we have to shrink the pointer, stripAndAccumulateInBoundsConstantOffsets
1899 // should properly handle a possible overflow and the value should fit into
1900 // the smallest data type used in the cast/gep chain.
1901 assert(OffsetA.getSignificantBits() <= NewPtrBitWidth &&
1902 OffsetB.getSignificantBits() <= NewPtrBitWidth);
1903
1904 OffsetA = OffsetA.sextOrTrunc(width: NewPtrBitWidth);
1905 OffsetB = OffsetB.sextOrTrunc(width: NewPtrBitWidth);
1906 if (PtrA == PtrB)
1907 return (OffsetB - OffsetA).sextOrTrunc(width: OrigBitWidth);
1908
1909 // Try to compute B - A.
1910 const SCEV *DistScev = SE.getMinusSCEV(LHS: SE.getSCEV(V: PtrB), RHS: SE.getSCEV(V: PtrA));
1911 if (DistScev != SE.getCouldNotCompute()) {
1912 LLVM_DEBUG(dbgs() << "LSV: SCEV PtrB - PtrA =" << *DistScev << "\n");
1913 ConstantRange DistRange = SE.getSignedRange(S: DistScev);
1914 if (DistRange.isSingleElement()) {
1915 // Handle index width (the width of Dist) != pointer width (the width of
1916 // the Offset*s at this point).
1917 APInt Dist = DistRange.getSingleElement()->sextOrTrunc(width: NewPtrBitWidth);
1918 return (OffsetB - OffsetA + Dist).sextOrTrunc(width: OrigBitWidth);
1919 }
1920 }
1921 if (std::optional<APInt> Diff =
1922 getConstantOffsetComplexAddrs(PtrA, PtrB, ContextInst, Depth))
1923 return (OffsetB - OffsetA + Diff->sext(width: OffsetB.getBitWidth()))
1924 .sextOrTrunc(width: OrigBitWidth);
1925 return std::nullopt;
1926}
1927
1928bool Vectorizer::accessIsAllowedAndFast(unsigned SizeBytes, unsigned AS,
1929 Align Alignment,
1930 unsigned VecElemBits) const {
1931 // Aligned vector accesses are ALWAYS faster than element-wise accesses.
1932 if (Alignment.value() % SizeBytes == 0)
1933 return true;
1934
1935 // Ask TTI whether misaligned accesses are faster as vector or element-wise.
1936 unsigned VectorizedSpeed = 0;
1937 bool AllowsMisaligned = TTI.allowsMisalignedMemoryAccesses(
1938 Context&: F.getContext(), BitWidth: SizeBytes * 8, AddressSpace: AS, Alignment, Fast: &VectorizedSpeed);
1939 if (!AllowsMisaligned) {
1940 LLVM_DEBUG(
1941 dbgs() << "LSV: Access of " << SizeBytes << "B in addrspace " << AS
1942 << " with alignment " << Alignment.value()
1943 << " is misaligned, and therefore can't be vectorized.\n");
1944 return false;
1945 }
1946
1947 unsigned ElementwiseSpeed = 0;
1948 (TTI).allowsMisalignedMemoryAccesses(Context&: (F).getContext(), BitWidth: VecElemBits, AddressSpace: AS,
1949 Alignment, Fast: &ElementwiseSpeed);
1950 if (VectorizedSpeed < ElementwiseSpeed) {
1951 LLVM_DEBUG(dbgs() << "LSV: Access of " << SizeBytes << "B in addrspace "
1952 << AS << " with alignment " << Alignment.value()
1953 << " has relative speed " << VectorizedSpeed
1954 << ", which is lower than the elementwise speed of "
1955 << ElementwiseSpeed
1956 << ". Therefore this access won't be vectorized.\n");
1957 return false;
1958 }
1959 return true;
1960}
1961
1962ChainElem Vectorizer::createExtraElementAfter(const ChainElem &Prev, Type *Ty,
1963 APInt Offset, StringRef Prefix,
1964 Align Alignment) {
1965 Instruction *NewElement = nullptr;
1966 Builder.SetInsertPoint(Prev.Inst->getNextNode());
1967 if (LoadInst *PrevLoad = dyn_cast<LoadInst>(Val: Prev.Inst)) {
1968 Value *NewGep = Builder.CreatePtrAdd(
1969 Ptr: PrevLoad->getPointerOperand(), Offset: Builder.getInt(AI: Offset), Name: Prefix + "GEP");
1970 LLVM_DEBUG(dbgs() << "LSV: Extra GEP Created: \n" << *NewGep << "\n");
1971 NewElement = Builder.CreateAlignedLoad(Ty, Ptr: NewGep, Align: Alignment, Name: Prefix);
1972 } else {
1973 StoreInst *PrevStore = cast<StoreInst>(Val: Prev.Inst);
1974
1975 Value *NewGep = Builder.CreatePtrAdd(
1976 Ptr: PrevStore->getPointerOperand(), Offset: Builder.getInt(AI: Offset), Name: Prefix + "GEP");
1977 LLVM_DEBUG(dbgs() << "LSV: Extra GEP Created: \n" << *NewGep << "\n");
1978 NewElement =
1979 Builder.CreateAlignedStore(Val: PoisonValue::get(T: Ty), Ptr: NewGep, Align: Alignment);
1980 }
1981
1982 // Attach all metadata to the new element.
1983 // propagateMetadata will fold it into the final vector when applicable.
1984 NewElement->copyMetadata(SrcInst: *Prev.Inst);
1985
1986 // Cache created elements for tracking and cleanup
1987 ExtraElements.insert(V: NewElement);
1988
1989 APInt NewOffsetFromLeader = Prev.OffsetFromLeader + Offset;
1990 LLVM_DEBUG(dbgs() << "LSV: Extra Element Created: \n"
1991 << *NewElement
1992 << " OffsetFromLeader: " << NewOffsetFromLeader << "\n");
1993 return ChainElem{NewElement, NewOffsetFromLeader};
1994}
1995
1996Value *Vectorizer::createMaskForExtraElements(const ArrayRef<ChainElem> C,
1997 FixedVectorType *VecTy) {
1998 // Start each mask element as false
1999 SmallVector<Constant *, 64> MaskElts(VecTy->getNumElements(),
2000 Builder.getInt1(V: false));
2001 // Iterate over the chain and set the corresponding mask element to true for
2002 // each element that is not an extra element.
2003 for (const ChainElem &E : C) {
2004 if (ExtraElements.contains(V: E.Inst))
2005 continue;
2006 unsigned EOffset =
2007 (E.OffsetFromLeader - C[0].OffsetFromLeader).getZExtValue();
2008 unsigned VecIdx =
2009 8 * EOffset / DL.getTypeSizeInBits(Ty: VecTy->getScalarType());
2010 if (FixedVectorType *VT =
2011 dyn_cast<FixedVectorType>(Val: getLoadStoreType(I: E.Inst)))
2012 for (unsigned J = 0; J < VT->getNumElements(); ++J)
2013 MaskElts[VecIdx + J] = Builder.getInt1(V: true);
2014 else
2015 MaskElts[VecIdx] = Builder.getInt1(V: true);
2016 }
2017 return ConstantVector::get(V: MaskElts);
2018}
2019
2020void Vectorizer::deleteExtraElements() {
2021 for (auto *ExtraElement : ExtraElements) {
2022 if (isa<LoadInst>(Val: ExtraElement)) {
2023 [[maybe_unused]] bool Deleted =
2024 RecursivelyDeleteTriviallyDeadInstructions(V: ExtraElement);
2025 assert(Deleted && "Extra Load should always be trivially dead");
2026 } else {
2027 // Unlike Extra Loads, Extra Stores won't be "dead", but should all be
2028 // deleted regardless. They will have either been combined into a masked
2029 // store, or will be left behind and need to be cleaned up.
2030 auto *PtrOperand = getLoadStorePointerOperand(V: ExtraElement);
2031 ExtraElement->eraseFromParent();
2032 RecursivelyDeleteTriviallyDeadInstructions(V: PtrOperand);
2033 }
2034 }
2035
2036 ExtraElements.clear();
2037}
2038