1//===- BundleVec.cpp - A bundle-forming SLP-style vectorizer pass ---------===//
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/BundleVec.h"
10#include "llvm/ADT/SmallVector.h"
11#include "llvm/SandboxIR/Function.h"
12#include "llvm/SandboxIR/Instruction.h"
13#include "llvm/SandboxIR/Module.h"
14#include "llvm/SandboxIR/Region.h"
15#include "llvm/SandboxIR/Utils.h"
16#include "llvm/Support/ErrorHandling.h"
17#include "llvm/Transforms/Vectorize/SandboxVectorizer/Debug.h"
18#include "llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h"
19
20namespace llvm {
21
22#ifndef NDEBUG
23static cl::opt<bool>
24 AlwaysVerify("sbvec-always-verify", cl::init(false), cl::Hidden,
25 cl::desc("Helps find bugs by verifying the IR whenever we "
26 "emit new instructions (*very* expensive)."));
27#endif // NDEBUG
28
29static constexpr unsigned long StopAtDisabled =
30 std::numeric_limits<unsigned long>::max();
31static cl::opt<unsigned long>
32 StopAt("sbvec-stop-at", cl::init(Val: StopAtDisabled), cl::Hidden,
33 cl::desc("Vectorize if the invocation count is < than this. 0 "
34 "disables vectorization."));
35
36static constexpr unsigned long StopBundleDisabled =
37 std::numeric_limits<unsigned long>::max();
38static cl::opt<unsigned long>
39 StopBundle("sbvec-stop-bndl", cl::init(Val: StopBundleDisabled), cl::Hidden,
40 cl::desc("Vectorize up to this many bundles."));
41
42namespace sandboxir {
43
44static BundleTy getOperand(ArrayRef<Value *> Bndl, unsigned OpIdx) {
45 BundleTy Operands;
46 for (Value *BndlV : Bndl) {
47 auto *BndlI = cast<Instruction>(Val: BndlV);
48 Operands.push_back(Elt: BndlI->getOperand(OpIdx));
49 }
50 return Operands;
51}
52
53/// \Returns the BB iterator after the lowest instruction in \p Vals, or the top
54/// of BB if no instruction found in \p Vals.
55static BasicBlock::iterator getInsertPointAfterInstrs(ArrayRef<Value *> Vals,
56 BasicBlock *BB) {
57 auto *BotI = VecUtils::getLastPHIOrSelf(I: VecUtils::getLowest(Vals, BB));
58 if (BotI == nullptr)
59 // We are using BB->begin() (or after PHIs) as the fallback insert point.
60 return BB->empty()
61 ? BB->begin()
62 : std::next(
63 x: VecUtils::getLastPHIOrSelf(I: &*BB->begin())->getIterator());
64 return std::next(x: BotI->getIterator());
65}
66
67Value *BundleVec::createVectorInstr(ArrayRef<Value *> Bndl,
68 ArrayRef<Value *> Operands) {
69 auto CreateVectorInstr = [](ArrayRef<Value *> Bndl,
70 ArrayRef<Value *> Operands) -> Value * {
71 assert(all_of(Bndl, [](auto *V) { return isa<Instruction>(V); }) &&
72 "Expect Instructions!");
73 auto &Ctx = Bndl[0]->getContext();
74
75 Type *ScalarTy = VecUtils::getElementType(Ty: Utils::getExpectedType(V: Bndl[0]));
76 auto *VecTy = VecUtils::getWideType(ElemTy: ScalarTy, NumElts: VecUtils::getNumLanes(Bndl));
77
78 BasicBlock::iterator WhereIt = getInsertPointAfterInstrs(
79 Vals: Bndl, BB: cast<Instruction>(Val: Bndl[0])->getParent());
80
81 auto Opcode = cast<Instruction>(Val: Bndl[0])->getOpcode();
82 switch (Opcode) {
83 case Instruction::Opcode::ZExt:
84 case Instruction::Opcode::SExt:
85 case Instruction::Opcode::FPToUI:
86 case Instruction::Opcode::FPToSI:
87 case Instruction::Opcode::FPExt:
88 case Instruction::Opcode::PtrToInt:
89 case Instruction::Opcode::IntToPtr:
90 case Instruction::Opcode::SIToFP:
91 case Instruction::Opcode::UIToFP:
92 case Instruction::Opcode::Trunc:
93 case Instruction::Opcode::FPTrunc:
94 case Instruction::Opcode::BitCast: {
95 assert(Operands.size() == 1u && "Casts are unary!");
96 return CastInst::create(DestTy: VecTy, Op: Opcode, Operand: Operands[0], Pos: WhereIt, Ctx,
97 Name: "VCast");
98 }
99 case Instruction::Opcode::FCmp:
100 case Instruction::Opcode::ICmp: {
101 auto Pred = cast<CmpInst>(Val: Bndl[0])->getPredicate();
102 assert(all_of(drop_begin(Bndl),
103 [Pred](auto *SBV) {
104 return cast<CmpInst>(SBV)->getPredicate() == Pred;
105 }) &&
106 "Expected same predicate across bundle.");
107 return CmpInst::create(Pred, S1: Operands[0], S2: Operands[1], Pos: WhereIt, Ctx,
108 Name: "VCmp");
109 }
110 case Instruction::Opcode::Select: {
111 return SelectInst::create(Cond: Operands[0], True: Operands[1], False: Operands[2], Pos: WhereIt,
112 Ctx, Name: "Vec");
113 }
114 case Instruction::Opcode::FNeg: {
115 auto *UOp0 = cast<UnaryOperator>(Val: Bndl[0]);
116 auto OpC = UOp0->getOpcode();
117 return UnaryOperator::createWithCopiedFlags(Op: OpC, OpV: Operands[0], CopyFrom: UOp0,
118 Pos: WhereIt, Ctx, Name: "Vec");
119 }
120 case Instruction::Opcode::Add:
121 case Instruction::Opcode::FAdd:
122 case Instruction::Opcode::Sub:
123 case Instruction::Opcode::FSub:
124 case Instruction::Opcode::Mul:
125 case Instruction::Opcode::FMul:
126 case Instruction::Opcode::UDiv:
127 case Instruction::Opcode::SDiv:
128 case Instruction::Opcode::FDiv:
129 case Instruction::Opcode::URem:
130 case Instruction::Opcode::SRem:
131 case Instruction::Opcode::FRem:
132 case Instruction::Opcode::Shl:
133 case Instruction::Opcode::LShr:
134 case Instruction::Opcode::AShr:
135 case Instruction::Opcode::And:
136 case Instruction::Opcode::Or:
137 case Instruction::Opcode::Xor: {
138 auto *BinOp0 = cast<BinaryOperator>(Val: Bndl[0]);
139 auto *LHS = Operands[0];
140 auto *RHS = Operands[1];
141 return BinaryOperator::createWithCopiedFlags(
142 Op: BinOp0->getOpcode(), LHS, RHS, CopyFrom: BinOp0, Pos: WhereIt, Ctx, Name: "Vec");
143 }
144 case Instruction::Opcode::Load: {
145 auto *Ld0 = cast<LoadInst>(Val: Bndl[0]);
146 Value *Ptr = Ld0->getPointerOperand();
147 return LoadInst::create(Ty: VecTy, Ptr, Align: Ld0->getAlign(), Pos: WhereIt, Ctx,
148 Name: "VecL");
149 }
150 case Instruction::Opcode::Store: {
151 auto Align = cast<StoreInst>(Val: Bndl[0])->getAlign();
152 Value *Val = Operands[0];
153 Value *Ptr = Operands[1];
154 return StoreInst::create(V: Val, Ptr, Align, Pos: WhereIt, Ctx);
155 }
156 case Instruction::Opcode::UncondBr:
157 case Instruction::Opcode::CondBr:
158 case Instruction::Opcode::Ret:
159 case Instruction::Opcode::PHI:
160 case Instruction::Opcode::AddrSpaceCast:
161 case Instruction::Opcode::Call:
162 case Instruction::Opcode::GetElementPtr:
163 llvm_unreachable("Unimplemented");
164 break;
165 default:
166 llvm_unreachable("Unimplemented");
167 break;
168 }
169 llvm_unreachable("Missing switch case!");
170 // TODO: Propagate debug info.
171 };
172
173 auto *NewI = CreateVectorInstr(Bndl, Operands);
174 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "New instr: " << *NewI << "\n");
175 return NewI;
176}
177
178void BundleVec::tryEraseDeadInstrs() {
179 DenseMap<BasicBlock *, SmallVector<Instruction *>> SortedDeadInstrCandidates;
180 // The dead instrs could span BBs, so we need to collect and sort them per BB.
181 for (auto *DeadI : DeadInstrCandidates)
182 SortedDeadInstrCandidates[DeadI->getParent()].push_back(Elt: DeadI);
183 for (auto &Pair : SortedDeadInstrCandidates)
184 sort(C&: Pair.second,
185 Comp: [](Instruction *I1, Instruction *I2) { return I1->comesBefore(Other: I2); });
186 for (const auto &Pair : SortedDeadInstrCandidates) {
187 for (Instruction *I : reverse(C: Pair.second)) {
188 if (I->hasNUses(Num: 0)) {
189 // Erase the dead instructions bottom-to-top.
190 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Erase dead: " << *I << "\n");
191 I->eraseFromParent();
192 }
193 }
194 }
195 DeadInstrCandidates.clear();
196}
197
198Value *BundleVec::createShuffle(Value *VecOp, const ShuffleMask &Mask,
199 BasicBlock *UserBB) {
200 BasicBlock::iterator WhereIt = getInsertPointAfterInstrs(Vals: {VecOp}, BB: UserBB);
201 return ShuffleVectorInst::create(V1: VecOp, V2: VecOp, Mask, Pos: WhereIt,
202 Ctx&: VecOp->getContext(), Name: "VShuf");
203}
204
205Value *BundleVec::createPack(ArrayRef<Value *> ToPack, BasicBlock *UserBB) {
206 BasicBlock::iterator WhereIt = getInsertPointAfterInstrs(Vals: ToPack, BB: UserBB);
207
208 Type *ScalarTy = VecUtils::getCommonScalarType(Bndl: ToPack);
209 unsigned Lanes = VecUtils::getNumLanes(Bndl: ToPack);
210 Type *VecTy = VecUtils::getWideType(ElemTy: ScalarTy, NumElts: Lanes);
211
212 // Create a series of pack instructions.
213 Value *LastInsert = PoisonValue::get(T: VecTy);
214
215 Context &Ctx = ToPack[0]->getContext();
216
217 unsigned InsertIdx = 0;
218 for (Value *Elm : ToPack) {
219 // An element can be either scalar or vector. We need to generate different
220 // IR for each case.
221 if (Elm->getType()->isVectorTy()) {
222 unsigned NumElms =
223 cast<FixedVectorType>(Val: Elm->getType())->getNumElements();
224 for (auto ExtrLane : seq<int>(Begin: 0, End: NumElms)) {
225 // We generate extract-insert pairs, for each lane in `Elm`.
226 Constant *ExtrLaneC =
227 ConstantInt::getSigned(Ty: Type::getInt32Ty(Ctx), V: ExtrLane);
228 // This may return a Constant if Elm is a Constant.
229 auto *ExtrI =
230 ExtractElementInst::create(Vec: Elm, Idx: ExtrLaneC, Pos: WhereIt, Ctx, Name: "VPack");
231 if (!isa<Constant>(Val: ExtrI))
232 WhereIt = std::next(x: cast<Instruction>(Val: ExtrI)->getIterator());
233 Constant *InsertLaneC =
234 ConstantInt::getSigned(Ty: Type::getInt32Ty(Ctx), V: InsertIdx++);
235 // This may also return a Constant if ExtrI is a Constant.
236 auto *InsertI = InsertElementInst::create(
237 Vec: LastInsert, NewElt: ExtrI, Idx: InsertLaneC, Pos: WhereIt, Ctx, Name: "VPack");
238 LastInsert = InsertI;
239 if (!isa<Constant>(Val: InsertI))
240 WhereIt = std::next(x: cast<Instruction>(Val: LastInsert)->getIterator());
241 }
242 } else {
243 Constant *InsertLaneC =
244 ConstantInt::getSigned(Ty: Type::getInt32Ty(Ctx), V: InsertIdx++);
245 // This may be folded into a Constant if LastInsert is a Constant. In
246 // that case we only collect the last constant.
247 LastInsert = InsertElementInst::create(Vec: LastInsert, NewElt: Elm, Idx: InsertLaneC,
248 Pos: WhereIt, Ctx, Name: "Pack");
249 if (auto *NewI = dyn_cast<Instruction>(Val: LastInsert))
250 WhereIt = std::next(x: NewI->getIterator());
251 }
252 }
253 return LastInsert;
254}
255
256void BundleVec::collectPotentiallyDeadInstrs(ArrayRef<Value *> Bndl) {
257 for (Value *V : Bndl)
258 DeadInstrCandidates.insert(V: cast<Instruction>(Val: V));
259 // Also collect the GEPs of vectorized loads and stores.
260 auto Opcode = cast<Instruction>(Val: Bndl[0])->getOpcode();
261 switch (Opcode) {
262 case Instruction::Opcode::Load: {
263 for (Value *V : drop_begin(RangeOrContainer&: Bndl))
264 if (auto *Ptr =
265 dyn_cast<Instruction>(Val: cast<LoadInst>(Val: V)->getPointerOperand()))
266 DeadInstrCandidates.insert(V: Ptr);
267 break;
268 }
269 case Instruction::Opcode::Store: {
270 for (Value *V : drop_begin(RangeOrContainer&: Bndl))
271 if (auto *Ptr =
272 dyn_cast<Instruction>(Val: cast<StoreInst>(Val: V)->getPointerOperand()))
273 DeadInstrCandidates.insert(V: Ptr);
274 break;
275 }
276 default:
277 break;
278 }
279}
280
281Action *BundleVec::vectorizeRec(ArrayRef<Value *> Bndl,
282 ArrayRef<Value *> UserBndl, unsigned Depth,
283 LegalityAnalysis &Legality) {
284 bool StopForDebug =
285 DebugBndlCnt++ >= StopBundle && StopBundle != StopBundleDisabled;
286 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "canVectorize() Bundle:\n";
287 VecUtils::dump(Bndl));
288 const auto &LegalityRes = StopForDebug ? Legality.getForcedPackForDebugging()
289 : Legality.canVectorize(Bndl);
290 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Legality: " << LegalityRes << "\n");
291
292 if (Dir == SchedDirection::TopDown) {
293 // A non-Widen result means we can't extend the vectorized region into
294 // this bundle, so leave its instructions scalar and don't record an
295 // action for it.
296 if (LegalityRes.getSubclassID() != LegalityResultID::Widen)
297 return nullptr;
298
299 auto ActionPtr = std::make_unique<Action>(args: &LegalityRes, args&: Bndl,
300 args: ArrayRef<Value *>(), args&: Depth);
301 Action *Action = ActionPtr.get();
302 IMaps->registerVector(Origs: Bndl, Vec: Action);
303 Actions.push_back(ActPtr: std::move(ActionPtr));
304
305 // Walk down the def-use chain. Each lane in \p Bndl may feed several
306 // users, so we form every compatible user bundle and recurse into each
307 // one.
308 SmallPtrSet<Instruction *, 4> Claimed;
309 for (const auto &NextUserBndl :
310 VecUtils::getNextUserBundles(Bndl, IMaps: *IMaps, Claimed))
311 vectorizeRec(Bndl: NextUserBndl, UserBndl: Bndl, Depth: Depth + 1, Legality);
312
313 return Action;
314 }
315
316 // Bottom up direction
317 auto ActionPtr =
318 std::make_unique<Action>(args: &LegalityRes, args&: Bndl, args&: UserBndl, args&: Depth);
319 SmallVector<Action *> Operands;
320 switch (LegalityRes.getSubclassID()) {
321 case LegalityResultID::Widen: {
322 auto *I = cast<Instruction>(Val: Bndl[0]);
323 switch (I->getOpcode()) {
324 case Instruction::Opcode::Load:
325 break;
326 case Instruction::Opcode::Store: {
327 // Don't recurse towards the pointer operand.
328 Action *OpA =
329 vectorizeRec(Bndl: getOperand(Bndl, OpIdx: 0), UserBndl: Bndl, Depth: Depth + 1, Legality);
330 Operands.push_back(Elt: OpA);
331 break;
332 }
333 default:
334 // Visit all operands.
335 for (auto OpIdx : seq<unsigned>(Size: I->getNumOperands())) {
336 Action *OpA =
337 vectorizeRec(Bndl: getOperand(Bndl, OpIdx), UserBndl: Bndl, Depth: Depth + 1, Legality);
338 Operands.push_back(Elt: OpA);
339 }
340 break;
341 }
342 // Update the maps to mark Bndl as "vectorized".
343 IMaps->registerVector(Origs: Bndl, Vec: ActionPtr.get());
344 break;
345 }
346 case LegalityResultID::DiamondReuse:
347 case LegalityResultID::DiamondReuseWithShuffle:
348 case LegalityResultID::DiamondReuseMultiInput:
349 case LegalityResultID::Pack:
350 break;
351 }
352 // Create actions in post-order.
353 ActionPtr->Operands = std::move(Operands);
354 auto *Action = ActionPtr.get();
355 Actions.push_back(ActPtr: std::move(ActionPtr));
356 return Action;
357}
358
359#ifndef NDEBUG
360void BundleVec::ActionsVector::print(raw_ostream &OS) const {
361 for (auto [Idx, Action] : enumerate(Actions)) {
362 Action->print(OS);
363 OS << "\n";
364 }
365}
366void BundleVec::ActionsVector::dump() const { print(dbgs()); }
367#endif // NDEBUG
368
369void BundleVec::emitUnpacksForExternalUses(const ArrayRef<Value *> Bndl,
370 Value *Vec) {
371 // Find where we should emit the unpacks.
372 BasicBlock::iterator WhereIt;
373 if (auto *VecI = dyn_cast<Instruction>(Val: Vec)) {
374 WhereIt = std::next(x: VecI->getIterator());
375 } else {
376 // If Vec is a constant then it should be safe to emit the unpacks at the
377 // top of the block.
378 // Note: Extracts from constants are usually folded to constants.
379 assert(isa<Constant>(Vec) && "Expected constant!");
380 assert(isa<Instruction>(Bndl[0]) &&
381 "A widened Bndl should contain instrs!");
382 BasicBlock *BB = cast<Instruction>(Val: Bndl[0])->getParent();
383 WhereIt =
384 BB->empty()
385 ? BB->begin()
386 : std::next(
387 x: VecUtils::getLastPHIOrSelf(I: &*BB->begin())->getIterator());
388 }
389
390 for (auto [Lane, Elm] : VecUtils::enumerateLanes(Range: Bndl)) {
391 // Only redirect the external (non-vectorized) uses to an unpack and leave
392 // the vectorized users untouched. A blanket replaceAllUsesWith() would
393 // also rewrite the operands of users we are going to vectorize but have
394 // not emitted yet (in the top-down direction a user bundle is emitted
395 // after its operand bundle), which would corrupt those operands.
396 auto IsExternal = [this](const Use &U) {
397 return !IMaps->isVectorized(Orig: U.getUser());
398 };
399 // Don't emit a dead unpack if all uses are internal to the vector region.
400 if (none_of(Range: Elm->uses(), P: IsExternal))
401 continue;
402 auto *UnpackV = VecUtils::unpack(FromVec: Vec, ExtrTy: Elm->getType(), Lane, WhereIt);
403 Elm->replaceUsesWithIf(OtherV: UnpackV, ShouldReplace: IsExternal);
404 }
405}
406
407Value *BundleVec::emitVectors() {
408 Value *NewVec = nullptr;
409 for (const auto &ActionPtr : Actions) {
410 ArrayRef<Value *> Bndl = ActionPtr->Bndl;
411 ArrayRef<Value *> UserBndl = ActionPtr->UserBndl;
412 const LegalityResult &LegalityRes = *ActionPtr->LegalityRes;
413 unsigned Depth = ActionPtr->Depth;
414 auto *UserBB = !UserBndl.empty()
415 ? cast<Instruction>(Val: UserBndl.front())->getParent()
416 : cast<Instruction>(Val: Bndl[0])->getParent();
417
418 switch (LegalityRes.getSubclassID()) {
419 case LegalityResultID::Widen: {
420 auto *I = cast<Instruction>(Val: Bndl[0]);
421 SmallVector<Value *, 2> VecOperands;
422 if (Dir == SchedDirection::BottomUp) {
423 switch (I->getOpcode()) {
424 case Instruction::Opcode::Load:
425 VecOperands.push_back(Elt: cast<LoadInst>(Val: I)->getPointerOperand());
426 break;
427 case Instruction::Opcode::Store:
428 VecOperands.push_back(Elt: ActionPtr->Operands[0]->Vec);
429 VecOperands.push_back(Elt: cast<StoreInst>(Val: I)->getPointerOperand());
430 break;
431 default:
432 for (Action *OpA : ActionPtr->Operands)
433 VecOperands.push_back(Elt: OpA->Vec);
434 break;
435 }
436 } else {
437 switch (I->getOpcode()) {
438 case Instruction::Opcode::Load:
439 VecOperands.push_back(Elt: cast<LoadInst>(Val: I)->getPointerOperand());
440 break;
441 case Instruction::Opcode::Store: {
442 auto OpBndl = getOperand(Bndl, OpIdx: 0);
443 if (Action *OpA = IMaps->getVectorForOrig(Orig: OpBndl[0]))
444 VecOperands.push_back(Elt: OpA->Vec);
445 else
446 VecOperands.push_back(Elt: createPack(ToPack: OpBndl, UserBB));
447 VecOperands.push_back(Elt: cast<StoreInst>(Val: I)->getPointerOperand());
448 break;
449 }
450 default:
451 for (unsigned OpIdx = 0; OpIdx < I->getNumOperands(); ++OpIdx) {
452 BundleTy OpBndl = getOperand(Bndl, OpIdx);
453 if (Action *OpA = IMaps->getVectorForOrig(Orig: OpBndl[0]))
454 VecOperands.push_back(Elt: OpA->Vec);
455 else
456 VecOperands.push_back(Elt: createPack(ToPack: OpBndl, UserBB));
457 }
458 break;
459 }
460 }
461 NewVec = createVectorInstr(Bndl: ActionPtr->Bndl, Operands: VecOperands);
462 // Collect any potentially dead scalar instructions, including the
463 // original scalars and pointer operands of loads/stores.
464 if (NewVec != nullptr)
465 collectPotentiallyDeadInstrs(Bndl);
466
467 // Emit unpacks for all external uses, if any.
468 emitUnpacksForExternalUses(Bndl: ActionPtr->Bndl, Vec: NewVec);
469 break;
470 }
471 case LegalityResultID::DiamondReuse: {
472 NewVec = cast<DiamondReuse>(Val: LegalityRes).getVector()->Vec;
473 break;
474 }
475 case LegalityResultID::DiamondReuseWithShuffle: {
476 auto *VecOp = cast<DiamondReuseWithShuffle>(Val: LegalityRes).getVector()->Vec;
477 const ShuffleMask &Mask =
478 cast<DiamondReuseWithShuffle>(Val: LegalityRes).getMask();
479 NewVec = createShuffle(VecOp, Mask, UserBB);
480 assert(NewVec->getType() == VecOp->getType() &&
481 "Expected same type! Bad mask ?");
482 break;
483 }
484 case LegalityResultID::DiamondReuseMultiInput: {
485 const auto &Descr =
486 cast<DiamondReuseMultiInput>(Val: LegalityRes).getCollectDescr();
487 Type *ResTy = VecUtils::getWideType(ElemTy: Bndl[0]->getType(), NumElts: Bndl.size());
488
489 // TODO: Try to get WhereIt without creating a vector.
490 SmallVector<Value *, 4> DescrInstrs;
491 for (const auto &ElmDescr : Descr.getDescrs()) {
492 auto *V = ElmDescr.needsExtract() ? ElmDescr.getValue()->Vec
493 : ElmDescr.getScalar();
494 if (auto *I = dyn_cast<Instruction>(Val: V))
495 DescrInstrs.push_back(Elt: I);
496 }
497 BasicBlock::iterator WhereIt =
498 getInsertPointAfterInstrs(Vals: DescrInstrs, BB: UserBB);
499
500 Value *LastV = PoisonValue::get(T: ResTy);
501 Context &Ctx = LastV->getContext();
502 unsigned Lane = 0;
503 for (const auto &ElmDescr : Descr.getDescrs()) {
504 Value *VecOp = nullptr;
505 Value *ValueToInsert;
506 if (ElmDescr.needsExtract()) {
507 VecOp = ElmDescr.getValue()->Vec;
508 ConstantInt *IdxC =
509 ConstantInt::get(Ty: Type::getInt32Ty(Ctx), V: ElmDescr.getExtractIdx());
510 ValueToInsert = ExtractElementInst::create(
511 Vec: VecOp, Idx: IdxC, Pos: WhereIt, Ctx&: VecOp->getContext(), Name: "VExt");
512 } else {
513 ValueToInsert = ElmDescr.getScalar();
514 }
515 auto NumLanesToInsert = VecUtils::getNumLanes(V: ValueToInsert);
516 if (NumLanesToInsert == 1) {
517 // If we are inserting a scalar element then we need a single insert.
518 // %VIns = insert %DstVec, %SrcScalar, Lane
519 ConstantInt *LaneC = ConstantInt::get(Ty: Type::getInt32Ty(Ctx), V: Lane);
520 LastV = InsertElementInst::create(Vec: LastV, NewElt: ValueToInsert, Idx: LaneC,
521 Pos: WhereIt, Ctx, Name: "VIns");
522 } else {
523 // If we are inserting a vector element then we need to extract and
524 // insert each vector element one by one with a chain of extracts and
525 // inserts, for example:
526 // %VExt0 = extract %SrcVec, 0
527 // %VIns0 = insert %DstVec, %Vect0, Lane + 0
528 // %VExt1 = extract %SrcVec, 1
529 // %VIns1 = insert %VIns0, %Vect0, Lane + 1
530 for (unsigned LnCnt = 0; LnCnt != NumLanesToInsert; ++LnCnt) {
531 auto *ExtrIdxC = ConstantInt::get(Ty: Type::getInt32Ty(Ctx), V: LnCnt);
532 auto *ExtrI = ExtractElementInst::create(Vec: ValueToInsert, Idx: ExtrIdxC,
533 Pos: WhereIt, Ctx, Name: "VExt");
534 unsigned InsLane = Lane + LnCnt;
535 auto *InsLaneC = ConstantInt::get(Ty: Type::getInt32Ty(Ctx), V: InsLane);
536 LastV = InsertElementInst::create(Vec: LastV, NewElt: ExtrI, Idx: InsLaneC, Pos: WhereIt,
537 Ctx, Name: "VIns");
538 }
539 }
540 Lane += NumLanesToInsert;
541 }
542 NewVec = LastV;
543 break;
544 }
545 case LegalityResultID::Pack: {
546 // If we can't vectorize the seeds then just return.
547 if (Depth == 0)
548 return nullptr;
549 NewVec = createPack(ToPack: Bndl, UserBB);
550 break;
551 }
552 }
553 if (NewVec != nullptr) {
554 Change = true;
555 ActionPtr->Vec = NewVec;
556 }
557#ifndef NDEBUG
558 if (AlwaysVerify) {
559 // This helps find broken IR by constantly verifying the function. Note
560 // that this is very expensive and should only be used for debugging.
561 Instruction *I0 = isa<Instruction>(Bndl[0])
562 ? cast<Instruction>(Bndl[0])
563 : cast<Instruction>(UserBndl[0]);
564 assert(!Utils::verifyFunction(I0->getParent()->getParent(), dbgs()) &&
565 "Broken function!");
566 }
567#endif // NDEBUG
568 }
569 return NewVec;
570}
571
572bool BundleVec::tryVectorize(ArrayRef<Value *> Bndl,
573 LegalityAnalysis &Legality) {
574 Change = false;
575 if (LLVM_UNLIKELY(InvocationCnt++ >= StopAt && StopAt != StopAtDisabled))
576 return false;
577 DeadInstrCandidates.clear();
578 Legality.clear();
579 Actions.clear();
580 DebugBndlCnt = 0;
581 vectorizeRec(Bndl, UserBndl: {}, /*Depth=*/0, Legality);
582 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << schedDirectionToStr(Dir)
583 << "Vec: Vectorization Actions:\n";
584 Actions.dump());
585 emitVectors();
586 tryEraseDeadInstrs();
587 return Change;
588}
589
590bool BundleVec::runOnRegion(Region &Rgn, const Analyses &A) {
591 const auto &SeedSlice = Rgn.getAux();
592 assert(SeedSlice.size() >= 2 && "Bad slice!");
593 Function &F = *SeedSlice[0]->getParent()->getParent();
594 IMaps = std::make_unique<InstrMaps>();
595 LegalityAnalysis Legality(A.getAA(), A.getScalarEvolution(),
596 F.getParent()->getDataLayout(), F.getContext(),
597 *IMaps, Dir);
598
599 // TODO: Refactor to remove the unnecessary copy to SeedSliceVals.
600 SmallVector<Value *> SeedSliceVals(SeedSlice.begin(), SeedSlice.end());
601 // Try to vectorize starting from the seed slice. The returned value
602 // is true if we found vectorizable code and generated some vector
603 // code for it. It does not mean that the code is profitable.
604 return tryVectorize(Bndl: SeedSliceVals, Legality);
605}
606
607} // namespace sandboxir
608} // namespace llvm
609