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#include "SLPUtils.h"
13
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/SmallBitVector.h"
16#include "llvm/Analysis/IVDescriptors.h"
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/Analysis/ValueTracking.h"
19#include "llvm/IR/Constants.h"
20#include "llvm/IR/DataLayout.h"
21#include "llvm/IR/DerivedTypes.h"
22#include "llvm/IR/Dominators.h"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/Instructions.h"
25#include "llvm/IR/Intrinsics.h"
26#include "llvm/IR/PatternMatch.h"
27#include "llvm/IR/Type.h"
28
29using namespace llvm;
30using namespace llvm::PatternMatch;
31
32namespace llvm::slpvectorizer {
33
34static bool matchRdxBop(Instruction *I, Value *&V0, Value *&V1) {
35 if (match(V: I, P: m_BinOp(L: m_Value(V&: V0), R: m_Value(V&: V1))))
36 return true;
37 if (match(V: I, P: m_FMaxNum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
38 return true;
39 if (match(V: I, P: m_FMinNum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
40 return true;
41 if (match(V: I, P: m_FMaximum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
42 return true;
43 if (match(V: I, P: m_FMinimum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
44 return true;
45 if (match(V: I, P: m_Intrinsic<Intrinsic::smax>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
46 return true;
47 if (match(V: I, P: m_Intrinsic<Intrinsic::smin>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
48 return true;
49 if (match(V: I, P: m_Intrinsic<Intrinsic::umax>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
50 return true;
51 if (match(V: I, P: m_Intrinsic<Intrinsic::umin>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
52 return true;
53 return false;
54}
55
56Instruction *getNonPhiOperand(Instruction *I, PHINode *Phi) {
57 Value *Op0 = nullptr;
58 Value *Op1 = nullptr;
59 if (!matchRdxBop(I, V0&: Op0, V1&: Op1))
60 return nullptr;
61 return dyn_cast<Instruction>(Val: Op0 == Phi ? Op1 : Op0);
62}
63
64bool isReductionCandidate(Instruction *I) {
65 bool IsSelect = match(V: I, P: m_Select(C: m_Value(), L: m_Value(), R: m_Value()));
66 Value *B0 = nullptr, *B1 = nullptr;
67 bool IsBinop = matchRdxBop(I, V0&: B0, V1&: B1);
68 return IsBinop || IsSelect;
69}
70
71Type *getBoolReduxWideTy(RecurKind RdxKind, Type *RootTy, Type *LeafTy) {
72 if ((RdxKind == RecurKind::And || RdxKind == RecurKind::Or) &&
73 RootTy->isIntegerTy(BitWidth: 1) && LeafTy->isIntegerTy() &&
74 !LeafTy->isIntegerTy(BitWidth: 1))
75 return LeafTy;
76 return nullptr;
77}
78
79BoolBitmask isBoolBitmaskRdx(
80 RecurKind RdxKind,
81 const SmallDenseMap<Value *, NarrowedLeafInfo> &NarrowedLeafShifts,
82 const DataLayout &DL) {
83 if (RdxKind != RecurKind::Or || DL.isBigEndian() ||
84 NarrowedLeafShifts.empty())
85 return BoolBitmask::None;
86 unsigned NumLeaves = NarrowedLeafShifts.size();
87 SmallBitVector Seen(NumLeaves);
88 bool NeedMask = false;
89 for (const auto &[V, L] : NarrowedLeafShifts) {
90 if (L.Shift >= NumLeaves || Seen.test(Idx: L.Shift))
91 return BoolBitmask::None;
92 Seen.set(L.Shift);
93 KnownBits Known = computeKnownBits(V, DL);
94 // The masked leaf must be known to be 0 or 1.
95 if ((L.Mask & ~Known.Zero).ugt(RHS: 1))
96 return BoolBitmask::None;
97 // The mask is redundant if it keeps all not-known-zero bits.
98 NeedMask |= !(Known.Zero | L.Mask).isAllOnes();
99 }
100 return NeedMask ? BoolBitmask::NeedMask : BoolBitmask::NoMask;
101}
102
103bool matchPackedFields(Value *V, unsigned MaxDepth,
104 SmallVectorImpl<Value *> &Fields,
105 SmallVectorImpl<Instruction *> &Chain) {
106 auto *PackTy = dyn_cast<IntegerType>(Val: V->getType());
107 if (!PackTy)
108 return false;
109 SmallVector<NarrowedLeafInfo> Leaves;
110 collectNarrowedLeaves(V, RdxOpcode: Instruction::Or, WideBW: PackTy->getBitWidth(), MaxDepth,
111 Leaves, ChainInsts&: Chain);
112 if (Leaves.size() < 2)
113 return false;
114 Type *FieldTy = Leaves.front().V->getType();
115 if (!FieldTy->isIntegerTy() ||
116 PackTy->getBitWidth() != Leaves.size() * FieldTy->getIntegerBitWidth())
117 return false;
118 llvm::sort(C&: Leaves, Comp: [](const NarrowedLeafInfo &A, const NarrowedLeafInfo &B) {
119 return A.Shift < B.Shift;
120 });
121 for (const auto &[Pos, L] : enumerate(First&: Leaves))
122 if (L.V->getType() != FieldTy || !L.Mask.isAllOnes() ||
123 L.Shift != Pos * FieldTy->getIntegerBitWidth())
124 return false;
125 append_range(
126 C&: Fields, R: map_range(C&: Leaves, F: [](const NarrowedLeafInfo &L) { return L.V; }));
127 return true;
128}
129
130Value *tryEmitBoolReduxBitcastCmp(IRBuilderBase &Builder,
131 const TargetTransformInfo &TTI,
132 RecurKind RdxKind, Value *Vec,
133 const Value *Root, FastMathFlags FMF,
134 const TTI::TargetCostKind CostKind) {
135 auto *VecTy = cast<FixedVectorType>(Val: Vec->getType());
136 unsigned VF = VecTy->getNumElements();
137 auto *I1VecTy = FixedVectorType::get(ElementType: Builder.getInt1Ty(), NumElts: VF);
138 DebugLoc DL = Builder.getCurrentDebugLocation();
139 Builder.SetCurrentDebugLocation(cast<Instruction>(Val: Root)->getDebugLoc());
140 Value *T = Builder.CreateTrunc(V: Vec, DestTy: I1VecTy);
141 Value *BC = Builder.CreateBitCast(V: T, DestTy: Builder.getIntNTy(N: VF));
142 CmpInst::Predicate Pred =
143 RdxKind == RecurKind::And ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
144 Constant *RHS = RdxKind == RecurKind::And
145 ? Constant::getAllOnesValue(Ty: BC->getType())
146 : Constant::getNullValue(Ty: BC->getType());
147 Value *Res = Builder.CreateICmp(P: Pred, LHS: BC, RHS);
148 // The costs are evaluated from the emitted instructions; they are dropped
149 // if the wide reduction form is cheaper.
150 auto CastCost = [&](Value *V, unsigned Opcode, Type *SrcTy) {
151 auto *I = dyn_cast<Instruction>(Val: V);
152 if (!I)
153 return InstructionCost(0);
154 return TTI.getCastInstrCost(Opcode, Dst: I->getType(), Src: SrcTy,
155 CCH: TTI.getCastContextHint(I), CostKind, I);
156 };
157 InstructionCost BitcastCmpCost = CastCost(T, Instruction::Trunc, VecTy) +
158 CastCost(BC, Instruction::BitCast, I1VecTy);
159 if (auto *Cmp = dyn_cast<Instruction>(Val: Res))
160 BitcastCmpCost += TTI.getCmpSelInstrCost(
161 Opcode: Instruction::ICmp, ValTy: BC->getType(), /*CondTy=*/nullptr, VecPred: Pred, CostKind,
162 Op1Info: TTI.getOperandInfo(V: BC), Op2Info: TTI.getOperandInfo(V: RHS), I: Cmp);
163 if (BitcastCmpCost >=
164 getBoolReduxWideRdxCost(TTI, RdxKind, VecTy, Root, FMF, CostKind)) {
165 for (Value *V : {Res, BC, T})
166 if (auto *I = dyn_cast<Instruction>(Val: V))
167 I->eraseFromParent();
168 Builder.SetCurrentDebugLocation(DL);
169 return nullptr;
170 }
171 Builder.SetCurrentDebugLocation(DL);
172 return Res;
173}
174
175Instruction *getReductionInstr(const DominatorTree *DT, PHINode *P,
176 BasicBlock *ParentBB, LoopInfo *LI) {
177 // There are situations where the reduction value is not dominated by the
178 // reduction phi. Vectorizing such cases has been reported to cause
179 // miscompiles. See PR25787.
180 auto DominatedReduxValue = [&](Value *R) {
181 return isa<Instruction>(Val: R) &&
182 DT->dominates(A: P->getParent(), B: cast<Instruction>(Val: R)->getParent());
183 };
184
185 Instruction *Rdx = nullptr;
186
187 // Return the incoming value if it comes from the same BB as the phi node.
188 if (P->getIncomingBlock(i: 0) == ParentBB) {
189 Rdx = dyn_cast<Instruction>(Val: P->getIncomingValue(i: 0));
190 } else if (P->getIncomingBlock(i: 1) == ParentBB) {
191 Rdx = dyn_cast<Instruction>(Val: P->getIncomingValue(i: 1));
192 }
193
194 if (Rdx && DominatedReduxValue(Rdx))
195 return Rdx;
196
197 // Otherwise, check whether we have a loop latch to look at.
198 Loop *BBL = LI->getLoopFor(BB: ParentBB);
199 if (!BBL)
200 return nullptr;
201 BasicBlock *BBLatch = BBL->getLoopLatch();
202 if (!BBLatch)
203 return nullptr;
204
205 // There is a loop latch, return the incoming value if it comes from
206 // that. This reduction pattern occasionally turns up.
207 if (P->getIncomingBlock(i: 0) == BBLatch) {
208 Rdx = dyn_cast<Instruction>(Val: P->getIncomingValue(i: 0));
209 } else if (P->getIncomingBlock(i: 1) == BBLatch) {
210 Rdx = dyn_cast<Instruction>(Val: P->getIncomingValue(i: 1));
211 }
212
213 if (Rdx && DominatedReduxValue(Rdx))
214 return Rdx;
215
216 return nullptr;
217}
218
219} // namespace llvm::slpvectorizer
220