1//===- VPlanHelpers.h - VPlan-related auxiliary helpers -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// This file contains the declarations of different VPlan-related auxiliary
11/// helpers.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANHELPERS_H
16#define LLVM_TRANSFORMS_VECTORIZE_VPLANHELPERS_H
17
18#include "VPlanAnalysis.h"
19#include "VPlanDominatorTree.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/Analysis/DomTreeUpdater.h"
24#include "llvm/Analysis/TargetTransformInfo.h"
25#include "llvm/IR/DebugLoc.h"
26#include "llvm/IR/ModuleSlotTracker.h"
27#include "llvm/Support/InstructionCost.h"
28
29namespace llvm {
30
31class AssumptionCache;
32class BasicBlock;
33class DominatorTree;
34class Function;
35class IRBuilderBase;
36class LoopInfo;
37class Type;
38class VFSelectionContext;
39class VPBasicBlock;
40class VPRegionBlock;
41class VPlan;
42class VPSlotTracker;
43class Value;
44struct VectorizeOptions;
45
46namespace Intrinsic {
47typedef unsigned ID;
48}
49
50/// Returns a calculation for the total number of elements for a given \p VF.
51/// For fixed width vectors this value is a constant, whereas for scalable
52/// vectors it is an expression determined at runtime.
53Value *getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF);
54
55/// A range of powers-of-2 vectorization factors with fixed start and
56/// adjustable end. The range includes start and excludes end, e.g.,:
57/// [1, 16) = {1, 2, 4, 8}
58struct VFRange {
59 // A power of 2.
60 const ElementCount Start;
61
62 // A power of 2. If End <= Start range is empty.
63 ElementCount End;
64
65 bool isEmpty() const {
66 return End.getKnownMinValue() <= Start.getKnownMinValue();
67 }
68
69 VFRange(const ElementCount &Start, const ElementCount &End)
70 : Start(Start), End(End) {
71 assert(Start.isScalable() == End.isScalable() &&
72 "Both Start and End should have the same scalable flag");
73 assert(Start.isPowerOf2() && "Expected Start to be a power of 2");
74 assert(End.isPowerOf2() && "Expected End to be a power of 2");
75 }
76
77 /// Iterator to iterate over vectorization factors in a VFRange.
78 class iterator
79 : public iterator_facade_base<iterator, std::forward_iterator_tag,
80 ElementCount> {
81 ElementCount VF;
82
83 public:
84 iterator(ElementCount VF) : VF(VF) {}
85
86 bool operator==(const iterator &Other) const { return VF == Other.VF; }
87
88 ElementCount operator*() const { return VF; }
89
90 iterator &operator++() {
91 VF *= 2;
92 return *this;
93 }
94 };
95
96 iterator begin() { return iterator(Start); }
97 iterator end() {
98 assert(End.isPowerOf2());
99 return iterator(End);
100 }
101};
102
103/// In what follows, the term "input IR" refers to code that is fed into the
104/// vectorizer whereas the term "output IR" refers to code that is generated by
105/// the vectorizer.
106
107/// VPLane provides a way to access lanes in both fixed width and scalable
108/// vectors, where for the latter the lane index sometimes needs calculating
109/// as a runtime expression.
110class VPLane {
111public:
112 /// Kind describes how to interpret Lane.
113 enum class Kind : uint8_t {
114 /// For First, Lane is the index into the first N elements of a
115 /// fixed-vector <N x <ElTy>> or a scalable vector <vscale x N x <ElTy>>.
116 First,
117 /// For ScalableLast, Lane is the offset from the start of the last
118 /// N-element subvector in a scalable vector <vscale x N x <ElTy>>. For
119 /// example, a Lane of 0 corresponds to lane `(vscale - 1) * N`, a Lane of
120 /// 1 corresponds to `((vscale - 1) * N) + 1`, etc.
121 ScalableLast
122 };
123
124private:
125 /// in [0..VF)
126 unsigned Lane;
127
128 /// Indicates how the Lane should be interpreted, as described above.
129 Kind LaneKind = Kind::First;
130
131public:
132 VPLane(unsigned Lane) : Lane(Lane) {}
133 VPLane(unsigned Lane, Kind LaneKind) : Lane(Lane), LaneKind(LaneKind) {}
134
135 static VPLane getFirstLane() { return VPLane(0, VPLane::Kind::First); }
136
137 static VPLane getLaneFromEnd(const ElementCount &VF, unsigned Offset) {
138 assert(Offset > 0 && Offset <= VF.getKnownMinValue() &&
139 "trying to extract with invalid offset");
140 unsigned LaneOffset = VF.getKnownMinValue() - Offset;
141 Kind LaneKind;
142 if (VF.isScalable())
143 // In this case 'LaneOffset' refers to the offset from the start of the
144 // last subvector with VF.getKnownMinValue() elements.
145 LaneKind = VPLane::Kind::ScalableLast;
146 else
147 LaneKind = VPLane::Kind::First;
148 return VPLane(LaneOffset, LaneKind);
149 }
150
151 static VPLane getLastLaneForVF(const ElementCount &VF) {
152 return getLaneFromEnd(VF, Offset: 1);
153 }
154
155 /// Returns an expression describing the lane index that can be used at
156 /// runtime.
157 Value *getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const;
158
159 /// Returns true if this is the first lane of the whole vector.
160 bool isFirstLane() const { return Lane == 0 && LaneKind == Kind::First; }
161
162 /// Maps the lane to a cache index based on \p VF.
163 unsigned mapToCacheIndex(const ElementCount &VF) const {
164 switch (LaneKind) {
165 case VPLane::Kind::ScalableLast:
166 assert(VF.isScalable() && Lane < VF.getKnownMinValue() &&
167 "ScalableLast can only be used with scalable VFs");
168 return VF.getKnownMinValue() + Lane;
169 default:
170 assert(Lane < VF.getKnownMinValue() &&
171 "Cannot extract lane larger than VF");
172 return Lane;
173 }
174 }
175};
176
177/// VPTransformState holds information passed down when "executing" a VPlan,
178/// needed for generating the output IR.
179struct VPTransformState {
180 VPTransformState(const TargetTransformInfo *TTI, ElementCount VF,
181 LoopInfo *LI, DominatorTree *DT, AssumptionCache *AC,
182 IRBuilderBase &Builder, VPlan *Plan,
183 Loop *CurrentParentLoop);
184 /// Target Transform Info.
185 const TargetTransformInfo *TTI;
186
187 /// The chosen Vectorization Factor of the loop being vectorized.
188 ElementCount VF;
189
190 struct DataState {
191 // Each value from the original loop, when vectorized, is represented by a
192 // vector value in the map.
193 DenseMap<const VPValue *, Value *> VPV2Vector;
194
195 DenseMap<const VPValue *, SmallVector<Value *, 4>> VPV2Scalars;
196 } Data;
197
198 /// Get the generated vector Value for a given VPValue \p Def if
199 /// \p NeedsSingleScalar is false, otherwise return the generated scalar.
200 /// \See set.
201 Value *get(const VPValue *Def, bool NeedsSingleScalar = false);
202
203 /// Get the generated Value for a given VPValue and given Part and Lane.
204 Value *get(const VPValue *Def, const VPLane &Lane);
205
206 bool hasVectorValue(const VPValue *Def) {
207 return Data.VPV2Vector.contains(Val: Def);
208 }
209
210 bool hasScalarValue(const VPValue *Def, VPLane Lane) {
211 auto I = Data.VPV2Scalars.find(Val: Def);
212 if (I == Data.VPV2Scalars.end())
213 return false;
214 unsigned CacheIdx = Lane.mapToCacheIndex(VF);
215 return CacheIdx < I->second.size() && I->second[CacheIdx];
216 }
217
218 /// Set the generated vector Value for a given VPValue, if \p
219 /// IsScalar is false. If \p IsScalar is true, set the scalar in lane 0.
220 void set(const VPValue *Def, Value *V, bool IsScalar = false) {
221 if (IsScalar) {
222 set(Def, V, Lane: VPLane(0));
223 return;
224 }
225 assert((VF.isScalar() || isVectorizedTy(V->getType())) &&
226 "scalar values must be stored as (0, 0)");
227 Data.VPV2Vector[Def] = V;
228 }
229
230 /// Set the generated scalar \p V for \p Def and the given \p Lane.
231 void set(const VPValue *Def, Value *V, const VPLane &Lane) {
232 auto &Scalars = Data.VPV2Scalars[Def];
233 unsigned CacheIdx = Lane.mapToCacheIndex(VF);
234 if (Scalars.size() <= CacheIdx)
235 Scalars.resize(N: CacheIdx + 1);
236 assert(!Scalars[CacheIdx] && "should overwrite existing value");
237 Scalars[CacheIdx] = V;
238 }
239
240 /// Set the debug location in the builder using the debug location \p DL.
241 void setDebugLocFrom(DebugLoc DL);
242
243 /// Add the backedge (latch) incoming value to the canonical, reduction and
244 /// first-order recurrence phis in all loop headers state's plan, after
245 /// the loop body has been generated.
246 void fixupHeaderPhis();
247
248 /// Hold state information used when constructing the CFG of the output IR,
249 /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
250 struct CFGState {
251 /// The previous VPBasicBlock visited. Initially set to null.
252 VPBasicBlock *PrevVPBB = nullptr;
253
254 /// The previous IR BasicBlock created or used. Initially set to the new
255 /// header BasicBlock.
256 BasicBlock *PrevBB = nullptr;
257
258 /// The last IR BasicBlock in the output IR. Set to the exit block of the
259 /// vector loop.
260 BasicBlock *ExitBB = nullptr;
261
262 /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
263 /// of replication, maps the BasicBlock of the last replica created.
264 SmallDenseMap<const VPBasicBlock *, BasicBlock *> VPBB2IRBB;
265
266 /// Updater for the DominatorTree.
267 DomTreeUpdater DTU;
268
269 CFGState(DominatorTree *DT)
270 : DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy) {}
271 } CFG;
272
273 /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
274 LoopInfo *LI;
275
276 /// Hold a pointer to AssumptionCache to register new assumptions after
277 /// replicating assume calls.
278 AssumptionCache *AC;
279
280 /// Hold a reference to the IRBuilder used to generate output IR code.
281 IRBuilderBase &Builder;
282
283 /// Pointer to the VPlan code is generated for.
284 VPlan *Plan;
285
286 /// The parent loop object for the current scope, or nullptr.
287 Loop *CurrentParentLoop = nullptr;
288
289 /// VPlan-based dominator tree.
290 VPDominatorTree VPDT;
291};
292
293/// Struct to hold various analysis needed for cost computations.
294struct VPCostContext {
295 const VectorizeOptions &Opts;
296 const TargetTransformInfo &TTI;
297 const TargetLibraryInfo &TLI;
298 LLVMContext &LLVMCtx;
299 LoopVectorizationCostModel &CM;
300 const VFSelectionContext &Config;
301 SmallPtrSet<Instruction *, 8> SkipCostComputation;
302 TargetTransformInfo::TargetCostKind CostKind;
303 PredicatedScalarEvolution &PSE;
304 const Loop *L;
305
306 /// Number of predicated stores in the VPlan, computed on demand.
307 std::optional<unsigned> NumPredStores;
308
309 VPCostContext(const TargetLibraryInfo &TLI, const VPlan &Plan,
310 LoopVectorizationCostModel &CM, VFSelectionContext &Config,
311 bool ReusePrintingSlotTracker = false);
312
313 /// Return the cost for \p UI with \p VF using the legacy cost model as
314 /// fallback until computing the cost of all recipes migrates to VPlan.
315 InstructionCost getLegacyCost(Instruction *UI, ElementCount VF) const;
316
317 /// Return true if the cost for \p UI shouldn't be computed, e.g. because it
318 /// has already been pre-computed.
319 bool skipCostComputation(Instruction *UI, bool IsVector) const;
320
321 /// Mark the widening decision for \p I at \p VF as invalidated since a VPlan
322 /// transform replaced the original recipe.
323 void invalidateWideningDecision(Instruction *I, ElementCount VF);
324
325 /// \returns how much the cost of a block executing with recorded frequency
326 /// \p Freq should be divided by.
327 uint64_t getCostDivisor(std::optional<VPExecutionFrequency> Freq) const;
328
329 /// Returns true if \p I is known to be scalarized at \p VF.
330 bool willBeScalarized(Instruction *I, ElementCount VF) const;
331
332 /// Returns true if the vector loop body of \p Plan is known to execute at
333 /// most once at \p VF, i.e. its trip count is a constant not greater than
334 /// \p VF. Currently ignores UF.
335 static bool executesAtMostOnce(const VPlan &Plan, ElementCount VF);
336
337 /// Forwards to LoopVectorizationCostModel::isMaskRequired.
338 bool isMaskRequired(Instruction *I) const;
339
340 /// Returns the OperandInfo for \p V, if it is a live-in.
341 TargetTransformInfo::OperandValueInfo getOperandInfo(VPValue *V) const;
342
343 /// Estimate the overhead of scalarizing a recipe with result type \p ResultTy
344 /// and \p Operands with \p VF. This is a convenience wrapper for the
345 /// type-based getScalarizationOverhead API. \p VIC provides context about
346 /// whether the scalarization is for a load/store operation. If \p
347 /// AlwaysIncludeReplicatingR is true, always compute the cost of scalarizing
348 /// replicating operands.
349 InstructionCost getScalarizationOverhead(
350 Type *ResultTy, ArrayRef<const VPValue *> Operands, ElementCount VF,
351 TTI::VectorInstrContext VIC = TTI::VectorInstrContext::None,
352 bool AlwaysIncludeReplicatingR = false);
353
354 /// Returns true if an artificially high cost for emulated masked memrefs
355 /// should be used.
356 bool useEmulatedMaskMemRefHack(const VPReplicateRecipe *R, ElementCount VF);
357
358 /// Returns true if \p ID is a pseudo intrinsic that is dropped via
359 /// scalarization rather than widened.
360 static bool isFreeScalarIntrinsic(Intrinsic::ID ID);
361
362#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
363 /// Return a VPSlotTracker to re-use for printing, lazily constructing it on
364 /// first use. Returns nullptr if slot-tracker re-use was not requested at
365 /// construction.
366 VPSlotTracker *getSlotTracker();
367
368private:
369 /// VPlan to build the printing VPSlotTracker for, or nullptr if slot-tracker
370 /// re-use was not requested.
371 const VPlan *PlanForSlotTracker = nullptr;
372
373 /// SlotTracker to re-use when printing, lazily constructed by getSlotTracker.
374 std::unique_ptr<VPSlotTracker> SlotTracker;
375#endif
376};
377
378/// This class can be used to assign names to VPValues. For VPValues without
379/// underlying value, assign consecutive numbers and use those as names (wrapped
380/// in vp<>). Otherwise, use the name from the underlying value (wrapped in
381/// ir<>), appending a .V version number if there are multiple uses of the same
382/// name. Allows querying names for VPValues for printing, similar to the
383/// ModuleSlotTracker for IR values.
384class VPSlotTracker {
385 /// Keep track of versioned names assigned to VPValues with underlying IR
386 /// values.
387 DenseMap<const VPValue *, std::string> VPValue2Name;
388 /// Keep track of the next number to use to version the base name.
389 StringMap<unsigned> BaseName2Version;
390
391 /// Number to assign to the next VPValue without underlying value.
392 unsigned NextSlot = 0;
393
394 /// Lazily created ModuleSlotTracker, used only when unnamed IR instructions
395 /// require slot tracking.
396 std::unique_ptr<ModuleSlotTracker> MST;
397
398 /// Cached metadata kind names from the Module's LLVMContext.
399 SmallVector<StringRef> MDNames;
400
401 /// Cached Function pointer for printing names and metadata.
402 const Function *F = nullptr;
403
404 void assignName(const VPValue *V);
405 LLVM_ABI_FOR_TEST void assignNames(const VPlan &Plan);
406 void assignNames(const VPBasicBlock *VPBB);
407 std::string getName(const Value *V);
408
409 /// Lazily create the ModuleSlotTracker.
410 ModuleSlotTracker &getOrCreateMST();
411
412public:
413 VPSlotTracker(const VPlan *Plan = nullptr) {
414 if (Plan) {
415 if (auto *ScalarHeader = Plan->getScalarHeader()) {
416 const BasicBlock *ScalarHeaderIRBB = ScalarHeader->getIRBasicBlock();
417 F = ScalarHeaderIRBB->getParent();
418 }
419 assignNames(Plan: *Plan);
420 }
421 }
422
423 /// Returns the name assigned to \p V, if there is one, otherwise try to
424 /// construct one from the underlying value, if there's one; else return
425 /// <badref>.
426 std::string getOrCreateName(const VPValue *V) const;
427
428 /// Returns the cached metadata kind names.
429 ArrayRef<StringRef> getMDNames() {
430 const Module *M = getModule();
431 if (MDNames.empty() && M)
432 M->getContext().getMDKindNames(Result&: MDNames);
433 return MDNames;
434 }
435
436 /// Print a reference to metadata node \p N to \p O.
437 void printMetadataAsOperand(raw_ostream &O, const MDNode *N);
438
439 /// Returns the module the plan operates on, if any.
440 const Module *getModule() const { return F ? F->getParent() : nullptr; }
441};
442
443#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
444/// VPlanPrinter prints a given VPlan to a given output stream. The printing is
445/// indented and follows the dot format.
446class VPlanPrinter {
447 raw_ostream &OS;
448 const VPlan &Plan;
449 unsigned Depth = 0;
450 unsigned TabWidth = 2;
451 std::string Indent;
452 unsigned BID = 0;
453 SmallDenseMap<const VPBlockBase *, unsigned> BlockID;
454
455 VPSlotTracker SlotTracker;
456
457 /// Handle indentation.
458 void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
459
460 /// Print a given \p Block of the Plan.
461 void dumpBlock(const VPBlockBase *Block);
462
463 /// Print the information related to the CFG edges going out of a given
464 /// \p Block, followed by printing the successor blocks themselves.
465 void dumpEdges(const VPBlockBase *Block);
466
467 /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
468 /// its successor blocks.
469 void dumpBasicBlock(const VPBasicBlock *BasicBlock);
470
471 /// Print a given \p Region of the Plan.
472 void dumpRegion(const VPRegionBlock *Region);
473
474 unsigned getOrCreateBID(const VPBlockBase *Block) {
475 return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
476 }
477
478 Twine getUID(const VPBlockBase *Block);
479
480 /// Print the information related to a CFG edge between two VPBlockBases.
481 void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
482 const Twine &Label);
483
484public:
485 VPlanPrinter(raw_ostream &O, const VPlan &P)
486 : OS(O), Plan(P), SlotTracker(&P) {}
487
488 LLVM_DUMP_METHOD void dump();
489};
490#endif
491
492/// Check if a constant \p CI can be safely treated as having been extended
493/// from a narrower type with the given extension kind.
494bool canConstantBeExtended(const APInt *C, Type *NarrowType,
495 TTI::PartialReductionExtendKind ExtKind);
496} // end namespace llvm
497
498#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
499