10b57cec5SDimitry Andric //===- VPlan.h - Represent A Vectorizer Plan --------------------*- C++ -*-===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric /// \file
100b57cec5SDimitry Andric /// This file contains the declarations of the Vectorization Plan base classes:
110b57cec5SDimitry Andric /// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual
120b57cec5SDimitry Andric /// VPBlockBase, together implementing a Hierarchical CFG;
13bdd1243dSDimitry Andric /// 2. Pure virtual VPRecipeBase serving as the base class for recipes contained
140b57cec5SDimitry Andric /// within VPBasicBlocks;
157a6dacacSDimitry Andric /// 3. Pure virtual VPSingleDefRecipe serving as a base class for recipes that
167a6dacacSDimitry Andric /// also inherit from VPValue.
177a6dacacSDimitry Andric /// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned
180b57cec5SDimitry Andric /// instruction;
197a6dacacSDimitry Andric /// 5. The VPlan class holding a candidate for vectorization;
207a6dacacSDimitry Andric /// 6. The VPlanPrinter class providing a way to print a plan in dot format;
210b57cec5SDimitry Andric /// These are documented in docs/VectorizationPlan.rst.
220b57cec5SDimitry Andric //
230b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
240b57cec5SDimitry Andric
250b57cec5SDimitry Andric #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
260b57cec5SDimitry Andric #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
270b57cec5SDimitry Andric
285f757f3fSDimitry Andric #include "VPlanAnalysis.h"
290b57cec5SDimitry Andric #include "VPlanValue.h"
300b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h"
3181ad6265SDimitry Andric #include "llvm/ADT/MapVector.h"
32480093f4SDimitry Andric #include "llvm/ADT/SmallBitVector.h"
330b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h"
340b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h"
350b57cec5SDimitry Andric #include "llvm/ADT/Twine.h"
360b57cec5SDimitry Andric #include "llvm/ADT/ilist.h"
370b57cec5SDimitry Andric #include "llvm/ADT/ilist_node.h"
3806c3fb27SDimitry Andric #include "llvm/Analysis/IVDescriptors.h"
3981ad6265SDimitry Andric #include "llvm/Analysis/LoopInfo.h"
400b57cec5SDimitry Andric #include "llvm/Analysis/VectorUtils.h"
410eae32dcSDimitry Andric #include "llvm/IR/DebugLoc.h"
4281ad6265SDimitry Andric #include "llvm/IR/FMF.h"
4306c3fb27SDimitry Andric #include "llvm/IR/Operator.h"
440b57cec5SDimitry Andric #include <algorithm>
450b57cec5SDimitry Andric #include <cassert>
460b57cec5SDimitry Andric #include <cstddef>
470b57cec5SDimitry Andric #include <string>
480b57cec5SDimitry Andric
490b57cec5SDimitry Andric namespace llvm {
500b57cec5SDimitry Andric
510b57cec5SDimitry Andric class BasicBlock;
520b57cec5SDimitry Andric class DominatorTree;
530b57cec5SDimitry Andric class InnerLoopVectorizer;
5481ad6265SDimitry Andric class IRBuilderBase;
550b57cec5SDimitry Andric class LoopInfo;
560b57cec5SDimitry Andric class raw_ostream;
57e8d8bef9SDimitry Andric class RecurrenceDescriptor;
58bdd1243dSDimitry Andric class SCEV;
59bdd1243dSDimitry Andric class Type;
600b57cec5SDimitry Andric class VPBasicBlock;
610b57cec5SDimitry Andric class VPRegionBlock;
620b57cec5SDimitry Andric class VPlan;
634824e7fdSDimitry Andric class VPReplicateRecipe;
640b57cec5SDimitry Andric class VPlanSlp;
65bdd1243dSDimitry Andric class Value;
6606c3fb27SDimitry Andric class LoopVersioning;
67bdd1243dSDimitry Andric
68bdd1243dSDimitry Andric namespace Intrinsic {
69bdd1243dSDimitry Andric typedef unsigned ID;
70bdd1243dSDimitry Andric }
710b57cec5SDimitry Andric
72fe6060f1SDimitry Andric /// Returns a calculation for the total number of elements for a given \p VF.
73fe6060f1SDimitry Andric /// For fixed width vectors this value is a constant, whereas for scalable
74fe6060f1SDimitry Andric /// vectors it is an expression determined at runtime.
7581ad6265SDimitry Andric Value *getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF);
76fe6060f1SDimitry Andric
7704eeddc0SDimitry Andric /// Return a value for Step multiplied by VF.
7881ad6265SDimitry Andric Value *createStepForVF(IRBuilderBase &B, Type *Ty, ElementCount VF,
7981ad6265SDimitry Andric int64_t Step);
8004eeddc0SDimitry Andric
8106c3fb27SDimitry Andric const SCEV *createTripCountSCEV(Type *IdxTy, PredicatedScalarEvolution &PSE,
8206c3fb27SDimitry Andric Loop *CurLoop = nullptr);
83bdd1243dSDimitry Andric
840b57cec5SDimitry Andric /// A range of powers-of-2 vectorization factors with fixed start and
850b57cec5SDimitry Andric /// adjustable end. The range includes start and excludes end, e.g.,:
8606c3fb27SDimitry Andric /// [1, 16) = {1, 2, 4, 8}
870b57cec5SDimitry Andric struct VFRange {
880b57cec5SDimitry Andric // A power of 2.
89e8d8bef9SDimitry Andric const ElementCount Start;
900b57cec5SDimitry Andric
9106c3fb27SDimitry Andric // A power of 2. If End <= Start range is empty.
92e8d8bef9SDimitry Andric ElementCount End;
93e8d8bef9SDimitry Andric
isEmptyVFRange94e8d8bef9SDimitry Andric bool isEmpty() const {
95e8d8bef9SDimitry Andric return End.getKnownMinValue() <= Start.getKnownMinValue();
96e8d8bef9SDimitry Andric }
97e8d8bef9SDimitry Andric
VFRangeVFRange98e8d8bef9SDimitry Andric VFRange(const ElementCount &Start, const ElementCount &End)
99e8d8bef9SDimitry Andric : Start(Start), End(End) {
100e8d8bef9SDimitry Andric assert(Start.isScalable() == End.isScalable() &&
101e8d8bef9SDimitry Andric "Both Start and End should have the same scalable flag");
102e8d8bef9SDimitry Andric assert(isPowerOf2_32(Start.getKnownMinValue()) &&
103e8d8bef9SDimitry Andric "Expected Start to be a power of 2");
10406c3fb27SDimitry Andric assert(isPowerOf2_32(End.getKnownMinValue()) &&
10506c3fb27SDimitry Andric "Expected End to be a power of 2");
10606c3fb27SDimitry Andric }
10706c3fb27SDimitry Andric
10806c3fb27SDimitry Andric /// Iterator to iterate over vectorization factors in a VFRange.
10906c3fb27SDimitry Andric class iterator
11006c3fb27SDimitry Andric : public iterator_facade_base<iterator, std::forward_iterator_tag,
11106c3fb27SDimitry Andric ElementCount> {
11206c3fb27SDimitry Andric ElementCount VF;
11306c3fb27SDimitry Andric
11406c3fb27SDimitry Andric public:
iteratorVFRange11506c3fb27SDimitry Andric iterator(ElementCount VF) : VF(VF) {}
11606c3fb27SDimitry Andric
11706c3fb27SDimitry Andric bool operator==(const iterator &Other) const { return VF == Other.VF; }
11806c3fb27SDimitry Andric
11906c3fb27SDimitry Andric ElementCount operator*() const { return VF; }
12006c3fb27SDimitry Andric
12106c3fb27SDimitry Andric iterator &operator++() {
12206c3fb27SDimitry Andric VF *= 2;
12306c3fb27SDimitry Andric return *this;
12406c3fb27SDimitry Andric }
12506c3fb27SDimitry Andric };
12606c3fb27SDimitry Andric
beginVFRange12706c3fb27SDimitry Andric iterator begin() { return iterator(Start); }
endVFRange12806c3fb27SDimitry Andric iterator end() {
12906c3fb27SDimitry Andric assert(isPowerOf2_32(End.getKnownMinValue()));
13006c3fb27SDimitry Andric return iterator(End);
131e8d8bef9SDimitry Andric }
1320b57cec5SDimitry Andric };
1330b57cec5SDimitry Andric
1340b57cec5SDimitry Andric using VPlanPtr = std::unique_ptr<VPlan>;
1350b57cec5SDimitry Andric
1360b57cec5SDimitry Andric /// In what follows, the term "input IR" refers to code that is fed into the
1370b57cec5SDimitry Andric /// vectorizer whereas the term "output IR" refers to code that is generated by
1380b57cec5SDimitry Andric /// the vectorizer.
1390b57cec5SDimitry Andric
140fe6060f1SDimitry Andric /// VPLane provides a way to access lanes in both fixed width and scalable
141fe6060f1SDimitry Andric /// vectors, where for the latter the lane index sometimes needs calculating
142fe6060f1SDimitry Andric /// as a runtime expression.
143fe6060f1SDimitry Andric class VPLane {
144fe6060f1SDimitry Andric public:
145fe6060f1SDimitry Andric /// Kind describes how to interpret Lane.
146fe6060f1SDimitry Andric enum class Kind : uint8_t {
147fe6060f1SDimitry Andric /// For First, Lane is the index into the first N elements of a
148fe6060f1SDimitry Andric /// fixed-vector <N x <ElTy>> or a scalable vector <vscale x N x <ElTy>>.
149fe6060f1SDimitry Andric First,
150fe6060f1SDimitry Andric /// For ScalableLast, Lane is the offset from the start of the last
151fe6060f1SDimitry Andric /// N-element subvector in a scalable vector <vscale x N x <ElTy>>. For
152fe6060f1SDimitry Andric /// example, a Lane of 0 corresponds to lane `(vscale - 1) * N`, a Lane of
153fe6060f1SDimitry Andric /// 1 corresponds to `((vscale - 1) * N) + 1`, etc.
154fe6060f1SDimitry Andric ScalableLast
155fe6060f1SDimitry Andric };
156fe6060f1SDimitry Andric
157fe6060f1SDimitry Andric private:
158fe6060f1SDimitry Andric /// in [0..VF)
159fe6060f1SDimitry Andric unsigned Lane;
160fe6060f1SDimitry Andric
161fe6060f1SDimitry Andric /// Indicates how the Lane should be interpreted, as described above.
162fe6060f1SDimitry Andric Kind LaneKind;
163fe6060f1SDimitry Andric
164fe6060f1SDimitry Andric public:
VPLane(unsigned Lane,Kind LaneKind)165fe6060f1SDimitry Andric VPLane(unsigned Lane, Kind LaneKind) : Lane(Lane), LaneKind(LaneKind) {}
166fe6060f1SDimitry Andric
getFirstLane()167fe6060f1SDimitry Andric static VPLane getFirstLane() { return VPLane(0, VPLane::Kind::First); }
168fe6060f1SDimitry Andric
getLastLaneForVF(const ElementCount & VF)169fe6060f1SDimitry Andric static VPLane getLastLaneForVF(const ElementCount &VF) {
170fe6060f1SDimitry Andric unsigned LaneOffset = VF.getKnownMinValue() - 1;
171fe6060f1SDimitry Andric Kind LaneKind;
172fe6060f1SDimitry Andric if (VF.isScalable())
173fe6060f1SDimitry Andric // In this case 'LaneOffset' refers to the offset from the start of the
174fe6060f1SDimitry Andric // last subvector with VF.getKnownMinValue() elements.
175fe6060f1SDimitry Andric LaneKind = VPLane::Kind::ScalableLast;
176fe6060f1SDimitry Andric else
177fe6060f1SDimitry Andric LaneKind = VPLane::Kind::First;
178fe6060f1SDimitry Andric return VPLane(LaneOffset, LaneKind);
179fe6060f1SDimitry Andric }
180fe6060f1SDimitry Andric
181fe6060f1SDimitry Andric /// Returns a compile-time known value for the lane index and asserts if the
182fe6060f1SDimitry Andric /// lane can only be calculated at runtime.
getKnownLane()183fe6060f1SDimitry Andric unsigned getKnownLane() const {
184fe6060f1SDimitry Andric assert(LaneKind == Kind::First);
185fe6060f1SDimitry Andric return Lane;
186fe6060f1SDimitry Andric }
187fe6060f1SDimitry Andric
188fe6060f1SDimitry Andric /// Returns an expression describing the lane index that can be used at
189fe6060f1SDimitry Andric /// runtime.
19081ad6265SDimitry Andric Value *getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const;
191fe6060f1SDimitry Andric
192fe6060f1SDimitry Andric /// Returns the Kind of lane offset.
getKind()193fe6060f1SDimitry Andric Kind getKind() const { return LaneKind; }
194fe6060f1SDimitry Andric
195fe6060f1SDimitry Andric /// Returns true if this is the first lane of the whole vector.
isFirstLane()196fe6060f1SDimitry Andric bool isFirstLane() const { return Lane == 0 && LaneKind == Kind::First; }
197fe6060f1SDimitry Andric
198fe6060f1SDimitry Andric /// Maps the lane to a cache index based on \p VF.
mapToCacheIndex(const ElementCount & VF)199fe6060f1SDimitry Andric unsigned mapToCacheIndex(const ElementCount &VF) const {
200fe6060f1SDimitry Andric switch (LaneKind) {
201fe6060f1SDimitry Andric case VPLane::Kind::ScalableLast:
202fe6060f1SDimitry Andric assert(VF.isScalable() && Lane < VF.getKnownMinValue());
203fe6060f1SDimitry Andric return VF.getKnownMinValue() + Lane;
204fe6060f1SDimitry Andric default:
205fe6060f1SDimitry Andric assert(Lane < VF.getKnownMinValue());
206fe6060f1SDimitry Andric return Lane;
207fe6060f1SDimitry Andric }
208fe6060f1SDimitry Andric }
209fe6060f1SDimitry Andric
210fe6060f1SDimitry Andric /// Returns the maxmimum number of lanes that we are able to consider
211fe6060f1SDimitry Andric /// caching for \p VF.
getNumCachedLanes(const ElementCount & VF)212fe6060f1SDimitry Andric static unsigned getNumCachedLanes(const ElementCount &VF) {
213fe6060f1SDimitry Andric return VF.getKnownMinValue() * (VF.isScalable() ? 2 : 1);
214fe6060f1SDimitry Andric }
215fe6060f1SDimitry Andric };
216fe6060f1SDimitry Andric
2170b57cec5SDimitry Andric /// VPIteration represents a single point in the iteration space of the output
2180b57cec5SDimitry Andric /// (vectorized and/or unrolled) IR loop.
2190b57cec5SDimitry Andric struct VPIteration {
2200b57cec5SDimitry Andric /// in [0..UF)
2210b57cec5SDimitry Andric unsigned Part;
2220b57cec5SDimitry Andric
223fe6060f1SDimitry Andric VPLane Lane;
2240b57cec5SDimitry Andric
225fe6060f1SDimitry Andric VPIteration(unsigned Part, unsigned Lane,
226fe6060f1SDimitry Andric VPLane::Kind Kind = VPLane::Kind::First)
PartVPIteration227fe6060f1SDimitry Andric : Part(Part), Lane(Lane, Kind) {}
2280b57cec5SDimitry Andric
VPIterationVPIteration229fe6060f1SDimitry Andric VPIteration(unsigned Part, const VPLane &Lane) : Part(Part), Lane(Lane) {}
2300b57cec5SDimitry Andric
isFirstIterationVPIteration231fe6060f1SDimitry Andric bool isFirstIteration() const { return Part == 0 && Lane.isFirstLane(); }
2320b57cec5SDimitry Andric };
2330b57cec5SDimitry Andric
2340b57cec5SDimitry Andric /// VPTransformState holds information passed down when "executing" a VPlan,
2350b57cec5SDimitry Andric /// needed for generating the output IR.
2360b57cec5SDimitry Andric struct VPTransformState {
VPTransformStateVPTransformState237fe6060f1SDimitry Andric VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI,
23881ad6265SDimitry Andric DominatorTree *DT, IRBuilderBase &Builder,
2395f757f3fSDimitry Andric InnerLoopVectorizer *ILV, VPlan *Plan, LLVMContext &Ctx)
24081ad6265SDimitry Andric : VF(VF), UF(UF), LI(LI), DT(DT), Builder(Builder), ILV(ILV), Plan(Plan),
2415f757f3fSDimitry Andric LVer(nullptr), TypeAnalysis(Ctx) {}
2420b57cec5SDimitry Andric
2430b57cec5SDimitry Andric /// The chosen Vectorization and Unroll Factors of the loop being vectorized.
244e8d8bef9SDimitry Andric ElementCount VF;
2450b57cec5SDimitry Andric unsigned UF;
2460b57cec5SDimitry Andric
2470b57cec5SDimitry Andric /// Hold the indices to generate specific scalar instructions. Null indicates
2480b57cec5SDimitry Andric /// that all instances are to be generated, using either scalar or vector
2490b57cec5SDimitry Andric /// instructions.
250bdd1243dSDimitry Andric std::optional<VPIteration> Instance;
2510b57cec5SDimitry Andric
2520b57cec5SDimitry Andric struct DataState {
2530b57cec5SDimitry Andric /// A type for vectorized values in the new loop. Each value from the
2540b57cec5SDimitry Andric /// original loop, when vectorized, is represented by UF vector values in
2550b57cec5SDimitry Andric /// the new unrolled loop, where UF is the unroll factor.
2560b57cec5SDimitry Andric typedef SmallVector<Value *, 2> PerPartValuesTy;
2570b57cec5SDimitry Andric
2580b57cec5SDimitry Andric DenseMap<VPValue *, PerPartValuesTy> PerPartOutput;
259e8d8bef9SDimitry Andric
260e8d8bef9SDimitry Andric using ScalarsPerPartValuesTy = SmallVector<SmallVector<Value *, 4>, 2>;
261e8d8bef9SDimitry Andric DenseMap<VPValue *, ScalarsPerPartValuesTy> PerPartScalars;
2620b57cec5SDimitry Andric } Data;
2630b57cec5SDimitry Andric
2640b57cec5SDimitry Andric /// Get the generated Value for a given VPValue and a given Part. Note that
2650b57cec5SDimitry Andric /// as some Defs are still created by ILV and managed in its ValueMap, this
2660b57cec5SDimitry Andric /// method will delegate the call to ILV in such cases in order to provide
2670b57cec5SDimitry Andric /// callers a consistent API.
2680b57cec5SDimitry Andric /// \see set.
269fe6060f1SDimitry Andric Value *get(VPValue *Def, unsigned Part);
2700b57cec5SDimitry Andric
2715ffd83dbSDimitry Andric /// Get the generated Value for a given VPValue and given Part and Lane.
272e8d8bef9SDimitry Andric Value *get(VPValue *Def, const VPIteration &Instance);
273e8d8bef9SDimitry Andric
hasVectorValueVPTransformState274e8d8bef9SDimitry Andric bool hasVectorValue(VPValue *Def, unsigned Part) {
275e8d8bef9SDimitry Andric auto I = Data.PerPartOutput.find(Def);
276e8d8bef9SDimitry Andric return I != Data.PerPartOutput.end() && Part < I->second.size() &&
277e8d8bef9SDimitry Andric I->second[Part];
2785ffd83dbSDimitry Andric }
2795ffd83dbSDimitry Andric
hasScalarValueVPTransformState280e8d8bef9SDimitry Andric bool hasScalarValue(VPValue *Def, VPIteration Instance) {
281e8d8bef9SDimitry Andric auto I = Data.PerPartScalars.find(Def);
282e8d8bef9SDimitry Andric if (I == Data.PerPartScalars.end())
283e8d8bef9SDimitry Andric return false;
284fe6060f1SDimitry Andric unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
285e8d8bef9SDimitry Andric return Instance.Part < I->second.size() &&
286fe6060f1SDimitry Andric CacheIdx < I->second[Instance.Part].size() &&
287fe6060f1SDimitry Andric I->second[Instance.Part][CacheIdx];
288480093f4SDimitry Andric }
289480093f4SDimitry Andric
2900b57cec5SDimitry Andric /// Set the generated Value for a given VPValue and a given Part.
setVPTransformState2910b57cec5SDimitry Andric void set(VPValue *Def, Value *V, unsigned Part) {
2920b57cec5SDimitry Andric if (!Data.PerPartOutput.count(Def)) {
2930b57cec5SDimitry Andric DataState::PerPartValuesTy Entry(UF);
2940b57cec5SDimitry Andric Data.PerPartOutput[Def] = Entry;
2950b57cec5SDimitry Andric }
2960b57cec5SDimitry Andric Data.PerPartOutput[Def][Part] = V;
2970b57cec5SDimitry Andric }
298fe6060f1SDimitry Andric /// Reset an existing vector value for \p Def and a given \p Part.
resetVPTransformState299fe6060f1SDimitry Andric void reset(VPValue *Def, Value *V, unsigned Part) {
300fe6060f1SDimitry Andric auto Iter = Data.PerPartOutput.find(Def);
301fe6060f1SDimitry Andric assert(Iter != Data.PerPartOutput.end() &&
302fe6060f1SDimitry Andric "need to overwrite existing value");
303fe6060f1SDimitry Andric Iter->second[Part] = V;
304fe6060f1SDimitry Andric }
305e8d8bef9SDimitry Andric
306fe6060f1SDimitry Andric /// Set the generated scalar \p V for \p Def and the given \p Instance.
setVPTransformState307e8d8bef9SDimitry Andric void set(VPValue *Def, Value *V, const VPIteration &Instance) {
308e8d8bef9SDimitry Andric auto Iter = Data.PerPartScalars.insert({Def, {}});
309e8d8bef9SDimitry Andric auto &PerPartVec = Iter.first->second;
310e8d8bef9SDimitry Andric while (PerPartVec.size() <= Instance.Part)
311e8d8bef9SDimitry Andric PerPartVec.emplace_back();
312e8d8bef9SDimitry Andric auto &Scalars = PerPartVec[Instance.Part];
313fe6060f1SDimitry Andric unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
314fe6060f1SDimitry Andric while (Scalars.size() <= CacheIdx)
315e8d8bef9SDimitry Andric Scalars.push_back(nullptr);
316fe6060f1SDimitry Andric assert(!Scalars[CacheIdx] && "should overwrite existing value");
317fe6060f1SDimitry Andric Scalars[CacheIdx] = V;
318fe6060f1SDimitry Andric }
319fe6060f1SDimitry Andric
320fe6060f1SDimitry Andric /// Reset an existing scalar value for \p Def and a given \p Instance.
resetVPTransformState321fe6060f1SDimitry Andric void reset(VPValue *Def, Value *V, const VPIteration &Instance) {
322fe6060f1SDimitry Andric auto Iter = Data.PerPartScalars.find(Def);
323fe6060f1SDimitry Andric assert(Iter != Data.PerPartScalars.end() &&
324fe6060f1SDimitry Andric "need to overwrite existing value");
325fe6060f1SDimitry Andric assert(Instance.Part < Iter->second.size() &&
326fe6060f1SDimitry Andric "need to overwrite existing value");
327fe6060f1SDimitry Andric unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
328fe6060f1SDimitry Andric assert(CacheIdx < Iter->second[Instance.Part].size() &&
329fe6060f1SDimitry Andric "need to overwrite existing value");
330fe6060f1SDimitry Andric Iter->second[Instance.Part][CacheIdx] = V;
331e8d8bef9SDimitry Andric }
3320b57cec5SDimitry Andric
33381ad6265SDimitry Andric /// Add additional metadata to \p To that was not present on \p Orig.
33481ad6265SDimitry Andric ///
33581ad6265SDimitry Andric /// Currently this is used to add the noalias annotations based on the
33681ad6265SDimitry Andric /// inserted memchecks. Use this for instructions that are *cloned* into the
33781ad6265SDimitry Andric /// vector loop.
33881ad6265SDimitry Andric void addNewMetadata(Instruction *To, const Instruction *Orig);
33981ad6265SDimitry Andric
34081ad6265SDimitry Andric /// Add metadata from one instruction to another.
34181ad6265SDimitry Andric ///
34281ad6265SDimitry Andric /// This includes both the original MDs from \p From and additional ones (\see
34381ad6265SDimitry Andric /// addNewMetadata). Use this for *newly created* instructions in the vector
34481ad6265SDimitry Andric /// loop.
34581ad6265SDimitry Andric void addMetadata(Instruction *To, Instruction *From);
34681ad6265SDimitry Andric
34781ad6265SDimitry Andric /// Similar to the previous function but it adds the metadata to a
34881ad6265SDimitry Andric /// vector of instructions.
34981ad6265SDimitry Andric void addMetadata(ArrayRef<Value *> To, Instruction *From);
35081ad6265SDimitry Andric
3515f757f3fSDimitry Andric /// Set the debug location in the builder using the debug location \p DL.
3525f757f3fSDimitry Andric void setDebugLocFrom(DebugLoc DL);
3535f757f3fSDimitry Andric
3545f757f3fSDimitry Andric /// Construct the vector value of a scalarized value \p V one lane at a time.
3555f757f3fSDimitry Andric void packScalarIntoVectorValue(VPValue *Def, const VPIteration &Instance);
35681ad6265SDimitry Andric
3570b57cec5SDimitry Andric /// Hold state information used when constructing the CFG of the output IR,
3580b57cec5SDimitry Andric /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
3590b57cec5SDimitry Andric struct CFGState {
3600b57cec5SDimitry Andric /// The previous VPBasicBlock visited. Initially set to null.
3610b57cec5SDimitry Andric VPBasicBlock *PrevVPBB = nullptr;
3620b57cec5SDimitry Andric
3630b57cec5SDimitry Andric /// The previous IR BasicBlock created or used. Initially set to the new
3640b57cec5SDimitry Andric /// header BasicBlock.
3650b57cec5SDimitry Andric BasicBlock *PrevBB = nullptr;
3660b57cec5SDimitry Andric
36781ad6265SDimitry Andric /// The last IR BasicBlock in the output IR. Set to the exit block of the
36881ad6265SDimitry Andric /// vector loop.
36981ad6265SDimitry Andric BasicBlock *ExitBB = nullptr;
370fe6060f1SDimitry Andric
3710b57cec5SDimitry Andric /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
3720b57cec5SDimitry Andric /// of replication, maps the BasicBlock of the last replica created.
3730b57cec5SDimitry Andric SmallDenseMap<VPBasicBlock *, BasicBlock *> VPBB2IRBB;
3740b57cec5SDimitry Andric
3750b57cec5SDimitry Andric CFGState() = default;
37681ad6265SDimitry Andric
37781ad6265SDimitry Andric /// Returns the BasicBlock* mapped to the pre-header of the loop region
37881ad6265SDimitry Andric /// containing \p R.
37981ad6265SDimitry Andric BasicBlock *getPreheaderBBFor(VPRecipeBase *R);
3800b57cec5SDimitry Andric } CFG;
3810b57cec5SDimitry Andric
3820b57cec5SDimitry Andric /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
3830b57cec5SDimitry Andric LoopInfo *LI;
3840b57cec5SDimitry Andric
3850b57cec5SDimitry Andric /// Hold a pointer to Dominator Tree to register new basic blocks in the loop.
3860b57cec5SDimitry Andric DominatorTree *DT;
3870b57cec5SDimitry Andric
3880b57cec5SDimitry Andric /// Hold a reference to the IRBuilder used to generate output IR code.
38981ad6265SDimitry Andric IRBuilderBase &Builder;
3900b57cec5SDimitry Andric
3910b57cec5SDimitry Andric VPValue2ValueTy VPValue2Value;
3920b57cec5SDimitry Andric
3935ffd83dbSDimitry Andric /// Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
3945ffd83dbSDimitry Andric Value *CanonicalIV = nullptr;
3955ffd83dbSDimitry Andric
3960b57cec5SDimitry Andric /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
3970b57cec5SDimitry Andric InnerLoopVectorizer *ILV;
3980b57cec5SDimitry Andric
399fe6060f1SDimitry Andric /// Pointer to the VPlan code is generated for.
400fe6060f1SDimitry Andric VPlan *Plan;
4014824e7fdSDimitry Andric
40281ad6265SDimitry Andric /// The loop object for the current parent region, or nullptr.
40381ad6265SDimitry Andric Loop *CurrentVectorLoop = nullptr;
404fe6060f1SDimitry Andric
40581ad6265SDimitry Andric /// LoopVersioning. It's only set up (non-null) if memchecks were
40681ad6265SDimitry Andric /// used.
40781ad6265SDimitry Andric ///
40881ad6265SDimitry Andric /// This is currently only used to add no-alias metadata based on the
40981ad6265SDimitry Andric /// memchecks. The actually versioning is performed manually.
41006c3fb27SDimitry Andric LoopVersioning *LVer = nullptr;
41106c3fb27SDimitry Andric
41206c3fb27SDimitry Andric /// Map SCEVs to their expanded values. Populated when executing
41306c3fb27SDimitry Andric /// VPExpandSCEVRecipes.
41406c3fb27SDimitry Andric DenseMap<const SCEV *, Value *> ExpandedSCEVs;
4155f757f3fSDimitry Andric
4165f757f3fSDimitry Andric /// VPlan-based type analysis.
4175f757f3fSDimitry Andric VPTypeAnalysis TypeAnalysis;
4180b57cec5SDimitry Andric };
4190b57cec5SDimitry Andric
4200b57cec5SDimitry Andric /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
4210b57cec5SDimitry Andric /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
4220b57cec5SDimitry Andric class VPBlockBase {
4230b57cec5SDimitry Andric friend class VPBlockUtils;
4240b57cec5SDimitry Andric
4250b57cec5SDimitry Andric const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
4260b57cec5SDimitry Andric
4270b57cec5SDimitry Andric /// An optional name for the block.
4280b57cec5SDimitry Andric std::string Name;
4290b57cec5SDimitry Andric
4300b57cec5SDimitry Andric /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
4310b57cec5SDimitry Andric /// it is a topmost VPBlockBase.
4320b57cec5SDimitry Andric VPRegionBlock *Parent = nullptr;
4330b57cec5SDimitry Andric
4340b57cec5SDimitry Andric /// List of predecessor blocks.
4350b57cec5SDimitry Andric SmallVector<VPBlockBase *, 1> Predecessors;
4360b57cec5SDimitry Andric
4370b57cec5SDimitry Andric /// List of successor blocks.
4380b57cec5SDimitry Andric SmallVector<VPBlockBase *, 1> Successors;
4390b57cec5SDimitry Andric
4405ffd83dbSDimitry Andric /// VPlan containing the block. Can only be set on the entry block of the
4415ffd83dbSDimitry Andric /// plan.
4425ffd83dbSDimitry Andric VPlan *Plan = nullptr;
4435ffd83dbSDimitry Andric
4440b57cec5SDimitry Andric /// Add \p Successor as the last successor to this block.
appendSuccessor(VPBlockBase * Successor)4450b57cec5SDimitry Andric void appendSuccessor(VPBlockBase *Successor) {
4460b57cec5SDimitry Andric assert(Successor && "Cannot add nullptr successor!");
4470b57cec5SDimitry Andric Successors.push_back(Successor);
4480b57cec5SDimitry Andric }
4490b57cec5SDimitry Andric
4500b57cec5SDimitry Andric /// Add \p Predecessor as the last predecessor to this block.
appendPredecessor(VPBlockBase * Predecessor)4510b57cec5SDimitry Andric void appendPredecessor(VPBlockBase *Predecessor) {
4520b57cec5SDimitry Andric assert(Predecessor && "Cannot add nullptr predecessor!");
4530b57cec5SDimitry Andric Predecessors.push_back(Predecessor);
4540b57cec5SDimitry Andric }
4550b57cec5SDimitry Andric
4560b57cec5SDimitry Andric /// Remove \p Predecessor from the predecessors of this block.
removePredecessor(VPBlockBase * Predecessor)4570b57cec5SDimitry Andric void removePredecessor(VPBlockBase *Predecessor) {
458e8d8bef9SDimitry Andric auto Pos = find(Predecessors, Predecessor);
4590b57cec5SDimitry Andric assert(Pos && "Predecessor does not exist");
4600b57cec5SDimitry Andric Predecessors.erase(Pos);
4610b57cec5SDimitry Andric }
4620b57cec5SDimitry Andric
4630b57cec5SDimitry Andric /// Remove \p Successor from the successors of this block.
removeSuccessor(VPBlockBase * Successor)4640b57cec5SDimitry Andric void removeSuccessor(VPBlockBase *Successor) {
465e8d8bef9SDimitry Andric auto Pos = find(Successors, Successor);
4660b57cec5SDimitry Andric assert(Pos && "Successor does not exist");
4670b57cec5SDimitry Andric Successors.erase(Pos);
4680b57cec5SDimitry Andric }
4690b57cec5SDimitry Andric
4700b57cec5SDimitry Andric protected:
VPBlockBase(const unsigned char SC,const std::string & N)4710b57cec5SDimitry Andric VPBlockBase(const unsigned char SC, const std::string &N)
4720b57cec5SDimitry Andric : SubclassID(SC), Name(N) {}
4730b57cec5SDimitry Andric
4740b57cec5SDimitry Andric public:
4750b57cec5SDimitry Andric /// An enumeration for keeping track of the concrete subclass of VPBlockBase
4760b57cec5SDimitry Andric /// that are actually instantiated. Values of this enumeration are kept in the
4770b57cec5SDimitry Andric /// SubclassID field of the VPBlockBase objects. They are used for concrete
4780b57cec5SDimitry Andric /// type identification.
4790b57cec5SDimitry Andric using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
4800b57cec5SDimitry Andric
4810b57cec5SDimitry Andric using VPBlocksTy = SmallVectorImpl<VPBlockBase *>;
4820b57cec5SDimitry Andric
4830b57cec5SDimitry Andric virtual ~VPBlockBase() = default;
4840b57cec5SDimitry Andric
getName()4850b57cec5SDimitry Andric const std::string &getName() const { return Name; }
4860b57cec5SDimitry Andric
setName(const Twine & newName)4870b57cec5SDimitry Andric void setName(const Twine &newName) { Name = newName.str(); }
4880b57cec5SDimitry Andric
4890b57cec5SDimitry Andric /// \return an ID for the concrete type of this object.
4900b57cec5SDimitry Andric /// This is used to implement the classof checks. This should not be used
4910b57cec5SDimitry Andric /// for any other purpose, as the values may change as LLVM evolves.
getVPBlockID()4920b57cec5SDimitry Andric unsigned getVPBlockID() const { return SubclassID; }
4930b57cec5SDimitry Andric
getParent()4940b57cec5SDimitry Andric VPRegionBlock *getParent() { return Parent; }
getParent()4950b57cec5SDimitry Andric const VPRegionBlock *getParent() const { return Parent; }
4960b57cec5SDimitry Andric
4975ffd83dbSDimitry Andric /// \return A pointer to the plan containing the current block.
4985ffd83dbSDimitry Andric VPlan *getPlan();
4995ffd83dbSDimitry Andric const VPlan *getPlan() const;
5005ffd83dbSDimitry Andric
5015ffd83dbSDimitry Andric /// Sets the pointer of the plan containing the block. The block must be the
5025ffd83dbSDimitry Andric /// entry block into the VPlan.
5035ffd83dbSDimitry Andric void setPlan(VPlan *ParentPlan);
5045ffd83dbSDimitry Andric
setParent(VPRegionBlock * P)5050b57cec5SDimitry Andric void setParent(VPRegionBlock *P) { Parent = P; }
5060b57cec5SDimitry Andric
5070b57cec5SDimitry Andric /// \return the VPBasicBlock that is the entry of this VPBlockBase,
5080b57cec5SDimitry Andric /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
5090b57cec5SDimitry Andric /// VPBlockBase is a VPBasicBlock, it is returned.
5100b57cec5SDimitry Andric const VPBasicBlock *getEntryBasicBlock() const;
5110b57cec5SDimitry Andric VPBasicBlock *getEntryBasicBlock();
5120b57cec5SDimitry Andric
51381ad6265SDimitry Andric /// \return the VPBasicBlock that is the exiting this VPBlockBase,
5140b57cec5SDimitry Andric /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
5150b57cec5SDimitry Andric /// VPBlockBase is a VPBasicBlock, it is returned.
51681ad6265SDimitry Andric const VPBasicBlock *getExitingBasicBlock() const;
51781ad6265SDimitry Andric VPBasicBlock *getExitingBasicBlock();
5180b57cec5SDimitry Andric
getSuccessors()5190b57cec5SDimitry Andric const VPBlocksTy &getSuccessors() const { return Successors; }
getSuccessors()5200b57cec5SDimitry Andric VPBlocksTy &getSuccessors() { return Successors; }
5210b57cec5SDimitry Andric
successors()5220eae32dcSDimitry Andric iterator_range<VPBlockBase **> successors() { return Successors; }
5230eae32dcSDimitry Andric
getPredecessors()5240b57cec5SDimitry Andric const VPBlocksTy &getPredecessors() const { return Predecessors; }
getPredecessors()5250b57cec5SDimitry Andric VPBlocksTy &getPredecessors() { return Predecessors; }
5260b57cec5SDimitry Andric
5270b57cec5SDimitry Andric /// \return the successor of this VPBlockBase if it has a single successor.
5280b57cec5SDimitry Andric /// Otherwise return a null pointer.
getSingleSuccessor()5290b57cec5SDimitry Andric VPBlockBase *getSingleSuccessor() const {
5300b57cec5SDimitry Andric return (Successors.size() == 1 ? *Successors.begin() : nullptr);
5310b57cec5SDimitry Andric }
5320b57cec5SDimitry Andric
5330b57cec5SDimitry Andric /// \return the predecessor of this VPBlockBase if it has a single
5340b57cec5SDimitry Andric /// predecessor. Otherwise return a null pointer.
getSinglePredecessor()5350b57cec5SDimitry Andric VPBlockBase *getSinglePredecessor() const {
5360b57cec5SDimitry Andric return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
5370b57cec5SDimitry Andric }
5380b57cec5SDimitry Andric
getNumSuccessors()5390b57cec5SDimitry Andric size_t getNumSuccessors() const { return Successors.size(); }
getNumPredecessors()5400b57cec5SDimitry Andric size_t getNumPredecessors() const { return Predecessors.size(); }
5410b57cec5SDimitry Andric
5420b57cec5SDimitry Andric /// An Enclosing Block of a block B is any block containing B, including B
5430b57cec5SDimitry Andric /// itself. \return the closest enclosing block starting from "this", which
5440b57cec5SDimitry Andric /// has successors. \return the root enclosing block if all enclosing blocks
5450b57cec5SDimitry Andric /// have no successors.
5460b57cec5SDimitry Andric VPBlockBase *getEnclosingBlockWithSuccessors();
5470b57cec5SDimitry Andric
5480b57cec5SDimitry Andric /// \return the closest enclosing block starting from "this", which has
5490b57cec5SDimitry Andric /// predecessors. \return the root enclosing block if all enclosing blocks
5500b57cec5SDimitry Andric /// have no predecessors.
5510b57cec5SDimitry Andric VPBlockBase *getEnclosingBlockWithPredecessors();
5520b57cec5SDimitry Andric
5530b57cec5SDimitry Andric /// \return the successors either attached directly to this VPBlockBase or, if
5540b57cec5SDimitry Andric /// this VPBlockBase is the exit block of a VPRegionBlock and has no
5550b57cec5SDimitry Andric /// successors of its own, search recursively for the first enclosing
5560b57cec5SDimitry Andric /// VPRegionBlock that has successors and return them. If no such
5570b57cec5SDimitry Andric /// VPRegionBlock exists, return the (empty) successors of the topmost
5580b57cec5SDimitry Andric /// VPBlockBase reached.
getHierarchicalSuccessors()5590b57cec5SDimitry Andric const VPBlocksTy &getHierarchicalSuccessors() {
5600b57cec5SDimitry Andric return getEnclosingBlockWithSuccessors()->getSuccessors();
5610b57cec5SDimitry Andric }
5620b57cec5SDimitry Andric
5630b57cec5SDimitry Andric /// \return the hierarchical successor of this VPBlockBase if it has a single
5640b57cec5SDimitry Andric /// hierarchical successor. Otherwise return a null pointer.
getSingleHierarchicalSuccessor()5650b57cec5SDimitry Andric VPBlockBase *getSingleHierarchicalSuccessor() {
5660b57cec5SDimitry Andric return getEnclosingBlockWithSuccessors()->getSingleSuccessor();
5670b57cec5SDimitry Andric }
5680b57cec5SDimitry Andric
5690b57cec5SDimitry Andric /// \return the predecessors either attached directly to this VPBlockBase or,
5700b57cec5SDimitry Andric /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
5710b57cec5SDimitry Andric /// predecessors of its own, search recursively for the first enclosing
5720b57cec5SDimitry Andric /// VPRegionBlock that has predecessors and return them. If no such
5730b57cec5SDimitry Andric /// VPRegionBlock exists, return the (empty) predecessors of the topmost
5740b57cec5SDimitry Andric /// VPBlockBase reached.
getHierarchicalPredecessors()5750b57cec5SDimitry Andric const VPBlocksTy &getHierarchicalPredecessors() {
5760b57cec5SDimitry Andric return getEnclosingBlockWithPredecessors()->getPredecessors();
5770b57cec5SDimitry Andric }
5780b57cec5SDimitry Andric
5790b57cec5SDimitry Andric /// \return the hierarchical predecessor of this VPBlockBase if it has a
5800b57cec5SDimitry Andric /// single hierarchical predecessor. Otherwise return a null pointer.
getSingleHierarchicalPredecessor()5810b57cec5SDimitry Andric VPBlockBase *getSingleHierarchicalPredecessor() {
5820b57cec5SDimitry Andric return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
5830b57cec5SDimitry Andric }
5840b57cec5SDimitry Andric
5850b57cec5SDimitry Andric /// Set a given VPBlockBase \p Successor as the single successor of this
5860b57cec5SDimitry Andric /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
5870b57cec5SDimitry Andric /// This VPBlockBase must have no successors.
setOneSuccessor(VPBlockBase * Successor)5880b57cec5SDimitry Andric void setOneSuccessor(VPBlockBase *Successor) {
5890b57cec5SDimitry Andric assert(Successors.empty() && "Setting one successor when others exist.");
5905f757f3fSDimitry Andric assert(Successor->getParent() == getParent() &&
5915f757f3fSDimitry Andric "connected blocks must have the same parent");
5920b57cec5SDimitry Andric appendSuccessor(Successor);
5930b57cec5SDimitry Andric }
5940b57cec5SDimitry Andric
5950b57cec5SDimitry Andric /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
59681ad6265SDimitry Andric /// successors of this VPBlockBase. This VPBlockBase is not added as
59781ad6265SDimitry Andric /// predecessor of \p IfTrue or \p IfFalse. This VPBlockBase must have no
59881ad6265SDimitry Andric /// successors.
setTwoSuccessors(VPBlockBase * IfTrue,VPBlockBase * IfFalse)59981ad6265SDimitry Andric void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {
6000b57cec5SDimitry Andric assert(Successors.empty() && "Setting two successors when others exist.");
6010b57cec5SDimitry Andric appendSuccessor(IfTrue);
6020b57cec5SDimitry Andric appendSuccessor(IfFalse);
6030b57cec5SDimitry Andric }
6040b57cec5SDimitry Andric
6050b57cec5SDimitry Andric /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
6060b57cec5SDimitry Andric /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
6070b57cec5SDimitry Andric /// as successor of any VPBasicBlock in \p NewPreds.
setPredecessors(ArrayRef<VPBlockBase * > NewPreds)6080b57cec5SDimitry Andric void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) {
6090b57cec5SDimitry Andric assert(Predecessors.empty() && "Block predecessors already set.");
6100b57cec5SDimitry Andric for (auto *Pred : NewPreds)
6110b57cec5SDimitry Andric appendPredecessor(Pred);
6120b57cec5SDimitry Andric }
6130b57cec5SDimitry Andric
6140b57cec5SDimitry Andric /// Remove all the predecessor of this block.
clearPredecessors()6150b57cec5SDimitry Andric void clearPredecessors() { Predecessors.clear(); }
6160b57cec5SDimitry Andric
61781ad6265SDimitry Andric /// Remove all the successors of this block.
clearSuccessors()61881ad6265SDimitry Andric void clearSuccessors() { Successors.clear(); }
6190b57cec5SDimitry Andric
6200b57cec5SDimitry Andric /// The method which generates the output IR that correspond to this
6210b57cec5SDimitry Andric /// VPBlockBase, thereby "executing" the VPlan.
622bdd1243dSDimitry Andric virtual void execute(VPTransformState *State) = 0;
6230b57cec5SDimitry Andric
6240b57cec5SDimitry Andric /// Delete all blocks reachable from a given VPBlockBase, inclusive.
6250b57cec5SDimitry Andric static void deleteCFG(VPBlockBase *Entry);
6260b57cec5SDimitry Andric
6270b57cec5SDimitry Andric /// Return true if it is legal to hoist instructions into this block.
isLegalToHoistInto()6280b57cec5SDimitry Andric bool isLegalToHoistInto() {
6290b57cec5SDimitry Andric // There are currently no constraints that prevent an instruction to be
6300b57cec5SDimitry Andric // hoisted into a VPBlockBase.
6310b57cec5SDimitry Andric return true;
6320b57cec5SDimitry Andric }
633e8d8bef9SDimitry Andric
634e8d8bef9SDimitry Andric /// Replace all operands of VPUsers in the block with \p NewValue and also
635e8d8bef9SDimitry Andric /// replaces all uses of VPValues defined in the block with NewValue.
636e8d8bef9SDimitry Andric virtual void dropAllReferences(VPValue *NewValue) = 0;
637fe6060f1SDimitry Andric
638fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
printAsOperand(raw_ostream & OS,bool PrintType)639fe6060f1SDimitry Andric void printAsOperand(raw_ostream &OS, bool PrintType) const {
640fe6060f1SDimitry Andric OS << getName();
641fe6060f1SDimitry Andric }
642fe6060f1SDimitry Andric
643fe6060f1SDimitry Andric /// Print plain-text dump of this VPBlockBase to \p O, prefixing all lines
644fe6060f1SDimitry Andric /// with \p Indent. \p SlotTracker is used to print unnamed VPValue's using
645fe6060f1SDimitry Andric /// consequtive numbers.
646fe6060f1SDimitry Andric ///
647fe6060f1SDimitry Andric /// Note that the numbering is applied to the whole VPlan, so printing
648fe6060f1SDimitry Andric /// individual blocks is consistent with the whole VPlan printing.
649fe6060f1SDimitry Andric virtual void print(raw_ostream &O, const Twine &Indent,
650fe6060f1SDimitry Andric VPSlotTracker &SlotTracker) const = 0;
651fe6060f1SDimitry Andric
652fe6060f1SDimitry Andric /// Print plain-text dump of this VPlan to \p O.
print(raw_ostream & O)653fe6060f1SDimitry Andric void print(raw_ostream &O) const {
654fe6060f1SDimitry Andric VPSlotTracker SlotTracker(getPlan());
655fe6060f1SDimitry Andric print(O, "", SlotTracker);
656fe6060f1SDimitry Andric }
657fe6060f1SDimitry Andric
658fe6060f1SDimitry Andric /// Print the successors of this block to \p O, prefixing all lines with \p
659fe6060f1SDimitry Andric /// Indent.
660fe6060f1SDimitry Andric void printSuccessors(raw_ostream &O, const Twine &Indent) const;
661fe6060f1SDimitry Andric
662fe6060f1SDimitry Andric /// Dump this VPBlockBase to dbgs().
dump()663fe6060f1SDimitry Andric LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
664fe6060f1SDimitry Andric #endif
6650b57cec5SDimitry Andric };
6660b57cec5SDimitry Andric
66781ad6265SDimitry Andric /// A value that is used outside the VPlan. The operand of the user needs to be
66881ad6265SDimitry Andric /// added to the associated LCSSA phi node.
66981ad6265SDimitry Andric class VPLiveOut : public VPUser {
67081ad6265SDimitry Andric PHINode *Phi;
67181ad6265SDimitry Andric
67281ad6265SDimitry Andric public:
VPLiveOut(PHINode * Phi,VPValue * Op)67381ad6265SDimitry Andric VPLiveOut(PHINode *Phi, VPValue *Op)
67481ad6265SDimitry Andric : VPUser({Op}, VPUser::VPUserID::LiveOut), Phi(Phi) {}
67581ad6265SDimitry Andric
classof(const VPUser * U)67606c3fb27SDimitry Andric static inline bool classof(const VPUser *U) {
67706c3fb27SDimitry Andric return U->getVPUserID() == VPUser::VPUserID::LiveOut;
67806c3fb27SDimitry Andric }
67906c3fb27SDimitry Andric
68081ad6265SDimitry Andric /// Fixup the wrapped LCSSA phi node in the unique exit block. This simply
68181ad6265SDimitry Andric /// means we need to add the appropriate incoming value from the middle
68281ad6265SDimitry Andric /// block as exiting edges from the scalar epilogue loop (if present) are
68381ad6265SDimitry Andric /// already in place, and we exit the vector loop exclusively to the middle
68481ad6265SDimitry Andric /// block.
68581ad6265SDimitry Andric void fixPhi(VPlan &Plan, VPTransformState &State);
68681ad6265SDimitry Andric
68781ad6265SDimitry Andric /// Returns true if the VPLiveOut uses scalars of operand \p Op.
usesScalars(const VPValue * Op)68881ad6265SDimitry Andric bool usesScalars(const VPValue *Op) const override {
68981ad6265SDimitry Andric assert(is_contained(operands(), Op) &&
69081ad6265SDimitry Andric "Op must be an operand of the recipe");
69181ad6265SDimitry Andric return true;
69281ad6265SDimitry Andric }
69381ad6265SDimitry Andric
getPhi()69481ad6265SDimitry Andric PHINode *getPhi() const { return Phi; }
69506c3fb27SDimitry Andric
69606c3fb27SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
69706c3fb27SDimitry Andric /// Print the VPLiveOut to \p O.
69806c3fb27SDimitry Andric void print(raw_ostream &O, VPSlotTracker &SlotTracker) const;
69906c3fb27SDimitry Andric #endif
70081ad6265SDimitry Andric };
70181ad6265SDimitry Andric
7020b57cec5SDimitry Andric /// VPRecipeBase is a base class modeling a sequence of one or more output IR
7035f757f3fSDimitry Andric /// instructions. VPRecipeBase owns the VPValues it defines through VPDef
704e8d8bef9SDimitry Andric /// and is responsible for deleting its defined values. Single-value
7057a6dacacSDimitry Andric /// recipes must inherit from VPSingleDef instead of inheriting from both
7067a6dacacSDimitry Andric /// VPRecipeBase and VPValue separately.
707e8d8bef9SDimitry Andric class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,
708fe6060f1SDimitry Andric public VPDef,
709fe6060f1SDimitry Andric public VPUser {
7100b57cec5SDimitry Andric friend VPBasicBlock;
711480093f4SDimitry Andric friend class VPBlockUtils;
7120b57cec5SDimitry Andric
7130b57cec5SDimitry Andric /// Each VPRecipe belongs to a single VPBasicBlock.
7140b57cec5SDimitry Andric VPBasicBlock *Parent = nullptr;
7150b57cec5SDimitry Andric
7165f757f3fSDimitry Andric /// The debug location for the recipe.
7175f757f3fSDimitry Andric DebugLoc DL;
7185f757f3fSDimitry Andric
7190b57cec5SDimitry Andric public:
7205f757f3fSDimitry Andric VPRecipeBase(const unsigned char SC, ArrayRef<VPValue *> Operands,
7215f757f3fSDimitry Andric DebugLoc DL = {})
VPDef(SC)7225f757f3fSDimitry Andric : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe), DL(DL) {}
723fe6060f1SDimitry Andric
724fe6060f1SDimitry Andric template <typename IterT>
7255f757f3fSDimitry Andric VPRecipeBase(const unsigned char SC, iterator_range<IterT> Operands,
7265f757f3fSDimitry Andric DebugLoc DL = {})
VPDef(SC)7275f757f3fSDimitry Andric : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe), DL(DL) {}
7280b57cec5SDimitry Andric virtual ~VPRecipeBase() = default;
7290b57cec5SDimitry Andric
7300b57cec5SDimitry Andric /// \return the VPBasicBlock which this VPRecipe belongs to.
getParent()7310b57cec5SDimitry Andric VPBasicBlock *getParent() { return Parent; }
getParent()7320b57cec5SDimitry Andric const VPBasicBlock *getParent() const { return Parent; }
7330b57cec5SDimitry Andric
7340b57cec5SDimitry Andric /// The method which generates the output IR instructions that correspond to
7350b57cec5SDimitry Andric /// this VPRecipe, thereby "executing" the VPlan.
736bdd1243dSDimitry Andric virtual void execute(VPTransformState &State) = 0;
7370b57cec5SDimitry Andric
7380b57cec5SDimitry Andric /// Insert an unlinked recipe into a basic block immediately before
7390b57cec5SDimitry Andric /// the specified recipe.
7400b57cec5SDimitry Andric void insertBefore(VPRecipeBase *InsertPos);
74181ad6265SDimitry Andric /// Insert an unlinked recipe into \p BB immediately before the insertion
74281ad6265SDimitry Andric /// point \p IP;
74381ad6265SDimitry Andric void insertBefore(VPBasicBlock &BB, iplist<VPRecipeBase>::iterator IP);
7440b57cec5SDimitry Andric
745480093f4SDimitry Andric /// Insert an unlinked Recipe into a basic block immediately after
746480093f4SDimitry Andric /// the specified Recipe.
747480093f4SDimitry Andric void insertAfter(VPRecipeBase *InsertPos);
748480093f4SDimitry Andric
7498bcb0991SDimitry Andric /// Unlink this recipe from its current VPBasicBlock and insert it into
7508bcb0991SDimitry Andric /// the VPBasicBlock that MovePos lives in, right after MovePos.
7518bcb0991SDimitry Andric void moveAfter(VPRecipeBase *MovePos);
7528bcb0991SDimitry Andric
753e8d8bef9SDimitry Andric /// Unlink this recipe and insert into BB before I.
754e8d8bef9SDimitry Andric ///
755e8d8bef9SDimitry Andric /// \pre I is a valid iterator into BB.
756e8d8bef9SDimitry Andric void moveBefore(VPBasicBlock &BB, iplist<VPRecipeBase>::iterator I);
757e8d8bef9SDimitry Andric
758480093f4SDimitry Andric /// This method unlinks 'this' from the containing basic block, but does not
759480093f4SDimitry Andric /// delete it.
760480093f4SDimitry Andric void removeFromParent();
761480093f4SDimitry Andric
7620b57cec5SDimitry Andric /// This method unlinks 'this' from the containing basic block and deletes it.
7630b57cec5SDimitry Andric ///
7640b57cec5SDimitry Andric /// \returns an iterator pointing to the element after the erased one
7650b57cec5SDimitry Andric iplist<VPRecipeBase>::iterator eraseFromParent();
766e8d8bef9SDimitry Andric
767e8d8bef9SDimitry Andric /// Method to support type inquiry through isa, cast, and dyn_cast.
classof(const VPDef * D)768e8d8bef9SDimitry Andric static inline bool classof(const VPDef *D) {
769e8d8bef9SDimitry Andric // All VPDefs are also VPRecipeBases.
770e8d8bef9SDimitry Andric return true;
771e8d8bef9SDimitry Andric }
772fe6060f1SDimitry Andric
classof(const VPUser * U)773fe6060f1SDimitry Andric static inline bool classof(const VPUser *U) {
774fe6060f1SDimitry Andric return U->getVPUserID() == VPUser::VPUserID::Recipe;
775fe6060f1SDimitry Andric }
776fe6060f1SDimitry Andric
777fe6060f1SDimitry Andric /// Returns true if the recipe may have side-effects.
778fe6060f1SDimitry Andric bool mayHaveSideEffects() const;
779fe6060f1SDimitry Andric
780fe6060f1SDimitry Andric /// Returns true for PHI-like recipes.
isPhi()781fe6060f1SDimitry Andric bool isPhi() const {
782fe6060f1SDimitry Andric return getVPDefID() >= VPFirstPHISC && getVPDefID() <= VPLastPHISC;
783fe6060f1SDimitry Andric }
784fe6060f1SDimitry Andric
785fe6060f1SDimitry Andric /// Returns true if the recipe may read from memory.
786fe6060f1SDimitry Andric bool mayReadFromMemory() const;
787fe6060f1SDimitry Andric
788fe6060f1SDimitry Andric /// Returns true if the recipe may write to memory.
789fe6060f1SDimitry Andric bool mayWriteToMemory() const;
790fe6060f1SDimitry Andric
791fe6060f1SDimitry Andric /// Returns true if the recipe may read from or write to memory.
mayReadOrWriteMemory()792fe6060f1SDimitry Andric bool mayReadOrWriteMemory() const {
793fe6060f1SDimitry Andric return mayReadFromMemory() || mayWriteToMemory();
794fe6060f1SDimitry Andric }
7955f757f3fSDimitry Andric
7965f757f3fSDimitry Andric /// Returns the debug location of the recipe.
getDebugLoc()7975f757f3fSDimitry Andric DebugLoc getDebugLoc() const { return DL; }
7980b57cec5SDimitry Andric };
7990b57cec5SDimitry Andric
800bdd1243dSDimitry Andric // Helper macro to define common classof implementations for recipes.
801bdd1243dSDimitry Andric #define VP_CLASSOF_IMPL(VPDefID) \
802bdd1243dSDimitry Andric static inline bool classof(const VPDef *D) { \
803bdd1243dSDimitry Andric return D->getVPDefID() == VPDefID; \
804bdd1243dSDimitry Andric } \
805bdd1243dSDimitry Andric static inline bool classof(const VPValue *V) { \
806bdd1243dSDimitry Andric auto *R = V->getDefiningRecipe(); \
807bdd1243dSDimitry Andric return R && R->getVPDefID() == VPDefID; \
808bdd1243dSDimitry Andric } \
809bdd1243dSDimitry Andric static inline bool classof(const VPUser *U) { \
810bdd1243dSDimitry Andric auto *R = dyn_cast<VPRecipeBase>(U); \
811bdd1243dSDimitry Andric return R && R->getVPDefID() == VPDefID; \
812bdd1243dSDimitry Andric } \
813bdd1243dSDimitry Andric static inline bool classof(const VPRecipeBase *R) { \
814bdd1243dSDimitry Andric return R->getVPDefID() == VPDefID; \
8157a6dacacSDimitry Andric } \
8167a6dacacSDimitry Andric static inline bool classof(const VPSingleDefRecipe *R) { \
8177a6dacacSDimitry Andric return R->getVPDefID() == VPDefID; \
818e8d8bef9SDimitry Andric }
819e8d8bef9SDimitry Andric
8207a6dacacSDimitry Andric /// VPSingleDef is a base class for recipes for modeling a sequence of one or
8217a6dacacSDimitry Andric /// more output IR that define a single result VPValue.
8227a6dacacSDimitry Andric /// Note that VPRecipeBase must be inherited from before VPValue.
8237a6dacacSDimitry Andric class VPSingleDefRecipe : public VPRecipeBase, public VPValue {
8247a6dacacSDimitry Andric public:
8257a6dacacSDimitry Andric template <typename IterT>
8267a6dacacSDimitry Andric VPSingleDefRecipe(const unsigned char SC, IterT Operands, DebugLoc DL = {})
VPRecipeBase(SC,Operands,DL)8277a6dacacSDimitry Andric : VPRecipeBase(SC, Operands, DL), VPValue(this) {}
8287a6dacacSDimitry Andric
8297a6dacacSDimitry Andric VPSingleDefRecipe(const unsigned char SC, ArrayRef<VPValue *> Operands,
8307a6dacacSDimitry Andric DebugLoc DL = {})
VPRecipeBase(SC,Operands,DL)8317a6dacacSDimitry Andric : VPRecipeBase(SC, Operands, DL), VPValue(this) {}
8327a6dacacSDimitry Andric
8337a6dacacSDimitry Andric template <typename IterT>
8347a6dacacSDimitry Andric VPSingleDefRecipe(const unsigned char SC, IterT Operands, Value *UV,
8357a6dacacSDimitry Andric DebugLoc DL = {})
VPRecipeBase(SC,Operands,DL)8367a6dacacSDimitry Andric : VPRecipeBase(SC, Operands, DL), VPValue(this, UV) {}
8377a6dacacSDimitry Andric
classof(const VPRecipeBase * R)8387a6dacacSDimitry Andric static inline bool classof(const VPRecipeBase *R) {
8397a6dacacSDimitry Andric switch (R->getVPDefID()) {
8407a6dacacSDimitry Andric case VPRecipeBase::VPDerivedIVSC:
8417a6dacacSDimitry Andric case VPRecipeBase::VPExpandSCEVSC:
8427a6dacacSDimitry Andric case VPRecipeBase::VPInstructionSC:
8437a6dacacSDimitry Andric case VPRecipeBase::VPReductionSC:
8447a6dacacSDimitry Andric case VPRecipeBase::VPReplicateSC:
8457a6dacacSDimitry Andric case VPRecipeBase::VPScalarIVStepsSC:
8467a6dacacSDimitry Andric case VPRecipeBase::VPVectorPointerSC:
8477a6dacacSDimitry Andric case VPRecipeBase::VPWidenCallSC:
8487a6dacacSDimitry Andric case VPRecipeBase::VPWidenCanonicalIVSC:
8497a6dacacSDimitry Andric case VPRecipeBase::VPWidenCastSC:
8507a6dacacSDimitry Andric case VPRecipeBase::VPWidenGEPSC:
8517a6dacacSDimitry Andric case VPRecipeBase::VPWidenSC:
8527a6dacacSDimitry Andric case VPRecipeBase::VPWidenSelectSC:
8537a6dacacSDimitry Andric case VPRecipeBase::VPBlendSC:
8547a6dacacSDimitry Andric case VPRecipeBase::VPPredInstPHISC:
8557a6dacacSDimitry Andric case VPRecipeBase::VPCanonicalIVPHISC:
8567a6dacacSDimitry Andric case VPRecipeBase::VPActiveLaneMaskPHISC:
8577a6dacacSDimitry Andric case VPRecipeBase::VPFirstOrderRecurrencePHISC:
8587a6dacacSDimitry Andric case VPRecipeBase::VPWidenPHISC:
8597a6dacacSDimitry Andric case VPRecipeBase::VPWidenIntOrFpInductionSC:
8607a6dacacSDimitry Andric case VPRecipeBase::VPWidenPointerInductionSC:
8617a6dacacSDimitry Andric case VPRecipeBase::VPReductionPHISC:
8627a6dacacSDimitry Andric return true;
8637a6dacacSDimitry Andric case VPRecipeBase::VPInterleaveSC:
8647a6dacacSDimitry Andric case VPRecipeBase::VPBranchOnMaskSC:
8657a6dacacSDimitry Andric case VPRecipeBase::VPWidenMemoryInstructionSC:
8667a6dacacSDimitry Andric // TODO: Widened stores don't define a value, but widened loads do. Split
8677a6dacacSDimitry Andric // the recipes to be able to make widened loads VPSingleDefRecipes.
8687a6dacacSDimitry Andric return false;
8697a6dacacSDimitry Andric }
8707a6dacacSDimitry Andric llvm_unreachable("Unhandled VPDefID");
8717a6dacacSDimitry Andric }
8727a6dacacSDimitry Andric
classof(const VPUser * U)8737a6dacacSDimitry Andric static inline bool classof(const VPUser *U) {
8747a6dacacSDimitry Andric auto *R = dyn_cast<VPRecipeBase>(U);
8757a6dacacSDimitry Andric return R && classof(R);
8767a6dacacSDimitry Andric }
8777a6dacacSDimitry Andric
8787a6dacacSDimitry Andric /// Returns the underlying instruction.
getUnderlyingInstr()8797a6dacacSDimitry Andric Instruction *getUnderlyingInstr() {
8807a6dacacSDimitry Andric return cast<Instruction>(getUnderlyingValue());
8817a6dacacSDimitry Andric }
getUnderlyingInstr()8827a6dacacSDimitry Andric const Instruction *getUnderlyingInstr() const {
8837a6dacacSDimitry Andric return cast<Instruction>(getUnderlyingValue());
8847a6dacacSDimitry Andric }
8857a6dacacSDimitry Andric };
8867a6dacacSDimitry Andric
8875f757f3fSDimitry Andric /// Class to record LLVM IR flag for a recipe along with it.
8887a6dacacSDimitry Andric class VPRecipeWithIRFlags : public VPSingleDefRecipe {
8895f757f3fSDimitry Andric enum class OperationType : unsigned char {
8905f757f3fSDimitry Andric Cmp,
8915f757f3fSDimitry Andric OverflowingBinOp,
8925f757f3fSDimitry Andric DisjointOp,
8935f757f3fSDimitry Andric PossiblyExactOp,
8945f757f3fSDimitry Andric GEPOp,
8955f757f3fSDimitry Andric FPMathOp,
8965f757f3fSDimitry Andric NonNegOp,
8975f757f3fSDimitry Andric Other
8985f757f3fSDimitry Andric };
8995f757f3fSDimitry Andric
9005f757f3fSDimitry Andric public:
9015f757f3fSDimitry Andric struct WrapFlagsTy {
9025f757f3fSDimitry Andric char HasNUW : 1;
9035f757f3fSDimitry Andric char HasNSW : 1;
9045f757f3fSDimitry Andric
WrapFlagsTyWrapFlagsTy9055f757f3fSDimitry Andric WrapFlagsTy(bool HasNUW, bool HasNSW) : HasNUW(HasNUW), HasNSW(HasNSW) {}
9065f757f3fSDimitry Andric };
9075f757f3fSDimitry Andric
9081db9f3b2SDimitry Andric protected:
9091db9f3b2SDimitry Andric struct GEPFlagsTy {
9101db9f3b2SDimitry Andric char IsInBounds : 1;
GEPFlagsTyGEPFlagsTy9111db9f3b2SDimitry Andric GEPFlagsTy(bool IsInBounds) : IsInBounds(IsInBounds) {}
9121db9f3b2SDimitry Andric };
9131db9f3b2SDimitry Andric
9145f757f3fSDimitry Andric private:
9155f757f3fSDimitry Andric struct DisjointFlagsTy {
9165f757f3fSDimitry Andric char IsDisjoint : 1;
9175f757f3fSDimitry Andric };
9185f757f3fSDimitry Andric struct ExactFlagsTy {
9195f757f3fSDimitry Andric char IsExact : 1;
9205f757f3fSDimitry Andric };
9215f757f3fSDimitry Andric struct NonNegFlagsTy {
9225f757f3fSDimitry Andric char NonNeg : 1;
9235f757f3fSDimitry Andric };
9245f757f3fSDimitry Andric struct FastMathFlagsTy {
9255f757f3fSDimitry Andric char AllowReassoc : 1;
9265f757f3fSDimitry Andric char NoNaNs : 1;
9275f757f3fSDimitry Andric char NoInfs : 1;
9285f757f3fSDimitry Andric char NoSignedZeros : 1;
9295f757f3fSDimitry Andric char AllowReciprocal : 1;
9305f757f3fSDimitry Andric char AllowContract : 1;
9315f757f3fSDimitry Andric char ApproxFunc : 1;
9325f757f3fSDimitry Andric
9335f757f3fSDimitry Andric FastMathFlagsTy(const FastMathFlags &FMF);
9345f757f3fSDimitry Andric };
9355f757f3fSDimitry Andric
9365f757f3fSDimitry Andric OperationType OpType;
9375f757f3fSDimitry Andric
9385f757f3fSDimitry Andric union {
9395f757f3fSDimitry Andric CmpInst::Predicate CmpPredicate;
9405f757f3fSDimitry Andric WrapFlagsTy WrapFlags;
9415f757f3fSDimitry Andric DisjointFlagsTy DisjointFlags;
9425f757f3fSDimitry Andric ExactFlagsTy ExactFlags;
9435f757f3fSDimitry Andric GEPFlagsTy GEPFlags;
9445f757f3fSDimitry Andric NonNegFlagsTy NonNegFlags;
9455f757f3fSDimitry Andric FastMathFlagsTy FMFs;
9465f757f3fSDimitry Andric unsigned AllFlags;
9475f757f3fSDimitry Andric };
9485f757f3fSDimitry Andric
9495f757f3fSDimitry Andric public:
9505f757f3fSDimitry Andric template <typename IterT>
9515f757f3fSDimitry Andric VPRecipeWithIRFlags(const unsigned char SC, IterT Operands, DebugLoc DL = {})
VPSingleDefRecipe(SC,Operands,DL)9527a6dacacSDimitry Andric : VPSingleDefRecipe(SC, Operands, DL) {
9535f757f3fSDimitry Andric OpType = OperationType::Other;
9545f757f3fSDimitry Andric AllFlags = 0;
9555f757f3fSDimitry Andric }
9565f757f3fSDimitry Andric
9575f757f3fSDimitry Andric template <typename IterT>
VPRecipeWithIRFlags(const unsigned char SC,IterT Operands,Instruction & I)9585f757f3fSDimitry Andric VPRecipeWithIRFlags(const unsigned char SC, IterT Operands, Instruction &I)
9597a6dacacSDimitry Andric : VPSingleDefRecipe(SC, Operands, &I, I.getDebugLoc()) {
9605f757f3fSDimitry Andric if (auto *Op = dyn_cast<CmpInst>(&I)) {
9615f757f3fSDimitry Andric OpType = OperationType::Cmp;
9625f757f3fSDimitry Andric CmpPredicate = Op->getPredicate();
9635f757f3fSDimitry Andric } else if (auto *Op = dyn_cast<PossiblyDisjointInst>(&I)) {
9645f757f3fSDimitry Andric OpType = OperationType::DisjointOp;
9655f757f3fSDimitry Andric DisjointFlags.IsDisjoint = Op->isDisjoint();
9665f757f3fSDimitry Andric } else if (auto *Op = dyn_cast<OverflowingBinaryOperator>(&I)) {
9675f757f3fSDimitry Andric OpType = OperationType::OverflowingBinOp;
9685f757f3fSDimitry Andric WrapFlags = {Op->hasNoUnsignedWrap(), Op->hasNoSignedWrap()};
9695f757f3fSDimitry Andric } else if (auto *Op = dyn_cast<PossiblyExactOperator>(&I)) {
9705f757f3fSDimitry Andric OpType = OperationType::PossiblyExactOp;
9715f757f3fSDimitry Andric ExactFlags.IsExact = Op->isExact();
9725f757f3fSDimitry Andric } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
9735f757f3fSDimitry Andric OpType = OperationType::GEPOp;
9745f757f3fSDimitry Andric GEPFlags.IsInBounds = GEP->isInBounds();
9755f757f3fSDimitry Andric } else if (auto *PNNI = dyn_cast<PossiblyNonNegInst>(&I)) {
9765f757f3fSDimitry Andric OpType = OperationType::NonNegOp;
9775f757f3fSDimitry Andric NonNegFlags.NonNeg = PNNI->hasNonNeg();
9785f757f3fSDimitry Andric } else if (auto *Op = dyn_cast<FPMathOperator>(&I)) {
9795f757f3fSDimitry Andric OpType = OperationType::FPMathOp;
9805f757f3fSDimitry Andric FMFs = Op->getFastMathFlags();
9817a6dacacSDimitry Andric } else {
9827a6dacacSDimitry Andric OpType = OperationType::Other;
9837a6dacacSDimitry Andric AllFlags = 0;
9845f757f3fSDimitry Andric }
9855f757f3fSDimitry Andric }
9865f757f3fSDimitry Andric
9875f757f3fSDimitry Andric template <typename IterT>
9885f757f3fSDimitry Andric VPRecipeWithIRFlags(const unsigned char SC, IterT Operands,
9895f757f3fSDimitry Andric CmpInst::Predicate Pred, DebugLoc DL = {})
VPSingleDefRecipe(SC,Operands,DL)9907a6dacacSDimitry Andric : VPSingleDefRecipe(SC, Operands, DL), OpType(OperationType::Cmp),
9915f757f3fSDimitry Andric CmpPredicate(Pred) {}
9925f757f3fSDimitry Andric
9935f757f3fSDimitry Andric template <typename IterT>
9945f757f3fSDimitry Andric VPRecipeWithIRFlags(const unsigned char SC, IterT Operands,
9955f757f3fSDimitry Andric WrapFlagsTy WrapFlags, DebugLoc DL = {})
VPSingleDefRecipe(SC,Operands,DL)9967a6dacacSDimitry Andric : VPSingleDefRecipe(SC, Operands, DL),
9977a6dacacSDimitry Andric OpType(OperationType::OverflowingBinOp), WrapFlags(WrapFlags) {}
9985f757f3fSDimitry Andric
9995f757f3fSDimitry Andric template <typename IterT>
10005f757f3fSDimitry Andric VPRecipeWithIRFlags(const unsigned char SC, IterT Operands,
10015f757f3fSDimitry Andric FastMathFlags FMFs, DebugLoc DL = {})
VPSingleDefRecipe(SC,Operands,DL)10027a6dacacSDimitry Andric : VPSingleDefRecipe(SC, Operands, DL), OpType(OperationType::FPMathOp),
10035f757f3fSDimitry Andric FMFs(FMFs) {}
10045f757f3fSDimitry Andric
10051db9f3b2SDimitry Andric protected:
10061db9f3b2SDimitry Andric template <typename IterT>
10071db9f3b2SDimitry Andric VPRecipeWithIRFlags(const unsigned char SC, IterT Operands,
10081db9f3b2SDimitry Andric GEPFlagsTy GEPFlags, DebugLoc DL = {})
VPSingleDefRecipe(SC,Operands,DL)10097a6dacacSDimitry Andric : VPSingleDefRecipe(SC, Operands, DL), OpType(OperationType::GEPOp),
10101db9f3b2SDimitry Andric GEPFlags(GEPFlags) {}
10111db9f3b2SDimitry Andric
10121db9f3b2SDimitry Andric public:
classof(const VPRecipeBase * R)10135f757f3fSDimitry Andric static inline bool classof(const VPRecipeBase *R) {
10145f757f3fSDimitry Andric return R->getVPDefID() == VPRecipeBase::VPInstructionSC ||
10155f757f3fSDimitry Andric R->getVPDefID() == VPRecipeBase::VPWidenSC ||
10165f757f3fSDimitry Andric R->getVPDefID() == VPRecipeBase::VPWidenGEPSC ||
10175f757f3fSDimitry Andric R->getVPDefID() == VPRecipeBase::VPWidenCastSC ||
10181db9f3b2SDimitry Andric R->getVPDefID() == VPRecipeBase::VPReplicateSC ||
10191db9f3b2SDimitry Andric R->getVPDefID() == VPRecipeBase::VPVectorPointerSC;
10205f757f3fSDimitry Andric }
10215f757f3fSDimitry Andric
10225f757f3fSDimitry Andric /// Drop all poison-generating flags.
dropPoisonGeneratingFlags()10235f757f3fSDimitry Andric void dropPoisonGeneratingFlags() {
10245f757f3fSDimitry Andric // NOTE: This needs to be kept in-sync with
10255f757f3fSDimitry Andric // Instruction::dropPoisonGeneratingFlags.
10265f757f3fSDimitry Andric switch (OpType) {
10275f757f3fSDimitry Andric case OperationType::OverflowingBinOp:
10285f757f3fSDimitry Andric WrapFlags.HasNUW = false;
10295f757f3fSDimitry Andric WrapFlags.HasNSW = false;
10305f757f3fSDimitry Andric break;
10315f757f3fSDimitry Andric case OperationType::DisjointOp:
10325f757f3fSDimitry Andric DisjointFlags.IsDisjoint = false;
10335f757f3fSDimitry Andric break;
10345f757f3fSDimitry Andric case OperationType::PossiblyExactOp:
10355f757f3fSDimitry Andric ExactFlags.IsExact = false;
10365f757f3fSDimitry Andric break;
10375f757f3fSDimitry Andric case OperationType::GEPOp:
10385f757f3fSDimitry Andric GEPFlags.IsInBounds = false;
10395f757f3fSDimitry Andric break;
10405f757f3fSDimitry Andric case OperationType::FPMathOp:
10415f757f3fSDimitry Andric FMFs.NoNaNs = false;
10425f757f3fSDimitry Andric FMFs.NoInfs = false;
10435f757f3fSDimitry Andric break;
10445f757f3fSDimitry Andric case OperationType::NonNegOp:
10455f757f3fSDimitry Andric NonNegFlags.NonNeg = false;
10465f757f3fSDimitry Andric break;
10475f757f3fSDimitry Andric case OperationType::Cmp:
10485f757f3fSDimitry Andric case OperationType::Other:
10495f757f3fSDimitry Andric break;
10505f757f3fSDimitry Andric }
10515f757f3fSDimitry Andric }
10525f757f3fSDimitry Andric
10535f757f3fSDimitry Andric /// Set the IR flags for \p I.
setFlags(Instruction * I)10545f757f3fSDimitry Andric void setFlags(Instruction *I) const {
10555f757f3fSDimitry Andric switch (OpType) {
10565f757f3fSDimitry Andric case OperationType::OverflowingBinOp:
10575f757f3fSDimitry Andric I->setHasNoUnsignedWrap(WrapFlags.HasNUW);
10585f757f3fSDimitry Andric I->setHasNoSignedWrap(WrapFlags.HasNSW);
10595f757f3fSDimitry Andric break;
10605f757f3fSDimitry Andric case OperationType::DisjointOp:
10615f757f3fSDimitry Andric cast<PossiblyDisjointInst>(I)->setIsDisjoint(DisjointFlags.IsDisjoint);
10625f757f3fSDimitry Andric break;
10635f757f3fSDimitry Andric case OperationType::PossiblyExactOp:
10645f757f3fSDimitry Andric I->setIsExact(ExactFlags.IsExact);
10655f757f3fSDimitry Andric break;
10665f757f3fSDimitry Andric case OperationType::GEPOp:
10675f757f3fSDimitry Andric cast<GetElementPtrInst>(I)->setIsInBounds(GEPFlags.IsInBounds);
10685f757f3fSDimitry Andric break;
10695f757f3fSDimitry Andric case OperationType::FPMathOp:
10705f757f3fSDimitry Andric I->setHasAllowReassoc(FMFs.AllowReassoc);
10715f757f3fSDimitry Andric I->setHasNoNaNs(FMFs.NoNaNs);
10725f757f3fSDimitry Andric I->setHasNoInfs(FMFs.NoInfs);
10735f757f3fSDimitry Andric I->setHasNoSignedZeros(FMFs.NoSignedZeros);
10745f757f3fSDimitry Andric I->setHasAllowReciprocal(FMFs.AllowReciprocal);
10755f757f3fSDimitry Andric I->setHasAllowContract(FMFs.AllowContract);
10765f757f3fSDimitry Andric I->setHasApproxFunc(FMFs.ApproxFunc);
10775f757f3fSDimitry Andric break;
10785f757f3fSDimitry Andric case OperationType::NonNegOp:
10795f757f3fSDimitry Andric I->setNonNeg(NonNegFlags.NonNeg);
10805f757f3fSDimitry Andric break;
10815f757f3fSDimitry Andric case OperationType::Cmp:
10825f757f3fSDimitry Andric case OperationType::Other:
10835f757f3fSDimitry Andric break;
10845f757f3fSDimitry Andric }
10855f757f3fSDimitry Andric }
10865f757f3fSDimitry Andric
getPredicate()10875f757f3fSDimitry Andric CmpInst::Predicate getPredicate() const {
10885f757f3fSDimitry Andric assert(OpType == OperationType::Cmp &&
10895f757f3fSDimitry Andric "recipe doesn't have a compare predicate");
10905f757f3fSDimitry Andric return CmpPredicate;
10915f757f3fSDimitry Andric }
10925f757f3fSDimitry Andric
isInBounds()10935f757f3fSDimitry Andric bool isInBounds() const {
10945f757f3fSDimitry Andric assert(OpType == OperationType::GEPOp &&
10955f757f3fSDimitry Andric "recipe doesn't have inbounds flag");
10965f757f3fSDimitry Andric return GEPFlags.IsInBounds;
10975f757f3fSDimitry Andric }
10985f757f3fSDimitry Andric
10995f757f3fSDimitry Andric /// Returns true if the recipe has fast-math flags.
hasFastMathFlags()11005f757f3fSDimitry Andric bool hasFastMathFlags() const { return OpType == OperationType::FPMathOp; }
11015f757f3fSDimitry Andric
11025f757f3fSDimitry Andric FastMathFlags getFastMathFlags() const;
11035f757f3fSDimitry Andric
hasNoUnsignedWrap()11045f757f3fSDimitry Andric bool hasNoUnsignedWrap() const {
11055f757f3fSDimitry Andric assert(OpType == OperationType::OverflowingBinOp &&
11065f757f3fSDimitry Andric "recipe doesn't have a NUW flag");
11075f757f3fSDimitry Andric return WrapFlags.HasNUW;
11085f757f3fSDimitry Andric }
11095f757f3fSDimitry Andric
hasNoSignedWrap()11105f757f3fSDimitry Andric bool hasNoSignedWrap() const {
11115f757f3fSDimitry Andric assert(OpType == OperationType::OverflowingBinOp &&
11125f757f3fSDimitry Andric "recipe doesn't have a NSW flag");
11135f757f3fSDimitry Andric return WrapFlags.HasNSW;
11145f757f3fSDimitry Andric }
11155f757f3fSDimitry Andric
11165f757f3fSDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
11175f757f3fSDimitry Andric void printFlags(raw_ostream &O) const;
11185f757f3fSDimitry Andric #endif
11195f757f3fSDimitry Andric };
11205f757f3fSDimitry Andric
11210b57cec5SDimitry Andric /// This is a concrete Recipe that models a single VPlan-level instruction.
11220b57cec5SDimitry Andric /// While as any Recipe it may generate a sequence of IR instructions when
11230b57cec5SDimitry Andric /// executed, these instructions would always form a single-def expression as
11240b57cec5SDimitry Andric /// the VPInstruction is also a single def-use vertex.
11257a6dacacSDimitry Andric class VPInstruction : public VPRecipeWithIRFlags {
11260b57cec5SDimitry Andric friend class VPlanSlp;
11270b57cec5SDimitry Andric
11280b57cec5SDimitry Andric public:
11290b57cec5SDimitry Andric /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
11300b57cec5SDimitry Andric enum {
1131fe6060f1SDimitry Andric FirstOrderRecurrenceSplice =
1132fe6060f1SDimitry Andric Instruction::OtherOpsEnd + 1, // Combines the incoming and previous
1133fe6060f1SDimitry Andric // values of a first-order recurrence.
1134fe6060f1SDimitry Andric Not,
11350b57cec5SDimitry Andric SLPLoad,
11360b57cec5SDimitry Andric SLPStore,
11375ffd83dbSDimitry Andric ActiveLaneMask,
113806c3fb27SDimitry Andric CalculateTripCountMinusVF,
11395f757f3fSDimitry Andric // Increment the canonical IV separately for each unrolled part.
1140753f127fSDimitry Andric CanonicalIVIncrementForPart,
114104eeddc0SDimitry Andric BranchOnCount,
11421db9f3b2SDimitry Andric BranchOnCond,
11431db9f3b2SDimitry Andric ComputeReductionResult,
11440b57cec5SDimitry Andric };
11450b57cec5SDimitry Andric
11460b57cec5SDimitry Andric private:
11470b57cec5SDimitry Andric typedef unsigned char OpcodeTy;
11480b57cec5SDimitry Andric OpcodeTy Opcode;
11490b57cec5SDimitry Andric
1150753f127fSDimitry Andric /// An optional name that can be used for the generated IR instruction.
1151753f127fSDimitry Andric const std::string Name;
1152753f127fSDimitry Andric
11530b57cec5SDimitry Andric /// Utility method serving execute(): generates a single instance of the
115406c3fb27SDimitry Andric /// modeled instruction. \returns the generated value for \p Part.
115506c3fb27SDimitry Andric /// In some cases an existing value is returned rather than a generated
115606c3fb27SDimitry Andric /// one.
115706c3fb27SDimitry Andric Value *generateInstruction(VPTransformState &State, unsigned Part);
11580b57cec5SDimitry Andric
11595f757f3fSDimitry Andric #if !defined(NDEBUG)
11605f757f3fSDimitry Andric /// Return true if the VPInstruction is a floating point math operation, i.e.
11615f757f3fSDimitry Andric /// has fast-math flags.
11625f757f3fSDimitry Andric bool isFPMathOp() const;
11635f757f3fSDimitry Andric #endif
11645f757f3fSDimitry Andric
11650b57cec5SDimitry Andric protected:
setUnderlyingInstr(Instruction * I)11660b57cec5SDimitry Andric void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); }
11670b57cec5SDimitry Andric
11680b57cec5SDimitry Andric public:
1169753f127fSDimitry Andric VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands, DebugLoc DL,
1170753f127fSDimitry Andric const Twine &Name = "")
VPRecipeWithIRFlags(VPDef::VPInstructionSC,Operands,DL)11715f757f3fSDimitry Andric : VPRecipeWithIRFlags(VPDef::VPInstructionSC, Operands, DL),
11727a6dacacSDimitry Andric Opcode(Opcode), Name(Name.str()) {}
1173e8d8bef9SDimitry Andric
11740eae32dcSDimitry Andric VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands,
1175753f127fSDimitry Andric DebugLoc DL = {}, const Twine &Name = "")
VPInstruction(Opcode,ArrayRef<VPValue * > (Operands),DL,Name)1176753f127fSDimitry Andric : VPInstruction(Opcode, ArrayRef<VPValue *>(Operands), DL, Name) {}
11770b57cec5SDimitry Andric
11785f757f3fSDimitry Andric VPInstruction(unsigned Opcode, CmpInst::Predicate Pred, VPValue *A,
11795f757f3fSDimitry Andric VPValue *B, DebugLoc DL = {}, const Twine &Name = "");
11800b57cec5SDimitry Andric
11815f757f3fSDimitry Andric VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands,
11825f757f3fSDimitry Andric WrapFlagsTy WrapFlags, DebugLoc DL = {}, const Twine &Name = "")
VPRecipeWithIRFlags(VPDef::VPInstructionSC,Operands,WrapFlags,DL)11835f757f3fSDimitry Andric : VPRecipeWithIRFlags(VPDef::VPInstructionSC, Operands, WrapFlags, DL),
11847a6dacacSDimitry Andric Opcode(Opcode), Name(Name.str()) {}
11855f757f3fSDimitry Andric
11865f757f3fSDimitry Andric VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands,
11875f757f3fSDimitry Andric FastMathFlags FMFs, DebugLoc DL = {}, const Twine &Name = "");
11885f757f3fSDimitry Andric
VP_CLASSOF_IMPL(VPDef::VPInstructionSC)11895f757f3fSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPInstructionSC)
11900b57cec5SDimitry Andric
11910b57cec5SDimitry Andric unsigned getOpcode() const { return Opcode; }
11920b57cec5SDimitry Andric
11930b57cec5SDimitry Andric /// Generate the instruction.
11940b57cec5SDimitry Andric /// TODO: We currently execute only per-part unless a specific instance is
11950b57cec5SDimitry Andric /// provided.
11960b57cec5SDimitry Andric void execute(VPTransformState &State) override;
11970b57cec5SDimitry Andric
1198fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1199e8d8bef9SDimitry Andric /// Print the VPInstruction to \p O.
12005ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
12015ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
12020b57cec5SDimitry Andric
1203e8d8bef9SDimitry Andric /// Print the VPInstruction to dbgs() (for debugging).
1204fe6060f1SDimitry Andric LLVM_DUMP_METHOD void dump() const;
1205fe6060f1SDimitry Andric #endif
12060b57cec5SDimitry Andric
12070b57cec5SDimitry Andric /// Return true if this instruction may modify memory.
mayWriteToMemory()12080b57cec5SDimitry Andric bool mayWriteToMemory() const {
12090b57cec5SDimitry Andric // TODO: we can use attributes of the called function to rule out memory
12100b57cec5SDimitry Andric // modifications.
12110b57cec5SDimitry Andric return Opcode == Instruction::Store || Opcode == Instruction::Call ||
12120b57cec5SDimitry Andric Opcode == Instruction::Invoke || Opcode == SLPStore;
12130b57cec5SDimitry Andric }
12145ffd83dbSDimitry Andric
hasResult()12155ffd83dbSDimitry Andric bool hasResult() const {
12165ffd83dbSDimitry Andric // CallInst may or may not have a result, depending on the called function.
12175ffd83dbSDimitry Andric // Conservatively return calls have results for now.
12185ffd83dbSDimitry Andric switch (getOpcode()) {
12195ffd83dbSDimitry Andric case Instruction::Ret:
12205ffd83dbSDimitry Andric case Instruction::Br:
12215ffd83dbSDimitry Andric case Instruction::Store:
12225ffd83dbSDimitry Andric case Instruction::Switch:
12235ffd83dbSDimitry Andric case Instruction::IndirectBr:
12245ffd83dbSDimitry Andric case Instruction::Resume:
12255ffd83dbSDimitry Andric case Instruction::CatchRet:
12265ffd83dbSDimitry Andric case Instruction::Unreachable:
12275ffd83dbSDimitry Andric case Instruction::Fence:
12285ffd83dbSDimitry Andric case Instruction::AtomicRMW:
122981ad6265SDimitry Andric case VPInstruction::BranchOnCond:
123004eeddc0SDimitry Andric case VPInstruction::BranchOnCount:
12315ffd83dbSDimitry Andric return false;
12325ffd83dbSDimitry Andric default:
12335ffd83dbSDimitry Andric return true;
12345ffd83dbSDimitry Andric }
12355ffd83dbSDimitry Andric }
12364824e7fdSDimitry Andric
12371fd87a68SDimitry Andric /// Returns true if the recipe only uses the first lane of operand \p Op.
onlyFirstLaneUsed(const VPValue * Op)12381fd87a68SDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
12391fd87a68SDimitry Andric assert(is_contained(operands(), Op) &&
12401fd87a68SDimitry Andric "Op must be an operand of the recipe");
12411fd87a68SDimitry Andric if (getOperand(0) != Op)
12421fd87a68SDimitry Andric return false;
12431fd87a68SDimitry Andric switch (getOpcode()) {
12441fd87a68SDimitry Andric default:
12451fd87a68SDimitry Andric return false;
12461fd87a68SDimitry Andric case VPInstruction::ActiveLaneMask:
124706c3fb27SDimitry Andric case VPInstruction::CalculateTripCountMinusVF:
1248753f127fSDimitry Andric case VPInstruction::CanonicalIVIncrementForPart:
12495f757f3fSDimitry Andric case VPInstruction::BranchOnCount:
12505f757f3fSDimitry Andric return true;
12515f757f3fSDimitry Andric };
12525f757f3fSDimitry Andric llvm_unreachable("switch should return");
12535f757f3fSDimitry Andric }
12545f757f3fSDimitry Andric
12555f757f3fSDimitry Andric /// Returns true if the recipe only uses the first part of operand \p Op.
onlyFirstPartUsed(const VPValue * Op)12565f757f3fSDimitry Andric bool onlyFirstPartUsed(const VPValue *Op) const override {
12575f757f3fSDimitry Andric assert(is_contained(operands(), Op) &&
12585f757f3fSDimitry Andric "Op must be an operand of the recipe");
12595f757f3fSDimitry Andric if (getOperand(0) != Op)
12605f757f3fSDimitry Andric return false;
12615f757f3fSDimitry Andric switch (getOpcode()) {
12625f757f3fSDimitry Andric default:
12635f757f3fSDimitry Andric return false;
12641fd87a68SDimitry Andric case VPInstruction::BranchOnCount:
12651fd87a68SDimitry Andric return true;
12661fd87a68SDimitry Andric };
12671fd87a68SDimitry Andric llvm_unreachable("switch should return");
12681fd87a68SDimitry Andric }
12690b57cec5SDimitry Andric };
12700b57cec5SDimitry Andric
12715ffd83dbSDimitry Andric /// VPWidenRecipe is a recipe for producing a copy of vector type its
12725ffd83dbSDimitry Andric /// ingredient. This recipe covers most of the traditional vectorization cases
12735ffd83dbSDimitry Andric /// where each ingredient transforms into a vectorized version of itself.
12747a6dacacSDimitry Andric class VPWidenRecipe : public VPRecipeWithIRFlags {
12755f757f3fSDimitry Andric unsigned Opcode;
127606c3fb27SDimitry Andric
12770b57cec5SDimitry Andric public:
12785ffd83dbSDimitry Andric template <typename IterT>
VPWidenRecipe(Instruction & I,iterator_range<IterT> Operands)12795ffd83dbSDimitry Andric VPWidenRecipe(Instruction &I, iterator_range<IterT> Operands)
12807a6dacacSDimitry Andric : VPRecipeWithIRFlags(VPDef::VPWidenSC, Operands, I),
12815f757f3fSDimitry Andric Opcode(I.getOpcode()) {}
12820b57cec5SDimitry Andric
12830b57cec5SDimitry Andric ~VPWidenRecipe() override = default;
12840b57cec5SDimitry Andric
1285bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenSC)
12860b57cec5SDimitry Andric
12870b57cec5SDimitry Andric /// Produce widened copies of all Ingredients.
12880b57cec5SDimitry Andric void execute(VPTransformState &State) override;
12890b57cec5SDimitry Andric
getOpcode()12905f757f3fSDimitry Andric unsigned getOpcode() const { return Opcode; }
12915f757f3fSDimitry Andric
1292fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
12935ffd83dbSDimitry Andric /// Print the recipe.
12945ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
12955ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
1296fe6060f1SDimitry Andric #endif
12975ffd83dbSDimitry Andric };
12985ffd83dbSDimitry Andric
129906c3fb27SDimitry Andric /// VPWidenCastRecipe is a recipe to create vector cast instructions.
13007a6dacacSDimitry Andric class VPWidenCastRecipe : public VPRecipeWithIRFlags {
130106c3fb27SDimitry Andric /// Cast instruction opcode.
130206c3fb27SDimitry Andric Instruction::CastOps Opcode;
130306c3fb27SDimitry Andric
130406c3fb27SDimitry Andric /// Result type for the cast.
130506c3fb27SDimitry Andric Type *ResultTy;
130606c3fb27SDimitry Andric
130706c3fb27SDimitry Andric public:
VPWidenCastRecipe(Instruction::CastOps Opcode,VPValue * Op,Type * ResultTy,CastInst & UI)130806c3fb27SDimitry Andric VPWidenCastRecipe(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy,
13095f757f3fSDimitry Andric CastInst &UI)
13107a6dacacSDimitry Andric : VPRecipeWithIRFlags(VPDef::VPWidenCastSC, Op, UI), Opcode(Opcode),
13117a6dacacSDimitry Andric ResultTy(ResultTy) {
13125f757f3fSDimitry Andric assert(UI.getOpcode() == Opcode &&
131306c3fb27SDimitry Andric "opcode of underlying cast doesn't match");
13145f757f3fSDimitry Andric assert(UI.getType() == ResultTy &&
131506c3fb27SDimitry Andric "result type of underlying cast doesn't match");
131606c3fb27SDimitry Andric }
131706c3fb27SDimitry Andric
VPWidenCastRecipe(Instruction::CastOps Opcode,VPValue * Op,Type * ResultTy)13185f757f3fSDimitry Andric VPWidenCastRecipe(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy)
13197a6dacacSDimitry Andric : VPRecipeWithIRFlags(VPDef::VPWidenCastSC, Op), Opcode(Opcode),
13207a6dacacSDimitry Andric ResultTy(ResultTy) {}
13215f757f3fSDimitry Andric
132206c3fb27SDimitry Andric ~VPWidenCastRecipe() override = default;
132306c3fb27SDimitry Andric
132406c3fb27SDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenCastSC)
132506c3fb27SDimitry Andric
132606c3fb27SDimitry Andric /// Produce widened copies of the cast.
132706c3fb27SDimitry Andric void execute(VPTransformState &State) override;
132806c3fb27SDimitry Andric
132906c3fb27SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
133006c3fb27SDimitry Andric /// Print the recipe.
133106c3fb27SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
133206c3fb27SDimitry Andric VPSlotTracker &SlotTracker) const override;
133306c3fb27SDimitry Andric #endif
133406c3fb27SDimitry Andric
getOpcode()133506c3fb27SDimitry Andric Instruction::CastOps getOpcode() const { return Opcode; }
133606c3fb27SDimitry Andric
133706c3fb27SDimitry Andric /// Returns the result type of the cast.
getResultType()133806c3fb27SDimitry Andric Type *getResultType() const { return ResultTy; }
133906c3fb27SDimitry Andric };
134006c3fb27SDimitry Andric
13415ffd83dbSDimitry Andric /// A recipe for widening Call instructions.
13427a6dacacSDimitry Andric class VPWidenCallRecipe : public VPSingleDefRecipe {
1343bdd1243dSDimitry Andric /// ID of the vector intrinsic to call when widening the call. If set the
1344bdd1243dSDimitry Andric /// Intrinsic::not_intrinsic, a library call will be used instead.
1345bdd1243dSDimitry Andric Intrinsic::ID VectorIntrinsicID;
134606c3fb27SDimitry Andric /// If this recipe represents a library call, Variant stores a pointer to
134706c3fb27SDimitry Andric /// the chosen function. There is a 1:1 mapping between a given VF and the
134806c3fb27SDimitry Andric /// chosen vectorized variant, so there will be a different vplan for each
134906c3fb27SDimitry Andric /// VF with a valid variant.
135006c3fb27SDimitry Andric Function *Variant;
13515ffd83dbSDimitry Andric
13525ffd83dbSDimitry Andric public:
13535ffd83dbSDimitry Andric template <typename IterT>
1354bdd1243dSDimitry Andric VPWidenCallRecipe(CallInst &I, iterator_range<IterT> CallArguments,
13557a6dacacSDimitry Andric Intrinsic::ID VectorIntrinsicID, DebugLoc DL = {},
135606c3fb27SDimitry Andric Function *Variant = nullptr)
13577a6dacacSDimitry Andric : VPSingleDefRecipe(VPDef::VPWidenCallSC, CallArguments, &I, DL),
135806c3fb27SDimitry Andric VectorIntrinsicID(VectorIntrinsicID), Variant(Variant) {}
13595ffd83dbSDimitry Andric
13605ffd83dbSDimitry Andric ~VPWidenCallRecipe() override = default;
13615ffd83dbSDimitry Andric
1362bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenCallSC)
13630b57cec5SDimitry Andric
13645ffd83dbSDimitry Andric /// Produce a widened version of the call instruction.
13655ffd83dbSDimitry Andric void execute(VPTransformState &State) override;
13665ffd83dbSDimitry Andric
1367fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
13680b57cec5SDimitry Andric /// Print the recipe.
13695ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
13705ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
1371fe6060f1SDimitry Andric #endif
13725ffd83dbSDimitry Andric };
13735ffd83dbSDimitry Andric
13745ffd83dbSDimitry Andric /// A recipe for widening select instructions.
13757a6dacacSDimitry Andric struct VPWidenSelectRecipe : public VPSingleDefRecipe {
13765ffd83dbSDimitry Andric template <typename IterT>
VPWidenSelectRecipeVPWidenSelectRecipe137706c3fb27SDimitry Andric VPWidenSelectRecipe(SelectInst &I, iterator_range<IterT> Operands)
13787a6dacacSDimitry Andric : VPSingleDefRecipe(VPDef::VPWidenSelectSC, Operands, &I,
13797a6dacacSDimitry Andric I.getDebugLoc()) {}
13805ffd83dbSDimitry Andric
13815ffd83dbSDimitry Andric ~VPWidenSelectRecipe() override = default;
13825ffd83dbSDimitry Andric
1383bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenSelectSC)
13845ffd83dbSDimitry Andric
13855ffd83dbSDimitry Andric /// Produce a widened version of the select instruction.
13865ffd83dbSDimitry Andric void execute(VPTransformState &State) override;
13875ffd83dbSDimitry Andric
1388fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
13895ffd83dbSDimitry Andric /// Print the recipe.
13905ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
13915ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
1392fe6060f1SDimitry Andric #endif
139306c3fb27SDimitry Andric
getCondVPWidenSelectRecipe139406c3fb27SDimitry Andric VPValue *getCond() const {
139506c3fb27SDimitry Andric return getOperand(0);
139606c3fb27SDimitry Andric }
139706c3fb27SDimitry Andric
isInvariantCondVPWidenSelectRecipe139806c3fb27SDimitry Andric bool isInvariantCond() const {
139906c3fb27SDimitry Andric return getCond()->isDefinedOutsideVectorRegions();
140006c3fb27SDimitry Andric }
14010b57cec5SDimitry Andric };
14020b57cec5SDimitry Andric
1403480093f4SDimitry Andric /// A recipe for handling GEP instructions.
14047a6dacacSDimitry Andric class VPWidenGEPRecipe : public VPRecipeWithIRFlags {
isPointerLoopInvariant()140506c3fb27SDimitry Andric bool isPointerLoopInvariant() const {
140606c3fb27SDimitry Andric return getOperand(0)->isDefinedOutsideVectorRegions();
140706c3fb27SDimitry Andric }
140806c3fb27SDimitry Andric
isIndexLoopInvariant(unsigned I)140906c3fb27SDimitry Andric bool isIndexLoopInvariant(unsigned I) const {
141006c3fb27SDimitry Andric return getOperand(I + 1)->isDefinedOutsideVectorRegions();
141106c3fb27SDimitry Andric }
141206c3fb27SDimitry Andric
areAllOperandsInvariant()141306c3fb27SDimitry Andric bool areAllOperandsInvariant() const {
141406c3fb27SDimitry Andric return all_of(operands(), [](VPValue *Op) {
141506c3fb27SDimitry Andric return Op->isDefinedOutsideVectorRegions();
141606c3fb27SDimitry Andric });
141706c3fb27SDimitry Andric }
1418480093f4SDimitry Andric
1419480093f4SDimitry Andric public:
14205ffd83dbSDimitry Andric template <typename IterT>
VPWidenGEPRecipe(GetElementPtrInst * GEP,iterator_range<IterT> Operands)1421e8d8bef9SDimitry Andric VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands)
14227a6dacacSDimitry Andric : VPRecipeWithIRFlags(VPDef::VPWidenGEPSC, Operands, *GEP) {}
1423e8d8bef9SDimitry Andric
1424480093f4SDimitry Andric ~VPWidenGEPRecipe() override = default;
1425480093f4SDimitry Andric
1426bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenGEPSC)
1427480093f4SDimitry Andric
1428480093f4SDimitry Andric /// Generate the gep nodes.
1429480093f4SDimitry Andric void execute(VPTransformState &State) override;
1430480093f4SDimitry Andric
1431fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1432480093f4SDimitry Andric /// Print the recipe.
14335ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
14345ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
1435fe6060f1SDimitry Andric #endif
1436480093f4SDimitry Andric };
1437480093f4SDimitry Andric
1438647cbc5dSDimitry Andric /// A recipe to compute the pointers for widened memory accesses of IndexTy for
1439647cbc5dSDimitry Andric /// all parts. If IsReverse is true, compute pointers for accessing the input in
1440647cbc5dSDimitry Andric /// reverse order per part.
14417a6dacacSDimitry Andric class VPVectorPointerRecipe : public VPRecipeWithIRFlags {
1442647cbc5dSDimitry Andric Type *IndexedTy;
1443647cbc5dSDimitry Andric bool IsReverse;
1444647cbc5dSDimitry Andric
1445647cbc5dSDimitry Andric public:
VPVectorPointerRecipe(VPValue * Ptr,Type * IndexedTy,bool IsReverse,bool IsInBounds,DebugLoc DL)1446647cbc5dSDimitry Andric VPVectorPointerRecipe(VPValue *Ptr, Type *IndexedTy, bool IsReverse,
14471db9f3b2SDimitry Andric bool IsInBounds, DebugLoc DL)
14481db9f3b2SDimitry Andric : VPRecipeWithIRFlags(VPDef::VPVectorPointerSC, ArrayRef<VPValue *>(Ptr),
14491db9f3b2SDimitry Andric GEPFlagsTy(IsInBounds), DL),
14507a6dacacSDimitry Andric IndexedTy(IndexedTy), IsReverse(IsReverse) {}
1451647cbc5dSDimitry Andric
1452647cbc5dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPVectorPointerSC)
1453647cbc5dSDimitry Andric
1454647cbc5dSDimitry Andric void execute(VPTransformState &State) override;
1455647cbc5dSDimitry Andric
onlyFirstLaneUsed(const VPValue * Op)1456647cbc5dSDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
1457647cbc5dSDimitry Andric assert(is_contained(operands(), Op) &&
1458647cbc5dSDimitry Andric "Op must be an operand of the recipe");
1459647cbc5dSDimitry Andric return true;
1460647cbc5dSDimitry Andric }
1461647cbc5dSDimitry Andric
1462647cbc5dSDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1463647cbc5dSDimitry Andric /// Print the recipe.
1464647cbc5dSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
1465647cbc5dSDimitry Andric VPSlotTracker &SlotTracker) const override;
1466647cbc5dSDimitry Andric #endif
1467647cbc5dSDimitry Andric };
1468647cbc5dSDimitry Andric
146904eeddc0SDimitry Andric /// A pure virtual base class for all recipes modeling header phis, including
147004eeddc0SDimitry Andric /// phis for first order recurrences, pointer inductions and reductions. The
147104eeddc0SDimitry Andric /// start value is the first operand of the recipe and the incoming value from
147204eeddc0SDimitry Andric /// the backedge is the second operand.
1473bdd1243dSDimitry Andric ///
1474bdd1243dSDimitry Andric /// Inductions are modeled using the following sub-classes:
1475bdd1243dSDimitry Andric /// * VPCanonicalIVPHIRecipe: Canonical scalar induction of the vector loop,
1476bdd1243dSDimitry Andric /// starting at a specified value (zero for the main vector loop, the resume
1477bdd1243dSDimitry Andric /// value for the epilogue vector loop) and stepping by 1. The induction
1478bdd1243dSDimitry Andric /// controls exiting of the vector loop by comparing against the vector trip
1479bdd1243dSDimitry Andric /// count. Produces a single scalar PHI for the induction value per
1480bdd1243dSDimitry Andric /// iteration.
1481bdd1243dSDimitry Andric /// * VPWidenIntOrFpInductionRecipe: Generates vector values for integer and
1482bdd1243dSDimitry Andric /// floating point inductions with arbitrary start and step values. Produces
1483bdd1243dSDimitry Andric /// a vector PHI per-part.
1484bdd1243dSDimitry Andric /// * VPDerivedIVRecipe: Converts the canonical IV value to the corresponding
1485bdd1243dSDimitry Andric /// value of an IV with different start and step values. Produces a single
1486bdd1243dSDimitry Andric /// scalar value per iteration
1487bdd1243dSDimitry Andric /// * VPScalarIVStepsRecipe: Generates scalar values per-lane based on a
1488bdd1243dSDimitry Andric /// canonical or derived induction.
1489bdd1243dSDimitry Andric /// * VPWidenPointerInductionRecipe: Generate vector and scalar values for a
1490bdd1243dSDimitry Andric /// pointer induction. Produces either a vector PHI per-part or scalar values
1491bdd1243dSDimitry Andric /// per-lane based on the canonical induction.
14927a6dacacSDimitry Andric class VPHeaderPHIRecipe : public VPSingleDefRecipe {
1493fe6060f1SDimitry Andric protected:
149406c3fb27SDimitry Andric VPHeaderPHIRecipe(unsigned char VPDefID, Instruction *UnderlyingInstr,
14955f757f3fSDimitry Andric VPValue *Start = nullptr, DebugLoc DL = {})
VPSingleDefRecipe(VPDefID,ArrayRef<VPValue * > (),UnderlyingInstr,DL)14967a6dacacSDimitry Andric : VPSingleDefRecipe(VPDefID, ArrayRef<VPValue *>(), UnderlyingInstr, DL) {
1497fe6060f1SDimitry Andric if (Start)
1498fe6060f1SDimitry Andric addOperand(Start);
1499fe6060f1SDimitry Andric }
1500e8d8bef9SDimitry Andric
15010b57cec5SDimitry Andric public:
150204eeddc0SDimitry Andric ~VPHeaderPHIRecipe() override = default;
1503fe6060f1SDimitry Andric
150404eeddc0SDimitry Andric /// Method to support type inquiry through isa, cast, and dyn_cast.
classof(const VPRecipeBase * B)150504eeddc0SDimitry Andric static inline bool classof(const VPRecipeBase *B) {
1506bdd1243dSDimitry Andric return B->getVPDefID() >= VPDef::VPFirstHeaderPHISC &&
150706c3fb27SDimitry Andric B->getVPDefID() <= VPDef::VPLastHeaderPHISC;
150804eeddc0SDimitry Andric }
classof(const VPValue * V)150904eeddc0SDimitry Andric static inline bool classof(const VPValue *V) {
1510bdd1243dSDimitry Andric auto *B = V->getDefiningRecipe();
1511bdd1243dSDimitry Andric return B && B->getVPDefID() >= VPRecipeBase::VPFirstHeaderPHISC &&
151206c3fb27SDimitry Andric B->getVPDefID() <= VPRecipeBase::VPLastHeaderPHISC;
151304eeddc0SDimitry Andric }
151404eeddc0SDimitry Andric
151504eeddc0SDimitry Andric /// Generate the phi nodes.
151604eeddc0SDimitry Andric void execute(VPTransformState &State) override = 0;
151704eeddc0SDimitry Andric
151804eeddc0SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
151904eeddc0SDimitry Andric /// Print the recipe.
152004eeddc0SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
152104eeddc0SDimitry Andric VPSlotTracker &SlotTracker) const override = 0;
152204eeddc0SDimitry Andric #endif
152304eeddc0SDimitry Andric
152404eeddc0SDimitry Andric /// Returns the start value of the phi, if one is set.
getStartValue()152504eeddc0SDimitry Andric VPValue *getStartValue() {
152604eeddc0SDimitry Andric return getNumOperands() == 0 ? nullptr : getOperand(0);
152704eeddc0SDimitry Andric }
getStartValue()152881ad6265SDimitry Andric VPValue *getStartValue() const {
152981ad6265SDimitry Andric return getNumOperands() == 0 ? nullptr : getOperand(0);
153081ad6265SDimitry Andric }
153104eeddc0SDimitry Andric
1532bdd1243dSDimitry Andric /// Update the start value of the recipe.
setStartValue(VPValue * V)1533bdd1243dSDimitry Andric void setStartValue(VPValue *V) { setOperand(0, V); }
1534bdd1243dSDimitry Andric
153504eeddc0SDimitry Andric /// Returns the incoming value from the loop backedge.
getBackedgeValue()153606c3fb27SDimitry Andric virtual VPValue *getBackedgeValue() {
153704eeddc0SDimitry Andric return getOperand(1);
153804eeddc0SDimitry Andric }
153904eeddc0SDimitry Andric
154004eeddc0SDimitry Andric /// Returns the backedge value as a recipe. The backedge value is guaranteed
154104eeddc0SDimitry Andric /// to be a recipe.
getBackedgeRecipe()154206c3fb27SDimitry Andric virtual VPRecipeBase &getBackedgeRecipe() {
1543bdd1243dSDimitry Andric return *getBackedgeValue()->getDefiningRecipe();
154404eeddc0SDimitry Andric }
154504eeddc0SDimitry Andric };
154604eeddc0SDimitry Andric
154706c3fb27SDimitry Andric /// A recipe for handling phi nodes of integer and floating-point inductions,
154806c3fb27SDimitry Andric /// producing their vector values.
154906c3fb27SDimitry Andric class VPWidenIntOrFpInductionRecipe : public VPHeaderPHIRecipe {
155006c3fb27SDimitry Andric PHINode *IV;
155106c3fb27SDimitry Andric TruncInst *Trunc;
155206c3fb27SDimitry Andric const InductionDescriptor &IndDesc;
155306c3fb27SDimitry Andric
155406c3fb27SDimitry Andric public:
VPWidenIntOrFpInductionRecipe(PHINode * IV,VPValue * Start,VPValue * Step,const InductionDescriptor & IndDesc)155506c3fb27SDimitry Andric VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step,
155606c3fb27SDimitry Andric const InductionDescriptor &IndDesc)
155706c3fb27SDimitry Andric : VPHeaderPHIRecipe(VPDef::VPWidenIntOrFpInductionSC, IV, Start), IV(IV),
155806c3fb27SDimitry Andric Trunc(nullptr), IndDesc(IndDesc) {
155906c3fb27SDimitry Andric addOperand(Step);
156006c3fb27SDimitry Andric }
156106c3fb27SDimitry Andric
VPWidenIntOrFpInductionRecipe(PHINode * IV,VPValue * Start,VPValue * Step,const InductionDescriptor & IndDesc,TruncInst * Trunc)156206c3fb27SDimitry Andric VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step,
156306c3fb27SDimitry Andric const InductionDescriptor &IndDesc,
156406c3fb27SDimitry Andric TruncInst *Trunc)
156506c3fb27SDimitry Andric : VPHeaderPHIRecipe(VPDef::VPWidenIntOrFpInductionSC, Trunc, Start),
156606c3fb27SDimitry Andric IV(IV), Trunc(Trunc), IndDesc(IndDesc) {
156706c3fb27SDimitry Andric addOperand(Step);
156806c3fb27SDimitry Andric }
156906c3fb27SDimitry Andric
157006c3fb27SDimitry Andric ~VPWidenIntOrFpInductionRecipe() override = default;
157106c3fb27SDimitry Andric
157206c3fb27SDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenIntOrFpInductionSC)
157306c3fb27SDimitry Andric
157406c3fb27SDimitry Andric /// Generate the vectorized and scalarized versions of the phi node as
157506c3fb27SDimitry Andric /// needed by their users.
157606c3fb27SDimitry Andric void execute(VPTransformState &State) override;
157706c3fb27SDimitry Andric
157806c3fb27SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
157906c3fb27SDimitry Andric /// Print the recipe.
158006c3fb27SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
158106c3fb27SDimitry Andric VPSlotTracker &SlotTracker) const override;
158206c3fb27SDimitry Andric #endif
158306c3fb27SDimitry Andric
getBackedgeValue()158406c3fb27SDimitry Andric VPValue *getBackedgeValue() override {
158506c3fb27SDimitry Andric // TODO: All operands of base recipe must exist and be at same index in
158606c3fb27SDimitry Andric // derived recipe.
158706c3fb27SDimitry Andric llvm_unreachable(
158806c3fb27SDimitry Andric "VPWidenIntOrFpInductionRecipe generates its own backedge value");
158906c3fb27SDimitry Andric }
159006c3fb27SDimitry Andric
getBackedgeRecipe()159106c3fb27SDimitry Andric VPRecipeBase &getBackedgeRecipe() override {
159206c3fb27SDimitry Andric // TODO: All operands of base recipe must exist and be at same index in
159306c3fb27SDimitry Andric // derived recipe.
159406c3fb27SDimitry Andric llvm_unreachable(
159506c3fb27SDimitry Andric "VPWidenIntOrFpInductionRecipe generates its own backedge value");
159606c3fb27SDimitry Andric }
159706c3fb27SDimitry Andric
159806c3fb27SDimitry Andric /// Returns the step value of the induction.
getStepValue()159906c3fb27SDimitry Andric VPValue *getStepValue() { return getOperand(1); }
getStepValue()160006c3fb27SDimitry Andric const VPValue *getStepValue() const { return getOperand(1); }
160106c3fb27SDimitry Andric
160206c3fb27SDimitry Andric /// Returns the first defined value as TruncInst, if it is one or nullptr
160306c3fb27SDimitry Andric /// otherwise.
getTruncInst()160406c3fb27SDimitry Andric TruncInst *getTruncInst() { return Trunc; }
getTruncInst()160506c3fb27SDimitry Andric const TruncInst *getTruncInst() const { return Trunc; }
160606c3fb27SDimitry Andric
getPHINode()160706c3fb27SDimitry Andric PHINode *getPHINode() { return IV; }
160806c3fb27SDimitry Andric
160906c3fb27SDimitry Andric /// Returns the induction descriptor for the recipe.
getInductionDescriptor()161006c3fb27SDimitry Andric const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
161106c3fb27SDimitry Andric
161206c3fb27SDimitry Andric /// Returns true if the induction is canonical, i.e. starting at 0 and
161306c3fb27SDimitry Andric /// incremented by UF * VF (= the original IV is incremented by 1).
161406c3fb27SDimitry Andric bool isCanonical() const;
161506c3fb27SDimitry Andric
161606c3fb27SDimitry Andric /// Returns the scalar type of the induction.
getScalarType()16175f757f3fSDimitry Andric Type *getScalarType() const {
161806c3fb27SDimitry Andric return Trunc ? Trunc->getType() : IV->getType();
161906c3fb27SDimitry Andric }
162006c3fb27SDimitry Andric };
162106c3fb27SDimitry Andric
162281ad6265SDimitry Andric class VPWidenPointerInductionRecipe : public VPHeaderPHIRecipe {
162381ad6265SDimitry Andric const InductionDescriptor &IndDesc;
162481ad6265SDimitry Andric
16256246ae0bSDimitry Andric bool IsScalarAfterVectorization;
16266246ae0bSDimitry Andric
162781ad6265SDimitry Andric public:
162881ad6265SDimitry Andric /// Create a new VPWidenPointerInductionRecipe for \p Phi with start value \p
162981ad6265SDimitry Andric /// Start.
VPWidenPointerInductionRecipe(PHINode * Phi,VPValue * Start,VPValue * Step,const InductionDescriptor & IndDesc,bool IsScalarAfterVectorization)1630bdd1243dSDimitry Andric VPWidenPointerInductionRecipe(PHINode *Phi, VPValue *Start, VPValue *Step,
163181ad6265SDimitry Andric const InductionDescriptor &IndDesc,
16326246ae0bSDimitry Andric bool IsScalarAfterVectorization)
1633bdd1243dSDimitry Andric : VPHeaderPHIRecipe(VPDef::VPWidenPointerInductionSC, Phi),
1634bdd1243dSDimitry Andric IndDesc(IndDesc),
16356246ae0bSDimitry Andric IsScalarAfterVectorization(IsScalarAfterVectorization) {
163681ad6265SDimitry Andric addOperand(Start);
1637bdd1243dSDimitry Andric addOperand(Step);
163881ad6265SDimitry Andric }
163981ad6265SDimitry Andric
164081ad6265SDimitry Andric ~VPWidenPointerInductionRecipe() override = default;
164181ad6265SDimitry Andric
1642bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenPointerInductionSC)
164381ad6265SDimitry Andric
164481ad6265SDimitry Andric /// Generate vector values for the pointer induction.
164581ad6265SDimitry Andric void execute(VPTransformState &State) override;
164681ad6265SDimitry Andric
164781ad6265SDimitry Andric /// Returns true if only scalar values will be generated.
164881ad6265SDimitry Andric bool onlyScalarsGenerated(ElementCount VF);
164981ad6265SDimitry Andric
1650bdd1243dSDimitry Andric /// Returns the induction descriptor for the recipe.
getInductionDescriptor()1651bdd1243dSDimitry Andric const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
1652bdd1243dSDimitry Andric
165381ad6265SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
165481ad6265SDimitry Andric /// Print the recipe.
165581ad6265SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
165681ad6265SDimitry Andric VPSlotTracker &SlotTracker) const override;
165781ad6265SDimitry Andric #endif
165881ad6265SDimitry Andric };
165981ad6265SDimitry Andric
166004eeddc0SDimitry Andric /// A recipe for handling header phis that are widened in the vector loop.
166104eeddc0SDimitry Andric /// In the VPlan native path, all incoming VPValues & VPBasicBlock pairs are
166204eeddc0SDimitry Andric /// managed in the recipe directly.
166304eeddc0SDimitry Andric class VPWidenPHIRecipe : public VPHeaderPHIRecipe {
166404eeddc0SDimitry Andric /// List of incoming blocks. Only used in the VPlan native path.
166504eeddc0SDimitry Andric SmallVector<VPBasicBlock *, 2> IncomingBlocks;
166604eeddc0SDimitry Andric
166704eeddc0SDimitry Andric public:
1668fe6060f1SDimitry Andric /// Create a new VPWidenPHIRecipe for \p Phi with start value \p Start.
166904eeddc0SDimitry Andric VPWidenPHIRecipe(PHINode *Phi, VPValue *Start = nullptr)
VPHeaderPHIRecipe(VPDef::VPWidenPHISC,Phi)1670bdd1243dSDimitry Andric : VPHeaderPHIRecipe(VPDef::VPWidenPHISC, Phi) {
167104eeddc0SDimitry Andric if (Start)
167204eeddc0SDimitry Andric addOperand(Start);
1673e8d8bef9SDimitry Andric }
1674e8d8bef9SDimitry Andric
16750b57cec5SDimitry Andric ~VPWidenPHIRecipe() override = default;
16760b57cec5SDimitry Andric
1677bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenPHISC)
16780b57cec5SDimitry Andric
16790b57cec5SDimitry Andric /// Generate the phi/select nodes.
16800b57cec5SDimitry Andric void execute(VPTransformState &State) override;
16810b57cec5SDimitry Andric
1682fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
16830b57cec5SDimitry Andric /// Print the recipe.
16845ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
16855ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
1686fe6060f1SDimitry Andric #endif
1687e8d8bef9SDimitry Andric
1688fe6060f1SDimitry Andric /// Adds a pair (\p IncomingV, \p IncomingBlock) to the phi.
addIncoming(VPValue * IncomingV,VPBasicBlock * IncomingBlock)1689fe6060f1SDimitry Andric void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock) {
1690fe6060f1SDimitry Andric addOperand(IncomingV);
1691fe6060f1SDimitry Andric IncomingBlocks.push_back(IncomingBlock);
1692fe6060f1SDimitry Andric }
1693fe6060f1SDimitry Andric
1694fe6060f1SDimitry Andric /// Returns the \p I th incoming VPBasicBlock.
getIncomingBlock(unsigned I)1695fe6060f1SDimitry Andric VPBasicBlock *getIncomingBlock(unsigned I) { return IncomingBlocks[I]; }
169604eeddc0SDimitry Andric
169704eeddc0SDimitry Andric /// Returns the \p I th incoming VPValue.
getIncomingValue(unsigned I)169804eeddc0SDimitry Andric VPValue *getIncomingValue(unsigned I) { return getOperand(I); }
1699fe6060f1SDimitry Andric };
1700fe6060f1SDimitry Andric
1701fe6060f1SDimitry Andric /// A recipe for handling first-order recurrence phis. The start value is the
1702fe6060f1SDimitry Andric /// first operand of the recipe and the incoming value from the backedge is the
1703fe6060f1SDimitry Andric /// second operand.
170404eeddc0SDimitry Andric struct VPFirstOrderRecurrencePHIRecipe : public VPHeaderPHIRecipe {
VPFirstOrderRecurrencePHIRecipeVPFirstOrderRecurrencePHIRecipe1705fe6060f1SDimitry Andric VPFirstOrderRecurrencePHIRecipe(PHINode *Phi, VPValue &Start)
1706bdd1243dSDimitry Andric : VPHeaderPHIRecipe(VPDef::VPFirstOrderRecurrencePHISC, Phi, &Start) {}
1707fe6060f1SDimitry Andric
VP_CLASSOF_IMPLVPFirstOrderRecurrencePHIRecipe1708bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPFirstOrderRecurrencePHISC)
1709bdd1243dSDimitry Andric
171004eeddc0SDimitry Andric static inline bool classof(const VPHeaderPHIRecipe *R) {
1711bdd1243dSDimitry Andric return R->getVPDefID() == VPDef::VPFirstOrderRecurrencePHISC;
1712fe6060f1SDimitry Andric }
1713fe6060f1SDimitry Andric
1714fe6060f1SDimitry Andric void execute(VPTransformState &State) override;
1715fe6060f1SDimitry Andric
1716fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1717fe6060f1SDimitry Andric /// Print the recipe.
1718fe6060f1SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
1719fe6060f1SDimitry Andric VPSlotTracker &SlotTracker) const override;
1720fe6060f1SDimitry Andric #endif
1721fe6060f1SDimitry Andric };
1722fe6060f1SDimitry Andric
1723fe6060f1SDimitry Andric /// A recipe for handling reduction phis. The start value is the first operand
1724fe6060f1SDimitry Andric /// of the recipe and the incoming value from the backedge is the second
1725fe6060f1SDimitry Andric /// operand.
172604eeddc0SDimitry Andric class VPReductionPHIRecipe : public VPHeaderPHIRecipe {
1727fe6060f1SDimitry Andric /// Descriptor for the reduction.
17280eae32dcSDimitry Andric const RecurrenceDescriptor &RdxDesc;
1729fe6060f1SDimitry Andric
1730fe6060f1SDimitry Andric /// The phi is part of an in-loop reduction.
1731fe6060f1SDimitry Andric bool IsInLoop;
1732fe6060f1SDimitry Andric
1733fe6060f1SDimitry Andric /// The phi is part of an ordered reduction. Requires IsInLoop to be true.
1734fe6060f1SDimitry Andric bool IsOrdered;
1735fe6060f1SDimitry Andric
1736fe6060f1SDimitry Andric public:
1737fe6060f1SDimitry Andric /// Create a new VPReductionPHIRecipe for the reduction \p Phi described by \p
1738fe6060f1SDimitry Andric /// RdxDesc.
17390eae32dcSDimitry Andric VPReductionPHIRecipe(PHINode *Phi, const RecurrenceDescriptor &RdxDesc,
1740fe6060f1SDimitry Andric VPValue &Start, bool IsInLoop = false,
1741fe6060f1SDimitry Andric bool IsOrdered = false)
1742bdd1243dSDimitry Andric : VPHeaderPHIRecipe(VPDef::VPReductionPHISC, Phi, &Start),
1743fe6060f1SDimitry Andric RdxDesc(RdxDesc), IsInLoop(IsInLoop), IsOrdered(IsOrdered) {
1744fe6060f1SDimitry Andric assert((!IsOrdered || IsInLoop) && "IsOrdered requires IsInLoop");
1745fe6060f1SDimitry Andric }
1746fe6060f1SDimitry Andric
1747fe6060f1SDimitry Andric ~VPReductionPHIRecipe() override = default;
1748fe6060f1SDimitry Andric
VP_CLASSOF_IMPL(VPDef::VPReductionPHISC)1749bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPReductionPHISC)
1750bdd1243dSDimitry Andric
175104eeddc0SDimitry Andric static inline bool classof(const VPHeaderPHIRecipe *R) {
1752bdd1243dSDimitry Andric return R->getVPDefID() == VPDef::VPReductionPHISC;
1753fe6060f1SDimitry Andric }
1754fe6060f1SDimitry Andric
1755fe6060f1SDimitry Andric /// Generate the phi/select nodes.
1756fe6060f1SDimitry Andric void execute(VPTransformState &State) override;
1757fe6060f1SDimitry Andric
1758fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1759fe6060f1SDimitry Andric /// Print the recipe.
1760fe6060f1SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
1761fe6060f1SDimitry Andric VPSlotTracker &SlotTracker) const override;
1762fe6060f1SDimitry Andric #endif
1763fe6060f1SDimitry Andric
getRecurrenceDescriptor()17640eae32dcSDimitry Andric const RecurrenceDescriptor &getRecurrenceDescriptor() const {
17650eae32dcSDimitry Andric return RdxDesc;
17660eae32dcSDimitry Andric }
1767fe6060f1SDimitry Andric
1768fe6060f1SDimitry Andric /// Returns true, if the phi is part of an ordered reduction.
isOrdered()1769fe6060f1SDimitry Andric bool isOrdered() const { return IsOrdered; }
1770fe6060f1SDimitry Andric
1771fe6060f1SDimitry Andric /// Returns true, if the phi is part of an in-loop reduction.
isInLoop()1772fe6060f1SDimitry Andric bool isInLoop() const { return IsInLoop; }
17730b57cec5SDimitry Andric };
17740b57cec5SDimitry Andric
17750b57cec5SDimitry Andric /// A recipe for vectorizing a phi-node as a sequence of mask-based select
17760b57cec5SDimitry Andric /// instructions.
17777a6dacacSDimitry Andric class VPBlendRecipe : public VPSingleDefRecipe {
1778e8d8bef9SDimitry Andric public:
17795ffd83dbSDimitry Andric /// The blend operation is a User of the incoming values and of their
17805ffd83dbSDimitry Andric /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value
17815ffd83dbSDimitry Andric /// might be incoming with a full mask for which there is no VPValue.
VPBlendRecipe(PHINode * Phi,ArrayRef<VPValue * > Operands)17825ffd83dbSDimitry Andric VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands)
17837a6dacacSDimitry Andric : VPSingleDefRecipe(VPDef::VPBlendSC, Operands, Phi, Phi->getDebugLoc()) {
17845ffd83dbSDimitry Andric assert(Operands.size() > 0 &&
17855ffd83dbSDimitry Andric ((Operands.size() == 1) || (Operands.size() % 2 == 0)) &&
17865ffd83dbSDimitry Andric "Expected either a single incoming value or a positive even number "
17875ffd83dbSDimitry Andric "of operands");
17880b57cec5SDimitry Andric }
17890b57cec5SDimitry Andric
VP_CLASSOF_IMPL(VPDef::VPBlendSC)1790bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPBlendSC)
17910b57cec5SDimitry Andric
17925ffd83dbSDimitry Andric /// Return the number of incoming values, taking into account that a single
17935ffd83dbSDimitry Andric /// incoming value has no mask.
1794e8d8bef9SDimitry Andric unsigned getNumIncomingValues() const { return (getNumOperands() + 1) / 2; }
17955ffd83dbSDimitry Andric
17965ffd83dbSDimitry Andric /// Return incoming value number \p Idx.
getIncomingValue(unsigned Idx)1797e8d8bef9SDimitry Andric VPValue *getIncomingValue(unsigned Idx) const { return getOperand(Idx * 2); }
17985ffd83dbSDimitry Andric
17995ffd83dbSDimitry Andric /// Return mask number \p Idx.
getMask(unsigned Idx)1800e8d8bef9SDimitry Andric VPValue *getMask(unsigned Idx) const { return getOperand(Idx * 2 + 1); }
18015ffd83dbSDimitry Andric
18020b57cec5SDimitry Andric /// Generate the phi/select nodes.
18030b57cec5SDimitry Andric void execute(VPTransformState &State) override;
18040b57cec5SDimitry Andric
1805fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
18060b57cec5SDimitry Andric /// Print the recipe.
18075ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
18085ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
1809fe6060f1SDimitry Andric #endif
18101fd87a68SDimitry Andric
18111fd87a68SDimitry Andric /// Returns true if the recipe only uses the first lane of operand \p Op.
onlyFirstLaneUsed(const VPValue * Op)18121fd87a68SDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
18131fd87a68SDimitry Andric assert(is_contained(operands(), Op) &&
18141fd87a68SDimitry Andric "Op must be an operand of the recipe");
18151fd87a68SDimitry Andric // Recursing through Blend recipes only, must terminate at header phi's the
18161fd87a68SDimitry Andric // latest.
181781ad6265SDimitry Andric return all_of(users(),
181881ad6265SDimitry Andric [this](VPUser *U) { return U->onlyFirstLaneUsed(this); });
18191fd87a68SDimitry Andric }
18200b57cec5SDimitry Andric };
18210b57cec5SDimitry Andric
18220b57cec5SDimitry Andric /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
1823e8d8bef9SDimitry Andric /// or stores into one wide load/store and shuffles. The first operand of a
1824e8d8bef9SDimitry Andric /// VPInterleave recipe is the address, followed by the stored values, followed
1825e8d8bef9SDimitry Andric /// by an optional mask.
1826fe6060f1SDimitry Andric class VPInterleaveRecipe : public VPRecipeBase {
18270b57cec5SDimitry Andric const InterleaveGroup<Instruction> *IG;
1828e8d8bef9SDimitry Andric
182906c3fb27SDimitry Andric /// Indicates if the interleave group is in a conditional block and requires a
183006c3fb27SDimitry Andric /// mask.
1831e8d8bef9SDimitry Andric bool HasMask = false;
18320b57cec5SDimitry Andric
183306c3fb27SDimitry Andric /// Indicates if gaps between members of the group need to be masked out or if
183406c3fb27SDimitry Andric /// unusued gaps can be loaded speculatively.
183506c3fb27SDimitry Andric bool NeedsMaskForGaps = false;
183606c3fb27SDimitry Andric
18370b57cec5SDimitry Andric public:
VPInterleaveRecipe(const InterleaveGroup<Instruction> * IG,VPValue * Addr,ArrayRef<VPValue * > StoredValues,VPValue * Mask,bool NeedsMaskForGaps)1838480093f4SDimitry Andric VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr,
183906c3fb27SDimitry Andric ArrayRef<VPValue *> StoredValues, VPValue *Mask,
184006c3fb27SDimitry Andric bool NeedsMaskForGaps)
184106c3fb27SDimitry Andric : VPRecipeBase(VPDef::VPInterleaveSC, {Addr}), IG(IG),
184206c3fb27SDimitry Andric NeedsMaskForGaps(NeedsMaskForGaps) {
1843e8d8bef9SDimitry Andric for (unsigned i = 0; i < IG->getFactor(); ++i)
1844e8d8bef9SDimitry Andric if (Instruction *I = IG->getMember(i)) {
1845e8d8bef9SDimitry Andric if (I->getType()->isVoidTy())
1846e8d8bef9SDimitry Andric continue;
1847e8d8bef9SDimitry Andric new VPValue(I, this);
1848e8d8bef9SDimitry Andric }
1849e8d8bef9SDimitry Andric
1850e8d8bef9SDimitry Andric for (auto *SV : StoredValues)
1851e8d8bef9SDimitry Andric addOperand(SV);
1852e8d8bef9SDimitry Andric if (Mask) {
1853e8d8bef9SDimitry Andric HasMask = true;
1854e8d8bef9SDimitry Andric addOperand(Mask);
1855e8d8bef9SDimitry Andric }
18560b57cec5SDimitry Andric }
18570b57cec5SDimitry Andric ~VPInterleaveRecipe() override = default;
18580b57cec5SDimitry Andric
VP_CLASSOF_IMPL(VPDef::VPInterleaveSC)1859bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPInterleaveSC)
18600b57cec5SDimitry Andric
1861480093f4SDimitry Andric /// Return the address accessed by this recipe.
1862480093f4SDimitry Andric VPValue *getAddr() const {
1863e8d8bef9SDimitry Andric return getOperand(0); // Address is the 1st, mandatory operand.
1864480093f4SDimitry Andric }
1865480093f4SDimitry Andric
1866480093f4SDimitry Andric /// Return the mask used by this recipe. Note that a full mask is represented
1867480093f4SDimitry Andric /// by a nullptr.
getMask()1868480093f4SDimitry Andric VPValue *getMask() const {
1869480093f4SDimitry Andric // Mask is optional and therefore the last, currently 2nd operand.
1870e8d8bef9SDimitry Andric return HasMask ? getOperand(getNumOperands() - 1) : nullptr;
1871e8d8bef9SDimitry Andric }
1872e8d8bef9SDimitry Andric
1873e8d8bef9SDimitry Andric /// Return the VPValues stored by this interleave group. If it is a load
1874e8d8bef9SDimitry Andric /// interleave group, return an empty ArrayRef.
getStoredValues()1875e8d8bef9SDimitry Andric ArrayRef<VPValue *> getStoredValues() const {
1876e8d8bef9SDimitry Andric // The first operand is the address, followed by the stored values, followed
1877e8d8bef9SDimitry Andric // by an optional mask.
1878e8d8bef9SDimitry Andric return ArrayRef<VPValue *>(op_begin(), getNumOperands())
1879349cc55cSDimitry Andric .slice(1, getNumStoreOperands());
1880480093f4SDimitry Andric }
1881480093f4SDimitry Andric
18820b57cec5SDimitry Andric /// Generate the wide load or store, and shuffles.
18830b57cec5SDimitry Andric void execute(VPTransformState &State) override;
18840b57cec5SDimitry Andric
1885fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
18860b57cec5SDimitry Andric /// Print the recipe.
18875ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
18885ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
1889fe6060f1SDimitry Andric #endif
18900b57cec5SDimitry Andric
getInterleaveGroup()18910b57cec5SDimitry Andric const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; }
1892349cc55cSDimitry Andric
1893349cc55cSDimitry Andric /// Returns the number of stored operands of this interleave group. Returns 0
1894349cc55cSDimitry Andric /// for load interleave groups.
getNumStoreOperands()1895349cc55cSDimitry Andric unsigned getNumStoreOperands() const {
1896349cc55cSDimitry Andric return getNumOperands() - (HasMask ? 2 : 1);
1897349cc55cSDimitry Andric }
189881ad6265SDimitry Andric
189981ad6265SDimitry Andric /// The recipe only uses the first lane of the address.
onlyFirstLaneUsed(const VPValue * Op)190081ad6265SDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
190181ad6265SDimitry Andric assert(is_contained(operands(), Op) &&
190281ad6265SDimitry Andric "Op must be an operand of the recipe");
1903bdd1243dSDimitry Andric return Op == getAddr() && !llvm::is_contained(getStoredValues(), Op);
190481ad6265SDimitry Andric }
19050b57cec5SDimitry Andric };
19060b57cec5SDimitry Andric
1907e8d8bef9SDimitry Andric /// A recipe to represent inloop reduction operations, performing a reduction on
1908e8d8bef9SDimitry Andric /// a vector operand into a scalar value, and adding the result to a chain.
1909e8d8bef9SDimitry Andric /// The Operands are {ChainOp, VecOp, [Condition]}.
19107a6dacacSDimitry Andric class VPReductionRecipe : public VPSingleDefRecipe {
1911e8d8bef9SDimitry Andric /// The recurrence decriptor for the reduction in question.
19125f757f3fSDimitry Andric const RecurrenceDescriptor &RdxDesc;
1913e8d8bef9SDimitry Andric
1914e8d8bef9SDimitry Andric public:
VPReductionRecipe(const RecurrenceDescriptor & R,Instruction * I,VPValue * ChainOp,VPValue * VecOp,VPValue * CondOp)19155f757f3fSDimitry Andric VPReductionRecipe(const RecurrenceDescriptor &R, Instruction *I,
19165f757f3fSDimitry Andric VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp)
19177a6dacacSDimitry Andric : VPSingleDefRecipe(VPDef::VPReductionSC,
19187a6dacacSDimitry Andric ArrayRef<VPValue *>({ChainOp, VecOp}), I),
19195f757f3fSDimitry Andric RdxDesc(R) {
1920e8d8bef9SDimitry Andric if (CondOp)
1921e8d8bef9SDimitry Andric addOperand(CondOp);
1922e8d8bef9SDimitry Andric }
1923e8d8bef9SDimitry Andric
1924e8d8bef9SDimitry Andric ~VPReductionRecipe() override = default;
1925e8d8bef9SDimitry Andric
1926bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPReductionSC)
1927e8d8bef9SDimitry Andric
1928e8d8bef9SDimitry Andric /// Generate the reduction in the loop
1929e8d8bef9SDimitry Andric void execute(VPTransformState &State) override;
1930e8d8bef9SDimitry Andric
1931fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1932e8d8bef9SDimitry Andric /// Print the recipe.
1933e8d8bef9SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
1934e8d8bef9SDimitry Andric VPSlotTracker &SlotTracker) const override;
1935fe6060f1SDimitry Andric #endif
1936e8d8bef9SDimitry Andric
1937e8d8bef9SDimitry Andric /// The VPValue of the scalar Chain being accumulated.
getChainOp()1938e8d8bef9SDimitry Andric VPValue *getChainOp() const { return getOperand(0); }
1939e8d8bef9SDimitry Andric /// The VPValue of the vector value to be reduced.
getVecOp()1940e8d8bef9SDimitry Andric VPValue *getVecOp() const { return getOperand(1); }
1941e8d8bef9SDimitry Andric /// The VPValue of the condition for the block.
getCondOp()1942e8d8bef9SDimitry Andric VPValue *getCondOp() const {
1943e8d8bef9SDimitry Andric return getNumOperands() > 2 ? getOperand(2) : nullptr;
1944e8d8bef9SDimitry Andric }
1945e8d8bef9SDimitry Andric };
1946e8d8bef9SDimitry Andric
19470b57cec5SDimitry Andric /// VPReplicateRecipe replicates a given instruction producing multiple scalar
19480b57cec5SDimitry Andric /// copies of the original scalar type, one per lane, instead of producing a
19490b57cec5SDimitry Andric /// single copy of widened type for all lanes. If the instruction is known to be
19500b57cec5SDimitry Andric /// uniform only one copy, per lane zero, will be generated.
19517a6dacacSDimitry Andric class VPReplicateRecipe : public VPRecipeWithIRFlags {
19520b57cec5SDimitry Andric /// Indicator if only a single replica per lane is needed.
19530b57cec5SDimitry Andric bool IsUniform;
19540b57cec5SDimitry Andric
19550b57cec5SDimitry Andric /// Indicator if the replicas are also predicated.
19560b57cec5SDimitry Andric bool IsPredicated;
19570b57cec5SDimitry Andric
19580b57cec5SDimitry Andric public:
19595ffd83dbSDimitry Andric template <typename IterT>
19605ffd83dbSDimitry Andric VPReplicateRecipe(Instruction *I, iterator_range<IterT> Operands,
196106c3fb27SDimitry Andric bool IsUniform, VPValue *Mask = nullptr)
196206c3fb27SDimitry Andric : VPRecipeWithIRFlags(VPDef::VPReplicateSC, Operands, *I),
19637a6dacacSDimitry Andric IsUniform(IsUniform), IsPredicated(Mask) {
196406c3fb27SDimitry Andric if (Mask)
196506c3fb27SDimitry Andric addOperand(Mask);
19660b57cec5SDimitry Andric }
19670b57cec5SDimitry Andric
19680b57cec5SDimitry Andric ~VPReplicateRecipe() override = default;
19690b57cec5SDimitry Andric
1970bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPReplicateSC)
19710b57cec5SDimitry Andric
19720b57cec5SDimitry Andric /// Generate replicas of the desired Ingredient. Replicas will be generated
19730b57cec5SDimitry Andric /// for all parts and lanes unless a specific part and lane are specified in
19740b57cec5SDimitry Andric /// the \p State.
19750b57cec5SDimitry Andric void execute(VPTransformState &State) override;
19760b57cec5SDimitry Andric
1977fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
19780b57cec5SDimitry Andric /// Print the recipe.
19795ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
19805ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
1981fe6060f1SDimitry Andric #endif
1982e8d8bef9SDimitry Andric
isUniform()1983e8d8bef9SDimitry Andric bool isUniform() const { return IsUniform; }
1984fe6060f1SDimitry Andric
isPredicated()1985fe6060f1SDimitry Andric bool isPredicated() const { return IsPredicated; }
19861fd87a68SDimitry Andric
19871fd87a68SDimitry Andric /// Returns true if the recipe only uses the first lane of operand \p Op.
onlyFirstLaneUsed(const VPValue * Op)19881fd87a68SDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
19891fd87a68SDimitry Andric assert(is_contained(operands(), Op) &&
19901fd87a68SDimitry Andric "Op must be an operand of the recipe");
19911fd87a68SDimitry Andric return isUniform();
19921fd87a68SDimitry Andric }
199381ad6265SDimitry Andric
199481ad6265SDimitry Andric /// Returns true if the recipe uses scalars of operand \p Op.
usesScalars(const VPValue * Op)199581ad6265SDimitry Andric bool usesScalars(const VPValue *Op) const override {
199681ad6265SDimitry Andric assert(is_contained(operands(), Op) &&
199781ad6265SDimitry Andric "Op must be an operand of the recipe");
199881ad6265SDimitry Andric return true;
199981ad6265SDimitry Andric }
200006c3fb27SDimitry Andric
200106c3fb27SDimitry Andric /// Returns true if the recipe is used by a widened recipe via an intervening
200206c3fb27SDimitry Andric /// VPPredInstPHIRecipe. In this case, the scalar values should also be packed
200306c3fb27SDimitry Andric /// in a vector.
200406c3fb27SDimitry Andric bool shouldPack() const;
200506c3fb27SDimitry Andric
200606c3fb27SDimitry Andric /// Return the mask of a predicated VPReplicateRecipe.
getMask()200706c3fb27SDimitry Andric VPValue *getMask() {
200806c3fb27SDimitry Andric assert(isPredicated() && "Trying to get the mask of a unpredicated recipe");
200906c3fb27SDimitry Andric return getOperand(getNumOperands() - 1);
201006c3fb27SDimitry Andric }
20110b57cec5SDimitry Andric };
20120b57cec5SDimitry Andric
20130b57cec5SDimitry Andric /// A recipe for generating conditional branches on the bits of a mask.
2014fe6060f1SDimitry Andric class VPBranchOnMaskRecipe : public VPRecipeBase {
20150b57cec5SDimitry Andric public:
VPBranchOnMaskRecipe(VPValue * BlockInMask)2016fe6060f1SDimitry Andric VPBranchOnMaskRecipe(VPValue *BlockInMask)
2017bdd1243dSDimitry Andric : VPRecipeBase(VPDef::VPBranchOnMaskSC, {}) {
20180b57cec5SDimitry Andric if (BlockInMask) // nullptr means all-one mask.
2019e8d8bef9SDimitry Andric addOperand(BlockInMask);
20200b57cec5SDimitry Andric }
20210b57cec5SDimitry Andric
2022bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPBranchOnMaskSC)
20230b57cec5SDimitry Andric
20240b57cec5SDimitry Andric /// Generate the extraction of the appropriate bit from the block mask and the
20250b57cec5SDimitry Andric /// conditional branch.
20260b57cec5SDimitry Andric void execute(VPTransformState &State) override;
20270b57cec5SDimitry Andric
2028fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
20290b57cec5SDimitry Andric /// Print the recipe.
print(raw_ostream & O,const Twine & Indent,VPSlotTracker & SlotTracker)20305ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
20315ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override {
2032fe6060f1SDimitry Andric O << Indent << "BRANCH-ON-MASK ";
20335ffd83dbSDimitry Andric if (VPValue *Mask = getMask())
2034e8d8bef9SDimitry Andric Mask->printAsOperand(O, SlotTracker);
20350b57cec5SDimitry Andric else
20360b57cec5SDimitry Andric O << " All-One";
20370b57cec5SDimitry Andric }
2038fe6060f1SDimitry Andric #endif
20395ffd83dbSDimitry Andric
20405ffd83dbSDimitry Andric /// Return the mask used by this recipe. Note that a full mask is represented
20415ffd83dbSDimitry Andric /// by a nullptr.
getMask()20425ffd83dbSDimitry Andric VPValue *getMask() const {
2043e8d8bef9SDimitry Andric assert(getNumOperands() <= 1 && "should have either 0 or 1 operands");
20445ffd83dbSDimitry Andric // Mask is optional.
2045e8d8bef9SDimitry Andric return getNumOperands() == 1 ? getOperand(0) : nullptr;
20465ffd83dbSDimitry Andric }
204781ad6265SDimitry Andric
204881ad6265SDimitry Andric /// Returns true if the recipe uses scalars of operand \p Op.
usesScalars(const VPValue * Op)204981ad6265SDimitry Andric bool usesScalars(const VPValue *Op) const override {
205081ad6265SDimitry Andric assert(is_contained(operands(), Op) &&
205181ad6265SDimitry Andric "Op must be an operand of the recipe");
205281ad6265SDimitry Andric return true;
205381ad6265SDimitry Andric }
20540b57cec5SDimitry Andric };
20550b57cec5SDimitry Andric
20560b57cec5SDimitry Andric /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
20570b57cec5SDimitry Andric /// control converges back from a Branch-on-Mask. The phi nodes are needed in
20580b57cec5SDimitry Andric /// order to merge values that are set under such a branch and feed their uses.
20590b57cec5SDimitry Andric /// The phi nodes can be scalar or vector depending on the users of the value.
20600b57cec5SDimitry Andric /// This recipe works in concert with VPBranchOnMaskRecipe.
20617a6dacacSDimitry Andric class VPPredInstPHIRecipe : public VPSingleDefRecipe {
20620b57cec5SDimitry Andric public:
20630b57cec5SDimitry Andric /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
20640b57cec5SDimitry Andric /// nodes after merging back from a Branch-on-Mask.
VPPredInstPHIRecipe(VPValue * PredV)2065e8d8bef9SDimitry Andric VPPredInstPHIRecipe(VPValue *PredV)
20667a6dacacSDimitry Andric : VPSingleDefRecipe(VPDef::VPPredInstPHISC, PredV) {}
20670b57cec5SDimitry Andric ~VPPredInstPHIRecipe() override = default;
20680b57cec5SDimitry Andric
2069bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPPredInstPHISC)
20700b57cec5SDimitry Andric
20710b57cec5SDimitry Andric /// Generates phi nodes for live-outs as needed to retain SSA form.
20720b57cec5SDimitry Andric void execute(VPTransformState &State) override;
20730b57cec5SDimitry Andric
2074fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
20750b57cec5SDimitry Andric /// Print the recipe.
20765ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
20775ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
2078fe6060f1SDimitry Andric #endif
207981ad6265SDimitry Andric
208081ad6265SDimitry Andric /// Returns true if the recipe uses scalars of operand \p Op.
usesScalars(const VPValue * Op)208181ad6265SDimitry Andric bool usesScalars(const VPValue *Op) const override {
208281ad6265SDimitry Andric assert(is_contained(operands(), Op) &&
208381ad6265SDimitry Andric "Op must be an operand of the recipe");
208481ad6265SDimitry Andric return true;
208581ad6265SDimitry Andric }
20860b57cec5SDimitry Andric };
20870b57cec5SDimitry Andric
20880b57cec5SDimitry Andric /// A Recipe for widening load/store operations.
20895ffd83dbSDimitry Andric /// The recipe uses the following VPValues:
20905ffd83dbSDimitry Andric /// - For load: Address, optional mask
20915ffd83dbSDimitry Andric /// - For store: Address, stored value, optional mask
20920b57cec5SDimitry Andric /// TODO: We currently execute only per-part unless a specific instance is
20930b57cec5SDimitry Andric /// provided.
209481ad6265SDimitry Andric class VPWidenMemoryInstructionRecipe : public VPRecipeBase {
2095e8d8bef9SDimitry Andric Instruction &Ingredient;
20960b57cec5SDimitry Andric
2097349cc55cSDimitry Andric // Whether the loaded-from / stored-to addresses are consecutive.
2098349cc55cSDimitry Andric bool Consecutive;
2099349cc55cSDimitry Andric
2100349cc55cSDimitry Andric // Whether the consecutive loaded/stored addresses are in reverse order.
2101349cc55cSDimitry Andric bool Reverse;
2102349cc55cSDimitry Andric
setMask(VPValue * Mask)21035ffd83dbSDimitry Andric void setMask(VPValue *Mask) {
21045ffd83dbSDimitry Andric if (!Mask)
21055ffd83dbSDimitry Andric return;
2106e8d8bef9SDimitry Andric addOperand(Mask);
21070b57cec5SDimitry Andric }
21080b57cec5SDimitry Andric
isMasked()21095ffd83dbSDimitry Andric bool isMasked() const {
2110e8d8bef9SDimitry Andric return isStore() ? getNumOperands() == 3 : getNumOperands() == 2;
21115ffd83dbSDimitry Andric }
21125ffd83dbSDimitry Andric
21135ffd83dbSDimitry Andric public:
VPWidenMemoryInstructionRecipe(LoadInst & Load,VPValue * Addr,VPValue * Mask,bool Consecutive,bool Reverse)2114349cc55cSDimitry Andric VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask,
2115349cc55cSDimitry Andric bool Consecutive, bool Reverse)
2116bdd1243dSDimitry Andric : VPRecipeBase(VPDef::VPWidenMemoryInstructionSC, {Addr}),
2117bdd1243dSDimitry Andric Ingredient(Load), Consecutive(Consecutive), Reverse(Reverse) {
2118349cc55cSDimitry Andric assert((Consecutive || !Reverse) && "Reverse implies consecutive");
2119bdd1243dSDimitry Andric new VPValue(this, &Load);
21205ffd83dbSDimitry Andric setMask(Mask);
21215ffd83dbSDimitry Andric }
21225ffd83dbSDimitry Andric
VPWidenMemoryInstructionRecipe(StoreInst & Store,VPValue * Addr,VPValue * StoredValue,VPValue * Mask,bool Consecutive,bool Reverse)21235ffd83dbSDimitry Andric VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr,
2124349cc55cSDimitry Andric VPValue *StoredValue, VPValue *Mask,
2125349cc55cSDimitry Andric bool Consecutive, bool Reverse)
2126bdd1243dSDimitry Andric : VPRecipeBase(VPDef::VPWidenMemoryInstructionSC, {Addr, StoredValue}),
2127349cc55cSDimitry Andric Ingredient(Store), Consecutive(Consecutive), Reverse(Reverse) {
2128349cc55cSDimitry Andric assert((Consecutive || !Reverse) && "Reverse implies consecutive");
21295ffd83dbSDimitry Andric setMask(Mask);
21305ffd83dbSDimitry Andric }
21315ffd83dbSDimitry Andric
VP_CLASSOF_IMPL(VPDef::VPWidenMemoryInstructionSC)2132bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenMemoryInstructionSC)
21330b57cec5SDimitry Andric
2134480093f4SDimitry Andric /// Return the address accessed by this recipe.
2135480093f4SDimitry Andric VPValue *getAddr() const {
2136e8d8bef9SDimitry Andric return getOperand(0); // Address is the 1st, mandatory operand.
2137480093f4SDimitry Andric }
2138480093f4SDimitry Andric
2139480093f4SDimitry Andric /// Return the mask used by this recipe. Note that a full mask is represented
2140480093f4SDimitry Andric /// by a nullptr.
getMask()2141480093f4SDimitry Andric VPValue *getMask() const {
21425ffd83dbSDimitry Andric // Mask is optional and therefore the last operand.
2143e8d8bef9SDimitry Andric return isMasked() ? getOperand(getNumOperands() - 1) : nullptr;
21445ffd83dbSDimitry Andric }
21455ffd83dbSDimitry Andric
2146e8d8bef9SDimitry Andric /// Returns true if this recipe is a store.
isStore()2147e8d8bef9SDimitry Andric bool isStore() const { return isa<StoreInst>(Ingredient); }
2148e8d8bef9SDimitry Andric
21495ffd83dbSDimitry Andric /// Return the address accessed by this recipe.
getStoredValue()21505ffd83dbSDimitry Andric VPValue *getStoredValue() const {
2151e8d8bef9SDimitry Andric assert(isStore() && "Stored value only available for store instructions");
2152e8d8bef9SDimitry Andric return getOperand(1); // Stored value is the 2nd, mandatory operand.
2153480093f4SDimitry Andric }
2154480093f4SDimitry Andric
2155349cc55cSDimitry Andric // Return whether the loaded-from / stored-to addresses are consecutive.
isConsecutive()2156349cc55cSDimitry Andric bool isConsecutive() const { return Consecutive; }
2157349cc55cSDimitry Andric
2158349cc55cSDimitry Andric // Return whether the consecutive loaded/stored addresses are in reverse
2159349cc55cSDimitry Andric // order.
isReverse()2160349cc55cSDimitry Andric bool isReverse() const { return Reverse; }
2161349cc55cSDimitry Andric
21620b57cec5SDimitry Andric /// Generate the wide load/store.
21630b57cec5SDimitry Andric void execute(VPTransformState &State) override;
21640b57cec5SDimitry Andric
2165fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
21660b57cec5SDimitry Andric /// Print the recipe.
21675ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
21685ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
2169fe6060f1SDimitry Andric #endif
21701fd87a68SDimitry Andric
21711fd87a68SDimitry Andric /// Returns true if the recipe only uses the first lane of operand \p Op.
onlyFirstLaneUsed(const VPValue * Op)21721fd87a68SDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
21731fd87a68SDimitry Andric assert(is_contained(operands(), Op) &&
21741fd87a68SDimitry Andric "Op must be an operand of the recipe");
21751fd87a68SDimitry Andric
21761fd87a68SDimitry Andric // Widened, consecutive memory operations only demand the first lane of
217781ad6265SDimitry Andric // their address, unless the same operand is also stored. That latter can
217881ad6265SDimitry Andric // happen with opaque pointers.
217981ad6265SDimitry Andric return Op == getAddr() && isConsecutive() &&
218081ad6265SDimitry Andric (!isStore() || Op != getStoredValue());
21811fd87a68SDimitry Andric }
218281ad6265SDimitry Andric
getIngredient()218381ad6265SDimitry Andric Instruction &getIngredient() const { return Ingredient; }
218481ad6265SDimitry Andric };
218581ad6265SDimitry Andric
218681ad6265SDimitry Andric /// Recipe to expand a SCEV expression.
21877a6dacacSDimitry Andric class VPExpandSCEVRecipe : public VPSingleDefRecipe {
218881ad6265SDimitry Andric const SCEV *Expr;
218981ad6265SDimitry Andric ScalarEvolution &SE;
219081ad6265SDimitry Andric
219181ad6265SDimitry Andric public:
VPExpandSCEVRecipe(const SCEV * Expr,ScalarEvolution & SE)219281ad6265SDimitry Andric VPExpandSCEVRecipe(const SCEV *Expr, ScalarEvolution &SE)
21937a6dacacSDimitry Andric : VPSingleDefRecipe(VPDef::VPExpandSCEVSC, {}), Expr(Expr), SE(SE) {}
219481ad6265SDimitry Andric
219581ad6265SDimitry Andric ~VPExpandSCEVRecipe() override = default;
219681ad6265SDimitry Andric
2197bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPExpandSCEVSC)
219881ad6265SDimitry Andric
219981ad6265SDimitry Andric /// Generate a canonical vector induction variable of the vector loop, with
220081ad6265SDimitry Andric void execute(VPTransformState &State) override;
220181ad6265SDimitry Andric
220281ad6265SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
220381ad6265SDimitry Andric /// Print the recipe.
220481ad6265SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
220581ad6265SDimitry Andric VPSlotTracker &SlotTracker) const override;
220681ad6265SDimitry Andric #endif
220781ad6265SDimitry Andric
getSCEV()220881ad6265SDimitry Andric const SCEV *getSCEV() const { return Expr; }
22095ffd83dbSDimitry Andric };
22105ffd83dbSDimitry Andric
221104eeddc0SDimitry Andric /// Canonical scalar induction phi of the vector loop. Starting at the specified
221204eeddc0SDimitry Andric /// start value (either 0 or the resume value when vectorizing the epilogue
221304eeddc0SDimitry Andric /// loop). VPWidenCanonicalIVRecipe represents the vector version of the
221404eeddc0SDimitry Andric /// canonical induction variable.
221504eeddc0SDimitry Andric class VPCanonicalIVPHIRecipe : public VPHeaderPHIRecipe {
221604eeddc0SDimitry Andric public:
VPCanonicalIVPHIRecipe(VPValue * StartV,DebugLoc DL)221704eeddc0SDimitry Andric VPCanonicalIVPHIRecipe(VPValue *StartV, DebugLoc DL)
22185f757f3fSDimitry Andric : VPHeaderPHIRecipe(VPDef::VPCanonicalIVPHISC, nullptr, StartV, DL) {}
221904eeddc0SDimitry Andric
222004eeddc0SDimitry Andric ~VPCanonicalIVPHIRecipe() override = default;
222104eeddc0SDimitry Andric
VP_CLASSOF_IMPL(VPDef::VPCanonicalIVPHISC)2222bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPCanonicalIVPHISC)
2223bdd1243dSDimitry Andric
222481ad6265SDimitry Andric static inline bool classof(const VPHeaderPHIRecipe *D) {
2225bdd1243dSDimitry Andric return D->getVPDefID() == VPDef::VPCanonicalIVPHISC;
222681ad6265SDimitry Andric }
222704eeddc0SDimitry Andric
222804eeddc0SDimitry Andric /// Generate the canonical scalar induction phi of the vector loop.
222904eeddc0SDimitry Andric void execute(VPTransformState &State) override;
223004eeddc0SDimitry Andric
223104eeddc0SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
223204eeddc0SDimitry Andric /// Print the recipe.
223304eeddc0SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
223404eeddc0SDimitry Andric VPSlotTracker &SlotTracker) const override;
223504eeddc0SDimitry Andric #endif
223604eeddc0SDimitry Andric
223704eeddc0SDimitry Andric /// Returns the scalar type of the induction.
getScalarType()22385f757f3fSDimitry Andric Type *getScalarType() const {
22395f757f3fSDimitry Andric return getStartValue()->getLiveInIRValue()->getType();
224004eeddc0SDimitry Andric }
22411fd87a68SDimitry Andric
22421fd87a68SDimitry Andric /// Returns true if the recipe only uses the first lane of operand \p Op.
onlyFirstLaneUsed(const VPValue * Op)22431fd87a68SDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
22441fd87a68SDimitry Andric assert(is_contained(operands(), Op) &&
22451fd87a68SDimitry Andric "Op must be an operand of the recipe");
22461fd87a68SDimitry Andric return true;
22471fd87a68SDimitry Andric }
2248bdd1243dSDimitry Andric
22495f757f3fSDimitry Andric /// Returns true if the recipe only uses the first part of operand \p Op.
onlyFirstPartUsed(const VPValue * Op)22505f757f3fSDimitry Andric bool onlyFirstPartUsed(const VPValue *Op) const override {
22515f757f3fSDimitry Andric assert(is_contained(operands(), Op) &&
22525f757f3fSDimitry Andric "Op must be an operand of the recipe");
22535f757f3fSDimitry Andric return true;
22545f757f3fSDimitry Andric }
22555f757f3fSDimitry Andric
225606c3fb27SDimitry Andric /// Check if the induction described by \p Kind, /p Start and \p Step is
225706c3fb27SDimitry Andric /// canonical, i.e. has the same start, step (of 1), and type as the
225806c3fb27SDimitry Andric /// canonical IV.
225906c3fb27SDimitry Andric bool isCanonical(InductionDescriptor::InductionKind Kind, VPValue *Start,
226006c3fb27SDimitry Andric VPValue *Step, Type *Ty) const;
226104eeddc0SDimitry Andric };
226204eeddc0SDimitry Andric
2263753f127fSDimitry Andric /// A recipe for generating the active lane mask for the vector loop that is
2264753f127fSDimitry Andric /// used to predicate the vector operations.
2265753f127fSDimitry Andric /// TODO: It would be good to use the existing VPWidenPHIRecipe instead and
2266753f127fSDimitry Andric /// remove VPActiveLaneMaskPHIRecipe.
2267753f127fSDimitry Andric class VPActiveLaneMaskPHIRecipe : public VPHeaderPHIRecipe {
2268753f127fSDimitry Andric public:
VPActiveLaneMaskPHIRecipe(VPValue * StartMask,DebugLoc DL)2269753f127fSDimitry Andric VPActiveLaneMaskPHIRecipe(VPValue *StartMask, DebugLoc DL)
22705f757f3fSDimitry Andric : VPHeaderPHIRecipe(VPDef::VPActiveLaneMaskPHISC, nullptr, StartMask,
22715f757f3fSDimitry Andric DL) {}
2272753f127fSDimitry Andric
2273753f127fSDimitry Andric ~VPActiveLaneMaskPHIRecipe() override = default;
2274753f127fSDimitry Andric
VP_CLASSOF_IMPL(VPDef::VPActiveLaneMaskPHISC)2275bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPActiveLaneMaskPHISC)
2276bdd1243dSDimitry Andric
2277753f127fSDimitry Andric static inline bool classof(const VPHeaderPHIRecipe *D) {
2278bdd1243dSDimitry Andric return D->getVPDefID() == VPDef::VPActiveLaneMaskPHISC;
2279753f127fSDimitry Andric }
2280753f127fSDimitry Andric
2281753f127fSDimitry Andric /// Generate the active lane mask phi of the vector loop.
2282753f127fSDimitry Andric void execute(VPTransformState &State) override;
2283753f127fSDimitry Andric
2284753f127fSDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2285753f127fSDimitry Andric /// Print the recipe.
2286753f127fSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
2287753f127fSDimitry Andric VPSlotTracker &SlotTracker) const override;
2288753f127fSDimitry Andric #endif
2289753f127fSDimitry Andric };
2290753f127fSDimitry Andric
22915ffd83dbSDimitry Andric /// A Recipe for widening the canonical induction variable of the vector loop.
22927a6dacacSDimitry Andric class VPWidenCanonicalIVRecipe : public VPSingleDefRecipe {
22935ffd83dbSDimitry Andric public:
VPWidenCanonicalIVRecipe(VPCanonicalIVPHIRecipe * CanonicalIV)229404eeddc0SDimitry Andric VPWidenCanonicalIVRecipe(VPCanonicalIVPHIRecipe *CanonicalIV)
22957a6dacacSDimitry Andric : VPSingleDefRecipe(VPDef::VPWidenCanonicalIVSC, {CanonicalIV}) {}
2296e8d8bef9SDimitry Andric
22975ffd83dbSDimitry Andric ~VPWidenCanonicalIVRecipe() override = default;
22985ffd83dbSDimitry Andric
2299bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPWidenCanonicalIVSC)
230004eeddc0SDimitry Andric
23015ffd83dbSDimitry Andric /// Generate a canonical vector induction variable of the vector loop, with
23025ffd83dbSDimitry Andric /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and
23035ffd83dbSDimitry Andric /// step = <VF*UF, VF*UF, ..., VF*UF>.
23045ffd83dbSDimitry Andric void execute(VPTransformState &State) override;
23055ffd83dbSDimitry Andric
2306fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
23075ffd83dbSDimitry Andric /// Print the recipe.
23085ffd83dbSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
23095ffd83dbSDimitry Andric VPSlotTracker &SlotTracker) const override;
2310fe6060f1SDimitry Andric #endif
231104eeddc0SDimitry Andric
231204eeddc0SDimitry Andric /// Returns the scalar type of the induction.
getScalarType()231304eeddc0SDimitry Andric const Type *getScalarType() const {
2314bdd1243dSDimitry Andric return cast<VPCanonicalIVPHIRecipe>(getOperand(0)->getDefiningRecipe())
231504eeddc0SDimitry Andric ->getScalarType();
231604eeddc0SDimitry Andric }
23170b57cec5SDimitry Andric };
23180b57cec5SDimitry Andric
2319bdd1243dSDimitry Andric /// A recipe for converting the canonical IV value to the corresponding value of
2320bdd1243dSDimitry Andric /// an IV with different start and step values, using Start + CanonicalIV *
2321bdd1243dSDimitry Andric /// Step.
23227a6dacacSDimitry Andric class VPDerivedIVRecipe : public VPSingleDefRecipe {
23235f757f3fSDimitry Andric /// If not nullptr, the result of the induction will get truncated to
23245f757f3fSDimitry Andric /// TruncResultTy.
23255f757f3fSDimitry Andric Type *TruncResultTy;
2326bdd1243dSDimitry Andric
23275f757f3fSDimitry Andric /// Kind of the induction.
23285f757f3fSDimitry Andric const InductionDescriptor::InductionKind Kind;
23295f757f3fSDimitry Andric /// If not nullptr, the floating point induction binary operator. Must be set
23305f757f3fSDimitry Andric /// for floating point inductions.
23315f757f3fSDimitry Andric const FPMathOperator *FPBinOp;
2332bdd1243dSDimitry Andric
2333bdd1243dSDimitry Andric public:
VPDerivedIVRecipe(const InductionDescriptor & IndDesc,VPValue * Start,VPCanonicalIVPHIRecipe * CanonicalIV,VPValue * Step,Type * TruncResultTy)2334bdd1243dSDimitry Andric VPDerivedIVRecipe(const InductionDescriptor &IndDesc, VPValue *Start,
2335bdd1243dSDimitry Andric VPCanonicalIVPHIRecipe *CanonicalIV, VPValue *Step,
23365f757f3fSDimitry Andric Type *TruncResultTy)
23377a6dacacSDimitry Andric : VPSingleDefRecipe(VPDef::VPDerivedIVSC, {Start, CanonicalIV, Step}),
23387a6dacacSDimitry Andric TruncResultTy(TruncResultTy), Kind(IndDesc.getKind()),
23395f757f3fSDimitry Andric FPBinOp(dyn_cast_or_null<FPMathOperator>(IndDesc.getInductionBinOp())) {
23405f757f3fSDimitry Andric }
2341bdd1243dSDimitry Andric
2342bdd1243dSDimitry Andric ~VPDerivedIVRecipe() override = default;
2343bdd1243dSDimitry Andric
2344bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPDerivedIVSC)
2345bdd1243dSDimitry Andric
2346bdd1243dSDimitry Andric /// Generate the transformed value of the induction at offset StartValue (1.
2347bdd1243dSDimitry Andric /// operand) + IV (2. operand) * StepValue (3, operand).
2348bdd1243dSDimitry Andric void execute(VPTransformState &State) override;
2349bdd1243dSDimitry Andric
2350bdd1243dSDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2351bdd1243dSDimitry Andric /// Print the recipe.
2352bdd1243dSDimitry Andric void print(raw_ostream &O, const Twine &Indent,
2353bdd1243dSDimitry Andric VPSlotTracker &SlotTracker) const override;
2354bdd1243dSDimitry Andric #endif
2355bdd1243dSDimitry Andric
getScalarType()23565f757f3fSDimitry Andric Type *getScalarType() const {
23575f757f3fSDimitry Andric return TruncResultTy ? TruncResultTy
23585f757f3fSDimitry Andric : getStartValue()->getLiveInIRValue()->getType();
23595f757f3fSDimitry Andric }
23605f757f3fSDimitry Andric
getStartValue()2361bdd1243dSDimitry Andric VPValue *getStartValue() const { return getOperand(0); }
getCanonicalIV()2362bdd1243dSDimitry Andric VPValue *getCanonicalIV() const { return getOperand(1); }
getStepValue()2363bdd1243dSDimitry Andric VPValue *getStepValue() const { return getOperand(2); }
2364bdd1243dSDimitry Andric
2365bdd1243dSDimitry Andric /// Returns true if the recipe only uses the first lane of operand \p Op.
onlyFirstLaneUsed(const VPValue * Op)2366bdd1243dSDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
2367bdd1243dSDimitry Andric assert(is_contained(operands(), Op) &&
2368bdd1243dSDimitry Andric "Op must be an operand of the recipe");
2369bdd1243dSDimitry Andric return true;
2370bdd1243dSDimitry Andric }
2371bdd1243dSDimitry Andric };
2372bdd1243dSDimitry Andric
237381ad6265SDimitry Andric /// A recipe for handling phi nodes of integer and floating-point inductions,
237481ad6265SDimitry Andric /// producing their scalar values.
23757a6dacacSDimitry Andric class VPScalarIVStepsRecipe : public VPRecipeWithIRFlags {
23765f757f3fSDimitry Andric Instruction::BinaryOps InductionOpcode;
237781ad6265SDimitry Andric
237881ad6265SDimitry Andric public:
VPScalarIVStepsRecipe(VPValue * IV,VPValue * Step,Instruction::BinaryOps Opcode,FastMathFlags FMFs)23795f757f3fSDimitry Andric VPScalarIVStepsRecipe(VPValue *IV, VPValue *Step,
23805f757f3fSDimitry Andric Instruction::BinaryOps Opcode, FastMathFlags FMFs)
23815f757f3fSDimitry Andric : VPRecipeWithIRFlags(VPDef::VPScalarIVStepsSC,
23825f757f3fSDimitry Andric ArrayRef<VPValue *>({IV, Step}), FMFs),
23837a6dacacSDimitry Andric InductionOpcode(Opcode) {}
23845f757f3fSDimitry Andric
VPScalarIVStepsRecipe(const InductionDescriptor & IndDesc,VPValue * IV,VPValue * Step)2385bdd1243dSDimitry Andric VPScalarIVStepsRecipe(const InductionDescriptor &IndDesc, VPValue *IV,
2386bdd1243dSDimitry Andric VPValue *Step)
23875f757f3fSDimitry Andric : VPScalarIVStepsRecipe(
23885f757f3fSDimitry Andric IV, Step, IndDesc.getInductionOpcode(),
23895f757f3fSDimitry Andric dyn_cast_or_null<FPMathOperator>(IndDesc.getInductionBinOp())
23905f757f3fSDimitry Andric ? IndDesc.getInductionBinOp()->getFastMathFlags()
23915f757f3fSDimitry Andric : FastMathFlags()) {}
239281ad6265SDimitry Andric
239381ad6265SDimitry Andric ~VPScalarIVStepsRecipe() override = default;
239481ad6265SDimitry Andric
2395bdd1243dSDimitry Andric VP_CLASSOF_IMPL(VPDef::VPScalarIVStepsSC)
239681ad6265SDimitry Andric
239781ad6265SDimitry Andric /// Generate the scalarized versions of the phi node as needed by their users.
239881ad6265SDimitry Andric void execute(VPTransformState &State) override;
239981ad6265SDimitry Andric
240081ad6265SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
240181ad6265SDimitry Andric /// Print the recipe.
240281ad6265SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
240381ad6265SDimitry Andric VPSlotTracker &SlotTracker) const override;
240481ad6265SDimitry Andric #endif
240581ad6265SDimitry Andric
getStepValue()2406bdd1243dSDimitry Andric VPValue *getStepValue() const { return getOperand(1); }
240781ad6265SDimitry Andric
240881ad6265SDimitry Andric /// Returns true if the recipe only uses the first lane of operand \p Op.
onlyFirstLaneUsed(const VPValue * Op)240981ad6265SDimitry Andric bool onlyFirstLaneUsed(const VPValue *Op) const override {
241081ad6265SDimitry Andric assert(is_contained(operands(), Op) &&
241181ad6265SDimitry Andric "Op must be an operand of the recipe");
241281ad6265SDimitry Andric return true;
241381ad6265SDimitry Andric }
241481ad6265SDimitry Andric };
241581ad6265SDimitry Andric
24160b57cec5SDimitry Andric /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
24170b57cec5SDimitry Andric /// holds a sequence of zero or more VPRecipe's each representing a sequence of
2418fe6060f1SDimitry Andric /// output IR instructions. All PHI-like recipes must come before any non-PHI recipes.
24190b57cec5SDimitry Andric class VPBasicBlock : public VPBlockBase {
24200b57cec5SDimitry Andric public:
24210b57cec5SDimitry Andric using RecipeListTy = iplist<VPRecipeBase>;
24220b57cec5SDimitry Andric
24230b57cec5SDimitry Andric private:
24240b57cec5SDimitry Andric /// The VPRecipes held in the order of output instructions to generate.
24250b57cec5SDimitry Andric RecipeListTy Recipes;
24260b57cec5SDimitry Andric
24270b57cec5SDimitry Andric public:
24280b57cec5SDimitry Andric VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
24290b57cec5SDimitry Andric : VPBlockBase(VPBasicBlockSC, Name.str()) {
24300b57cec5SDimitry Andric if (Recipe)
24310b57cec5SDimitry Andric appendRecipe(Recipe);
24320b57cec5SDimitry Andric }
24330b57cec5SDimitry Andric
~VPBasicBlock()2434fe6060f1SDimitry Andric ~VPBasicBlock() override {
2435fe6060f1SDimitry Andric while (!Recipes.empty())
2436fe6060f1SDimitry Andric Recipes.pop_back();
2437fe6060f1SDimitry Andric }
24380b57cec5SDimitry Andric
24390b57cec5SDimitry Andric /// Instruction iterators...
24400b57cec5SDimitry Andric using iterator = RecipeListTy::iterator;
24410b57cec5SDimitry Andric using const_iterator = RecipeListTy::const_iterator;
24420b57cec5SDimitry Andric using reverse_iterator = RecipeListTy::reverse_iterator;
24430b57cec5SDimitry Andric using const_reverse_iterator = RecipeListTy::const_reverse_iterator;
24440b57cec5SDimitry Andric
24450b57cec5SDimitry Andric //===--------------------------------------------------------------------===//
24460b57cec5SDimitry Andric /// Recipe iterator methods
24470b57cec5SDimitry Andric ///
begin()24480b57cec5SDimitry Andric inline iterator begin() { return Recipes.begin(); }
begin()24490b57cec5SDimitry Andric inline const_iterator begin() const { return Recipes.begin(); }
end()24500b57cec5SDimitry Andric inline iterator end() { return Recipes.end(); }
end()24510b57cec5SDimitry Andric inline const_iterator end() const { return Recipes.end(); }
24520b57cec5SDimitry Andric
rbegin()24530b57cec5SDimitry Andric inline reverse_iterator rbegin() { return Recipes.rbegin(); }
rbegin()24540b57cec5SDimitry Andric inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
rend()24550b57cec5SDimitry Andric inline reverse_iterator rend() { return Recipes.rend(); }
rend()24560b57cec5SDimitry Andric inline const_reverse_iterator rend() const { return Recipes.rend(); }
24570b57cec5SDimitry Andric
size()24580b57cec5SDimitry Andric inline size_t size() const { return Recipes.size(); }
empty()24590b57cec5SDimitry Andric inline bool empty() const { return Recipes.empty(); }
front()24600b57cec5SDimitry Andric inline const VPRecipeBase &front() const { return Recipes.front(); }
front()24610b57cec5SDimitry Andric inline VPRecipeBase &front() { return Recipes.front(); }
back()24620b57cec5SDimitry Andric inline const VPRecipeBase &back() const { return Recipes.back(); }
back()24630b57cec5SDimitry Andric inline VPRecipeBase &back() { return Recipes.back(); }
24640b57cec5SDimitry Andric
24650b57cec5SDimitry Andric /// Returns a reference to the list of recipes.
getRecipeList()24660b57cec5SDimitry Andric RecipeListTy &getRecipeList() { return Recipes; }
24670b57cec5SDimitry Andric
24680b57cec5SDimitry Andric /// Returns a pointer to a member of the recipe list.
getSublistAccess(VPRecipeBase *)24690b57cec5SDimitry Andric static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) {
24700b57cec5SDimitry Andric return &VPBasicBlock::Recipes;
24710b57cec5SDimitry Andric }
24720b57cec5SDimitry Andric
24730b57cec5SDimitry Andric /// Method to support type inquiry through isa, cast, and dyn_cast.
classof(const VPBlockBase * V)24740b57cec5SDimitry Andric static inline bool classof(const VPBlockBase *V) {
24750b57cec5SDimitry Andric return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
24760b57cec5SDimitry Andric }
24770b57cec5SDimitry Andric
insert(VPRecipeBase * Recipe,iterator InsertPt)24780b57cec5SDimitry Andric void insert(VPRecipeBase *Recipe, iterator InsertPt) {
24790b57cec5SDimitry Andric assert(Recipe && "No recipe to append.");
24800b57cec5SDimitry Andric assert(!Recipe->Parent && "Recipe already in VPlan");
24810b57cec5SDimitry Andric Recipe->Parent = this;
24820b57cec5SDimitry Andric Recipes.insert(InsertPt, Recipe);
24830b57cec5SDimitry Andric }
24840b57cec5SDimitry Andric
24850b57cec5SDimitry Andric /// Augment the existing recipes of a VPBasicBlock with an additional
24860b57cec5SDimitry Andric /// \p Recipe as the last recipe.
appendRecipe(VPRecipeBase * Recipe)24870b57cec5SDimitry Andric void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
24880b57cec5SDimitry Andric
24890b57cec5SDimitry Andric /// The method which generates the output IR instructions that correspond to
24900b57cec5SDimitry Andric /// this VPBasicBlock, thereby "executing" the VPlan.
2491bdd1243dSDimitry Andric void execute(VPTransformState *State) override;
24920b57cec5SDimitry Andric
2493e8d8bef9SDimitry Andric /// Return the position of the first non-phi node recipe in the block.
2494e8d8bef9SDimitry Andric iterator getFirstNonPhi();
2495e8d8bef9SDimitry Andric
2496fe6060f1SDimitry Andric /// Returns an iterator range over the PHI-like recipes in the block.
phis()2497fe6060f1SDimitry Andric iterator_range<iterator> phis() {
2498fe6060f1SDimitry Andric return make_range(begin(), getFirstNonPhi());
2499fe6060f1SDimitry Andric }
2500fe6060f1SDimitry Andric
2501e8d8bef9SDimitry Andric void dropAllReferences(VPValue *NewValue) override;
2502e8d8bef9SDimitry Andric
2503fe6060f1SDimitry Andric /// Split current block at \p SplitAt by inserting a new block between the
2504fe6060f1SDimitry Andric /// current block and its successors and moving all recipes starting at
2505fe6060f1SDimitry Andric /// SplitAt to the new block. Returns the new block.
2506fe6060f1SDimitry Andric VPBasicBlock *splitAt(iterator SplitAt);
2507fe6060f1SDimitry Andric
250881ad6265SDimitry Andric VPRegionBlock *getEnclosingLoopRegion();
250981ad6265SDimitry Andric
2510fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2511fe6060f1SDimitry Andric /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p
2512fe6060f1SDimitry Andric /// SlotTracker is used to print unnamed VPValue's using consequtive numbers.
2513fe6060f1SDimitry Andric ///
2514fe6060f1SDimitry Andric /// Note that the numbering is applied to the whole VPlan, so printing
2515fe6060f1SDimitry Andric /// individual blocks is consistent with the whole VPlan printing.
2516fe6060f1SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
2517fe6060f1SDimitry Andric VPSlotTracker &SlotTracker) const override;
2518fe6060f1SDimitry Andric using VPBlockBase::print; // Get the print(raw_stream &O) version.
2519fe6060f1SDimitry Andric #endif
2520fe6060f1SDimitry Andric
252181ad6265SDimitry Andric /// If the block has multiple successors, return the branch recipe terminating
252281ad6265SDimitry Andric /// the block. If there are no or only a single successor, return nullptr;
252381ad6265SDimitry Andric VPRecipeBase *getTerminator();
252481ad6265SDimitry Andric const VPRecipeBase *getTerminator() const;
252581ad6265SDimitry Andric
252681ad6265SDimitry Andric /// Returns true if the block is exiting it's parent region.
252781ad6265SDimitry Andric bool isExiting() const;
252881ad6265SDimitry Andric
25290b57cec5SDimitry Andric private:
25300b57cec5SDimitry Andric /// Create an IR BasicBlock to hold the output instructions generated by this
25310b57cec5SDimitry Andric /// VPBasicBlock, and return it. Update the CFGState accordingly.
25320b57cec5SDimitry Andric BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
25330b57cec5SDimitry Andric };
25340b57cec5SDimitry Andric
25350b57cec5SDimitry Andric /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
253681ad6265SDimitry Andric /// which form a Single-Entry-Single-Exiting subgraph of the output IR CFG.
25370b57cec5SDimitry Andric /// A VPRegionBlock may indicate that its contents are to be replicated several
25380b57cec5SDimitry Andric /// times. This is designed to support predicated scalarization, in which a
25390b57cec5SDimitry Andric /// scalar if-then code structure needs to be generated VF * UF times. Having
25400b57cec5SDimitry Andric /// this replication indicator helps to keep a single model for multiple
25410b57cec5SDimitry Andric /// candidate VF's. The actual replication takes place only once the desired VF
25420b57cec5SDimitry Andric /// and UF have been determined.
25430b57cec5SDimitry Andric class VPRegionBlock : public VPBlockBase {
25440b57cec5SDimitry Andric /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
25450b57cec5SDimitry Andric VPBlockBase *Entry;
25460b57cec5SDimitry Andric
254781ad6265SDimitry Andric /// Hold the Single Exiting block of the SESE region modelled by the
254881ad6265SDimitry Andric /// VPRegionBlock.
254981ad6265SDimitry Andric VPBlockBase *Exiting;
25500b57cec5SDimitry Andric
25510b57cec5SDimitry Andric /// An indicator whether this region is to generate multiple replicated
25520b57cec5SDimitry Andric /// instances of output IR corresponding to its VPBlockBases.
25530b57cec5SDimitry Andric bool IsReplicator;
25540b57cec5SDimitry Andric
25550b57cec5SDimitry Andric public:
255681ad6265SDimitry Andric VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exiting,
25570b57cec5SDimitry Andric const std::string &Name = "", bool IsReplicator = false)
VPBlockBase(VPRegionBlockSC,Name)255881ad6265SDimitry Andric : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exiting(Exiting),
25590b57cec5SDimitry Andric IsReplicator(IsReplicator) {
25600b57cec5SDimitry Andric assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
256181ad6265SDimitry Andric assert(Exiting->getSuccessors().empty() && "Exit block has successors.");
25620b57cec5SDimitry Andric Entry->setParent(this);
256381ad6265SDimitry Andric Exiting->setParent(this);
25640b57cec5SDimitry Andric }
25650b57cec5SDimitry Andric VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
VPBlockBase(VPRegionBlockSC,Name)256681ad6265SDimitry Andric : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exiting(nullptr),
25670b57cec5SDimitry Andric IsReplicator(IsReplicator) {}
25680b57cec5SDimitry Andric
~VPRegionBlock()25690b57cec5SDimitry Andric ~VPRegionBlock() override {
2570e8d8bef9SDimitry Andric if (Entry) {
2571e8d8bef9SDimitry Andric VPValue DummyValue;
2572e8d8bef9SDimitry Andric Entry->dropAllReferences(&DummyValue);
25730b57cec5SDimitry Andric deleteCFG(Entry);
25740b57cec5SDimitry Andric }
2575e8d8bef9SDimitry Andric }
25760b57cec5SDimitry Andric
25770b57cec5SDimitry Andric /// Method to support type inquiry through isa, cast, and dyn_cast.
classof(const VPBlockBase * V)25780b57cec5SDimitry Andric static inline bool classof(const VPBlockBase *V) {
25790b57cec5SDimitry Andric return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
25800b57cec5SDimitry Andric }
25810b57cec5SDimitry Andric
getEntry()25820b57cec5SDimitry Andric const VPBlockBase *getEntry() const { return Entry; }
getEntry()25830b57cec5SDimitry Andric VPBlockBase *getEntry() { return Entry; }
25840b57cec5SDimitry Andric
25850b57cec5SDimitry Andric /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
25860b57cec5SDimitry Andric /// EntryBlock must have no predecessors.
setEntry(VPBlockBase * EntryBlock)25870b57cec5SDimitry Andric void setEntry(VPBlockBase *EntryBlock) {
25880b57cec5SDimitry Andric assert(EntryBlock->getPredecessors().empty() &&
25890b57cec5SDimitry Andric "Entry block cannot have predecessors.");
25900b57cec5SDimitry Andric Entry = EntryBlock;
25910b57cec5SDimitry Andric EntryBlock->setParent(this);
25920b57cec5SDimitry Andric }
25930b57cec5SDimitry Andric
getExiting()259481ad6265SDimitry Andric const VPBlockBase *getExiting() const { return Exiting; }
getExiting()259581ad6265SDimitry Andric VPBlockBase *getExiting() { return Exiting; }
25960b57cec5SDimitry Andric
259781ad6265SDimitry Andric /// Set \p ExitingBlock as the exiting VPBlockBase of this VPRegionBlock. \p
259881ad6265SDimitry Andric /// ExitingBlock must have no successors.
setExiting(VPBlockBase * ExitingBlock)259981ad6265SDimitry Andric void setExiting(VPBlockBase *ExitingBlock) {
260081ad6265SDimitry Andric assert(ExitingBlock->getSuccessors().empty() &&
26010b57cec5SDimitry Andric "Exit block cannot have successors.");
260281ad6265SDimitry Andric Exiting = ExitingBlock;
260381ad6265SDimitry Andric ExitingBlock->setParent(this);
260481ad6265SDimitry Andric }
260581ad6265SDimitry Andric
260681ad6265SDimitry Andric /// Returns the pre-header VPBasicBlock of the loop region.
getPreheaderVPBB()260781ad6265SDimitry Andric VPBasicBlock *getPreheaderVPBB() {
260881ad6265SDimitry Andric assert(!isReplicator() && "should only get pre-header of loop regions");
260981ad6265SDimitry Andric return getSinglePredecessor()->getExitingBasicBlock();
26100b57cec5SDimitry Andric }
26110b57cec5SDimitry Andric
26120b57cec5SDimitry Andric /// An indicator whether this region is to generate multiple replicated
26130b57cec5SDimitry Andric /// instances of output IR corresponding to its VPBlockBases.
isReplicator()26140b57cec5SDimitry Andric bool isReplicator() const { return IsReplicator; }
26150b57cec5SDimitry Andric
26160b57cec5SDimitry Andric /// The method which generates the output IR instructions that correspond to
26170b57cec5SDimitry Andric /// this VPRegionBlock, thereby "executing" the VPlan.
2618bdd1243dSDimitry Andric void execute(VPTransformState *State) override;
2619e8d8bef9SDimitry Andric
2620e8d8bef9SDimitry Andric void dropAllReferences(VPValue *NewValue) override;
2621fe6060f1SDimitry Andric
2622fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2623fe6060f1SDimitry Andric /// Print this VPRegionBlock to \p O (recursively), prefixing all lines with
2624fe6060f1SDimitry Andric /// \p Indent. \p SlotTracker is used to print unnamed VPValue's using
2625fe6060f1SDimitry Andric /// consequtive numbers.
2626fe6060f1SDimitry Andric ///
2627fe6060f1SDimitry Andric /// Note that the numbering is applied to the whole VPlan, so printing
2628fe6060f1SDimitry Andric /// individual regions is consistent with the whole VPlan printing.
2629fe6060f1SDimitry Andric void print(raw_ostream &O, const Twine &Indent,
2630fe6060f1SDimitry Andric VPSlotTracker &SlotTracker) const override;
2631fe6060f1SDimitry Andric using VPBlockBase::print; // Get the print(raw_stream &O) version.
2632fe6060f1SDimitry Andric #endif
26330b57cec5SDimitry Andric };
26340b57cec5SDimitry Andric
2635480093f4SDimitry Andric /// VPlan models a candidate for vectorization, encoding various decisions take
2636480093f4SDimitry Andric /// to produce efficient output IR, including which branches, basic-blocks and
2637480093f4SDimitry Andric /// output IR instructions to generate, and their cost. VPlan holds a
2638480093f4SDimitry Andric /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
263906c3fb27SDimitry Andric /// VPBasicBlock.
2640480093f4SDimitry Andric class VPlan {
2641480093f4SDimitry Andric friend class VPlanPrinter;
26425ffd83dbSDimitry Andric friend class VPSlotTracker;
2643480093f4SDimitry Andric
264406c3fb27SDimitry Andric /// Hold the single entry to the Hierarchical CFG of the VPlan, i.e. the
264506c3fb27SDimitry Andric /// preheader of the vector loop.
264606c3fb27SDimitry Andric VPBasicBlock *Entry;
264706c3fb27SDimitry Andric
264806c3fb27SDimitry Andric /// VPBasicBlock corresponding to the original preheader. Used to place
264906c3fb27SDimitry Andric /// VPExpandSCEV recipes for expressions used during skeleton creation and the
265006c3fb27SDimitry Andric /// rest of VPlan execution.
265106c3fb27SDimitry Andric VPBasicBlock *Preheader;
2652480093f4SDimitry Andric
2653480093f4SDimitry Andric /// Holds the VFs applicable to this VPlan.
2654e8d8bef9SDimitry Andric SmallSetVector<ElementCount, 2> VFs;
2655480093f4SDimitry Andric
2656bdd1243dSDimitry Andric /// Holds the UFs applicable to this VPlan. If empty, the VPlan is valid for
2657bdd1243dSDimitry Andric /// any UF.
2658bdd1243dSDimitry Andric SmallSetVector<unsigned, 2> UFs;
2659bdd1243dSDimitry Andric
2660480093f4SDimitry Andric /// Holds the name of the VPlan, for printing.
2661480093f4SDimitry Andric std::string Name;
2662480093f4SDimitry Andric
266304eeddc0SDimitry Andric /// Represents the trip count of the original loop, for folding
2664480093f4SDimitry Andric /// the tail.
266504eeddc0SDimitry Andric VPValue *TripCount = nullptr;
266604eeddc0SDimitry Andric
266704eeddc0SDimitry Andric /// Represents the backedge taken count of the original loop, for folding
266804eeddc0SDimitry Andric /// the tail. It equals TripCount - 1.
2669480093f4SDimitry Andric VPValue *BackedgeTakenCount = nullptr;
2670480093f4SDimitry Andric
267104eeddc0SDimitry Andric /// Represents the vector trip count.
267204eeddc0SDimitry Andric VPValue VectorTripCount;
267304eeddc0SDimitry Andric
26745f757f3fSDimitry Andric /// Represents the loop-invariant VF * UF of the vector loop region.
26755f757f3fSDimitry Andric VPValue VFxUF;
26765f757f3fSDimitry Andric
2677480093f4SDimitry Andric /// Holds a mapping between Values and their corresponding VPValue inside
2678480093f4SDimitry Andric /// VPlan.
2679480093f4SDimitry Andric Value2VPValueTy Value2VPValue;
2680480093f4SDimitry Andric
268106c3fb27SDimitry Andric /// Contains all the external definitions created for this VPlan. External
268206c3fb27SDimitry Andric /// definitions are VPValues that hold a pointer to their underlying IR.
268306c3fb27SDimitry Andric SmallVector<VPValue *, 16> VPLiveInsToFree;
2684e8d8bef9SDimitry Andric
2685349cc55cSDimitry Andric /// Indicates whether it is safe use the Value2VPValue mapping or if the
2686349cc55cSDimitry Andric /// mapping cannot be used any longer, because it is stale.
2687349cc55cSDimitry Andric bool Value2VPValueEnabled = true;
2688349cc55cSDimitry Andric
268981ad6265SDimitry Andric /// Values used outside the plan.
269081ad6265SDimitry Andric MapVector<PHINode *, VPLiveOut *> LiveOuts;
269181ad6265SDimitry Andric
269206c3fb27SDimitry Andric /// Mapping from SCEVs to the VPValues representing their expansions.
269306c3fb27SDimitry Andric /// NOTE: This mapping is temporary and will be removed once all users have
269406c3fb27SDimitry Andric /// been modeled in VPlan directly.
269506c3fb27SDimitry Andric DenseMap<const SCEV *, VPValue *> SCEVToExpansion;
269606c3fb27SDimitry Andric
2697480093f4SDimitry Andric public:
269806c3fb27SDimitry Andric /// Construct a VPlan with original preheader \p Preheader, trip count \p TC
269906c3fb27SDimitry Andric /// and \p Entry to the plan. At the moment, \p Preheader and \p Entry need to
270006c3fb27SDimitry Andric /// be disconnected, as the bypass blocks between them are not yet modeled in
270106c3fb27SDimitry Andric /// VPlan.
VPlan(VPBasicBlock * Preheader,VPValue * TC,VPBasicBlock * Entry)270206c3fb27SDimitry Andric VPlan(VPBasicBlock *Preheader, VPValue *TC, VPBasicBlock *Entry)
270306c3fb27SDimitry Andric : VPlan(Preheader, Entry) {
270406c3fb27SDimitry Andric TripCount = TC;
270506c3fb27SDimitry Andric }
270606c3fb27SDimitry Andric
270706c3fb27SDimitry Andric /// Construct a VPlan with original preheader \p Preheader and \p Entry to
270806c3fb27SDimitry Andric /// the plan. At the moment, \p Preheader and \p Entry need to be
270906c3fb27SDimitry Andric /// disconnected, as the bypass blocks between them are not yet modeled in
271006c3fb27SDimitry Andric /// VPlan.
VPlan(VPBasicBlock * Preheader,VPBasicBlock * Entry)271106c3fb27SDimitry Andric VPlan(VPBasicBlock *Preheader, VPBasicBlock *Entry)
271206c3fb27SDimitry Andric : Entry(Entry), Preheader(Preheader) {
27135ffd83dbSDimitry Andric Entry->setPlan(this);
271406c3fb27SDimitry Andric Preheader->setPlan(this);
271506c3fb27SDimitry Andric assert(Preheader->getNumSuccessors() == 0 &&
271606c3fb27SDimitry Andric Preheader->getNumPredecessors() == 0 &&
271706c3fb27SDimitry Andric "preheader must be disconnected");
27185ffd83dbSDimitry Andric }
2719480093f4SDimitry Andric
2720bdd1243dSDimitry Andric ~VPlan();
2721480093f4SDimitry Andric
27225f757f3fSDimitry Andric /// Create initial VPlan skeleton, having an "entry" VPBasicBlock (wrapping
27235f757f3fSDimitry Andric /// original scalar pre-header) which contains SCEV expansions that need to
27245f757f3fSDimitry Andric /// happen before the CFG is modified; a VPBasicBlock for the vector
27255f757f3fSDimitry Andric /// pre-header, followed by a region for the vector loop, followed by the
27265f757f3fSDimitry Andric /// middle VPBasicBlock.
272706c3fb27SDimitry Andric static VPlanPtr createInitialVPlan(const SCEV *TripCount,
272806c3fb27SDimitry Andric ScalarEvolution &PSE);
272906c3fb27SDimitry Andric
273004eeddc0SDimitry Andric /// Prepare the plan for execution, setting up the required live-in values.
273104eeddc0SDimitry Andric void prepareToExecute(Value *TripCount, Value *VectorTripCount,
27325f757f3fSDimitry Andric Value *CanonicalIVStartValue, VPTransformState &State);
273304eeddc0SDimitry Andric
2734480093f4SDimitry Andric /// Generate the IR code for this VPlan.
2735bdd1243dSDimitry Andric void execute(VPTransformState *State);
2736480093f4SDimitry Andric
getEntry()273706c3fb27SDimitry Andric VPBasicBlock *getEntry() { return Entry; }
getEntry()273806c3fb27SDimitry Andric const VPBasicBlock *getEntry() const { return Entry; }
2739480093f4SDimitry Andric
274004eeddc0SDimitry Andric /// The trip count of the original loop.
getTripCount()274106c3fb27SDimitry Andric VPValue *getTripCount() const {
274206c3fb27SDimitry Andric assert(TripCount && "trip count needs to be set before accessing it");
274304eeddc0SDimitry Andric return TripCount;
274404eeddc0SDimitry Andric }
274504eeddc0SDimitry Andric
2746480093f4SDimitry Andric /// The backedge taken count of the original loop.
getOrCreateBackedgeTakenCount()2747480093f4SDimitry Andric VPValue *getOrCreateBackedgeTakenCount() {
2748480093f4SDimitry Andric if (!BackedgeTakenCount)
2749480093f4SDimitry Andric BackedgeTakenCount = new VPValue();
2750480093f4SDimitry Andric return BackedgeTakenCount;
2751480093f4SDimitry Andric }
2752480093f4SDimitry Andric
275304eeddc0SDimitry Andric /// The vector trip count.
getVectorTripCount()275404eeddc0SDimitry Andric VPValue &getVectorTripCount() { return VectorTripCount; }
275504eeddc0SDimitry Andric
27565f757f3fSDimitry Andric /// Returns VF * UF of the vector loop region.
getVFxUF()27575f757f3fSDimitry Andric VPValue &getVFxUF() { return VFxUF; }
27585f757f3fSDimitry Andric
2759349cc55cSDimitry Andric /// Mark the plan to indicate that using Value2VPValue is not safe any
2760349cc55cSDimitry Andric /// longer, because it may be stale.
disableValue2VPValue()2761349cc55cSDimitry Andric void disableValue2VPValue() { Value2VPValueEnabled = false; }
2762349cc55cSDimitry Andric
addVF(ElementCount VF)2763e8d8bef9SDimitry Andric void addVF(ElementCount VF) { VFs.insert(VF); }
2764480093f4SDimitry Andric
setVF(ElementCount VF)2765bdd1243dSDimitry Andric void setVF(ElementCount VF) {
2766bdd1243dSDimitry Andric assert(hasVF(VF) && "Cannot set VF not already in plan");
2767bdd1243dSDimitry Andric VFs.clear();
2768bdd1243dSDimitry Andric VFs.insert(VF);
2769bdd1243dSDimitry Andric }
2770bdd1243dSDimitry Andric
hasVF(ElementCount VF)2771e8d8bef9SDimitry Andric bool hasVF(ElementCount VF) { return VFs.count(VF); }
2772480093f4SDimitry Andric
hasScalarVFOnly()2773bdd1243dSDimitry Andric bool hasScalarVFOnly() const { return VFs.size() == 1 && VFs[0].isScalar(); }
2774bdd1243dSDimitry Andric
hasUF(unsigned UF)2775bdd1243dSDimitry Andric bool hasUF(unsigned UF) const { return UFs.empty() || UFs.contains(UF); }
2776bdd1243dSDimitry Andric
setUF(unsigned UF)2777bdd1243dSDimitry Andric void setUF(unsigned UF) {
2778bdd1243dSDimitry Andric assert(hasUF(UF) && "Cannot set the UF not already in plan");
2779bdd1243dSDimitry Andric UFs.clear();
2780bdd1243dSDimitry Andric UFs.insert(UF);
2781bdd1243dSDimitry Andric }
2782bdd1243dSDimitry Andric
2783bdd1243dSDimitry Andric /// Return a string with the name of the plan and the applicable VFs and UFs.
2784bdd1243dSDimitry Andric std::string getName() const;
2785480093f4SDimitry Andric
setName(const Twine & newName)2786480093f4SDimitry Andric void setName(const Twine &newName) { Name = newName.str(); }
2787480093f4SDimitry Andric
addVPValue(Value * V,VPValue * VPV)2788e8d8bef9SDimitry Andric void addVPValue(Value *V, VPValue *VPV) {
278906c3fb27SDimitry Andric assert((Value2VPValueEnabled || VPV->isLiveIn()) &&
279006c3fb27SDimitry Andric "Value2VPValue mapping may be out of date!");
2791e8d8bef9SDimitry Andric assert(V && "Trying to add a null Value to VPlan");
2792e8d8bef9SDimitry Andric assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
2793e8d8bef9SDimitry Andric Value2VPValue[V] = VPV;
2794480093f4SDimitry Andric }
2795480093f4SDimitry Andric
2796349cc55cSDimitry Andric /// Returns the VPValue for \p V. \p OverrideAllowed can be used to disable
279706c3fb27SDimitry Andric /// /// checking whether it is safe to query VPValues using IR Values.
2798349cc55cSDimitry Andric VPValue *getVPValue(Value *V, bool OverrideAllowed = false) {
2799480093f4SDimitry Andric assert(V && "Trying to get the VPValue of a null Value");
2800480093f4SDimitry Andric assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
280106c3fb27SDimitry Andric assert((Value2VPValueEnabled || OverrideAllowed ||
280206c3fb27SDimitry Andric Value2VPValue[V]->isLiveIn()) &&
280306c3fb27SDimitry Andric "Value2VPValue mapping may be out of date!");
2804480093f4SDimitry Andric return Value2VPValue[V];
2805480093f4SDimitry Andric }
2806480093f4SDimitry Andric
280706c3fb27SDimitry Andric /// Gets the VPValue for \p V or adds a new live-in (if none exists yet) for
280806c3fb27SDimitry Andric /// \p V.
getVPValueOrAddLiveIn(Value * V)280906c3fb27SDimitry Andric VPValue *getVPValueOrAddLiveIn(Value *V) {
2810480093f4SDimitry Andric assert(V && "Trying to get or add the VPValue of a null Value");
281106c3fb27SDimitry Andric if (!Value2VPValue.count(V)) {
281206c3fb27SDimitry Andric VPValue *VPV = new VPValue(V);
281306c3fb27SDimitry Andric VPLiveInsToFree.push_back(VPV);
281406c3fb27SDimitry Andric addVPValue(V, VPV);
281506c3fb27SDimitry Andric }
281606c3fb27SDimitry Andric
2817480093f4SDimitry Andric return getVPValue(V);
2818480093f4SDimitry Andric }
2819480093f4SDimitry Andric
2820fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
28215f757f3fSDimitry Andric /// Print the live-ins of this VPlan to \p O.
28225f757f3fSDimitry Andric void printLiveIns(raw_ostream &O) const;
28235f757f3fSDimitry Andric
2824fe6060f1SDimitry Andric /// Print this VPlan to \p O.
2825fe6060f1SDimitry Andric void print(raw_ostream &O) const;
2826fe6060f1SDimitry Andric
2827fe6060f1SDimitry Andric /// Print this VPlan in DOT format to \p O.
2828fe6060f1SDimitry Andric void printDOT(raw_ostream &O) const;
2829fe6060f1SDimitry Andric
2830480093f4SDimitry Andric /// Dump the plan to stderr (for debugging).
2831fe6060f1SDimitry Andric LLVM_DUMP_METHOD void dump() const;
2832fe6060f1SDimitry Andric #endif
2833480093f4SDimitry Andric
28345ffd83dbSDimitry Andric /// Returns a range mapping the values the range \p Operands to their
28355ffd83dbSDimitry Andric /// corresponding VPValues.
28365ffd83dbSDimitry Andric iterator_range<mapped_iterator<Use *, std::function<VPValue *(Value *)>>>
mapToVPValues(User::op_range Operands)28375ffd83dbSDimitry Andric mapToVPValues(User::op_range Operands) {
28385ffd83dbSDimitry Andric std::function<VPValue *(Value *)> Fn = [this](Value *Op) {
283906c3fb27SDimitry Andric return getVPValueOrAddLiveIn(Op);
28405ffd83dbSDimitry Andric };
28415ffd83dbSDimitry Andric return map_range(Operands, Fn);
28425ffd83dbSDimitry Andric }
28435ffd83dbSDimitry Andric
284404eeddc0SDimitry Andric /// Returns the VPRegionBlock of the vector loop.
getVectorLoopRegion()284504eeddc0SDimitry Andric VPRegionBlock *getVectorLoopRegion() {
284681ad6265SDimitry Andric return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
284781ad6265SDimitry Andric }
getVectorLoopRegion()284881ad6265SDimitry Andric const VPRegionBlock *getVectorLoopRegion() const {
284981ad6265SDimitry Andric return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
285004eeddc0SDimitry Andric }
285104eeddc0SDimitry Andric
285204eeddc0SDimitry Andric /// Returns the canonical induction recipe of the vector loop.
getCanonicalIV()285304eeddc0SDimitry Andric VPCanonicalIVPHIRecipe *getCanonicalIV() {
285404eeddc0SDimitry Andric VPBasicBlock *EntryVPBB = getVectorLoopRegion()->getEntryBasicBlock();
285504eeddc0SDimitry Andric if (EntryVPBB->empty()) {
285604eeddc0SDimitry Andric // VPlan native path.
285704eeddc0SDimitry Andric EntryVPBB = cast<VPBasicBlock>(EntryVPBB->getSingleSuccessor());
285804eeddc0SDimitry Andric }
285904eeddc0SDimitry Andric return cast<VPCanonicalIVPHIRecipe>(&*EntryVPBB->begin());
286004eeddc0SDimitry Andric }
286104eeddc0SDimitry Andric
286281ad6265SDimitry Andric void addLiveOut(PHINode *PN, VPValue *V);
286381ad6265SDimitry Andric
removeLiveOut(PHINode * PN)286481ad6265SDimitry Andric void removeLiveOut(PHINode *PN) {
286581ad6265SDimitry Andric delete LiveOuts[PN];
286681ad6265SDimitry Andric LiveOuts.erase(PN);
286781ad6265SDimitry Andric }
286881ad6265SDimitry Andric
getLiveOuts()286981ad6265SDimitry Andric const MapVector<PHINode *, VPLiveOut *> &getLiveOuts() const {
287081ad6265SDimitry Andric return LiveOuts;
287181ad6265SDimitry Andric }
287281ad6265SDimitry Andric
getSCEVExpansion(const SCEV * S)287306c3fb27SDimitry Andric VPValue *getSCEVExpansion(const SCEV *S) const {
287406c3fb27SDimitry Andric return SCEVToExpansion.lookup(S);
287506c3fb27SDimitry Andric }
287606c3fb27SDimitry Andric
addSCEVExpansion(const SCEV * S,VPValue * V)287706c3fb27SDimitry Andric void addSCEVExpansion(const SCEV *S, VPValue *V) {
287806c3fb27SDimitry Andric assert(!SCEVToExpansion.contains(S) && "SCEV already expanded");
287906c3fb27SDimitry Andric SCEVToExpansion[S] = V;
288006c3fb27SDimitry Andric }
288106c3fb27SDimitry Andric
288206c3fb27SDimitry Andric /// \return The block corresponding to the original preheader.
getPreheader()288306c3fb27SDimitry Andric VPBasicBlock *getPreheader() { return Preheader; }
getPreheader()288406c3fb27SDimitry Andric const VPBasicBlock *getPreheader() const { return Preheader; }
288506c3fb27SDimitry Andric
2886480093f4SDimitry Andric private:
2887480093f4SDimitry Andric /// Add to the given dominator tree the header block and every new basic block
2888480093f4SDimitry Andric /// that was created between it and the latch block, inclusive.
2889480093f4SDimitry Andric static void updateDominatorTree(DominatorTree *DT, BasicBlock *LoopLatchBB,
2890480093f4SDimitry Andric BasicBlock *LoopPreHeaderBB,
2891480093f4SDimitry Andric BasicBlock *LoopExitBB);
2892480093f4SDimitry Andric };
2893480093f4SDimitry Andric
2894fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2895480093f4SDimitry Andric /// VPlanPrinter prints a given VPlan to a given output stream. The printing is
2896480093f4SDimitry Andric /// indented and follows the dot format.
2897480093f4SDimitry Andric class VPlanPrinter {
2898480093f4SDimitry Andric raw_ostream &OS;
2899480093f4SDimitry Andric const VPlan &Plan;
2900480093f4SDimitry Andric unsigned Depth = 0;
2901480093f4SDimitry Andric unsigned TabWidth = 2;
2902480093f4SDimitry Andric std::string Indent;
2903480093f4SDimitry Andric unsigned BID = 0;
2904480093f4SDimitry Andric SmallDenseMap<const VPBlockBase *, unsigned> BlockID;
2905480093f4SDimitry Andric
29065ffd83dbSDimitry Andric VPSlotTracker SlotTracker;
29075ffd83dbSDimitry Andric
2908480093f4SDimitry Andric /// Handle indentation.
bumpIndent(int b)2909480093f4SDimitry Andric void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
2910480093f4SDimitry Andric
2911480093f4SDimitry Andric /// Print a given \p Block of the Plan.
2912480093f4SDimitry Andric void dumpBlock(const VPBlockBase *Block);
2913480093f4SDimitry Andric
2914480093f4SDimitry Andric /// Print the information related to the CFG edges going out of a given
2915480093f4SDimitry Andric /// \p Block, followed by printing the successor blocks themselves.
2916480093f4SDimitry Andric void dumpEdges(const VPBlockBase *Block);
2917480093f4SDimitry Andric
2918480093f4SDimitry Andric /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
2919480093f4SDimitry Andric /// its successor blocks.
2920480093f4SDimitry Andric void dumpBasicBlock(const VPBasicBlock *BasicBlock);
2921480093f4SDimitry Andric
2922480093f4SDimitry Andric /// Print a given \p Region of the Plan.
2923480093f4SDimitry Andric void dumpRegion(const VPRegionBlock *Region);
2924480093f4SDimitry Andric
getOrCreateBID(const VPBlockBase * Block)2925480093f4SDimitry Andric unsigned getOrCreateBID(const VPBlockBase *Block) {
2926480093f4SDimitry Andric return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
2927480093f4SDimitry Andric }
2928480093f4SDimitry Andric
2929349cc55cSDimitry Andric Twine getOrCreateName(const VPBlockBase *Block);
2930480093f4SDimitry Andric
2931349cc55cSDimitry Andric Twine getUID(const VPBlockBase *Block);
2932480093f4SDimitry Andric
2933480093f4SDimitry Andric /// Print the information related to a CFG edge between two VPBlockBases.
2934480093f4SDimitry Andric void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
2935480093f4SDimitry Andric const Twine &Label);
2936480093f4SDimitry Andric
2937fe6060f1SDimitry Andric public:
VPlanPrinter(raw_ostream & O,const VPlan & P)2938fe6060f1SDimitry Andric VPlanPrinter(raw_ostream &O, const VPlan &P)
2939fe6060f1SDimitry Andric : OS(O), Plan(P), SlotTracker(&P) {}
2940480093f4SDimitry Andric
2941fe6060f1SDimitry Andric LLVM_DUMP_METHOD void dump();
2942480093f4SDimitry Andric };
2943480093f4SDimitry Andric
2944480093f4SDimitry Andric struct VPlanIngredient {
2945e8d8bef9SDimitry Andric const Value *V;
2946480093f4SDimitry Andric
VPlanIngredientVPlanIngredient2947e8d8bef9SDimitry Andric VPlanIngredient(const Value *V) : V(V) {}
2948fe6060f1SDimitry Andric
2949fe6060f1SDimitry Andric void print(raw_ostream &O) const;
2950480093f4SDimitry Andric };
2951480093f4SDimitry Andric
2952480093f4SDimitry Andric inline raw_ostream &operator<<(raw_ostream &OS, const VPlanIngredient &I) {
2953fe6060f1SDimitry Andric I.print(OS);
2954480093f4SDimitry Andric return OS;
2955480093f4SDimitry Andric }
2956480093f4SDimitry Andric
2957480093f4SDimitry Andric inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) {
2958fe6060f1SDimitry Andric Plan.print(OS);
2959480093f4SDimitry Andric return OS;
2960480093f4SDimitry Andric }
2961fe6060f1SDimitry Andric #endif
2962480093f4SDimitry Andric
29630b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
29640b57cec5SDimitry Andric // VPlan Utilities
29650b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
29660b57cec5SDimitry Andric
29670b57cec5SDimitry Andric /// Class that provides utilities for VPBlockBases in VPlan.
29680b57cec5SDimitry Andric class VPBlockUtils {
29690b57cec5SDimitry Andric public:
29700b57cec5SDimitry Andric VPBlockUtils() = delete;
29710b57cec5SDimitry Andric
29720b57cec5SDimitry Andric /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
29730b57cec5SDimitry Andric /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
29740eae32dcSDimitry Andric /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
297581ad6265SDimitry Andric /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
297681ad6265SDimitry Andric /// have neither successors nor predecessors.
insertBlockAfter(VPBlockBase * NewBlock,VPBlockBase * BlockPtr)29770b57cec5SDimitry Andric static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
29780b57cec5SDimitry Andric assert(NewBlock->getSuccessors().empty() &&
29790eae32dcSDimitry Andric NewBlock->getPredecessors().empty() &&
29800eae32dcSDimitry Andric "Can't insert new block with predecessors or successors.");
29810b57cec5SDimitry Andric NewBlock->setParent(BlockPtr->getParent());
29820eae32dcSDimitry Andric SmallVector<VPBlockBase *> Succs(BlockPtr->successors());
29830eae32dcSDimitry Andric for (VPBlockBase *Succ : Succs) {
29840eae32dcSDimitry Andric disconnectBlocks(BlockPtr, Succ);
29850eae32dcSDimitry Andric connectBlocks(NewBlock, Succ);
29860eae32dcSDimitry Andric }
29870eae32dcSDimitry Andric connectBlocks(BlockPtr, NewBlock);
29880b57cec5SDimitry Andric }
29890b57cec5SDimitry Andric
29900b57cec5SDimitry Andric /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
29910b57cec5SDimitry Andric /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
29920b57cec5SDimitry Andric /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
299381ad6265SDimitry Andric /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
299481ad6265SDimitry Andric /// and \p IfTrue and \p IfFalse must have neither successors nor
299581ad6265SDimitry Andric /// predecessors.
insertTwoBlocksAfter(VPBlockBase * IfTrue,VPBlockBase * IfFalse,VPBlockBase * BlockPtr)29960b57cec5SDimitry Andric static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
299781ad6265SDimitry Andric VPBlockBase *BlockPtr) {
29980b57cec5SDimitry Andric assert(IfTrue->getSuccessors().empty() &&
29990b57cec5SDimitry Andric "Can't insert IfTrue with successors.");
30000b57cec5SDimitry Andric assert(IfFalse->getSuccessors().empty() &&
30010b57cec5SDimitry Andric "Can't insert IfFalse with successors.");
300281ad6265SDimitry Andric BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
30030b57cec5SDimitry Andric IfTrue->setPredecessors({BlockPtr});
30040b57cec5SDimitry Andric IfFalse->setPredecessors({BlockPtr});
30050b57cec5SDimitry Andric IfTrue->setParent(BlockPtr->getParent());
30060b57cec5SDimitry Andric IfFalse->setParent(BlockPtr->getParent());
30070b57cec5SDimitry Andric }
30080b57cec5SDimitry Andric
30090b57cec5SDimitry Andric /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
30100b57cec5SDimitry Andric /// the successors of \p From and \p From to the predecessors of \p To. Both
30110b57cec5SDimitry Andric /// VPBlockBases must have the same parent, which can be null. Both
30120b57cec5SDimitry Andric /// VPBlockBases can be already connected to other VPBlockBases.
connectBlocks(VPBlockBase * From,VPBlockBase * To)30130b57cec5SDimitry Andric static void connectBlocks(VPBlockBase *From, VPBlockBase *To) {
30140b57cec5SDimitry Andric assert((From->getParent() == To->getParent()) &&
30150b57cec5SDimitry Andric "Can't connect two block with different parents");
30160b57cec5SDimitry Andric assert(From->getNumSuccessors() < 2 &&
30170b57cec5SDimitry Andric "Blocks can't have more than two successors.");
30180b57cec5SDimitry Andric From->appendSuccessor(To);
30190b57cec5SDimitry Andric To->appendPredecessor(From);
30200b57cec5SDimitry Andric }
30210b57cec5SDimitry Andric
30220b57cec5SDimitry Andric /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
30230b57cec5SDimitry Andric /// from the successors of \p From and \p From from the predecessors of \p To.
disconnectBlocks(VPBlockBase * From,VPBlockBase * To)30240b57cec5SDimitry Andric static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
30250b57cec5SDimitry Andric assert(To && "Successor to disconnect is null.");
30260b57cec5SDimitry Andric From->removeSuccessor(To);
30270b57cec5SDimitry Andric To->removePredecessor(From);
30280b57cec5SDimitry Andric }
30290b57cec5SDimitry Andric
3030fe6060f1SDimitry Andric /// Return an iterator range over \p Range which only includes \p BlockTy
3031fe6060f1SDimitry Andric /// blocks. The accesses are casted to \p BlockTy.
3032fe6060f1SDimitry Andric template <typename BlockTy, typename T>
blocksOnly(const T & Range)3033fe6060f1SDimitry Andric static auto blocksOnly(const T &Range) {
3034fe6060f1SDimitry Andric // Create BaseTy with correct const-ness based on BlockTy.
3035bdd1243dSDimitry Andric using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
3036bdd1243dSDimitry Andric const VPBlockBase, VPBlockBase>;
3037fe6060f1SDimitry Andric
3038fe6060f1SDimitry Andric // We need to first create an iterator range over (const) BlocktTy & instead
3039fe6060f1SDimitry Andric // of (const) BlockTy * for filter_range to work properly.
3040fe6060f1SDimitry Andric auto Mapped =
3041fe6060f1SDimitry Andric map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
3042fe6060f1SDimitry Andric auto Filter = make_filter_range(
3043fe6060f1SDimitry Andric Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
3044fe6060f1SDimitry Andric return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
3045fe6060f1SDimitry Andric return cast<BlockTy>(&Block);
3046fe6060f1SDimitry Andric });
3047fe6060f1SDimitry Andric }
30480b57cec5SDimitry Andric };
30490b57cec5SDimitry Andric
30500b57cec5SDimitry Andric class VPInterleavedAccessInfo {
30510b57cec5SDimitry Andric DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *>
30520b57cec5SDimitry Andric InterleaveGroupMap;
30530b57cec5SDimitry Andric
30540b57cec5SDimitry Andric /// Type for mapping of instruction based interleave groups to VPInstruction
30550b57cec5SDimitry Andric /// interleave groups
30560b57cec5SDimitry Andric using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *,
30570b57cec5SDimitry Andric InterleaveGroup<VPInstruction> *>;
30580b57cec5SDimitry Andric
30590b57cec5SDimitry Andric /// Recursively \p Region and populate VPlan based interleave groups based on
30600b57cec5SDimitry Andric /// \p IAI.
30610b57cec5SDimitry Andric void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,
30620b57cec5SDimitry Andric InterleavedAccessInfo &IAI);
30630b57cec5SDimitry Andric /// Recursively traverse \p Block and populate VPlan based interleave groups
30640b57cec5SDimitry Andric /// based on \p IAI.
30650b57cec5SDimitry Andric void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
30660b57cec5SDimitry Andric InterleavedAccessInfo &IAI);
30670b57cec5SDimitry Andric
30680b57cec5SDimitry Andric public:
30690b57cec5SDimitry Andric VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI);
30700b57cec5SDimitry Andric
~VPInterleavedAccessInfo()30710b57cec5SDimitry Andric ~VPInterleavedAccessInfo() {
30720b57cec5SDimitry Andric SmallPtrSet<InterleaveGroup<VPInstruction> *, 4> DelSet;
30730b57cec5SDimitry Andric // Avoid releasing a pointer twice.
30740b57cec5SDimitry Andric for (auto &I : InterleaveGroupMap)
30750b57cec5SDimitry Andric DelSet.insert(I.second);
30760b57cec5SDimitry Andric for (auto *Ptr : DelSet)
30770b57cec5SDimitry Andric delete Ptr;
30780b57cec5SDimitry Andric }
30790b57cec5SDimitry Andric
30800b57cec5SDimitry Andric /// Get the interleave group that \p Instr belongs to.
30810b57cec5SDimitry Andric ///
30820b57cec5SDimitry Andric /// \returns nullptr if doesn't have such group.
30830b57cec5SDimitry Andric InterleaveGroup<VPInstruction> *
getInterleaveGroup(VPInstruction * Instr)30840b57cec5SDimitry Andric getInterleaveGroup(VPInstruction *Instr) const {
3085e8d8bef9SDimitry Andric return InterleaveGroupMap.lookup(Instr);
30860b57cec5SDimitry Andric }
30870b57cec5SDimitry Andric };
30880b57cec5SDimitry Andric
30890b57cec5SDimitry Andric /// Class that maps (parts of) an existing VPlan to trees of combined
30900b57cec5SDimitry Andric /// VPInstructions.
30910b57cec5SDimitry Andric class VPlanSlp {
30920b57cec5SDimitry Andric enum class OpMode { Failed, Load, Opcode };
30930b57cec5SDimitry Andric
30940b57cec5SDimitry Andric /// A DenseMapInfo implementation for using SmallVector<VPValue *, 4> as
30950b57cec5SDimitry Andric /// DenseMap keys.
30960b57cec5SDimitry Andric struct BundleDenseMapInfo {
getEmptyKeyBundleDenseMapInfo30970b57cec5SDimitry Andric static SmallVector<VPValue *, 4> getEmptyKey() {
30980b57cec5SDimitry Andric return {reinterpret_cast<VPValue *>(-1)};
30990b57cec5SDimitry Andric }
31000b57cec5SDimitry Andric
getTombstoneKeyBundleDenseMapInfo31010b57cec5SDimitry Andric static SmallVector<VPValue *, 4> getTombstoneKey() {
31020b57cec5SDimitry Andric return {reinterpret_cast<VPValue *>(-2)};
31030b57cec5SDimitry Andric }
31040b57cec5SDimitry Andric
getHashValueBundleDenseMapInfo31050b57cec5SDimitry Andric static unsigned getHashValue(const SmallVector<VPValue *, 4> &V) {
31060b57cec5SDimitry Andric return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
31070b57cec5SDimitry Andric }
31080b57cec5SDimitry Andric
isEqualBundleDenseMapInfo31090b57cec5SDimitry Andric static bool isEqual(const SmallVector<VPValue *, 4> &LHS,
31100b57cec5SDimitry Andric const SmallVector<VPValue *, 4> &RHS) {
31110b57cec5SDimitry Andric return LHS == RHS;
31120b57cec5SDimitry Andric }
31130b57cec5SDimitry Andric };
31140b57cec5SDimitry Andric
31150b57cec5SDimitry Andric /// Mapping of values in the original VPlan to a combined VPInstruction.
31160b57cec5SDimitry Andric DenseMap<SmallVector<VPValue *, 4>, VPInstruction *, BundleDenseMapInfo>
31170b57cec5SDimitry Andric BundleToCombined;
31180b57cec5SDimitry Andric
31190b57cec5SDimitry Andric VPInterleavedAccessInfo &IAI;
31200b57cec5SDimitry Andric
31210b57cec5SDimitry Andric /// Basic block to operate on. For now, only instructions in a single BB are
31220b57cec5SDimitry Andric /// considered.
31230b57cec5SDimitry Andric const VPBasicBlock &BB;
31240b57cec5SDimitry Andric
31250b57cec5SDimitry Andric /// Indicates whether we managed to combine all visited instructions or not.
31260b57cec5SDimitry Andric bool CompletelySLP = true;
31270b57cec5SDimitry Andric
31280b57cec5SDimitry Andric /// Width of the widest combined bundle in bits.
31290b57cec5SDimitry Andric unsigned WidestBundleBits = 0;
31300b57cec5SDimitry Andric
31310b57cec5SDimitry Andric using MultiNodeOpTy =
31320b57cec5SDimitry Andric typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;
31330b57cec5SDimitry Andric
31340b57cec5SDimitry Andric // Input operand bundles for the current multi node. Each multi node operand
31350b57cec5SDimitry Andric // bundle contains values not matching the multi node's opcode. They will
31360b57cec5SDimitry Andric // be reordered in reorderMultiNodeOps, once we completed building a
31370b57cec5SDimitry Andric // multi node.
31380b57cec5SDimitry Andric SmallVector<MultiNodeOpTy, 4> MultiNodeOps;
31390b57cec5SDimitry Andric
31400b57cec5SDimitry Andric /// Indicates whether we are building a multi node currently.
31410b57cec5SDimitry Andric bool MultiNodeActive = false;
31420b57cec5SDimitry Andric
31430b57cec5SDimitry Andric /// Check if we can vectorize Operands together.
31440b57cec5SDimitry Andric bool areVectorizable(ArrayRef<VPValue *> Operands) const;
31450b57cec5SDimitry Andric
31460b57cec5SDimitry Andric /// Add combined instruction \p New for the bundle \p Operands.
31470b57cec5SDimitry Andric void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);
31480b57cec5SDimitry Andric
31490b57cec5SDimitry Andric /// Indicate we hit a bundle we failed to combine. Returns nullptr for now.
31500b57cec5SDimitry Andric VPInstruction *markFailed();
31510b57cec5SDimitry Andric
31520b57cec5SDimitry Andric /// Reorder operands in the multi node to maximize sequential memory access
31530b57cec5SDimitry Andric /// and commutative operations.
31540b57cec5SDimitry Andric SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();
31550b57cec5SDimitry Andric
31560b57cec5SDimitry Andric /// Choose the best candidate to use for the lane after \p Last. The set of
31570b57cec5SDimitry Andric /// candidates to choose from are values with an opcode matching \p Last's
31580b57cec5SDimitry Andric /// or loads consecutive to \p Last.
31590b57cec5SDimitry Andric std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,
31600b57cec5SDimitry Andric SmallPtrSetImpl<VPValue *> &Candidates,
31610b57cec5SDimitry Andric VPInterleavedAccessInfo &IAI);
31620b57cec5SDimitry Andric
3163fe6060f1SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
31640b57cec5SDimitry Andric /// Print bundle \p Values to dbgs().
31650b57cec5SDimitry Andric void dumpBundle(ArrayRef<VPValue *> Values);
3166fe6060f1SDimitry Andric #endif
31670b57cec5SDimitry Andric
31680b57cec5SDimitry Andric public:
VPlanSlp(VPInterleavedAccessInfo & IAI,VPBasicBlock & BB)31690b57cec5SDimitry Andric VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {}
31700b57cec5SDimitry Andric
3171e8d8bef9SDimitry Andric ~VPlanSlp() = default;
31720b57cec5SDimitry Andric
31730b57cec5SDimitry Andric /// Tries to build an SLP tree rooted at \p Operands and returns a
31740b57cec5SDimitry Andric /// VPInstruction combining \p Operands, if they can be combined.
31750b57cec5SDimitry Andric VPInstruction *buildGraph(ArrayRef<VPValue *> Operands);
31760b57cec5SDimitry Andric
31770b57cec5SDimitry Andric /// Return the width of the widest combined bundle in bits.
getWidestBundleBits()31780b57cec5SDimitry Andric unsigned getWidestBundleBits() const { return WidestBundleBits; }
31790b57cec5SDimitry Andric
31800b57cec5SDimitry Andric /// Return true if all visited instruction can be combined.
isCompletelySLP()31810b57cec5SDimitry Andric bool isCompletelySLP() const { return CompletelySLP; }
31820b57cec5SDimitry Andric };
31831fd87a68SDimitry Andric
31841fd87a68SDimitry Andric namespace vputils {
31851fd87a68SDimitry Andric
31861fd87a68SDimitry Andric /// Returns true if only the first lane of \p Def is used.
31871fd87a68SDimitry Andric bool onlyFirstLaneUsed(VPValue *Def);
31881fd87a68SDimitry Andric
31895f757f3fSDimitry Andric /// Returns true if only the first part of \p Def is used.
31905f757f3fSDimitry Andric bool onlyFirstPartUsed(VPValue *Def);
31915f757f3fSDimitry Andric
319281ad6265SDimitry Andric /// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p
319381ad6265SDimitry Andric /// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in
319481ad6265SDimitry Andric /// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's
319581ad6265SDimitry Andric /// pre-header already contains a recipe expanding \p Expr, return it. If not,
319681ad6265SDimitry Andric /// create a new one.
319781ad6265SDimitry Andric VPValue *getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr,
319881ad6265SDimitry Andric ScalarEvolution &SE);
3199bdd1243dSDimitry Andric
3200bdd1243dSDimitry Andric /// Returns true if \p VPV is uniform after vectorization.
isUniformAfterVectorization(VPValue * VPV)3201bdd1243dSDimitry Andric inline bool isUniformAfterVectorization(VPValue *VPV) {
3202bdd1243dSDimitry Andric // A value defined outside the vector region must be uniform after
3203bdd1243dSDimitry Andric // vectorization inside a vector region.
3204bdd1243dSDimitry Andric if (VPV->isDefinedOutsideVectorRegions())
3205bdd1243dSDimitry Andric return true;
3206bdd1243dSDimitry Andric VPRecipeBase *Def = VPV->getDefiningRecipe();
3207bdd1243dSDimitry Andric assert(Def && "Must have definition for value defined inside vector region");
3208bdd1243dSDimitry Andric if (auto Rep = dyn_cast<VPReplicateRecipe>(Def))
3209bdd1243dSDimitry Andric return Rep->isUniform();
321006c3fb27SDimitry Andric if (auto *GEP = dyn_cast<VPWidenGEPRecipe>(Def))
321106c3fb27SDimitry Andric return all_of(GEP->operands(), isUniformAfterVectorization);
32121db9f3b2SDimitry Andric if (auto *VPI = dyn_cast<VPInstruction>(Def))
32131db9f3b2SDimitry Andric return VPI->getOpcode() == VPInstruction::ComputeReductionResult;
3214bdd1243dSDimitry Andric return false;
3215bdd1243dSDimitry Andric }
32161fd87a68SDimitry Andric } // end namespace vputils
32171fd87a68SDimitry Andric
32180b57cec5SDimitry Andric } // end namespace llvm
32190b57cec5SDimitry Andric
32200b57cec5SDimitry Andric #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
3221