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 if (IsPointer) {
391 if (Frag == 0)
392 CV[Frag] = V;
393 else
394 CV[Frag] = Builder.CreateConstGEP1_32(Ty: VS.SplitTy, Ptr: V, Idx0: Frag,
395 Name: V->getName() + ".i" + Twine(Frag));
396 return CV[Frag];
397 }
398
399 Type *FragmentTy = VS.getFragmentType(I: Frag);
400
401 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: FragmentTy)) {
402 SmallVector<int> Mask;
403 for (unsigned J = 0; J < VecTy->getNumElements(); ++J)
404 Mask.push_back(Elt: Frag * VS.NumPacked + J);
405 CV[Frag] =
406 Builder.CreateShuffleVector(V1: V, V2: PoisonValue::get(T: V->getType()), Mask,
407 Name: V->getName() + ".i" + Twine(Frag));
408 } else {
409 // Search through a chain of InsertElementInsts looking for element Frag.
410 // Record other elements in the cache. The new V is still suitable
411 // for all uncached indices.
412 while (true) {
413 InsertElementInst *Insert = dyn_cast<InsertElementInst>(Val: V);
414 if (!Insert)
415 break;
416 ConstantInt *Idx = dyn_cast<ConstantInt>(Val: Insert->getOperand(i_nocapture: 2));
417 if (!Idx)
418 break;
419 unsigned J = Idx->getZExtValue();
420 V = Insert->getOperand(i_nocapture: 0);
421 if (Frag * VS.NumPacked == J) {
422 CV[Frag] = Insert->getOperand(i_nocapture: 1);
423 return CV[Frag];
424 }
425
426 if (VS.NumPacked == 1 && !CV[J]) {
427 // Only cache the first entry we find for each index we're not actively
428 // searching for. This prevents us from going too far up the chain and
429 // caching incorrect entries.
430 CV[J] = Insert->getOperand(i_nocapture: 1);
431 }
432 }
433 CV[Frag] = Builder.CreateExtractElement(Vec: V, Idx: Frag * VS.NumPacked,
434 Name: V->getName() + ".i" + Twine(Frag));
435 }
436
437 return CV[Frag];
438}
439
440bool ScalarizerLegacyPass::runOnFunction(Function &F) {
441 if (skipFunction(F))
442 return false;
443
444 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
445 const TargetTransformInfo *TTI =
446 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
447 ScalarizerVisitor Impl(DT, TTI, Options);
448 return Impl.visit(F);
449}
450
451FunctionPass *llvm::createScalarizerPass(const ScalarizerPassOptions &Options) {
452 return new ScalarizerLegacyPass(Options);
453}
454
455bool ScalarizerVisitor::visit(Function &F) {
456 assert(Gathered.empty() && Scattered.empty());
457
458 Scalarized = false;
459
460 // To ensure we replace gathered components correctly we need to do an ordered
461 // traversal of the basic blocks in the function.
462 ReversePostOrderTraversal<BasicBlock *> RPOT(&F.getEntryBlock());
463 for (BasicBlock *BB : RPOT) {
464 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
465 Instruction *I = &*II;
466 bool Done = InstVisitor::visit(I);
467 ++II;
468 if (Done && I->getType()->isVoidTy()) {
469 I->eraseFromParent();
470 Scalarized = true;
471 }
472 }
473 }
474 return finish();
475}
476
477// Return a scattered form of V that can be accessed by Point. V must be a
478// vector or a pointer to a vector.
479Scatterer ScalarizerVisitor::scatter(Instruction *Point, Value *V,
480 const VectorSplit &VS) {
481 if (Argument *VArg = dyn_cast<Argument>(Val: V)) {
482 // Put the scattered form of arguments in the entry block,
483 // so that it can be used everywhere.
484 Function *F = VArg->getParent();
485 BasicBlock *BB = &F->getEntryBlock();
486 return Scatterer(BB->begin(), V, VS, &Scattered[{V, VS.SplitTy}]);
487 }
488 if (Instruction *VOp = dyn_cast<Instruction>(Val: V)) {
489 // When scalarizing PHI nodes we might try to examine/rewrite InsertElement
490 // nodes in predecessors. If those predecessors are unreachable from entry,
491 // then the IR in those blocks could have unexpected properties resulting in
492 // infinite loops in Scatterer::operator[]. By simply treating values
493 // originating from instructions in unreachable blocks as undef we do not
494 // need to analyse them further.
495 if (!DT->isReachableFromEntry(A: VOp->getParent()))
496 return Scatterer(Point->getIterator(), PoisonValue::get(T: V->getType()),
497 VS);
498 // Put the scattered form of an instruction directly after the
499 // instruction, skipping over PHI nodes.
500 return Scatterer(skipPastPhiNodes(Itr: std::next(x: BasicBlock::iterator(VOp))), V,
501 VS, &Scattered[{V, VS.SplitTy}]);
502 }
503 // In the fallback case, just put the scattered before Point and
504 // keep the result local to Point.
505 return Scatterer(Point->getIterator(), V, VS);
506}
507
508// Replace Op with the gathered form of the components in CV. Defer the
509// deletion of Op and creation of the gathered form to the end of the pass,
510// so that we can avoid creating the gathered form if all uses of Op are
511// replaced with uses of CV.
512void ScalarizerVisitor::gather(Instruction *Op, const ValueVector &CV,
513 const VectorSplit &VS) {
514 transferMetadataAndIRFlags(Op, CV);
515
516 // If we already have a scattered form of Op (created from ExtractElements
517 // of Op itself), replace them with the new form.
518 ValueVector &SV = Scattered[{Op, VS.SplitTy}];
519 if (!SV.empty()) {
520 for (unsigned I = 0, E = SV.size(); I != E; ++I) {
521 Value *V = SV[I];
522 if (V == nullptr || SV[I] == CV[I])
523 continue;
524
525 Instruction *Old = cast<Instruction>(Val: V);
526 if (isa<Instruction>(Val: CV[I]))
527 CV[I]->takeName(V: Old);
528 Old->replaceAllUsesWith(V: CV[I]);
529 PotentiallyDeadInstrs.emplace_back(Args&: Old);
530 }
531 }
532 SV = CV;
533 Gathered.push_back(Elt: GatherList::value_type(Op, &SV));
534}
535
536// Replace Op with CV and collect Op has a potentially dead instruction.
537void ScalarizerVisitor::replaceUses(Instruction *Op, Value *CV) {
538 if (CV != Op) {
539 Op->replaceAllUsesWith(V: CV);
540 PotentiallyDeadInstrs.emplace_back(Args&: Op);
541 Scalarized = true;
542 }
543}
544
545// Return true if it is safe to transfer the given metadata tag from
546// vector to scalar instructions.
547bool ScalarizerVisitor::canTransferMetadata(unsigned Tag) {
548 return (Tag == LLVMContext::MD_tbaa
549 || Tag == LLVMContext::MD_fpmath
550 || Tag == LLVMContext::MD_tbaa_struct
551 || Tag == LLVMContext::MD_invariant_load
552 || Tag == LLVMContext::MD_alias_scope
553 || Tag == LLVMContext::MD_noalias
554 || Tag == LLVMContext::MD_mem_parallel_loop_access
555 || Tag == LLVMContext::MD_access_group);
556}
557
558// Transfer metadata from Op to the instructions in CV if it is known
559// to be safe to do so.
560void ScalarizerVisitor::transferMetadataAndIRFlags(Instruction *Op,
561 const ValueVector &CV) {
562 SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
563 Op->getAllMetadataOtherThanDebugLoc(MDs);
564 for (Value *V : CV) {
565 if (Instruction *New = dyn_cast<Instruction>(Val: V)) {
566 for (const auto &MD : MDs)
567 if (canTransferMetadata(Tag: MD.first))
568 New->setMetadata(KindID: MD.first, Node: MD.second);
569 New->copyIRFlags(V: Op);
570 if (Op->getDebugLoc() && !New->getDebugLoc())
571 New->setDebugLoc(Op->getDebugLoc());
572 }
573 }
574}
575
576// Determine how Ty is split, if at all.
577std::optional<VectorSplit> ScalarizerVisitor::getVectorSplit(Type *Ty) {
578 VectorSplit Split;
579 Split.VecTy = dyn_cast<FixedVectorType>(Val: Ty);
580 if (!Split.VecTy)
581 return {};
582
583 unsigned NumElems = Split.VecTy->getNumElements();
584 Type *ElemTy = Split.VecTy->getElementType();
585
586 if (NumElems == 1 || ElemTy->isPointerTy() ||
587 2 * ElemTy->getScalarSizeInBits() > ScalarizeMinBits) {
588 Split.NumPacked = 1;
589 Split.NumFragments = NumElems;
590 Split.SplitTy = ElemTy;
591 } else {
592 Split.NumPacked = ScalarizeMinBits / ElemTy->getScalarSizeInBits();
593 if (Split.NumPacked >= NumElems)
594 return {};
595
596 Split.NumFragments = divideCeil(Numerator: NumElems, Denominator: Split.NumPacked);
597 Split.SplitTy = FixedVectorType::get(ElementType: ElemTy, NumElts: Split.NumPacked);
598
599 unsigned RemainderElems = NumElems % Split.NumPacked;
600 if (RemainderElems > 1)
601 Split.RemainderTy = FixedVectorType::get(ElementType: ElemTy, NumElts: RemainderElems);
602 else if (RemainderElems == 1)
603 Split.RemainderTy = ElemTy;
604 }
605
606 return Split;
607}
608
609// Try to fill in Layout from Ty, returning true on success. Alignment is
610// the alignment of the vector, or std::nullopt if the ABI default should be
611// used.
612std::optional<VectorLayout>
613ScalarizerVisitor::getVectorLayout(Type *Ty, Align Alignment,
614 const DataLayout &DL) {
615 std::optional<VectorSplit> VS = getVectorSplit(Ty);
616 if (!VS)
617 return {};
618
619 VectorLayout Layout;
620 Layout.VS = *VS;
621 // Check that we're dealing with full-byte fragments.
622 if (!DL.typeSizeEqualsStoreSize(Ty: VS->SplitTy) ||
623 (VS->RemainderTy && !DL.typeSizeEqualsStoreSize(Ty: VS->RemainderTy)))
624 return {};
625 Layout.VecAlign = Alignment;
626 Layout.SplitSize = DL.getTypeStoreSize(Ty: VS->SplitTy);
627 return Layout;
628}
629
630// Scalarize one-operand instruction I, using Split(Builder, X, Name)
631// to create an instruction like I with operand X and name Name.
632template<typename Splitter>
633bool ScalarizerVisitor::splitUnary(Instruction &I, const Splitter &Split) {
634 std::optional<VectorSplit> VS = getVectorSplit(Ty: I.getType());
635 if (!VS)
636 return false;
637
638 std::optional<VectorSplit> OpVS;
639 if (I.getOperand(i: 0)->getType() == I.getType()) {
640 OpVS = VS;
641 } else {
642 OpVS = getVectorSplit(Ty: I.getOperand(i: 0)->getType());
643 if (!OpVS || VS->NumPacked != OpVS->NumPacked)
644 return false;
645 }
646
647 IRBuilder<> Builder(&I);
648 Scatterer Op = scatter(Point: &I, V: I.getOperand(i: 0), VS: *OpVS);
649 assert(Op.size() == VS->NumFragments && "Mismatched unary operation");
650 ValueVector Res;
651 Res.resize(N: VS->NumFragments);
652 for (unsigned Frag = 0; Frag < VS->NumFragments; ++Frag)
653 Res[Frag] = Split(Builder, Op[Frag], I.getName() + ".i" + Twine(Frag));
654 gather(Op: &I, CV: Res, VS: *VS);
655 return true;
656}
657
658// Scalarize two-operand instruction I, using Split(Builder, X, Y, Name)
659// to create an instruction like I with operands X and Y and name Name.
660template<typename Splitter>
661bool ScalarizerVisitor::splitBinary(Instruction &I, const Splitter &Split) {
662 std::optional<VectorSplit> VS = getVectorSplit(Ty: I.getType());
663 if (!VS)
664 return false;
665
666 std::optional<VectorSplit> OpVS;
667 if (I.getOperand(i: 0)->getType() == I.getType()) {
668 OpVS = VS;
669 } else {
670 OpVS = getVectorSplit(Ty: I.getOperand(i: 0)->getType());
671 if (!OpVS || VS->NumPacked != OpVS->NumPacked)
672 return false;
673 }
674
675 IRBuilder<> Builder(&I);
676 Scatterer VOp0 = scatter(Point: &I, V: I.getOperand(i: 0), VS: *OpVS);
677 Scatterer VOp1 = scatter(Point: &I, V: I.getOperand(i: 1), VS: *OpVS);
678 assert(VOp0.size() == VS->NumFragments && "Mismatched binary operation");
679 assert(VOp1.size() == VS->NumFragments && "Mismatched binary operation");
680 ValueVector Res;
681 Res.resize(N: VS->NumFragments);
682 for (unsigned Frag = 0; Frag < VS->NumFragments; ++Frag) {
683 Value *Op0 = VOp0[Frag];
684 Value *Op1 = VOp1[Frag];
685 Res[Frag] = Split(Builder, Op0, Op1, I.getName() + ".i" + Twine(Frag));
686 }
687 gather(Op: &I, CV: Res, VS: *VS);
688 return true;
689}
690
691/// If a call to a vector typed intrinsic function, split into a scalar call per
692/// element if possible for the intrinsic.
693bool ScalarizerVisitor::splitCall(CallInst &CI) {
694 Type *CallType = CI.getType();
695 bool AreAllVectorsOfMatchingSize = isStructOfMatchingFixedVectors(Ty: CallType);
696 std::optional<VectorSplit> VS;
697 if (AreAllVectorsOfMatchingSize)
698 VS = getVectorSplit(Ty: CallType->getContainedType(i: 0));
699 else
700 VS = getVectorSplit(Ty: CallType);
701 if (!VS)
702 return false;
703
704 Function *F = CI.getCalledFunction();
705 if (!F)
706 return false;
707
708 Intrinsic::ID ID = F->getIntrinsicID();
709
710 if (ID == Intrinsic::not_intrinsic || !isTriviallyScalarizable(ID))
711 return false;
712
713 // unsigned NumElems = VT->getNumElements();
714 unsigned NumArgs = CI.arg_size();
715
716 ValueVector ScalarOperands(NumArgs);
717 SmallVector<Scatterer, 8> Scattered(NumArgs);
718 SmallVector<int> OverloadIdx(NumArgs, -1);
719
720 SmallVector<llvm::Type *, 3> Tys;
721 // Add return type if intrinsic is overloaded on it.
722 if (isVectorIntrinsicWithOverloadTypeAtArg(ID, OpdIdx: -1, TTI))
723 Tys.push_back(Elt: VS->SplitTy);
724
725 if (AreAllVectorsOfMatchingSize) {
726 for (unsigned I = 1; I < CallType->getNumContainedTypes(); I++) {
727 std::optional<VectorSplit> CurrVS =
728 getVectorSplit(Ty: cast<FixedVectorType>(Val: CallType->getContainedType(i: I)));
729 // It is possible for VectorSplit.NumPacked >= NumElems. If that happens a
730 // VectorSplit is not returned and we will bailout of handling this call.
731 // The secondary bailout case is if NumPacked does not match. This can
732 // happen if ScalarizeMinBits is not set to the default. This means with
733 // certain ScalarizeMinBits intrinsics like frexp will only scalarize when
734 // the struct elements have the same bitness.
735 if (!CurrVS || CurrVS->NumPacked != VS->NumPacked)
736 return false;
737 if (isVectorIntrinsicWithStructReturnOverloadAtField(ID, RetIdx: I, TTI))
738 Tys.push_back(Elt: CurrVS->SplitTy);
739 }
740 }
741 // Assumes that any vector type has the same number of elements as the return
742 // vector type, which is true for all current intrinsics.
743 for (unsigned I = 0; I != NumArgs; ++I) {
744 Value *OpI = CI.getOperand(i_nocapture: I);
745 if ([[maybe_unused]] auto *OpVecTy =
746 dyn_cast<FixedVectorType>(Val: OpI->getType())) {
747 assert(OpVecTy->getNumElements() == VS->VecTy->getNumElements());
748 std::optional<VectorSplit> OpVS = getVectorSplit(Ty: OpI->getType());
749 if (!OpVS || OpVS->NumPacked != VS->NumPacked) {
750 // The natural split of the operand doesn't match the result. This could
751 // happen if the vector elements are different and the ScalarizeMinBits
752 // option is used.
753 //
754 // We could in principle handle this case as well, at the cost of
755 // complicating the scattering machinery to support multiple scattering
756 // granularities for a single value.
757 return false;
758 }
759
760 Scattered[I] = scatter(Point: &CI, V: OpI, VS: *OpVS);
761 if (isVectorIntrinsicWithOverloadTypeAtArg(ID, OpdIdx: I, TTI)) {
762 OverloadIdx[I] = Tys.size();
763 Tys.push_back(Elt: OpVS->SplitTy);
764 }
765 } else {
766 ScalarOperands[I] = OpI;
767 if (isVectorIntrinsicWithOverloadTypeAtArg(ID, OpdIdx: I, TTI))
768 Tys.push_back(Elt: OpI->getType());
769 }
770 }
771
772 ValueVector Res(VS->NumFragments);
773 ValueVector ScalarCallOps(NumArgs);
774
775 Function *NewIntrin =
776 Intrinsic::getOrInsertDeclaration(M: F->getParent(), id: ID, OverloadTys: Tys);
777 IRBuilder<> Builder(&CI);
778
779 // Perform actual scalarization, taking care to preserve any scalar operands.
780 for (unsigned I = 0; I < VS->NumFragments; ++I) {
781 bool IsRemainder = I == VS->NumFragments - 1 && VS->RemainderTy;
782 ScalarCallOps.clear();
783
784 if (IsRemainder)
785 Tys[0] = VS->RemainderTy;
786
787 for (unsigned J = 0; J != NumArgs; ++J) {
788 if (isVectorIntrinsicWithScalarOpAtArg(ID, ScalarOpdIdx: J, TTI)) {
789 ScalarCallOps.push_back(Elt: ScalarOperands[J]);
790 } else {
791 ScalarCallOps.push_back(Elt: Scattered[J][I]);
792 if (IsRemainder && OverloadIdx[J] >= 0)
793 Tys[OverloadIdx[J]] = Scattered[J][I]->getType();
794 }
795 }
796
797 if (IsRemainder)
798 NewIntrin = Intrinsic::getOrInsertDeclaration(M: F->getParent(), id: ID, OverloadTys: Tys);
799
800 Res[I] = Builder.CreateCall(Callee: NewIntrin, Args: ScalarCallOps,
801 Name: CI.getName() + ".i" + Twine(I));
802 }
803
804 gather(Op: &CI, CV: Res, VS: *VS);
805 return true;
806}
807
808bool ScalarizerVisitor::visitSelectInst(SelectInst &SI) {
809 std::optional<VectorSplit> VS = getVectorSplit(Ty: SI.getType());
810 if (!VS)
811 return false;
812
813 std::optional<VectorSplit> CondVS;
814 if (isa<FixedVectorType>(Val: SI.getCondition()->getType())) {
815 CondVS = getVectorSplit(Ty: SI.getCondition()->getType());
816 if (!CondVS || CondVS->NumPacked != VS->NumPacked) {
817 // This happens when ScalarizeMinBits is used.
818 return false;
819 }
820 }
821
822 IRBuilder<> Builder(&SI);
823 Scatterer VOp1 = scatter(Point: &SI, V: SI.getOperand(i_nocapture: 1), VS: *VS);
824 Scatterer VOp2 = scatter(Point: &SI, V: SI.getOperand(i_nocapture: 2), VS: *VS);
825 assert(VOp1.size() == VS->NumFragments && "Mismatched select");
826 assert(VOp2.size() == VS->NumFragments && "Mismatched select");
827 ValueVector Res;
828 Res.resize(N: VS->NumFragments);
829
830 if (CondVS) {
831 Scatterer VOp0 = scatter(Point: &SI, V: SI.getOperand(i_nocapture: 0), VS: *CondVS);
832 assert(VOp0.size() == CondVS->NumFragments && "Mismatched select");
833 for (unsigned I = 0; I < VS->NumFragments; ++I) {
834 Value *Op0 = VOp0[I];
835 Value *Op1 = VOp1[I];
836 Value *Op2 = VOp2[I];
837 Res[I] = Builder.CreateSelect(C: Op0, True: Op1, False: Op2,
838 Name: SI.getName() + ".i" + Twine(I));
839 }
840 } else {
841 Value *Op0 = SI.getOperand(i_nocapture: 0);
842 for (unsigned I = 0; I < VS->NumFragments; ++I) {
843 Value *Op1 = VOp1[I];
844 Value *Op2 = VOp2[I];
845 Res[I] = Builder.CreateSelect(C: Op0, True: Op1, False: Op2,
846 Name: SI.getName() + ".i" + Twine(I));
847 }
848 }
849 gather(Op: &SI, CV: Res, VS: *VS);
850 return true;
851}
852
853bool ScalarizerVisitor::visitICmpInst(ICmpInst &ICI) {
854 return splitBinary(I&: ICI, Split: ICmpSplitter(ICI));
855}
856
857bool ScalarizerVisitor::visitFCmpInst(FCmpInst &FCI) {
858 return splitBinary(I&: FCI, Split: FCmpSplitter(FCI));
859}
860
861bool ScalarizerVisitor::visitUnaryOperator(UnaryOperator &UO) {
862 return splitUnary(I&: UO, Split: UnarySplitter(UO));
863}
864
865bool ScalarizerVisitor::visitBinaryOperator(BinaryOperator &BO) {
866 return splitBinary(I&: BO, Split: BinarySplitter(BO));
867}
868
869bool ScalarizerVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) {
870 std::optional<VectorSplit> VS = getVectorSplit(Ty: GEPI.getType());
871 if (!VS)
872 return false;
873
874 IRBuilder<> Builder(&GEPI);
875 unsigned NumIndices = GEPI.getNumIndices();
876
877 // The base pointer and indices might be scalar even if it's a vector GEP.
878 SmallVector<Value *, 8> ScalarOps{1 + NumIndices};
879 SmallVector<Scatterer, 8> ScatterOps{1 + NumIndices};
880
881 for (unsigned I = 0; I < 1 + NumIndices; ++I) {
882 if (auto *VecTy =
883 dyn_cast<FixedVectorType>(Val: GEPI.getOperand(i_nocapture: I)->getType())) {
884 std::optional<VectorSplit> OpVS = getVectorSplit(Ty: VecTy);
885 if (!OpVS || OpVS->NumPacked != VS->NumPacked) {
886 // This can happen when ScalarizeMinBits is used.
887 return false;
888 }
889 ScatterOps[I] = scatter(Point: &GEPI, V: GEPI.getOperand(i_nocapture: I), VS: *OpVS);
890 } else {
891 ScalarOps[I] = GEPI.getOperand(i_nocapture: I);
892 }
893 }
894
895 ValueVector Res;
896 Res.resize(N: VS->NumFragments);
897 for (unsigned I = 0; I < VS->NumFragments; ++I) {
898 SmallVector<Value *, 8> SplitOps;
899 SplitOps.resize(N: 1 + NumIndices);
900 for (unsigned J = 0; J < 1 + NumIndices; ++J) {
901 if (ScalarOps[J])
902 SplitOps[J] = ScalarOps[J];
903 else
904 SplitOps[J] = ScatterOps[J][I];
905 }
906 Res[I] = Builder.CreateGEP(Ty: GEPI.getSourceElementType(), Ptr: SplitOps[0],
907 IdxList: ArrayRef(SplitOps).drop_front(),
908 Name: GEPI.getName() + ".i" + Twine(I));
909 if (GEPI.isInBounds())
910 if (GetElementPtrInst *NewGEPI = dyn_cast<GetElementPtrInst>(Val: Res[I]))
911 NewGEPI->setIsInBounds();
912 }
913 gather(Op: &GEPI, CV: Res, VS: *VS);
914 return true;
915}
916
917bool ScalarizerVisitor::visitCastInst(CastInst &CI) {
918 std::optional<VectorSplit> DestVS = getVectorSplit(Ty: CI.getDestTy());
919 if (!DestVS)
920 return false;
921
922 std::optional<VectorSplit> SrcVS = getVectorSplit(Ty: CI.getSrcTy());
923 if (!SrcVS || SrcVS->NumPacked != DestVS->NumPacked)
924 return false;
925
926 IRBuilder<> Builder(&CI);
927 Scatterer Op0 = scatter(Point: &CI, V: CI.getOperand(i_nocapture: 0), VS: *SrcVS);
928 assert(Op0.size() == SrcVS->NumFragments && "Mismatched cast");
929 ValueVector Res;
930 Res.resize(N: DestVS->NumFragments);
931 for (unsigned I = 0; I < DestVS->NumFragments; ++I)
932 Res[I] =
933 Builder.CreateCast(Op: CI.getOpcode(), V: Op0[I], DestTy: DestVS->getFragmentType(I),
934 Name: CI.getName() + ".i" + Twine(I));
935 gather(Op: &CI, CV: Res, VS: *DestVS);
936 return true;
937}
938
939bool ScalarizerVisitor::visitBitCastInst(BitCastInst &BCI) {
940 std::optional<VectorSplit> DstVS = getVectorSplit(Ty: BCI.getDestTy());
941 std::optional<VectorSplit> SrcVS = getVectorSplit(Ty: BCI.getSrcTy());
942
943 if (DstVS && !SrcVS && BCI.getSrcTy()->isIntegerTy() && !DstVS->RemainderTy &&
944 DstVS->NumPacked == 1 && DstVS->SplitTy->isIntegerTy()) {
945 IRBuilder<> Builder(&BCI);
946 Builder.SetCurrentDebugLocation(BCI.getDebugLoc());
947 ValueVector Res(DstVS->NumFragments);
948 unsigned FragmentBits = DstVS->SplitTy->getPrimitiveSizeInBits();
949 bool IsBigEndian = BCI.getDataLayout().isBigEndian();
950 for (unsigned I = 0; I < DstVS->NumFragments; ++I) {
951 unsigned FragmentIndex = IsBigEndian ? DstVS->NumFragments - I - 1 : I;
952 Value *Fragment = BCI.getOperand(i_nocapture: 0);
953 if (FragmentIndex)
954 Fragment = Builder.CreateLShr(LHS: Fragment, RHS: FragmentIndex * FragmentBits);
955 Res[I] = Builder.CreateTruncOrBitCast(V: Fragment, DestTy: DstVS->getFragmentType(I),
956 Name: BCI.getName() + ".i" + Twine(I));
957 }
958 gather(Op: &BCI, CV: Res, VS: *DstVS);
959 return true;
960 }
961
962 if (!DstVS && SrcVS && BCI.getDestTy()->isIntegerTy() &&
963 !SrcVS->RemainderTy && SrcVS->NumPacked == 1 &&
964 SrcVS->SplitTy->isIntegerTy()) {
965 IRBuilder<> Builder(&BCI);
966 Builder.SetCurrentDebugLocation(BCI.getDebugLoc());
967 Scatterer Op0 = scatter(Point: &BCI, V: BCI.getOperand(i_nocapture: 0), VS: *SrcVS);
968 Value *Result = nullptr;
969 unsigned FragmentBits = SrcVS->SplitTy->getPrimitiveSizeInBits();
970 bool IsBigEndian = BCI.getDataLayout().isBigEndian();
971 for (unsigned I = 0; I < SrcVS->NumFragments; ++I) {
972 unsigned FragmentIndex = IsBigEndian ? SrcVS->NumFragments - I - 1 : I;
973 Value *Fragment = Builder.CreateZExtOrTrunc(V: Op0[I], DestTy: BCI.getDestTy());
974 if (FragmentIndex)
975 Fragment = Builder.CreateShl(LHS: Fragment, RHS: FragmentIndex * FragmentBits);
976 Result = Result ? Builder.CreateOr(LHS: Result, RHS: Fragment) : Fragment;
977 }
978 replaceUses(Op: &BCI, CV: Result);
979 return true;
980 }
981
982 if (!DstVS || !SrcVS || DstVS->RemainderTy || SrcVS->RemainderTy)
983 return false;
984
985 const bool isPointerTy = DstVS->VecTy->getElementType()->isPointerTy();
986
987 // Vectors of pointers are always fully scalarized.
988 assert(!isPointerTy || (DstVS->NumPacked == 1 && SrcVS->NumPacked == 1));
989
990 IRBuilder<> Builder(&BCI);
991 Scatterer Op0 = scatter(Point: &BCI, V: BCI.getOperand(i_nocapture: 0), VS: *SrcVS);
992 ValueVector Res;
993 Res.resize(N: DstVS->NumFragments);
994
995 unsigned DstSplitBits = DstVS->SplitTy->getPrimitiveSizeInBits();
996 unsigned SrcSplitBits = SrcVS->SplitTy->getPrimitiveSizeInBits();
997
998 if (isPointerTy || DstSplitBits == SrcSplitBits) {
999 assert(DstVS->NumFragments == SrcVS->NumFragments);
1000 for (unsigned I = 0; I < DstVS->NumFragments; ++I) {
1001 Res[I] = Builder.CreateBitCast(V: Op0[I], DestTy: DstVS->getFragmentType(I),
1002 Name: BCI.getName() + ".i" + Twine(I));
1003 }
1004 } else if (SrcSplitBits % DstSplitBits == 0) {
1005 // Convert each source fragment to the same-sized destination vector and
1006 // then scatter the result to the destination.
1007 VectorSplit MidVS;
1008 MidVS.NumPacked = DstVS->NumPacked;
1009 MidVS.NumFragments = SrcSplitBits / DstSplitBits;
1010 MidVS.VecTy = FixedVectorType::get(ElementType: DstVS->VecTy->getElementType(),
1011 NumElts: MidVS.NumPacked * MidVS.NumFragments);
1012 MidVS.SplitTy = DstVS->SplitTy;
1013
1014 unsigned ResI = 0;
1015 for (unsigned I = 0; I < SrcVS->NumFragments; ++I) {
1016 Value *V = Op0[I];
1017
1018 // Look through any existing bitcasts before converting to <N x t2>.
1019 // In the best case, the resulting conversion might be a no-op.
1020 Instruction *VI;
1021 while ((VI = dyn_cast<Instruction>(Val: V)) &&
1022 VI->getOpcode() == Instruction::BitCast)
1023 V = VI->getOperand(i: 0);
1024
1025 V = Builder.CreateBitCast(V, DestTy: MidVS.VecTy, Name: V->getName() + ".cast");
1026
1027 Scatterer Mid = scatter(Point: &BCI, V, VS: MidVS);
1028 for (unsigned J = 0; J < MidVS.NumFragments; ++J)
1029 Res[ResI++] = Mid[J];
1030 }
1031 } else if (DstSplitBits % SrcSplitBits == 0) {
1032 // Gather enough source fragments to make up a destination fragment and
1033 // then convert to the destination type.
1034 VectorSplit MidVS;
1035 MidVS.NumFragments = DstSplitBits / SrcSplitBits;
1036 MidVS.NumPacked = SrcVS->NumPacked;
1037 MidVS.VecTy = FixedVectorType::get(ElementType: SrcVS->VecTy->getElementType(),
1038 NumElts: MidVS.NumPacked * MidVS.NumFragments);
1039 MidVS.SplitTy = SrcVS->SplitTy;
1040
1041 unsigned SrcI = 0;
1042 SmallVector<Value *, 8> ConcatOps;
1043 ConcatOps.resize(N: MidVS.NumFragments);
1044 for (unsigned I = 0; I < DstVS->NumFragments; ++I) {
1045 for (unsigned J = 0; J < MidVS.NumFragments; ++J)
1046 ConcatOps[J] = Op0[SrcI++];
1047 Value *V = concatenate(Builder, Fragments: ConcatOps, VS: MidVS,
1048 Name: BCI.getName() + ".i" + Twine(I));
1049 Res[I] = Builder.CreateBitCast(V, DestTy: DstVS->getFragmentType(I),
1050 Name: BCI.getName() + ".i" + Twine(I));
1051 }
1052 } else {
1053 return false;
1054 }
1055
1056 gather(Op: &BCI, CV: Res, VS: *DstVS);
1057 return true;
1058}
1059
1060bool ScalarizerVisitor::visitInsertElementInst(InsertElementInst &IEI) {
1061 std::optional<VectorSplit> VS = getVectorSplit(Ty: IEI.getType());
1062 if (!VS)
1063 return false;
1064
1065 IRBuilder<> Builder(&IEI);
1066 Scatterer Op0 = scatter(Point: &IEI, V: IEI.getOperand(i_nocapture: 0), VS: *VS);
1067 Value *NewElt = IEI.getOperand(i_nocapture: 1);
1068 Value *InsIdx = IEI.getOperand(i_nocapture: 2);
1069
1070 ValueVector Res;
1071 Res.resize(N: VS->NumFragments);
1072
1073 if (auto *CI = dyn_cast<ConstantInt>(Val: InsIdx)) {
1074 unsigned Idx = CI->getZExtValue();
1075 unsigned Fragment = Idx / VS->NumPacked;
1076 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1077 if (I == Fragment) {
1078 bool IsPacked = VS->NumPacked > 1;
1079 if (Fragment == VS->NumFragments - 1 && VS->RemainderTy &&
1080 !VS->RemainderTy->isVectorTy())
1081 IsPacked = false;
1082 if (IsPacked) {
1083 Res[I] =
1084 Builder.CreateInsertElement(Vec: Op0[I], NewElt, Idx: Idx % VS->NumPacked);
1085 } else {
1086 Res[I] = NewElt;
1087 }
1088 } else {
1089 Res[I] = Op0[I];
1090 }
1091 }
1092 } else {
1093 // Never split a variable insertelement that isn't fully scalarized.
1094 if (!ScalarizeVariableInsertExtract || VS->NumPacked > 1)
1095 return false;
1096
1097 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1098 Value *ShouldReplace =
1099 Builder.CreateICmpEQ(LHS: InsIdx, RHS: ConstantInt::get(Ty: InsIdx->getType(), V: I),
1100 Name: InsIdx->getName() + ".is." + Twine(I));
1101 Value *OldElt = Op0[I];
1102 Res[I] = Builder.CreateSelect(C: ShouldReplace, True: NewElt, False: OldElt,
1103 Name: IEI.getName() + ".i" + Twine(I));
1104 }
1105 }
1106
1107 gather(Op: &IEI, CV: Res, VS: *VS);
1108 return true;
1109}
1110
1111bool ScalarizerVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
1112 Value *Op = EVI.getOperand(i_nocapture: 0);
1113 Type *OpTy = Op->getType();
1114 ValueVector Res;
1115 if (!isStructOfMatchingFixedVectors(Ty: OpTy))
1116 return false;
1117 if (CallInst *CI = dyn_cast<CallInst>(Val: Op)) {
1118 Function *F = CI->getCalledFunction();
1119 if (!F)
1120 return false;
1121 Intrinsic::ID ID = F->getIntrinsicID();
1122 if (ID == Intrinsic::not_intrinsic || !isTriviallyScalarizable(ID))
1123 return false;
1124 // Note: Fall through means Operand is a`CallInst` and it is defined in
1125 // `isTriviallyScalarizable`.
1126 } else
1127 return false;
1128 Type *VecType = cast<FixedVectorType>(Val: OpTy->getContainedType(i: 0));
1129 std::optional<VectorSplit> VS = getVectorSplit(Ty: VecType);
1130 if (!VS)
1131 return false;
1132 for (unsigned I = 1; I < OpTy->getNumContainedTypes(); I++) {
1133 std::optional<VectorSplit> CurrVS =
1134 getVectorSplit(Ty: cast<FixedVectorType>(Val: OpTy->getContainedType(i: I)));
1135 // It is possible for VectorSplit.NumPacked >= NumElems. If that happens a
1136 // VectorSplit is not returned and we will bailout of handling this call.
1137 // The secondary bailout case is if NumPacked does not match. This can
1138 // happen if ScalarizeMinBits is not set to the default. This means with
1139 // certain ScalarizeMinBits intrinsics like frexp will only scalarize when
1140 // the struct elements have the same bitness.
1141 if (!CurrVS || CurrVS->NumPacked != VS->NumPacked)
1142 return false;
1143 }
1144 IRBuilder<> Builder(&EVI);
1145 Scatterer Op0 = scatter(Point: &EVI, V: Op, VS: *VS);
1146 assert(!EVI.getIndices().empty() && "Make sure an index exists");
1147 // Note for our use case we only care about the top level index.
1148 unsigned Index = EVI.getIndices()[0];
1149 for (unsigned OpIdx = 0; OpIdx < Op0.size(); ++OpIdx) {
1150 Value *ResElem = Builder.CreateExtractValue(
1151 Agg: Op0[OpIdx], Idxs: Index, Name: EVI.getName() + ".elem" + Twine(Index));
1152 Res.push_back(Elt: ResElem);
1153 }
1154
1155 Type *ActualVecType = cast<FixedVectorType>(Val: OpTy->getContainedType(i: Index));
1156 std::optional<VectorSplit> AVS = getVectorSplit(Ty: ActualVecType);
1157 gather(Op: &EVI, CV: Res, VS: *AVS);
1158 return true;
1159}
1160
1161bool ScalarizerVisitor::visitExtractElementInst(ExtractElementInst &EEI) {
1162 std::optional<VectorSplit> VS = getVectorSplit(Ty: EEI.getOperand(i_nocapture: 0)->getType());
1163 if (!VS)
1164 return false;
1165
1166 IRBuilder<> Builder(&EEI);
1167 Scatterer Op0 = scatter(Point: &EEI, V: EEI.getOperand(i_nocapture: 0), VS: *VS);
1168 Value *ExtIdx = EEI.getOperand(i_nocapture: 1);
1169
1170 if (auto *CI = dyn_cast<ConstantInt>(Val: ExtIdx)) {
1171 unsigned Idx = CI->getZExtValue();
1172 if (Idx >= VS->VecTy->getNumElements())
1173 return false;
1174 unsigned Fragment = Idx / VS->NumPacked;
1175 Value *Res = Op0[Fragment];
1176 bool IsPacked = VS->NumPacked > 1;
1177 if (Fragment == VS->NumFragments - 1 && VS->RemainderTy &&
1178 !VS->RemainderTy->isVectorTy())
1179 IsPacked = false;
1180 if (IsPacked)
1181 Res = Builder.CreateExtractElement(Vec: Res, Idx: Idx % VS->NumPacked);
1182 replaceUses(Op: &EEI, CV: Res);
1183 return true;
1184 }
1185
1186 // Never split a variable extractelement that isn't fully scalarized.
1187 if (!ScalarizeVariableInsertExtract || VS->NumPacked > 1)
1188 return false;
1189
1190 Value *Res = PoisonValue::get(T: VS->VecTy->getElementType());
1191 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1192 Value *ShouldExtract =
1193 Builder.CreateICmpEQ(LHS: ExtIdx, RHS: ConstantInt::get(Ty: ExtIdx->getType(), V: I),
1194 Name: ExtIdx->getName() + ".is." + Twine(I));
1195 Value *Elt = Op0[I];
1196 Res = Builder.CreateSelect(C: ShouldExtract, True: Elt, False: Res,
1197 Name: EEI.getName() + ".upto" + Twine(I));
1198 }
1199 replaceUses(Op: &EEI, CV: Res);
1200 return true;
1201}
1202
1203bool ScalarizerVisitor::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
1204 std::optional<VectorSplit> VS = getVectorSplit(Ty: SVI.getType());
1205 std::optional<VectorSplit> VSOp =
1206 getVectorSplit(Ty: SVI.getOperand(i_nocapture: 0)->getType());
1207 if (!VS || !VSOp || VS->NumPacked > 1 || VSOp->NumPacked > 1)
1208 return false;
1209
1210 Scatterer Op0 = scatter(Point: &SVI, V: SVI.getOperand(i_nocapture: 0), VS: *VSOp);
1211 Scatterer Op1 = scatter(Point: &SVI, V: SVI.getOperand(i_nocapture: 1), VS: *VSOp);
1212 ValueVector Res;
1213 Res.resize(N: VS->NumFragments);
1214
1215 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1216 int Selector = SVI.getMaskValue(Elt: I);
1217 if (Selector < 0)
1218 Res[I] = PoisonValue::get(T: VS->VecTy->getElementType());
1219 else if (unsigned(Selector) < Op0.size())
1220 Res[I] = Op0[Selector];
1221 else
1222 Res[I] = Op1[Selector - Op0.size()];
1223 }
1224 gather(Op: &SVI, CV: Res, VS: *VS);
1225 return true;
1226}
1227
1228bool ScalarizerVisitor::visitPHINode(PHINode &PHI) {
1229 std::optional<VectorSplit> VS = getVectorSplit(Ty: PHI.getType());
1230 if (!VS)
1231 return false;
1232
1233 IRBuilder<> Builder(&PHI);
1234 ValueVector Res;
1235 Res.resize(N: VS->NumFragments);
1236
1237 unsigned NumOps = PHI.getNumOperands();
1238 for (unsigned I = 0; I < VS->NumFragments; ++I) {
1239 Res[I] = Builder.CreatePHI(Ty: VS->getFragmentType(I), NumReservedValues: NumOps,
1240 Name: PHI.getName() + ".i" + Twine(I));
1241 }
1242
1243 for (unsigned I = 0; I < NumOps; ++I) {
1244 Scatterer Op = scatter(Point: &PHI, V: PHI.getIncomingValue(i: I), VS: *VS);
1245 BasicBlock *IncomingBlock = PHI.getIncomingBlock(i: I);
1246 for (unsigned J = 0; J < VS->NumFragments; ++J)
1247 cast<PHINode>(Val: Res[J])->addIncoming(V: Op[J], BB: IncomingBlock);
1248 }
1249 gather(Op: &PHI, CV: Res, VS: *VS);
1250 return true;
1251}
1252
1253bool ScalarizerVisitor::visitLoadInst(LoadInst &LI) {
1254 if (!ScalarizeLoadStore)
1255 return false;
1256 if (!LI.isSimple())
1257 return false;
1258
1259 std::optional<VectorLayout> Layout = getVectorLayout(
1260 Ty: LI.getType(), Alignment: LI.getAlign(), DL: LI.getDataLayout());
1261 if (!Layout)
1262 return false;
1263
1264 IRBuilder<> Builder(&LI);
1265 Scatterer Ptr = scatter(Point: &LI, V: LI.getPointerOperand(), VS: Layout->VS);
1266 ValueVector Res;
1267 Res.resize(N: Layout->VS.NumFragments);
1268
1269 for (unsigned I = 0; I < Layout->VS.NumFragments; ++I) {
1270 Res[I] = Builder.CreateAlignedLoad(Ty: Layout->VS.getFragmentType(I), Ptr: Ptr[I],
1271 Align: Align(Layout->getFragmentAlign(Frag: I)),
1272 Name: LI.getName() + ".i" + Twine(I));
1273 }
1274 gather(Op: &LI, CV: Res, VS: Layout->VS);
1275 return true;
1276}
1277
1278bool ScalarizerVisitor::visitStoreInst(StoreInst &SI) {
1279 if (!ScalarizeLoadStore)
1280 return false;
1281 if (!SI.isSimple())
1282 return false;
1283
1284 Value *FullValue = SI.getValueOperand();
1285 std::optional<VectorLayout> Layout = getVectorLayout(
1286 Ty: FullValue->getType(), Alignment: SI.getAlign(), DL: SI.getDataLayout());
1287 if (!Layout)
1288 return false;
1289
1290 IRBuilder<> Builder(&SI);
1291 Scatterer VPtr = scatter(Point: &SI, V: SI.getPointerOperand(), VS: Layout->VS);
1292 Scatterer VVal = scatter(Point: &SI, V: FullValue, VS: Layout->VS);
1293
1294 ValueVector Stores;
1295 Stores.resize(N: Layout->VS.NumFragments);
1296 for (unsigned I = 0; I < Layout->VS.NumFragments; ++I) {
1297 Value *Val = VVal[I];
1298 Value *Ptr = VPtr[I];
1299 Stores[I] =
1300 Builder.CreateAlignedStore(Val, Ptr, Align: Layout->getFragmentAlign(Frag: I));
1301 }
1302 transferMetadataAndIRFlags(Op: &SI, CV: Stores);
1303 return true;
1304}
1305
1306bool ScalarizerVisitor::visitCallInst(CallInst &CI) {
1307 return splitCall(CI);
1308}
1309
1310bool ScalarizerVisitor::visitFreezeInst(FreezeInst &FI) {
1311 return splitUnary(I&: FI, Split: [](IRBuilder<> &Builder, Value *Op, const Twine &Name) {
1312 return Builder.CreateFreeze(V: Op, Name);
1313 });
1314}
1315
1316// Delete the instructions that we scalarized. If a full vector result
1317// is still needed, recreate it using InsertElements.
1318bool ScalarizerVisitor::finish() {
1319 // The presence of data in Gathered or Scattered indicates changes
1320 // made to the Function.
1321 if (Gathered.empty() && Scattered.empty() && !Scalarized)
1322 return false;
1323 for (const auto &GMI : Gathered) {
1324 Instruction *Op = GMI.first;
1325 ValueVector &CV = *GMI.second;
1326 if (!Op->use_empty()) {
1327 // The value is still needed, so recreate it using a series of
1328 // insertelements and/or shufflevectors.
1329 Value *Res;
1330 if (auto *Ty = dyn_cast<FixedVectorType>(Val: Op->getType())) {
1331 BasicBlock *BB = Op->getParent();
1332 IRBuilder<> Builder(Op);
1333 if (isa<PHINode>(Val: Op))
1334 Builder.SetInsertPoint(BB->getFirstInsertionPt());
1335
1336 VectorSplit VS = *getVectorSplit(Ty);
1337 assert(VS.NumFragments == CV.size());
1338
1339 Res = concatenate(Builder, Fragments: CV, VS, Name: Op->getName());
1340
1341 Res->takeName(V: Op);
1342 } else if (auto *Ty = dyn_cast<StructType>(Val: Op->getType())) {
1343 BasicBlock *BB = Op->getParent();
1344 IRBuilder<> Builder(Op);
1345 if (isa<PHINode>(Val: Op))
1346 Builder.SetInsertPoint(BB->getFirstInsertionPt());
1347
1348 // Iterate over each element in the struct
1349 unsigned NumOfStructElements = Ty->getNumElements();
1350 SmallVector<ValueVector, 4> ElemCV(NumOfStructElements);
1351 for (unsigned I = 0; I < NumOfStructElements; ++I) {
1352 for (auto *CVelem : CV) {
1353 Value *Elem = Builder.CreateExtractValue(
1354 Agg: CVelem, Idxs: I, Name: Op->getName() + ".elem" + Twine(I));
1355 ElemCV[I].push_back(Elt: Elem);
1356 }
1357 }
1358 Res = PoisonValue::get(T: Ty);
1359 for (unsigned I = 0; I < NumOfStructElements; ++I) {
1360 Type *ElemTy = Ty->getElementType(N: I);
1361 assert(isa<FixedVectorType>(ElemTy) &&
1362 "Only Structs of all FixedVectorType supported");
1363 VectorSplit VS = *getVectorSplit(Ty: ElemTy);
1364 assert(VS.NumFragments == CV.size());
1365
1366 Value *ConcatenatedVector =
1367 concatenate(Builder, Fragments: ElemCV[I], VS, Name: Op->getName());
1368 Res = Builder.CreateInsertValue(Agg: Res, Val: ConcatenatedVector, Idxs: I,
1369 Name: Op->getName() + ".insert");
1370 }
1371 } else {
1372 assert(CV.size() == 1 && Op->getType() == CV[0]->getType());
1373 Res = CV[0];
1374 if (Op == Res)
1375 continue;
1376 }
1377 Op->replaceAllUsesWith(V: Res);
1378 }
1379 PotentiallyDeadInstrs.emplace_back(Args&: Op);
1380 }
1381 Gathered.clear();
1382 Scattered.clear();
1383 Scalarized = false;
1384
1385 RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts&: PotentiallyDeadInstrs);
1386
1387 return true;
1388}
1389
1390PreservedAnalyses ScalarizerPass::run(Function &F, FunctionAnalysisManager &AM) {
1391 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F);
1392 const TargetTransformInfo *TTI = &AM.getResult<TargetIRAnalysis>(IR&: F);
1393 ScalarizerVisitor Impl(DT, TTI, Options);
1394 bool Changed = Impl.visit(F);
1395 PreservedAnalyses PA;
1396 PA.preserve<DominatorTreeAnalysis>();
1397 return Changed ? PA : PreservedAnalyses::all();
1398}
1399