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/SmallPtrSet.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/Analysis/TargetTransformInfo.h"
22
23namespace llvm {
24class BasicBlock;
25class DataLayout;
26class DominatorTree;
27class FastMathFlags;
28class IRBuilderBase;
29class Instruction;
30class LoopInfo;
31class PHINode;
32class ScalarEvolution;
33class Type;
34class Value;
35enum class RecurKind;
36} // namespace llvm
37
38namespace llvm::slpvectorizer {
39
40struct NarrowedLeafInfo;
41
42/// The result of matching a boolean bitmask reduction over narrowed leaves.
43enum class BoolBitmask {
44 None, // not a boolean bitmask reduction
45 NoMask, // bitmask; the absorbed masks are redundant
46 NeedMask, // bitmask; the absorbed masks must be applied before the zero test
47};
48
49/// \returns the wide leaf type if the logical and/or reduction \p RdxKind
50/// with the i1 root type \p RootTy and the leaf type \p LeafTy is a
51/// booleanized reduction (performed in the wide leaf type, bit 0 of the
52/// result is the final value), nullptr otherwise.
53Type *getBoolReduxWideTy(RecurKind RdxKind, Type *RootTy, Type *LeafTy);
54
55/// \returns the BoolBitmask match if the or-reduction of the narrowed leaves
56/// packs each boolean (0 or 1 after masking) leaf into its own bit position
57/// 0..N-1, i.e. it is a bitcast of the per-lane zero tests to an iN integer;
58/// BoolBitmask::None otherwise.
59BoolBitmask isBoolBitmaskRdx(
60 RecurKind RdxKind,
61 const SmallDenseMap<Value *, NarrowedLeafInfo> &NarrowedLeafShifts,
62 const DataLayout &DL);
63
64/// Matches \p V as the zero-extended fields, placed one after another from the
65/// lowest bit and filling \p V completely. The instructions are looked through
66/// up to \p MaxDepth. Appends the fields in the order of their positions to
67/// \p Fields and the instructions of the pack to \p Chain.
68bool matchPackedFields(Value *V, unsigned MaxDepth,
69 SmallVectorImpl<Value *> &Fields,
70 SmallVectorImpl<Instruction *> &Chain);
71
72/// \returns the first operand of \p I that does not match \p Phi. If
73/// the operand is not an instruction, returns nullptr.
74Instruction *getNonPhiOperand(Instruction *I, PHINode *Phi);
75
76/// \returns true if \p I is a candidate instruction for reduction
77/// vectorization.
78bool isReductionCandidate(Instruction *I);
79
80/// Checks if the reduction, rooted at \p Root, reduces the loop accumulators,
81/// whose updates are the same expressions \p Shape in the same block, loading
82/// from consecutive addresses at each position. Such a reduction vectorizes
83/// along its own reduced values without gathers, while a tree across several
84/// such reductions transposes them. The different update expressions may form
85/// the nodes, which the other reductions, sharing them, cannot reuse. An empty
86/// \p Shape is set to the expressions of \p Root, \p Accs collects the
87/// accumulators.
88bool isReductionOfConsecutiveAccumulators(Instruction *Root, const LoopInfo &LI,
89 const DataLayout &DL,
90 ScalarEvolution &SE,
91 unsigned MaxDepth,
92 SmallVectorImpl<unsigned> &Shape,
93 SmallPtrSetImpl<PHINode *> &Accs);
94
95/// Emits the booleanized logical and/or reduction of \p Vec with the i1 root
96/// \p Root as trunc+bitcast+cmp (all-ones comparison for And, zero for Or) if
97/// it is cheaper than the wide reduction plus the result trunc. \returns the
98/// i1 result or nullptr if the wide reduction form is cheaper.
99Value *tryEmitBoolReduxBitcastCmp(IRBuilderBase &Builder,
100 const TargetTransformInfo &TTI,
101 RecurKind RdxKind, Value *Vec,
102 const Value *Root, FastMathFlags FMF,
103 TargetTransformInfo::TargetCostKind CostKind);
104
105/// Try to get a reduction instruction from phi node \p P in block \p ParentBB,
106/// considering incoming values from \p ParentBB or the containing loop latch.
107/// \returns a candidate reduction value, or nullptr if none.
108Instruction *getReductionInstr(const DominatorTree *DT, PHINode *P,
109 BasicBlock *ParentBB, LoopInfo *LI);
110
111/// Gets recurrence kind from the specified value.
112RecurKind getRdxKind(Value *V);
113
114} // namespace llvm::slpvectorizer
115
116#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPREDUCTIONUTILS_H
117