1//===- BottomUpVec.cpp - A bottom-up 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/BottomUpVec.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/Transforms/Vectorize/SandboxVectorizer/Debug.h"
17#include "llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h"
18
19namespace llvm {
20
21#ifndef NDEBUG
22static cl::opt<bool>
23 AlwaysVerify("sbvec-always-verify", cl::init(false), cl::Hidden,
24 cl::desc("Helps find bugs by verifying the IR whenever we "
25 "emit new instructions (*very* expensive)."));
26#endif // NDEBUG
27
28static constexpr unsigned long StopAtDisabled =
29 std::numeric_limits<unsigned long>::max();
30static cl::opt<unsigned long>
31 StopAt("sbvec-stop-at", cl::init(Val: StopAtDisabled), cl::Hidden,
32 cl::desc("Vectorize if the invocation count is < than this. 0 "
33 "disables vectorization."));
34
35static constexpr unsigned long StopBundleDisabled =
36 std::numeric_limits<unsigned long>::max();
37static cl::opt<unsigned long>
38 StopBundle("sbvec-stop-bndl", cl::init(Val: StopBundleDisabled), cl::Hidden,
39 cl::desc("Vectorize up to this many bundles."));
40
41namespace sandboxir {
42
43static SmallVector<Value *, 4> getOperand(ArrayRef<Value *> Bndl,
44 unsigned OpIdx) {
45 SmallVector<Value *, 4> 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 *BottomUpVec::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 BottomUpVec::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 *BottomUpVec::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 *BottomUpVec::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 BottomUpVec::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 *BottomUpVec::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 auto ActionPtr =
292 std::make_unique<Action>(args: &LegalityRes, args&: Bndl, args&: UserBndl, args&: Depth);
293 SmallVector<Action *> Operands;
294 switch (LegalityRes.getSubclassID()) {
295 case LegalityResultID::Widen: {
296 auto *I = cast<Instruction>(Val: Bndl[0]);
297 switch (I->getOpcode()) {
298 case Instruction::Opcode::Load:
299 break;
300 case Instruction::Opcode::Store: {
301 // Don't recurse towards the pointer operand.
302 Action *OpA =
303 vectorizeRec(Bndl: getOperand(Bndl, OpIdx: 0), UserBndl: Bndl, Depth: Depth + 1, Legality);
304 Operands.push_back(Elt: OpA);
305 break;
306 }
307 default:
308 // Visit all operands.
309 for (auto OpIdx : seq<unsigned>(Size: I->getNumOperands())) {
310 Action *OpA =
311 vectorizeRec(Bndl: getOperand(Bndl, OpIdx), UserBndl: Bndl, Depth: Depth + 1, Legality);
312 Operands.push_back(Elt: OpA);
313 }
314 break;
315 }
316 // Update the maps to mark Bndl as "vectorized".
317 IMaps->registerVector(Origs: Bndl, Vec: ActionPtr.get());
318 break;
319 }
320 case LegalityResultID::DiamondReuse:
321 case LegalityResultID::DiamondReuseWithShuffle:
322 case LegalityResultID::DiamondReuseMultiInput:
323 case LegalityResultID::Pack:
324 break;
325 }
326 // Create actions in post-order.
327 ActionPtr->Operands = std::move(Operands);
328 auto *Action = ActionPtr.get();
329 Actions.push_back(ActPtr: std::move(ActionPtr));
330 return Action;
331}
332
333#ifndef NDEBUG
334void BottomUpVec::ActionsVector::print(raw_ostream &OS) const {
335 for (auto [Idx, Action] : enumerate(Actions)) {
336 Action->print(OS);
337 OS << "\n";
338 }
339}
340void BottomUpVec::ActionsVector::dump() const { print(dbgs()); }
341#endif // NDEBUG
342
343void BottomUpVec::emitUnpacksForExternalUses(const ArrayRef<Value *> Bndl,
344 Value *Vec) {
345 // Find where we should emit the unpacks.
346 BasicBlock::iterator WhereIt;
347 if (auto *VecI = dyn_cast<Instruction>(Val: Vec)) {
348 WhereIt = std::next(x: VecI->getIterator());
349 } else {
350 // If Vec is a constant then it should be safe to emit the unpacks at the
351 // top of the block.
352 // Note: Extracts from constants are usually folded to constants.
353 assert(isa<Constant>(Vec) && "Expected constant!");
354 assert(isa<Instruction>(Bndl[0]) &&
355 "A widened Bndl should contain instrs!");
356 BasicBlock *BB = cast<Instruction>(Val: Bndl[0])->getParent();
357 WhereIt =
358 BB->empty()
359 ? BB->begin()
360 : std::next(
361 x: VecUtils::getLastPHIOrSelf(I: &*BB->begin())->getIterator());
362 }
363
364 for (auto [Lane, Elm] : VecUtils::enumerateLanes(Range: Bndl)) {
365 for (User *U : Elm->users()) {
366 // Skip users that we just vectorized.
367 if (IMaps->isVectorized(Orig: U))
368 continue;
369 auto *LastUnpackV = VecUtils::unpack(FromVec: Vec, ExtrTy: Elm->getType(), Lane, WhereIt);
370 Elm->replaceAllUsesWith(Other: LastUnpackV);
371 }
372 }
373}
374
375Value *BottomUpVec::emitVectors() {
376 Value *NewVec = nullptr;
377 for (const auto &ActionPtr : Actions) {
378 ArrayRef<Value *> Bndl = ActionPtr->Bndl;
379 ArrayRef<Value *> UserBndl = ActionPtr->UserBndl;
380 const LegalityResult &LegalityRes = *ActionPtr->LegalityRes;
381 unsigned Depth = ActionPtr->Depth;
382 auto *UserBB = !UserBndl.empty()
383 ? cast<Instruction>(Val: UserBndl.front())->getParent()
384 : cast<Instruction>(Val: Bndl[0])->getParent();
385
386 switch (LegalityRes.getSubclassID()) {
387 case LegalityResultID::Widen: {
388 auto *I = cast<Instruction>(Val: Bndl[0]);
389 SmallVector<Value *, 2> VecOperands;
390 switch (I->getOpcode()) {
391 case Instruction::Opcode::Load:
392 VecOperands.push_back(Elt: cast<LoadInst>(Val: I)->getPointerOperand());
393 break;
394 case Instruction::Opcode::Store: {
395 VecOperands.push_back(Elt: ActionPtr->Operands[0]->Vec);
396 VecOperands.push_back(Elt: cast<StoreInst>(Val: I)->getPointerOperand());
397 break;
398 }
399 default:
400 // Visit all operands.
401 for (Action *OpA : ActionPtr->Operands) {
402 auto *VecOp = OpA->Vec;
403 VecOperands.push_back(Elt: VecOp);
404 }
405 break;
406 }
407 NewVec = createVectorInstr(Bndl: ActionPtr->Bndl, Operands: VecOperands);
408 // Collect any potentially dead scalar instructions, including the
409 // original scalars and pointer operands of loads/stores.
410 if (NewVec != nullptr)
411 collectPotentiallyDeadInstrs(Bndl);
412
413 // Emit unpacks for all external uses, if any.
414 emitUnpacksForExternalUses(Bndl: ActionPtr->Bndl, Vec: NewVec);
415 break;
416 }
417 case LegalityResultID::DiamondReuse: {
418 NewVec = cast<DiamondReuse>(Val: LegalityRes).getVector()->Vec;
419 break;
420 }
421 case LegalityResultID::DiamondReuseWithShuffle: {
422 auto *VecOp = cast<DiamondReuseWithShuffle>(Val: LegalityRes).getVector()->Vec;
423 const ShuffleMask &Mask =
424 cast<DiamondReuseWithShuffle>(Val: LegalityRes).getMask();
425 NewVec = createShuffle(VecOp, Mask, UserBB);
426 assert(NewVec->getType() == VecOp->getType() &&
427 "Expected same type! Bad mask ?");
428 break;
429 }
430 case LegalityResultID::DiamondReuseMultiInput: {
431 const auto &Descr =
432 cast<DiamondReuseMultiInput>(Val: LegalityRes).getCollectDescr();
433 Type *ResTy = VecUtils::getWideType(ElemTy: Bndl[0]->getType(), NumElts: Bndl.size());
434
435 // TODO: Try to get WhereIt without creating a vector.
436 SmallVector<Value *, 4> DescrInstrs;
437 for (const auto &ElmDescr : Descr.getDescrs()) {
438 auto *V = ElmDescr.needsExtract() ? ElmDescr.getValue()->Vec
439 : ElmDescr.getScalar();
440 if (auto *I = dyn_cast<Instruction>(Val: V))
441 DescrInstrs.push_back(Elt: I);
442 }
443 BasicBlock::iterator WhereIt =
444 getInsertPointAfterInstrs(Vals: DescrInstrs, BB: UserBB);
445
446 Value *LastV = PoisonValue::get(T: ResTy);
447 Context &Ctx = LastV->getContext();
448 unsigned Lane = 0;
449 for (const auto &ElmDescr : Descr.getDescrs()) {
450 Value *VecOp = nullptr;
451 Value *ValueToInsert;
452 if (ElmDescr.needsExtract()) {
453 VecOp = ElmDescr.getValue()->Vec;
454 ConstantInt *IdxC =
455 ConstantInt::get(Ty: Type::getInt32Ty(Ctx), V: ElmDescr.getExtractIdx());
456 ValueToInsert = ExtractElementInst::create(
457 Vec: VecOp, Idx: IdxC, Pos: WhereIt, Ctx&: VecOp->getContext(), Name: "VExt");
458 } else {
459 ValueToInsert = ElmDescr.getScalar();
460 }
461 auto NumLanesToInsert = VecUtils::getNumLanes(V: ValueToInsert);
462 if (NumLanesToInsert == 1) {
463 // If we are inserting a scalar element then we need a single insert.
464 // %VIns = insert %DstVec, %SrcScalar, Lane
465 ConstantInt *LaneC = ConstantInt::get(Ty: Type::getInt32Ty(Ctx), V: Lane);
466 LastV = InsertElementInst::create(Vec: LastV, NewElt: ValueToInsert, Idx: LaneC,
467 Pos: WhereIt, Ctx, Name: "VIns");
468 } else {
469 // If we are inserting a vector element then we need to extract and
470 // insert each vector element one by one with a chain of extracts and
471 // inserts, for example:
472 // %VExt0 = extract %SrcVec, 0
473 // %VIns0 = insert %DstVec, %Vect0, Lane + 0
474 // %VExt1 = extract %SrcVec, 1
475 // %VIns1 = insert %VIns0, %Vect0, Lane + 1
476 for (unsigned LnCnt = 0; LnCnt != NumLanesToInsert; ++LnCnt) {
477 auto *ExtrIdxC = ConstantInt::get(Ty: Type::getInt32Ty(Ctx), V: LnCnt);
478 auto *ExtrI = ExtractElementInst::create(Vec: ValueToInsert, Idx: ExtrIdxC,
479 Pos: WhereIt, Ctx, Name: "VExt");
480 unsigned InsLane = Lane + LnCnt;
481 auto *InsLaneC = ConstantInt::get(Ty: Type::getInt32Ty(Ctx), V: InsLane);
482 LastV = InsertElementInst::create(Vec: LastV, NewElt: ExtrI, Idx: InsLaneC, Pos: WhereIt,
483 Ctx, Name: "VIns");
484 }
485 }
486 Lane += NumLanesToInsert;
487 }
488 NewVec = LastV;
489 break;
490 }
491 case LegalityResultID::Pack: {
492 // If we can't vectorize the seeds then just return.
493 if (Depth == 0)
494 return nullptr;
495 NewVec = createPack(ToPack: Bndl, UserBB);
496 break;
497 }
498 }
499 if (NewVec != nullptr) {
500 Change = true;
501 ActionPtr->Vec = NewVec;
502 }
503#ifndef NDEBUG
504 if (AlwaysVerify) {
505 // This helps find broken IR by constantly verifying the function. Note
506 // that this is very expensive and should only be used for debugging.
507 Instruction *I0 = isa<Instruction>(Bndl[0])
508 ? cast<Instruction>(Bndl[0])
509 : cast<Instruction>(UserBndl[0]);
510 assert(!Utils::verifyFunction(I0->getParent()->getParent(), dbgs()) &&
511 "Broken function!");
512 }
513#endif // NDEBUG
514 }
515 return NewVec;
516}
517
518bool BottomUpVec::tryVectorize(ArrayRef<Value *> Bndl,
519 LegalityAnalysis &Legality) {
520 Change = false;
521 if (LLVM_UNLIKELY(BottomUpInvocationCnt++ >= StopAt &&
522 StopAt != StopAtDisabled))
523 return false;
524 DeadInstrCandidates.clear();
525 Legality.clear();
526 Actions.clear();
527 DebugBndlCnt = 0;
528 vectorizeRec(Bndl, UserBndl: {}, /*Depth=*/0, Legality);
529 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "BottomUpVec: Vectorization Actions:\n";
530 Actions.dump());
531 emitVectors();
532 tryEraseDeadInstrs();
533 return Change;
534}
535
536bool BottomUpVec::runOnRegion(Region &Rgn, const Analyses &A) {
537 const auto &SeedSlice = Rgn.getAux();
538 assert(SeedSlice.size() >= 2 && "Bad slice!");
539 Function &F = *SeedSlice[0]->getParent()->getParent();
540 IMaps = std::make_unique<InstrMaps>();
541 LegalityAnalysis Legality(A.getAA(), A.getScalarEvolution(),
542 F.getParent()->getDataLayout(), F.getContext(),
543 *IMaps);
544
545 // TODO: Refactor to remove the unnecessary copy to SeedSliceVals.
546 SmallVector<Value *> SeedSliceVals(SeedSlice.begin(), SeedSlice.end());
547 // Try to vectorize starting from the seed slice. The returned value
548 // is true if we found vectorizable code and generated some vector
549 // code for it. It does not mean that the code is profitable.
550 return tryVectorize(Bndl: SeedSliceVals, Legality);
551}
552
553} // namespace sandboxir
554} // namespace llvm
555