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/Sequence.h"
16#include "llvm/ADT/SmallBitVector.h"
17#include "llvm/Analysis/IVDescriptors.h"
18#include "llvm/Analysis/LoopAccessAnalysis.h"
19#include "llvm/Analysis/LoopInfo.h"
20#include "llvm/Analysis/ValueTracking.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/DerivedTypes.h"
23#include "llvm/IR/Dominators.h"
24#include "llvm/IR/IRBuilder.h"
25#include "llvm/IR/Instructions.h"
26#include "llvm/IR/Intrinsics.h"
27#include "llvm/IR/PatternMatch.h"
28#include "llvm/IR/Type.h"
29
30using namespace llvm;
31using namespace llvm::PatternMatch;
32
33namespace llvm::slpvectorizer {
34
35static bool matchRdxBop(Instruction *I, Value *&V0, Value *&V1) {
36 if (match(V: I, P: m_BinOp(L: m_Value(V&: V0), R: m_Value(V&: V1))))
37 return true;
38 if (match(V: I, P: m_FMaxNum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
39 return true;
40 if (match(V: I, P: m_FMinNum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
41 return true;
42 if (match(V: I, P: m_FMaximum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
43 return true;
44 if (match(V: I, P: m_FMinimum(Op0: m_Value(V&: V0), Op1: m_Value(V&: V1))))
45 return true;
46 if (match(V: I, P: m_Intrinsic<Intrinsic::smax>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
47 return true;
48 if (match(V: I, P: m_Intrinsic<Intrinsic::smin>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
49 return true;
50 if (match(V: I, P: m_Intrinsic<Intrinsic::umax>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
51 return true;
52 if (match(V: I, P: m_Intrinsic<Intrinsic::umin>(Ops: m_Value(V&: V0), Ops: m_Value(V&: V1))))
53 return true;
54 return false;
55}
56
57Instruction *getNonPhiOperand(Instruction *I, PHINode *Phi) {
58 Value *Op0 = nullptr;
59 Value *Op1 = nullptr;
60 if (!matchRdxBop(I, V0&: Op0, V1&: Op1))
61 return nullptr;
62 return dyn_cast<Instruction>(Val: Op0 == Phi ? Op1 : Op0);
63}
64
65bool isReductionCandidate(Instruction *I) {
66 bool IsSelect = match(V: I, P: m_Select(C: m_Value(), L: m_Value(), R: m_Value()));
67 Value *B0 = nullptr, *B1 = nullptr;
68 bool IsBinop = matchRdxBop(I, V0&: B0, V1&: B1);
69 return IsBinop || IsSelect;
70}
71
72Type *getBoolReduxWideTy(RecurKind RdxKind, Type *RootTy, Type *LeafTy) {
73 if ((RdxKind == RecurKind::And || RdxKind == RecurKind::Or) &&
74 RootTy->isIntegerTy(BitWidth: 1) && LeafTy->isIntegerTy() &&
75 !LeafTy->isIntegerTy(BitWidth: 1))
76 return LeafTy;
77 return nullptr;
78}
79
80BoolBitmask isBoolBitmaskRdx(
81 RecurKind RdxKind,
82 const SmallDenseMap<Value *, NarrowedLeafInfo> &NarrowedLeafShifts,
83 const DataLayout &DL) {
84 if (RdxKind != RecurKind::Or || DL.isBigEndian() ||
85 NarrowedLeafShifts.empty())
86 return BoolBitmask::None;
87 unsigned NumLeaves = NarrowedLeafShifts.size();
88 SmallBitVector Seen(NumLeaves);
89 bool NeedMask = false;
90 for (const auto &[V, L] : NarrowedLeafShifts) {
91 if (L.Shift >= NumLeaves || Seen.test(Idx: L.Shift))
92 return BoolBitmask::None;
93 Seen.set(L.Shift);
94 KnownBits Known = computeKnownBits(V, DL);
95 // The masked leaf must be known to be 0 or 1.
96 if ((L.Mask & ~Known.Zero).ugt(RHS: 1))
97 return BoolBitmask::None;
98 // The mask is redundant if it keeps all not-known-zero bits.
99 NeedMask |= !(Known.Zero | L.Mask).isAllOnes();
100 }
101 return NeedMask ? BoolBitmask::NeedMask : BoolBitmask::NoMask;
102}
103
104bool matchPackedFields(Value *V, unsigned MaxDepth,
105 SmallVectorImpl<Value *> &Fields,
106 SmallVectorImpl<Instruction *> &Chain) {
107 auto *PackTy = dyn_cast<IntegerType>(Val: V->getType());
108 if (!PackTy)
109 return false;
110 SmallVector<NarrowedLeafInfo> Leaves;
111 collectNarrowedLeaves(V, RdxOpcode: Instruction::Or, WideBW: PackTy->getBitWidth(), MaxDepth,
112 Leaves, ChainInsts&: Chain);
113 if (Leaves.size() < 2)
114 return false;
115 Type *FieldTy = Leaves.front().V->getType();
116 if (!FieldTy->isIntegerTy() ||
117 PackTy->getBitWidth() != Leaves.size() * FieldTy->getIntegerBitWidth())
118 return false;
119 llvm::sort(C&: Leaves, Comp: [](const NarrowedLeafInfo &A, const NarrowedLeafInfo &B) {
120 return A.Shift < B.Shift;
121 });
122 for (const auto &[Pos, L] : enumerate(First&: Leaves))
123 if (L.V->getType() != FieldTy || !L.Mask.isAllOnes() ||
124 L.Shift != Pos * FieldTy->getIntegerBitWidth())
125 return false;
126 append_range(
127 C&: Fields, R: map_range(C&: Leaves, F: [](const NarrowedLeafInfo &L) { return L.V; }));
128 return true;
129}
130
131Value *tryEmitBoolReduxBitcastCmp(IRBuilderBase &Builder,
132 const TargetTransformInfo &TTI,
133 RecurKind RdxKind, Value *Vec,
134 const Value *Root, FastMathFlags FMF,
135 const TTI::TargetCostKind CostKind) {
136 auto *VecTy = cast<FixedVectorType>(Val: Vec->getType());
137 unsigned VF = VecTy->getNumElements();
138 auto *I1VecTy = FixedVectorType::get(ElementType: Builder.getInt1Ty(), NumElts: VF);
139 DebugLoc DL = Builder.getCurrentDebugLocation();
140 Builder.SetCurrentDebugLocation(cast<Instruction>(Val: Root)->getDebugLoc());
141 Value *T = Builder.CreateTrunc(V: Vec, DestTy: I1VecTy);
142 Value *BC = Builder.CreateBitCast(V: T, DestTy: Builder.getIntNTy(N: VF));
143 CmpInst::Predicate Pred =
144 RdxKind == RecurKind::And ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
145 Constant *RHS = RdxKind == RecurKind::And
146 ? Constant::getAllOnesValue(Ty: BC->getType())
147 : Constant::getNullValue(Ty: BC->getType());
148 Value *Res = Builder.CreateICmp(P: Pred, LHS: BC, RHS);
149 // The costs are evaluated from the emitted instructions; they are dropped
150 // if the wide reduction form is cheaper.
151 auto CastCost = [&](Value *V, unsigned Opcode, Type *SrcTy) {
152 auto *I = dyn_cast<Instruction>(Val: V);
153 if (!I)
154 return InstructionCost(0);
155 return TTI.getCastInstrCost(Opcode, Dst: I->getType(), Src: SrcTy,
156 CCH: TTI.getCastContextHint(I), CostKind, I);
157 };
158 InstructionCost BitcastCmpCost = CastCost(T, Instruction::Trunc, VecTy) +
159 CastCost(BC, Instruction::BitCast, I1VecTy);
160 if (auto *Cmp = dyn_cast<Instruction>(Val: Res))
161 BitcastCmpCost += TTI.getCmpSelInstrCost(
162 Opcode: Instruction::ICmp, ValTy: BC->getType(), /*CondTy=*/nullptr, VecPred: Pred, CostKind,
163 Op1Info: TTI.getOperandInfo(V: BC), Op2Info: TTI.getOperandInfo(V: RHS), I: Cmp);
164 if (BitcastCmpCost >=
165 getBoolReduxWideRdxCost(TTI, RdxKind, VecTy, Root, FMF, CostKind)) {
166 for (Value *V : {Res, BC, T})
167 if (auto *I = dyn_cast<Instruction>(Val: V))
168 I->eraseFromParent();
169 Builder.SetCurrentDebugLocation(DL);
170 return nullptr;
171 }
172 Builder.SetCurrentDebugLocation(DL);
173 return Res;
174}
175
176Instruction *getReductionInstr(const DominatorTree *DT, PHINode *P,
177 BasicBlock *ParentBB, LoopInfo *LI) {
178 // There are situations where the reduction value is not dominated by the
179 // reduction phi. Vectorizing such cases has been reported to cause
180 // miscompiles. See PR25787.
181 auto DominatedReduxValue = [&](Value *R) {
182 return isa<Instruction>(Val: R) &&
183 DT->dominates(A: P->getParent(), B: cast<Instruction>(Val: R)->getParent());
184 };
185
186 Instruction *Rdx = nullptr;
187
188 // Return the incoming value if it comes from the same BB as the phi node.
189 if (P->getIncomingBlock(i: 0) == ParentBB) {
190 Rdx = dyn_cast<Instruction>(Val: P->getIncomingValue(i: 0));
191 } else if (P->getIncomingBlock(i: 1) == ParentBB) {
192 Rdx = dyn_cast<Instruction>(Val: P->getIncomingValue(i: 1));
193 }
194
195 if (Rdx && DominatedReduxValue(Rdx))
196 return Rdx;
197
198 // Otherwise, check whether we have a loop latch to look at.
199 Loop *BBL = LI->getLoopFor(BB: ParentBB);
200 if (!BBL)
201 return nullptr;
202 BasicBlock *BBLatch = BBL->getLoopLatch();
203 if (!BBLatch)
204 return nullptr;
205
206 // There is a loop latch, return the incoming value if it comes from
207 // that. This reduction pattern occasionally turns up.
208 if (P->getIncomingBlock(i: 0) == BBLatch) {
209 Rdx = dyn_cast<Instruction>(Val: P->getIncomingValue(i: 0));
210 } else if (P->getIncomingBlock(i: 1) == BBLatch) {
211 Rdx = dyn_cast<Instruction>(Val: P->getIncomingValue(i: 1));
212 }
213
214 if (Rdx && DominatedReduxValue(Rdx))
215 return Rdx;
216
217 return nullptr;
218}
219
220bool isReductionOfConsecutiveAccumulators(Instruction *Root, const LoopInfo &LI,
221 const DataLayout &DL,
222 ScalarEvolution &SE,
223 unsigned MaxDepth,
224 SmallVectorImpl<unsigned> &Shape,
225 SmallPtrSetImpl<PHINode *> &Accs) {
226 SmallVector<Instruction *> RdxVals;
227 SmallVector<Instruction *> Worklist(1, Root);
228 while (!Worklist.empty()) {
229 for (Value *Op : Worklist.pop_back_val()->operands()) {
230 auto *I = dyn_cast<Instruction>(Val: Op);
231 if (!I)
232 return false;
233 if (I->getOpcode() == Root->getOpcode() &&
234 I->getParent() == Root->getParent() && I->hasOneUse() &&
235 isReductionCandidate(I))
236 Worklist.push_back(Elt: I);
237 else
238 RdxVals.push_back(Elt: I);
239 }
240 }
241 constexpr unsigned MinReducedVals = 4;
242 BasicBlock *BB = RdxVals.front()->getParent();
243 const Loop *L = LI.getLoopFor(BB);
244 if (RdxVals.size() < MinReducedVals || !L || L->contains(Inst: Root) ||
245 any_of(Range&: RdxVals, P: [&](Instruction *I) { return I->getParent() != BB; }))
246 return false;
247 // The accumulators, used by the other ones, cannot be vectorized along the
248 // reduced values without the shuffles in the loop.
249 auto GetAccumulator = [&](Instruction *RdxVal) -> PHINode * {
250 PHINode *Acc = nullptr;
251 for (User *U : RdxVal->users()) {
252 if (!L->contains(Inst: cast<Instruction>(Val: U)))
253 continue;
254 auto *P = dyn_cast<PHINode>(Val: U);
255 if (Acc || !P || P->getParent() != L->getHeader() || !P->hasOneUse())
256 return nullptr;
257 Acc = P;
258 }
259 return Acc;
260 };
261 SmallVector<SmallVector<LoadInst *>> Loads;
262 for (Instruction *RdxVal : RdxVals) {
263 PHINode *Acc = GetAccumulator(RdxVal);
264 if (!Acc)
265 return false;
266 Accs.insert(Ptr: Acc);
267 SmallVectorImpl<LoadInst *> &RdxLoads = Loads.emplace_back();
268 SmallVector<unsigned> RdxShape;
269 SmallPtrSet<Instruction *, 16> Visited;
270 SmallVector<std::pair<Instruction *, unsigned>> Stack(1, {RdxVal, 0});
271 while (!Stack.empty()) {
272 auto [I, Depth] = Stack.pop_back_val();
273 if (!Visited.insert(Ptr: I).second)
274 continue;
275 if (I != Acc && isa<PHINode>(Val: I) && I->getParent() == L->getHeader())
276 return false;
277 if (auto *LdI = dyn_cast<LoadInst>(Val: I)) {
278 RdxLoads.push_back(Elt: LdI);
279 RdxShape.push_back(Elt: I->getOpcode());
280 continue;
281 }
282 if (Depth == MaxDepth || isa<PHINode>(Val: I) || I->getParent() != BB)
283 continue;
284 RdxShape.push_back(Elt: I->getOpcode());
285 if (auto *Cmp = dyn_cast<CmpInst>(Val: I))
286 RdxShape.push_back(Elt: Cmp->getPredicate());
287 for (Value *Op : reverse(C: I->operands()))
288 if (auto *OpI = dyn_cast<Instruction>(Val: Op))
289 Stack.emplace_back(Args&: OpI, Args: Depth + 1);
290 }
291 if (RdxLoads.empty() || !Visited.contains(Ptr: Acc))
292 return false;
293 if (Shape.empty())
294 Shape.assign(in_start: RdxShape.begin(), in_end: RdxShape.end());
295 else if (RdxShape != Shape)
296 return false;
297 }
298 return all_of(Range: seq<unsigned>(Size: Loads.front().size()), P: [&](unsigned Pos) {
299 LoadInst *Ld0 = Loads.front()[Pos];
300 SmallVector<int64_t> Offsets;
301 for (ArrayRef<LoadInst *> RdxLoads : Loads) {
302 std::optional<int64_t> Diff = getPointersDiff(
303 ElemTyA: Ld0->getType(), PtrA: Ld0->getPointerOperand(), ElemTyB: RdxLoads[Pos]->getType(),
304 PtrB: RdxLoads[Pos]->getPointerOperand(), DL, SE);
305 if (!Diff)
306 return false;
307 Offsets.push_back(Elt: *Diff);
308 }
309 sort(C&: Offsets);
310 return all_of(Range: enumerate(First&: Offsets), P: [&](const auto &P) {
311 return P.value() == Offsets.front() + static_cast<int64_t>(P.index());
312 });
313 });
314}
315
316RecurKind getRdxKind(Value *V) {
317 auto *I = dyn_cast<Instruction>(Val: V);
318 if (!I)
319 return RecurKind::None;
320 if (match(V: I, P: m_Add(L: m_Value(), R: m_Value())))
321 return RecurKind::Add;
322 if (match(V: I, P: m_Mul(L: m_Value(), R: m_Value())))
323 return RecurKind::Mul;
324 if (match(V: I, P: m_And(L: m_Value(), R: m_Value())) ||
325 match(V: I, P: m_LogicalAnd(L: m_Value(), R: m_Value())))
326 return RecurKind::And;
327 if (match(V: I, P: m_Or(L: m_Value(), R: m_Value())) ||
328 match(V: I, P: m_LogicalOr(L: m_Value(), R: m_Value())))
329 return RecurKind::Or;
330 if (match(V: I, P: m_Xor(L: m_Value(), R: m_Value())))
331 return RecurKind::Xor;
332 if (match(V: I, P: m_FAdd(L: m_Value(), R: m_Value())))
333 return RecurKind::FAdd;
334 if (match(V: I, P: m_FMul(L: m_Value(), R: m_Value())))
335 return RecurKind::FMul;
336
337 if (match(V: I, P: m_Intrinsic<Intrinsic::maxnum>(Ops: m_Value(), Ops: m_Value())))
338 return RecurKind::FMax;
339 if (match(V: I, P: m_Intrinsic<Intrinsic::minnum>(Ops: m_Value(), Ops: m_Value())))
340 return RecurKind::FMin;
341
342 if (match(V: I, P: m_FMaximum(Op0: m_Value(), Op1: m_Value())))
343 return RecurKind::FMaximum;
344 if (match(V: I, P: m_FMinimum(Op0: m_Value(), Op1: m_Value())))
345 return RecurKind::FMinimum;
346 // TODO: remove several special-case paths that deal with selects.
347 if (match(V: I, P: m_SMax(Op0: m_Value(), Op1: m_Value())))
348 return RecurKind::SMax;
349 if (match(V: I, P: m_SMin(Op0: m_Value(), Op1: m_Value())))
350 return RecurKind::SMin;
351 if (match(V: I, P: m_UMax(Op0: m_Value(), Op1: m_Value())))
352 return RecurKind::UMax;
353 if (match(V: I, P: m_UMin(Op0: m_Value(), Op1: m_Value())))
354 return RecurKind::UMin;
355
356 if (auto *Select = dyn_cast<SelectInst>(Val: I)) {
357 // Try harder: look for min/max pattern based on instructions producing
358 // same values such as: select ((cmp Inst1, Inst2), Inst1, Inst2).
359 // During the intermediate stages of SLP, it's very common to have
360 // pattern like this (since optimizeGatherSequence is run only once
361 // at the end):
362 // %1 = extractelement <2 x i32> %a, i32 0
363 // %2 = extractelement <2 x i32> %a, i32 1
364 // %cond = icmp sgt i32 %1, %2
365 // %3 = extractelement <2 x i32> %a, i32 0
366 // %4 = extractelement <2 x i32> %a, i32 1
367 // %select = select i1 %cond, i32 %3, i32 %4
368 CmpPredicate Pred;
369 Instruction *L1;
370 Instruction *L2;
371
372 Value *LHS = Select->getTrueValue();
373 Value *RHS = Select->getFalseValue();
374 Value *Cond = Select->getCondition();
375
376 // TODO: Support inverse predicates.
377 if (match(V: Cond, P: m_Cmp(Pred, L: m_Specific(V: LHS), R: m_Instruction(I&: L2)))) {
378 if (!isa<ExtractElementInst>(Val: RHS) ||
379 !L2->isIdenticalTo(I: cast<Instruction>(Val: RHS)))
380 return RecurKind::None;
381 } else if (match(V: Cond, P: m_Cmp(Pred, L: m_Instruction(I&: L1), R: m_Specific(V: RHS)))) {
382 if (!isa<ExtractElementInst>(Val: LHS) ||
383 !L1->isIdenticalTo(I: cast<Instruction>(Val: LHS)))
384 return RecurKind::None;
385 } else {
386 if (!isa<ExtractElementInst>(Val: LHS) || !isa<ExtractElementInst>(Val: RHS))
387 return RecurKind::None;
388 if (!match(V: Cond, P: m_Cmp(Pred, L: m_Instruction(I&: L1), R: m_Instruction(I&: L2))) ||
389 !L1->isIdenticalTo(I: cast<Instruction>(Val: LHS)) ||
390 !L2->isIdenticalTo(I: cast<Instruction>(Val: RHS)))
391 return RecurKind::None;
392 }
393
394 switch (Pred) {
395 default:
396 return RecurKind::None;
397 case CmpInst::ICMP_SGT:
398 case CmpInst::ICMP_SGE:
399 return RecurKind::SMax;
400 case CmpInst::ICMP_SLT:
401 case CmpInst::ICMP_SLE:
402 return RecurKind::SMin;
403 case CmpInst::ICMP_UGT:
404 case CmpInst::ICMP_UGE:
405 return RecurKind::UMax;
406 case CmpInst::ICMP_ULT:
407 case CmpInst::ICMP_ULE:
408 return RecurKind::UMin;
409 }
410 }
411 return RecurKind::None;
412}
413
414} // namespace llvm::slpvectorizer
415