LLVM 19.0.0git
SVEIntrinsicOpts.cpp
Go to the documentation of this file.
1//===----- SVEIntrinsicOpts - SVE ACLE Intrinsics Opts --------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Performs general IR level optimizations on SVE intrinsics.
10//
11// This pass performs the following optimizations:
12//
13// - removes unnecessary ptrue intrinsics (llvm.aarch64.sve.ptrue), e.g:
14// %1 = @llvm.aarch64.sve.ptrue.nxv4i1(i32 31)
15// %2 = @llvm.aarch64.sve.ptrue.nxv8i1(i32 31)
16// ; (%1 can be replaced with a reinterpret of %2)
17//
18// - optimizes ptest intrinsics where the operands are being needlessly
19// converted to and from svbool_t.
20//
21//===----------------------------------------------------------------------===//
22
23#include "AArch64.h"
26#include "llvm/ADT/SetVector.h"
27#include "llvm/IR/Constants.h"
28#include "llvm/IR/Dominators.h"
29#include "llvm/IR/IRBuilder.h"
32#include "llvm/IR/IntrinsicsAArch64.h"
33#include "llvm/IR/LLVMContext.h"
36#include "llvm/Support/Debug.h"
37#include <optional>
38
39using namespace llvm;
40using namespace llvm::PatternMatch;
41
42#define DEBUG_TYPE "aarch64-sve-intrinsic-opts"
43
44namespace {
45struct SVEIntrinsicOpts : public ModulePass {
46 static char ID; // Pass identification, replacement for typeid
47 SVEIntrinsicOpts() : ModulePass(ID) {
49 }
50
51 bool runOnModule(Module &M) override;
52 void getAnalysisUsage(AnalysisUsage &AU) const override;
53
54private:
55 bool coalescePTrueIntrinsicCalls(BasicBlock &BB,
57 bool optimizePTrueIntrinsicCalls(SmallSetVector<Function *, 4> &Functions);
58 bool optimizePredicateStore(Instruction *I);
59 bool optimizePredicateLoad(Instruction *I);
60
61 bool optimizeInstructions(SmallSetVector<Function *, 4> &Functions);
62
63 /// Operates at the function-scope. I.e., optimizations are applied local to
64 /// the functions themselves.
65 bool optimizeFunctions(SmallSetVector<Function *, 4> &Functions);
66};
67} // end anonymous namespace
68
69void SVEIntrinsicOpts::getAnalysisUsage(AnalysisUsage &AU) const {
71 AU.setPreservesCFG();
72}
73
74char SVEIntrinsicOpts::ID = 0;
75static const char *name = "SVE intrinsics optimizations";
76INITIALIZE_PASS_BEGIN(SVEIntrinsicOpts, DEBUG_TYPE, name, false, false)
78INITIALIZE_PASS_END(SVEIntrinsicOpts, DEBUG_TYPE, name, false, false)
79
81 return new SVEIntrinsicOpts();
82}
83
84/// Checks if a ptrue intrinsic call is promoted. The act of promoting a
85/// ptrue will introduce zeroing. For example:
86///
87/// %1 = <vscale x 4 x i1> call @llvm.aarch64.sve.ptrue.nxv4i1(i32 31)
88/// %2 = <vscale x 16 x i1> call @llvm.aarch64.sve.convert.to.svbool.nxv4i1(<vscale x 4 x i1> %1)
89/// %3 = <vscale x 8 x i1> call @llvm.aarch64.sve.convert.from.svbool.nxv8i1(<vscale x 16 x i1> %2)
90///
91/// %1 is promoted, because it is converted:
92///
93/// <vscale x 4 x i1> => <vscale x 16 x i1> => <vscale x 8 x i1>
94///
95/// via a sequence of the SVE reinterpret intrinsics convert.{to,from}.svbool.
96static bool isPTruePromoted(IntrinsicInst *PTrue) {
97 // Find all users of this intrinsic that are calls to convert-to-svbool
98 // reinterpret intrinsics.
100 for (User *User : PTrue->users()) {
101 if (match(User, m_Intrinsic<Intrinsic::aarch64_sve_convert_to_svbool>())) {
102 ConvertToUses.push_back(cast<IntrinsicInst>(User));
103 }
104 }
105
106 // If no such calls were found, this is ptrue is not promoted.
107 if (ConvertToUses.empty())
108 return false;
109
110 // Otherwise, try to find users of the convert-to-svbool intrinsics that are
111 // calls to the convert-from-svbool intrinsic, and would result in some lanes
112 // being zeroed.
113 const auto *PTrueVTy = cast<ScalableVectorType>(PTrue->getType());
114 for (IntrinsicInst *ConvertToUse : ConvertToUses) {
115 for (User *User : ConvertToUse->users()) {
116 auto *IntrUser = dyn_cast<IntrinsicInst>(User);
117 if (IntrUser && IntrUser->getIntrinsicID() ==
118 Intrinsic::aarch64_sve_convert_from_svbool) {
119 const auto *IntrUserVTy = cast<ScalableVectorType>(IntrUser->getType());
120
121 // Would some lanes become zeroed by the conversion?
122 if (IntrUserVTy->getElementCount().getKnownMinValue() >
123 PTrueVTy->getElementCount().getKnownMinValue())
124 // This is a promoted ptrue.
125 return true;
126 }
127 }
128 }
129
130 // If no matching calls were found, this is not a promoted ptrue.
131 return false;
132}
133
134/// Attempts to coalesce ptrues in a basic block.
135bool SVEIntrinsicOpts::coalescePTrueIntrinsicCalls(
137 if (PTrues.size() <= 1)
138 return false;
139
140 // Find the ptrue with the most lanes.
141 auto *MostEncompassingPTrue =
142 *llvm::max_element(PTrues, [](auto *PTrue1, auto *PTrue2) {
143 auto *PTrue1VTy = cast<ScalableVectorType>(PTrue1->getType());
144 auto *PTrue2VTy = cast<ScalableVectorType>(PTrue2->getType());
145 return PTrue1VTy->getElementCount().getKnownMinValue() <
146 PTrue2VTy->getElementCount().getKnownMinValue();
147 });
148
149 // Remove the most encompassing ptrue, as well as any promoted ptrues, leaving
150 // behind only the ptrues to be coalesced.
151 PTrues.remove(MostEncompassingPTrue);
153
154 // Hoist MostEncompassingPTrue to the start of the basic block. It is always
155 // safe to do this, since ptrue intrinsic calls are guaranteed to have no
156 // predecessors.
157 MostEncompassingPTrue->moveBefore(BB, BB.getFirstInsertionPt());
158
159 LLVMContext &Ctx = BB.getContext();
160 IRBuilder<> Builder(Ctx);
161 Builder.SetInsertPoint(&BB, ++MostEncompassingPTrue->getIterator());
162
163 auto *MostEncompassingPTrueVTy =
164 cast<VectorType>(MostEncompassingPTrue->getType());
165 auto *ConvertToSVBool = Builder.CreateIntrinsic(
166 Intrinsic::aarch64_sve_convert_to_svbool, {MostEncompassingPTrueVTy},
167 {MostEncompassingPTrue});
168
169 bool ConvertFromCreated = false;
170 for (auto *PTrue : PTrues) {
171 auto *PTrueVTy = cast<VectorType>(PTrue->getType());
172
173 // Only create the converts if the types are not already the same, otherwise
174 // just use the most encompassing ptrue.
175 if (MostEncompassingPTrueVTy != PTrueVTy) {
176 ConvertFromCreated = true;
177
178 Builder.SetInsertPoint(&BB, ++ConvertToSVBool->getIterator());
179 auto *ConvertFromSVBool =
180 Builder.CreateIntrinsic(Intrinsic::aarch64_sve_convert_from_svbool,
181 {PTrueVTy}, {ConvertToSVBool});
182 PTrue->replaceAllUsesWith(ConvertFromSVBool);
183 } else
184 PTrue->replaceAllUsesWith(MostEncompassingPTrue);
185
186 PTrue->eraseFromParent();
187 }
188
189 // We never used the ConvertTo so remove it
190 if (!ConvertFromCreated)
191 ConvertToSVBool->eraseFromParent();
192
193 return true;
194}
195
196/// The goal of this function is to remove redundant calls to the SVE ptrue
197/// intrinsic in each basic block within the given functions.
198///
199/// SVE ptrues have two representations in LLVM IR:
200/// - a logical representation -- an arbitrary-width scalable vector of i1s,
201/// i.e. <vscale x N x i1>.
202/// - a physical representation (svbool, <vscale x 16 x i1>) -- a 16-element
203/// scalable vector of i1s, i.e. <vscale x 16 x i1>.
204///
205/// The SVE ptrue intrinsic is used to create a logical representation of an SVE
206/// predicate. Suppose that we have two SVE ptrue intrinsic calls: P1 and P2. If
207/// P1 creates a logical SVE predicate that is at least as wide as the logical
208/// SVE predicate created by P2, then all of the bits that are true in the
209/// physical representation of P2 are necessarily also true in the physical
210/// representation of P1. P1 'encompasses' P2, therefore, the intrinsic call to
211/// P2 is redundant and can be replaced by an SVE reinterpret of P1 via
212/// convert.{to,from}.svbool.
213///
214/// Currently, this pass only coalesces calls to SVE ptrue intrinsics
215/// if they match the following conditions:
216///
217/// - the call to the intrinsic uses either the SV_ALL or SV_POW2 patterns.
218/// SV_ALL indicates that all bits of the predicate vector are to be set to
219/// true. SV_POW2 indicates that all bits of the predicate vector up to the
220/// largest power-of-two are to be set to true.
221/// - the result of the call to the intrinsic is not promoted to a wider
222/// predicate. In this case, keeping the extra ptrue leads to better codegen
223/// -- coalescing here would create an irreducible chain of SVE reinterprets
224/// via convert.{to,from}.svbool.
225///
226/// EXAMPLE:
227///
228/// %1 = <vscale x 8 x i1> ptrue(i32 SV_ALL)
229/// ; Logical: <1, 1, 1, 1, 1, 1, 1, 1>
230/// ; Physical: <1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0>
231/// ...
232///
233/// %2 = <vscale x 4 x i1> ptrue(i32 SV_ALL)
234/// ; Logical: <1, 1, 1, 1>
235/// ; Physical: <1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0>
236/// ...
237///
238/// Here, %2 can be replaced by an SVE reinterpret of %1, giving, for instance:
239///
240/// %1 = <vscale x 8 x i1> ptrue(i32 i31)
241/// %2 = <vscale x 16 x i1> convert.to.svbool(<vscale x 8 x i1> %1)
242/// %3 = <vscale x 4 x i1> convert.from.svbool(<vscale x 16 x i1> %2)
243///
244bool SVEIntrinsicOpts::optimizePTrueIntrinsicCalls(
246 bool Changed = false;
247
248 for (auto *F : Functions) {
249 for (auto &BB : *F) {
252
253 // For each basic block, collect the used ptrues and try to coalesce them.
254 for (Instruction &I : BB) {
255 if (I.use_empty())
256 continue;
257
258 auto *IntrI = dyn_cast<IntrinsicInst>(&I);
259 if (!IntrI || IntrI->getIntrinsicID() != Intrinsic::aarch64_sve_ptrue)
260 continue;
261
262 const auto PTruePattern =
263 cast<ConstantInt>(IntrI->getOperand(0))->getZExtValue();
264
265 if (PTruePattern == AArch64SVEPredPattern::all)
266 SVAllPTrues.insert(IntrI);
267 if (PTruePattern == AArch64SVEPredPattern::pow2)
268 SVPow2PTrues.insert(IntrI);
269 }
270
271 Changed |= coalescePTrueIntrinsicCalls(BB, SVAllPTrues);
272 Changed |= coalescePTrueIntrinsicCalls(BB, SVPow2PTrues);
273 }
274 }
275
276 return Changed;
277}
278
279// This is done in SVEIntrinsicOpts rather than InstCombine so that we introduce
280// scalable stores as late as possible
281bool SVEIntrinsicOpts::optimizePredicateStore(Instruction *I) {
282 auto *F = I->getFunction();
283 auto Attr = F->getFnAttribute(Attribute::VScaleRange);
284 if (!Attr.isValid())
285 return false;
286
287 unsigned MinVScale = Attr.getVScaleRangeMin();
288 std::optional<unsigned> MaxVScale = Attr.getVScaleRangeMax();
289 // The transform needs to know the exact runtime length of scalable vectors
290 if (!MaxVScale || MinVScale != MaxVScale)
291 return false;
292
293 auto *PredType =
294 ScalableVectorType::get(Type::getInt1Ty(I->getContext()), 16);
295 auto *FixedPredType =
296 FixedVectorType::get(Type::getInt8Ty(I->getContext()), MinVScale * 2);
297
298 // If we have a store..
299 auto *Store = dyn_cast<StoreInst>(I);
300 if (!Store || !Store->isSimple())
301 return false;
302
303 // ..that is storing a predicate vector sized worth of bits..
304 if (Store->getOperand(0)->getType() != FixedPredType)
305 return false;
306
307 // ..where the value stored comes from a vector extract..
308 auto *IntrI = dyn_cast<IntrinsicInst>(Store->getOperand(0));
309 if (!IntrI || IntrI->getIntrinsicID() != Intrinsic::vector_extract)
310 return false;
311
312 // ..that is extracting from index 0..
313 if (!cast<ConstantInt>(IntrI->getOperand(1))->isZero())
314 return false;
315
316 // ..where the value being extract from comes from a bitcast
317 auto *BitCast = dyn_cast<BitCastInst>(IntrI->getOperand(0));
318 if (!BitCast)
319 return false;
320
321 // ..and the bitcast is casting from predicate type
322 if (BitCast->getOperand(0)->getType() != PredType)
323 return false;
324
325 IRBuilder<> Builder(I->getContext());
326 Builder.SetInsertPoint(I);
327
328 Builder.CreateStore(BitCast->getOperand(0), Store->getPointerOperand());
329
330 Store->eraseFromParent();
331 if (IntrI->getNumUses() == 0)
332 IntrI->eraseFromParent();
333 if (BitCast->getNumUses() == 0)
334 BitCast->eraseFromParent();
335
336 return true;
337}
338
339// This is done in SVEIntrinsicOpts rather than InstCombine so that we introduce
340// scalable loads as late as possible
341bool SVEIntrinsicOpts::optimizePredicateLoad(Instruction *I) {
342 auto *F = I->getFunction();
343 auto Attr = F->getFnAttribute(Attribute::VScaleRange);
344 if (!Attr.isValid())
345 return false;
346
347 unsigned MinVScale = Attr.getVScaleRangeMin();
348 std::optional<unsigned> MaxVScale = Attr.getVScaleRangeMax();
349 // The transform needs to know the exact runtime length of scalable vectors
350 if (!MaxVScale || MinVScale != MaxVScale)
351 return false;
352
353 auto *PredType =
354 ScalableVectorType::get(Type::getInt1Ty(I->getContext()), 16);
355 auto *FixedPredType =
356 FixedVectorType::get(Type::getInt8Ty(I->getContext()), MinVScale * 2);
357
358 // If we have a bitcast..
359 auto *BitCast = dyn_cast<BitCastInst>(I);
360 if (!BitCast || BitCast->getType() != PredType)
361 return false;
362
363 // ..whose operand is a vector_insert..
364 auto *IntrI = dyn_cast<IntrinsicInst>(BitCast->getOperand(0));
365 if (!IntrI || IntrI->getIntrinsicID() != Intrinsic::vector_insert)
366 return false;
367
368 // ..that is inserting into index zero of an undef vector..
369 if (!isa<UndefValue>(IntrI->getOperand(0)) ||
370 !cast<ConstantInt>(IntrI->getOperand(2))->isZero())
371 return false;
372
373 // ..where the value inserted comes from a load..
374 auto *Load = dyn_cast<LoadInst>(IntrI->getOperand(1));
375 if (!Load || !Load->isSimple())
376 return false;
377
378 // ..that is loading a predicate vector sized worth of bits..
379 if (Load->getType() != FixedPredType)
380 return false;
381
382 IRBuilder<> Builder(I->getContext());
383 Builder.SetInsertPoint(Load);
384
385 auto *LoadPred = Builder.CreateLoad(PredType, Load->getPointerOperand());
386
387 BitCast->replaceAllUsesWith(LoadPred);
388 BitCast->eraseFromParent();
389 if (IntrI->getNumUses() == 0)
390 IntrI->eraseFromParent();
391 if (Load->getNumUses() == 0)
392 Load->eraseFromParent();
393
394 return true;
395}
396
397bool SVEIntrinsicOpts::optimizeInstructions(
399 bool Changed = false;
400
401 for (auto *F : Functions) {
402 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>(*F).getDomTree();
403
404 // Traverse the DT with an rpo walk so we see defs before uses, allowing
405 // simplification to be done incrementally.
406 BasicBlock *Root = DT->getRoot();
408 for (auto *BB : RPOT) {
409 for (Instruction &I : make_early_inc_range(*BB)) {
410 switch (I.getOpcode()) {
411 case Instruction::Store:
412 Changed |= optimizePredicateStore(&I);
413 break;
414 case Instruction::BitCast:
415 Changed |= optimizePredicateLoad(&I);
416 break;
417 }
418 }
419 }
420 }
421
422 return Changed;
423}
424
425bool SVEIntrinsicOpts::optimizeFunctions(
427 bool Changed = false;
428
429 Changed |= optimizePTrueIntrinsicCalls(Functions);
430 Changed |= optimizeInstructions(Functions);
431
432 return Changed;
433}
434
435bool SVEIntrinsicOpts::runOnModule(Module &M) {
436 bool Changed = false;
438
439 // Check for SVE intrinsic declarations first so that we only iterate over
440 // relevant functions. Where an appropriate declaration is found, store the
441 // function(s) where it is used so we can target these only.
442 for (auto &F : M.getFunctionList()) {
443 if (!F.isDeclaration())
444 continue;
445
446 switch (F.getIntrinsicID()) {
447 case Intrinsic::vector_extract:
448 case Intrinsic::vector_insert:
449 case Intrinsic::aarch64_sve_ptrue:
450 for (User *U : F.users())
451 Functions.insert(cast<Instruction>(U)->getFunction());
452 break;
453 default:
454 break;
455 }
456 }
457
458 if (!Functions.empty())
459 Changed |= optimizeFunctions(Functions);
460
461 return Changed;
462}
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:236
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
static const char * name
static bool isPTruePromoted(IntrinsicInst *PTrue)
Checks if a ptrue intrinsic call is promoted.
#define DEBUG_TYPE
This file implements a set that has insertion order iteration characteristics.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:398
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:157
NodeT * getRoot() const
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition: Type.cpp:692
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2644
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:251
virtual bool runOnModule(Module &M)=0
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
static ScalableVectorType * get(Type *ElementType, unsigned MinNumElts)
Definition: Type.cpp:713
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:188
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
Definition: SetVector.h:237
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
static IntegerType * getInt1Ty(LLVMContext &C)
static IntegerType * getInt8Ty(LLVMContext &C)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
iterator_range< user_iterator > users()
Definition: Value.h:421
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
ModulePass * createSVEIntrinsicOptsPass()
auto max_element(R &&Range)
Definition: STLExtras.h:1995
void initializeSVEIntrinsicOptsPass(PassRegistry &)