1//===- Scalarizer.cpp - Scalarize vector operations -----------------------===//
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 converts vector operations into scalar operations (or, optionally,
10// operations on smaller vector widths), in order to expose optimization
11// opportunities on the individual scalar operations.
12// It is mainly intended for targets that do not have vector units, but it
13// may also be useful for revectorizing code to different vector widths.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Transforms/Scalar/Scalarizer.h"
18#include "llvm/ADT/PostOrderIterator.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Twine.h"
21#include "llvm/Analysis/TargetTransformInfo.h"
22#include "llvm/Analysis/VectorUtils.h"
23#include "llvm/IR/Argument.h"
24#include "llvm/IR/BasicBlock.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/DerivedTypes.h"
28#include "llvm/IR/Dominators.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/IRBuilder.h"
31#include "llvm/IR/InstVisitor.h"
32#include "llvm/IR/InstrTypes.h"
33#include "llvm/IR/Instruction.h"
34#include "llvm/IR/Instructions.h"
35#include "llvm/IR/Intrinsics.h"
36#include "llvm/IR/LLVMContext.h"
37#include "llvm/IR/Module.h"
38#include "llvm/IR/Type.h"
39#include "llvm/IR/Value.h"
40#include "llvm/InitializePasses.h"
41#include "llvm/Support/Casting.h"
42#include "llvm/Transforms/Utils/Local.h"
43#include <cassert>
44#include <cstdint>
45#include <iterator>
46#include <map>
47#include <utility>
48
49using namespace llvm;
50
51#define DEBUG_TYPE "scalarizer"
52
53static BasicBlock::iterator skipPastPhiNodes(BasicBlock::iterator Itr) {
54 BasicBlock *BB = Itr->getParent();
55 if (isa<PHINode>(Val: Itr))
56 Itr = BB->getFirstInsertionPt();
57 return Itr;
58}
59
60// Used to store the scattered form of a vector.
61using ValueVector = SmallVector<Value *, 8>;
62
63// Used to map a vector Value and associated type to its scattered form.
64// The associated type is only non-null for pointer values that are "scattered"
65// when used as pointer operands to load or store.
66//
67// We use std::map because we want iterators to persist across insertion and
68// because the values are relatively large.
69using ScatterMap = std::map<std::pair<Value *, Type *>, ValueVector>;
70
71// Lists Instructions that have been replaced with scalar implementations,
72// along with a pointer to their scattered forms.
73using GatherList = SmallVector<std::pair<Instruction *, ValueVector *>, 16>;
74
75namespace {
76
77struct VectorSplit {
78 // The type of the vector.
79 FixedVectorType *VecTy = nullptr;
80
81 // The number of elements packed in a fragment (other than the remainder).
82 unsigned NumPacked = 0;
83
84 // The number of fragments (scalars or smaller vectors) into which the vector
85 // shall be split.
86 unsigned NumFragments = 0;
87
88 // The type of each complete fragment.
89 Type *SplitTy = nullptr;
90
91 // The type of the remainder (last) fragment; null if all fragments are
92 // complete.
93 Type *RemainderTy = nullptr;
94
95 Type *getFragmentType(unsigned I) const {
96 return RemainderTy && I == NumFragments - 1 ? RemainderTy : SplitTy;
97 }
98};
99
100// Provides a very limited vector-like interface for lazily accessing one
101// component of a scattered vector or vector pointer.
102class Scatterer {
103public:
104 Scatterer() = default;
105
106 // Scatter V into Size components. If new instructions are needed,
107 // insert them before BBI. If Cache is nonnull, use it to cache
108 // the results.
109 Scatterer(BasicBlock::iterator bbi, Value *v, const VectorSplit &VS,
110 ValueVector *cachePtr = nullptr);
111
112 // Return component I, creating a new Value for it if necessary.
113 Value *operator[](unsigned I);
114
115 // Return the number of components.
116 unsigned size() const { return VS.NumFragments; }
117
118private:
119 BasicBlock::iterator BBI;
120 Value *V;
121 VectorSplit VS;
122 bool IsPointer;
123 ValueVector *CachePtr;
124 ValueVector Tmp;
125};
126
127// FCmpSplitter(FCI)(Builder, X, Y, Name) uses Builder to create an FCmp
128// called Name that compares X and Y in the same way as FCI.
129struct FCmpSplitter {
130 FCmpSplitter(FCmpInst &fci) : FCI(fci) {}
131
132 Value *operator()(IRBuilder<> &Builder, Value *Op0, Value *Op1,
133 const Twine &Name) const {
134 return Builder.CreateFCmp(P: FCI.getPredicate(), LHS: Op0, RHS: Op1, Name);
135 }
136
137 FCmpInst &FCI;
138};
139
140// ICmpSplitter(ICI)(Builder, X, Y, Name) uses Builder to create an ICmp
141// called Name that compares X and Y in the same way as ICI.
142struct ICmpSplitter {
143 ICmpSplitter(ICmpInst &ici) : ICI(ici) {}
144
145 Value *operator()(IRBuilder<> &Builder, Value *Op0, Value *Op1,
146 const Twine &Name) const {
147 return Builder.CreateICmp(P: ICI.getPredicate(), LHS: Op0, RHS: Op1, Name);
148 }
149
150 ICmpInst &ICI;
151};
152
153// UnarySplitter(UO)(Builder, X, Name) uses Builder to create
154// a unary operator like UO called Name with operand X.
155struct UnarySplitter {
156 UnarySplitter(UnaryOperator &uo) : UO(uo) {}
157
158 Value *operator()(IRBuilder<> &Builder, Value *Op, const Twine &Name) const {
159 return Builder.CreateUnOp(Opc: UO.getOpcode(), V: Op, Name);
160 }
161
162 UnaryOperator &UO;
163};
164
165// BinarySplitter(BO)(Builder, X, Y, Name) uses Builder to create
166// a binary operator like BO called Name with operands X and Y.
167struct BinarySplitter {
168 BinarySplitter(BinaryOperator &bo) : BO(bo) {}
169
170 Value *operator()(IRBuilder<> &Builder, Value *Op0, Value *Op1,
171 const Twine &Name) const {
172 return Builder.CreateBinOp(Opc: BO.getOpcode(), LHS: Op0, RHS: Op1, Name);
173 }
174
175 BinaryOperator &BO;
176};
177
178// Information about a load or store that we're scalarizing.
179struct VectorLayout {
180 VectorLayout() = default;
181
182 // Return the alignment of fragment Frag.
183 Align getFragmentAlign(unsigned Frag) {
184 return commonAlignment(A: VecAlign, Offset: Frag * SplitSize);
185 }
186
187 // The split of the underlying vector type.
188 VectorSplit VS;
189
190 // The alignment of the vector.
191 Align VecAlign;
192
193 // The size of each (non-remainder) fragment in bytes.
194 uint64_t SplitSize = 0;
195};
196} // namespace
197
198static bool isStructOfMatchingFixedVectors(Type *Ty) {
199 if (!isa<StructType>(Val: Ty))
200 return false;
201 unsigned StructSize = Ty->getNumContainedTypes();
202 if (StructSize < 1)
203 return false;
204 FixedVectorType *VecTy = dyn_cast<FixedVectorType>(Val: Ty->getContainedType(i: 0));
205 if (!VecTy)
206 return false;
207 unsigned VecSize = VecTy->getNumElements();
208 for (unsigned I = 1; I < StructSize; I++) {
209 VecTy = dyn_cast<FixedVectorType>(Val: Ty->getContainedType(i: I));
210 if (!VecTy || VecSize != VecTy->getNumElements())
211 return false;
212 }
213 return true;
214}
215
216/// Concatenate the given fragments to a single vector value of the type
217/// described in @p VS.
218static Value *concatenate(IRBuilder<> &Builder, ArrayRef<Value *> Fragments,
219 const VectorSplit &VS, Twine Name) {
220 unsigned NumElements = VS.VecTy->getNumElements();
221 SmallVector<int> ExtendMask;
222 SmallVector<int> InsertMask;
223
224 if (VS.NumPacked > 1) {
225 // Prepare the shufflevector masks once and re-use them for all
226 // fragments.
227 ExtendMask.resize(N: NumElements, NV: -1);
228 for (unsigned I = 0; I < VS.NumPacked; ++I)
229 ExtendMask[I] = I;
230
231 InsertMask.resize(N: NumElements);
232 for (unsigned I = 0; I < NumElements; ++I)
233 InsertMask[I] = I;
234 }
235
236 Value *Res = PoisonValue::get(T: VS.VecTy);
237 for (unsigned I = 0; I < VS.NumFragments; ++I) {
238 Value *Fragment = Fragments[I];
239
240 unsigned NumPacked = VS.NumPacked;
241 if (I == VS.NumFragments - 1 && VS.RemainderTy) {
242 if (auto *RemVecTy = dyn_cast<FixedVectorType>(Val: VS.RemainderTy))
243 NumPacked = RemVecTy->getNumElements();
244 else
245 NumPacked = 1;
246 }
247
248 if (NumPacked == 1) {
249 Res = Builder.CreateInsertElement(Vec: Res, NewElt: Fragment, Idx: I * VS.NumPacked,
250 Name: Name + ".upto" + Twine(I));
251 } else {
252 if (NumPacked < VS.NumPacked) {
253 // If last pack of remained bits not match current ExtendMask size.
254 ExtendMask.truncate(N: NumPacked);
255 ExtendMask.resize(N: NumElements, NV: -1);
256 }
257
258 Fragment = Builder.CreateShuffleVector(
259 V1: Fragment, V2: PoisonValue::get(T: Fragment->getType()), Mask: ExtendMask);
260 if (I == 0) {
261 Res = Fragment;
262 } else {
263 for (unsigned J = 0; J < NumPacked; ++J)
264 InsertMask[I * VS.NumPacked + J] = NumElements + J;
265 Res = Builder.CreateShuffleVector(V1: Res, V2: Fragment, Mask: InsertMask,
266 Name: Name + ".upto" + Twine(I));
267 for (unsigned J = 0; J < NumPacked; ++J)
268 InsertMask[I * VS.NumPacked + J] = I * VS.NumPacked + J;
269 }
270 }
271 }
272
273 return Res;
274}
275
276namespace {
277class ScalarizerVisitor : public InstVisitor<ScalarizerVisitor, bool> {
278public:
279 ScalarizerVisitor(DominatorTree *DT, const TargetTransformInfo *TTI,
280 ScalarizerPassOptions Options)
281 : DT(DT), TTI(TTI),
282 ScalarizeVariableInsertExtract(Options.ScalarizeVariableInsertExtract),
283 ScalarizeLoadStore(Options.ScalarizeLoadStore),
284 ScalarizeMinBits(Options.ScalarizeMinBits) {}
285
286 bool visit(Function &F);
287
288 // InstVisitor methods. They return true if the instruction was scalarized,
289 // false if nothing changed.
290 bool visitInstruction(Instruction &I) { return false; }
291 bool visitSelectInst(SelectInst &SI);
292 bool visitICmpInst(ICmpInst &ICI);
293 bool visitFCmpInst(FCmpInst &FCI);
294 bool visitUnaryOperator(UnaryOperator &UO);
295 bool visitBinaryOperator(BinaryOperator &BO);
296 bool visitGetElementPtrInst(GetElementPtrInst &GEPI);
297 bool visitCastInst(CastInst &CI);
298 bool visitBitCastInst(BitCastInst &BCI);
299 bool visitInsertElementInst(InsertElementInst &IEI);
300 bool visitExtractElementInst(ExtractElementInst &EEI);
301 bool visitExtractValueInst(ExtractValueInst &EVI);
302 bool visitShuffleVectorInst(ShuffleVectorInst &SVI);
303 bool visitPHINode(PHINode &PHI);
304 bool visitLoadInst(LoadInst &LI);
305 bool visitStoreInst(StoreInst &SI);
306 bool visitCallInst(CallInst &ICI);
307 bool visitFreezeInst(FreezeInst &FI);
308
309private:
310 Scatterer scatter(Instruction *Point, Value *V, const VectorSplit &VS);
311 void gather(Instruction *Op, const ValueVector &CV, const VectorSplit &VS);
312 void replaceUses(Instruction *Op, Value *CV);
313 bool canTransferMetadata(unsigned Kind);
314 void transferMetadataAndIRFlags(Instruction *Op, const ValueVector &CV);
315 std::optional<VectorSplit> getVectorSplit(Type *Ty);
316 std::optional<VectorLayout> getVectorLayout(Type *Ty, Align Alignment,
317 const DataLayout &DL);
318 bool finish();
319
320 template<typename T> bool splitUnary(Instruction &, const T &);
321 template<typename T> bool splitBinary(Instruction &, const T &);
322
323 bool splitCall(CallInst &CI);
324
325 ScatterMap Scattered;
326 GatherList Gathered;
327 bool Scalarized;
328
329 SmallVector<WeakTrackingVH, 32> PotentiallyDeadInstrs;
330
331 DominatorTree *DT;
332 const TargetTransformInfo *TTI;
333
334 const bool ScalarizeVariableInsertExtract;
335 const bool ScalarizeLoadStore;
336 const unsigned ScalarizeMinBits;
337};
338
339class ScalarizerLegacyPass : public FunctionPass {
340public:
341 static char ID;
342 ScalarizerPassOptions Options;
343 ScalarizerLegacyPass() : FunctionPass(ID), Options() {}
344 ScalarizerLegacyPass(const ScalarizerPassOptions &Options);
345 bool runOnFunction(Function &F) override;
346 void getAnalysisUsage(AnalysisUsage &AU) const override;
347};
348
349} // end anonymous namespace
350
351ScalarizerLegacyPass::ScalarizerLegacyPass(const ScalarizerPassOptions &Options)
352 : FunctionPass(ID), Options(Options) {}
353
354void ScalarizerLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
355 AU.addRequired<DominatorTreeWrapperPass>();
356 AU.addRequired<TargetTransformInfoWrapperPass>();
357 AU.addPreserved<DominatorTreeWrapperPass>();
358}
359
360char ScalarizerLegacyPass::ID = 0;
361INITIALIZE_PASS_BEGIN(ScalarizerLegacyPass, "scalarizer",
362 "Scalarize vector operations", false, false)
363INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
364INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
365INITIALIZE_PASS_END(ScalarizerLegacyPass, "scalarizer",
366 "Scalarize vector operations", false, false)
367
368Scatterer::Scatterer(BasicBlock::iterator bbi, Value *v, const VectorSplit &VS,
369 ValueVector *cachePtr)
370 : BBI(bbi), V(v), VS(VS), CachePtr(cachePtr) {
371 IsPointer = V->getType()->isPointerTy();
372 if (!CachePtr) {
373 Tmp.resize(N: VS.NumFragments, NV: nullptr);
374 } else {
375 assert((CachePtr->empty() || VS.NumFragments == CachePtr->size() ||
376 IsPointer) &&
377 "Inconsistent vector sizes");
378 if (VS.NumFragments > CachePtr->size())
379 CachePtr->resize(N: VS.NumFragments, NV: nullptr);
380 }
381}
382
383// Return fragment Frag, creating a new Value for it if necessary.
384Value *Scatterer::operator[](unsigned Frag) {
385 ValueVector &CV = CachePtr ? *CachePtr : Tmp;
386 // Try to reuse a previous value.
387 if (CV[Frag])
388 return CV[Frag];
389 IRBuilder<> Builder(BBI);
390 Builder.disableGEPCanonicalization();
391 if (IsPointer) {
392 if (Frag == 0)
393 CV[Frag] = V;
394 else
395 CV[Frag] = Builder.CreateConstGEP1_32(Ty: VS.SplitTy, Ptr: V, Idx0: Frag,
396 Name: V->getName() + ".i" + Twine(Frag));
397 return CV[Frag];
398 }
399
400 Type *FragmentTy = VS.getFragmentType(I: Frag);
401
402 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: FragmentTy)) {
403 SmallVector<int> Mask;
404 for (unsigned J = 0; J < VecTy->getNumElements(); ++J)
405 Mask.push_back(Elt: Frag * VS.NumPacked + J);
406 CV[Frag] =
407 Builder.CreateShuffleVector(V1: V, V2: PoisonValue::get(T: V->getType()), Mask,
408 Name: V->getName() + ".i" + Twine(Frag));
409 } else {
410 // Search through a chain of InsertElementInsts looking for element Frag.
411 // Record other elements in the cache. The new V is still suitable
412 // for all uncached indices.
413 while (true) {
414 InsertElementInst *Insert = dyn_cast<InsertElementInst>(Val: V);
415 if (!Insert)
416 break;
417 ConstantInt *Idx = dyn_cast<ConstantInt>(Val: Insert->getOperand(i_nocapture: 2));
418 if (!Idx)
419 break;
420 unsigned J = Idx->getZExtValue();
421 V = Insert->getOperand(i_nocapture: 0);
422 if (Frag * VS.NumPacked == J) {
423 CV[Frag] = Insert->getOperand(i_nocapture: 1);
424 return CV[Frag];
425 }
426
427 if (VS.NumPacked == 1 && !CV[J]) {
428 // Only cache the first entry we find for each index we're not actively
429 // searching for. This prevents us from going too far up the chain and
430 // caching incorrect entries.
431 CV[J] = Insert->getOperand(i_nocapture: 1);
432 }
433 }
434 CV[Frag] = Builder.CreateExtractElement(Vec: V, Idx: Frag * VS.NumPacked,
435 Name: V->getName() + ".i" + Twine(Frag));
436 }
437
438 return CV[Frag];
439}
440
441bool ScalarizerLegacyPass::runOnFunction(Function &F) {
442 if (skipFunction(F))
443 return false;
444
445 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
446 const TargetTransformInfo *TTI =
447 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
448 ScalarizerVisitor Impl(DT, TTI, Options);
449 return Impl.visit(F);
450}
451
452FunctionPass *llvm::createScalarizerPass(const ScalarizerPassOptions &Options) {
453 return new ScalarizerLegacyPass(Options);
454}
455
456bool ScalarizerVisitor::visit(Function &F) {
457 assert(Gathered.empty() && Scattered.empty());
458
459 Scalarized = false;
460
461 // To ensure we replace gathered components correctly we need to do an ordered
462 // traversal of the basic blocks in the function.
463 ReversePostOrderTraversal<BasicBlock *> RPOT(&F.getEntryBlock());
464 for (BasicBlock *BB : RPOT) {
465 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
466 Instruction *I = &*II;
467 bool Done = InstVisitor::visit(I);
468 ++II;
469 if (Done && I->getType()->isVoidTy()) {
470 I->eraseFromParent();
471 Scalarized = true;
472 }
473 }
474 }
475 return finish();
476}
477
478// Return a scattered form of V that can be accessed by Point. V must be a
479// vector or a pointer to a vector.
480Scatterer ScalarizerVisitor::scatter(Instruction *Point, Value *V,
481 const VectorSplit &VS) {
482 if (Argument *VArg = dyn_cast<Argument>(Val: V)) {
483 // Put the scattered form of arguments in the entry block,
484 // so that it can be used everywhere.
485 Function *F = VArg->getParent();
486 BasicBlock *BB = &F->getEntryBlock();
487 return Scatterer(BB->begin(), V, VS, &Scattered[{V, VS.SplitTy}]);
488 }
489 if (Instruction *VOp = dyn_cast<Instruction>(Val: V)) {
490 // When scalarizing PHI nodes we might try to examine/rewrite InsertElement
491 // nodes in predecessors. If those predecessors are unreachable from entry,
492 // then the IR in those blocks could have unexpected properties resulting in
493 // infinite loops in Scatterer::operator[]. By simply treating values
494 // originating from instructions in unreachable blocks as undef we do not
495 // need to analyse them further.
496 if (!DT->isReachableFromEntry(A: VOp->getParent()))
497 return Scatterer(Point->getIterator(), PoisonValue::get(T: V->getType()),
498 VS);
499 // Put the scattered form of an instruction directly after the
500 // instruction, skipping over PHI nodes.
501 return Scatterer(skipPastPhiNodes(Itr: std::next(x: BasicBlock::iterator(VOp))), V,
502 VS, &Scattered[{V, VS.SplitTy}]);
503 }
504 // In the fallback case, just put the scattered before Point and
505 // keep the result local to Point.
506 return Scatterer(Point->getIterator(), V, VS);
507}
508
509// Replace Op with the gathered form of the components in CV. Defer the
510// deletion of Op and creation of the gathered form to the end of the pass,
511// so that we can avoid creating the gathered form if all uses of Op are
512// replaced with uses of CV.
513void ScalarizerVisitor::gather(Instruction *Op, const ValueVector &CV,
514 const VectorSplit &VS) {
515 transferMetadataAndIRFlags(Op, CV);
516
517 // If we already have a scattered form of Op (created from ExtractElements
518 // of Op itself), replace them with the new form.
519 ValueVector &SV = Scattered[{Op, VS.SplitTy}];
520 if (!SV.empty()) {
521 for (unsigned I = 0, E = SV.size(); I != E; ++I) {
522 Value *V = SV[I];
523 if (V == nullptr || SV[I] == CV[I])
524 continue;
525
526 Instruction *Old = cast<Instruction>(Val: V);
527 if (isa<Instruction>(Val: CV[I]))
528 CV[I]->takeName(V: Old);
529 Old->replaceAllUsesWith(V: CV[I]);
530 PotentiallyDeadInstrs.emplace_back(Args&: Old);
531 }
532 }
533 SV = CV;
534 Gathered.push_back(Elt: GatherList::value_type(Op, &SV));
535}
536
537// Replace Op with CV and collect Op has a potentially dead instruction.
538void ScalarizerVisitor::replaceUses(Instruction *Op, Value *CV) {
539 if (CV != Op) {
540 Op->replaceAllUsesWith(V: CV);
541 PotentiallyDeadInstrs.emplace_back(Args&: Op);
542 Scalarized = true;
543 }
544}
545
546// Return true if it is safe to transfer the given metadata tag from
547// vector to scalar instructions.
548bool ScalarizerVisitor::canTransferMetadata(unsigned Tag) {
549 return (Tag == LLVMContext::MD_tbaa
550 || Tag == LLVMContext::MD_fpmath
551 || Tag == LLVMContext::MD_tbaa_struct
552 || Tag == LLVMContext::MD_invariant_load
553 || Tag == LLVMContext::MD_alias_scope
554 || Tag == LLVMContext::MD_noalias
555 || Tag == LLVMContext::MD_mem_parallel_loop_access
556 || Tag == LLVMContext::MD_access_group);
557}
558
559// Transfer metadata from Op to the instructions in CV if it is known
560// to be safe to do so.
561void ScalarizerVisitor::transferMetadataAndIRFlags(Instruction *Op,
562 const ValueVector &CV) {
563 SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
564 Op->getAllMetadataOtherThanDebugLoc(MDs);
565 for (Value *V : CV) {
566 if (Instruction *New = dyn_cast<Instruction>(Val: V)) {
567 for (const auto &MD : MDs)
568 if (canTransferMetadata(Tag: MD.first))
569 New->setMetadata(KindID: MD.first, Node: MD.second);
570 New->copyIRFlags(V: Op);
571 if (Op->getDebugLoc() && !New->getDebugLoc())
572 New->setDebugLoc(Op->getDebugLoc());
573 }
574 }
575}
576
577// Determine how Ty is split, if at all.
578std::optional<VectorSplit> ScalarizerVisitor::getVectorSplit(Type *Ty) {
579 VectorSplit Split;
580 Split.VecTy = dyn_cast<FixedVectorType>(Val: Ty);
581 if (!Split.VecTy)
582 return {};
583
584 unsigned NumElems = Split.VecTy->getNumElements();
585 Type *ElemTy = Split.VecTy->getElementType();
586
587 if (NumElems == 1 || ElemTy->isPointerTy() ||
588 2 * ElemTy->getScalarSizeInBits() > ScalarizeMinBits) {
589 Split.NumPacked = 1;
590 Split.NumFragments = NumElems;
591 Split.SplitTy = ElemTy;
592 } else {
593 Split.NumPacked = ScalarizeMinBits / ElemTy->getScalarSizeInBits();
594 if (Split.NumPacked >= NumElems)
595 return {};
596
597 Split.NumFragments = divideCeil(Numerator: NumElems, Denominator: Split.NumPacked);
598 Split.SplitTy = FixedVectorType::get(ElementType: ElemTy, NumElts: Split.NumPacked);
599
600 unsigned RemainderElems = NumElems % Split.NumPacked;
601 if (RemainderElems > 1)
602 Split.RemainderTy = FixedVectorType::get(ElementType: ElemTy, NumElts: RemainderElems);
603 else if (RemainderElems == 1)
604 Split.RemainderTy = ElemTy;
605 }
606
607 return Split;
608}
609
610// Try to fill in Layout from Ty, returning true on success. Alignment is
611// the alignment of the vector, or std::nullopt if the ABI default should be
612// used.
613std::optional<VectorLayout>
614ScalarizerVisitor::getVectorLayout(Type *Ty, Align Alignment,
615 const DataLayout &DL) {
616 std::optional<VectorSplit> VS = getVectorSplit(Ty);
617 if (!VS)
618 return {};
619
620 VectorLayout Layout;
621 Layout.VS = *VS;
622 // Check that we're dealing with full-byte fragments.
623 if (!DL.typeSizeEqualsStoreSize(Ty: VS->SplitTy) ||
624 (VS->RemainderTy && !DL.typeSizeEqualsStoreSize(Ty: VS->RemainderTy)))
625 return {};
626 Layout.VecAlign = Alignment;
627 Layout.SplitSize = DL.getTypeStoreSize(Ty: VS->SplitTy);
628 return Layout;
629}
630
631// Scalarize one-operand instruction I, using Split(Builder, X, Name)
632// to create an instruction like I with operand X and name Name.
633template<typename Splitter>
634bool ScalarizerVisitor::splitUnary(Instruction &I, const Splitter &Split) {
635 std::optional<VectorSplit> VS = getVectorSplit(Ty: I.getType());
636 if (!VS)
637 return false;
638
639 std::optional<VectorSplit> OpVS;
640 if (I.getOperand(i: 0)->getType() == I.getType()) {
641 OpVS = VS;
642 } else {
643 OpVS = getVectorSplit(Ty: I.getOperand(i: 0)->getType());
644 if (!OpVS || VS->NumPacked != OpVS->NumPacked)
645 return false;
646 }
647
648 IRBuilder<> Builder(&I);
649 Scatterer Op = scatter(Point: &I, V: I.getOperand(i: 0), VS: *OpVS);
650 assert(Op.size() == VS->NumFragments && "Mismatched unary operation");
651 ValueVector Res;
652 Res.resize(N: VS->NumFragments);
653 for (unsigned Frag = 0; Frag < VS->NumFragments; ++Frag)
654 Res[Frag] = Split(Builder, Op[Frag], I.getName() + ".i" + Twine(Frag));
655 gather(Op: &I, CV: Res, VS: *VS);
656 return true;
657}
658
659// Scalarize two-operand instruction I, using Split(Builder, X, Y, Name)
660// to create an instruction like I with operands X and Y and name Name.
661template<typename Splitter>
662bool ScalarizerVisitor::splitBinary(Instruction &I, const Splitter &Split) {
663 std::optional<VectorSplit> VS = getVectorSplit(Ty: I.getType());
664 if (!VS)
665 return false;
666
667 std::optional<VectorSplit> OpVS;
668 if (I.getOperand(i: 0)->getType() == I.getType()) {
669 OpVS = VS;
670 } else {
671 OpVS = getVectorSplit(Ty: I.getOperand(i: 0)->getType());
672 if (!OpVS || VS->NumPacked != OpVS->NumPacked)
673 return false;
674 }
675
676 IRBuilder<> Builder(&I);
677 Scatterer VOp0 = scatter(Point: &I, V: I.getOperand(i: 0), VS: *OpVS);
678 Scatterer VOp1 = scatter(Point: &I, V: I.getOperand(i: 1), VS: *OpVS);
679 assert(VOp0.size() == VS->NumFragments && "Mismatched binary operation");
680 assert(VOp1.size() == VS->NumFragments && "Mismatched binary operation");
681 ValueVector Res;
682 Res.resize(N: VS->NumFragments);
683 for (unsigned Frag = 0; Frag < VS->NumFragments; ++Frag) {
684 Value *Op0 = VOp0[Frag];
685 Value *Op1 = VOp1[Frag];
686 Res[Frag] = Split(Builder, Op0, Op1, I.getName() + ".i" + Twine(Frag));
687 }
688 gather(Op: &I, CV: Res, VS: *VS);
689 return true;
690}
691
692/// If a call to a vector typed intrinsic function, split into a scalar call per
693/// element if possible for the intrinsic.
694bool ScalarizerVisitor::splitCall(CallInst &CI) {
695 Type *CallType = CI.getType();
696 bool AreAllVectorsOfMatchingSize = isStructOfMatchingFixedVectors(Ty: CallType);
697 std::optional<VectorSplit> VS;
698 if (AreAllVectorsOfMatchingSize)
699 VS = getVectorSplit(Ty: CallType->getContainedType(i: 0));
700 else
701 VS = getVectorSplit(Ty: CallType);
702 if (!VS)
703 return false;
704
705 Function *F = CI.getCalledFunction();
706 if (!F)
707 return false;
708
709 Intrinsic::ID ID = F->getIntrinsicID();
710
711 if (ID == Intrinsic::not_intrinsic || !isTriviallyScalarizable(ID))
712 return false;
713
714 // unsigned NumElems = VT->getNumElements();
715 unsigned NumArgs = CI.arg_size();
716
717 ValueVector ScalarOperands(NumArgs);
718 SmallVector<Scatterer, 8> Scattered(NumArgs);
719 SmallVector<int> OverloadIdx(NumArgs, -1);
720
721 SmallVector<llvm::Type *, 3> Tys;
722 // Add return type if intrinsic is overloaded on it.
723 if (isVectorIntrinsicWithOverloadTypeAtArg(ID, OpdIdx: -1, TTI))
724 Tys.push_back(Elt: VS->SplitTy);
725
726 if (AreAllVectorsOfMatchingSize) {
727 for (unsigned I = 1; I < CallType->getNumContainedTypes(); I++) {
728 std::optional<VectorSplit> CurrVS =
729 getVectorSplit(Ty: cast<FixedVectorType>(Val: CallType->getContainedType(i: I)));
730 // It is possible for VectorSplit.NumPacked >= NumElems. If that happens a
731 // VectorSplit is not returned and we will bailout of handling this call.
732 // The secondary bailout case is if NumPacked does not match. This can
733 // happen if ScalarizeMinBits is not set to the default. This means with
734 // certain ScalarizeMinBits intrinsics like frexp will only scalarize when
735 // the struct elements have the same bitness.
736 if (!CurrVS || CurrVS->NumPacked != VS->NumPacked)
737 return false;
738 if (isVectorIntrinsicWithStructReturnOverloadAtField(ID, RetIdx: I, TTI))
739 Tys.push_back(Elt: CurrVS->SplitTy);
740 }
741 }
742 // Assumes that any vector type has the same number of elements as the return
743 // vector type, which is true for all current intrinsics.
744 for (unsigned I = 0; I != NumArgs; ++I) {
745 Value *OpI = CI.getOperand(i_nocapture: I);
746 if ([[maybe_unused]] auto *OpVecTy =
747 dyn_cast<FixedVectorType>(Val: OpI->getType())) {
748 assert(OpVecTy->getNumElements() == VS->VecTy->getNumElements());
749 std::optional<VectorSplit> OpVS = getVectorSplit(Ty: OpI->getType());
750 if (!OpVS || OpVS->NumPacked != VS->NumPacked) {
751 // The natural split of the operand doesn't match the result. This could
752 // happen if the vector elements are different and the ScalarizeMinBits
753 // option is used.
754 //
755 // We could in principle handle this case as well, at the cost of
756 // complicating the scattering machinery to support multiple scattering
757 // granularities for a single value.
758 return false;
759 }
760
761 Scattered[I] = scatter(Point: &CI, V: OpI, VS: *OpVS);
762 if (isVectorIntrinsicWithOverloadTypeAtArg(ID, OpdIdx: I, TTI)) {
763 OverloadIdx[I] = Tys.size();
764 Tys.push_back(Elt: OpVS->SplitTy);
765 }
766 } else {
767 ScalarOperands[I] = OpI;
768 if (isVectorIntrinsicWithOverloadTypeAtArg(ID, OpdIdx: I, TTI))
769 Tys.push_back(Elt: OpI->getType());
770 }
771 }
772
773 ValueVector Res(VS->NumFragments);
774 ValueVector ScalarCallOps(NumArgs);
775
776 Function *NewIntrin =
777 Intrinsic::getOrInsertDeclaration(M: F->getParent(), id: ID, OverloadTys: Tys);
778 IRBuilder<> Builder(&CI);
779
780 // Perform actual scalarization, taking care to preserve any scalar operands.
781 for (unsigned I = 0; I < VS->NumFragments; ++I) {
782 bool IsRemainder = I == VS->NumFragments - 1 && VS->RemainderTy;
783 ScalarCallOps.clear();
784
785 if (IsRemainder)
786 Tys[0] = VS->RemainderTy;
787
788 for (unsigned J = 0; J != NumArgs; ++J) {
789 if (isVectorIntrinsicWithScalarOpAtArg(ID, ScalarOpdIdx: J, TTI)) {
790 ScalarCallOps.push_back(Elt: ScalarOperands[J]);
791 } else {
792 ScalarCallOps.push_back(Elt: Scattered[J][I]);
793 if (IsRemainder && OverloadIdx[J] >= 0)
794 Tys[OverloadIdx[J]] = Scattered[J][I]->getType();
795 }
796 }
797
798 if (IsRemainder)
799 NewIntrin = Intrinsic::getOrInsertDeclaration(M: F->getParent(), id: ID, OverloadTys: Tys);
800
801 Res[I] = Builder.CreateCall(Callee: NewIntrin, Args: ScalarCallOps,
802 Name: CI.getName() + ".i" + Twine(I));
803 }
804
805 gather(Op: &CI, CV: Res, VS: *VS);
806 return true;
807}
808
809bool ScalarizerVisitor::visitSelectInst(SelectInst &SI) {
810 std::optional<VectorSplit> VS = getVectorSplit(Ty: SI.getType());
811 if (!VS)
812 return false;
813
814 std::optional<VectorSplit> CondVS;
815 if (isa<FixedVectorType>(Val: SI.getCondition()->getType())) {
816 CondVS = getVectorSplit(Ty: SI.getCondition()->getType());
817 if (!CondVS || CondVS->NumPacked != VS->NumPacked) {
818 // This happens when ScalarizeMinBits is used.
819 return false;
820 }
821 }
822
823 IRBuilder<> Builder(&SI);
824 Scatterer VOp1 = scatter(Point: &SI, V: SI.getOperand(i_nocapture: 1), VS: *VS);
825 Scatterer VOp2 = scatter(Point: &SI, V: SI.getOperand(i_nocapture: 2), VS: *VS);
826 assert(VOp1.size() == VS->NumFragments && "Mismatched select");
827 assert(VOp2.size() == VS->NumFragments && "Mismatched select");
828 ValueVector Res;
829 Res.resize(N: VS->NumFragments);
830
831 if (CondVS) {
832 Scatterer VOp0 = scatter(Point: &SI, V: SI.getOperand(i_nocapture: 0), VS: *CondVS);
833 assert(VOp0.size() == CondVS->NumFragments && "Mismatched select");
834 for (unsigned I = 0; I < VS->NumFragments; ++I) {
835 Value *Op0 = VOp0[I];
836 Value *Op1 = VOp1[I];
837 Value *Op2 = VOp2[I];
838 Res[I] = Builder.CreateSelect(C: Op0, True: Op1, False: Op2,
839 Name: SI.getName() + ".i" + Twine(I));
840 }
841 } else {
842 Value *Op0 = SI.getOperand(i_nocapture: 0);
843 for (unsigned I = 0; I < VS->NumFragments; ++I) {
844 Value *Op1 = VOp1[I];
845 Value *Op2 = VOp2[I];
846 Res[I] = Builder.CreateSelect(C: Op0, True: Op1, False: Op2,
847 Name: SI.getName() + ".i" + Twine(I));
848 }
849 }
850 gather(Op: &SI, CV: Res, VS: *VS);
851 return true;
852}
853
854bool ScalarizerVisitor::visitICmpInst(ICmpInst &ICI) {
855 return splitBinary(I&: ICI, Split: ICmpSplitter(ICI));
856}
857
858bool ScalarizerVisitor::visitFCmpInst(FCmpInst &FCI) {
859 return splitBinary(I&: FCI, Split: FCmpSplitter(FCI));
860}
861
862bool ScalarizerVisitor::visitUnaryOperator(UnaryOperator &UO) {
863 return splitUnary(I&: UO, Split: UnarySplitter(UO));
864}
865
866bool ScalarizerVisitor::visitBinaryOperator(BinaryOperator &BO) {
867 return splitBinary(I&: BO, Split: BinarySplitter(BO));
868}
869
870bool ScalarizerVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) {
871 std::optional<VectorSplit> VS = getVectorSplit(Ty: GEPI.getType());
872 if (!VS)
873 return false;
874
875 IRBuilder<> Builder(&GEPI);
876 Builder.disableGEPCanonicalization();
877 unsigned NumIndices = GEPI.getNumIndices();
878
879 // The base pointer and indices might be scalar even if it's a vector GEP.
880 SmallVector<Value *, 8> ScalarOps{1 + NumIndices};
881 SmallVector<Scatterer, 8> ScatterOps{1 + NumIndices};
882
883 for (unsigned I = 0; I < 1 + NumIndices; ++I) {
884 if (auto *VecTy =
885 dyn_cast<FixedVectorType>(Val: GEPI.getOperand(i_nocapture: I)->getType())) {
886 std::optional<VectorSplit> OpVS = getVectorSplit(Ty: VecTy);
887 if (!OpVS || OpVS->NumPacked != VS->NumPacked) {
888 // This can happen when ScalarizeMinBits is used.
889 return false;
890 }
891 ScatterOps[I] = scatter(Point: &GEPI, V: GEPI.getOperand(i_nocapture: I), VS: *OpVS);
892 } else {
893 ScalarOps[I] = GEPI.getOperand(i_nocapture: I);
894 }
895 }
896
897 ValueVector Res;
898 Res.resize(N: VS->NumFragments);
899 for (unsigned I = 0; I < VS->NumFragments; ++I) {
900 SmallVector<Value *, 8> SplitOps;
901 SplitOps.resize(N: 1 + NumIndices);
902 for (unsigned J = 0; J < 1 + NumIndices; ++J) {
903 if (ScalarOps[J])
904 SplitOps[J] = ScalarOps[J];
905 else
906 SplitOps[J] = ScatterOps[J][I];
907 }
908 Res[I] = Builder.CreateGEP(Ty: GEPI.getSourceElementType(), Ptr: SplitOps[0],
909 IdxList: ArrayRef(SplitOps).drop_front(),
910 Name: GEPI.getName() + ".i" + Twine(I));
911 if (GEPI.isInBounds())
912 if (GetElementPtrInst *NewGEPI = dyn_cast<GetElementPtrInst>(Val: Res[I]))
913 NewGEPI->setIsInBounds();
914 }
915 gather(Op: &GEPI, CV: Res, VS: *VS);
916 return true;
917}
918
919bool ScalarizerVisitor::visitCastInst(CastInst &CI) {
920 std::optional<VectorSplit> DestVS = getVectorSplit(Ty: CI.getDestTy());
921 if (!DestVS)
922 return false;
923
924 std::optional<VectorSplit> SrcVS = getVectorSplit(Ty: CI.getSrcTy());
925 if (!SrcVS || SrcVS->NumPacked != DestVS->NumPacked)
926 return false;
927
928 IRBuilder<> Builder(&CI);
929 Scatterer Op0 = scatter(Point: &CI, V: CI.getOperand(i_nocapture: 0), VS: *SrcVS);
930 assert(Op0.size() == SrcVS->NumFragments && "Mismatched cast");
931 ValueVector Res;
932 Res.resize(N: DestVS->NumFragments);
933 for (unsigned I = 0; I < DestVS->NumFragments; ++I)
934 Res[I] =
935 Builder.CreateCast(Op: CI.getOpcode(), V: Op0[I], DestTy: DestVS->getFragmentType(I),
936 Name: CI.getName() + ".i" + Twine(I));
937 gather(Op: &CI, CV: Res, VS: *DestVS);
938 return true;
939}
940
941bool ScalarizerVisitor::visitBitCastInst(BitCastInst &BCI) {
942 std::optional<VectorSplit> DstVS = getVectorSplit(Ty: BCI.getDestTy());
943 std::optional<VectorSplit> SrcVS = getVectorSplit(Ty: BCI.getSrcTy());
944
945 if (DstVS && !SrcVS && BCI.getSrcTy()->isIntegerTy() && !DstVS->RemainderTy &&
946 DstVS->NumPacked == 1 && DstVS->SplitTy->isIntegerTy()) {
947 IRBuilder<> Builder(&BCI);
948 Builder.SetCurrentDebugLocation(BCI.getDebugLoc());
949 ValueVector Res(DstVS->NumFragments);
950 unsigned FragmentBits = DstVS->SplitTy->getPrimitiveSizeInBits();
951 bool IsBigEndian = BCI.getDataLayout().isBigEndian();
952 for (unsigned I = 0; I < DstVS->NumFragments; ++I) {
953 unsigned FragmentIndex = IsBigEndian ? DstVS->NumFragments - I - 1 : I;
954 Value *Fragment = BCI.getOperand(i_nocapture: 0);
955 if (FragmentIndex)
956 Fragment = Builder.CreateLShr(LHS: Fragment, RHS: FragmentIndex * FragmentBits);
957 Res[I] = Builder.CreateTruncOrBitCast(V: Fragment, DestTy: DstVS->getFragmentType(I),
958 Name: BCI.getName() + ".i" + Twine(I));
959 }
960 gather(Op: &BCI, CV: Res, VS: *DstVS);
961 return true;
962 }
963
964 if (!DstVS && SrcVS && BCI.getDestTy()->isIntegerTy() &&
965 !SrcVS->RemainderTy && SrcVS->NumPacked == 1 &&
966 SrcVS->SplitTy->isIntegerTy()) {
967 IRBuilder<> Builder(&BCI);
968 Builder.SetCurrentDebugLocation(BCI.getDebugLoc());
969 Scatterer Op0 = scatter(Point: &BCI, V: BCI.getOperand(i_nocapture: 0), VS: *SrcVS);
970 Value *Result = nullptr;
971 unsigned FragmentBits = SrcVS->SplitTy->getPrimitiveSizeInBits();
972 bool IsBigEndian = BCI.getDataLayout().isBigEndian();
973 for (unsigned I = 0; I < SrcVS->NumFragments; ++I) {
974 unsigned FragmentIndex = IsBigEndian ? SrcVS->NumFragments - I - 1 : I;
975 Value *Fragment = Builder.CreateZExtOrTrunc(V: Op0[I], DestTy: BCI.getDestTy());
976 if (FragmentIndex)
977 Fragment = Builder.CreateShl(LHS: Fragment, RHS: FragmentIndex * FragmentBits);
978 Result = Result ? Builder.CreateOr(LHS: Result, RHS: Fragment) : Fragment;
979 }
980 replaceUses(Op: &BCI, CV: Result);
981 return true;
982 }
983
984 if (!DstVS || !SrcVS || DstVS->RemainderTy || SrcVS->RemainderTy)
985 return false;
986
987 const bool isPointerTy = DstVS->VecTy->getElementType()->isPointerTy();
988
989 // Vectors of pointers are always fully scalarized.
990 assert(!isPointerTy || (DstVS->NumPacked == 1 && SrcVS->NumPacked == 1));
991
992 IRBuilder<> Builder(&BCI);
993 Scatterer Op0 = scatter(Point: &BCI, V: BCI.getOperand(i_nocapture: 0), VS: *SrcVS);
994 ValueVector Res;
995 Res.resize(N: DstVS->NumFragments);
996
997 unsigned DstSplitBits = DstVS->SplitTy->getPrimitiveSizeInBits();
998 unsigned SrcSplitBits = SrcVS->SplitTy->getPrimitiveSizeInBits();
999
1000 if (isPointerTy || DstSplitBits == SrcSplitBits) {
1001 assert(DstVS->NumFragments == SrcVS->NumFragments);
1002 for (unsigned I = 0; I < DstVS->NumFragments; ++I) {
1003 Res[I] = Builder.CreateBitCast(V: Op0[I], DestTy: DstVS->getFragmentType(I),
1004 Name: BCI.getName() + ".i" + Twine(I));
1005 }
1006 } else if (SrcSplitBits % DstSplitBits == 0) {
1007 // Convert each source fragment to the same-sized destination vector and
1008 // then scatter the result to the destination.
1009 VectorSplit MidVS;
1010 MidVS.NumPacked = DstVS->NumPacked;
1011 MidVS.NumFragments = SrcSplitBits / DstSplitBits;
1012 MidVS.VecTy = FixedVectorType::get(ElementType: DstVS->VecTy->getElementType(),
1013 NumElts: MidVS.NumPacked * MidVS.NumFragments);
1014 MidVS.SplitTy = DstVS->SplitTy;
1015
1016 unsigned ResI = 0;
1017 for (unsigned I = 0; I < SrcVS->NumFragments; ++I) {
1018 Value *V = Op0[I];
1019
1020 // Look through any existing bitcasts before converting to <N x t2>.
1021 // In the best case, the resulting conversion might be a no-op.
1022 Instruction *VI;
1023 while ((VI = dyn_cast<Instruction>(Val: V)) &&
1024 VI->getOpcode() == Instruction::BitCast)
1025 V = VI->getOperand(i: 0);
1026
1027 V = Builder.CreateBitCast(V, DestTy: MidVS.VecTy, Name: V->getName() + ".cast");
1028
1029 Scatterer Mid = scatter(Point: &BCI, V, VS: MidVS);
1030 for (unsigned J = 0; J < MidVS.NumFragments; ++J)
1031 Res[ResI++] = Mid[J];
1032 }
1033 } else if (DstSplitBits % SrcSplitBits == 0) {
1034 // Gather enough source fragments to make up a destination fragment and
1035 // then convert to the destination type.
1036 VectorSplit MidVS;
1037 MidVS.NumFragments = DstSplitBits / SrcSplitBits;
1038 MidVS.NumPacked = SrcVS->NumPacked;
1039 MidVS.VecTy = FixedVectorType::get(ElementType: SrcVS->VecTy->getElementType(),
1040 NumElts: MidVS.NumPacked * MidVS.NumFragments);
1041 MidVS.SplitTy = SrcVS->SplitTy;
1042
1043 unsigned SrcI = 0;
1044 SmallVector<Value *, 8> ConcatOps;
1045 ConcatOps.resize(N: MidVS.NumFragments);
1046 for (unsigned I = 0; I < DstVS->NumFragments; ++I) {
1047 for (unsigned J = 0; J < MidVS.NumFragments; ++J)
1048 ConcatOps[J] = Op0[SrcI++];
1049 Value *V = concatenate(Builder, Fragments: ConcatOps, VS: MidVS,
1050 Name: BCI.getName() + ".i" + Twine(I));
1051 Res[I] = Builder.CreateBitCast(V, DestTy: DstVS->getFragmentType(I),
1052 Name: BCI.getName() + ".i" + Twine(I));
1053 }
1054 } else {
1055 return false;
1056 }
1057
1058 gather(Op: &BCI, CV: Res, VS: *DstVS);
1059 return true;
1060}
1061
1062bool ScalarizerVisitor::visitInsertElementInst(InsertElementInst &IEI) {
1063 std::optional<VectorSplit> VS = getVectorSplit(Ty: IEI.getType());
1064 if (!VS)
1065 return false;
1066
1067 IRBuilder<> Builder(&IEI);
1068 Scatterer Op0 = scatter(Point: &IEI, V: IEI.getOperand(i_nocapture: 0), VS: *VS);
1069 Value *NewElt = IEI.getOperand(i_nocapture: 1);
1070 Value *InsIdx = IEI.getOperand(i_nocapture: 2);
1071
1072 ValueVector Res;
1073 Res.resize(N: VS->NumFragments);
1074
1075 if (auto *CI = dyn_cast<ConstantInt>(Val: InsIdx)) {
1076 unsigned Idx = CI->getZExtValue();
1077 unsigned Fragment = Idx / VS->NumPacked;
1078 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1079 if (I == Fragment) {
1080 bool IsPacked = VS->NumPacked > 1;
1081 if (Fragment == VS->NumFragments - 1 && VS->RemainderTy &&
1082 !VS->RemainderTy->isVectorTy())
1083 IsPacked = false;
1084 if (IsPacked) {
1085 Res[I] =
1086 Builder.CreateInsertElement(Vec: Op0[I], NewElt, Idx: Idx % VS->NumPacked);
1087 } else {
1088 Res[I] = NewElt;
1089 }
1090 } else {
1091 Res[I] = Op0[I];
1092 }
1093 }
1094 } else {
1095 // Never split a variable insertelement that isn't fully scalarized.
1096 if (!ScalarizeVariableInsertExtract || VS->NumPacked > 1)
1097 return false;
1098
1099 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1100 Value *ShouldReplace =
1101 Builder.CreateICmpEQ(LHS: InsIdx, RHS: ConstantInt::get(Ty: InsIdx->getType(), V: I),
1102 Name: InsIdx->getName() + ".is." + Twine(I));
1103 Value *OldElt = Op0[I];
1104 Res[I] = Builder.CreateSelect(C: ShouldReplace, True: NewElt, False: OldElt,
1105 Name: IEI.getName() + ".i" + Twine(I));
1106 }
1107 }
1108
1109 gather(Op: &IEI, CV: Res, VS: *VS);
1110 return true;
1111}
1112
1113bool ScalarizerVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
1114 Value *Op = EVI.getOperand(i_nocapture: 0);
1115 Type *OpTy = Op->getType();
1116 ValueVector Res;
1117 if (!isStructOfMatchingFixedVectors(Ty: OpTy))
1118 return false;
1119 if (CallInst *CI = dyn_cast<CallInst>(Val: Op)) {
1120 Function *F = CI->getCalledFunction();
1121 if (!F)
1122 return false;
1123 Intrinsic::ID ID = F->getIntrinsicID();
1124 if (ID == Intrinsic::not_intrinsic || !isTriviallyScalarizable(ID))
1125 return false;
1126 // Note: Fall through means Operand is a`CallInst` and it is defined in
1127 // `isTriviallyScalarizable`.
1128 } else
1129 return false;
1130 Type *VecType = cast<FixedVectorType>(Val: OpTy->getContainedType(i: 0));
1131 std::optional<VectorSplit> VS = getVectorSplit(Ty: VecType);
1132 if (!VS)
1133 return false;
1134 for (unsigned I = 1; I < OpTy->getNumContainedTypes(); I++) {
1135 std::optional<VectorSplit> CurrVS =
1136 getVectorSplit(Ty: cast<FixedVectorType>(Val: OpTy->getContainedType(i: I)));
1137 // It is possible for VectorSplit.NumPacked >= NumElems. If that happens a
1138 // VectorSplit is not returned and we will bailout of handling this call.
1139 // The secondary bailout case is if NumPacked does not match. This can
1140 // happen if ScalarizeMinBits is not set to the default. This means with
1141 // certain ScalarizeMinBits intrinsics like frexp will only scalarize when
1142 // the struct elements have the same bitness.
1143 if (!CurrVS || CurrVS->NumPacked != VS->NumPacked)
1144 return false;
1145 }
1146 IRBuilder<> Builder(&EVI);
1147 Scatterer Op0 = scatter(Point: &EVI, V: Op, VS: *VS);
1148 assert(!EVI.getIndices().empty() && "Make sure an index exists");
1149 // Note for our use case we only care about the top level index.
1150 unsigned Index = EVI.getIndices()[0];
1151 for (unsigned OpIdx = 0; OpIdx < Op0.size(); ++OpIdx) {
1152 Value *ResElem = Builder.CreateExtractValue(
1153 Agg: Op0[OpIdx], Idxs: Index, Name: EVI.getName() + ".elem" + Twine(Index));
1154 Res.push_back(Elt: ResElem);
1155 }
1156
1157 Type *ActualVecType = cast<FixedVectorType>(Val: OpTy->getContainedType(i: Index));
1158 std::optional<VectorSplit> AVS = getVectorSplit(Ty: ActualVecType);
1159 gather(Op: &EVI, CV: Res, VS: *AVS);
1160 return true;
1161}
1162
1163bool ScalarizerVisitor::visitExtractElementInst(ExtractElementInst &EEI) {
1164 std::optional<VectorSplit> VS = getVectorSplit(Ty: EEI.getOperand(i_nocapture: 0)->getType());
1165 if (!VS)
1166 return false;
1167
1168 IRBuilder<> Builder(&EEI);
1169 Scatterer Op0 = scatter(Point: &EEI, V: EEI.getOperand(i_nocapture: 0), VS: *VS);
1170 Value *ExtIdx = EEI.getOperand(i_nocapture: 1);
1171
1172 if (auto *CI = dyn_cast<ConstantInt>(Val: ExtIdx)) {
1173 unsigned Idx = CI->getZExtValue();
1174 if (Idx >= VS->VecTy->getNumElements())
1175 return false;
1176 unsigned Fragment = Idx / VS->NumPacked;
1177 Value *Res = Op0[Fragment];
1178 bool IsPacked = VS->NumPacked > 1;
1179 if (Fragment == VS->NumFragments - 1 && VS->RemainderTy &&
1180 !VS->RemainderTy->isVectorTy())
1181 IsPacked = false;
1182 if (IsPacked)
1183 Res = Builder.CreateExtractElement(Vec: Res, Idx: Idx % VS->NumPacked);
1184 replaceUses(Op: &EEI, CV: Res);
1185 return true;
1186 }
1187
1188 // Never split a variable extractelement that isn't fully scalarized.
1189 if (!ScalarizeVariableInsertExtract || VS->NumPacked > 1)
1190 return false;
1191
1192 Value *Res = PoisonValue::get(T: VS->VecTy->getElementType());
1193 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1194 Value *ShouldExtract =
1195 Builder.CreateICmpEQ(LHS: ExtIdx, RHS: ConstantInt::get(Ty: ExtIdx->getType(), V: I),
1196 Name: ExtIdx->getName() + ".is." + Twine(I));
1197 Value *Elt = Op0[I];
1198 Res = Builder.CreateSelect(C: ShouldExtract, True: Elt, False: Res,
1199 Name: EEI.getName() + ".upto" + Twine(I));
1200 }
1201 replaceUses(Op: &EEI, CV: Res);
1202 return true;
1203}
1204
1205bool ScalarizerVisitor::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
1206 std::optional<VectorSplit> VS = getVectorSplit(Ty: SVI.getType());
1207 std::optional<VectorSplit> VSOp =
1208 getVectorSplit(Ty: SVI.getOperand(i_nocapture: 0)->getType());
1209 if (!VS || !VSOp || VS->NumPacked > 1 || VSOp->NumPacked > 1)
1210 return false;
1211
1212 Scatterer Op0 = scatter(Point: &SVI, V: SVI.getOperand(i_nocapture: 0), VS: *VSOp);
1213 Scatterer Op1 = scatter(Point: &SVI, V: SVI.getOperand(i_nocapture: 1), VS: *VSOp);
1214 ValueVector Res;
1215 Res.resize(N: VS->NumFragments);
1216
1217 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1218 int Selector = SVI.getMaskValue(Elt: I);
1219 if (Selector < 0)
1220 Res[I] = PoisonValue::get(T: VS->VecTy->getElementType());
1221 else if (unsigned(Selector) < Op0.size())
1222 Res[I] = Op0[Selector];
1223 else
1224 Res[I] = Op1[Selector - Op0.size()];
1225 }
1226 gather(Op: &SVI, CV: Res, VS: *VS);
1227 return true;
1228}
1229
1230bool ScalarizerVisitor::visitPHINode(PHINode &PHI) {
1231 std::optional<VectorSplit> VS = getVectorSplit(Ty: PHI.getType());
1232 if (!VS)
1233 return false;
1234
1235 IRBuilder<> Builder(&PHI);
1236 ValueVector Res;
1237 Res.resize(N: VS->NumFragments);
1238
1239 unsigned NumOps = PHI.getNumOperands();
1240 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1241 Res[I] = Builder.CreatePHI(Ty: VS->getFragmentType(I), NumReservedValues: NumOps,
1242 Name: PHI.getName() + ".i" + Twine(I));
1243 }
1244
1245 for (unsigned I = 0; I < NumOps; ++I) {
1246 Scatterer Op = scatter(Point: &PHI, V: PHI.getIncomingValue(i: I), VS: *VS);
1247 BasicBlock *IncomingBlock = PHI.getIncomingBlock(i: I);
1248 for (unsigned J = 0; J < VS->NumFragments; ++J)
1249 cast<PHINode>(Val: Res[J])->addIncoming(V: Op[J], BB: IncomingBlock);
1250 }
1251 gather(Op: &PHI, CV: Res, VS: *VS);
1252 return true;
1253}
1254
1255bool ScalarizerVisitor::visitLoadInst(LoadInst &LI) {
1256 if (!ScalarizeLoadStore)
1257 return false;
1258 if (!LI.isSimple())
1259 return false;
1260
1261 std::optional<VectorLayout> Layout = getVectorLayout(
1262 Ty: LI.getType(), Alignment: LI.getAlign(), DL: LI.getDataLayout());
1263 if (!Layout)
1264 return false;
1265
1266 IRBuilder<> Builder(&LI);
1267 Scatterer Ptr = scatter(Point: &LI, V: LI.getPointerOperand(), VS: Layout->VS);
1268 ValueVector Res;
1269 Res.resize(N: Layout->VS.NumFragments);
1270
1271 for (unsigned I = 0; I < Layout->VS.NumFragments; ++I) {
1272 Res[I] = Builder.CreateAlignedLoad(Ty: Layout->VS.getFragmentType(I), Ptr: Ptr[I],
1273 Align: Align(Layout->getFragmentAlign(Frag: I)),
1274 Name: LI.getName() + ".i" + Twine(I));
1275 }
1276 gather(Op: &LI, CV: Res, VS: Layout->VS);
1277 return true;
1278}
1279
1280bool ScalarizerVisitor::visitStoreInst(StoreInst &SI) {
1281 if (!ScalarizeLoadStore)
1282 return false;
1283 if (!SI.isSimple())
1284 return false;
1285
1286 Value *FullValue = SI.getValueOperand();
1287 std::optional<VectorLayout> Layout = getVectorLayout(
1288 Ty: FullValue->getType(), Alignment: SI.getAlign(), DL: SI.getDataLayout());
1289 if (!Layout)
1290 return false;
1291
1292 IRBuilder<> Builder(&SI);
1293 Scatterer VPtr = scatter(Point: &SI, V: SI.getPointerOperand(), VS: Layout->VS);
1294 Scatterer VVal = scatter(Point: &SI, V: FullValue, VS: Layout->VS);
1295
1296 ValueVector Stores;
1297 Stores.resize(N: Layout->VS.NumFragments);
1298 for (unsigned I = 0; I < Layout->VS.NumFragments; ++I) {
1299 Value *Val = VVal[I];
1300 Value *Ptr = VPtr[I];
1301 Stores[I] =
1302 Builder.CreateAlignedStore(Val, Ptr, Align: Layout->getFragmentAlign(Frag: I));
1303 }
1304 transferMetadataAndIRFlags(Op: &SI, CV: Stores);
1305 return true;
1306}
1307
1308bool ScalarizerVisitor::visitCallInst(CallInst &CI) {
1309 return splitCall(CI);
1310}
1311
1312bool ScalarizerVisitor::visitFreezeInst(FreezeInst &FI) {
1313 return splitUnary(I&: FI, Split: [](IRBuilder<> &Builder, Value *Op, const Twine &Name) {
1314 return Builder.CreateFreeze(V: Op, Name);
1315 });
1316}
1317
1318// Delete the instructions that we scalarized. If a full vector result
1319// is still needed, recreate it using InsertElements.
1320bool ScalarizerVisitor::finish() {
1321 // The presence of data in Gathered or Scattered indicates changes
1322 // made to the Function.
1323 if (Gathered.empty() && Scattered.empty() && !Scalarized)
1324 return false;
1325 for (const auto &GMI : Gathered) {
1326 Instruction *Op = GMI.first;
1327 ValueVector &CV = *GMI.second;
1328 if (!Op->use_empty()) {
1329 // The value is still needed, so recreate it using a series of
1330 // insertelements and/or shufflevectors.
1331 Value *Res;
1332 if (auto *Ty = dyn_cast<FixedVectorType>(Val: Op->getType())) {
1333 BasicBlock *BB = Op->getParent();
1334 IRBuilder<> Builder(Op);
1335 if (isa<PHINode>(Val: Op))
1336 Builder.SetInsertPoint(BB->getFirstInsertionPt());
1337
1338 VectorSplit VS = *getVectorSplit(Ty);
1339 assert(VS.NumFragments == CV.size());
1340
1341 Res = concatenate(Builder, Fragments: CV, VS, Name: Op->getName());
1342
1343 Res->takeName(V: Op);
1344 } else if (auto *Ty = dyn_cast<StructType>(Val: Op->getType())) {
1345 BasicBlock *BB = Op->getParent();
1346 IRBuilder<> Builder(Op);
1347 if (isa<PHINode>(Val: Op))
1348 Builder.SetInsertPoint(BB->getFirstInsertionPt());
1349
1350 // Iterate over each element in the struct
1351 unsigned NumOfStructElements = Ty->getNumElements();
1352 SmallVector<ValueVector, 4> ElemCV(NumOfStructElements);
1353 for (unsigned I = 0; I < NumOfStructElements; ++I) {
1354 for (auto *CVelem : CV) {
1355 Value *Elem = Builder.CreateExtractValue(
1356 Agg: CVelem, Idxs: I, Name: Op->getName() + ".elem" + Twine(I));
1357 ElemCV[I].push_back(Elt: Elem);
1358 }
1359 }
1360 Res = PoisonValue::get(T: Ty);
1361 for (unsigned I = 0; I < NumOfStructElements; ++I) {
1362 Type *ElemTy = Ty->getElementType(N: I);
1363 assert(isa<FixedVectorType>(ElemTy) &&
1364 "Only Structs of all FixedVectorType supported");
1365 VectorSplit VS = *getVectorSplit(Ty: ElemTy);
1366 assert(VS.NumFragments == CV.size());
1367
1368 Value *ConcatenatedVector =
1369 concatenate(Builder, Fragments: ElemCV[I], VS, Name: Op->getName());
1370 Res = Builder.CreateInsertValue(Agg: Res, Val: ConcatenatedVector, Idxs: I,
1371 Name: Op->getName() + ".insert");
1372 }
1373 } else {
1374 assert(CV.size() == 1 && Op->getType() == CV[0]->getType());
1375 Res = CV[0];
1376 if (Op == Res)
1377 continue;
1378 }
1379 Op->replaceAllUsesWith(V: Res);
1380 }
1381 PotentiallyDeadInstrs.emplace_back(Args&: Op);
1382 }
1383 Gathered.clear();
1384 Scattered.clear();
1385 Scalarized = false;
1386
1387 RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts&: PotentiallyDeadInstrs);
1388
1389 return true;
1390}
1391
1392PreservedAnalyses ScalarizerPass::run(Function &F, FunctionAnalysisManager &AM) {
1393 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F);
1394 const TargetTransformInfo *TTI = &AM.getResult<TargetIRAnalysis>(IR&: F);
1395 ScalarizerVisitor Impl(DT, TTI, Options);
1396 bool Changed = Impl.visit(F);
1397 PreservedAnalyses PA;
1398 PA.preserve<DominatorTreeAnalysis>();
1399 return Changed ? PA : PreservedAnalyses::all();
1400}
1401