472 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file10/// This file contains the declarations of different VPlan-related auxiliary11/// helpers.12//13//===----------------------------------------------------------------------===//14 15#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANHELPERS_H16#define LLVM_TRANSFORMS_VECTORIZE_VPLANHELPERS_H17 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 InnerLoopVectorizer;35class IRBuilderBase;36class LoopInfo;37class SCEV;38class Type;39class VPBasicBlock;40class VPRegionBlock;41class VPlan;42class Value;43 44/// Returns a calculation for the total number of elements for a given \p VF.45/// For fixed width vectors this value is a constant, whereas for scalable46/// vectors it is an expression determined at runtime.47Value *getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF);48 49/// Return a value for Step multiplied by VF.50Value *createStepForVF(IRBuilderBase &B, Type *Ty, ElementCount VF,51 int64_t Step);52 53/// A range of powers-of-2 vectorization factors with fixed start and54/// adjustable end. The range includes start and excludes end, e.g.,:55/// [1, 16) = {1, 2, 4, 8}56struct VFRange {57 // A power of 2.58 const ElementCount Start;59 60 // A power of 2. If End <= Start range is empty.61 ElementCount End;62 63 bool isEmpty() const {64 return End.getKnownMinValue() <= Start.getKnownMinValue();65 }66 67 VFRange(const ElementCount &Start, const ElementCount &End)68 : Start(Start), End(End) {69 assert(Start.isScalable() == End.isScalable() &&70 "Both Start and End should have the same scalable flag");71 assert(isPowerOf2_32(Start.getKnownMinValue()) &&72 "Expected Start to be a power of 2");73 assert(isPowerOf2_32(End.getKnownMinValue()) &&74 "Expected End to be a power of 2");75 }76 77 /// Iterator to iterate over vectorization factors in a VFRange.78 class iterator79 : 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(isPowerOf2_32(End.getKnownMinValue()));99 return iterator(End);100 }101};102 103/// In what follows, the term "input IR" refers to code that is fed into the104/// vectorizer whereas the term "output IR" refers to code that is generated by105/// the vectorizer.106 107/// VPLane provides a way to access lanes in both fixed width and scalable108/// vectors, where for the latter the lane index sometimes needs calculating109/// 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 a115 /// 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 last118 /// N-element subvector in a scalable vector <vscale x N x <ElTy>>. For119 /// example, a Lane of 0 corresponds to lane `(vscale - 1) * N`, a Lane of120 /// 1 corresponds to `((vscale - 1) * N) + 1`, etc.121 ScalableLast122 };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 the144 // last subvector with VF.getKnownMinValue() elements.145 LaneKind = VPLane::Kind::ScalableLast;146 else147 LaneKind = VPLane::Kind::First;148 return VPLane(LaneOffset, LaneKind);149 }150 151 static VPLane getLastLaneForVF(const ElementCount &VF) {152 return getLaneFromEnd(VF, 1);153 }154 155 /// Returns a compile-time known value for the lane index and asserts if the156 /// lane can only be calculated at runtime.157 unsigned getKnownLane() const {158 assert(LaneKind == Kind::First &&159 "can only get known lane from the beginning");160 return Lane;161 }162 163 /// Returns an expression describing the lane index that can be used at164 /// runtime.165 Value *getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const;166 167 /// Returns the Kind of lane offset.168 Kind getKind() const { return LaneKind; }169 170 /// Returns true if this is the first lane of the whole vector.171 bool isFirstLane() const { return Lane == 0 && LaneKind == Kind::First; }172 173 /// Maps the lane to a cache index based on \p VF.174 unsigned mapToCacheIndex(const ElementCount &VF) const {175 switch (LaneKind) {176 case VPLane::Kind::ScalableLast:177 assert(VF.isScalable() && Lane < VF.getKnownMinValue() &&178 "ScalableLast can only be used with scalable VFs");179 return VF.getKnownMinValue() + Lane;180 default:181 assert(Lane < VF.getKnownMinValue() &&182 "Cannot extract lane larger than VF");183 return Lane;184 }185 }186};187 188/// VPTransformState holds information passed down when "executing" a VPlan,189/// needed for generating the output IR.190struct VPTransformState {191 VPTransformState(const TargetTransformInfo *TTI, ElementCount VF,192 LoopInfo *LI, DominatorTree *DT, AssumptionCache *AC,193 IRBuilderBase &Builder, VPlan *Plan, Loop *CurrentParentLoop,194 Type *CanonicalIVTy);195 /// Target Transform Info.196 const TargetTransformInfo *TTI;197 198 /// The chosen Vectorization Factor of the loop being vectorized.199 ElementCount VF;200 201 /// Hold the index to generate specific scalar instructions. Null indicates202 /// that all instances are to be generated, using either scalar or vector203 /// instructions.204 std::optional<VPLane> Lane;205 206 struct DataState {207 // Each value from the original loop, when vectorized, is represented by a208 // 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 \p IsScalar215 /// is false, otherwise return the generated scalar. \See set.216 Value *get(const VPValue *Def, bool IsScalar = false);217 218 /// Get the generated Value for a given VPValue and given Part and Lane.219 Value *get(const VPValue *Def, const VPLane &Lane);220 221 bool hasVectorValue(const VPValue *Def) {222 return Data.VPV2Vector.contains(Def);223 }224 225 bool hasScalarValue(const VPValue *Def, VPLane Lane) {226 auto I = Data.VPV2Scalars.find(Def);227 if (I == Data.VPV2Scalars.end())228 return false;229 unsigned CacheIdx = Lane.mapToCacheIndex(VF);230 return CacheIdx < I->second.size() && I->second[CacheIdx];231 }232 233 /// Set the generated vector Value for a given VPValue, if \p234 /// IsScalar is false. If \p IsScalar is true, set the scalar in lane 0.235 void set(const VPValue *Def, Value *V, bool IsScalar = false) {236 if (IsScalar) {237 set(Def, V, VPLane(0));238 return;239 }240 assert((VF.isScalar() || isVectorizedTy(V->getType())) &&241 "scalar values must be stored as (0, 0)");242 Data.VPV2Vector[Def] = V;243 }244 245 /// Reset an existing vector value for \p Def and a given \p Part.246 void reset(const VPValue *Def, Value *V) {247 assert(Data.VPV2Vector.contains(Def) && "need to overwrite existing value");248 Data.VPV2Vector[Def] = V;249 }250 251 /// Set the generated scalar \p V for \p Def and the given \p Lane.252 void set(const VPValue *Def, Value *V, const VPLane &Lane) {253 auto &Scalars = Data.VPV2Scalars[Def];254 unsigned CacheIdx = Lane.mapToCacheIndex(VF);255 if (Scalars.size() <= CacheIdx)256 Scalars.resize(CacheIdx + 1);257 assert(!Scalars[CacheIdx] && "should overwrite existing value");258 Scalars[CacheIdx] = V;259 }260 261 /// Reset an existing scalar value for \p Def and a given \p Lane.262 void reset(const VPValue *Def, Value *V, const VPLane &Lane) {263 auto Iter = Data.VPV2Scalars.find(Def);264 assert(Iter != Data.VPV2Scalars.end() &&265 "need to overwrite existing value");266 unsigned CacheIdx = Lane.mapToCacheIndex(VF);267 assert(CacheIdx < Iter->second.size() &&268 "need to overwrite existing value");269 Iter->second[CacheIdx] = V;270 }271 272 /// Set the debug location in the builder using the debug location \p DL.273 void setDebugLocFrom(DebugLoc DL);274 275 /// Insert the scalar value of \p Def at \p Lane into \p Lane of \p WideValue276 /// and return the resulting value.277 Value *packScalarIntoVectorizedValue(const VPValue *Def, Value *WideValue,278 const VPLane &Lane);279 280 /// Hold state information used when constructing the CFG of the output IR,281 /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.282 struct CFGState {283 /// The previous VPBasicBlock visited. Initially set to null.284 VPBasicBlock *PrevVPBB = nullptr;285 286 /// The previous IR BasicBlock created or used. Initially set to the new287 /// header BasicBlock.288 BasicBlock *PrevBB = nullptr;289 290 /// The last IR BasicBlock in the output IR. Set to the exit block of the291 /// vector loop.292 BasicBlock *ExitBB = nullptr;293 294 /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case295 /// of replication, maps the BasicBlock of the last replica created.296 SmallDenseMap<const VPBasicBlock *, BasicBlock *> VPBB2IRBB;297 298 /// Updater for the DominatorTree.299 DomTreeUpdater DTU;300 301 CFGState(DominatorTree *DT)302 : DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy) {}303 } CFG;304 305 /// Hold a pointer to LoopInfo to register new basic blocks in the loop.306 LoopInfo *LI;307 308 /// Hold a pointer to AssumptionCache to register new assumptions after309 /// replicating assume calls.310 AssumptionCache *AC;311 312 /// Hold a reference to the IRBuilder used to generate output IR code.313 IRBuilderBase &Builder;314 315 /// Pointer to the VPlan code is generated for.316 VPlan *Plan;317 318 /// The parent loop object for the current scope, or nullptr.319 Loop *CurrentParentLoop = nullptr;320 321 /// VPlan-based type analysis.322 VPTypeAnalysis TypeAnalysis;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 VPTypeAnalysis Types;333 LLVMContext &LLVMCtx;334 LoopVectorizationCostModel &CM;335 SmallPtrSet<Instruction *, 8> SkipCostComputation;336 TargetTransformInfo::TargetCostKind CostKind;337 ScalarEvolution &SE;338 const Loop *L;339 340 VPCostContext(const TargetTransformInfo &TTI, const TargetLibraryInfo &TLI,341 const VPlan &Plan, LoopVectorizationCostModel &CM,342 TargetTransformInfo::TargetCostKind CostKind,343 ScalarEvolution &SE, const Loop *L)344 : TTI(TTI), TLI(TLI), Types(Plan), LLVMCtx(Plan.getContext()), CM(CM),345 CostKind(CostKind), SE(SE), L(L) {}346 347 /// Return the cost for \p UI with \p VF using the legacy cost model as348 /// 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 it352 /// has already been pre-computed.353 bool skipCostComputation(Instruction *UI, bool IsVector) const;354 355 /// \returns how much the cost of a predicated block should be divided by.356 /// Forwards to LoopVectorizationCostModel::getPredBlockCostDivisor.357 unsigned getPredBlockCostDivisor(BasicBlock *BB) const;358 359 /// Returns the OperandInfo for \p V, if it is a live-in.360 TargetTransformInfo::OperandValueInfo getOperandInfo(VPValue *V) const;361 362 /// Return true if \p I is considered uniform-after-vectorization in the363 /// legacy cost model for \p VF. Only used to check for additional VPlan364 /// simplifications.365 bool isLegacyUniformAfterVectorization(Instruction *I, ElementCount VF) const;366 367 /// Estimate the overhead of scalarizing a recipe with result type \p ResultTy368 /// and \p Operands with \p VF. This is a convenience wrapper for the369 /// type-based getScalarizationOverhead API. If \p AlwaysIncludeReplicatingR370 /// is true, always compute the cost of scalarizing replicating operands.371 InstructionCost372 getScalarizationOverhead(Type *ResultTy, ArrayRef<const VPValue *> Operands,373 ElementCount VF,374 bool AlwaysIncludeReplicatingR = false);375};376 377/// This class can be used to assign names to VPValues. For VPValues without378/// underlying value, assign consecutive numbers and use those as names (wrapped379/// in vp<>). Otherwise, use the name from the underlying value (wrapped in380/// ir<>), appending a .V version number if there are multiple uses of the same381/// name. Allows querying names for VPValues for printing, similar to the382/// ModuleSlotTracker for IR values.383class VPSlotTracker {384 /// Keep track of versioned names assigned to VPValues with underlying IR385 /// values.386 DenseMap<const VPValue *, std::string> VPValue2Name;387 /// Keep track of the next number to use to version the base name.388 StringMap<unsigned> BaseName2Version;389 390 /// Number to assign to the next VPValue without underlying value.391 unsigned NextSlot = 0;392 393 /// Lazily created ModuleSlotTracker, used only when unnamed IR instructions394 /// require slot tracking.395 std::unique_ptr<ModuleSlotTracker> MST;396 397 void assignName(const VPValue *V);398 LLVM_ABI_FOR_TEST void assignNames(const VPlan &Plan);399 void assignNames(const VPBasicBlock *VPBB);400 std::string getName(const Value *V);401 402public:403 VPSlotTracker(const VPlan *Plan = nullptr) {404 if (Plan)405 assignNames(*Plan);406 }407 408 /// Returns the name assigned to \p V, if there is one, otherwise try to409 /// construct one from the underlying value, if there's one; else return410 /// <badref>.411 std::string getOrCreateName(const VPValue *V) const;412};413 414#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)415/// VPlanPrinter prints a given VPlan to a given output stream. The printing is416/// indented and follows the dot format.417class VPlanPrinter {418 raw_ostream &OS;419 const VPlan &Plan;420 unsigned Depth = 0;421 unsigned TabWidth = 2;422 std::string Indent;423 unsigned BID = 0;424 SmallDenseMap<const VPBlockBase *, unsigned> BlockID;425 426 VPSlotTracker SlotTracker;427 428 /// Handle indentation.429 void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }430 431 /// Print a given \p Block of the Plan.432 void dumpBlock(const VPBlockBase *Block);433 434 /// Print the information related to the CFG edges going out of a given435 /// \p Block, followed by printing the successor blocks themselves.436 void dumpEdges(const VPBlockBase *Block);437 438 /// Print a given \p BasicBlock, including its VPRecipes, followed by printing439 /// its successor blocks.440 void dumpBasicBlock(const VPBasicBlock *BasicBlock);441 442 /// Print a given \p Region of the Plan.443 void dumpRegion(const VPRegionBlock *Region);444 445 unsigned getOrCreateBID(const VPBlockBase *Block) {446 return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;447 }448 449 Twine getOrCreateName(const VPBlockBase *Block);450 451 Twine getUID(const VPBlockBase *Block);452 453 /// Print the information related to a CFG edge between two VPBlockBases.454 void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,455 const Twine &Label);456 457public:458 VPlanPrinter(raw_ostream &O, const VPlan &P)459 : OS(O), Plan(P), SlotTracker(&P) {}460 461 LLVM_DUMP_METHOD void dump();462};463#endif464 465/// Check if a constant \p CI can be safely treated as having been extended466/// from a narrower type with the given extension kind.467bool canConstantBeExtended(const APInt *C, Type *NarrowType,468 TTI::PartialReductionExtendKind ExtKind);469} // end namespace llvm470 471#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H472