1//===----- RISCVCodeGenPrepare.cpp ----------------------------------------===//
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// This is a RISC-V specific version of CodeGenPrepare.
10// It munges the code in the input function to better prepare it for
11// SelectionDAG-based code generation. This works around limitations in it's
12// basic-block-at-a-time approach.
13//
14//===----------------------------------------------------------------------===//
15
16#include "RISCV.h"
17#include "RISCVTargetMachine.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/Analysis/ValueTracking.h"
20#include "llvm/CodeGen/TargetPassConfig.h"
21#include "llvm/IR/Dominators.h"
22#include "llvm/IR/IRBuilder.h"
23#include "llvm/IR/InstVisitor.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/IR/Intrinsics.h"
26#include "llvm/IR/PatternMatch.h"
27#include "llvm/InitializePasses.h"
28#include "llvm/Pass.h"
29#include "llvm/Transforms/Utils/Local.h"
30
31using namespace llvm;
32
33#define DEBUG_TYPE "riscv-codegenprepare"
34#define PASS_NAME "RISC-V CodeGenPrepare"
35
36namespace {
37class RISCVCodeGenPrepareImpl
38 : public InstVisitor<RISCVCodeGenPrepareImpl, bool> {
39 Function &F;
40 const DataLayout *DL;
41 const DominatorTree *DT;
42 const RISCVSubtarget *ST;
43
44public:
45 RISCVCodeGenPrepareImpl(Function &F, const DominatorTree *DT,
46 const RISCVSubtarget *ST)
47 : F(F), DL(&F.getDataLayout()), DT(DT), ST(ST) {}
48 bool run();
49 bool visitInstruction(Instruction &I) { return false; }
50 bool visitAnd(BinaryOperator &BO);
51 bool visitIntrinsicInst(IntrinsicInst &I);
52 bool expandVPStrideLoad(IntrinsicInst &I);
53 bool expandMulReduction(IntrinsicInst &I);
54 bool widenVPMerge(Instruction *I);
55 bool visitFreezeInst(FreezeInst &BO);
56};
57} // namespace
58
59namespace {
60class RISCVCodeGenPrepareLegacy : public FunctionPass {
61public:
62 static char ID;
63
64 RISCVCodeGenPrepareLegacy() : FunctionPass(ID) {}
65
66 bool runOnFunction(Function &F) override;
67 StringRef getPassName() const override { return PASS_NAME; }
68
69 void getAnalysisUsage(AnalysisUsage &AU) const override {
70 AU.setPreservesCFG();
71 AU.addRequired<DominatorTreeWrapperPass>();
72 AU.addRequired<TargetPassConfig>();
73 }
74};
75} // namespace
76
77// Try to optimize (i64 (and (zext/sext (i32 X), C1))) if C1 has bit 31 set,
78// but bits 63:32 are zero. If we know that bit 31 of X is 0, we can fill
79// the upper 32 bits with ones.
80bool RISCVCodeGenPrepareImpl::visitAnd(BinaryOperator &BO) {
81 if (!ST->is64Bit())
82 return false;
83
84 if (!BO.getType()->isIntegerTy(BitWidth: 64))
85 return false;
86
87 using namespace PatternMatch;
88
89 // Left hand side should be a zext nneg.
90 Value *LHSSrc;
91 if (!match(V: BO.getOperand(i_nocapture: 0), P: m_NNegZExt(Op: m_Value(V&: LHSSrc))))
92 return false;
93
94 if (!LHSSrc->getType()->isIntegerTy(BitWidth: 32))
95 return false;
96
97 // Right hand side should be a constant.
98 Value *RHS = BO.getOperand(i_nocapture: 1);
99
100 auto *CI = dyn_cast<ConstantInt>(Val: RHS);
101 if (!CI)
102 return false;
103 uint64_t C = CI->getZExtValue();
104
105 // Look for constants that fit in 32 bits but not simm12, and can be made
106 // into simm12 by sign extending bit 31. This will allow use of ANDI.
107 // TODO: Is worth making simm32?
108 if (!isUInt<32>(x: C) || isInt<12>(x: C) || !isInt<12>(x: SignExtend64<32>(x: C)))
109 return false;
110
111 // Sign extend the constant and replace the And operand.
112 C = SignExtend64<32>(x: C);
113 BO.setOperand(i_nocapture: 1, Val_nocapture: ConstantInt::get(Ty: RHS->getType(), V: C));
114
115 return true;
116}
117
118// With EVL tail folding, an AnyOf reduction will generate an i1 vp.merge like
119// follows:
120//
121// loop:
122// %phi = phi <vscale x 4 x i1> [zeroinitializer, %entry], [%freeze, %loop]
123// %cmp = icmp ...
124// %rec = call <vscale x 4 x i1> @llvm.vp.merge(%cmp, i1 true, %phi, %evl)
125// %freeze = freeze <vscale x 4 x i1> %rec [optional]
126// ...
127// middle:
128// %res = call i1 @llvm.vector.reduce.or(<vscale x 4 x i1> %freeze)
129//
130// However RVV doesn't have any tail undisturbed mask instructions and so we
131// need a convoluted sequence of mask instructions to lower the i1 vp.merge: see
132// llvm/test/CodeGen/RISCV/rvv/vpmerge-sdnode.ll.
133//
134// To avoid that this widens the i1 vp.merge to an i8 vp.merge, which will
135// generate a single vmerge.vim:
136//
137// loop:
138// %phi = phi <vscale x 4 x i8> [zeroinitializer, %entry], [%freeze, %loop]
139// %cmp = icmp ...
140// %rec = call <vscale x 4 x i8> @llvm.vp.merge(%cmp, i8 true, %phi, %evl)
141// %freeze = freeze <vscale x 4 x i8> %rec
142// %trunc = trunc <vscale x 4 x i8> %freeze to <vscale x 4 x i1>
143// ...
144// middle:
145// %res = call i1 @llvm.vector.reduce.or(<vscale x 4 x i1> %trunc)
146//
147// The trunc will normally be sunk outside of the loop, but even if there are
148// users inside the loop it is still profitable.
149bool RISCVCodeGenPrepareImpl::widenVPMerge(Instruction *Root) {
150 if (!Root->getType()->getScalarType()->isIntegerTy(BitWidth: 1))
151 return false;
152
153 Value *Mask, *True, *EVL;
154 PHINode *Phi;
155 using namespace PatternMatch;
156 auto m_VPMerge = m_Intrinsic<Intrinsic::vp_merge>(
157 Ops: m_Value(V&: Mask), Ops: m_Value(V&: True), Ops: m_Phi(PN&: Phi), Ops: m_Value(V&: EVL));
158 if (!match(V: Root, P: m_CombineOr(Ps: m_VPMerge, Ps: m_Freeze(Op: m_VPMerge))))
159 return false;
160
161 if (!Phi->hasOneUse() || Phi->getNumIncomingValues() != 2 ||
162 !match(V: Phi->getIncomingValue(i: 0), P: m_Zero()) ||
163 Phi->getIncomingValue(i: 1) != Root)
164 return false;
165
166 Type *WideTy =
167 VectorType::get(ElementType: IntegerType::getInt8Ty(C&: Root->getContext()),
168 EC: cast<VectorType>(Val: Root->getType())->getElementCount());
169
170 IRBuilder<> Builder(Phi);
171 PHINode *WidePhi = Builder.CreatePHI(Ty: WideTy, NumReservedValues: 2);
172 WidePhi->addIncoming(V: ConstantAggregateZero::get(Ty: WideTy),
173 BB: Phi->getIncomingBlock(i: 0));
174 Builder.SetInsertPoint(Root);
175 Value *WideTrue = Builder.CreateZExt(V: True, DestTy: WideTy);
176 Value *WideMerge = Builder.CreateIntrinsic(ID: Intrinsic::vp_merge, OverloadTypes: {WideTy},
177 Args: {Mask, WideTrue, WidePhi, EVL});
178 if (isa<FreezeInst>(Val: Root))
179 WideMerge = Builder.CreateFreeze(V: WideMerge);
180 WidePhi->addIncoming(V: WideMerge, BB: Phi->getIncomingBlock(i: 1));
181 Value *Trunc = Builder.CreateTrunc(V: WideMerge, DestTy: Root->getType());
182
183 Root->replaceAllUsesWith(V: Trunc);
184
185 // Break the cycle and delete the old chain.
186 Phi->setIncomingValue(i: 1, V: Phi->getIncomingValue(i: 0));
187 llvm::RecursivelyDeleteTriviallyDeadInstructions(V: Root);
188
189 return true;
190}
191
192bool RISCVCodeGenPrepareImpl::visitFreezeInst(FreezeInst &I) {
193 if (auto *II = dyn_cast<IntrinsicInst>(Val: I.getOperand(i_nocapture: 0)))
194 if (II->getIntrinsicID() == Intrinsic::vp_merge)
195 return widenVPMerge(Root: &I);
196 return false;
197}
198
199// LLVM vector reduction intrinsics return a scalar result, but on RISC-V vector
200// reduction instructions write the result in the first element of a vector
201// register. So when a reduction in a loop uses a scalar phi, we end up with
202// unnecessary scalar moves:
203//
204// loop:
205// vfmv.s.f v10, fa0
206// vfredosum.vs v8, v8, v10
207// vfmv.f.s fa0, v8
208//
209// This mainly affects ordered fadd reductions and VP reductions that have a
210// scalar start value, since other types of reduction typically use element-wise
211// vectorisation in the loop body. This tries to vectorize any scalar phis that
212// feed into these reductions:
213//
214// loop:
215// %phi = phi <float> [ ..., %entry ], [ %acc, %loop ]
216// %acc = call float @llvm.vector.reduce.fadd.nxv2f32(float %phi,
217// <vscale x 2 x float> %vec)
218//
219// ->
220//
221// loop:
222// %phi = phi <vscale x 2 x float> [ ..., %entry ], [ %acc.vec, %loop ]
223// %phi.scalar = extractelement <vscale x 2 x float> %phi, i64 0
224// %acc = call float @llvm.vector.reduce.fadd.nxv2f32(float %x,
225// <vscale x 2 x float> %vec)
226// %acc.vec = insertelement <vscale x 2 x float> poison, float %acc.next, i64 0
227//
228// Which eliminates the scalar -> vector -> scalar crossing during instruction
229// selection.
230bool RISCVCodeGenPrepareImpl::visitIntrinsicInst(IntrinsicInst &I) {
231 if (expandVPStrideLoad(I))
232 return true;
233
234 if (expandMulReduction(I))
235 return true;
236
237 if (widenVPMerge(Root: &I))
238 return true;
239
240 if (I.getIntrinsicID() != Intrinsic::vector_reduce_fadd &&
241 !isa<VPReductionIntrinsic>(Val: &I))
242 return false;
243
244 auto *PHI = dyn_cast<PHINode>(Val: I.getOperand(i_nocapture: 0));
245 if (!PHI || !PHI->hasOneUse() ||
246 !llvm::is_contained(Range: PHI->incoming_values(), Element: &I))
247 return false;
248
249 Type *VecTy = I.getOperand(i_nocapture: 1)->getType();
250 IRBuilder<> Builder(PHI);
251 auto *VecPHI = Builder.CreatePHI(Ty: VecTy, NumReservedValues: PHI->getNumIncomingValues());
252
253 for (auto *BB : PHI->blocks()) {
254 Builder.SetInsertPoint(BB->getTerminator());
255 Value *InsertElt = Builder.CreateInsertElement(
256 VecTy, NewElt: PHI->getIncomingValueForBlock(BB), Idx: (uint64_t)0);
257 VecPHI->addIncoming(V: InsertElt, BB);
258 }
259
260 Builder.SetInsertPoint(&I);
261 I.setOperand(i_nocapture: 0, Val_nocapture: Builder.CreateExtractElement(Vec: VecPHI, Idx: (uint64_t)0));
262
263 PHI->eraseFromParent();
264
265 return true;
266}
267
268// Extract pieces of size PieceEC from Vec, then build a binary tree of
269// element-wise multiplies reducing to a single piece.
270static Value *buildMulTree(IRBuilder<> &Builder, ElementCount PieceEC,
271 Value *Vec) {
272 auto *VecTy = cast<VectorType>(Val: Vec->getType());
273 auto *PieceTy = VectorType::get(ElementType: VecTy->getElementType(), EC: PieceEC);
274 unsigned PieceElts = PieceEC.getKnownMinValue();
275 unsigned NumPieces = VecTy->getElementCount().getKnownMinValue() / PieceElts;
276 assert(isPowerOf2_32(NumPieces));
277
278 SmallVector<Value *, 8> Pieces(NumPieces);
279 for (unsigned i = 0; i < NumPieces; i++)
280 Pieces[i] = Builder.CreateExtractVector(DstType: PieceTy, SrcVec: Vec, Idx: i * PieceElts);
281
282 while (Pieces.size() > 1) {
283 for (unsigned i = 0; i < Pieces.size() / 2; i++)
284 Pieces[i] =
285 Builder.CreateMul(LHS: Pieces[i * 2], RHS: Pieces[i * 2 + 1], Name: "bin.rdx");
286 Pieces.truncate(N: Pieces.size() / 2);
287 }
288 return Pieces[0];
289}
290
291// Partially expand a vector_reduce_mul wider than M1 to reduce
292// register pressure and the number of vsetvlis required.
293bool RISCVCodeGenPrepareImpl::expandMulReduction(IntrinsicInst &II) {
294 if (II.getIntrinsicID() != Intrinsic::vector_reduce_mul)
295 return false;
296
297 if (!ST->hasVInstructions())
298 return false;
299
300 Value *TmpVec = II.getArgOperand(i: 0);
301 auto *VecTy = cast<VectorType>(Val: TmpVec->getType());
302 unsigned EltSize = VecTy->getScalarSizeInBits();
303
304 if (auto *ScalTy = dyn_cast<ScalableVectorType>(Val: VecTy)) {
305 unsigned MinElts = ScalTy->getMinNumElements();
306
307 if (auto VLen = ST->getRealVLen()) {
308 // If VLEN is exactly known, convert to a fixed vector reduction and
309 // recurse to let the fixed path handle it (shuffle reduction instead
310 // of a scalar loop).
311 unsigned VScale = *VLen / RISCV::RVVBitsPerBlock;
312 auto *FixedTy =
313 FixedVectorType::get(ElementType: VecTy->getElementType(), NumElts: MinElts * VScale);
314 IRBuilder<> Builder(&II);
315 Value *Fixed = Builder.CreateExtractVector(DstType: FixedTy, SrcVec: TmpVec, Idx: (uint64_t)0);
316 auto *FixedRdx = cast<IntrinsicInst>(Val: Builder.CreateIntrinsic(
317 ID: Intrinsic::vector_reduce_mul, OverloadTypes: {FixedTy}, Args: {Fixed}));
318 II.replaceAllUsesWith(V: FixedRdx);
319 II.eraseFromParent();
320 expandMulReduction(II&: *FixedRdx);
321 return true;
322 }
323
324 unsigned M1MinElts = RISCV::RVVBitsPerBlock / EltSize;
325 if (MinElts <= M1MinElts || !isPowerOf2_32(Value: MinElts / M1MinElts))
326 return false;
327
328 IRBuilder<> Builder(&II);
329 auto M1EC = ElementCount::getScalable(MinVal: M1MinElts);
330 Value *Reduced = buildMulTree(Builder, PieceEC: M1EC, Vec: TmpVec);
331 Value *Rdx = Builder.CreateIntrinsic(ID: Intrinsic::vector_reduce_mul,
332 OverloadTypes: {Reduced->getType()}, Args: {Reduced});
333 II.replaceAllUsesWith(V: Rdx);
334 II.eraseFromParent();
335 return true;
336 }
337
338 unsigned VF = cast<FixedVectorType>(Val: VecTy)->getNumElements();
339 unsigned MinVLen = ST->getRealMinVLen();
340 unsigned M1VF = MinVLen / EltSize;
341
342 if (!isPowerOf2_32(Value: VF) || VF <= M1VF)
343 return false;
344
345 IRBuilder<> Builder(&II);
346 auto M1EC = ElementCount::getFixed(MinVal: M1VF);
347 auto *M1Ty = VectorType::get(ElementType: VecTy->getElementType(), EC: M1EC);
348
349 // When VLEN is exactly known, extract m1 pieces and build a mul tree.
350 // This greatly reduces register pressure during the reduction, and
351 // avoids all but one vsetvli (the one from original LMUL to m1).
352 // TODO: Generalize to handle the splitting case.
353 if (MinVLen == ST->getRealMaxVLen() && VF <= 8 * M1VF) {
354 TmpVec = buildMulTree(Builder, PieceEC: M1EC, Vec: TmpVec);
355 } else {
356 // For non-exact VLEN, shuffle-reduce at the original vector width down to
357 // m1, then extract. This prioritizes reducing the number of vsetvli
358 // over maximal reduction of LMUL for the intermediate states.
359 SmallVector<int, 32> ShuffleMask(VF);
360 for (unsigned LiveElts = VF; LiveElts > M1VF; LiveElts /= 2) {
361 unsigned Half = LiveElts / 2;
362 std::iota(first: ShuffleMask.begin(), last: ShuffleMask.begin() + Half, value: Half);
363 std::fill(first: ShuffleMask.begin() + Half, last: ShuffleMask.end(), value: -1);
364 Value *Shuf =
365 Builder.CreateShuffleVector(V: TmpVec, Mask: ShuffleMask, Name: "rdx.shuf");
366 TmpVec = Builder.CreateMul(LHS: TmpVec, RHS: Shuf, Name: "bin.rdx");
367 }
368 // Extract the M1-sized subvector and emit the final reduction intrinsic.
369 // This is the reason we're here - to force a vsetvli toggle once at m1.
370 TmpVec = Builder.CreateExtractVector(DstType: M1Ty, SrcVec: TmpVec, Idx: (uint64_t)0, Name: "rdx.sub");
371 }
372
373 Value *Rdx =
374 Builder.CreateIntrinsic(ID: Intrinsic::vector_reduce_mul, OverloadTypes: {M1Ty}, Args: {TmpVec});
375 II.replaceAllUsesWith(V: Rdx);
376 II.eraseFromParent();
377 return true;
378}
379
380// Always expand zero strided loads so we match more .vx splat patterns, even if
381// we have +optimized-zero-stride-loads. RISCVDAGToDAGISel::Select will convert
382// it back to a strided load if it's optimized.
383bool RISCVCodeGenPrepareImpl::expandVPStrideLoad(IntrinsicInst &II) {
384 Value *BasePtr, *VL;
385
386 using namespace PatternMatch;
387 if (!match(V: &II, P: m_Intrinsic<Intrinsic::experimental_vp_strided_load>(
388 Ops: m_Value(V&: BasePtr), Ops: m_Zero(), Ops: m_AllOnes(), Ops: m_Value(V&: VL))))
389 return false;
390
391 // If SEW>XLEN then a splat will get lowered as a zero strided load anyway, so
392 // avoid expanding here.
393 if (II.getType()->getScalarSizeInBits() > ST->getXLen())
394 return false;
395
396 if (!isKnownNonZero(V: VL, Q: {*DL, DT, nullptr, &II}))
397 return false;
398
399 auto *VTy = cast<VectorType>(Val: II.getType());
400
401 IRBuilder<> Builder(&II);
402 Type *STy = VTy->getElementType();
403 Value *Val = Builder.CreateLoad(Ty: STy, Ptr: BasePtr);
404 Value *Res = Builder.CreateIntrinsic(
405 ID: Intrinsic::vp_merge, OverloadTypes: VTy,
406 Args: {II.getOperand(i_nocapture: 2), Builder.CreateVectorSplat(EC: VTy->getElementCount(), V: Val),
407 PoisonValue::get(T: VTy), VL});
408
409 II.replaceAllUsesWith(V: Res);
410 II.eraseFromParent();
411 return true;
412}
413
414bool RISCVCodeGenPrepareImpl::run() {
415 bool MadeChange = false;
416 for (auto &BB : F)
417 for (Instruction &I : llvm::make_early_inc_range(Range&: BB))
418 MadeChange |= visit(I);
419
420 return MadeChange;
421}
422
423bool RISCVCodeGenPrepareLegacy::runOnFunction(Function &F) {
424 if (skipFunction(F))
425 return false;
426
427 auto &TPC = getAnalysis<TargetPassConfig>();
428 auto &TM = TPC.getTM<RISCVTargetMachine>();
429 auto ST = &TM.getSubtarget<RISCVSubtarget>(F);
430 auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
431
432 RISCVCodeGenPrepareImpl RVCGP(F, DT, ST);
433 return RVCGP.run();
434}
435
436INITIALIZE_PASS_BEGIN(RISCVCodeGenPrepareLegacy, DEBUG_TYPE, PASS_NAME, false,
437 false)
438INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
439INITIALIZE_PASS_END(RISCVCodeGenPrepareLegacy, DEBUG_TYPE, PASS_NAME, false,
440 false)
441
442char RISCVCodeGenPrepareLegacy::ID = 0;
443
444FunctionPass *llvm::createRISCVCodeGenPrepareLegacyPass() {
445 return new RISCVCodeGenPrepareLegacy();
446}
447
448PreservedAnalyses RISCVCodeGenPreparePass::run(Function &F,
449 FunctionAnalysisManager &FAM) {
450 DominatorTree *DT = &FAM.getResult<DominatorTreeAnalysis>(IR&: F);
451 auto ST = &TM->getSubtarget<RISCVSubtarget>(F);
452 bool Changed = RISCVCodeGenPrepareImpl(F, DT, ST).run();
453 if (!Changed)
454 return PreservedAnalyses::all();
455
456 PreservedAnalyses PA = PreservedAnalyses::none();
457 PA.preserveSet<CFGAnalyses>();
458 return PA;
459}
460