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. Values of this enumeration are kept in the 89 /// SubclassID field of the VPValue objects. They are used for concrete 90 /// type identification. 91 enum { 92 VPValueSC, 93 VPVInstructionSC, 94 VPVMemoryInstructionSC, 95 VPVReductionSC, 96 VPVReplicateSC, 97 VPVWidenSC, 98 VPVWidenCallSC, 99 VPVWidenCanonicalIVSC, 100 VPVWidenGEPSC, 101 VPVWidenSelectSC, 102 103 // Phi-like VPValues. Need to be kept together. 104 VPVBlendSC, 105 VPVCanonicalIVPHISC, 106 VPVActiveLaneMaskPHISC, 107 VPVFirstOrderRecurrencePHISC, 108 VPVWidenPHISC, 109 VPVWidenIntOrFpInductionSC, 110 VPVWidenPointerInductionSC, 111 VPVPredInstPHI, 112 VPVReductionPHISC, 113 }; 114 115 VPValue(Value *UV = nullptr, VPDef *Def = nullptr) 116 : VPValue(VPValueSC, UV, Def) {} 117 VPValue(const VPValue &) = delete; 118 VPValue &operator=(const VPValue &) = delete; 119 120 virtual ~VPValue(); 121 122 /// \return an ID for the concrete type of this object. 123 /// This is used to implement the classof checks. This should not be used 124 /// for any other purpose, as the values may change as LLVM evolves. 125 unsigned getVPValueID() const { return SubclassID; } 126 127 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 128 void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const; 129 void print(raw_ostream &OS, VPSlotTracker &Tracker) const; 130 131 /// Dump the value to stderr (for debugging). 132 void dump() const; 133 #endif 134 135 unsigned getNumUsers() const { return Users.size(); } 136 void addUser(VPUser &User) { Users.push_back(&User); } 137 138 /// Remove a single \p User from the list of users. 139 void removeUser(VPUser &User) { 140 bool Found = false; 141 // The same user can be added multiple times, e.g. because the same VPValue 142 // is used twice by the same VPUser. Remove a single one. 143 erase_if(Users, [&User, &Found](VPUser *Other) { 144 if (Found) 145 return false; 146 if (Other == &User) { 147 Found = true; 148 return true; 149 } 150 return false; 151 }); 152 } 153 154 typedef SmallVectorImpl<VPUser *>::iterator user_iterator; 155 typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator; 156 typedef iterator_range<user_iterator> user_range; 157 typedef iterator_range<const_user_iterator> const_user_range; 158 159 user_iterator user_begin() { return Users.begin(); } 160 const_user_iterator user_begin() const { return Users.begin(); } 161 user_iterator user_end() { return Users.end(); } 162 const_user_iterator user_end() const { return Users.end(); } 163 user_range users() { return user_range(user_begin(), user_end()); } 164 const_user_range users() const { 165 return const_user_range(user_begin(), user_end()); 166 } 167 168 /// Returns true if the value has more than one unique user. 169 bool hasMoreThanOneUniqueUser() { 170 if (getNumUsers() == 0) 171 return false; 172 173 // Check if all users match the first user. 174 auto Current = std::next(user_begin()); 175 while (Current != user_end() && *user_begin() == *Current) 176 Current++; 177 return Current != user_end(); 178 } 179 180 void replaceAllUsesWith(VPValue *New); 181 182 VPDef *getDef() { return Def; } 183 const VPDef *getDef() const { return Def; } 184 185 /// Returns the underlying IR value, if this VPValue is defined outside the 186 /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef 187 /// inside a VPlan. 188 Value *getLiveInIRValue() { 189 assert(!getDef() && 190 "VPValue is not a live-in; it is defined by a VPDef inside a VPlan"); 191 return getUnderlyingValue(); 192 } 193 const Value *getLiveInIRValue() const { 194 assert(!getDef() && 195 "VPValue is not a live-in; it is defined by a VPDef inside a VPlan"); 196 return getUnderlyingValue(); 197 } 198 }; 199 200 typedef DenseMap<Value *, VPValue *> Value2VPValueTy; 201 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy; 202 203 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V); 204 205 /// This class augments VPValue with operands which provide the inverse def-use 206 /// edges from VPValue's users to their defs. 207 class VPUser { 208 public: 209 /// Subclass identifier (for isa/dyn_cast). 210 enum class VPUserID { 211 Recipe, 212 LiveOut, 213 }; 214 215 private: 216 SmallVector<VPValue *, 2> Operands; 217 218 VPUserID ID; 219 220 protected: 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 #endif 225 226 VPUser(ArrayRef<VPValue *> Operands, VPUserID ID) : ID(ID) { 227 for (VPValue *Operand : Operands) 228 addOperand(Operand); 229 } 230 231 VPUser(std::initializer_list<VPValue *> Operands, VPUserID ID) 232 : VPUser(ArrayRef<VPValue *>(Operands), ID) {} 233 234 template <typename IterT> 235 VPUser(iterator_range<IterT> Operands, VPUserID ID) : ID(ID) { 236 for (VPValue *Operand : Operands) 237 addOperand(Operand); 238 } 239 240 public: 241 VPUser() = delete; 242 VPUser(const VPUser &) = delete; 243 VPUser &operator=(const VPUser &) = delete; 244 virtual ~VPUser() { 245 for (VPValue *Op : operands()) 246 Op->removeUser(*this); 247 } 248 249 VPUserID getVPUserID() const { return ID; } 250 251 void addOperand(VPValue *Operand) { 252 Operands.push_back(Operand); 253 Operand->addUser(*this); 254 } 255 256 unsigned getNumOperands() const { return Operands.size(); } 257 inline VPValue *getOperand(unsigned N) const { 258 assert(N < Operands.size() && "Operand index out of bounds"); 259 return Operands[N]; 260 } 261 262 void setOperand(unsigned I, VPValue *New) { 263 Operands[I]->removeUser(*this); 264 Operands[I] = New; 265 New->addUser(*this); 266 } 267 268 void removeLastOperand() { 269 VPValue *Op = Operands.pop_back_val(); 270 Op->removeUser(*this); 271 } 272 273 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator; 274 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator; 275 typedef iterator_range<operand_iterator> operand_range; 276 typedef iterator_range<const_operand_iterator> const_operand_range; 277 278 operand_iterator op_begin() { return Operands.begin(); } 279 const_operand_iterator op_begin() const { return Operands.begin(); } 280 operand_iterator op_end() { return Operands.end(); } 281 const_operand_iterator op_end() const { return Operands.end(); } 282 operand_range operands() { return operand_range(op_begin(), op_end()); } 283 const_operand_range operands() const { 284 return const_operand_range(op_begin(), op_end()); 285 } 286 287 /// Method to support type inquiry through isa, cast, and dyn_cast. 288 static inline bool classof(const VPDef *Recipe); 289 290 /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively 291 /// returns if only first (scalar) lane is used, as default. 292 virtual bool usesScalars(const VPValue *Op) const { 293 assert(is_contained(operands(), Op) && 294 "Op must be an operand of the recipe"); 295 return onlyFirstLaneUsed(Op); 296 } 297 298 /// Returns true if the VPUser only uses the first lane of operand \p Op. 299 /// Conservatively returns false. 300 virtual bool onlyFirstLaneUsed(const VPValue *Op) const { 301 assert(is_contained(operands(), Op) && 302 "Op must be an operand of the recipe"); 303 return false; 304 } 305 }; 306 307 /// This class augments a recipe with a set of VPValues defined by the recipe. 308 /// It allows recipes to define zero, one or multiple VPValues. A VPDef owns 309 /// the VPValues it defines and is responsible for deleting its defined values. 310 /// Single-value VPDefs that also inherit from VPValue must make sure to inherit 311 /// from VPDef before VPValue. 312 class VPDef { 313 friend class VPValue; 314 315 /// Subclass identifier (for isa/dyn_cast). 316 const unsigned char SubclassID; 317 318 /// The VPValues defined by this VPDef. 319 TinyPtrVector<VPValue *> DefinedValues; 320 321 /// Add \p V as a defined value by this VPDef. 322 void addDefinedValue(VPValue *V) { 323 assert(V->getDef() == this && 324 "can only add VPValue already linked with this VPDef"); 325 DefinedValues.push_back(V); 326 } 327 328 /// Remove \p V from the values defined by this VPDef. \p V must be a defined 329 /// value of this VPDef. 330 void removeDefinedValue(VPValue *V) { 331 assert(V->getDef() == this && 332 "can only remove VPValue linked with this VPDef"); 333 assert(is_contained(DefinedValues, V) && 334 "VPValue to remove must be in DefinedValues"); 335 erase_value(DefinedValues, V); 336 V->Def = nullptr; 337 } 338 339 public: 340 /// An enumeration for keeping track of the concrete subclass of VPRecipeBase 341 /// that is actually instantiated. Values of this enumeration are kept in the 342 /// SubclassID field of the VPRecipeBase objects. They are used for concrete 343 /// type identification. 344 using VPRecipeTy = enum { 345 VPBranchOnMaskSC, 346 VPExpandSCEVSC, 347 VPInstructionSC, 348 VPInterleaveSC, 349 VPReductionSC, 350 VPReplicateSC, 351 VPScalarIVStepsSC, 352 VPWidenCallSC, 353 VPWidenCanonicalIVSC, 354 VPWidenGEPSC, 355 VPWidenMemoryInstructionSC, 356 VPWidenSC, 357 VPWidenSelectSC, 358 359 // Phi-like recipes. Need to be kept together. 360 VPBlendSC, 361 VPCanonicalIVPHISC, 362 VPActiveLaneMaskPHISC, 363 VPFirstOrderRecurrencePHISC, 364 VPWidenPHISC, 365 VPWidenIntOrFpInductionSC, 366 VPWidenPointerInductionSC, 367 VPPredInstPHISC, 368 VPReductionPHISC, 369 VPFirstPHISC = VPBlendSC, 370 VPLastPHISC = VPReductionPHISC, 371 }; 372 373 VPDef(const unsigned char SC) : SubclassID(SC) {} 374 375 virtual ~VPDef() { 376 for (VPValue *D : make_early_inc_range(DefinedValues)) { 377 assert(D->Def == this && 378 "all defined VPValues should point to the containing VPDef"); 379 assert(D->getNumUsers() == 0 && 380 "all defined VPValues should have no more users"); 381 D->Def = nullptr; 382 delete D; 383 } 384 } 385 386 /// Returns the only VPValue defined by the VPDef. Can only be called for 387 /// VPDefs with a single defined value. 388 VPValue *getVPSingleValue() { 389 assert(DefinedValues.size() == 1 && "must have exactly one defined value"); 390 assert(DefinedValues[0] && "defined value must be non-null"); 391 return DefinedValues[0]; 392 } 393 const VPValue *getVPSingleValue() const { 394 assert(DefinedValues.size() == 1 && "must have exactly one defined value"); 395 assert(DefinedValues[0] && "defined value must be non-null"); 396 return DefinedValues[0]; 397 } 398 399 /// Returns the VPValue with index \p I defined by the VPDef. 400 VPValue *getVPValue(unsigned I) { 401 assert(DefinedValues[I] && "defined value must be non-null"); 402 return DefinedValues[I]; 403 } 404 const VPValue *getVPValue(unsigned I) const { 405 assert(DefinedValues[I] && "defined value must be non-null"); 406 return DefinedValues[I]; 407 } 408 409 /// Returns an ArrayRef of the values defined by the VPDef. 410 ArrayRef<VPValue *> definedValues() { return DefinedValues; } 411 /// Returns an ArrayRef of the values defined by the VPDef. 412 ArrayRef<VPValue *> definedValues() const { return DefinedValues; } 413 414 /// Returns the number of values defined by the VPDef. 415 unsigned getNumDefinedValues() const { return DefinedValues.size(); } 416 417 /// \return an ID for the concrete type of this object. 418 /// This is used to implement the classof checks. This should not be used 419 /// for any other purpose, as the values may change as LLVM evolves. 420 unsigned getVPDefID() const { return SubclassID; } 421 422 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 423 /// Dump the VPDef to stderr (for debugging). 424 void dump() const; 425 426 /// Each concrete VPDef prints itself. 427 virtual void print(raw_ostream &O, const Twine &Indent, 428 VPSlotTracker &SlotTracker) const = 0; 429 #endif 430 }; 431 432 class VPlan; 433 class VPBasicBlock; 434 435 /// This class can be used to assign consecutive numbers to all VPValues in a 436 /// VPlan and allows querying the numbering for printing, similar to the 437 /// ModuleSlotTracker for IR values. 438 class VPSlotTracker { 439 DenseMap<const VPValue *, unsigned> Slots; 440 unsigned NextSlot = 0; 441 442 void assignSlot(const VPValue *V); 443 void assignSlots(const VPlan &Plan); 444 445 public: 446 VPSlotTracker(const VPlan *Plan = nullptr) { 447 if (Plan) 448 assignSlots(*Plan); 449 } 450 451 unsigned getSlot(const VPValue *V) const { 452 auto I = Slots.find(V); 453 if (I == Slots.end()) 454 return -1; 455 return I->second; 456 } 457 }; 458 459 } // namespace llvm 460 461 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H 462