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