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