1 //===- VPlan.h - Represent A Vectorizer Plan --------------------*- C++ -*-===// 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 Vectorization Plan base classes: 11 /// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual 12 /// VPBlockBase, together implementing a Hierarchical CFG; 13 /// 2. Specializations of GraphTraits that allow VPBlockBase graphs to be 14 /// treated as proper graphs for generic algorithms; 15 /// 3. Pure virtual VPRecipeBase serving as the base class for recipes contained 16 /// within VPBasicBlocks; 17 /// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned 18 /// instruction; 19 /// 5. The VPlan class holding a candidate for vectorization; 20 /// 6. The VPlanPrinter class providing a way to print a plan in dot format; 21 /// These are documented in docs/VectorizationPlan.rst. 22 // 23 //===----------------------------------------------------------------------===// 24 25 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H 26 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H 27 28 #include "VPlanLoopInfo.h" 29 #include "VPlanValue.h" 30 #include "llvm/ADT/DenseMap.h" 31 #include "llvm/ADT/DepthFirstIterator.h" 32 #include "llvm/ADT/GraphTraits.h" 33 #include "llvm/ADT/Optional.h" 34 #include "llvm/ADT/SmallBitVector.h" 35 #include "llvm/ADT/SmallPtrSet.h" 36 #include "llvm/ADT/SmallSet.h" 37 #include "llvm/ADT/SmallVector.h" 38 #include "llvm/ADT/Twine.h" 39 #include "llvm/ADT/ilist.h" 40 #include "llvm/ADT/ilist_node.h" 41 #include "llvm/Analysis/VectorUtils.h" 42 #include "llvm/IR/IRBuilder.h" 43 #include <algorithm> 44 #include <cassert> 45 #include <cstddef> 46 #include <map> 47 #include <string> 48 49 namespace llvm { 50 51 class BasicBlock; 52 class DominatorTree; 53 class InnerLoopVectorizer; 54 template <class T> class InterleaveGroup; 55 class LoopInfo; 56 class raw_ostream; 57 class RecurrenceDescriptor; 58 class Value; 59 class VPBasicBlock; 60 class VPRegionBlock; 61 class VPSlotTracker; 62 class VPlan; 63 class VPlanSlp; 64 65 /// A range of powers-of-2 vectorization factors with fixed start and 66 /// adjustable end. The range includes start and excludes end, e.g.,: 67 /// [1, 9) = {1, 2, 4, 8} 68 struct VFRange { 69 // A power of 2. 70 const unsigned Start; 71 72 // Need not be a power of 2. If End <= Start range is empty. 73 unsigned End; 74 }; 75 76 using VPlanPtr = std::unique_ptr<VPlan>; 77 78 /// In what follows, the term "input IR" refers to code that is fed into the 79 /// vectorizer whereas the term "output IR" refers to code that is generated by 80 /// the vectorizer. 81 82 /// VPIteration represents a single point in the iteration space of the output 83 /// (vectorized and/or unrolled) IR loop. 84 struct VPIteration { 85 /// in [0..UF) 86 unsigned Part; 87 88 /// in [0..VF) 89 unsigned Lane; 90 }; 91 92 /// This is a helper struct for maintaining vectorization state. It's used for 93 /// mapping values from the original loop to their corresponding values in 94 /// the new loop. Two mappings are maintained: one for vectorized values and 95 /// one for scalarized values. Vectorized values are represented with UF 96 /// vector values in the new loop, and scalarized values are represented with 97 /// UF x VF scalar values in the new loop. UF and VF are the unroll and 98 /// vectorization factors, respectively. 99 /// 100 /// Entries can be added to either map with setVectorValue and setScalarValue, 101 /// which assert that an entry was not already added before. If an entry is to 102 /// replace an existing one, call resetVectorValue and resetScalarValue. This is 103 /// currently needed to modify the mapped values during "fix-up" operations that 104 /// occur once the first phase of widening is complete. These operations include 105 /// type truncation and the second phase of recurrence widening. 106 /// 107 /// Entries from either map can be retrieved using the getVectorValue and 108 /// getScalarValue functions, which assert that the desired value exists. 109 struct VectorizerValueMap { 110 friend struct VPTransformState; 111 112 private: 113 /// The unroll factor. Each entry in the vector map contains UF vector values. 114 unsigned UF; 115 116 /// The vectorization factor. Each entry in the scalar map contains UF x VF 117 /// scalar values. 118 ElementCount VF; 119 120 /// The vector and scalar map storage. We use std::map and not DenseMap 121 /// because insertions to DenseMap invalidate its iterators. 122 using VectorParts = SmallVector<Value *, 2>; 123 using ScalarParts = SmallVector<SmallVector<Value *, 4>, 2>; 124 std::map<Value *, VectorParts> VectorMapStorage; 125 std::map<Value *, ScalarParts> ScalarMapStorage; 126 127 public: 128 /// Construct an empty map with the given unroll and vectorization factors. 129 VectorizerValueMap(unsigned UF, ElementCount VF) : UF(UF), VF(VF) {} 130 131 /// \return True if the map has any vector entry for \p Key. 132 bool hasAnyVectorValue(Value *Key) const { 133 return VectorMapStorage.count(Key); 134 } 135 136 /// \return True if the map has a vector entry for \p Key and \p Part. 137 bool hasVectorValue(Value *Key, unsigned Part) const { 138 assert(Part < UF && "Queried Vector Part is too large."); 139 if (!hasAnyVectorValue(Key)) 140 return false; 141 const VectorParts &Entry = VectorMapStorage.find(Key)->second; 142 assert(Entry.size() == UF && "VectorParts has wrong dimensions."); 143 return Entry[Part] != nullptr; 144 } 145 146 /// \return True if the map has any scalar entry for \p Key. 147 bool hasAnyScalarValue(Value *Key) const { 148 return ScalarMapStorage.count(Key); 149 } 150 151 /// \return True if the map has a scalar entry for \p Key and \p Instance. 152 bool hasScalarValue(Value *Key, const VPIteration &Instance) const { 153 assert(Instance.Part < UF && "Queried Scalar Part is too large."); 154 assert(Instance.Lane < VF.Min && "Queried Scalar Lane is too large."); 155 assert(!VF.Scalable && "VF is assumed to be non scalable."); 156 157 if (!hasAnyScalarValue(Key)) 158 return false; 159 const ScalarParts &Entry = ScalarMapStorage.find(Key)->second; 160 assert(Entry.size() == UF && "ScalarParts has wrong dimensions."); 161 assert(Entry[Instance.Part].size() == VF.Min && 162 "ScalarParts has wrong dimensions."); 163 return Entry[Instance.Part][Instance.Lane] != nullptr; 164 } 165 166 /// Retrieve the existing vector value that corresponds to \p Key and 167 /// \p Part. 168 Value *getVectorValue(Value *Key, unsigned Part) { 169 assert(hasVectorValue(Key, Part) && "Getting non-existent value."); 170 return VectorMapStorage[Key][Part]; 171 } 172 173 /// Retrieve the existing scalar value that corresponds to \p Key and 174 /// \p Instance. 175 Value *getScalarValue(Value *Key, const VPIteration &Instance) { 176 assert(hasScalarValue(Key, Instance) && "Getting non-existent value."); 177 return ScalarMapStorage[Key][Instance.Part][Instance.Lane]; 178 } 179 180 /// Set a vector value associated with \p Key and \p Part. Assumes such a 181 /// value is not already set. If it is, use resetVectorValue() instead. 182 void setVectorValue(Value *Key, unsigned Part, Value *Vector) { 183 assert(!hasVectorValue(Key, Part) && "Vector value already set for part"); 184 if (!VectorMapStorage.count(Key)) { 185 VectorParts Entry(UF); 186 VectorMapStorage[Key] = Entry; 187 } 188 VectorMapStorage[Key][Part] = Vector; 189 } 190 191 /// Set a scalar value associated with \p Key and \p Instance. Assumes such a 192 /// value is not already set. 193 void setScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar) { 194 assert(!hasScalarValue(Key, Instance) && "Scalar value already set"); 195 if (!ScalarMapStorage.count(Key)) { 196 ScalarParts Entry(UF); 197 // TODO: Consider storing uniform values only per-part, as they occupy 198 // lane 0 only, keeping the other VF-1 redundant entries null. 199 for (unsigned Part = 0; Part < UF; ++Part) 200 Entry[Part].resize(VF.Min, nullptr); 201 ScalarMapStorage[Key] = Entry; 202 } 203 ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar; 204 } 205 206 /// Reset the vector value associated with \p Key for the given \p Part. 207 /// This function can be used to update values that have already been 208 /// vectorized. This is the case for "fix-up" operations including type 209 /// truncation and the second phase of recurrence vectorization. 210 void resetVectorValue(Value *Key, unsigned Part, Value *Vector) { 211 assert(hasVectorValue(Key, Part) && "Vector value not set for part"); 212 VectorMapStorage[Key][Part] = Vector; 213 } 214 215 /// Reset the scalar value associated with \p Key for \p Part and \p Lane. 216 /// This function can be used to update values that have already been 217 /// scalarized. This is the case for "fix-up" operations including scalar phi 218 /// nodes for scalarized and predicated instructions. 219 void resetScalarValue(Value *Key, const VPIteration &Instance, 220 Value *Scalar) { 221 assert(hasScalarValue(Key, Instance) && 222 "Scalar value not set for part and lane"); 223 ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar; 224 } 225 }; 226 227 /// This class is used to enable the VPlan to invoke a method of ILV. This is 228 /// needed until the method is refactored out of ILV and becomes reusable. 229 struct VPCallback { 230 virtual ~VPCallback() {} 231 virtual Value *getOrCreateVectorValues(Value *V, unsigned Part) = 0; 232 virtual Value *getOrCreateScalarValue(Value *V, 233 const VPIteration &Instance) = 0; 234 }; 235 236 /// VPTransformState holds information passed down when "executing" a VPlan, 237 /// needed for generating the output IR. 238 struct VPTransformState { 239 VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, 240 DominatorTree *DT, IRBuilder<> &Builder, 241 VectorizerValueMap &ValueMap, InnerLoopVectorizer *ILV, 242 VPCallback &Callback) 243 : VF(VF), UF(UF), Instance(), LI(LI), DT(DT), Builder(Builder), 244 ValueMap(ValueMap), ILV(ILV), Callback(Callback) {} 245 246 /// The chosen Vectorization and Unroll Factors of the loop being vectorized. 247 ElementCount VF; 248 unsigned UF; 249 250 /// Hold the indices to generate specific scalar instructions. Null indicates 251 /// that all instances are to be generated, using either scalar or vector 252 /// instructions. 253 Optional<VPIteration> Instance; 254 255 struct DataState { 256 /// A type for vectorized values in the new loop. Each value from the 257 /// original loop, when vectorized, is represented by UF vector values in 258 /// the new unrolled loop, where UF is the unroll factor. 259 typedef SmallVector<Value *, 2> PerPartValuesTy; 260 261 DenseMap<VPValue *, PerPartValuesTy> PerPartOutput; 262 } Data; 263 264 /// Get the generated Value for a given VPValue and a given Part. Note that 265 /// as some Defs are still created by ILV and managed in its ValueMap, this 266 /// method will delegate the call to ILV in such cases in order to provide 267 /// callers a consistent API. 268 /// \see set. 269 Value *get(VPValue *Def, unsigned Part) { 270 // If Values have been set for this Def return the one relevant for \p Part. 271 if (Data.PerPartOutput.count(Def)) 272 return Data.PerPartOutput[Def][Part]; 273 // Def is managed by ILV: bring the Values from ValueMap. 274 return Callback.getOrCreateVectorValues(VPValue2Value[Def], Part); 275 } 276 277 /// Get the generated Value for a given VPValue and given Part and Lane. 278 Value *get(VPValue *Def, const VPIteration &Instance) { 279 // If the Def is managed directly by VPTransformState, extract the lane from 280 // the relevant part. Note that currently only VPInstructions and external 281 // defs are managed by VPTransformState. Other Defs are still created by ILV 282 // and managed in its ValueMap. For those this method currently just 283 // delegates the call to ILV below. 284 if (Data.PerPartOutput.count(Def)) { 285 auto *VecPart = Data.PerPartOutput[Def][Instance.Part]; 286 // TODO: Cache created scalar values. 287 return Builder.CreateExtractElement(VecPart, 288 Builder.getInt32(Instance.Lane)); 289 } 290 291 return Callback.getOrCreateScalarValue(VPValue2Value[Def], Instance); 292 } 293 294 /// Set the generated Value for a given VPValue and a given Part. 295 void set(VPValue *Def, Value *V, unsigned Part) { 296 if (!Data.PerPartOutput.count(Def)) { 297 DataState::PerPartValuesTy Entry(UF); 298 Data.PerPartOutput[Def] = Entry; 299 } 300 Data.PerPartOutput[Def][Part] = V; 301 } 302 303 /// Hold state information used when constructing the CFG of the output IR, 304 /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks. 305 struct CFGState { 306 /// The previous VPBasicBlock visited. Initially set to null. 307 VPBasicBlock *PrevVPBB = nullptr; 308 309 /// The previous IR BasicBlock created or used. Initially set to the new 310 /// header BasicBlock. 311 BasicBlock *PrevBB = nullptr; 312 313 /// The last IR BasicBlock in the output IR. Set to the new latch 314 /// BasicBlock, used for placing the newly created BasicBlocks. 315 BasicBlock *LastBB = nullptr; 316 317 /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case 318 /// of replication, maps the BasicBlock of the last replica created. 319 SmallDenseMap<VPBasicBlock *, BasicBlock *> VPBB2IRBB; 320 321 /// Vector of VPBasicBlocks whose terminator instruction needs to be fixed 322 /// up at the end of vector code generation. 323 SmallVector<VPBasicBlock *, 8> VPBBsToFix; 324 325 CFGState() = default; 326 } CFG; 327 328 /// Hold a pointer to LoopInfo to register new basic blocks in the loop. 329 LoopInfo *LI; 330 331 /// Hold a pointer to Dominator Tree to register new basic blocks in the loop. 332 DominatorTree *DT; 333 334 /// Hold a reference to the IRBuilder used to generate output IR code. 335 IRBuilder<> &Builder; 336 337 /// Hold a reference to the Value state information used when generating the 338 /// Values of the output IR. 339 VectorizerValueMap &ValueMap; 340 341 /// Hold a reference to a mapping between VPValues in VPlan and original 342 /// Values they correspond to. 343 VPValue2ValueTy VPValue2Value; 344 345 /// Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF). 346 Value *CanonicalIV = nullptr; 347 348 /// Hold the trip count of the scalar loop. 349 Value *TripCount = nullptr; 350 351 /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods. 352 InnerLoopVectorizer *ILV; 353 354 VPCallback &Callback; 355 }; 356 357 /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph. 358 /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock. 359 class VPBlockBase { 360 friend class VPBlockUtils; 361 362 const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast). 363 364 /// An optional name for the block. 365 std::string Name; 366 367 /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if 368 /// it is a topmost VPBlockBase. 369 VPRegionBlock *Parent = nullptr; 370 371 /// List of predecessor blocks. 372 SmallVector<VPBlockBase *, 1> Predecessors; 373 374 /// List of successor blocks. 375 SmallVector<VPBlockBase *, 1> Successors; 376 377 /// Successor selector, null for zero or single successor blocks. 378 VPValue *CondBit = nullptr; 379 380 /// Current block predicate - null if the block does not need a predicate. 381 VPValue *Predicate = nullptr; 382 383 /// VPlan containing the block. Can only be set on the entry block of the 384 /// plan. 385 VPlan *Plan = nullptr; 386 387 /// Add \p Successor as the last successor to this block. 388 void appendSuccessor(VPBlockBase *Successor) { 389 assert(Successor && "Cannot add nullptr successor!"); 390 Successors.push_back(Successor); 391 } 392 393 /// Add \p Predecessor as the last predecessor to this block. 394 void appendPredecessor(VPBlockBase *Predecessor) { 395 assert(Predecessor && "Cannot add nullptr predecessor!"); 396 Predecessors.push_back(Predecessor); 397 } 398 399 /// Remove \p Predecessor from the predecessors of this block. 400 void removePredecessor(VPBlockBase *Predecessor) { 401 auto Pos = std::find(Predecessors.begin(), Predecessors.end(), Predecessor); 402 assert(Pos && "Predecessor does not exist"); 403 Predecessors.erase(Pos); 404 } 405 406 /// Remove \p Successor from the successors of this block. 407 void removeSuccessor(VPBlockBase *Successor) { 408 auto Pos = std::find(Successors.begin(), Successors.end(), Successor); 409 assert(Pos && "Successor does not exist"); 410 Successors.erase(Pos); 411 } 412 413 protected: 414 VPBlockBase(const unsigned char SC, const std::string &N) 415 : SubclassID(SC), Name(N) {} 416 417 public: 418 /// An enumeration for keeping track of the concrete subclass of VPBlockBase 419 /// that are actually instantiated. Values of this enumeration are kept in the 420 /// SubclassID field of the VPBlockBase objects. They are used for concrete 421 /// type identification. 422 using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC }; 423 424 using VPBlocksTy = SmallVectorImpl<VPBlockBase *>; 425 426 virtual ~VPBlockBase() = default; 427 428 const std::string &getName() const { return Name; } 429 430 void setName(const Twine &newName) { Name = newName.str(); } 431 432 /// \return an ID for the concrete type of this object. 433 /// This is used to implement the classof checks. This should not be used 434 /// for any other purpose, as the values may change as LLVM evolves. 435 unsigned getVPBlockID() const { return SubclassID; } 436 437 VPRegionBlock *getParent() { return Parent; } 438 const VPRegionBlock *getParent() const { return Parent; } 439 440 /// \return A pointer to the plan containing the current block. 441 VPlan *getPlan(); 442 const VPlan *getPlan() const; 443 444 /// Sets the pointer of the plan containing the block. The block must be the 445 /// entry block into the VPlan. 446 void setPlan(VPlan *ParentPlan); 447 448 void setParent(VPRegionBlock *P) { Parent = P; } 449 450 /// \return the VPBasicBlock that is the entry of this VPBlockBase, 451 /// recursively, if the latter is a VPRegionBlock. Otherwise, if this 452 /// VPBlockBase is a VPBasicBlock, it is returned. 453 const VPBasicBlock *getEntryBasicBlock() const; 454 VPBasicBlock *getEntryBasicBlock(); 455 456 /// \return the VPBasicBlock that is the exit of this VPBlockBase, 457 /// recursively, if the latter is a VPRegionBlock. Otherwise, if this 458 /// VPBlockBase is a VPBasicBlock, it is returned. 459 const VPBasicBlock *getExitBasicBlock() const; 460 VPBasicBlock *getExitBasicBlock(); 461 462 const VPBlocksTy &getSuccessors() const { return Successors; } 463 VPBlocksTy &getSuccessors() { return Successors; } 464 465 const VPBlocksTy &getPredecessors() const { return Predecessors; } 466 VPBlocksTy &getPredecessors() { return Predecessors; } 467 468 /// \return the successor of this VPBlockBase if it has a single successor. 469 /// Otherwise return a null pointer. 470 VPBlockBase *getSingleSuccessor() const { 471 return (Successors.size() == 1 ? *Successors.begin() : nullptr); 472 } 473 474 /// \return the predecessor of this VPBlockBase if it has a single 475 /// predecessor. Otherwise return a null pointer. 476 VPBlockBase *getSinglePredecessor() const { 477 return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr); 478 } 479 480 size_t getNumSuccessors() const { return Successors.size(); } 481 size_t getNumPredecessors() const { return Predecessors.size(); } 482 483 /// An Enclosing Block of a block B is any block containing B, including B 484 /// itself. \return the closest enclosing block starting from "this", which 485 /// has successors. \return the root enclosing block if all enclosing blocks 486 /// have no successors. 487 VPBlockBase *getEnclosingBlockWithSuccessors(); 488 489 /// \return the closest enclosing block starting from "this", which has 490 /// predecessors. \return the root enclosing block if all enclosing blocks 491 /// have no predecessors. 492 VPBlockBase *getEnclosingBlockWithPredecessors(); 493 494 /// \return the successors either attached directly to this VPBlockBase or, if 495 /// this VPBlockBase is the exit block of a VPRegionBlock and has no 496 /// successors of its own, search recursively for the first enclosing 497 /// VPRegionBlock that has successors and return them. If no such 498 /// VPRegionBlock exists, return the (empty) successors of the topmost 499 /// VPBlockBase reached. 500 const VPBlocksTy &getHierarchicalSuccessors() { 501 return getEnclosingBlockWithSuccessors()->getSuccessors(); 502 } 503 504 /// \return the hierarchical successor of this VPBlockBase if it has a single 505 /// hierarchical successor. Otherwise return a null pointer. 506 VPBlockBase *getSingleHierarchicalSuccessor() { 507 return getEnclosingBlockWithSuccessors()->getSingleSuccessor(); 508 } 509 510 /// \return the predecessors either attached directly to this VPBlockBase or, 511 /// if this VPBlockBase is the entry block of a VPRegionBlock and has no 512 /// predecessors of its own, search recursively for the first enclosing 513 /// VPRegionBlock that has predecessors and return them. If no such 514 /// VPRegionBlock exists, return the (empty) predecessors of the topmost 515 /// VPBlockBase reached. 516 const VPBlocksTy &getHierarchicalPredecessors() { 517 return getEnclosingBlockWithPredecessors()->getPredecessors(); 518 } 519 520 /// \return the hierarchical predecessor of this VPBlockBase if it has a 521 /// single hierarchical predecessor. Otherwise return a null pointer. 522 VPBlockBase *getSingleHierarchicalPredecessor() { 523 return getEnclosingBlockWithPredecessors()->getSinglePredecessor(); 524 } 525 526 /// \return the condition bit selecting the successor. 527 VPValue *getCondBit() { return CondBit; } 528 529 const VPValue *getCondBit() const { return CondBit; } 530 531 void setCondBit(VPValue *CV) { CondBit = CV; } 532 533 VPValue *getPredicate() { return Predicate; } 534 535 const VPValue *getPredicate() const { return Predicate; } 536 537 void setPredicate(VPValue *Pred) { Predicate = Pred; } 538 539 /// Set a given VPBlockBase \p Successor as the single successor of this 540 /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor. 541 /// This VPBlockBase must have no successors. 542 void setOneSuccessor(VPBlockBase *Successor) { 543 assert(Successors.empty() && "Setting one successor when others exist."); 544 appendSuccessor(Successor); 545 } 546 547 /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two 548 /// successors of this VPBlockBase. \p Condition is set as the successor 549 /// selector. This VPBlockBase is not added as predecessor of \p IfTrue or \p 550 /// IfFalse. This VPBlockBase must have no successors. 551 void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse, 552 VPValue *Condition) { 553 assert(Successors.empty() && "Setting two successors when others exist."); 554 assert(Condition && "Setting two successors without condition!"); 555 CondBit = Condition; 556 appendSuccessor(IfTrue); 557 appendSuccessor(IfFalse); 558 } 559 560 /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase. 561 /// This VPBlockBase must have no predecessors. This VPBlockBase is not added 562 /// as successor of any VPBasicBlock in \p NewPreds. 563 void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) { 564 assert(Predecessors.empty() && "Block predecessors already set."); 565 for (auto *Pred : NewPreds) 566 appendPredecessor(Pred); 567 } 568 569 /// Remove all the predecessor of this block. 570 void clearPredecessors() { Predecessors.clear(); } 571 572 /// Remove all the successors of this block and set to null its condition bit 573 void clearSuccessors() { 574 Successors.clear(); 575 CondBit = nullptr; 576 } 577 578 /// The method which generates the output IR that correspond to this 579 /// VPBlockBase, thereby "executing" the VPlan. 580 virtual void execute(struct VPTransformState *State) = 0; 581 582 /// Delete all blocks reachable from a given VPBlockBase, inclusive. 583 static void deleteCFG(VPBlockBase *Entry); 584 585 void printAsOperand(raw_ostream &OS, bool PrintType) const { 586 OS << getName(); 587 } 588 589 void print(raw_ostream &OS) const { 590 // TODO: Only printing VPBB name for now since we only have dot printing 591 // support for VPInstructions/Recipes. 592 printAsOperand(OS, false); 593 } 594 595 /// Return true if it is legal to hoist instructions into this block. 596 bool isLegalToHoistInto() { 597 // There are currently no constraints that prevent an instruction to be 598 // hoisted into a VPBlockBase. 599 return true; 600 } 601 }; 602 603 /// VPRecipeBase is a base class modeling a sequence of one or more output IR 604 /// instructions. 605 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> { 606 friend VPBasicBlock; 607 friend class VPBlockUtils; 608 609 const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast). 610 611 /// Each VPRecipe belongs to a single VPBasicBlock. 612 VPBasicBlock *Parent = nullptr; 613 614 public: 615 /// An enumeration for keeping track of the concrete subclass of VPRecipeBase 616 /// that is actually instantiated. Values of this enumeration are kept in the 617 /// SubclassID field of the VPRecipeBase objects. They are used for concrete 618 /// type identification. 619 using VPRecipeTy = enum { 620 VPBlendSC, 621 VPBranchOnMaskSC, 622 VPInstructionSC, 623 VPInterleaveSC, 624 VPPredInstPHISC, 625 VPReductionSC, 626 VPReplicateSC, 627 VPWidenCallSC, 628 VPWidenCanonicalIVSC, 629 VPWidenGEPSC, 630 VPWidenIntOrFpInductionSC, 631 VPWidenMemoryInstructionSC, 632 VPWidenPHISC, 633 VPWidenSC, 634 VPWidenSelectSC 635 }; 636 637 VPRecipeBase(const unsigned char SC) : SubclassID(SC) {} 638 virtual ~VPRecipeBase() = default; 639 640 /// \return an ID for the concrete type of this object. 641 /// This is used to implement the classof checks. This should not be used 642 /// for any other purpose, as the values may change as LLVM evolves. 643 unsigned getVPRecipeID() const { return SubclassID; } 644 645 /// \return the VPBasicBlock which this VPRecipe belongs to. 646 VPBasicBlock *getParent() { return Parent; } 647 const VPBasicBlock *getParent() const { return Parent; } 648 649 /// The method which generates the output IR instructions that correspond to 650 /// this VPRecipe, thereby "executing" the VPlan. 651 virtual void execute(struct VPTransformState &State) = 0; 652 653 /// Each recipe prints itself. 654 virtual void print(raw_ostream &O, const Twine &Indent, 655 VPSlotTracker &SlotTracker) const = 0; 656 657 /// Insert an unlinked recipe into a basic block immediately before 658 /// the specified recipe. 659 void insertBefore(VPRecipeBase *InsertPos); 660 661 /// Insert an unlinked Recipe into a basic block immediately after 662 /// the specified Recipe. 663 void insertAfter(VPRecipeBase *InsertPos); 664 665 /// Unlink this recipe from its current VPBasicBlock and insert it into 666 /// the VPBasicBlock that MovePos lives in, right after MovePos. 667 void moveAfter(VPRecipeBase *MovePos); 668 669 /// This method unlinks 'this' from the containing basic block, but does not 670 /// delete it. 671 void removeFromParent(); 672 673 /// This method unlinks 'this' from the containing basic block and deletes it. 674 /// 675 /// \returns an iterator pointing to the element after the erased one 676 iplist<VPRecipeBase>::iterator eraseFromParent(); 677 }; 678 679 /// This is a concrete Recipe that models a single VPlan-level instruction. 680 /// While as any Recipe it may generate a sequence of IR instructions when 681 /// executed, these instructions would always form a single-def expression as 682 /// the VPInstruction is also a single def-use vertex. 683 class VPInstruction : public VPUser, public VPRecipeBase { 684 friend class VPlanSlp; 685 686 public: 687 /// VPlan opcodes, extending LLVM IR with idiomatics instructions. 688 enum { 689 Not = Instruction::OtherOpsEnd + 1, 690 ICmpULE, 691 SLPLoad, 692 SLPStore, 693 ActiveLaneMask, 694 }; 695 696 private: 697 typedef unsigned char OpcodeTy; 698 OpcodeTy Opcode; 699 700 /// Utility method serving execute(): generates a single instance of the 701 /// modeled instruction. 702 void generateInstruction(VPTransformState &State, unsigned Part); 703 704 protected: 705 Instruction *getUnderlyingInstr() { 706 return cast_or_null<Instruction>(getUnderlyingValue()); 707 } 708 709 void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); } 710 711 public: 712 VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands) 713 : VPUser(VPValue::VPInstructionSC, Operands), 714 VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {} 715 716 VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands) 717 : VPInstruction(Opcode, ArrayRef<VPValue *>(Operands)) {} 718 719 /// Method to support type inquiry through isa, cast, and dyn_cast. 720 static inline bool classof(const VPValue *V) { 721 return V->getVPValueID() == VPValue::VPInstructionSC; 722 } 723 724 VPInstruction *clone() const { 725 SmallVector<VPValue *, 2> Operands(operands()); 726 return new VPInstruction(Opcode, Operands); 727 } 728 729 /// Method to support type inquiry through isa, cast, and dyn_cast. 730 static inline bool classof(const VPRecipeBase *R) { 731 return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC; 732 } 733 734 unsigned getOpcode() const { return Opcode; } 735 736 /// Generate the instruction. 737 /// TODO: We currently execute only per-part unless a specific instance is 738 /// provided. 739 void execute(VPTransformState &State) override; 740 741 /// Print the Recipe. 742 void print(raw_ostream &O, const Twine &Indent, 743 VPSlotTracker &SlotTracker) const override; 744 745 /// Print the VPInstruction. 746 void print(raw_ostream &O) const; 747 void print(raw_ostream &O, VPSlotTracker &SlotTracker) const; 748 749 /// Return true if this instruction may modify memory. 750 bool mayWriteToMemory() const { 751 // TODO: we can use attributes of the called function to rule out memory 752 // modifications. 753 return Opcode == Instruction::Store || Opcode == Instruction::Call || 754 Opcode == Instruction::Invoke || Opcode == SLPStore; 755 } 756 757 bool hasResult() const { 758 // CallInst may or may not have a result, depending on the called function. 759 // Conservatively return calls have results for now. 760 switch (getOpcode()) { 761 case Instruction::Ret: 762 case Instruction::Br: 763 case Instruction::Store: 764 case Instruction::Switch: 765 case Instruction::IndirectBr: 766 case Instruction::Resume: 767 case Instruction::CatchRet: 768 case Instruction::Unreachable: 769 case Instruction::Fence: 770 case Instruction::AtomicRMW: 771 return false; 772 default: 773 return true; 774 } 775 } 776 }; 777 778 /// VPWidenRecipe is a recipe for producing a copy of vector type its 779 /// ingredient. This recipe covers most of the traditional vectorization cases 780 /// where each ingredient transforms into a vectorized version of itself. 781 class VPWidenRecipe : public VPRecipeBase { 782 /// Hold the instruction to be widened. 783 Instruction &Ingredient; 784 785 /// Hold VPValues for the operands of the ingredient. 786 VPUser User; 787 788 public: 789 template <typename IterT> 790 VPWidenRecipe(Instruction &I, iterator_range<IterT> Operands) 791 : VPRecipeBase(VPWidenSC), Ingredient(I), User(Operands) {} 792 793 ~VPWidenRecipe() override = default; 794 795 /// Method to support type inquiry through isa, cast, and dyn_cast. 796 static inline bool classof(const VPRecipeBase *V) { 797 return V->getVPRecipeID() == VPRecipeBase::VPWidenSC; 798 } 799 800 /// Produce widened copies of all Ingredients. 801 void execute(VPTransformState &State) override; 802 803 /// Print the recipe. 804 void print(raw_ostream &O, const Twine &Indent, 805 VPSlotTracker &SlotTracker) const override; 806 }; 807 808 /// A recipe for widening Call instructions. 809 class VPWidenCallRecipe : public VPRecipeBase { 810 /// Hold the call to be widened. 811 CallInst &Ingredient; 812 813 /// Hold VPValues for the arguments of the call. 814 VPUser User; 815 816 public: 817 template <typename IterT> 818 VPWidenCallRecipe(CallInst &I, iterator_range<IterT> CallArguments) 819 : VPRecipeBase(VPWidenCallSC), Ingredient(I), User(CallArguments) {} 820 821 ~VPWidenCallRecipe() override = default; 822 823 /// Method to support type inquiry through isa, cast, and dyn_cast. 824 static inline bool classof(const VPRecipeBase *V) { 825 return V->getVPRecipeID() == VPRecipeBase::VPWidenCallSC; 826 } 827 828 /// Produce a widened version of the call instruction. 829 void execute(VPTransformState &State) override; 830 831 /// Print the recipe. 832 void print(raw_ostream &O, const Twine &Indent, 833 VPSlotTracker &SlotTracker) const override; 834 }; 835 836 /// A recipe for widening select instructions. 837 class VPWidenSelectRecipe : public VPRecipeBase { 838 private: 839 /// Hold the select to be widened. 840 SelectInst &Ingredient; 841 842 /// Hold VPValues for the operands of the select. 843 VPUser User; 844 845 /// Is the condition of the select loop invariant? 846 bool InvariantCond; 847 848 public: 849 template <typename IterT> 850 VPWidenSelectRecipe(SelectInst &I, iterator_range<IterT> Operands, 851 bool InvariantCond) 852 : VPRecipeBase(VPWidenSelectSC), Ingredient(I), User(Operands), 853 InvariantCond(InvariantCond) {} 854 855 ~VPWidenSelectRecipe() override = default; 856 857 /// Method to support type inquiry through isa, cast, and dyn_cast. 858 static inline bool classof(const VPRecipeBase *V) { 859 return V->getVPRecipeID() == VPRecipeBase::VPWidenSelectSC; 860 } 861 862 /// Produce a widened version of the select instruction. 863 void execute(VPTransformState &State) override; 864 865 /// Print the recipe. 866 void print(raw_ostream &O, const Twine &Indent, 867 VPSlotTracker &SlotTracker) const override; 868 }; 869 870 /// A recipe for handling GEP instructions. 871 class VPWidenGEPRecipe : public VPRecipeBase { 872 GetElementPtrInst *GEP; 873 874 /// Hold VPValues for the base and indices of the GEP. 875 VPUser User; 876 877 bool IsPtrLoopInvariant; 878 SmallBitVector IsIndexLoopInvariant; 879 880 public: 881 template <typename IterT> 882 VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands, 883 Loop *OrigLoop) 884 : VPRecipeBase(VPWidenGEPSC), GEP(GEP), User(Operands), 885 IsIndexLoopInvariant(GEP->getNumIndices(), false) { 886 IsPtrLoopInvariant = OrigLoop->isLoopInvariant(GEP->getPointerOperand()); 887 for (auto Index : enumerate(GEP->indices())) 888 IsIndexLoopInvariant[Index.index()] = 889 OrigLoop->isLoopInvariant(Index.value().get()); 890 } 891 ~VPWidenGEPRecipe() override = default; 892 893 /// Method to support type inquiry through isa, cast, and dyn_cast. 894 static inline bool classof(const VPRecipeBase *V) { 895 return V->getVPRecipeID() == VPRecipeBase::VPWidenGEPSC; 896 } 897 898 /// Generate the gep nodes. 899 void execute(VPTransformState &State) override; 900 901 /// Print the recipe. 902 void print(raw_ostream &O, const Twine &Indent, 903 VPSlotTracker &SlotTracker) const override; 904 }; 905 906 /// A recipe for handling phi nodes of integer and floating-point inductions, 907 /// producing their vector and scalar values. 908 class VPWidenIntOrFpInductionRecipe : public VPRecipeBase { 909 PHINode *IV; 910 TruncInst *Trunc; 911 912 public: 913 VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc = nullptr) 914 : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {} 915 ~VPWidenIntOrFpInductionRecipe() override = default; 916 917 /// Method to support type inquiry through isa, cast, and dyn_cast. 918 static inline bool classof(const VPRecipeBase *V) { 919 return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC; 920 } 921 922 /// Generate the vectorized and scalarized versions of the phi node as 923 /// needed by their users. 924 void execute(VPTransformState &State) override; 925 926 /// Print the recipe. 927 void print(raw_ostream &O, const Twine &Indent, 928 VPSlotTracker &SlotTracker) const override; 929 }; 930 931 /// A recipe for handling all phi nodes except for integer and FP inductions. 932 class VPWidenPHIRecipe : public VPRecipeBase { 933 PHINode *Phi; 934 935 public: 936 VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {} 937 ~VPWidenPHIRecipe() override = default; 938 939 /// Method to support type inquiry through isa, cast, and dyn_cast. 940 static inline bool classof(const VPRecipeBase *V) { 941 return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC; 942 } 943 944 /// Generate the phi/select nodes. 945 void execute(VPTransformState &State) override; 946 947 /// Print the recipe. 948 void print(raw_ostream &O, const Twine &Indent, 949 VPSlotTracker &SlotTracker) const override; 950 }; 951 952 /// A recipe for vectorizing a phi-node as a sequence of mask-based select 953 /// instructions. 954 class VPBlendRecipe : public VPRecipeBase { 955 PHINode *Phi; 956 957 /// The blend operation is a User of the incoming values and of their 958 /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value 959 /// might be incoming with a full mask for which there is no VPValue. 960 VPUser User; 961 962 public: 963 VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands) 964 : VPRecipeBase(VPBlendSC), Phi(Phi), User(Operands) { 965 assert(Operands.size() > 0 && 966 ((Operands.size() == 1) || (Operands.size() % 2 == 0)) && 967 "Expected either a single incoming value or a positive even number " 968 "of operands"); 969 } 970 971 /// Method to support type inquiry through isa, cast, and dyn_cast. 972 static inline bool classof(const VPRecipeBase *V) { 973 return V->getVPRecipeID() == VPRecipeBase::VPBlendSC; 974 } 975 976 /// Return the number of incoming values, taking into account that a single 977 /// incoming value has no mask. 978 unsigned getNumIncomingValues() const { 979 return (User.getNumOperands() + 1) / 2; 980 } 981 982 /// Return incoming value number \p Idx. 983 VPValue *getIncomingValue(unsigned Idx) const { 984 return User.getOperand(Idx * 2); 985 } 986 987 /// Return mask number \p Idx. 988 VPValue *getMask(unsigned Idx) const { return User.getOperand(Idx * 2 + 1); } 989 990 /// Generate the phi/select nodes. 991 void execute(VPTransformState &State) override; 992 993 /// Print the recipe. 994 void print(raw_ostream &O, const Twine &Indent, 995 VPSlotTracker &SlotTracker) const override; 996 }; 997 998 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load 999 /// or stores into one wide load/store and shuffles. 1000 class VPInterleaveRecipe : public VPRecipeBase { 1001 const InterleaveGroup<Instruction> *IG; 1002 VPUser User; 1003 1004 public: 1005 VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr, 1006 VPValue *Mask) 1007 : VPRecipeBase(VPInterleaveSC), IG(IG), User({Addr}) { 1008 if (Mask) 1009 User.addOperand(Mask); 1010 } 1011 ~VPInterleaveRecipe() override = default; 1012 1013 /// Method to support type inquiry through isa, cast, and dyn_cast. 1014 static inline bool classof(const VPRecipeBase *V) { 1015 return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC; 1016 } 1017 1018 /// Return the address accessed by this recipe. 1019 VPValue *getAddr() const { 1020 return User.getOperand(0); // Address is the 1st, mandatory operand. 1021 } 1022 1023 /// Return the mask used by this recipe. Note that a full mask is represented 1024 /// by a nullptr. 1025 VPValue *getMask() const { 1026 // Mask is optional and therefore the last, currently 2nd operand. 1027 return User.getNumOperands() == 2 ? User.getOperand(1) : nullptr; 1028 } 1029 1030 /// Generate the wide load or store, and shuffles. 1031 void execute(VPTransformState &State) override; 1032 1033 /// Print the recipe. 1034 void print(raw_ostream &O, const Twine &Indent, 1035 VPSlotTracker &SlotTracker) const override; 1036 1037 const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; } 1038 }; 1039 1040 /// A recipe to represent inloop reduction operations, performing a reduction on 1041 /// a vector operand into a scalar value, and adding the result to a chain. 1042 class VPReductionRecipe : public VPRecipeBase { 1043 /// The recurrence decriptor for the reduction in question. 1044 RecurrenceDescriptor *RdxDesc; 1045 /// The original instruction being converted to a reduction. 1046 Instruction *I; 1047 /// The VPValue of the vector value to be reduced. 1048 VPValue *VecOp; 1049 /// The VPValue of the scalar Chain being accumulated. 1050 VPValue *ChainOp; 1051 /// Fast math flags to use for the resulting reduction operation. 1052 bool NoNaN; 1053 /// Pointer to the TTI, needed to create the target reduction 1054 const TargetTransformInfo *TTI; 1055 1056 public: 1057 VPReductionRecipe(RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp, 1058 VPValue *VecOp, bool NoNaN, const TargetTransformInfo *TTI) 1059 : VPRecipeBase(VPReductionSC), RdxDesc(R), I(I), VecOp(VecOp), 1060 ChainOp(ChainOp), NoNaN(NoNaN), TTI(TTI) {} 1061 1062 ~VPReductionRecipe() override = default; 1063 1064 /// Method to support type inquiry through isa, cast, and dyn_cast. 1065 static inline bool classof(const VPRecipeBase *V) { 1066 return V->getVPRecipeID() == VPRecipeBase::VPReductionSC; 1067 } 1068 1069 /// Generate the reduction in the loop 1070 void execute(VPTransformState &State) override; 1071 1072 /// Print the recipe. 1073 void print(raw_ostream &O, const Twine &Indent, 1074 VPSlotTracker &SlotTracker) const override; 1075 }; 1076 1077 /// VPReplicateRecipe replicates a given instruction producing multiple scalar 1078 /// copies of the original scalar type, one per lane, instead of producing a 1079 /// single copy of widened type for all lanes. If the instruction is known to be 1080 /// uniform only one copy, per lane zero, will be generated. 1081 class VPReplicateRecipe : public VPRecipeBase { 1082 /// The instruction being replicated. 1083 Instruction *Ingredient; 1084 1085 /// Hold VPValues for the operands of the ingredient. 1086 VPUser User; 1087 1088 /// Indicator if only a single replica per lane is needed. 1089 bool IsUniform; 1090 1091 /// Indicator if the replicas are also predicated. 1092 bool IsPredicated; 1093 1094 /// Indicator if the scalar values should also be packed into a vector. 1095 bool AlsoPack; 1096 1097 public: 1098 template <typename IterT> 1099 VPReplicateRecipe(Instruction *I, iterator_range<IterT> Operands, 1100 bool IsUniform, bool IsPredicated = false) 1101 : VPRecipeBase(VPReplicateSC), Ingredient(I), User(Operands), 1102 IsUniform(IsUniform), IsPredicated(IsPredicated) { 1103 // Retain the previous behavior of predicateInstructions(), where an 1104 // insert-element of a predicated instruction got hoisted into the 1105 // predicated basic block iff it was its only user. This is achieved by 1106 // having predicated instructions also pack their values into a vector by 1107 // default unless they have a replicated user which uses their scalar value. 1108 AlsoPack = IsPredicated && !I->use_empty(); 1109 } 1110 1111 ~VPReplicateRecipe() override = default; 1112 1113 /// Method to support type inquiry through isa, cast, and dyn_cast. 1114 static inline bool classof(const VPRecipeBase *V) { 1115 return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC; 1116 } 1117 1118 /// Generate replicas of the desired Ingredient. Replicas will be generated 1119 /// for all parts and lanes unless a specific part and lane are specified in 1120 /// the \p State. 1121 void execute(VPTransformState &State) override; 1122 1123 void setAlsoPack(bool Pack) { AlsoPack = Pack; } 1124 1125 /// Print the recipe. 1126 void print(raw_ostream &O, const Twine &Indent, 1127 VPSlotTracker &SlotTracker) const override; 1128 }; 1129 1130 /// A recipe for generating conditional branches on the bits of a mask. 1131 class VPBranchOnMaskRecipe : public VPRecipeBase { 1132 VPUser User; 1133 1134 public: 1135 VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) { 1136 if (BlockInMask) // nullptr means all-one mask. 1137 User.addOperand(BlockInMask); 1138 } 1139 1140 /// Method to support type inquiry through isa, cast, and dyn_cast. 1141 static inline bool classof(const VPRecipeBase *V) { 1142 return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC; 1143 } 1144 1145 /// Generate the extraction of the appropriate bit from the block mask and the 1146 /// conditional branch. 1147 void execute(VPTransformState &State) override; 1148 1149 /// Print the recipe. 1150 void print(raw_ostream &O, const Twine &Indent, 1151 VPSlotTracker &SlotTracker) const override { 1152 O << " +\n" << Indent << "\"BRANCH-ON-MASK "; 1153 if (VPValue *Mask = getMask()) 1154 Mask->print(O, SlotTracker); 1155 else 1156 O << " All-One"; 1157 O << "\\l\""; 1158 } 1159 1160 /// Return the mask used by this recipe. Note that a full mask is represented 1161 /// by a nullptr. 1162 VPValue *getMask() const { 1163 assert(User.getNumOperands() <= 1 && "should have either 0 or 1 operands"); 1164 // Mask is optional. 1165 return User.getNumOperands() == 1 ? User.getOperand(0) : nullptr; 1166 } 1167 }; 1168 1169 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when 1170 /// control converges back from a Branch-on-Mask. The phi nodes are needed in 1171 /// order to merge values that are set under such a branch and feed their uses. 1172 /// The phi nodes can be scalar or vector depending on the users of the value. 1173 /// This recipe works in concert with VPBranchOnMaskRecipe. 1174 class VPPredInstPHIRecipe : public VPRecipeBase { 1175 Instruction *PredInst; 1176 1177 public: 1178 /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi 1179 /// nodes after merging back from a Branch-on-Mask. 1180 VPPredInstPHIRecipe(Instruction *PredInst) 1181 : VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {} 1182 ~VPPredInstPHIRecipe() override = default; 1183 1184 /// Method to support type inquiry through isa, cast, and dyn_cast. 1185 static inline bool classof(const VPRecipeBase *V) { 1186 return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC; 1187 } 1188 1189 /// Generates phi nodes for live-outs as needed to retain SSA form. 1190 void execute(VPTransformState &State) override; 1191 1192 /// Print the recipe. 1193 void print(raw_ostream &O, const Twine &Indent, 1194 VPSlotTracker &SlotTracker) const override; 1195 }; 1196 1197 /// A Recipe for widening load/store operations. 1198 /// The recipe uses the following VPValues: 1199 /// - For load: Address, optional mask 1200 /// - For store: Address, stored value, optional mask 1201 /// TODO: We currently execute only per-part unless a specific instance is 1202 /// provided. 1203 class VPWidenMemoryInstructionRecipe : public VPRecipeBase { 1204 Instruction &Instr; 1205 VPUser User; 1206 1207 void setMask(VPValue *Mask) { 1208 if (!Mask) 1209 return; 1210 User.addOperand(Mask); 1211 } 1212 1213 bool isMasked() const { 1214 return (isa<LoadInst>(Instr) && User.getNumOperands() == 2) || 1215 (isa<StoreInst>(Instr) && User.getNumOperands() == 3); 1216 } 1217 1218 public: 1219 VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask) 1220 : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Load), User({Addr}) { 1221 setMask(Mask); 1222 } 1223 1224 VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr, 1225 VPValue *StoredValue, VPValue *Mask) 1226 : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Store), 1227 User({Addr, StoredValue}) { 1228 setMask(Mask); 1229 } 1230 1231 /// Method to support type inquiry through isa, cast, and dyn_cast. 1232 static inline bool classof(const VPRecipeBase *V) { 1233 return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC; 1234 } 1235 1236 /// Return the address accessed by this recipe. 1237 VPValue *getAddr() const { 1238 return User.getOperand(0); // Address is the 1st, mandatory operand. 1239 } 1240 1241 /// Return the mask used by this recipe. Note that a full mask is represented 1242 /// by a nullptr. 1243 VPValue *getMask() const { 1244 // Mask is optional and therefore the last operand. 1245 return isMasked() ? User.getOperand(User.getNumOperands() - 1) : nullptr; 1246 } 1247 1248 /// Return the address accessed by this recipe. 1249 VPValue *getStoredValue() const { 1250 assert(isa<StoreInst>(Instr) && 1251 "Stored value only available for store instructions"); 1252 return User.getOperand(1); // Stored value is the 2nd, mandatory operand. 1253 } 1254 1255 /// Generate the wide load/store. 1256 void execute(VPTransformState &State) override; 1257 1258 /// Print the recipe. 1259 void print(raw_ostream &O, const Twine &Indent, 1260 VPSlotTracker &SlotTracker) const override; 1261 }; 1262 1263 /// A Recipe for widening the canonical induction variable of the vector loop. 1264 class VPWidenCanonicalIVRecipe : public VPRecipeBase { 1265 /// A VPValue representing the canonical vector IV. 1266 VPValue Val; 1267 1268 public: 1269 VPWidenCanonicalIVRecipe() : VPRecipeBase(VPWidenCanonicalIVSC) {} 1270 ~VPWidenCanonicalIVRecipe() override = default; 1271 1272 /// Return the VPValue representing the canonical vector induction variable of 1273 /// the vector loop. 1274 const VPValue *getVPValue() const { return &Val; } 1275 VPValue *getVPValue() { return &Val; } 1276 1277 /// Method to support type inquiry through isa, cast, and dyn_cast. 1278 static inline bool classof(const VPRecipeBase *V) { 1279 return V->getVPRecipeID() == VPRecipeBase::VPWidenCanonicalIVSC; 1280 } 1281 1282 /// Generate a canonical vector induction variable of the vector loop, with 1283 /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and 1284 /// step = <VF*UF, VF*UF, ..., VF*UF>. 1285 void execute(VPTransformState &State) override; 1286 1287 /// Print the recipe. 1288 void print(raw_ostream &O, const Twine &Indent, 1289 VPSlotTracker &SlotTracker) const override; 1290 }; 1291 1292 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It 1293 /// holds a sequence of zero or more VPRecipe's each representing a sequence of 1294 /// output IR instructions. 1295 class VPBasicBlock : public VPBlockBase { 1296 public: 1297 using RecipeListTy = iplist<VPRecipeBase>; 1298 1299 private: 1300 /// The VPRecipes held in the order of output instructions to generate. 1301 RecipeListTy Recipes; 1302 1303 public: 1304 VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr) 1305 : VPBlockBase(VPBasicBlockSC, Name.str()) { 1306 if (Recipe) 1307 appendRecipe(Recipe); 1308 } 1309 1310 ~VPBasicBlock() override { Recipes.clear(); } 1311 1312 /// Instruction iterators... 1313 using iterator = RecipeListTy::iterator; 1314 using const_iterator = RecipeListTy::const_iterator; 1315 using reverse_iterator = RecipeListTy::reverse_iterator; 1316 using const_reverse_iterator = RecipeListTy::const_reverse_iterator; 1317 1318 //===--------------------------------------------------------------------===// 1319 /// Recipe iterator methods 1320 /// 1321 inline iterator begin() { return Recipes.begin(); } 1322 inline const_iterator begin() const { return Recipes.begin(); } 1323 inline iterator end() { return Recipes.end(); } 1324 inline const_iterator end() const { return Recipes.end(); } 1325 1326 inline reverse_iterator rbegin() { return Recipes.rbegin(); } 1327 inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); } 1328 inline reverse_iterator rend() { return Recipes.rend(); } 1329 inline const_reverse_iterator rend() const { return Recipes.rend(); } 1330 1331 inline size_t size() const { return Recipes.size(); } 1332 inline bool empty() const { return Recipes.empty(); } 1333 inline const VPRecipeBase &front() const { return Recipes.front(); } 1334 inline VPRecipeBase &front() { return Recipes.front(); } 1335 inline const VPRecipeBase &back() const { return Recipes.back(); } 1336 inline VPRecipeBase &back() { return Recipes.back(); } 1337 1338 /// Returns a reference to the list of recipes. 1339 RecipeListTy &getRecipeList() { return Recipes; } 1340 1341 /// Returns a pointer to a member of the recipe list. 1342 static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) { 1343 return &VPBasicBlock::Recipes; 1344 } 1345 1346 /// Method to support type inquiry through isa, cast, and dyn_cast. 1347 static inline bool classof(const VPBlockBase *V) { 1348 return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC; 1349 } 1350 1351 void insert(VPRecipeBase *Recipe, iterator InsertPt) { 1352 assert(Recipe && "No recipe to append."); 1353 assert(!Recipe->Parent && "Recipe already in VPlan"); 1354 Recipe->Parent = this; 1355 Recipes.insert(InsertPt, Recipe); 1356 } 1357 1358 /// Augment the existing recipes of a VPBasicBlock with an additional 1359 /// \p Recipe as the last recipe. 1360 void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); } 1361 1362 /// The method which generates the output IR instructions that correspond to 1363 /// this VPBasicBlock, thereby "executing" the VPlan. 1364 void execute(struct VPTransformState *State) override; 1365 1366 private: 1367 /// Create an IR BasicBlock to hold the output instructions generated by this 1368 /// VPBasicBlock, and return it. Update the CFGState accordingly. 1369 BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG); 1370 }; 1371 1372 /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks 1373 /// which form a Single-Entry-Single-Exit subgraph of the output IR CFG. 1374 /// A VPRegionBlock may indicate that its contents are to be replicated several 1375 /// times. This is designed to support predicated scalarization, in which a 1376 /// scalar if-then code structure needs to be generated VF * UF times. Having 1377 /// this replication indicator helps to keep a single model for multiple 1378 /// candidate VF's. The actual replication takes place only once the desired VF 1379 /// and UF have been determined. 1380 class VPRegionBlock : public VPBlockBase { 1381 /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock. 1382 VPBlockBase *Entry; 1383 1384 /// Hold the Single Exit of the SESE region modelled by the VPRegionBlock. 1385 VPBlockBase *Exit; 1386 1387 /// An indicator whether this region is to generate multiple replicated 1388 /// instances of output IR corresponding to its VPBlockBases. 1389 bool IsReplicator; 1390 1391 public: 1392 VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exit, 1393 const std::string &Name = "", bool IsReplicator = false) 1394 : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exit(Exit), 1395 IsReplicator(IsReplicator) { 1396 assert(Entry->getPredecessors().empty() && "Entry block has predecessors."); 1397 assert(Exit->getSuccessors().empty() && "Exit block has successors."); 1398 Entry->setParent(this); 1399 Exit->setParent(this); 1400 } 1401 VPRegionBlock(const std::string &Name = "", bool IsReplicator = false) 1402 : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exit(nullptr), 1403 IsReplicator(IsReplicator) {} 1404 1405 ~VPRegionBlock() override { 1406 if (Entry) 1407 deleteCFG(Entry); 1408 } 1409 1410 /// Method to support type inquiry through isa, cast, and dyn_cast. 1411 static inline bool classof(const VPBlockBase *V) { 1412 return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC; 1413 } 1414 1415 const VPBlockBase *getEntry() const { return Entry; } 1416 VPBlockBase *getEntry() { return Entry; } 1417 1418 /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p 1419 /// EntryBlock must have no predecessors. 1420 void setEntry(VPBlockBase *EntryBlock) { 1421 assert(EntryBlock->getPredecessors().empty() && 1422 "Entry block cannot have predecessors."); 1423 Entry = EntryBlock; 1424 EntryBlock->setParent(this); 1425 } 1426 1427 // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a 1428 // specific interface of llvm::Function, instead of using 1429 // GraphTraints::getEntryNode. We should add a new template parameter to 1430 // DominatorTreeBase representing the Graph type. 1431 VPBlockBase &front() const { return *Entry; } 1432 1433 const VPBlockBase *getExit() const { return Exit; } 1434 VPBlockBase *getExit() { return Exit; } 1435 1436 /// Set \p ExitBlock as the exit VPBlockBase of this VPRegionBlock. \p 1437 /// ExitBlock must have no successors. 1438 void setExit(VPBlockBase *ExitBlock) { 1439 assert(ExitBlock->getSuccessors().empty() && 1440 "Exit block cannot have successors."); 1441 Exit = ExitBlock; 1442 ExitBlock->setParent(this); 1443 } 1444 1445 /// An indicator whether this region is to generate multiple replicated 1446 /// instances of output IR corresponding to its VPBlockBases. 1447 bool isReplicator() const { return IsReplicator; } 1448 1449 /// The method which generates the output IR instructions that correspond to 1450 /// this VPRegionBlock, thereby "executing" the VPlan. 1451 void execute(struct VPTransformState *State) override; 1452 }; 1453 1454 //===----------------------------------------------------------------------===// 1455 // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs // 1456 //===----------------------------------------------------------------------===// 1457 1458 // The following set of template specializations implement GraphTraits to treat 1459 // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note 1460 // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the 1461 // VPBlockBase is a VPRegionBlock, this specialization provides access to its 1462 // successors/predecessors but not to the blocks inside the region. 1463 1464 template <> struct GraphTraits<VPBlockBase *> { 1465 using NodeRef = VPBlockBase *; 1466 using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator; 1467 1468 static NodeRef getEntryNode(NodeRef N) { return N; } 1469 1470 static inline ChildIteratorType child_begin(NodeRef N) { 1471 return N->getSuccessors().begin(); 1472 } 1473 1474 static inline ChildIteratorType child_end(NodeRef N) { 1475 return N->getSuccessors().end(); 1476 } 1477 }; 1478 1479 template <> struct GraphTraits<const VPBlockBase *> { 1480 using NodeRef = const VPBlockBase *; 1481 using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator; 1482 1483 static NodeRef getEntryNode(NodeRef N) { return N; } 1484 1485 static inline ChildIteratorType child_begin(NodeRef N) { 1486 return N->getSuccessors().begin(); 1487 } 1488 1489 static inline ChildIteratorType child_end(NodeRef N) { 1490 return N->getSuccessors().end(); 1491 } 1492 }; 1493 1494 // Inverse order specialization for VPBasicBlocks. Predecessors are used instead 1495 // of successors for the inverse traversal. 1496 template <> struct GraphTraits<Inverse<VPBlockBase *>> { 1497 using NodeRef = VPBlockBase *; 1498 using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator; 1499 1500 static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; } 1501 1502 static inline ChildIteratorType child_begin(NodeRef N) { 1503 return N->getPredecessors().begin(); 1504 } 1505 1506 static inline ChildIteratorType child_end(NodeRef N) { 1507 return N->getPredecessors().end(); 1508 } 1509 }; 1510 1511 // The following set of template specializations implement GraphTraits to 1512 // treat VPRegionBlock as a graph and recurse inside its nodes. It's important 1513 // to note that the blocks inside the VPRegionBlock are treated as VPBlockBases 1514 // (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so 1515 // there won't be automatic recursion into other VPBlockBases that turn to be 1516 // VPRegionBlocks. 1517 1518 template <> 1519 struct GraphTraits<VPRegionBlock *> : public GraphTraits<VPBlockBase *> { 1520 using GraphRef = VPRegionBlock *; 1521 using nodes_iterator = df_iterator<NodeRef>; 1522 1523 static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); } 1524 1525 static nodes_iterator nodes_begin(GraphRef N) { 1526 return nodes_iterator::begin(N->getEntry()); 1527 } 1528 1529 static nodes_iterator nodes_end(GraphRef N) { 1530 // df_iterator::end() returns an empty iterator so the node used doesn't 1531 // matter. 1532 return nodes_iterator::end(N); 1533 } 1534 }; 1535 1536 template <> 1537 struct GraphTraits<const VPRegionBlock *> 1538 : public GraphTraits<const VPBlockBase *> { 1539 using GraphRef = const VPRegionBlock *; 1540 using nodes_iterator = df_iterator<NodeRef>; 1541 1542 static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); } 1543 1544 static nodes_iterator nodes_begin(GraphRef N) { 1545 return nodes_iterator::begin(N->getEntry()); 1546 } 1547 1548 static nodes_iterator nodes_end(GraphRef N) { 1549 // df_iterator::end() returns an empty iterator so the node used doesn't 1550 // matter. 1551 return nodes_iterator::end(N); 1552 } 1553 }; 1554 1555 template <> 1556 struct GraphTraits<Inverse<VPRegionBlock *>> 1557 : public GraphTraits<Inverse<VPBlockBase *>> { 1558 using GraphRef = VPRegionBlock *; 1559 using nodes_iterator = df_iterator<NodeRef>; 1560 1561 static NodeRef getEntryNode(Inverse<GraphRef> N) { 1562 return N.Graph->getExit(); 1563 } 1564 1565 static nodes_iterator nodes_begin(GraphRef N) { 1566 return nodes_iterator::begin(N->getExit()); 1567 } 1568 1569 static nodes_iterator nodes_end(GraphRef N) { 1570 // df_iterator::end() returns an empty iterator so the node used doesn't 1571 // matter. 1572 return nodes_iterator::end(N); 1573 } 1574 }; 1575 1576 /// VPlan models a candidate for vectorization, encoding various decisions take 1577 /// to produce efficient output IR, including which branches, basic-blocks and 1578 /// output IR instructions to generate, and their cost. VPlan holds a 1579 /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry 1580 /// VPBlock. 1581 class VPlan { 1582 friend class VPlanPrinter; 1583 friend class VPSlotTracker; 1584 1585 /// Hold the single entry to the Hierarchical CFG of the VPlan. 1586 VPBlockBase *Entry; 1587 1588 /// Holds the VFs applicable to this VPlan. 1589 SmallSetVector<ElementCount, 2> VFs; 1590 1591 /// Holds the name of the VPlan, for printing. 1592 std::string Name; 1593 1594 /// Holds all the external definitions created for this VPlan. 1595 // TODO: Introduce a specific representation for external definitions in 1596 // VPlan. External definitions must be immutable and hold a pointer to its 1597 // underlying IR that will be used to implement its structural comparison 1598 // (operators '==' and '<'). 1599 SmallPtrSet<VPValue *, 16> VPExternalDefs; 1600 1601 /// Represents the backedge taken count of the original loop, for folding 1602 /// the tail. 1603 VPValue *BackedgeTakenCount = nullptr; 1604 1605 /// Holds a mapping between Values and their corresponding VPValue inside 1606 /// VPlan. 1607 Value2VPValueTy Value2VPValue; 1608 1609 /// Holds the VPLoopInfo analysis for this VPlan. 1610 VPLoopInfo VPLInfo; 1611 1612 /// Holds the condition bit values built during VPInstruction to VPRecipe transformation. 1613 SmallVector<VPValue *, 4> VPCBVs; 1614 1615 public: 1616 VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) { 1617 if (Entry) 1618 Entry->setPlan(this); 1619 } 1620 1621 ~VPlan() { 1622 if (Entry) 1623 VPBlockBase::deleteCFG(Entry); 1624 for (auto &MapEntry : Value2VPValue) 1625 delete MapEntry.second; 1626 if (BackedgeTakenCount) 1627 delete BackedgeTakenCount; 1628 for (VPValue *Def : VPExternalDefs) 1629 delete Def; 1630 for (VPValue *CBV : VPCBVs) 1631 delete CBV; 1632 } 1633 1634 /// Generate the IR code for this VPlan. 1635 void execute(struct VPTransformState *State); 1636 1637 VPBlockBase *getEntry() { return Entry; } 1638 const VPBlockBase *getEntry() const { return Entry; } 1639 1640 VPBlockBase *setEntry(VPBlockBase *Block) { 1641 Entry = Block; 1642 Block->setPlan(this); 1643 return Entry; 1644 } 1645 1646 /// The backedge taken count of the original loop. 1647 VPValue *getOrCreateBackedgeTakenCount() { 1648 if (!BackedgeTakenCount) 1649 BackedgeTakenCount = new VPValue(); 1650 return BackedgeTakenCount; 1651 } 1652 1653 void addVF(ElementCount VF) { VFs.insert(VF); } 1654 1655 bool hasVF(ElementCount VF) { return VFs.count(VF); } 1656 1657 const std::string &getName() const { return Name; } 1658 1659 void setName(const Twine &newName) { Name = newName.str(); } 1660 1661 /// Add \p VPVal to the pool of external definitions if it's not already 1662 /// in the pool. 1663 void addExternalDef(VPValue *VPVal) { 1664 VPExternalDefs.insert(VPVal); 1665 } 1666 1667 /// Add \p CBV to the vector of condition bit values. 1668 void addCBV(VPValue *CBV) { 1669 VPCBVs.push_back(CBV); 1670 } 1671 1672 void addVPValue(Value *V) { 1673 assert(V && "Trying to add a null Value to VPlan"); 1674 assert(!Value2VPValue.count(V) && "Value already exists in VPlan"); 1675 Value2VPValue[V] = new VPValue(V); 1676 } 1677 1678 VPValue *getVPValue(Value *V) { 1679 assert(V && "Trying to get the VPValue of a null Value"); 1680 assert(Value2VPValue.count(V) && "Value does not exist in VPlan"); 1681 return Value2VPValue[V]; 1682 } 1683 1684 VPValue *getOrAddVPValue(Value *V) { 1685 assert(V && "Trying to get or add the VPValue of a null Value"); 1686 if (!Value2VPValue.count(V)) 1687 addVPValue(V); 1688 return getVPValue(V); 1689 } 1690 1691 /// Return the VPLoopInfo analysis for this VPlan. 1692 VPLoopInfo &getVPLoopInfo() { return VPLInfo; } 1693 const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; } 1694 1695 /// Dump the plan to stderr (for debugging). 1696 void dump() const; 1697 1698 /// Returns a range mapping the values the range \p Operands to their 1699 /// corresponding VPValues. 1700 iterator_range<mapped_iterator<Use *, std::function<VPValue *(Value *)>>> 1701 mapToVPValues(User::op_range Operands) { 1702 std::function<VPValue *(Value *)> Fn = [this](Value *Op) { 1703 return getOrAddVPValue(Op); 1704 }; 1705 return map_range(Operands, Fn); 1706 } 1707 1708 private: 1709 /// Add to the given dominator tree the header block and every new basic block 1710 /// that was created between it and the latch block, inclusive. 1711 static void updateDominatorTree(DominatorTree *DT, BasicBlock *LoopLatchBB, 1712 BasicBlock *LoopPreHeaderBB, 1713 BasicBlock *LoopExitBB); 1714 }; 1715 1716 /// VPlanPrinter prints a given VPlan to a given output stream. The printing is 1717 /// indented and follows the dot format. 1718 class VPlanPrinter { 1719 friend inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan); 1720 friend inline raw_ostream &operator<<(raw_ostream &OS, 1721 const struct VPlanIngredient &I); 1722 1723 private: 1724 raw_ostream &OS; 1725 const VPlan &Plan; 1726 unsigned Depth = 0; 1727 unsigned TabWidth = 2; 1728 std::string Indent; 1729 unsigned BID = 0; 1730 SmallDenseMap<const VPBlockBase *, unsigned> BlockID; 1731 1732 VPSlotTracker SlotTracker; 1733 1734 VPlanPrinter(raw_ostream &O, const VPlan &P) 1735 : OS(O), Plan(P), SlotTracker(&P) {} 1736 1737 /// Handle indentation. 1738 void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); } 1739 1740 /// Print a given \p Block of the Plan. 1741 void dumpBlock(const VPBlockBase *Block); 1742 1743 /// Print the information related to the CFG edges going out of a given 1744 /// \p Block, followed by printing the successor blocks themselves. 1745 void dumpEdges(const VPBlockBase *Block); 1746 1747 /// Print a given \p BasicBlock, including its VPRecipes, followed by printing 1748 /// its successor blocks. 1749 void dumpBasicBlock(const VPBasicBlock *BasicBlock); 1750 1751 /// Print a given \p Region of the Plan. 1752 void dumpRegion(const VPRegionBlock *Region); 1753 1754 unsigned getOrCreateBID(const VPBlockBase *Block) { 1755 return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++; 1756 } 1757 1758 const Twine getOrCreateName(const VPBlockBase *Block); 1759 1760 const Twine getUID(const VPBlockBase *Block); 1761 1762 /// Print the information related to a CFG edge between two VPBlockBases. 1763 void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden, 1764 const Twine &Label); 1765 1766 void dump(); 1767 1768 static void printAsIngredient(raw_ostream &O, Value *V); 1769 }; 1770 1771 struct VPlanIngredient { 1772 Value *V; 1773 1774 VPlanIngredient(Value *V) : V(V) {} 1775 }; 1776 1777 inline raw_ostream &operator<<(raw_ostream &OS, const VPlanIngredient &I) { 1778 VPlanPrinter::printAsIngredient(OS, I.V); 1779 return OS; 1780 } 1781 1782 inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) { 1783 VPlanPrinter Printer(OS, Plan); 1784 Printer.dump(); 1785 return OS; 1786 } 1787 1788 //===----------------------------------------------------------------------===// 1789 // VPlan Utilities 1790 //===----------------------------------------------------------------------===// 1791 1792 /// Class that provides utilities for VPBlockBases in VPlan. 1793 class VPBlockUtils { 1794 public: 1795 VPBlockUtils() = delete; 1796 1797 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p 1798 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p 1799 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. If \p BlockPtr 1800 /// has more than one successor, its conditional bit is propagated to \p 1801 /// NewBlock. \p NewBlock must have neither successors nor predecessors. 1802 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) { 1803 assert(NewBlock->getSuccessors().empty() && 1804 "Can't insert new block with successors."); 1805 // TODO: move successors from BlockPtr to NewBlock when this functionality 1806 // is necessary. For now, setBlockSingleSuccessor will assert if BlockPtr 1807 // already has successors. 1808 BlockPtr->setOneSuccessor(NewBlock); 1809 NewBlock->setPredecessors({BlockPtr}); 1810 NewBlock->setParent(BlockPtr->getParent()); 1811 } 1812 1813 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p 1814 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p 1815 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr 1816 /// parent to \p IfTrue and \p IfFalse. \p Condition is set as the successor 1817 /// selector. \p BlockPtr must have no successors and \p IfTrue and \p IfFalse 1818 /// must have neither successors nor predecessors. 1819 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, 1820 VPValue *Condition, VPBlockBase *BlockPtr) { 1821 assert(IfTrue->getSuccessors().empty() && 1822 "Can't insert IfTrue with successors."); 1823 assert(IfFalse->getSuccessors().empty() && 1824 "Can't insert IfFalse with successors."); 1825 BlockPtr->setTwoSuccessors(IfTrue, IfFalse, Condition); 1826 IfTrue->setPredecessors({BlockPtr}); 1827 IfFalse->setPredecessors({BlockPtr}); 1828 IfTrue->setParent(BlockPtr->getParent()); 1829 IfFalse->setParent(BlockPtr->getParent()); 1830 } 1831 1832 /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to 1833 /// the successors of \p From and \p From to the predecessors of \p To. Both 1834 /// VPBlockBases must have the same parent, which can be null. Both 1835 /// VPBlockBases can be already connected to other VPBlockBases. 1836 static void connectBlocks(VPBlockBase *From, VPBlockBase *To) { 1837 assert((From->getParent() == To->getParent()) && 1838 "Can't connect two block with different parents"); 1839 assert(From->getNumSuccessors() < 2 && 1840 "Blocks can't have more than two successors."); 1841 From->appendSuccessor(To); 1842 To->appendPredecessor(From); 1843 } 1844 1845 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To 1846 /// from the successors of \p From and \p From from the predecessors of \p To. 1847 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) { 1848 assert(To && "Successor to disconnect is null."); 1849 From->removeSuccessor(To); 1850 To->removePredecessor(From); 1851 } 1852 1853 /// Returns true if the edge \p FromBlock -> \p ToBlock is a back-edge. 1854 static bool isBackEdge(const VPBlockBase *FromBlock, 1855 const VPBlockBase *ToBlock, const VPLoopInfo *VPLI) { 1856 assert(FromBlock->getParent() == ToBlock->getParent() && 1857 FromBlock->getParent() && "Must be in same region"); 1858 const VPLoop *FromLoop = VPLI->getLoopFor(FromBlock); 1859 const VPLoop *ToLoop = VPLI->getLoopFor(ToBlock); 1860 if (!FromLoop || !ToLoop || FromLoop != ToLoop) 1861 return false; 1862 1863 // A back-edge is a branch from the loop latch to its header. 1864 return ToLoop->isLoopLatch(FromBlock) && ToBlock == ToLoop->getHeader(); 1865 } 1866 1867 /// Returns true if \p Block is a loop latch 1868 static bool blockIsLoopLatch(const VPBlockBase *Block, 1869 const VPLoopInfo *VPLInfo) { 1870 if (const VPLoop *ParentVPL = VPLInfo->getLoopFor(Block)) 1871 return ParentVPL->isLoopLatch(Block); 1872 1873 return false; 1874 } 1875 1876 /// Count and return the number of succesors of \p PredBlock excluding any 1877 /// backedges. 1878 static unsigned countSuccessorsNoBE(VPBlockBase *PredBlock, 1879 VPLoopInfo *VPLI) { 1880 unsigned Count = 0; 1881 for (VPBlockBase *SuccBlock : PredBlock->getSuccessors()) { 1882 if (!VPBlockUtils::isBackEdge(PredBlock, SuccBlock, VPLI)) 1883 Count++; 1884 } 1885 return Count; 1886 } 1887 }; 1888 1889 class VPInterleavedAccessInfo { 1890 DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *> 1891 InterleaveGroupMap; 1892 1893 /// Type for mapping of instruction based interleave groups to VPInstruction 1894 /// interleave groups 1895 using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *, 1896 InterleaveGroup<VPInstruction> *>; 1897 1898 /// Recursively \p Region and populate VPlan based interleave groups based on 1899 /// \p IAI. 1900 void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New, 1901 InterleavedAccessInfo &IAI); 1902 /// Recursively traverse \p Block and populate VPlan based interleave groups 1903 /// based on \p IAI. 1904 void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New, 1905 InterleavedAccessInfo &IAI); 1906 1907 public: 1908 VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI); 1909 1910 ~VPInterleavedAccessInfo() { 1911 SmallPtrSet<InterleaveGroup<VPInstruction> *, 4> DelSet; 1912 // Avoid releasing a pointer twice. 1913 for (auto &I : InterleaveGroupMap) 1914 DelSet.insert(I.second); 1915 for (auto *Ptr : DelSet) 1916 delete Ptr; 1917 } 1918 1919 /// Get the interleave group that \p Instr belongs to. 1920 /// 1921 /// \returns nullptr if doesn't have such group. 1922 InterleaveGroup<VPInstruction> * 1923 getInterleaveGroup(VPInstruction *Instr) const { 1924 if (InterleaveGroupMap.count(Instr)) 1925 return InterleaveGroupMap.find(Instr)->second; 1926 return nullptr; 1927 } 1928 }; 1929 1930 /// Class that maps (parts of) an existing VPlan to trees of combined 1931 /// VPInstructions. 1932 class VPlanSlp { 1933 enum class OpMode { Failed, Load, Opcode }; 1934 1935 /// A DenseMapInfo implementation for using SmallVector<VPValue *, 4> as 1936 /// DenseMap keys. 1937 struct BundleDenseMapInfo { 1938 static SmallVector<VPValue *, 4> getEmptyKey() { 1939 return {reinterpret_cast<VPValue *>(-1)}; 1940 } 1941 1942 static SmallVector<VPValue *, 4> getTombstoneKey() { 1943 return {reinterpret_cast<VPValue *>(-2)}; 1944 } 1945 1946 static unsigned getHashValue(const SmallVector<VPValue *, 4> &V) { 1947 return static_cast<unsigned>(hash_combine_range(V.begin(), V.end())); 1948 } 1949 1950 static bool isEqual(const SmallVector<VPValue *, 4> &LHS, 1951 const SmallVector<VPValue *, 4> &RHS) { 1952 return LHS == RHS; 1953 } 1954 }; 1955 1956 /// Mapping of values in the original VPlan to a combined VPInstruction. 1957 DenseMap<SmallVector<VPValue *, 4>, VPInstruction *, BundleDenseMapInfo> 1958 BundleToCombined; 1959 1960 VPInterleavedAccessInfo &IAI; 1961 1962 /// Basic block to operate on. For now, only instructions in a single BB are 1963 /// considered. 1964 const VPBasicBlock &BB; 1965 1966 /// Indicates whether we managed to combine all visited instructions or not. 1967 bool CompletelySLP = true; 1968 1969 /// Width of the widest combined bundle in bits. 1970 unsigned WidestBundleBits = 0; 1971 1972 using MultiNodeOpTy = 1973 typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>; 1974 1975 // Input operand bundles for the current multi node. Each multi node operand 1976 // bundle contains values not matching the multi node's opcode. They will 1977 // be reordered in reorderMultiNodeOps, once we completed building a 1978 // multi node. 1979 SmallVector<MultiNodeOpTy, 4> MultiNodeOps; 1980 1981 /// Indicates whether we are building a multi node currently. 1982 bool MultiNodeActive = false; 1983 1984 /// Check if we can vectorize Operands together. 1985 bool areVectorizable(ArrayRef<VPValue *> Operands) const; 1986 1987 /// Add combined instruction \p New for the bundle \p Operands. 1988 void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New); 1989 1990 /// Indicate we hit a bundle we failed to combine. Returns nullptr for now. 1991 VPInstruction *markFailed(); 1992 1993 /// Reorder operands in the multi node to maximize sequential memory access 1994 /// and commutative operations. 1995 SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps(); 1996 1997 /// Choose the best candidate to use for the lane after \p Last. The set of 1998 /// candidates to choose from are values with an opcode matching \p Last's 1999 /// or loads consecutive to \p Last. 2000 std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last, 2001 SmallPtrSetImpl<VPValue *> &Candidates, 2002 VPInterleavedAccessInfo &IAI); 2003 2004 /// Print bundle \p Values to dbgs(). 2005 void dumpBundle(ArrayRef<VPValue *> Values); 2006 2007 public: 2008 VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {} 2009 2010 ~VPlanSlp() { 2011 for (auto &KV : BundleToCombined) 2012 delete KV.second; 2013 } 2014 2015 /// Tries to build an SLP tree rooted at \p Operands and returns a 2016 /// VPInstruction combining \p Operands, if they can be combined. 2017 VPInstruction *buildGraph(ArrayRef<VPValue *> Operands); 2018 2019 /// Return the width of the widest combined bundle in bits. 2020 unsigned getWidestBundleBits() const { return WidestBundleBits; } 2021 2022 /// Return true if all visited instruction can be combined. 2023 bool isCompletelySLP() const { return CompletelySLP; } 2024 }; 2025 } // end namespace llvm 2026 2027 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H 2028