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);
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();
137 auto *BO = dyn_cast<BinaryOperator>(Start);
138 if (!BO || (BO->getOpcode() != Instruction::Add &&
139 BO->getOpcode() != Instruction::Shl &&
140 BO->getOpcode() != Instruction::Mul))
141 return std::make_pair(
nullptr,
nullptr);
144 unsigned OtherIndex = 0;
151 return std::make_pair(
nullptr,
nullptr);
157 return std::make_pair(
nullptr,
nullptr);
163 switch (BO->getOpcode()) {
166 case Instruction::Add:
169 case Instruction::Mul:
173 case Instruction::Shl:
179 return std::make_pair(Start, Stride);
186bool RISCVGatherScatterLowering::matchStridedRecurrence(
Value *
Index,
Loop *L,
192 if (
auto *Phi = dyn_cast<PHINode>(
Index)) {
195 if (
Phi->getParent() !=
L->getHeader())
202 assert(
Phi->getNumIncomingValues() == 2 &&
"Expected 2 operand phi.");
203 unsigned IncrementingBlock =
Phi->getIncomingValue(0) == Inc ? 0 : 1;
204 assert(
Phi->getIncomingValue(IncrementingBlock) == Inc &&
205 "Expected one operand of phi to be Inc");
208 if (!
L->isLoopInvariant(Step))
219 assert(Stride !=
nullptr);
224 Inc = BinaryOperator::CreateAdd(BasePtr, Step, Inc->
getName() +
".scalar",
226 BasePtr->addIncoming(Start,
Phi->getIncomingBlock(1 - IncrementingBlock));
227 BasePtr->addIncoming(Inc,
Phi->getIncomingBlock(IncrementingBlock));
230 MaybeDeadPHIs.push_back(Phi);
235 auto *BO = dyn_cast<BinaryOperator>(
Index);
239 switch (BO->getOpcode()) {
242 case Instruction::Or:
247 case Instruction::Add:
249 case Instruction::Shl:
251 case Instruction::Mul:
257 if (isa<Instruction>(BO->getOperand(0)) &&
258 L->contains(cast<Instruction>(BO->getOperand(0)))) {
259 Index = cast<Instruction>(BO->getOperand(0));
260 OtherOp = BO->getOperand(1);
261 }
else if (isa<Instruction>(BO->getOperand(1)) &&
262 L->contains(cast<Instruction>(BO->getOperand(1))) &&
264 Index = cast<Instruction>(BO->getOperand(1));
265 OtherOp = BO->getOperand(0);
271 if (!
L->isLoopInvariant(OtherOp))
280 if (!matchStridedRecurrence(
Index, L, Stride, BasePtr, Inc, Builder))
285 unsigned StartBlock =
BasePtr->getOperand(0) == Inc ? 1 : 0;
291 BasePtr->getIncomingBlock(StartBlock)->getTerminator());
294 switch (BO->getOpcode()) {
297 case Instruction::Add:
298 case Instruction::Or: {
301 Start =
Builder.CreateAdd(Start, SplatOp,
"start");
304 case Instruction::Mul: {
305 Start =
Builder.CreateMul(Start, SplatOp,
"start");
306 Step =
Builder.CreateMul(Step, SplatOp,
"step");
307 Stride =
Builder.CreateMul(Stride, SplatOp,
"stride");
310 case Instruction::Shl: {
311 Start =
Builder.CreateShl(Start, SplatOp,
"start");
312 Step =
Builder.CreateShl(Step, SplatOp,
"step");
313 Stride =
Builder.CreateShl(Stride, SplatOp,
"stride");
319 BasePtr->setIncomingValue(StartBlock, Start);
323std::pair<Value *, Value *>
324RISCVGatherScatterLowering::determineBaseAndStride(
Instruction *
Ptr,
333 auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr);
335 return std::make_pair(
nullptr,
nullptr);
337 auto I = StridedAddrs.find(
GEP);
338 if (
I != StridedAddrs.end())
344 Value *ScalarBase = Ops[0];
348 return std::make_pair(
nullptr,
nullptr);
351 std::optional<unsigned> VecOperand;
352 unsigned TypeScale = 0;
356 for (
unsigned i = 1, e =
GEP->getNumOperands(); i != e; ++i, ++GTI) {
357 if (!Ops[i]->
getType()->isVectorTy())
361 return std::make_pair(
nullptr,
nullptr);
367 return std::make_pair(
nullptr,
nullptr);
374 return std::make_pair(
nullptr,
nullptr);
381 Value *VecIndex = Ops[*VecOperand];
382 Type *VecIntPtrTy =
DL->getIntPtrType(
GEP->getType());
383 if (VecIndex->
getType() != VecIntPtrTy) {
384 auto *VecIndexC = dyn_cast<Constant>(VecIndex);
386 return std::make_pair(
nullptr,
nullptr);
401 Ops[*VecOperand] = Start;
402 Type *SourceTy =
GEP->getSourceElementType();
414 auto P = std::make_pair(BasePtr, Stride);
415 StridedAddrs[
GEP] =
P;
420 Loop *
L = LI->getLoopFor(
GEP->getParent());
421 if (!L || !
L->getLoopPreheader() || !
L->getLoopLatch())
422 return std::make_pair(
nullptr,
nullptr);
426 if (!matchStridedRecurrence(VecIndex, L, Stride, BasePhi, Inc, Builder))
427 return std::make_pair(
nullptr,
nullptr);
430 unsigned IncrementingBlock = BasePhi->
getOperand(0) == Inc ? 0 : 1;
432 "Expected one operand of phi to be Inc");
437 Ops[*VecOperand] = BasePhi;
438 Type *SourceTy =
GEP->getSourceElementType();
454 auto P = std::make_pair(BasePtr, Stride);
455 StridedAddrs[
GEP] =
P;
459bool RISCVGatherScatterLowering::tryCreateStridedLoadStore(
IntrinsicInst *II,
464 MaybeAlign MA = cast<ConstantInt>(AlignOp)->getMaybeAlignValue();
465 EVT DataTypeVT = TLI->getValueType(*
DL, DataType);
466 if (!MA || !TLI->isLegalStridedLoadStore(DataTypeVT, *MA))
470 if (!TLI->isTypeLegal(DataTypeVT))
474 auto *PtrI = dyn_cast<Instruction>(
Ptr);
483 std::tie(BasePtr, Stride) = determineBaseAndStride(PtrI, Builder);
486 assert(Stride !=
nullptr);
493 Intrinsic::riscv_masked_strided_load,
498 Intrinsic::riscv_masked_strided_store,
506 if (PtrI->use_empty())
512bool RISCVGatherScatterLowering::runOnFunction(
Function &
F) {
516 auto &TPC = getAnalysis<TargetPassConfig>();
519 if (!
ST->hasVInstructions() || !
ST->useRVVForFixedLengthVectors())
522 TLI =
ST->getTargetLowering();
523 DL = &
F.getParent()->getDataLayout();
524 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
526 StridedAddrs.clear();
531 bool Changed =
false;
538 }
else if (II && II->
getIntrinsicID() == Intrinsic::masked_scatter) {
545 for (
auto *II : Gathers)
546 Changed |= tryCreateStridedLoadStore(
548 for (
auto *II : Scatters)
554 while (!MaybeDeadPHIs.empty()) {
555 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.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
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.
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:
SymbolTableList< Instruction >::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="", Instruction *InsertBefore=nullptr)
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).
Type * getIndexedType() const
#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,...
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
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.