1//===- SLPReductionUtils.h - SLP reduction match helpers -------*- C++ -*-===//
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// Internal header used by SLPVectorizer.cpp. It declares free reduction
10// pattern-match helpers that do not depend on BoUpSLP or any other SLP-private
11// type.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPREDUCTIONUTILS_H
16#define LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPREDUCTIONUTILS_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Analysis/TargetTransformInfo.h"
21
22namespace llvm {
23class BasicBlock;
24class DataLayout;
25class DominatorTree;
26class FastMathFlags;
27class IRBuilderBase;
28class Instruction;
29class LoopInfo;
30class PHINode;
31class Type;
32class Value;
33enum class RecurKind;
34} // namespace llvm
35
36namespace llvm::slpvectorizer {
37
38struct NarrowedLeafInfo;
39
40/// The result of matching a boolean bitmask reduction over narrowed leaves.
41enum class BoolBitmask {
42 None, // not a boolean bitmask reduction
43 NoMask, // bitmask; the absorbed masks are redundant
44 NeedMask, // bitmask; the absorbed masks must be applied before the zero test
45};
46
47/// \returns the wide leaf type if the logical and/or reduction \p RdxKind
48/// with the i1 root type \p RootTy and the leaf type \p LeafTy is a
49/// booleanized reduction (performed in the wide leaf type, bit 0 of the
50/// result is the final value), nullptr otherwise.
51Type *getBoolReduxWideTy(RecurKind RdxKind, Type *RootTy, Type *LeafTy);
52
53/// \returns the BoolBitmask match if the or-reduction of the narrowed leaves
54/// packs each boolean (0 or 1 after masking) leaf into its own bit position
55/// 0..N-1, i.e. it is a bitcast of the per-lane zero tests to an iN integer;
56/// BoolBitmask::None otherwise.
57BoolBitmask isBoolBitmaskRdx(
58 RecurKind RdxKind,
59 const SmallDenseMap<Value *, NarrowedLeafInfo> &NarrowedLeafShifts,
60 const DataLayout &DL);
61
62/// Matches \p V as the zero-extended fields, placed one after another from the
63/// lowest bit and filling \p V completely. The instructions are looked through
64/// up to \p MaxDepth. Appends the fields in the order of their positions to
65/// \p Fields and the instructions of the pack to \p Chain.
66bool matchPackedFields(Value *V, unsigned MaxDepth,
67 SmallVectorImpl<Value *> &Fields,
68 SmallVectorImpl<Instruction *> &Chain);
69
70/// \returns the first operand of \p I that does not match \p Phi. If
71/// the operand is not an instruction, returns nullptr.
72Instruction *getNonPhiOperand(Instruction *I, PHINode *Phi);
73
74/// \returns true if \p I is a candidate instruction for reduction
75/// vectorization.
76bool isReductionCandidate(Instruction *I);
77
78/// Emits the booleanized logical and/or reduction of \p Vec with the i1 root
79/// \p Root as trunc+bitcast+cmp (all-ones comparison for And, zero for Or) if
80/// it is cheaper than the wide reduction plus the result trunc. \returns the
81/// i1 result or nullptr if the wide reduction form is cheaper.
82Value *tryEmitBoolReduxBitcastCmp(IRBuilderBase &Builder,
83 const TargetTransformInfo &TTI,
84 RecurKind RdxKind, Value *Vec,
85 const Value *Root, FastMathFlags FMF,
86 TargetTransformInfo::TargetCostKind CostKind);
87
88/// Try to get a reduction instruction from phi node \p P in block \p ParentBB,
89/// considering incoming values from \p ParentBB or the containing loop latch.
90/// \returns a candidate reduction value, or nullptr if none.
91Instruction *getReductionInstr(const DominatorTree *DT, PHINode *P,
92 BasicBlock *ParentBB, LoopInfo *LI);
93
94} // namespace llvm::slpvectorizer
95
96#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPREDUCTIONUTILS_H
97