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