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