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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file contains the declarations of the entities induced by Vectorization 11 /// Plans, e.g. the instructions the VPlan intends to generate if executed. 12 /// VPlan models the following entities: 13 /// VPValue VPUser VPDef 14 /// | | 15 /// VPInstruction 16 /// These are documented in docs/VectorizationPlan.rst. 17 /// 18 //===----------------------------------------------------------------------===// 19 20 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H 21 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H 22 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/ADT/STLExtras.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/TinyPtrVector.h" 27 #include "llvm/ADT/iterator_range.h" 28 29 namespace llvm { 30 31 // Forward declarations. 32 class raw_ostream; 33 class Value; 34 class VPDef; 35 class VPSlotTracker; 36 class VPUser; 37 class VPRecipeBase; 38 class VPWidenMemoryInstructionRecipe; 39 40 // This is the base class of the VPlan Def/Use graph, used for modeling the data 41 // flow into, within and out of the VPlan. VPValues can stand for live-ins 42 // coming from the input IR, instructions which VPlan will generate if executed 43 // and live-outs which the VPlan will need to fix accordingly. 44 class VPValue { 45 friend class VPBuilder; 46 friend class VPDef; 47 friend class VPInstruction; 48 friend struct VPlanTransforms; 49 friend class VPBasicBlock; 50 friend class VPInterleavedAccessInfo; 51 friend class VPSlotTracker; 52 friend class VPRecipeBase; 53 friend class VPWidenMemoryInstructionRecipe; 54 55 const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast). 56 57 SmallVector<VPUser *, 1> Users; 58 59 protected: 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, the 64 /// 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 // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to 70 // the front-end and back-end of VPlan so that the middle-end is as 71 // independent as possible of the underlying IR. We grant access to the 72 // underlying IR using friendship. In that way, we should be able to use VPlan 73 // for multiple underlying IRs (Polly?) by providing a new VPlan front-end, 74 // back-end and analysis information for the new IR. 75 76 // Set \p Val as the underlying Value of this VPValue. 77 void setUnderlyingValue(Value *Val) { 78 assert(!UnderlyingVal && "Underlying Value is already set."); 79 UnderlyingVal = Val; 80 } 81 82 public: 83 /// Return the underlying Value attached to this VPValue. 84 Value *getUnderlyingValue() { return UnderlyingVal; } 85 const Value *getUnderlyingValue() const { return UnderlyingVal; } 86 87 /// An enumeration for keeping track of the concrete subclass of VPValue that 88 /// are actually instantiated. 89 enum { 90 VPValueSC, /// A generic VPValue, like live-in values or defined by a recipe 91 /// that defines multiple values. 92 VPVRecipeSC /// A VPValue sub-class that is a VPRecipeBase. 93 }; 94 95 /// Create a live-in VPValue. 96 VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV, nullptr) {} 97 /// Create a VPValue for a \p Def which is a subclass of VPValue. 98 VPValue(VPDef *Def, Value *UV = nullptr) : VPValue(VPVRecipeSC, UV, Def) {} 99 /// Create a VPValue for a \p Def which defines multiple values. 100 VPValue(Value *UV, VPDef *Def) : VPValue(VPValueSC, UV, Def) {} 101 VPValue(const VPValue &) = delete; 102 VPValue &operator=(const VPValue &) = delete; 103 104 virtual ~VPValue(); 105 106 /// \return an ID for the concrete type of this object. 107 /// This is used to implement the classof checks. This should not be used 108 /// for any other purpose, as the values may change as LLVM evolves. 109 unsigned getVPValueID() const { return SubclassID; } 110 111 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 112 void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const; 113 void print(raw_ostream &OS, VPSlotTracker &Tracker) const; 114 115 /// Dump the value to stderr (for debugging). 116 void dump() const; 117 #endif 118 119 unsigned getNumUsers() const { return Users.size(); } 120 void addUser(VPUser &User) { Users.push_back(&User); } 121 122 /// Remove a single \p User from the list of users. 123 void removeUser(VPUser &User) { 124 bool Found = false; 125 // The same user can be added multiple times, e.g. because the same VPValue 126 // is used twice by the same VPUser. Remove a single one. 127 erase_if(Users, [&User, &Found](VPUser *Other) { 128 if (Found) 129 return false; 130 if (Other == &User) { 131 Found = true; 132 return true; 133 } 134 return false; 135 }); 136 } 137 138 typedef SmallVectorImpl<VPUser *>::iterator user_iterator; 139 typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator; 140 typedef iterator_range<user_iterator> user_range; 141 typedef iterator_range<const_user_iterator> const_user_range; 142 143 user_iterator user_begin() { return Users.begin(); } 144 const_user_iterator user_begin() const { return Users.begin(); } 145 user_iterator user_end() { return Users.end(); } 146 const_user_iterator user_end() const { return Users.end(); } 147 user_range users() { return user_range(user_begin(), user_end()); } 148 const_user_range users() const { 149 return const_user_range(user_begin(), user_end()); 150 } 151 152 /// Returns true if the value has more than one unique user. 153 bool hasMoreThanOneUniqueUser() { 154 if (getNumUsers() == 0) 155 return false; 156 157 // Check if all users match the first user. 158 auto Current = std::next(user_begin()); 159 while (Current != user_end() && *user_begin() == *Current) 160 Current++; 161 return Current != user_end(); 162 } 163 164 void replaceAllUsesWith(VPValue *New); 165 166 /// Returns the recipe defining this VPValue or nullptr if it is not defined 167 /// by a recipe, i.e. is a live-in. 168 VPRecipeBase *getDefiningRecipe(); 169 const VPRecipeBase *getDefiningRecipe() const; 170 171 /// Returns true if this VPValue is defined by a recipe. 172 bool hasDefiningRecipe() const { return getDefiningRecipe(); } 173 174 /// Returns the underlying IR value, if this VPValue is defined outside the 175 /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef 176 /// inside a VPlan. 177 Value *getLiveInIRValue() { 178 assert(!hasDefiningRecipe() && 179 "VPValue is not a live-in; it is defined by a VPDef inside a VPlan"); 180 return getUnderlyingValue(); 181 } 182 const Value *getLiveInIRValue() const { 183 assert(!hasDefiningRecipe() && 184 "VPValue is not a live-in; it is defined by a VPDef inside a VPlan"); 185 return getUnderlyingValue(); 186 } 187 188 /// Returns true if the VPValue is defined outside any vector regions, i.e. it 189 /// is a live-in value. 190 /// TODO: Also handle recipes defined in pre-header blocks. 191 bool isDefinedOutsideVectorRegions() const { return !hasDefiningRecipe(); } 192 }; 193 194 typedef DenseMap<Value *, VPValue *> Value2VPValueTy; 195 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy; 196 197 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V); 198 199 /// This class augments VPValue with operands which provide the inverse def-use 200 /// edges from VPValue's users to their defs. 201 class VPUser { 202 public: 203 /// Subclass identifier (for isa/dyn_cast). 204 enum class VPUserID { 205 Recipe, 206 LiveOut, 207 }; 208 209 private: 210 SmallVector<VPValue *, 2> Operands; 211 212 VPUserID ID; 213 214 protected: 215 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 216 /// Print the operands to \p O. 217 void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const; 218 #endif 219 220 VPUser(ArrayRef<VPValue *> Operands, VPUserID ID) : ID(ID) { 221 for (VPValue *Operand : Operands) 222 addOperand(Operand); 223 } 224 225 VPUser(std::initializer_list<VPValue *> Operands, VPUserID ID) 226 : VPUser(ArrayRef<VPValue *>(Operands), ID) {} 227 228 template <typename IterT> 229 VPUser(iterator_range<IterT> Operands, VPUserID ID) : ID(ID) { 230 for (VPValue *Operand : Operands) 231 addOperand(Operand); 232 } 233 234 public: 235 VPUser() = delete; 236 VPUser(const VPUser &) = delete; 237 VPUser &operator=(const VPUser &) = delete; 238 virtual ~VPUser() { 239 for (VPValue *Op : operands()) 240 Op->removeUser(*this); 241 } 242 243 VPUserID getVPUserID() const { return ID; } 244 245 void addOperand(VPValue *Operand) { 246 Operands.push_back(Operand); 247 Operand->addUser(*this); 248 } 249 250 unsigned getNumOperands() const { return Operands.size(); } 251 inline VPValue *getOperand(unsigned N) const { 252 assert(N < Operands.size() && "Operand index out of bounds"); 253 return Operands[N]; 254 } 255 256 void setOperand(unsigned I, VPValue *New) { 257 Operands[I]->removeUser(*this); 258 Operands[I] = New; 259 New->addUser(*this); 260 } 261 262 void removeLastOperand() { 263 VPValue *Op = Operands.pop_back_val(); 264 Op->removeUser(*this); 265 } 266 267 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator; 268 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator; 269 typedef iterator_range<operand_iterator> operand_range; 270 typedef iterator_range<const_operand_iterator> const_operand_range; 271 272 operand_iterator op_begin() { return Operands.begin(); } 273 const_operand_iterator op_begin() const { return Operands.begin(); } 274 operand_iterator op_end() { return Operands.end(); } 275 const_operand_iterator op_end() const { return Operands.end(); } 276 operand_range operands() { return operand_range(op_begin(), op_end()); } 277 const_operand_range operands() const { 278 return const_operand_range(op_begin(), op_end()); 279 } 280 281 /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively 282 /// returns if only first (scalar) lane is used, as default. 283 virtual bool usesScalars(const VPValue *Op) const { 284 assert(is_contained(operands(), Op) && 285 "Op must be an operand of the recipe"); 286 return onlyFirstLaneUsed(Op); 287 } 288 289 /// Returns true if the VPUser only uses the first lane of operand \p Op. 290 /// Conservatively returns false. 291 virtual bool onlyFirstLaneUsed(const VPValue *Op) const { 292 assert(is_contained(operands(), Op) && 293 "Op must be an operand of the recipe"); 294 return false; 295 } 296 }; 297 298 /// This class augments a recipe with a set of VPValues defined by the recipe. 299 /// It allows recipes to define zero, one or multiple VPValues. A VPDef owns 300 /// the VPValues it defines and is responsible for deleting its defined values. 301 /// Single-value VPDefs that also inherit from VPValue must make sure to inherit 302 /// from VPDef before VPValue. 303 class VPDef { 304 friend class VPValue; 305 306 /// Subclass identifier (for isa/dyn_cast). 307 const unsigned char SubclassID; 308 309 /// The VPValues defined by this VPDef. 310 TinyPtrVector<VPValue *> DefinedValues; 311 312 /// Add \p V as a defined value by this VPDef. 313 void addDefinedValue(VPValue *V) { 314 assert(V->Def == this && 315 "can only add VPValue already linked with this VPDef"); 316 DefinedValues.push_back(V); 317 } 318 319 /// Remove \p V from the values defined by this VPDef. \p V must be a defined 320 /// value of this VPDef. 321 void removeDefinedValue(VPValue *V) { 322 assert(V->Def == this && "can only remove VPValue linked with this VPDef"); 323 assert(is_contained(DefinedValues, V) && 324 "VPValue to remove must be in DefinedValues"); 325 erase_value(DefinedValues, V); 326 V->Def = nullptr; 327 } 328 329 public: 330 /// An enumeration for keeping track of the concrete subclass of VPRecipeBase 331 /// that is actually instantiated. Values of this enumeration are kept in the 332 /// SubclassID field of the VPRecipeBase objects. They are used for concrete 333 /// type identification. 334 using VPRecipeTy = enum { 335 VPBranchOnMaskSC, 336 VPDerivedIVSC, 337 VPExpandSCEVSC, 338 VPInstructionSC, 339 VPInterleaveSC, 340 VPReductionSC, 341 VPReplicateSC, 342 VPScalarIVStepsSC, 343 VPWidenCallSC, 344 VPWidenCanonicalIVSC, 345 VPWidenGEPSC, 346 VPWidenMemoryInstructionSC, 347 VPWidenSC, 348 VPWidenSelectSC, 349 350 // Phi-like recipes. Need to be kept together. 351 VPBlendSC, 352 VPPredInstPHISC, 353 // Header-phi recipes. Need to be kept together. 354 VPCanonicalIVPHISC, 355 VPActiveLaneMaskPHISC, 356 VPFirstOrderRecurrencePHISC, 357 VPWidenPHISC, 358 VPWidenIntOrFpInductionSC, 359 VPWidenPointerInductionSC, 360 VPReductionPHISC, 361 VPFirstPHISC = VPBlendSC, 362 VPFirstHeaderPHISC = VPCanonicalIVPHISC, 363 VPLastPHISC = VPReductionPHISC, 364 }; 365 366 VPDef(const unsigned char SC) : SubclassID(SC) {} 367 368 virtual ~VPDef() { 369 for (VPValue *D : make_early_inc_range(DefinedValues)) { 370 assert(D->Def == this && 371 "all defined VPValues should point to the containing VPDef"); 372 assert(D->getNumUsers() == 0 && 373 "all defined VPValues should have no more users"); 374 D->Def = nullptr; 375 delete D; 376 } 377 } 378 379 /// Returns the only VPValue defined by the VPDef. Can only be called for 380 /// VPDefs with a single defined value. 381 VPValue *getVPSingleValue() { 382 assert(DefinedValues.size() == 1 && "must have exactly one defined value"); 383 assert(DefinedValues[0] && "defined value must be non-null"); 384 return DefinedValues[0]; 385 } 386 const VPValue *getVPSingleValue() const { 387 assert(DefinedValues.size() == 1 && "must have exactly one defined value"); 388 assert(DefinedValues[0] && "defined value must be non-null"); 389 return DefinedValues[0]; 390 } 391 392 /// Returns the VPValue with index \p I defined by the VPDef. 393 VPValue *getVPValue(unsigned I) { 394 assert(DefinedValues[I] && "defined value must be non-null"); 395 return DefinedValues[I]; 396 } 397 const VPValue *getVPValue(unsigned I) const { 398 assert(DefinedValues[I] && "defined value must be non-null"); 399 return DefinedValues[I]; 400 } 401 402 /// Returns an ArrayRef of the values defined by the VPDef. 403 ArrayRef<VPValue *> definedValues() { return DefinedValues; } 404 /// Returns an ArrayRef of the values defined by the VPDef. 405 ArrayRef<VPValue *> definedValues() const { return DefinedValues; } 406 407 /// Returns the number of values defined by the VPDef. 408 unsigned getNumDefinedValues() const { return DefinedValues.size(); } 409 410 /// \return an ID for the concrete type of this object. 411 /// This is used to implement the classof checks. This should not be used 412 /// for any other purpose, as the values may change as LLVM evolves. 413 unsigned getVPDefID() const { return SubclassID; } 414 415 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 416 /// Dump the VPDef to stderr (for debugging). 417 void dump() const; 418 419 /// Each concrete VPDef prints itself. 420 virtual void print(raw_ostream &O, const Twine &Indent, 421 VPSlotTracker &SlotTracker) const = 0; 422 #endif 423 }; 424 425 class VPlan; 426 class VPBasicBlock; 427 428 /// This class can be used to assign consecutive numbers to all VPValues in a 429 /// VPlan and allows querying the numbering for printing, similar to the 430 /// ModuleSlotTracker for IR values. 431 class VPSlotTracker { 432 DenseMap<const VPValue *, unsigned> Slots; 433 unsigned NextSlot = 0; 434 435 void assignSlot(const VPValue *V); 436 void assignSlots(const VPlan &Plan); 437 438 public: 439 VPSlotTracker(const VPlan *Plan = nullptr) { 440 if (Plan) 441 assignSlots(*Plan); 442 } 443 444 unsigned getSlot(const VPValue *V) const { 445 auto I = Slots.find(V); 446 if (I == Slots.end()) 447 return -1; 448 return I->second; 449 } 450 }; 451 452 } // namespace llvm 453 454 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H 455