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