1//===- SLPReductionUtils.cpp - SLP reduction match helpers ----------------===//
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#include "SLPReductionUtils.h"
10
11#include "SLPCostAnalysis.h"
12
13#include "llvm/Analysis/IVDescriptors.h"
14#include "llvm/IR/Constants.h"
15#include "llvm/IR/IRBuilder.h"
16#include "llvm/IR/Instructions.h"
17#include "llvm/IR/Intrinsics.h"
18#include "llvm/IR/PatternMatch.h"
19#include "llvm/IR/Type.h"
20
21using namespace llvm;
22using namespace llvm::PatternMatch;
23
24namespace llvm::slpvectorizer {
25
26static bool matchRdxBop(Instruction *I, Value *&V0, Value *&V1) {
27 if (match(V: I, P: m_BinOp(L: m_Value(V&: V0), R: m_Value(V&: V1))))
28 return true;
29 if (match(V: I, P: m_FMaxNum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
30 return true;
31 if (match(V: I, P: m_FMinNum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
32 return true;
33 if (match(V: I, P: m_FMaximum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
34 return true;
35 if (match(V: I, P: m_FMinimum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
36 return true;
37 if (match(V: I, P: m_Intrinsic<Intrinsic::smax>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
38 return true;
39 if (match(V: I, P: m_Intrinsic<Intrinsic::smin>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
40 return true;
41 if (match(V: I, P: m_Intrinsic<Intrinsic::umax>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
42 return true;
43 if (match(V: I, P: m_Intrinsic<Intrinsic::umin>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
44 return true;
45 return false;
46}
47
48Instruction *getNonPhiOperand(Instruction *I, PHINode *Phi) {
49 Value *Op0 = nullptr;
50 Value *Op1 = nullptr;
51 if (!matchRdxBop(I, V0&: Op0, V1&: Op1))
52 return nullptr;
53 return dyn_cast<Instruction>(Val: Op0 == Phi ? Op1 : Op0);
54}
55
56bool isReductionCandidate(Instruction *I) {
57 bool IsSelect = match(V: I, P: m_Select(C: m_Value(), L: m_Value(), R: m_Value()));
58 Value *B0 = nullptr, *B1 = nullptr;
59 bool IsBinop = matchRdxBop(I, V0&: B0, V1&: B1);
60 return IsBinop || IsSelect;
61}
62
63Type *getBoolReduxWideTy(RecurKind RdxKind, Type *RootTy, Type *LeafTy) {
64 if ((RdxKind == RecurKind::And || RdxKind == RecurKind::Or) &&
65 RootTy->isIntegerTy(BitWidth: 1) && LeafTy->isIntegerTy() &&
66 !LeafTy->isIntegerTy(BitWidth: 1))
67 return LeafTy;
68 return nullptr;
69}
70
71Value *tryEmitBoolReduxBitcastCmp(IRBuilderBase &Builder,
72 const TargetTransformInfo &TTI,
73 RecurKind RdxKind, Value *Vec,
74 const Value *Root, FastMathFlags FMF,
75 const TTI::TargetCostKind CostKind) {
76 auto *VecTy = cast<FixedVectorType>(Val: Vec->getType());
77 unsigned VF = VecTy->getNumElements();
78 auto *I1VecTy = FixedVectorType::get(ElementType: Builder.getInt1Ty(), NumElts: VF);
79 DebugLoc DL = Builder.getCurrentDebugLocation();
80 Builder.SetCurrentDebugLocation(cast<Instruction>(Val: Root)->getDebugLoc());
81 Value *T = Builder.CreateTrunc(V: Vec, DestTy: I1VecTy);
82 Value *BC = Builder.CreateBitCast(V: T, DestTy: Builder.getIntNTy(N: VF));
83 CmpInst::Predicate Pred =
84 RdxKind == RecurKind::And ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
85 Constant *RHS = RdxKind == RecurKind::And
86 ? Constant::getAllOnesValue(Ty: BC->getType())
87 : Constant::getNullValue(Ty: BC->getType());
88 Value *Res = Builder.CreateICmp(P: Pred, LHS: BC, RHS);
89 // The costs are evaluated from the emitted instructions; they are dropped
90 // if the wide reduction form is cheaper.
91 auto CastCost = [&](Value *V, unsigned Opcode, Type *SrcTy) {
92 auto *I = dyn_cast<Instruction>(Val: V);
93 if (!I)
94 return InstructionCost(0);
95 return TTI.getCastInstrCost(Opcode, Dst: I->getType(), Src: SrcTy,
96 CCH: TTI.getCastContextHint(I), CostKind, I);
97 };
98 InstructionCost BitcastCmpCost = CastCost(T, Instruction::Trunc, VecTy) +
99 CastCost(BC, Instruction::BitCast, I1VecTy);
100 if (auto *Cmp = dyn_cast<Instruction>(Val: Res))
101 BitcastCmpCost += TTI.getCmpSelInstrCost(
102 Opcode: Instruction::ICmp, ValTy: BC->getType(), /*CondTy=*/nullptr, VecPred: Pred, CostKind,
103 Op1Info: TTI.getOperandInfo(V: BC), Op2Info: TTI.getOperandInfo(V: RHS), I: Cmp);
104 if (BitcastCmpCost >=
105 getBoolReduxWideRdxCost(TTI, RdxKind, VecTy, Root, FMF, CostKind)) {
106 for (Value *V : {Res, BC, T})
107 if (auto *I = dyn_cast<Instruction>(Val: V))
108 I->eraseFromParent();
109 Builder.SetCurrentDebugLocation(DL);
110 return nullptr;
111 }
112 Builder.SetCurrentDebugLocation(DL);
113 return Res;
114}
115
116} // namespace llvm::slpvectorizer
117