1//===- LoadStoreVec.cpp - Vectorizer pass short load-store chains ---------===//
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#include "llvm/Transforms/Vectorize/SandboxVectorizer/Passes/LoadStoreVec.h"
10#include "../../VectorizeOptions.h"
11#include "llvm/ADT/STLExtras.h"
12#include "llvm/SandboxIR/Constant.h"
13#include "llvm/SandboxIR/Instruction.h"
14#include "llvm/SandboxIR/Module.h"
15#include "llvm/SandboxIR/Region.h"
16#include "llvm/Support/InstructionCost.h"
17#include "llvm/Transforms/Vectorize/SandboxVectorizer/Debug.h"
18#include "llvm/Transforms/Vectorize/SandboxVectorizer/Legality.h"
19#include "llvm/Transforms/Vectorize/SandboxVectorizer/RegionWithScore.h"
20#include "llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h"
21
22namespace llvm {
23
24namespace sandboxir {
25
26#define DEBUG_PREFIX_LOCAL DEBUG_PREFIX "LoadStoreVec: "
27
28/// \returns true if \p Ty is a pointer, or a vector of pointers, in a
29/// non-integral address space, which has no stable integer representation.
30static bool isNonIntegralPtr(Type *Ty, const DataLayout &DL) {
31 Type *ScalarTy = Ty->getScalarType();
32 return ScalarTy->isPointerTy() &&
33 DL.isNonIntegralAddressSpace(AddrSpace: ScalarTy->getPointerAddressSpace());
34}
35
36std::optional<Type *> LoadStoreVec::canVectorize(BndlRef<Instruction *> Bndl) {
37 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "canVectorize() Bundle:\n";
38 VecUtils::dump(Bndl));
39 const auto &LegalityRes = Legality->canVectorizeLSV(Bndl);
40 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Legality: " << LegalityRes << "\n");
41
42 if (LegalityRes.getSubclassID() != LegalityResultID::Widen)
43 return std::nullopt;
44 return VecUtils::getCombinedVectorTypeFor(Bndl, DL: *DL);
45}
46
47void LoadStoreVec::saveIR(Region &R) {
48 Rgn = &R;
49 const auto &SB = cast<RegionWithScore>(Val: Rgn)->getScoreboard();
50 CostBefore = SB.getAfterCost() - SB.getBeforeCost();
51 Rgn->getContext().save();
52}
53
54bool LoadStoreVec::acceptOrRevert() {
55 const auto &SB = cast<RegionWithScore>(Val&: *Rgn).getScoreboard();
56 InstructionCost CostAfter = SB.getAfterCost() - SB.getBeforeCost();
57 InstructionCost CostGain = CostAfter - CostBefore;
58 LLVM_DEBUG(dbgs() << DEBUG_PREFIX_LOCAL << "CostGain=" << CostGain
59 << " (After=" << CostAfter << " Before=" << CostBefore
60 << ")\n");
61 const VectorizeOptions &Opts = getVectorizeOptions(C: *Ctx);
62 if (CostGain > Opts.sbvec_cost_threshold) {
63 LLVM_DEBUG(dbgs() << DEBUG_PREFIX_LOCAL << "Not profitable, reverting.\n");
64 Ctx->revert();
65 return false;
66 }
67 LLVM_DEBUG(dbgs() << DEBUG_PREFIX_LOCAL << "Profitable accepting.\n");
68 Ctx->accept();
69 return true;
70}
71
72LoadInst *LoadStoreVec::createVectorLoad(BndlRef<Instruction *> Loads) {
73 Type *Ty = VecUtils::getCombinedVectorTypeFor(Bndl: Loads, DL: *DL);
74 Value *LdPtr = cast<LoadInst>(Val: Loads[0])->getPointerOperand();
75 Align LdAlign = VecUtils::getVecAlignment(InstrRange: Loads);
76 auto LdWhereIt = std::next(x: VecUtils::getLowest(Instrs: Loads)->getIterator());
77 auto *VecL =
78 LoadInst::create(Ty, Ptr: LdPtr, Align: LdAlign, Pos: LdWhereIt, Ctx&: *Ctx, Name: "VecIinitL");
79 Utils::propagateMetadata(I: VecL, VL: Loads);
80 return VecL;
81}
82
83bool SameSizeReinterpret::canReinterpret(Type *SrcTy, Type *DestTy,
84 const DataLayout &DL) {
85 return !isNonIntegralPtr(Ty: SrcTy, DL) && !isNonIntegralPtr(Ty: DestTy, DL);
86}
87
88Type *SameSizeReinterpret::getIntTypeFor(Type *Ty, const DataLayout &DL) {
89 Context &Ctx = Ty->getContext();
90 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: Ty)) {
91 auto *ElmIntTy =
92 IntegerType::get(C&: Ctx, NumBits: Utils::getNumBits(Ty: VecTy->getElementType(), DL));
93 return FixedVectorType::get(ElementType: ElmIntTy, NumElts: VecTy->getNumElements());
94 }
95 return IntegerType::get(C&: Ctx, NumBits: Utils::getNumBits(Ty, DL));
96}
97
98SmallVector<SameSizeReinterpret::CastStep, 3>
99SameSizeReinterpret::getCastChain(Type *SrcTy, Type *DestTy,
100 const DataLayout &DL) {
101 assert(canReinterpret(SrcTy, DestTy, DL) &&
102 "Cannot reinterpret a non-integral pointer!");
103 assert(Utils::getNumBits(SrcTy, DL) == Utils::getNumBits(DestTy, DL) &&
104 "Expected types of the same size!");
105 SmallVector<CastStep, 3> Chain;
106 if (SrcTy == DestTy)
107 return Chain;
108 Type *Ty = SrcTy;
109 if (Ty->getScalarType()->isPointerTy()) {
110 Ty = getIntTypeFor(Ty, DL);
111 Chain.emplace_back(Args: Instruction::Opcode::PtrToInt, Args&: Ty);
112 }
113 bool DestIsPtr = DestTy->getScalarType()->isPointerTy();
114 Type *BitCastTy = DestIsPtr ? getIntTypeFor(Ty: DestTy, DL) : DestTy;
115 if (Ty != BitCastTy)
116 Chain.emplace_back(Args: Instruction::Opcode::BitCast, Args&: BitCastTy);
117 if (DestIsPtr)
118 Chain.emplace_back(Args: Instruction::Opcode::IntToPtr, Args&: DestTy);
119 // ptrtoint, bitcast, and inttoptr, with any step omitted. A vector of
120 // pointers and a scalar pointer of the same width need all three.
121 assert(Chain.size() <= 3 && "Unexpected reinterpret cast chain!");
122 return Chain;
123}
124
125Constant *SameSizeReinterpret::reinterpretConstant(Constant *C, Type *DestTy,
126 const DataLayout &DL) {
127 if (!canReinterpret(SrcTy: C->getType(), DestTy, DL))
128 return nullptr;
129 Constant *NewC = C;
130 for (auto [Opc, Ty] : getCastChain(SrcTy: C->getType(), DestTy, DL)) {
131 switch (Opc) {
132 case Instruction::Opcode::PtrToInt:
133 NewC = ConstantExpr::getPtrToInt(C: NewC, Ty);
134 break;
135 case Instruction::Opcode::BitCast:
136 NewC = ConstantExpr::getBitCast(C: NewC, Ty);
137 break;
138 case Instruction::Opcode::IntToPtr:
139 NewC = ConstantExpr::getIntToPtr(C: NewC, Ty);
140 break;
141 default:
142 llvm_unreachable("Unexpected cast in reinterpret chain!");
143 }
144 }
145 return NewC;
146}
147
148Constant *LoadStoreVec::createConstantVector(BndlRef<Constant *> Constants) {
149 auto *VecTy =
150 cast<FixedVectorType>(Val: VecUtils::getCombinedVectorTypeFor(Bndl: Constants, DL: *DL));
151 auto *LaneTy = VecTy->getScalarType();
152 unsigned LaneBits = Utils::getNumBits(Ty: LaneTy, DL: *DL);
153 assert(all_of(Constants,
154 [&](Value *V) {
155 return Utils::getNumBits(V, *DL) % LaneBits == 0;
156 }) &&
157 "Chain contains a constant which cannot be converted or split");
158
159 // Some of the contents of Constants may be vectors, like <i8 1, i8 2>.
160 // Collect each scalar element in ConstantElements.
161 SmallVector<Constant *, 4> ConstantElements;
162 for (Constant *COp : Constants) {
163 if (auto *AggrCOp = dyn_cast<ConstantAggregate>(Val: COp)) {
164 // If the operand is a constant aggregate, then append all its elements.
165 // TODO: Flatten nested aggregates such as {i32, {i32, <2 x i32>}} in a
166 // follow-up.
167 for (Value *Elm : AggrCOp->operands())
168 ConstantElements.push_back(Elt: cast<Constant>(Val: Elm));
169 } else if (auto *SeqCOp = dyn_cast<ConstantDataSequential>(Val: COp)) {
170 for (auto ElmIdx : seq<unsigned>(Size: SeqCOp->getNumElements()))
171 ConstantElements.push_back(Elt: SeqCOp->getElementAsConstant(ElmIdx));
172 } else if (auto *Zero = dyn_cast<ConstantAggregateZero>(Val: COp)) {
173 auto *ZeroElm = Zero->getSequentialElement();
174 for ([[maybe_unused]] auto Cnt :
175 seq<unsigned>(Size: Zero->getElementCount().getFixedValue()))
176 ConstantElements.push_back(Elt: ZeroElm);
177 } else if (isa<ConstantInt>(Val: COp) && isa<VectorType>(Val: COp->getType())) {
178 auto *Elm = ConstantInt::get(Ctx&: *Ctx, V: cast<ConstantInt>(Val: COp)->getValue());
179 for ([[maybe_unused]] auto Cnt :
180 seq<unsigned>(Size: cast<VectorType>(Val: COp->getType())
181 ->getElementCount()
182 .getFixedValue()))
183 ConstantElements.push_back(Elt: Elm);
184 } else if (isa<ConstantFP>(Val: COp) && isa<VectorType>(Val: COp->getType())) {
185 auto *Elm = ConstantFP::get(V: cast<ConstantFP>(Val: COp)->getValue(), Ctx&: *Ctx);
186 for ([[maybe_unused]] auto Cnt :
187 seq<unsigned>(Size: cast<VectorType>(Val: COp->getType())
188 ->getElementCount()
189 .getFixedValue()))
190 ConstantElements.push_back(Elt: Elm);
191 } else if (isa<PoisonValue>(Val: COp) && isa<VectorType>(Val: COp->getType())) {
192 auto *Elm =
193 PoisonValue::get(T: cast<VectorType>(Val: COp->getType())->getElementType());
194 for ([[maybe_unused]] auto Cnt :
195 seq<unsigned>(Size: cast<VectorType>(Val: COp->getType())
196 ->getElementCount()
197 .getFixedValue()))
198 ConstantElements.push_back(Elt: Elm);
199 } else if (isa<VectorType>(Val: COp->getType())) {
200 // TODO: Flatten the remaining vector constants.
201 return nullptr;
202 } else {
203 ConstantElements.push_back(Elt: COp);
204 }
205 }
206
207 // The elements in ConstantElements may not be of the same type, so we need to
208 // convert them to LaneTy such that we end up getting a vector
209 // <ConstantElements.size() x LaneTy>. This may involve converting integers to
210 // floats (e.g., float 1.0 to i32 0x3f800000), widening or slicing values if
211 // not at LaneTy bit-width (e.g., i16 0x0101 to i8 0x01, i8 0x01 on
212 // little-endian), or a combination of the two.
213 SmallVector<Constant *, 8> LaneTyConstants;
214 LaneTyConstants.reserve(N: ConstantElements.size());
215 for (Constant *C : ConstantElements) {
216 unsigned Bits = Utils::getNumBits(V: C, DL: *DL);
217 if (Bits == LaneBits) {
218 Constant *Lane = SameSizeReinterpret::reinterpretConstant(C, DestTy: LaneTy, DL: *DL);
219 if (Lane == nullptr)
220 return nullptr;
221 LaneTyConstants.push_back(Elt: Lane);
222 } else if (Bits > LaneBits) {
223 // C is wider than LaneTy, so slice it into LaneTy-sized pieces. That
224 // needs a known bit pattern. A ConstantExpr (for example, ptrtoint of a
225 // global) or a global's address is only known at link time and cannot
226 // be sliced.
227 if (!isa<ConstantInt, ConstantFP, ConstantPointerNull>(Val: C))
228 return nullptr;
229 APInt Val;
230 if (auto *CI = dyn_cast<ConstantInt>(Val: C))
231 Val = CI->getValue();
232 else if (auto *CFP = dyn_cast<ConstantFP>(Val: C))
233 Val = CFP->getValue().bitcastToAPInt();
234 else
235 Val = APInt::getZero(numBits: Bits);
236 unsigned NumSlices = Bits / LaneBits;
237 for (unsigned SliceIdx : seq<unsigned>(Size: NumSlices)) {
238 unsigned EndianAwareSlice =
239 DL->isLittleEndian() ? SliceIdx : NumSlices - 1 - SliceIdx;
240 // extractBits returns an integer. Convert that slice back to LaneTy
241 // without changing its bits, so a float lane stays a float.
242 Constant *SliceCInt = ConstantInt::get(
243 Ctx&: *Ctx, V: Val.extractBits(numBits: LaneBits, bitPosition: EndianAwareSlice * LaneBits));
244 Constant *SliceC =
245 SameSizeReinterpret::reinterpretConstant(C: SliceCInt, DestTy: LaneTy, DL: *DL);
246 if (SliceC == nullptr)
247 return nullptr;
248 LaneTyConstants.push_back(Elt: SliceC);
249 }
250 } else {
251 llvm_unreachable("Vector element type size was calculated incorrectly");
252 }
253 }
254 return ConstantVector::get(V: LaneTyConstants);
255}
256
257bool LoadStoreVec::vectorizeStores(BndlRef<Instruction *> Stores, Region &Rgn) {
258 if (!canVectorize(Bndl: Stores))
259 return false;
260 SmallVector<Value *, 4> Operands;
261 Operands.reserve(N: Stores.size());
262 for (auto *I : Stores) {
263 auto *Op = cast<StoreInst>(Val: I)->getValueOperand();
264 Operands.push_back(Elt: Op);
265 }
266 BasicBlock *BB = Stores[0]->getParent();
267 // TODO: For now we only support load operands.
268 // TODO: For now we don't cross BBs.
269 // TODO: For now don't vectorize if the loads have external uses.
270 bool AllLoads = all_of(Range&: Operands, P: [BB](Value *V) {
271 auto *LI = dyn_cast<LoadInst>(Val: V);
272 if (LI == nullptr)
273 return false;
274 // TODO: For now we don't cross BBs.
275 if (LI->getParent() != BB)
276 return false;
277 if (LI->hasNUsesOrMore(Num: 2))
278 return false;
279 return true;
280 });
281 bool AllConstants =
282 all_of(Range&: Operands, P: [](Value *V) { return isa<Constant>(Val: V); });
283 if (!AllLoads && !AllConstants)
284 return false;
285
286 // Vectorizing mixed floats and integers with external uses may not be
287 // profitable on some targets, so save state here.
288 saveIR(R&: Rgn);
289 Value *VecOp = nullptr;
290 SmallVector<Instruction *, 8> Loads;
291 if (AllLoads) {
292 Loads.reserve(N: Operands.size());
293 for (Value *Op : Operands)
294 Loads.push_back(Elt: cast<Instruction>(Val: Op));
295 if (!canVectorize(Bndl: Loads)) {
296 Ctx->accept();
297 return false;
298 }
299 VecOp = createVectorLoad(Loads);
300 assert(VecOp != nullptr && "Expected vector value!");
301 } else if (AllConstants) {
302 SmallVector<Constant *, 8> Constants;
303 Constants.reserve(N: Operands.size());
304 for (Value *Op : Operands)
305 Constants.push_back(Elt: cast<Constant>(Val: Op));
306 VecOp = createConstantVector(Constants);
307 if (VecOp == nullptr) {
308 Ctx->accept();
309 return false;
310 }
311 }
312
313 // Generate vector store.
314 Value *StPtr = cast<StoreInst>(Val: Stores[0])->getPointerOperand();
315 Align StAlign = VecUtils::getVecAlignment(InstrRange: Stores);
316 auto StWhereIt = std::next(x: VecUtils::getLowest(Instrs: Stores)->getIterator());
317 auto *VecS = StoreInst::create(V: VecOp, Ptr: StPtr, Align: StAlign, Pos: StWhereIt, Ctx&: *Ctx);
318 Utils::propagateMetadata(I: VecS, VL: Stores);
319
320 DeadInstrMorgue.collectPotentiallyDeadInstrs(Bndl: Stores);
321 if (AllLoads)
322 DeadInstrMorgue.collectPotentiallyDeadInstrs<Instruction>(Bndl: Loads);
323 DeadInstrMorgue.tryEraseDeadInstrs();
324
325 return acceptOrRevert();
326}
327
328LoadInst *LoadStoreVec::vectorizeLoads(BndlRef<Instruction *> Loads,
329 Region &Rgn) {
330 auto VecTy = canVectorize(Bndl: Loads);
331 if (!VecTy)
332 return nullptr;
333
334 // TODO: Support mixed-type top-level load chains.
335 Type *VecElemTy = cast<FixedVectorType>(Val: *VecTy)->getElementType();
336 if (!all_of(Range&: Loads, P: [VecElemTy](Instruction *I) {
337 return VecUtils::getElementType(Ty: I->getType()) == VecElemTy;
338 }))
339 return nullptr;
340
341 saveIR(R&: Rgn);
342
343 auto *VecLoad = createVectorLoad(Loads);
344 assert(VecLoad != nullptr && "Expected vector load");
345
346 BasicBlock::iterator WhereIt = std::next(x: VecLoad->getIterator());
347 for (auto [Lane, OrigV] : VecUtils::enumerateLanes(Range: Loads)) {
348 auto *OrigLoad = cast<LoadInst>(Val: OrigV);
349 if (OrigLoad->hasNUses(Num: 0))
350 continue;
351 Value *Unpacked =
352 VecUtils::unpack(FromVec: VecLoad, ExtrTy: OrigLoad->getType(), Lane, WhereIt);
353 OrigLoad->replaceAllUsesWith(Other: Unpacked);
354 }
355
356 DeadInstrMorgue.collectPotentiallyDeadInstrs(Bndl: Loads);
357 DeadInstrMorgue.tryEraseDeadInstrs();
358
359 if (!acceptOrRevert())
360 return nullptr;
361 return VecLoad;
362}
363
364bool LoadStoreVec::runOnRegion(Region &Rgn, const Analyses &RegionAnalyses) {
365 SmallVector<Instruction *, 8> Bndl(Rgn.getAux().begin(), Rgn.getAux().end());
366 if (Bndl.size() < 2)
367 return false;
368 Function &F = *Bndl[0]->getParent()->getParent();
369 DL = &F.getParent()->getDataLayout();
370 Ctx = &F.getContext();
371 A = &RegionAnalyses;
372 InstrMaps IMaps;
373 auto Opc = Bndl[0]->getOpcode();
374 assert(
375 all_of(Bndl, [Opc](Instruction *I) { return I->getOpcode() == Opc; }) &&
376 "Expected a homogeneous seed slice!");
377
378 SchedDirection Dir;
379 switch (Opc) {
380 case Instruction::Opcode::Load:
381 Dir = SchedDirection::TopDown;
382 break;
383 case Instruction::Opcode::Store:
384 Dir = SchedDirection::BottomUp;
385 break;
386 default:
387 llvm_unreachable("Expected Load or Store");
388 }
389
390 Legality = std::make_unique<LegalityAnalysis>(
391 args&: A->getAA(), args&: A->getScalarEvolution(), args: F.getParent()->getDataLayout(),
392 args&: A->getTTI(), args&: F.getContext(), args&: IMaps, args&: Dir);
393
394 bool Changed = false;
395 switch (Opc) {
396 case Instruction::Opcode::Load:
397 Changed = vectorizeLoads(Loads: Bndl, Rgn) != nullptr;
398 break;
399 case Instruction::Opcode::Store:
400 Changed = vectorizeStores(Stores: Bndl, Rgn);
401 break;
402 default:
403 llvm_unreachable("Expected Load or Store");
404 }
405 return Changed;
406}
407
408} // namespace sandboxir
409
410} // namespace llvm
411