1//===- ScalarizeMaskedMemIntrin.cpp - Scalarize unsupported masked mem ----===//
2// intrinsics
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass replaces masked memory intrinsics - when unsupported by the target
11// - with a chain of basic blocks, that deal with the elements one-by-one if the
12// appropriate mask bit is set.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Transforms/Scalar/ScalarizeMaskedMemIntrin.h"
17#include "llvm/ADT/Twine.h"
18#include "llvm/Analysis/DomTreeUpdater.h"
19#include "llvm/Analysis/TargetTransformInfo.h"
20#include "llvm/Analysis/VectorUtils.h"
21#include "llvm/IR/BasicBlock.h"
22#include "llvm/IR/Constant.h"
23#include "llvm/IR/Constants.h"
24#include "llvm/IR/DerivedTypes.h"
25#include "llvm/IR/Dominators.h"
26#include "llvm/IR/Function.h"
27#include "llvm/IR/IRBuilder.h"
28#include "llvm/IR/Instruction.h"
29#include "llvm/IR/Instructions.h"
30#include "llvm/IR/IntrinsicInst.h"
31#include "llvm/IR/MemCacheHint.h"
32#include "llvm/IR/Metadata.h"
33#include "llvm/IR/ProfDataUtils.h"
34#include "llvm/IR/Type.h"
35#include "llvm/IR/Value.h"
36#include "llvm/InitializePasses.h"
37#include "llvm/Pass.h"
38#include "llvm/Support/Casting.h"
39#include "llvm/Transforms/Scalar.h"
40#include "llvm/Transforms/Utils/BasicBlockUtils.h"
41#include <cassert>
42#include <optional>
43
44using namespace llvm;
45
46#define DEBUG_TYPE "scalarize-masked-mem-intrin"
47
48namespace {
49
50class ScalarizeMaskedMemIntrinLegacyPass : public FunctionPass {
51public:
52 static char ID; // Pass identification, replacement for typeid
53
54 explicit ScalarizeMaskedMemIntrinLegacyPass() : FunctionPass(ID) {
55 initializeScalarizeMaskedMemIntrinLegacyPassPass(
56 *PassRegistry::getPassRegistry());
57 }
58
59 bool runOnFunction(Function &F) override;
60
61 StringRef getPassName() const override {
62 return "Scalarize Masked Memory Intrinsics";
63 }
64
65 void getAnalysisUsage(AnalysisUsage &AU) const override {
66 AU.addRequired<TargetTransformInfoWrapperPass>();
67 AU.addPreserved<DominatorTreeWrapperPass>();
68 }
69};
70
71} // end anonymous namespace
72
73static bool optimizeBlock(BasicBlock &BB, bool &ModifiedDT,
74 const TargetTransformInfo &TTI, const DataLayout &DL,
75 bool HasBranchDivergence, DomTreeUpdater *DTU);
76static bool optimizeCallInst(CallInst *CI, bool &ModifiedDT,
77 const TargetTransformInfo &TTI,
78 const DataLayout &DL, bool HasBranchDivergence,
79 DomTreeUpdater *DTU);
80
81char ScalarizeMaskedMemIntrinLegacyPass::ID = 0;
82
83INITIALIZE_PASS_BEGIN(ScalarizeMaskedMemIntrinLegacyPass, DEBUG_TYPE,
84 "Scalarize unsupported masked memory intrinsics", false,
85 false)
86INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
87INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
88INITIALIZE_PASS_END(ScalarizeMaskedMemIntrinLegacyPass, DEBUG_TYPE,
89 "Scalarize unsupported masked memory intrinsics", false,
90 false)
91
92FunctionPass *llvm::createScalarizeMaskedMemIntrinLegacyPass() {
93 return new ScalarizeMaskedMemIntrinLegacyPass();
94}
95
96static bool isConstantIntVector(Value *Mask) {
97 Constant *C = dyn_cast<Constant>(Val: Mask);
98 if (!C)
99 return false;
100
101 unsigned NumElts = cast<FixedVectorType>(Val: Mask->getType())->getNumElements();
102 for (unsigned i = 0; i != NumElts; ++i) {
103 Constant *CElt = C->getAggregateElement(Elt: i);
104 if (!CElt || !isa<ConstantInt>(Val: CElt))
105 return false;
106 }
107
108 return true;
109}
110
111static unsigned adjustForEndian(const DataLayout &DL, unsigned VectorWidth,
112 unsigned Idx) {
113 return DL.isBigEndian() ? VectorWidth - 1 - Idx : Idx;
114}
115
116static void copyMetadataForMemoryAccess(
117 Instruction &Dest, const Instruction &Source, const DataLayout &DL,
118 unsigned SourcePtrOperand, unsigned DestPtrOperand, Type *AccessType,
119 bool IsWholeAccess, std::optional<size_t> ByteOffset) {
120 // Only propagate metadata that is valid on each constituent memory access.
121 // In particular, do not copy metadata whose meaning is tied to the call,
122 // such as !prof or !callsite.
123 Dest.copyMetadata(SrcInst: Source,
124 WL: {LLVMContext::MD_nontemporal,
125 LLVMContext::MD_mem_parallel_loop_access,
126 LLVMContext::MD_access_group, LLVMContext::MD_annotation,
127 LLVMContext::MD_nosanitize, LLVMContext::MD_mmra});
128
129 AAMDNodes AANodes = Source.getAAMetadata();
130 if (IsWholeAccess)
131 Dest.setAAMetadata(AANodes);
132 else if (ByteOffset)
133 Dest.setAAMetadata(AANodes.adjustForAccess(Offset: *ByteOffset, AccessTy: AccessType, DL));
134 else {
135 // The packed address is runtime-dependent. The other AA metadata remains
136 // applicable, but !tbaa.struct cannot be adjusted to a known byte range.
137 AANodes.TBAAStruct = nullptr;
138 Dest.setAAMetadata(AANodes);
139 }
140 setMemCacheHint(I&: Dest, OperandNo: DestPtrOperand,
141 Hint: getMemCacheHint(I: Source, OperandNo: SourcePtrOperand));
142}
143
144static void copyMetadataForScalarizedLoad(LoadInst &Dest,
145 const Instruction &Source,
146 const DataLayout &DL,
147 unsigned SourcePtrOperand,
148 std::optional<size_t> ByteOffset) {
149 copyMetadataForMemoryAccess(Dest, Source, DL, SourcePtrOperand,
150 DestPtrOperand: Dest.getPointerOperandIndex(), AccessType: Dest.getType(),
151 IsWholeAccess: Dest.getType() == Source.getType(), ByteOffset);
152
153 // !range applies element-wise to vectors, so the same range describes each
154 // scalar result. The other metadata here also describes the loaded result.
155 Dest.copyMetadata(SrcInst: Source, WL: {LLVMContext::MD_fpmath, LLVMContext::MD_range,
156 LLVMContext::MD_invariant_load});
157}
158
159static void copyMetadataForScalarizedStore(StoreInst &Dest,
160 const Instruction &Source,
161 const DataLayout &DL,
162 unsigned SourcePtrOperand,
163 std::optional<size_t> ByteOffset) {
164 copyMetadataForMemoryAccess(
165 Dest, Source, DL, SourcePtrOperand, DestPtrOperand: Dest.getPointerOperandIndex(),
166 AccessType: Dest.getValueOperand()->getType(),
167 IsWholeAccess: Dest.getValueOperand()->getType() == Source.getOperand(i: 0)->getType(),
168 ByteOffset);
169}
170
171// Translate a masked load intrinsic like
172// <16 x i32 > @llvm.masked.load( <16 x i32>* %addr,
173// <16 x i1> %mask, <16 x i32> %passthru)
174// to a chain of basic blocks, with loading element one-by-one if
175// the appropriate mask bit is set
176//
177// %1 = bitcast i8* %addr to i32*
178// %2 = extractelement <16 x i1> %mask, i32 0
179// br i1 %2, label %cond.load, label %else
180//
181// cond.load: ; preds = %0
182// %3 = getelementptr i32* %1, i32 0
183// %4 = load i32* %3
184// %5 = insertelement <16 x i32> %passthru, i32 %4, i32 0
185// br label %else
186//
187// else: ; preds = %0, %cond.load
188// %res.phi.else = phi <16 x i32> [ %5, %cond.load ], [ poison, %0 ]
189// %6 = extractelement <16 x i1> %mask, i32 1
190// br i1 %6, label %cond.load1, label %else2
191//
192// cond.load1: ; preds = %else
193// %7 = getelementptr i32* %1, i32 1
194// %8 = load i32* %7
195// %9 = insertelement <16 x i32> %res.phi.else, i32 %8, i32 1
196// br label %else2
197//
198// else2: ; preds = %else, %cond.load1
199// %res.phi.else3 = phi <16 x i32> [ %9, %cond.load1 ], [ %res.phi.else, %else
200// ] %10 = extractelement <16 x i1> %mask, i32 2 br i1 %10, label %cond.load4,
201// label %else5
202//
203static void scalarizeMaskedLoad(const DataLayout &DL, bool HasBranchDivergence,
204 CallInst *CI, DomTreeUpdater *DTU,
205 bool &ModifiedDT) {
206 Value *Ptr = CI->getArgOperand(i: 0);
207 Value *Mask = CI->getArgOperand(i: 1);
208 Value *Src0 = CI->getArgOperand(i: 2);
209
210 const Align AlignVal = CI->getParamAlign(ArgNo: 0).valueOrOne();
211 VectorType *VecType = cast<FixedVectorType>(Val: CI->getType());
212
213 Type *EltTy = VecType->getElementType();
214
215 Instruction *InsertPt = CI;
216 IRBuilder<> Builder(InsertPt);
217 Builder.disableGEPCanonicalization();
218 BasicBlock *IfBlock = CI->getParent();
219
220 // Short-cut if the mask is all-true.
221 if (isa<Constant>(Val: Mask) && cast<Constant>(Val: Mask)->isAllOnesValue()) {
222 LoadInst *NewI = Builder.CreateAlignedLoad(Ty: VecType, Ptr, Align: AlignVal);
223 copyMetadataForScalarizedLoad(Dest&: *NewI, Source: *CI, DL, /*SourcePtrOperand=*/0,
224 ByteOffset: std::nullopt);
225 NewI->takeName(V: CI);
226 CI->replaceAllUsesWith(V: NewI);
227 CI->eraseFromParent();
228 return;
229 }
230
231 // Adjust alignment for the scalar instruction.
232 const Align AdjustedAlignVal =
233 commonAlignment(A: AlignVal, Offset: EltTy->getPrimitiveSizeInBits() / 8);
234 unsigned VectorWidth = cast<FixedVectorType>(Val: VecType)->getNumElements();
235
236 // The result vector
237 Value *VResult = Src0;
238
239 if (isConstantIntVector(Mask)) {
240 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
241 if (cast<Constant>(Val: Mask)->getAggregateElement(Elt: Idx)->isNullValue())
242 continue;
243 Value *Gep = Builder.CreateConstInBoundsGEP1_32(Ty: EltTy, Ptr, Idx0: Idx);
244 LoadInst *Load = Builder.CreateAlignedLoad(Ty: EltTy, Ptr: Gep, Align: AdjustedAlignVal);
245 copyMetadataForScalarizedLoad(
246 Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
247 ByteOffset: Idx * DL.getTypeAllocSize(Ty: EltTy).getFixedValue());
248 VResult = Builder.CreateInsertElement(Vec: VResult, NewElt: Load, Idx);
249 }
250 CI->replaceAllUsesWith(V: VResult);
251 CI->eraseFromParent();
252 return;
253 }
254
255 // Optimize the case where the "masked load" is a predicated load - that is,
256 // where the mask is the splat of a non-constant scalar boolean. In that case,
257 // use that splated value as the guard on a conditional vector load.
258 if (isSplatValue(V: Mask, /*Index=*/0)) {
259 Value *Predicate = Builder.CreateExtractElement(Vec: Mask, Idx: uint64_t(0ull),
260 Name: Mask->getName() + ".first");
261 // We mark the branch weights as explicitly unknown given they would only
262 // be derivable from the mask which we do not have VP information for.
263 Instruction *ThenTerm =
264 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
265 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
266 F&: *CI->getFunction(), DEBUG_TYPE),
267 DTU);
268
269 BasicBlock *CondBlock = ThenTerm->getParent();
270 CondBlock->setName("cond.load");
271 Builder.SetInsertPoint(CondBlock->getTerminator());
272 LoadInst *Load = Builder.CreateAlignedLoad(Ty: VecType, Ptr, Align: AlignVal,
273 Name: CI->getName() + ".cond.load");
274 copyMetadataForScalarizedLoad(Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
275 ByteOffset: std::nullopt);
276
277 BasicBlock *PostLoad = ThenTerm->getSuccessor(Idx: 0);
278 Builder.SetInsertPoint(PostLoad->begin());
279 PHINode *Phi = Builder.CreatePHI(Ty: VecType, /*NumReservedValues=*/2);
280 Phi->addIncoming(V: Load, BB: CondBlock);
281 Phi->addIncoming(V: Src0, BB: IfBlock);
282 Phi->takeName(V: CI);
283
284 CI->replaceAllUsesWith(V: Phi);
285 CI->eraseFromParent();
286 ModifiedDT = true;
287 return;
288 }
289 // If the mask is not v1i1, use scalar bit test operations. This generates
290 // better results on X86 at least. However, don't do this on GPUs and other
291 // machines with divergence, as there each i1 needs a vector register.
292 Value *SclrMask = nullptr;
293 if (VectorWidth != 1 && !HasBranchDivergence) {
294 Type *SclrMaskTy = Builder.getIntNTy(N: VectorWidth);
295 SclrMask = Builder.CreateBitCast(V: Mask, DestTy: SclrMaskTy, Name: "scalar_mask");
296 }
297
298 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
299 // Fill the "else" block, created in the previous iteration
300 //
301 // %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else,
302 // %else ] %mask_1 = and i16 %scalar_mask, i32 1 << Idx %cond = icmp ne i16
303 // %mask_1, 0 br i1 %mask_1, label %cond.load, label %else
304 //
305 // On GPUs, use
306 // %cond = extrectelement %mask, Idx
307 // instead
308 Value *Predicate;
309 if (SclrMask != nullptr) {
310 Value *Mask = Builder.getInt(AI: APInt::getOneBitSet(
311 numBits: VectorWidth, BitNo: adjustForEndian(DL, VectorWidth, Idx)));
312 Predicate = Builder.CreateICmpNE(LHS: Builder.CreateAnd(LHS: SclrMask, RHS: Mask),
313 RHS: Builder.getIntN(N: VectorWidth, C: 0));
314 } else {
315 Predicate = Builder.CreateExtractElement(Vec: Mask, Idx);
316 }
317
318 // Create "cond" block
319 //
320 // %EltAddr = getelementptr i32* %1, i32 0
321 // %Elt = load i32* %EltAddr
322 // VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx
323 //
324 // We mark the branch weights as explicitly unknown given they would only
325 // be derivable from the mask which we do not have VP information for.
326 Instruction *ThenTerm =
327 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
328 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
329 F&: *CI->getFunction(), DEBUG_TYPE),
330 DTU);
331
332 BasicBlock *CondBlock = ThenTerm->getParent();
333 CondBlock->setName("cond.load");
334
335 Builder.SetInsertPoint(CondBlock->getTerminator());
336 Value *Gep = Builder.CreateConstInBoundsGEP1_32(Ty: EltTy, Ptr, Idx0: Idx);
337 LoadInst *Load = Builder.CreateAlignedLoad(Ty: EltTy, Ptr: Gep, Align: AdjustedAlignVal);
338 copyMetadataForScalarizedLoad(
339 Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
340 ByteOffset: Idx * DL.getTypeAllocSize(Ty: EltTy).getFixedValue());
341 Value *NewVResult = Builder.CreateInsertElement(Vec: VResult, NewElt: Load, Idx);
342
343 // Create "else" block, fill it in the next iteration
344 BasicBlock *NewIfBlock = ThenTerm->getSuccessor(Idx: 0);
345 NewIfBlock->setName("else");
346 BasicBlock *PrevIfBlock = IfBlock;
347 IfBlock = NewIfBlock;
348
349 // Create the phi to join the new and previous value.
350 Builder.SetInsertPoint(NewIfBlock->begin());
351 PHINode *Phi = Builder.CreatePHI(Ty: VecType, NumReservedValues: 2, Name: "res.phi.else");
352 Phi->addIncoming(V: NewVResult, BB: CondBlock);
353 Phi->addIncoming(V: VResult, BB: PrevIfBlock);
354 VResult = Phi;
355 }
356
357 CI->replaceAllUsesWith(V: VResult);
358 CI->eraseFromParent();
359
360 ModifiedDT = true;
361}
362
363// Translate a masked store intrinsic, like
364// void @llvm.masked.store(<16 x i32> %src, <16 x i32>* %addr,
365// <16 x i1> %mask)
366// to a chain of basic blocks, that stores element one-by-one if
367// the appropriate mask bit is set
368//
369// %1 = bitcast i8* %addr to i32*
370// %2 = extractelement <16 x i1> %mask, i32 0
371// br i1 %2, label %cond.store, label %else
372//
373// cond.store: ; preds = %0
374// %3 = extractelement <16 x i32> %val, i32 0
375// %4 = getelementptr i32* %1, i32 0
376// store i32 %3, i32* %4
377// br label %else
378//
379// else: ; preds = %0, %cond.store
380// %5 = extractelement <16 x i1> %mask, i32 1
381// br i1 %5, label %cond.store1, label %else2
382//
383// cond.store1: ; preds = %else
384// %6 = extractelement <16 x i32> %val, i32 1
385// %7 = getelementptr i32* %1, i32 1
386// store i32 %6, i32* %7
387// br label %else2
388// . . .
389static void scalarizeMaskedStore(const DataLayout &DL, bool HasBranchDivergence,
390 CallInst *CI, DomTreeUpdater *DTU,
391 bool &ModifiedDT) {
392 Value *Src = CI->getArgOperand(i: 0);
393 Value *Ptr = CI->getArgOperand(i: 1);
394 Value *Mask = CI->getArgOperand(i: 2);
395
396 const Align AlignVal = CI->getParamAlign(ArgNo: 1).valueOrOne();
397 auto *VecType = cast<VectorType>(Val: Src->getType());
398
399 Type *EltTy = VecType->getElementType();
400
401 Instruction *InsertPt = CI;
402 IRBuilder<> Builder(InsertPt);
403 Builder.disableGEPCanonicalization();
404
405 // Short-cut if the mask is all-true.
406 if (isa<Constant>(Val: Mask) && cast<Constant>(Val: Mask)->isAllOnesValue()) {
407 StoreInst *Store = Builder.CreateAlignedStore(Val: Src, Ptr, Align: AlignVal);
408 Store->takeName(V: CI);
409 copyMetadataForScalarizedStore(Dest&: *Store, Source: *CI, DL, /*SourcePtrOperand=*/1,
410 ByteOffset: std::nullopt);
411 // This is a one-to-one replacement, so the assignment link remains valid.
412 Store->copyMetadata(SrcInst: *CI, WL: LLVMContext::MD_DIAssignID);
413 CI->eraseFromParent();
414 return;
415 }
416
417 // Adjust alignment for the scalar instruction.
418 const Align AdjustedAlignVal =
419 commonAlignment(A: AlignVal, Offset: EltTy->getPrimitiveSizeInBits() / 8);
420 unsigned VectorWidth = cast<FixedVectorType>(Val: VecType)->getNumElements();
421
422 if (isConstantIntVector(Mask)) {
423 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
424 if (cast<Constant>(Val: Mask)->getAggregateElement(Elt: Idx)->isNullValue())
425 continue;
426 Value *OneElt = Builder.CreateExtractElement(Vec: Src, Idx);
427 Value *Gep = Builder.CreateConstInBoundsGEP1_32(Ty: EltTy, Ptr, Idx0: Idx);
428 StoreInst *Store =
429 Builder.CreateAlignedStore(Val: OneElt, Ptr: Gep, Align: AdjustedAlignVal);
430 copyMetadataForScalarizedStore(
431 Dest&: *Store, Source: *CI, DL, /*SourcePtrOperand=*/1,
432 ByteOffset: Idx * DL.getTypeAllocSize(Ty: EltTy).getFixedValue());
433 }
434 CI->eraseFromParent();
435 return;
436 }
437
438 // Optimize the case where the "masked store" is a predicated store - that is,
439 // when the mask is the splat of a non-constant scalar boolean. In that case,
440 // optimize to a conditional store.
441 if (isSplatValue(V: Mask, /*Index=*/0)) {
442 Value *Predicate = Builder.CreateExtractElement(Vec: Mask, Idx: uint64_t(0ull),
443 Name: Mask->getName() + ".first");
444 // We mark the branch weights as explicitly unknown given they would only
445 // be derivable from the mask which we do not have VP information for.
446 Instruction *ThenTerm =
447 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
448 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
449 F&: *CI->getFunction(), DEBUG_TYPE),
450 DTU);
451 BasicBlock *CondBlock = ThenTerm->getParent();
452 CondBlock->setName("cond.store");
453 Builder.SetInsertPoint(CondBlock->getTerminator());
454
455 StoreInst *Store = Builder.CreateAlignedStore(Val: Src, Ptr, Align: AlignVal);
456 Store->takeName(V: CI);
457 copyMetadataForScalarizedStore(Dest&: *Store, Source: *CI, DL, /*SourcePtrOperand=*/1,
458 ByteOffset: std::nullopt);
459 // This is a one-to-one replacement, so the assignment link remains valid.
460 Store->copyMetadata(SrcInst: *CI, WL: LLVMContext::MD_DIAssignID);
461
462 CI->eraseFromParent();
463 ModifiedDT = true;
464 return;
465 }
466
467 // If the mask is not v1i1, use scalar bit test operations. This generates
468 // better results on X86 at least. However, don't do this on GPUs or other
469 // machines with branch divergence, as there each i1 takes up a register.
470 Value *SclrMask = nullptr;
471 if (VectorWidth != 1 && !HasBranchDivergence) {
472 Type *SclrMaskTy = Builder.getIntNTy(N: VectorWidth);
473 SclrMask = Builder.CreateBitCast(V: Mask, DestTy: SclrMaskTy, Name: "scalar_mask");
474 }
475
476 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
477 // Fill the "else" block, created in the previous iteration
478 //
479 // %mask_1 = and i16 %scalar_mask, i32 1 << Idx
480 // %cond = icmp ne i16 %mask_1, 0
481 // br i1 %mask_1, label %cond.store, label %else
482 //
483 // On GPUs, use
484 // %cond = extrectelement %mask, Idx
485 // instead
486 Value *Predicate;
487 if (SclrMask != nullptr) {
488 Value *Mask = Builder.getInt(AI: APInt::getOneBitSet(
489 numBits: VectorWidth, BitNo: adjustForEndian(DL, VectorWidth, Idx)));
490 Predicate = Builder.CreateICmpNE(LHS: Builder.CreateAnd(LHS: SclrMask, RHS: Mask),
491 RHS: Builder.getIntN(N: VectorWidth, C: 0));
492 } else {
493 Predicate = Builder.CreateExtractElement(Vec: Mask, Idx);
494 }
495
496 // Create "cond" block
497 //
498 // %OneElt = extractelement <16 x i32> %Src, i32 Idx
499 // %EltAddr = getelementptr i32* %1, i32 0
500 // %store i32 %OneElt, i32* %EltAddr
501 //
502 // We mark the branch weights as explicitly unknown given they would only
503 // be derivable from the mask which we do not have VP information for.
504 Instruction *ThenTerm =
505 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
506 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
507 F&: *CI->getFunction(), DEBUG_TYPE),
508 DTU);
509
510 BasicBlock *CondBlock = ThenTerm->getParent();
511 CondBlock->setName("cond.store");
512
513 Builder.SetInsertPoint(CondBlock->getTerminator());
514 Value *OneElt = Builder.CreateExtractElement(Vec: Src, Idx);
515 Value *Gep = Builder.CreateConstInBoundsGEP1_32(Ty: EltTy, Ptr, Idx0: Idx);
516 StoreInst *Store =
517 Builder.CreateAlignedStore(Val: OneElt, Ptr: Gep, Align: AdjustedAlignVal);
518 copyMetadataForScalarizedStore(
519 Dest&: *Store, Source: *CI, DL, /*SourcePtrOperand=*/1,
520 ByteOffset: Idx * DL.getTypeAllocSize(Ty: EltTy).getFixedValue());
521
522 // Create "else" block, fill it in the next iteration
523 BasicBlock *NewIfBlock = ThenTerm->getSuccessor(Idx: 0);
524 NewIfBlock->setName("else");
525
526 Builder.SetInsertPoint(NewIfBlock->begin());
527 }
528 CI->eraseFromParent();
529
530 ModifiedDT = true;
531}
532
533// Translate a masked gather intrinsic like
534// <16 x i32 > @llvm.masked.gather.v16i32( <16 x i32*> %Ptrs, i32 4,
535// <16 x i1> %Mask, <16 x i32> %Src)
536// to a chain of basic blocks, with loading element one-by-one if
537// the appropriate mask bit is set
538//
539// %Ptrs = getelementptr i32, i32* %base, <16 x i64> %ind
540// %Mask0 = extractelement <16 x i1> %Mask, i32 0
541// br i1 %Mask0, label %cond.load, label %else
542//
543// cond.load:
544// %Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0
545// %Load0 = load i32, i32* %Ptr0, align 4
546// %Res0 = insertelement <16 x i32> poison, i32 %Load0, i32 0
547// br label %else
548//
549// else:
550// %res.phi.else = phi <16 x i32>[%Res0, %cond.load], [poison, %0]
551// %Mask1 = extractelement <16 x i1> %Mask, i32 1
552// br i1 %Mask1, label %cond.load1, label %else2
553//
554// cond.load1:
555// %Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
556// %Load1 = load i32, i32* %Ptr1, align 4
557// %Res1 = insertelement <16 x i32> %res.phi.else, i32 %Load1, i32 1
558// br label %else2
559// . . .
560// %Result = select <16 x i1> %Mask, <16 x i32> %res.phi.select, <16 x i32> %Src
561// ret <16 x i32> %Result
562static void scalarizeMaskedGather(const DataLayout &DL,
563 bool HasBranchDivergence, CallInst *CI,
564 DomTreeUpdater *DTU, bool &ModifiedDT) {
565 Value *Ptrs = CI->getArgOperand(i: 0);
566 Value *Mask = CI->getArgOperand(i: 1);
567 Value *Src0 = CI->getArgOperand(i: 2);
568
569 auto *VecType = cast<FixedVectorType>(Val: CI->getType());
570 Type *EltTy = VecType->getElementType();
571
572 Instruction *InsertPt = CI;
573 IRBuilder<> Builder(InsertPt);
574 BasicBlock *IfBlock = CI->getParent();
575 Align AlignVal = CI->getParamAlign(ArgNo: 0).valueOrOne();
576
577 // The result vector
578 Value *VResult = Src0;
579 unsigned VectorWidth = VecType->getNumElements();
580
581 // Shorten the way if the mask is a vector of constants.
582 if (isConstantIntVector(Mask)) {
583 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
584 if (cast<Constant>(Val: Mask)->getAggregateElement(Elt: Idx)->isNullValue())
585 continue;
586 Value *Ptr = Builder.CreateExtractElement(Vec: Ptrs, Idx, Name: "Ptr" + Twine(Idx));
587 LoadInst *Load =
588 Builder.CreateAlignedLoad(Ty: EltTy, Ptr, Align: AlignVal, Name: "Load" + Twine(Idx));
589 copyMetadataForScalarizedLoad(Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
590 /*ByteOffset=*/0);
591 VResult =
592 Builder.CreateInsertElement(Vec: VResult, NewElt: Load, Idx, Name: "Res" + Twine(Idx));
593 }
594 CI->replaceAllUsesWith(V: VResult);
595 CI->eraseFromParent();
596 return;
597 }
598
599 // If the mask is not v1i1, use scalar bit test operations. This generates
600 // better results on X86 at least. However, don't do this on GPUs or other
601 // machines with branch divergence, as there, each i1 takes up a register.
602 Value *SclrMask = nullptr;
603 if (VectorWidth != 1 && !HasBranchDivergence) {
604 Type *SclrMaskTy = Builder.getIntNTy(N: VectorWidth);
605 SclrMask = Builder.CreateBitCast(V: Mask, DestTy: SclrMaskTy, Name: "scalar_mask");
606 }
607
608 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
609 // Fill the "else" block, created in the previous iteration
610 //
611 // %Mask1 = and i16 %scalar_mask, i32 1 << Idx
612 // %cond = icmp ne i16 %mask_1, 0
613 // br i1 %Mask1, label %cond.load, label %else
614 //
615 // On GPUs, use
616 // %cond = extrectelement %mask, Idx
617 // instead
618
619 Value *Predicate;
620 if (SclrMask != nullptr) {
621 Value *Mask = Builder.getInt(AI: APInt::getOneBitSet(
622 numBits: VectorWidth, BitNo: adjustForEndian(DL, VectorWidth, Idx)));
623 Predicate = Builder.CreateICmpNE(LHS: Builder.CreateAnd(LHS: SclrMask, RHS: Mask),
624 RHS: Builder.getIntN(N: VectorWidth, C: 0));
625 } else {
626 Predicate = Builder.CreateExtractElement(Vec: Mask, Idx, Name: "Mask" + Twine(Idx));
627 }
628
629 // Create "cond" block
630 //
631 // %EltAddr = getelementptr i32* %1, i32 0
632 // %Elt = load i32* %EltAddr
633 // VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx
634 //
635 // We mark the branch weights as explicitly unknown given they would only
636 // be derivable from the mask which we do not have VP information for.
637 Instruction *ThenTerm =
638 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
639 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
640 F&: *CI->getFunction(), DEBUG_TYPE),
641 DTU);
642
643 BasicBlock *CondBlock = ThenTerm->getParent();
644 CondBlock->setName("cond.load");
645
646 Builder.SetInsertPoint(CondBlock->getTerminator());
647 Value *Ptr = Builder.CreateExtractElement(Vec: Ptrs, Idx, Name: "Ptr" + Twine(Idx));
648 LoadInst *Load =
649 Builder.CreateAlignedLoad(Ty: EltTy, Ptr, Align: AlignVal, Name: "Load" + Twine(Idx));
650 copyMetadataForScalarizedLoad(Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
651 /*ByteOffset=*/0);
652 Value *NewVResult =
653 Builder.CreateInsertElement(Vec: VResult, NewElt: Load, Idx, Name: "Res" + Twine(Idx));
654
655 // Create "else" block, fill it in the next iteration
656 BasicBlock *NewIfBlock = ThenTerm->getSuccessor(Idx: 0);
657 NewIfBlock->setName("else");
658 BasicBlock *PrevIfBlock = IfBlock;
659 IfBlock = NewIfBlock;
660
661 // Create the phi to join the new and previous value.
662 Builder.SetInsertPoint(NewIfBlock->begin());
663 PHINode *Phi = Builder.CreatePHI(Ty: VecType, NumReservedValues: 2, Name: "res.phi.else");
664 Phi->addIncoming(V: NewVResult, BB: CondBlock);
665 Phi->addIncoming(V: VResult, BB: PrevIfBlock);
666 VResult = Phi;
667 }
668
669 CI->replaceAllUsesWith(V: VResult);
670 CI->eraseFromParent();
671
672 ModifiedDT = true;
673}
674
675// Translate a masked scatter intrinsic, like
676// void @llvm.masked.scatter.v16i32(<16 x i32> %Src, <16 x i32*>* %Ptrs, i32 4,
677// <16 x i1> %Mask)
678// to a chain of basic blocks, that stores element one-by-one if
679// the appropriate mask bit is set.
680//
681// %Ptrs = getelementptr i32, i32* %ptr, <16 x i64> %ind
682// %Mask0 = extractelement <16 x i1> %Mask, i32 0
683// br i1 %Mask0, label %cond.store, label %else
684//
685// cond.store:
686// %Elt0 = extractelement <16 x i32> %Src, i32 0
687// %Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0
688// store i32 %Elt0, i32* %Ptr0, align 4
689// br label %else
690//
691// else:
692// %Mask1 = extractelement <16 x i1> %Mask, i32 1
693// br i1 %Mask1, label %cond.store1, label %else2
694//
695// cond.store1:
696// %Elt1 = extractelement <16 x i32> %Src, i32 1
697// %Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
698// store i32 %Elt1, i32* %Ptr1, align 4
699// br label %else2
700// . . .
701static void scalarizeMaskedScatter(const DataLayout &DL,
702 bool HasBranchDivergence, CallInst *CI,
703 DomTreeUpdater *DTU, bool &ModifiedDT) {
704 Value *Src = CI->getArgOperand(i: 0);
705 Value *Ptrs = CI->getArgOperand(i: 1);
706 Value *Mask = CI->getArgOperand(i: 2);
707
708 auto *SrcFVTy = cast<FixedVectorType>(Val: Src->getType());
709
710 assert(
711 isa<VectorType>(Ptrs->getType()) &&
712 isa<PointerType>(cast<VectorType>(Ptrs->getType())->getElementType()) &&
713 "Vector of pointers is expected in masked scatter intrinsic");
714
715 Instruction *InsertPt = CI;
716 IRBuilder<> Builder(InsertPt);
717
718 Align AlignVal = CI->getParamAlign(ArgNo: 1).valueOrOne();
719 unsigned VectorWidth = SrcFVTy->getNumElements();
720
721 // Shorten the way if the mask is a vector of constants.
722 if (isConstantIntVector(Mask)) {
723 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
724 if (cast<Constant>(Val: Mask)->getAggregateElement(Elt: Idx)->isNullValue())
725 continue;
726 Value *OneElt =
727 Builder.CreateExtractElement(Vec: Src, Idx, Name: "Elt" + Twine(Idx));
728 Value *Ptr = Builder.CreateExtractElement(Vec: Ptrs, Idx, Name: "Ptr" + Twine(Idx));
729 StoreInst *Store = Builder.CreateAlignedStore(Val: OneElt, Ptr, Align: AlignVal);
730 copyMetadataForScalarizedStore(Dest&: *Store, Source: *CI, DL,
731 /*SourcePtrOperand=*/1,
732 /*ByteOffset=*/0);
733 }
734 CI->eraseFromParent();
735 return;
736 }
737
738 // If the mask is not v1i1, use scalar bit test operations. This generates
739 // better results on X86 at least.
740 Value *SclrMask = nullptr;
741 if (VectorWidth != 1 && !HasBranchDivergence) {
742 Type *SclrMaskTy = Builder.getIntNTy(N: VectorWidth);
743 SclrMask = Builder.CreateBitCast(V: Mask, DestTy: SclrMaskTy, Name: "scalar_mask");
744 }
745
746 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
747 // Fill the "else" block, created in the previous iteration
748 //
749 // %Mask1 = and i16 %scalar_mask, i32 1 << Idx
750 // %cond = icmp ne i16 %mask_1, 0
751 // br i1 %Mask1, label %cond.store, label %else
752 //
753 // On GPUs, use
754 // %cond = extrectelement %mask, Idx
755 // instead
756 Value *Predicate;
757 if (SclrMask != nullptr) {
758 Value *Mask = Builder.getInt(AI: APInt::getOneBitSet(
759 numBits: VectorWidth, BitNo: adjustForEndian(DL, VectorWidth, Idx)));
760 Predicate = Builder.CreateICmpNE(LHS: Builder.CreateAnd(LHS: SclrMask, RHS: Mask),
761 RHS: Builder.getIntN(N: VectorWidth, C: 0));
762 } else {
763 Predicate = Builder.CreateExtractElement(Vec: Mask, Idx, Name: "Mask" + Twine(Idx));
764 }
765
766 // Create "cond" block
767 //
768 // %Elt1 = extractelement <16 x i32> %Src, i32 1
769 // %Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
770 // %store i32 %Elt1, i32* %Ptr1
771 //
772 // We mark the branch weights as explicitly unknown given they would only
773 // be derivable from the mask which we do not have VP information for.
774 Instruction *ThenTerm =
775 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
776 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
777 F&: *CI->getFunction(), DEBUG_TYPE),
778 DTU);
779
780 BasicBlock *CondBlock = ThenTerm->getParent();
781 CondBlock->setName("cond.store");
782
783 Builder.SetInsertPoint(CondBlock->getTerminator());
784 Value *OneElt = Builder.CreateExtractElement(Vec: Src, Idx, Name: "Elt" + Twine(Idx));
785 Value *Ptr = Builder.CreateExtractElement(Vec: Ptrs, Idx, Name: "Ptr" + Twine(Idx));
786 StoreInst *Store = Builder.CreateAlignedStore(Val: OneElt, Ptr, Align: AlignVal);
787 copyMetadataForScalarizedStore(Dest&: *Store, Source: *CI, DL,
788 /*SourcePtrOperand=*/1,
789 /*ByteOffset=*/0);
790
791 // Create "else" block, fill it in the next iteration
792 BasicBlock *NewIfBlock = ThenTerm->getSuccessor(Idx: 0);
793 NewIfBlock->setName("else");
794
795 Builder.SetInsertPoint(NewIfBlock->begin());
796 }
797 CI->eraseFromParent();
798
799 ModifiedDT = true;
800}
801
802static void scalarizeMaskedExpandLoad(const DataLayout &DL,
803 bool HasBranchDivergence, CallInst *CI,
804 DomTreeUpdater *DTU, bool &ModifiedDT) {
805 Value *Ptr = CI->getArgOperand(i: 0);
806 Value *Mask = CI->getArgOperand(i: 1);
807 Value *PassThru = CI->getArgOperand(i: 2);
808 Align Alignment = CI->getParamAlign(ArgNo: 0).valueOrOne();
809
810 auto *VecType = cast<FixedVectorType>(Val: CI->getType());
811
812 Type *EltTy = VecType->getElementType();
813
814 Instruction *InsertPt = CI;
815 IRBuilder<> Builder(InsertPt);
816 Builder.disableGEPCanonicalization();
817 BasicBlock *IfBlock = CI->getParent();
818
819 unsigned VectorWidth = VecType->getNumElements();
820
821 // The result vector
822 Value *VResult = PassThru;
823
824 // Adjust alignment for the scalar instruction.
825 const Align AdjustedAlignment =
826 commonAlignment(A: Alignment, Offset: EltTy->getPrimitiveSizeInBits() / 8);
827
828 // Shorten the way if the mask is a vector of constants.
829 // Create a build_vector pattern, with loads/poisons as necessary and then
830 // shuffle blend with the pass through value.
831 if (isConstantIntVector(Mask)) {
832 unsigned MemIndex = 0;
833 VResult = PoisonValue::get(T: VecType);
834 SmallVector<int, 16> ShuffleMask(VectorWidth, PoisonMaskElem);
835 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
836 Value *InsertElt;
837 if (cast<Constant>(Val: Mask)->getAggregateElement(Elt: Idx)->isNullValue()) {
838 InsertElt = PoisonValue::get(T: EltTy);
839 ShuffleMask[Idx] = Idx + VectorWidth;
840 } else {
841 Value *NewPtr =
842 Builder.CreateConstInBoundsGEP1_32(Ty: EltTy, Ptr, Idx0: MemIndex);
843 LoadInst *Load = Builder.CreateAlignedLoad(
844 Ty: EltTy, Ptr: NewPtr, Align: AdjustedAlignment, Name: "Load" + Twine(Idx));
845 copyMetadataForScalarizedLoad(
846 Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
847 ByteOffset: MemIndex * DL.getTypeAllocSize(Ty: EltTy).getFixedValue());
848 InsertElt = Load;
849 ShuffleMask[Idx] = Idx;
850 ++MemIndex;
851 }
852 VResult = Builder.CreateInsertElement(Vec: VResult, NewElt: InsertElt, Idx,
853 Name: "Res" + Twine(Idx));
854 }
855 VResult = Builder.CreateShuffleVector(V1: VResult, V2: PassThru, Mask: ShuffleMask);
856 CI->replaceAllUsesWith(V: VResult);
857 CI->eraseFromParent();
858 return;
859 }
860
861 // If the mask is not v1i1, use scalar bit test operations. This generates
862 // better results on X86 at least. However, don't do this on GPUs or other
863 // machines with branch divergence, as there, each i1 takes up a register.
864 Value *SclrMask = nullptr;
865 if (VectorWidth != 1 && !HasBranchDivergence) {
866 Type *SclrMaskTy = Builder.getIntNTy(N: VectorWidth);
867 SclrMask = Builder.CreateBitCast(V: Mask, DestTy: SclrMaskTy, Name: "scalar_mask");
868 }
869
870 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
871 // Fill the "else" block, created in the previous iteration
872 //
873 // %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else,
874 // %else ] %mask_1 = extractelement <16 x i1> %mask, i32 Idx br i1 %mask_1,
875 // label %cond.load, label %else
876 //
877 // On GPUs, use
878 // %cond = extrectelement %mask, Idx
879 // instead
880
881 Value *Predicate;
882 if (SclrMask != nullptr) {
883 Value *Mask = Builder.getInt(AI: APInt::getOneBitSet(
884 numBits: VectorWidth, BitNo: adjustForEndian(DL, VectorWidth, Idx)));
885 Predicate = Builder.CreateICmpNE(LHS: Builder.CreateAnd(LHS: SclrMask, RHS: Mask),
886 RHS: Builder.getIntN(N: VectorWidth, C: 0));
887 } else {
888 Predicate = Builder.CreateExtractElement(Vec: Mask, Idx, Name: "Mask" + Twine(Idx));
889 }
890
891 // Create "cond" block
892 //
893 // %EltAddr = getelementptr i32* %1, i32 0
894 // %Elt = load i32* %EltAddr
895 // VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx
896 //
897 // We mark the branch weights as explicitly unknown given they would only
898 // be derivable from the mask which we do not have VP information for.
899 Instruction *ThenTerm =
900 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
901 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
902 F&: *CI->getFunction(), DEBUG_TYPE),
903 DTU);
904
905 BasicBlock *CondBlock = ThenTerm->getParent();
906 CondBlock->setName("cond.load");
907
908 Builder.SetInsertPoint(CondBlock->getTerminator());
909 LoadInst *Load = Builder.CreateAlignedLoad(Ty: EltTy, Ptr, Align: AdjustedAlignment);
910 copyMetadataForScalarizedLoad(Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
911 ByteOffset: std::nullopt);
912 Value *NewVResult = Builder.CreateInsertElement(Vec: VResult, NewElt: Load, Idx);
913
914 // Move the pointer if there are more blocks to come.
915 Value *NewPtr;
916 if ((Idx + 1) != VectorWidth)
917 NewPtr = Builder.CreateConstInBoundsGEP1_32(Ty: EltTy, Ptr, Idx0: 1);
918
919 // Create "else" block, fill it in the next iteration
920 BasicBlock *NewIfBlock = ThenTerm->getSuccessor(Idx: 0);
921 NewIfBlock->setName("else");
922 BasicBlock *PrevIfBlock = IfBlock;
923 IfBlock = NewIfBlock;
924
925 // Create the phi to join the new and previous value.
926 Builder.SetInsertPoint(NewIfBlock->begin());
927 PHINode *ResultPhi = Builder.CreatePHI(Ty: VecType, NumReservedValues: 2, Name: "res.phi.else");
928 ResultPhi->addIncoming(V: NewVResult, BB: CondBlock);
929 ResultPhi->addIncoming(V: VResult, BB: PrevIfBlock);
930 VResult = ResultPhi;
931
932 // Add a PHI for the pointer if this isn't the last iteration.
933 if ((Idx + 1) != VectorWidth) {
934 PHINode *PtrPhi = Builder.CreatePHI(Ty: Ptr->getType(), NumReservedValues: 2, Name: "ptr.phi.else");
935 PtrPhi->addIncoming(V: NewPtr, BB: CondBlock);
936 PtrPhi->addIncoming(V: Ptr, BB: PrevIfBlock);
937 Ptr = PtrPhi;
938 }
939 }
940
941 CI->replaceAllUsesWith(V: VResult);
942 CI->eraseFromParent();
943
944 ModifiedDT = true;
945}
946
947static void scalarizeMaskedCompressStore(const DataLayout &DL,
948 bool HasBranchDivergence, CallInst *CI,
949 DomTreeUpdater *DTU,
950 bool &ModifiedDT) {
951 Value *Src = CI->getArgOperand(i: 0);
952 Value *Ptr = CI->getArgOperand(i: 1);
953 Value *Mask = CI->getArgOperand(i: 2);
954 Align Alignment = CI->getParamAlign(ArgNo: 1).valueOrOne();
955
956 auto *VecType = cast<FixedVectorType>(Val: Src->getType());
957
958 Instruction *InsertPt = CI;
959 IRBuilder<> Builder(InsertPt);
960 Builder.disableGEPCanonicalization();
961 BasicBlock *IfBlock = CI->getParent();
962
963 Type *EltTy = VecType->getElementType();
964
965 // Adjust alignment for the scalar instruction.
966 const Align AdjustedAlignment =
967 commonAlignment(A: Alignment, Offset: EltTy->getPrimitiveSizeInBits() / 8);
968
969 unsigned VectorWidth = VecType->getNumElements();
970
971 // Shorten the way if the mask is a vector of constants.
972 if (isConstantIntVector(Mask)) {
973 unsigned MemIndex = 0;
974 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
975 if (cast<Constant>(Val: Mask)->getAggregateElement(Elt: Idx)->isNullValue())
976 continue;
977 Value *OneElt =
978 Builder.CreateExtractElement(Vec: Src, Idx, Name: "Elt" + Twine(Idx));
979 Value *NewPtr = Builder.CreateConstInBoundsGEP1_32(Ty: EltTy, Ptr, Idx0: MemIndex);
980 StoreInst *Store =
981 Builder.CreateAlignedStore(Val: OneElt, Ptr: NewPtr, Align: AdjustedAlignment);
982 copyMetadataForScalarizedStore(
983 Dest&: *Store, Source: *CI, DL, /*SourcePtrOperand=*/1,
984 ByteOffset: MemIndex * DL.getTypeAllocSize(Ty: EltTy).getFixedValue());
985 ++MemIndex;
986 }
987 CI->eraseFromParent();
988 return;
989 }
990
991 // If the mask is not v1i1, use scalar bit test operations. This generates
992 // better results on X86 at least. However, don't do this on GPUs or other
993 // machines with branch divergence, as there, each i1 takes up a register.
994 Value *SclrMask = nullptr;
995 if (VectorWidth != 1 && !HasBranchDivergence) {
996 Type *SclrMaskTy = Builder.getIntNTy(N: VectorWidth);
997 SclrMask = Builder.CreateBitCast(V: Mask, DestTy: SclrMaskTy, Name: "scalar_mask");
998 }
999
1000 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
1001 // Fill the "else" block, created in the previous iteration
1002 //
1003 // %mask_1 = extractelement <16 x i1> %mask, i32 Idx
1004 // br i1 %mask_1, label %cond.store, label %else
1005 //
1006 // On GPUs, use
1007 // %cond = extrectelement %mask, Idx
1008 // instead
1009 Value *Predicate;
1010 if (SclrMask != nullptr) {
1011 Value *Mask = Builder.getInt(AI: APInt::getOneBitSet(
1012 numBits: VectorWidth, BitNo: adjustForEndian(DL, VectorWidth, Idx)));
1013 Predicate = Builder.CreateICmpNE(LHS: Builder.CreateAnd(LHS: SclrMask, RHS: Mask),
1014 RHS: Builder.getIntN(N: VectorWidth, C: 0));
1015 } else {
1016 Predicate = Builder.CreateExtractElement(Vec: Mask, Idx, Name: "Mask" + Twine(Idx));
1017 }
1018
1019 // Create "cond" block
1020 //
1021 // %OneElt = extractelement <16 x i32> %Src, i32 Idx
1022 // %EltAddr = getelementptr i32* %1, i32 0
1023 // %store i32 %OneElt, i32* %EltAddr
1024 //
1025 // We mark the branch weights as explicitly unknown given they would only
1026 // be derivable from the mask which we do not have VP information for.
1027 Instruction *ThenTerm =
1028 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
1029 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
1030 F&: *CI->getFunction(), DEBUG_TYPE),
1031 DTU);
1032
1033 BasicBlock *CondBlock = ThenTerm->getParent();
1034 CondBlock->setName("cond.store");
1035
1036 Builder.SetInsertPoint(CondBlock->getTerminator());
1037 Value *OneElt = Builder.CreateExtractElement(Vec: Src, Idx);
1038 StoreInst *Store =
1039 Builder.CreateAlignedStore(Val: OneElt, Ptr, Align: AdjustedAlignment);
1040 copyMetadataForScalarizedStore(Dest&: *Store, Source: *CI, DL, /*SourcePtrOperand=*/1,
1041 ByteOffset: std::nullopt);
1042
1043 // Move the pointer if there are more blocks to come.
1044 Value *NewPtr;
1045 if ((Idx + 1) != VectorWidth)
1046 NewPtr = Builder.CreateConstInBoundsGEP1_32(Ty: EltTy, Ptr, Idx0: 1);
1047
1048 // Create "else" block, fill it in the next iteration
1049 BasicBlock *NewIfBlock = ThenTerm->getSuccessor(Idx: 0);
1050 NewIfBlock->setName("else");
1051 BasicBlock *PrevIfBlock = IfBlock;
1052 IfBlock = NewIfBlock;
1053
1054 Builder.SetInsertPoint(NewIfBlock->begin());
1055
1056 // Add a PHI for the pointer if this isn't the last iteration.
1057 if ((Idx + 1) != VectorWidth) {
1058 PHINode *PtrPhi = Builder.CreatePHI(Ty: Ptr->getType(), NumReservedValues: 2, Name: "ptr.phi.else");
1059 PtrPhi->addIncoming(V: NewPtr, BB: CondBlock);
1060 PtrPhi->addIncoming(V: Ptr, BB: PrevIfBlock);
1061 Ptr = PtrPhi;
1062 }
1063 }
1064 CI->eraseFromParent();
1065
1066 ModifiedDT = true;
1067}
1068
1069static void scalarizeMaskedVectorHistogram(const DataLayout &DL, CallInst *CI,
1070 DomTreeUpdater *DTU,
1071 bool &ModifiedDT) {
1072 // If we extend histogram to return a result someday (like the updated vector)
1073 // then we'll need to support it here.
1074 assert(CI->getType()->isVoidTy() && "Histogram with non-void return.");
1075 Value *Ptrs = CI->getArgOperand(i: 0);
1076 Value *Inc = CI->getArgOperand(i: 1);
1077 Value *Mask = CI->getArgOperand(i: 2);
1078
1079 auto *AddrType = cast<FixedVectorType>(Val: Ptrs->getType());
1080 Type *EltTy = Inc->getType();
1081
1082 Instruction *InsertPt = CI;
1083 IRBuilder<> Builder(InsertPt);
1084
1085 // FIXME: Do we need to add an alignment parameter to the intrinsic?
1086 unsigned VectorWidth = AddrType->getNumElements();
1087 auto CreateHistogramUpdateValue = [&](IntrinsicInst *CI, Value *Load,
1088 Value *Inc) -> Value * {
1089 Value *UpdateOp;
1090 switch (CI->getIntrinsicID()) {
1091 case Intrinsic::experimental_vector_histogram_add:
1092 UpdateOp = Builder.CreateAdd(LHS: Load, RHS: Inc);
1093 break;
1094 case Intrinsic::experimental_vector_histogram_uadd_sat:
1095 UpdateOp =
1096 Builder.CreateIntrinsic(ID: Intrinsic::uadd_sat, OverloadTypes: {EltTy}, Args: {Load, Inc});
1097 break;
1098 case Intrinsic::experimental_vector_histogram_umin:
1099 UpdateOp = Builder.CreateIntrinsic(ID: Intrinsic::umin, OverloadTypes: {EltTy}, Args: {Load, Inc});
1100 break;
1101 case Intrinsic::experimental_vector_histogram_umax:
1102 UpdateOp = Builder.CreateIntrinsic(ID: Intrinsic::umax, OverloadTypes: {EltTy}, Args: {Load, Inc});
1103 break;
1104
1105 default:
1106 llvm_unreachable("Unexpected histogram intrinsic");
1107 }
1108 return UpdateOp;
1109 };
1110
1111 // Shorten the way if the mask is a vector of constants.
1112 if (isConstantIntVector(Mask)) {
1113 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
1114 if (cast<Constant>(Val: Mask)->getAggregateElement(Elt: Idx)->isNullValue())
1115 continue;
1116 Value *Ptr = Builder.CreateExtractElement(Vec: Ptrs, Idx, Name: "Ptr" + Twine(Idx));
1117 LoadInst *Load = Builder.CreateLoad(Ty: EltTy, Ptr, Name: "Load" + Twine(Idx));
1118 copyMetadataForScalarizedLoad(Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
1119 /*ByteOffset=*/0);
1120 Value *Update =
1121 CreateHistogramUpdateValue(cast<IntrinsicInst>(Val: CI), Load, Inc);
1122 StoreInst *Store = Builder.CreateStore(Val: Update, Ptr);
1123 copyMetadataForScalarizedStore(Dest&: *Store, Source: *CI, DL,
1124 /*SourcePtrOperand=*/0,
1125 /*ByteOffset=*/0);
1126 }
1127 CI->eraseFromParent();
1128 return;
1129 }
1130
1131 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
1132 Value *Predicate =
1133 Builder.CreateExtractElement(Vec: Mask, Idx, Name: "Mask" + Twine(Idx));
1134
1135 // We mark the branch weights as explicitly unknown given they would only
1136 // be derivable from the mask which we do not have VP information for.
1137 Instruction *ThenTerm =
1138 SplitBlockAndInsertIfThen(Cond: Predicate, SplitBefore: InsertPt, /*Unreachable=*/false,
1139 BranchWeights: getExplicitlyUnknownBranchWeightsIfProfiled(
1140 F&: *CI->getFunction(), DEBUG_TYPE),
1141 DTU);
1142
1143 BasicBlock *CondBlock = ThenTerm->getParent();
1144 CondBlock->setName("cond.histogram.update");
1145
1146 Builder.SetInsertPoint(CondBlock->getTerminator());
1147 Value *Ptr = Builder.CreateExtractElement(Vec: Ptrs, Idx, Name: "Ptr" + Twine(Idx));
1148 LoadInst *Load = Builder.CreateLoad(Ty: EltTy, Ptr, Name: "Load" + Twine(Idx));
1149 copyMetadataForScalarizedLoad(Dest&: *Load, Source: *CI, DL, /*SourcePtrOperand=*/0,
1150 /*ByteOffset=*/0);
1151 Value *UpdateOp =
1152 CreateHistogramUpdateValue(cast<IntrinsicInst>(Val: CI), Load, Inc);
1153 StoreInst *Store = Builder.CreateStore(Val: UpdateOp, Ptr);
1154 copyMetadataForScalarizedStore(Dest&: *Store, Source: *CI, DL,
1155 /*SourcePtrOperand=*/0,
1156 /*ByteOffset=*/0);
1157
1158 // Create "else" block, fill it in the next iteration
1159 BasicBlock *NewIfBlock = ThenTerm->getSuccessor(Idx: 0);
1160 NewIfBlock->setName("else");
1161 Builder.SetInsertPoint(NewIfBlock->begin());
1162 }
1163
1164 CI->eraseFromParent();
1165 ModifiedDT = true;
1166}
1167
1168static bool runImpl(Function &F, const TargetTransformInfo &TTI,
1169 DominatorTree *DT) {
1170 std::optional<DomTreeUpdater> DTU;
1171 if (DT)
1172 DTU.emplace(args&: DT, args: DomTreeUpdater::UpdateStrategy::Lazy);
1173
1174 bool EverMadeChange = false;
1175 bool MadeChange = true;
1176 auto &DL = F.getDataLayout();
1177 bool HasBranchDivergence = TTI.hasBranchDivergence(F: &F);
1178 while (MadeChange) {
1179 MadeChange = false;
1180 for (BasicBlock &BB : llvm::make_early_inc_range(Range&: F)) {
1181 bool ModifiedDTOnIteration = false;
1182 MadeChange |= optimizeBlock(BB, ModifiedDT&: ModifiedDTOnIteration, TTI, DL,
1183 HasBranchDivergence, DTU: DTU ? &*DTU : nullptr);
1184
1185 // Restart BB iteration if the dominator tree of the Function was changed
1186 if (ModifiedDTOnIteration)
1187 break;
1188 }
1189
1190 EverMadeChange |= MadeChange;
1191 }
1192 return EverMadeChange;
1193}
1194
1195bool ScalarizeMaskedMemIntrinLegacyPass::runOnFunction(Function &F) {
1196 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1197 DominatorTree *DT = nullptr;
1198 if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
1199 DT = &DTWP->getDomTree();
1200 return runImpl(F, TTI, DT);
1201}
1202
1203PreservedAnalyses
1204ScalarizeMaskedMemIntrinPass::run(Function &F, FunctionAnalysisManager &AM) {
1205 auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
1206 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
1207 if (!runImpl(F, TTI, DT))
1208 return PreservedAnalyses::all();
1209 PreservedAnalyses PA;
1210 PA.preserve<TargetIRAnalysis>();
1211 PA.preserve<DominatorTreeAnalysis>();
1212 return PA;
1213}
1214
1215static bool optimizeBlock(BasicBlock &BB, bool &ModifiedDT,
1216 const TargetTransformInfo &TTI, const DataLayout &DL,
1217 bool HasBranchDivergence, DomTreeUpdater *DTU) {
1218 bool MadeChange = false;
1219
1220 BasicBlock::iterator CurInstIterator = BB.begin();
1221 while (CurInstIterator != BB.end()) {
1222 if (CallInst *CI = dyn_cast<CallInst>(Val: &*CurInstIterator++))
1223 MadeChange |=
1224 optimizeCallInst(CI, ModifiedDT, TTI, DL, HasBranchDivergence, DTU);
1225 if (ModifiedDT)
1226 return true;
1227 }
1228
1229 return MadeChange;
1230}
1231
1232static bool optimizeCallInst(CallInst *CI, bool &ModifiedDT,
1233 const TargetTransformInfo &TTI,
1234 const DataLayout &DL, bool HasBranchDivergence,
1235 DomTreeUpdater *DTU) {
1236 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: CI);
1237 if (II) {
1238 // The scalarization code below does not work for scalable vectors.
1239 if (isa<ScalableVectorType>(Val: II->getType()) ||
1240 any_of(Range: II->args(),
1241 P: [](Value *V) { return isa<ScalableVectorType>(Val: V->getType()); }))
1242 return false;
1243 switch (II->getIntrinsicID()) {
1244 default:
1245 break;
1246 case Intrinsic::experimental_vector_histogram_add:
1247 case Intrinsic::experimental_vector_histogram_uadd_sat:
1248 case Intrinsic::experimental_vector_histogram_umin:
1249 case Intrinsic::experimental_vector_histogram_umax:
1250 if (TTI.isLegalMaskedVectorHistogram(AddrType: CI->getArgOperand(i: 0)->getType(),
1251 DataType: CI->getArgOperand(i: 1)->getType()))
1252 return false;
1253 scalarizeMaskedVectorHistogram(DL, CI, DTU, ModifiedDT);
1254 return true;
1255 case Intrinsic::masked_load:
1256 // Scalarize unsupported vector masked load
1257 if (TTI.isLegalMaskedLoad(
1258 DataType: CI->getType(), Alignment: CI->getParamAlign(ArgNo: 0).valueOrOne(),
1259 AddressSpace: cast<PointerType>(Val: CI->getArgOperand(i: 0)->getType())
1260 ->getAddressSpace(),
1261 MaskKind: isConstantIntVector(Mask: CI->getArgOperand(i: 1))
1262 ? TTI::MaskKind::ConstantMask
1263 : TTI::MaskKind::VariableOrConstantMask))
1264 return false;
1265 scalarizeMaskedLoad(DL, HasBranchDivergence, CI, DTU, ModifiedDT);
1266 return true;
1267 case Intrinsic::masked_store:
1268 if (TTI.isLegalMaskedStore(
1269 DataType: CI->getArgOperand(i: 0)->getType(),
1270 Alignment: CI->getParamAlign(ArgNo: 1).valueOrOne(),
1271 AddressSpace: cast<PointerType>(Val: CI->getArgOperand(i: 1)->getType())
1272 ->getAddressSpace(),
1273 MaskKind: isConstantIntVector(Mask: CI->getArgOperand(i: 2))
1274 ? TTI::MaskKind::ConstantMask
1275 : TTI::MaskKind::VariableOrConstantMask))
1276 return false;
1277 scalarizeMaskedStore(DL, HasBranchDivergence, CI, DTU, ModifiedDT);
1278 return true;
1279 case Intrinsic::masked_gather: {
1280 Align Alignment = CI->getParamAlign(ArgNo: 0).valueOrOne();
1281 Type *LoadTy = CI->getType();
1282 if (TTI.isLegalMaskedGather(DataType: LoadTy, Alignment) &&
1283 !TTI.forceScalarizeMaskedGather(Type: cast<VectorType>(Val: LoadTy), Alignment))
1284 return false;
1285 scalarizeMaskedGather(DL, HasBranchDivergence, CI, DTU, ModifiedDT);
1286 return true;
1287 }
1288 case Intrinsic::masked_scatter: {
1289 Align Alignment = CI->getParamAlign(ArgNo: 1).valueOrOne();
1290 Type *StoreTy = CI->getArgOperand(i: 0)->getType();
1291 if (TTI.isLegalMaskedScatter(DataType: StoreTy, Alignment) &&
1292 !TTI.forceScalarizeMaskedScatter(Type: cast<VectorType>(Val: StoreTy),
1293 Alignment))
1294 return false;
1295 scalarizeMaskedScatter(DL, HasBranchDivergence, CI, DTU, ModifiedDT);
1296 return true;
1297 }
1298 case Intrinsic::masked_expandload:
1299 if (TTI.isLegalMaskedExpandLoad(
1300 DataType: CI->getType(),
1301 Alignment: CI->getAttributes().getParamAttrs(ArgNo: 0).getAlignment().valueOrOne()))
1302 return false;
1303 scalarizeMaskedExpandLoad(DL, HasBranchDivergence, CI, DTU, ModifiedDT);
1304 return true;
1305 case Intrinsic::masked_compressstore:
1306 if (TTI.isLegalMaskedCompressStore(
1307 DataType: CI->getArgOperand(i: 0)->getType(),
1308 Alignment: CI->getAttributes().getParamAttrs(ArgNo: 1).getAlignment().valueOrOne()))
1309 return false;
1310 scalarizeMaskedCompressStore(DL, HasBranchDivergence, CI, DTU,
1311 ModifiedDT);
1312 return true;
1313 }
1314 }
1315
1316 return false;
1317}
1318