451 lines · c
1//===- VPlanValue.h - Represent Values in Vectorizer Plan -----------------===//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 the entities induced by Vectorization11/// Plans, e.g. the instructions the VPlan intends to generate if executed.12/// VPlan models the following entities:13/// VPValue VPUser VPDef14/// | |15/// VPInstruction16/// These are documented in docs/VectorizationPlan.rst.17///18//===----------------------------------------------------------------------===//19 20#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H21#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H22 23#include "llvm/ADT/DenseMap.h"24#include "llvm/ADT/STLExtras.h"25#include "llvm/ADT/SmallVector.h"26#include "llvm/ADT/StringMap.h"27#include "llvm/ADT/TinyPtrVector.h"28#include "llvm/ADT/iterator_range.h"29#include "llvm/Support/Compiler.h"30 31namespace llvm {32 33// Forward declarations.34class raw_ostream;35class Value;36class VPDef;37struct VPDoubleValueDef;38class VPSlotTracker;39class VPUser;40class VPRecipeBase;41class VPInterleaveBase;42class VPPhiAccessors;43 44/// This is the base class of the VPlan Def/Use graph, used for modeling the45/// data flow into, within and out of the VPlan. VPValues can stand for live-ins46/// coming from the input IR and instructions which VPlan will generate if47/// executed.48class LLVM_ABI_FOR_TEST VPValue {49 friend class VPDef;50 friend struct VPDoubleValueDef;51 friend class VPInterleaveBase;52 friend class VPlan;53 friend class VPExpressionRecipe;54 55 const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).56 57 SmallVector<VPUser *, 1> Users;58 59protected:60 /// Hold the underlying Value, if any, attached to this VPValue.61 Value *UnderlyingVal;62 63 /// Pointer to the VPDef that defines this VPValue. If it is nullptr, the64 /// VPValue is not defined by any recipe modeled in VPlan.65 VPDef *Def;66 67 VPValue(const unsigned char SC, Value *UV = nullptr, VPDef *Def = nullptr);68 69 /// Create a live-in VPValue.70 VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV, nullptr) {}71 /// Create a VPValue for a \p Def which is a subclass of VPValue.72 VPValue(VPDef *Def, Value *UV = nullptr) : VPValue(VPVRecipeSC, UV, Def) {}73 /// Create a VPValue for a \p Def which defines multiple values.74 VPValue(Value *UV, VPDef *Def) : VPValue(VPValueSC, UV, Def) {}75 76 // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to77 // the front-end and back-end of VPlan so that the middle-end is as78 // independent as possible of the underlying IR. We grant access to the79 // underlying IR using friendship. In that way, we should be able to use VPlan80 // for multiple underlying IRs (Polly?) by providing a new VPlan front-end,81 // back-end and analysis information for the new IR.82 83public:84 /// Return the underlying Value attached to this VPValue.85 Value *getUnderlyingValue() const { return UnderlyingVal; }86 87 /// An enumeration for keeping track of the concrete subclass of VPValue that88 /// are actually instantiated.89 enum {90 VPValueSC, /// A generic VPValue, like live-in values or defined by a recipe91 /// that defines multiple values.92 VPVRecipeSC /// A VPValue sub-class that is a VPRecipeBase.93 };94 95 VPValue(const VPValue &) = delete;96 VPValue &operator=(const VPValue &) = delete;97 98 virtual ~VPValue();99 100 /// \return an ID for the concrete type of this object.101 /// This is used to implement the classof checks. This should not be used102 /// for any other purpose, as the values may change as LLVM evolves.103 unsigned getVPValueID() const { return SubclassID; }104 105#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)106 void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;107 void print(raw_ostream &OS, VPSlotTracker &Tracker) const;108 109 /// Dump the value to stderr (for debugging).110 void dump() const;111#endif112 113 unsigned getNumUsers() const { return Users.size(); }114 void addUser(VPUser &User) { Users.push_back(&User); }115 116 /// Remove a single \p User from the list of users.117 void removeUser(VPUser &User) {118 // The same user can be added multiple times, e.g. because the same VPValue119 // is used twice by the same VPUser. Remove a single one.120 auto *I = find(Users, &User);121 if (I != Users.end())122 Users.erase(I);123 }124 125 typedef SmallVectorImpl<VPUser *>::iterator user_iterator;126 typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;127 typedef iterator_range<user_iterator> user_range;128 typedef iterator_range<const_user_iterator> const_user_range;129 130 user_iterator user_begin() { return Users.begin(); }131 const_user_iterator user_begin() const { return Users.begin(); }132 user_iterator user_end() { return Users.end(); }133 const_user_iterator user_end() const { return Users.end(); }134 user_range users() { return user_range(user_begin(), user_end()); }135 const_user_range users() const {136 return const_user_range(user_begin(), user_end());137 }138 139 /// Returns true if the value has more than one unique user.140 bool hasMoreThanOneUniqueUser() const {141 if (getNumUsers() == 0)142 return false;143 144 // Check if all users match the first user.145 auto Current = std::next(user_begin());146 while (Current != user_end() && *user_begin() == *Current)147 Current++;148 return Current != user_end();149 }150 151 bool hasOneUse() const { return getNumUsers() == 1; }152 153 /// Return the single user of this value, or nullptr if there is not exactly154 /// one user.155 VPUser *getSingleUser() { return hasOneUse() ? *user_begin() : nullptr; }156 const VPUser *getSingleUser() const {157 return hasOneUse() ? *user_begin() : nullptr;158 }159 160 void replaceAllUsesWith(VPValue *New);161 162 /// Go through the uses list for this VPValue and make each use point to \p163 /// New if the callback ShouldReplace returns true for the given use specified164 /// by a pair of (VPUser, the use index).165 void replaceUsesWithIf(166 VPValue *New,167 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace);168 169 /// Returns the recipe defining this VPValue or nullptr if it is not defined170 /// by a recipe, i.e. is a live-in.171 VPRecipeBase *getDefiningRecipe();172 const VPRecipeBase *getDefiningRecipe() const;173 174 /// Returns true if this VPValue is defined by a recipe.175 bool hasDefiningRecipe() const { return getDefiningRecipe(); }176 177 /// Returns true if this VPValue is a live-in, i.e. defined outside the VPlan.178 bool isLiveIn() const { return !hasDefiningRecipe(); }179 180 /// Returns the underlying IR value, if this VPValue is defined outside the181 /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef182 /// inside a VPlan.183 Value *getLiveInIRValue() const {184 assert(isLiveIn() &&185 "VPValue is not a live-in; it is defined by a VPDef inside a VPlan");186 return getUnderlyingValue();187 }188 189 /// Returns true if the VPValue is defined outside any loop.190 bool isDefinedOutsideLoopRegions() const;191 192 // Set \p Val as the underlying Value of this VPValue.193 void setUnderlyingValue(Value *Val) {194 assert(!UnderlyingVal && "Underlying Value is already set.");195 UnderlyingVal = Val;196 }197};198 199typedef DenseMap<Value *, VPValue *> Value2VPValueTy;200typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;201 202LLVM_ABI_FOR_TEST raw_ostream &operator<<(raw_ostream &OS,203 const VPRecipeBase &R);204 205/// This class augments VPValue with operands which provide the inverse def-use206/// edges from VPValue's users to their defs.207class VPUser {208 /// Grant access to removeOperand for VPPhiAccessors, the only supported user.209 friend class VPPhiAccessors;210 211 SmallVector<VPValue *, 2> Operands;212 213 /// Removes the operand at index \p Idx. This also removes the VPUser from the214 /// use-list of the operand.215 void removeOperand(unsigned Idx) {216 getOperand(Idx)->removeUser(*this);217 Operands.erase(Operands.begin() + Idx);218 }219 220protected:221#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)222 /// Print the operands to \p O.223 void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;224#endif225 226 VPUser(ArrayRef<VPValue *> Operands) {227 for (VPValue *Operand : Operands)228 addOperand(Operand);229 }230 231public:232 VPUser() = delete;233 VPUser(const VPUser &) = delete;234 VPUser &operator=(const VPUser &) = delete;235 virtual ~VPUser() {236 for (VPValue *Op : operands())237 Op->removeUser(*this);238 }239 240 void addOperand(VPValue *Operand) {241 Operands.push_back(Operand);242 Operand->addUser(*this);243 }244 245 unsigned getNumOperands() const { return Operands.size(); }246 inline VPValue *getOperand(unsigned N) const {247 assert(N < Operands.size() && "Operand index out of bounds");248 return Operands[N];249 }250 251 void setOperand(unsigned I, VPValue *New) {252 Operands[I]->removeUser(*this);253 Operands[I] = New;254 New->addUser(*this);255 }256 257 /// Swap operands of the VPUser. It must have exactly 2 operands.258 void swapOperands() {259 assert(Operands.size() == 2 && "must have 2 operands to swap");260 std::swap(Operands[0], Operands[1]);261 }262 263 /// Replaces all uses of \p From in the VPUser with \p To.264 void replaceUsesOfWith(VPValue *From, VPValue *To);265 266 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;267 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;268 typedef iterator_range<operand_iterator> operand_range;269 typedef iterator_range<const_operand_iterator> const_operand_range;270 271 operand_iterator op_begin() { return Operands.begin(); }272 const_operand_iterator op_begin() const { return Operands.begin(); }273 operand_iterator op_end() { return Operands.end(); }274 const_operand_iterator op_end() const { return Operands.end(); }275 operand_range operands() { return operand_range(op_begin(), op_end()); }276 const_operand_range operands() const {277 return const_operand_range(op_begin(), op_end());278 }279 280 /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively281 /// returns if only first (scalar) lane is used, as default.282 virtual bool usesScalars(const VPValue *Op) const {283 assert(is_contained(operands(), Op) &&284 "Op must be an operand of the recipe");285 return usesFirstLaneOnly(Op);286 }287 288 /// Returns true if the VPUser only uses the first lane of operand \p Op.289 /// Conservatively returns false.290 virtual bool usesFirstLaneOnly(const VPValue *Op) const {291 assert(is_contained(operands(), Op) &&292 "Op must be an operand of the recipe");293 return false;294 }295 296 /// Returns true if the VPUser only uses the first part of operand \p Op.297 /// Conservatively returns false.298 virtual bool usesFirstPartOnly(const VPValue *Op) const {299 assert(is_contained(operands(), Op) &&300 "Op must be an operand of the recipe");301 return false;302 }303};304 305/// This class augments a recipe with a set of VPValues defined by the recipe.306/// It allows recipes to define zero, one or multiple VPValues. A VPDef owns307/// the VPValues it defines and is responsible for deleting its defined values.308/// Single-value VPDefs that also inherit from VPValue must make sure to inherit309/// from VPDef before VPValue.310class VPDef {311 friend class VPValue;312 313 /// Subclass identifier (for isa/dyn_cast).314 const unsigned char SubclassID;315 316 /// The VPValues defined by this VPDef.317 TinyPtrVector<VPValue *> DefinedValues;318 319 /// Add \p V as a defined value by this VPDef.320 void addDefinedValue(VPValue *V) {321 assert(V->Def == this &&322 "can only add VPValue already linked with this VPDef");323 DefinedValues.push_back(V);324 }325 326 /// Remove \p V from the values defined by this VPDef. \p V must be a defined327 /// value of this VPDef.328 void removeDefinedValue(VPValue *V) {329 assert(V->Def == this && "can only remove VPValue linked with this VPDef");330 assert(is_contained(DefinedValues, V) &&331 "VPValue to remove must be in DefinedValues");332 llvm::erase(DefinedValues, V);333 V->Def = nullptr;334 }335 336public:337 /// An enumeration for keeping track of the concrete subclass of VPRecipeBase338 /// that is actually instantiated. Values of this enumeration are kept in the339 /// SubclassID field of the VPRecipeBase objects. They are used for concrete340 /// type identification.341 using VPRecipeTy = enum {342 VPBranchOnMaskSC,343 VPDerivedIVSC,344 VPExpandSCEVSC,345 VPExpressionSC,346 VPIRInstructionSC,347 VPInstructionSC,348 VPInterleaveEVLSC,349 VPInterleaveSC,350 VPReductionEVLSC,351 VPReductionSC,352 VPReplicateSC,353 VPScalarIVStepsSC,354 VPVectorPointerSC,355 VPVectorEndPointerSC,356 VPWidenCallSC,357 VPWidenCanonicalIVSC,358 VPWidenCastSC,359 VPWidenGEPSC,360 VPWidenIntrinsicSC,361 VPWidenLoadEVLSC,362 VPWidenLoadSC,363 VPWidenStoreEVLSC,364 VPWidenStoreSC,365 VPWidenSC,366 VPWidenSelectSC,367 VPBlendSC,368 VPHistogramSC,369 // START: Phi-like recipes. Need to be kept together.370 VPWidenPHISC,371 VPPredInstPHISC,372 // START: SubclassID for recipes that inherit VPHeaderPHIRecipe.373 // VPHeaderPHIRecipe need to be kept together.374 VPCanonicalIVPHISC,375 VPActiveLaneMaskPHISC,376 VPEVLBasedIVPHISC,377 VPFirstOrderRecurrencePHISC,378 VPWidenIntOrFpInductionSC,379 VPWidenPointerInductionSC,380 VPReductionPHISC,381 // END: SubclassID for recipes that inherit VPHeaderPHIRecipe382 // END: Phi-like recipes383 VPFirstPHISC = VPWidenPHISC,384 VPFirstHeaderPHISC = VPCanonicalIVPHISC,385 VPLastHeaderPHISC = VPReductionPHISC,386 VPLastPHISC = VPReductionPHISC,387 };388 389 VPDef(const unsigned char SC) : SubclassID(SC) {}390 391 virtual ~VPDef() {392 for (VPValue *D : make_early_inc_range(DefinedValues)) {393 assert(D->Def == this &&394 "all defined VPValues should point to the containing VPDef");395 assert(D->getNumUsers() == 0 &&396 "all defined VPValues should have no more users");397 D->Def = nullptr;398 delete D;399 }400 }401 402 /// Returns the only VPValue defined by the VPDef. Can only be called for403 /// VPDefs with a single defined value.404 VPValue *getVPSingleValue() {405 assert(DefinedValues.size() == 1 && "must have exactly one defined value");406 assert(DefinedValues[0] && "defined value must be non-null");407 return DefinedValues[0];408 }409 const VPValue *getVPSingleValue() const {410 assert(DefinedValues.size() == 1 && "must have exactly one defined value");411 assert(DefinedValues[0] && "defined value must be non-null");412 return DefinedValues[0];413 }414 415 /// Returns the VPValue with index \p I defined by the VPDef.416 VPValue *getVPValue(unsigned I) {417 assert(DefinedValues[I] && "defined value must be non-null");418 return DefinedValues[I];419 }420 const VPValue *getVPValue(unsigned I) const {421 assert(DefinedValues[I] && "defined value must be non-null");422 return DefinedValues[I];423 }424 425 /// Returns an ArrayRef of the values defined by the VPDef.426 ArrayRef<VPValue *> definedValues() { return DefinedValues; }427 /// Returns an ArrayRef of the values defined by the VPDef.428 ArrayRef<VPValue *> definedValues() const { return DefinedValues; }429 430 /// Returns the number of values defined by the VPDef.431 unsigned getNumDefinedValues() const { return DefinedValues.size(); }432 433 /// \return an ID for the concrete type of this object.434 /// This is used to implement the classof checks. This should not be used435 /// for any other purpose, as the values may change as LLVM evolves.436 unsigned getVPDefID() const { return SubclassID; }437 438#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)439 /// Dump the VPDef to stderr (for debugging).440 LLVM_ABI_FOR_TEST void dump() const;441 442 /// Each concrete VPDef prints itself.443 virtual void print(raw_ostream &O, const Twine &Indent,444 VPSlotTracker &SlotTracker) const = 0;445#endif446};447 448} // namespace llvm449 450#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H451