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 /// Go through the uses list for this VPValue and make each use point to \p 167 /// New if the callback ShouldReplace returns true for the given use specified 168 /// by a pair of (VPUser, the use index). 169 void replaceUsesWithIf( 170 VPValue *New, 171 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace); 172 173 /// Returns the recipe defining this VPValue or nullptr if it is not defined 174 /// by a recipe, i.e. is a live-in. 175 VPRecipeBase *getDefiningRecipe(); 176 const VPRecipeBase *getDefiningRecipe() const; 177 178 /// Returns true if this VPValue is defined by a recipe. 179 bool hasDefiningRecipe() const { return getDefiningRecipe(); } 180 181 /// Returns true if this VPValue is a live-in, i.e. defined outside the VPlan. 182 bool isLiveIn() const { return !hasDefiningRecipe(); } 183 184 /// Returns the underlying IR value, if this VPValue is defined outside the 185 /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef 186 /// inside a VPlan. 187 Value *getLiveInIRValue() { 188 assert(isLiveIn() && 189 "VPValue is not a live-in; it is defined by a VPDef inside a VPlan"); 190 return getUnderlyingValue(); 191 } 192 const Value *getLiveInIRValue() const { 193 assert(isLiveIn() && 194 "VPValue is not a live-in; it is defined by a VPDef inside a VPlan"); 195 return getUnderlyingValue(); 196 } 197 198 /// Returns true if the VPValue is defined outside any vector regions, i.e. it 199 /// is a live-in value. 200 /// TODO: Also handle recipes defined in pre-header blocks. 201 bool isDefinedOutsideVectorRegions() const { return !hasDefiningRecipe(); } 202 }; 203 204 typedef DenseMap<Value *, VPValue *> Value2VPValueTy; 205 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy; 206 207 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V); 208 209 /// This class augments VPValue with operands which provide the inverse def-use 210 /// edges from VPValue's users to their defs. 211 class VPUser { 212 public: 213 /// Subclass identifier (for isa/dyn_cast). 214 enum class VPUserID { 215 Recipe, 216 LiveOut, 217 }; 218 219 private: 220 SmallVector<VPValue *, 2> Operands; 221 222 VPUserID ID; 223 224 protected: 225 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 226 /// Print the operands to \p O. 227 void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const; 228 #endif 229 230 VPUser(ArrayRef<VPValue *> Operands, VPUserID ID) : ID(ID) { 231 for (VPValue *Operand : Operands) 232 addOperand(Operand); 233 } 234 235 VPUser(std::initializer_list<VPValue *> Operands, VPUserID ID) 236 : VPUser(ArrayRef<VPValue *>(Operands), ID) {} 237 238 template <typename IterT> 239 VPUser(iterator_range<IterT> Operands, VPUserID ID) : ID(ID) { 240 for (VPValue *Operand : Operands) 241 addOperand(Operand); 242 } 243 244 public: 245 VPUser() = delete; 246 VPUser(const VPUser &) = delete; 247 VPUser &operator=(const VPUser &) = delete; 248 virtual ~VPUser() { 249 for (VPValue *Op : operands()) 250 Op->removeUser(*this); 251 } 252 253 VPUserID getVPUserID() const { return ID; } 254 255 void addOperand(VPValue *Operand) { 256 Operands.push_back(Operand); 257 Operand->addUser(*this); 258 } 259 260 unsigned getNumOperands() const { return Operands.size(); } 261 inline VPValue *getOperand(unsigned N) const { 262 assert(N < Operands.size() && "Operand index out of bounds"); 263 return Operands[N]; 264 } 265 266 void setOperand(unsigned I, VPValue *New) { 267 Operands[I]->removeUser(*this); 268 Operands[I] = New; 269 New->addUser(*this); 270 } 271 272 void removeLastOperand() { 273 VPValue *Op = Operands.pop_back_val(); 274 Op->removeUser(*this); 275 } 276 277 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator; 278 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator; 279 typedef iterator_range<operand_iterator> operand_range; 280 typedef iterator_range<const_operand_iterator> const_operand_range; 281 282 operand_iterator op_begin() { return Operands.begin(); } 283 const_operand_iterator op_begin() const { return Operands.begin(); } 284 operand_iterator op_end() { return Operands.end(); } 285 const_operand_iterator op_end() const { return Operands.end(); } 286 operand_range operands() { return operand_range(op_begin(), op_end()); } 287 const_operand_range operands() const { 288 return const_operand_range(op_begin(), op_end()); 289 } 290 291 /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively 292 /// returns if only first (scalar) lane is used, as default. 293 virtual bool usesScalars(const VPValue *Op) const { 294 assert(is_contained(operands(), Op) && 295 "Op must be an operand of the recipe"); 296 return onlyFirstLaneUsed(Op); 297 } 298 299 /// Returns true if the VPUser only uses the first lane of operand \p Op. 300 /// Conservatively returns false. 301 virtual bool onlyFirstLaneUsed(const VPValue *Op) const { 302 assert(is_contained(operands(), Op) && 303 "Op must be an operand of the recipe"); 304 return false; 305 } 306 }; 307 308 /// This class augments a recipe with a set of VPValues defined by the recipe. 309 /// It allows recipes to define zero, one or multiple VPValues. A VPDef owns 310 /// the VPValues it defines and is responsible for deleting its defined values. 311 /// Single-value VPDefs that also inherit from VPValue must make sure to inherit 312 /// from VPDef before VPValue. 313 class VPDef { 314 friend class VPValue; 315 316 /// Subclass identifier (for isa/dyn_cast). 317 const unsigned char SubclassID; 318 319 /// The VPValues defined by this VPDef. 320 TinyPtrVector<VPValue *> DefinedValues; 321 322 /// Add \p V as a defined value by this VPDef. 323 void addDefinedValue(VPValue *V) { 324 assert(V->Def == this && 325 "can only add VPValue already linked with this VPDef"); 326 DefinedValues.push_back(V); 327 } 328 329 /// Remove \p V from the values defined by this VPDef. \p V must be a defined 330 /// value of this VPDef. 331 void removeDefinedValue(VPValue *V) { 332 assert(V->Def == this && "can only remove VPValue linked with this VPDef"); 333 assert(is_contained(DefinedValues, V) && 334 "VPValue to remove must be in DefinedValues"); 335 llvm::erase(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 VPDerivedIVSC, 347 VPExpandSCEVSC, 348 VPInstructionSC, 349 VPInterleaveSC, 350 VPReductionSC, 351 VPReplicateSC, 352 VPScalarIVStepsSC, 353 VPWidenCallSC, 354 VPWidenCanonicalIVSC, 355 VPWidenCastSC, 356 VPWidenGEPSC, 357 VPWidenMemoryInstructionSC, 358 VPWidenSC, 359 VPWidenSelectSC, 360 // START: Phi-like recipes. Need to be kept together. 361 VPBlendSC, 362 VPPredInstPHISC, 363 // START: SubclassID for recipes that inherit VPHeaderPHIRecipe. 364 // VPHeaderPHIRecipe need to be kept together. 365 VPCanonicalIVPHISC, 366 VPActiveLaneMaskPHISC, 367 VPFirstOrderRecurrencePHISC, 368 VPWidenPHISC, 369 VPWidenIntOrFpInductionSC, 370 VPWidenPointerInductionSC, 371 VPReductionPHISC, 372 // END: SubclassID for recipes that inherit VPHeaderPHIRecipe 373 // END: Phi-like recipes 374 VPFirstPHISC = VPBlendSC, 375 VPFirstHeaderPHISC = VPCanonicalIVPHISC, 376 VPLastHeaderPHISC = VPReductionPHISC, 377 VPLastPHISC = VPReductionPHISC, 378 }; 379 380 VPDef(const unsigned char SC) : SubclassID(SC) {} 381 382 virtual ~VPDef() { 383 for (VPValue *D : make_early_inc_range(DefinedValues)) { 384 assert(D->Def == this && 385 "all defined VPValues should point to the containing VPDef"); 386 assert(D->getNumUsers() == 0 && 387 "all defined VPValues should have no more users"); 388 D->Def = nullptr; 389 delete D; 390 } 391 } 392 393 /// Returns the only VPValue defined by the VPDef. Can only be called for 394 /// VPDefs with a single defined value. 395 VPValue *getVPSingleValue() { 396 assert(DefinedValues.size() == 1 && "must have exactly one defined value"); 397 assert(DefinedValues[0] && "defined value must be non-null"); 398 return DefinedValues[0]; 399 } 400 const VPValue *getVPSingleValue() const { 401 assert(DefinedValues.size() == 1 && "must have exactly one defined value"); 402 assert(DefinedValues[0] && "defined value must be non-null"); 403 return DefinedValues[0]; 404 } 405 406 /// Returns the VPValue with index \p I defined by the VPDef. 407 VPValue *getVPValue(unsigned I) { 408 assert(DefinedValues[I] && "defined value must be non-null"); 409 return DefinedValues[I]; 410 } 411 const VPValue *getVPValue(unsigned I) const { 412 assert(DefinedValues[I] && "defined value must be non-null"); 413 return DefinedValues[I]; 414 } 415 416 /// Returns an ArrayRef of the values defined by the VPDef. 417 ArrayRef<VPValue *> definedValues() { return DefinedValues; } 418 /// Returns an ArrayRef of the values defined by the VPDef. 419 ArrayRef<VPValue *> definedValues() const { return DefinedValues; } 420 421 /// Returns the number of values defined by the VPDef. 422 unsigned getNumDefinedValues() const { return DefinedValues.size(); } 423 424 /// \return an ID for the concrete type of this object. 425 /// This is used to implement the classof checks. This should not be used 426 /// for any other purpose, as the values may change as LLVM evolves. 427 unsigned getVPDefID() const { return SubclassID; } 428 429 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 430 /// Dump the VPDef to stderr (for debugging). 431 void dump() const; 432 433 /// Each concrete VPDef prints itself. 434 virtual void print(raw_ostream &O, const Twine &Indent, 435 VPSlotTracker &SlotTracker) const = 0; 436 #endif 437 }; 438 439 class VPlan; 440 class VPBasicBlock; 441 442 /// This class can be used to assign consecutive numbers to all VPValues in a 443 /// VPlan and allows querying the numbering for printing, similar to the 444 /// ModuleSlotTracker for IR values. 445 class VPSlotTracker { 446 DenseMap<const VPValue *, unsigned> Slots; 447 unsigned NextSlot = 0; 448 449 void assignSlot(const VPValue *V); 450 void assignSlots(const VPlan &Plan); 451 void assignSlots(const VPBasicBlock *VPBB); 452 453 public: 454 VPSlotTracker(const VPlan *Plan = nullptr) { 455 if (Plan) 456 assignSlots(*Plan); 457 } 458 459 unsigned getSlot(const VPValue *V) const { 460 auto I = Slots.find(V); 461 if (I == Slots.end()) 462 return -1; 463 return I->second; 464 } 465 }; 466 467 } // namespace llvm 468 469 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H 470