24#include "llvm/IR/IntrinsicsRISCV.h"
30using namespace PatternMatch;
32#define DEBUG_TYPE "riscv-gather-scatter-lowering"
63 return "RISC-V gather/scatter lowering";
70 std::pair<Value *, Value *> determineBaseAndStride(
Instruction *
Ptr,
80char RISCVGatherScatterLowering::ID = 0;
83 "RISC-V gather/scatter lowering pass",
false,
false)
86 return new RISCVGatherScatterLowering();
91 if (!isa<FixedVectorType>(StartC->
getType()))
92 return std::make_pair(
nullptr,
nullptr);
94 unsigned NumElts = cast<FixedVectorType>(StartC->
getType())->getNumElements();
100 return std::make_pair(
nullptr,
nullptr);
101 APInt StrideVal(StartVal->getValue().getBitWidth(), 0);
103 for (
unsigned i = 1; i != NumElts; ++i) {
106 return std::make_pair(
nullptr,
nullptr);
110 StrideVal = LocalStride;
111 else if (StrideVal != LocalStride)
112 return std::make_pair(
nullptr,
nullptr);
117 Value *Stride = ConstantInt::get(StartVal->getType(), StrideVal);
119 return std::make_pair(StartVal, Stride);
125 auto *StartC = dyn_cast<Constant>(Start);
130 if (
match(Start, m_Intrinsic<Intrinsic::experimental_stepvector>())) {
131 auto *Ty = Start->getType()->getScalarType();
132 return std::make_pair(ConstantInt::get(Ty, 0), ConstantInt::get(Ty, 1));
137 auto *BO = dyn_cast<BinaryOperator>(Start);
138 if (!BO || (BO->getOpcode() != Instruction::Add &&
139 BO->getOpcode() != Instruction::Or &&
140 BO->getOpcode() != Instruction::Shl &&
141 BO->getOpcode() != Instruction::Mul))
142 return std::make_pair(
nullptr,
nullptr);
144 if (BO->getOpcode() == Instruction::Or &&
145 !cast<PossiblyDisjointInst>(BO)->isDisjoint())
146 return std::make_pair(
nullptr,
nullptr);
149 unsigned OtherIndex = 0;
156 return std::make_pair(
nullptr,
nullptr);
162 return std::make_pair(
nullptr,
nullptr);
168 switch (BO->getOpcode()) {
171 case Instruction::Or:
175 case Instruction::Add:
178 case Instruction::Mul:
182 case Instruction::Shl:
188 return std::make_pair(Start, Stride);
195bool RISCVGatherScatterLowering::matchStridedRecurrence(
Value *
Index,
Loop *L,
201 if (
auto *Phi = dyn_cast<PHINode>(
Index)) {
204 if (
Phi->getParent() !=
L->getHeader())
211 assert(
Phi->getNumIncomingValues() == 2 &&
"Expected 2 operand phi.");
212 unsigned IncrementingBlock =
Phi->getIncomingValue(0) == Inc ? 0 : 1;
213 assert(
Phi->getIncomingValue(IncrementingBlock) == Inc &&
214 "Expected one operand of phi to be Inc");
217 if (!
L->isLoopInvariant(Step))
228 assert(Stride !=
nullptr);
233 Inc = BinaryOperator::CreateAdd(BasePtr, Step, Inc->
getName() +
".scalar",
235 BasePtr->addIncoming(Start,
Phi->getIncomingBlock(1 - IncrementingBlock));
236 BasePtr->addIncoming(Inc,
Phi->getIncomingBlock(IncrementingBlock));
239 MaybeDeadPHIs.push_back(Phi);
244 auto *BO = dyn_cast<BinaryOperator>(
Index);
248 switch (BO->getOpcode()) {
251 case Instruction::Or:
253 if (!cast<PossiblyDisjointInst>(BO)->isDisjoint())
256 case Instruction::Add:
258 case Instruction::Shl:
260 case Instruction::Mul:
266 if (isa<Instruction>(BO->getOperand(0)) &&
267 L->contains(cast<Instruction>(BO->getOperand(0)))) {
268 Index = cast<Instruction>(BO->getOperand(0));
269 OtherOp = BO->getOperand(1);
270 }
else if (isa<Instruction>(BO->getOperand(1)) &&
271 L->contains(cast<Instruction>(BO->getOperand(1))) &&
273 Index = cast<Instruction>(BO->getOperand(1));
274 OtherOp = BO->getOperand(0);
280 if (!
L->isLoopInvariant(OtherOp))
289 if (!matchStridedRecurrence(
Index, L, Stride, BasePtr, Inc, Builder))
294 unsigned StartBlock =
BasePtr->getOperand(0) == Inc ? 1 : 0;
300 BasePtr->getIncomingBlock(StartBlock)->getTerminator());
303 switch (BO->getOpcode()) {
306 case Instruction::Add:
307 case Instruction::Or: {
310 Start = Builder.
CreateAdd(Start, SplatOp,
"start");
313 case Instruction::Mul: {
314 Start = Builder.
CreateMul(Start, SplatOp,
"start");
315 Step = Builder.
CreateMul(Step, SplatOp,
"step");
316 Stride = Builder.
CreateMul(Stride, SplatOp,
"stride");
319 case Instruction::Shl: {
320 Start = Builder.
CreateShl(Start, SplatOp,
"start");
321 Step = Builder.
CreateShl(Step, SplatOp,
"step");
322 Stride = Builder.
CreateShl(Stride, SplatOp,
"stride");
328 BasePtr->setIncomingValue(StartBlock, Start);
332std::pair<Value *, Value *>
333RISCVGatherScatterLowering::determineBaseAndStride(
Instruction *
Ptr,
339 return std::make_pair(BasePtr, ConstantInt::get(IntPtrTy, 0));
342 auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr);
344 return std::make_pair(
nullptr,
nullptr);
346 auto I = StridedAddrs.find(
GEP);
347 if (
I != StridedAddrs.end())
353 Value *ScalarBase = Ops[0];
357 return std::make_pair(
nullptr,
nullptr);
360 std::optional<unsigned> VecOperand;
361 unsigned TypeScale = 0;
365 for (
unsigned i = 1, e =
GEP->getNumOperands(); i != e; ++i, ++GTI) {
366 if (!Ops[i]->
getType()->isVectorTy())
370 return std::make_pair(
nullptr,
nullptr);
376 return std::make_pair(
nullptr,
nullptr);
383 return std::make_pair(
nullptr,
nullptr);
390 Value *VecIndex = Ops[*VecOperand];
391 Type *VecIntPtrTy =
DL->getIntPtrType(
GEP->getType());
392 if (VecIndex->
getType() != VecIntPtrTy) {
393 auto *VecIndexC = dyn_cast<Constant>(VecIndex);
395 return std::make_pair(
nullptr,
nullptr);
410 Ops[*VecOperand] = Start;
411 Type *SourceTy =
GEP->getSourceElementType();
421 Stride = Builder.
CreateMul(Stride, ConstantInt::get(IntPtrTy, TypeScale));
423 auto P = std::make_pair(BasePtr, Stride);
424 StridedAddrs[
GEP] =
P;
429 Loop *
L = LI->getLoopFor(
GEP->getParent());
430 if (!L || !
L->getLoopPreheader() || !
L->getLoopLatch())
431 return std::make_pair(
nullptr,
nullptr);
435 if (!matchStridedRecurrence(VecIndex, L, Stride, BasePhi, Inc, Builder))
436 return std::make_pair(
nullptr,
nullptr);
439 unsigned IncrementingBlock = BasePhi->
getOperand(0) == Inc ? 0 : 1;
441 "Expected one operand of phi to be Inc");
446 Ops[*VecOperand] = BasePhi;
447 Type *SourceTy =
GEP->getSourceElementType();
461 Stride = Builder.
CreateMul(Stride, ConstantInt::get(IntPtrTy, TypeScale));
463 auto P = std::make_pair(BasePtr, Stride);
464 StridedAddrs[
GEP] =
P;
468bool RISCVGatherScatterLowering::tryCreateStridedLoadStore(
IntrinsicInst *II,
473 MaybeAlign MA = cast<ConstantInt>(AlignOp)->getMaybeAlignValue();
474 EVT DataTypeVT = TLI->getValueType(*
DL, DataType);
475 if (!MA || !TLI->isLegalStridedLoadStore(DataTypeVT, *MA))
479 if (!TLI->isTypeLegal(DataTypeVT))
483 auto *PtrI = dyn_cast<Instruction>(
Ptr);
492 std::tie(BasePtr, Stride) = determineBaseAndStride(PtrI, Builder);
495 assert(Stride !=
nullptr);
502 Intrinsic::riscv_masked_strided_load,
507 Intrinsic::riscv_masked_strided_store,
515 if (PtrI->use_empty())
521bool RISCVGatherScatterLowering::runOnFunction(
Function &
F) {
525 auto &TPC = getAnalysis<TargetPassConfig>();
528 if (!
ST->hasVInstructions() || !
ST->useRVVForFixedLengthVectors())
531 TLI =
ST->getTargetLowering();
532 DL = &
F.getParent()->getDataLayout();
533 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
535 StridedAddrs.clear();
540 bool Changed =
false;
547 }
else if (II && II->
getIntrinsicID() == Intrinsic::masked_scatter) {
554 for (
auto *II : Gathers)
555 Changed |= tryCreateStridedLoadStore(
557 for (
auto *II : Scatters)
563 while (!MaybeDeadPHIs.empty()) {
564 if (
auto *Phi = dyn_cast_or_null<PHINode>(MaybeDeadPHIs.pop_back_val()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static std::pair< Value *, Value * > matchStridedStart(Value *Start, IRBuilderBase &Builder)
static std::pair< Value *, Value * > matchStridedConstant(Constant *StartC)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static SymbolRef::Type getType(const Symbol *Sym)
Target-Independent Code Generator Pass Configuration Options pass.
Class for arbitrary precision integers.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesCFG()
This function should be called by the pass, iff they do not:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
BinaryOps getOpcode() const
Value * getArgOperand(unsigned i) const
This class represents a function call, abstracting a target machine's calling convention.
This is the shared class of boolean and integer constants.
const APInt & getValue() const
Return the constant as an APInt value reference.
This is an important base class in LLVM.
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
A parsed version of the target data layout string in and methods for querying it.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Common base class shared among various IRBuilders.
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", bool IsInBounds=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
This is an important class for using LLVM in a threaded context.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Target-Independent Code Generator Pass Configuration Options.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isVectorTy() const
True if this is an instance of VectorType.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
StringRef getName() const
Return a constant reference to the value's name.
constexpr ScalarTy getFixedValue() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
TypeSize getSequentialElementStride(const DataLayout &DL) const
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
bool match(Val *V, const Pattern &P)
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
FunctionPass * createRISCVGatherScatterLoweringPass()
bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
gep_type_iterator gep_type_begin(const User *GEP)
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
Constant * ConstantFoldCastInstruction(unsigned opcode, Constant *V, Type *DestTy)
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.