4676 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file10/// This file contains the declarations of the Vectorization Plan base classes:11/// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual12/// VPBlockBase, together implementing a Hierarchical CFG;13/// 2. Pure virtual VPRecipeBase serving as the base class for recipes contained14/// within VPBasicBlocks;15/// 3. Pure virtual VPSingleDefRecipe serving as a base class for recipes that16/// also inherit from VPValue.17/// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned18/// instruction;19/// 5. The VPlan class holding a candidate for vectorization;20/// These are documented in docs/VectorizationPlan.rst.21//22//===----------------------------------------------------------------------===//23 24#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H25#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H26 27#include "VPlanValue.h"28#include "llvm/ADT/DenseMap.h"29#include "llvm/ADT/SmallPtrSet.h"30#include "llvm/ADT/SmallVector.h"31#include "llvm/ADT/Twine.h"32#include "llvm/ADT/ilist.h"33#include "llvm/ADT/ilist_node.h"34#include "llvm/Analysis/IVDescriptors.h"35#include "llvm/Analysis/MemoryLocation.h"36#include "llvm/Analysis/VectorUtils.h"37#include "llvm/IR/DebugLoc.h"38#include "llvm/IR/FMF.h"39#include "llvm/IR/Operator.h"40#include "llvm/Support/Compiler.h"41#include "llvm/Support/InstructionCost.h"42#include <cassert>43#include <cstddef>44#include <functional>45#include <string>46#include <utility>47#include <variant>48 49namespace llvm {50 51class BasicBlock;52class DominatorTree;53class InnerLoopVectorizer;54class IRBuilderBase;55struct VPTransformState;56class raw_ostream;57class RecurrenceDescriptor;58class SCEV;59class Type;60class VPBasicBlock;61class VPBuilder;62class VPDominatorTree;63class VPRegionBlock;64class VPlan;65class VPLane;66class VPReplicateRecipe;67class VPlanSlp;68class Value;69class LoopVectorizationCostModel;70 71struct VPCostContext;72 73namespace Intrinsic {74typedef unsigned ID;75}76 77using VPlanPtr = std::unique_ptr<VPlan>;78 79/// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.80/// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.81class LLVM_ABI_FOR_TEST VPBlockBase {82 friend class VPBlockUtils;83 84 const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).85 86 /// An optional name for the block.87 std::string Name;88 89 /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if90 /// it is a topmost VPBlockBase.91 VPRegionBlock *Parent = nullptr;92 93 /// List of predecessor blocks.94 SmallVector<VPBlockBase *, 1> Predecessors;95 96 /// List of successor blocks.97 SmallVector<VPBlockBase *, 1> Successors;98 99 /// VPlan containing the block. Can only be set on the entry block of the100 /// plan.101 VPlan *Plan = nullptr;102 103 /// Add \p Successor as the last successor to this block.104 void appendSuccessor(VPBlockBase *Successor) {105 assert(Successor && "Cannot add nullptr successor!");106 Successors.push_back(Successor);107 }108 109 /// Add \p Predecessor as the last predecessor to this block.110 void appendPredecessor(VPBlockBase *Predecessor) {111 assert(Predecessor && "Cannot add nullptr predecessor!");112 Predecessors.push_back(Predecessor);113 }114 115 /// Remove \p Predecessor from the predecessors of this block.116 void removePredecessor(VPBlockBase *Predecessor) {117 auto Pos = find(Predecessors, Predecessor);118 assert(Pos && "Predecessor does not exist");119 Predecessors.erase(Pos);120 }121 122 /// Remove \p Successor from the successors of this block.123 void removeSuccessor(VPBlockBase *Successor) {124 auto Pos = find(Successors, Successor);125 assert(Pos && "Successor does not exist");126 Successors.erase(Pos);127 }128 129 /// This function replaces one predecessor with another, useful when130 /// trying to replace an old block in the CFG with a new one.131 void replacePredecessor(VPBlockBase *Old, VPBlockBase *New) {132 auto I = find(Predecessors, Old);133 assert(I != Predecessors.end());134 assert(Old->getParent() == New->getParent() &&135 "replaced predecessor must have the same parent");136 *I = New;137 }138 139 /// This function replaces one successor with another, useful when140 /// trying to replace an old block in the CFG with a new one.141 void replaceSuccessor(VPBlockBase *Old, VPBlockBase *New) {142 auto I = find(Successors, Old);143 assert(I != Successors.end());144 assert(Old->getParent() == New->getParent() &&145 "replaced successor must have the same parent");146 *I = New;147 }148 149protected:150 VPBlockBase(const unsigned char SC, const std::string &N)151 : SubclassID(SC), Name(N) {}152 153public:154 /// An enumeration for keeping track of the concrete subclass of VPBlockBase155 /// that are actually instantiated. Values of this enumeration are kept in the156 /// SubclassID field of the VPBlockBase objects. They are used for concrete157 /// type identification.158 using VPBlockTy = enum { VPRegionBlockSC, VPBasicBlockSC, VPIRBasicBlockSC };159 160 using VPBlocksTy = SmallVectorImpl<VPBlockBase *>;161 162 virtual ~VPBlockBase() = default;163 164 const std::string &getName() const { return Name; }165 166 void setName(const Twine &newName) { Name = newName.str(); }167 168 /// \return an ID for the concrete type of this object.169 /// This is used to implement the classof checks. This should not be used170 /// for any other purpose, as the values may change as LLVM evolves.171 unsigned getVPBlockID() const { return SubclassID; }172 173 VPRegionBlock *getParent() { return Parent; }174 const VPRegionBlock *getParent() const { return Parent; }175 176 /// \return A pointer to the plan containing the current block.177 VPlan *getPlan();178 const VPlan *getPlan() const;179 180 /// Sets the pointer of the plan containing the block. The block must be the181 /// entry block into the VPlan.182 void setPlan(VPlan *ParentPlan);183 184 void setParent(VPRegionBlock *P) { Parent = P; }185 186 /// \return the VPBasicBlock that is the entry of this VPBlockBase,187 /// recursively, if the latter is a VPRegionBlock. Otherwise, if this188 /// VPBlockBase is a VPBasicBlock, it is returned.189 const VPBasicBlock *getEntryBasicBlock() const;190 VPBasicBlock *getEntryBasicBlock();191 192 /// \return the VPBasicBlock that is the exiting this VPBlockBase,193 /// recursively, if the latter is a VPRegionBlock. Otherwise, if this194 /// VPBlockBase is a VPBasicBlock, it is returned.195 const VPBasicBlock *getExitingBasicBlock() const;196 VPBasicBlock *getExitingBasicBlock();197 198 const VPBlocksTy &getSuccessors() const { return Successors; }199 VPBlocksTy &getSuccessors() { return Successors; }200 201 iterator_range<VPBlockBase **> successors() { return Successors; }202 iterator_range<VPBlockBase **> predecessors() { return Predecessors; }203 204 const VPBlocksTy &getPredecessors() const { return Predecessors; }205 VPBlocksTy &getPredecessors() { return Predecessors; }206 207 /// \return the successor of this VPBlockBase if it has a single successor.208 /// Otherwise return a null pointer.209 VPBlockBase *getSingleSuccessor() const {210 return (Successors.size() == 1 ? *Successors.begin() : nullptr);211 }212 213 /// \return the predecessor of this VPBlockBase if it has a single214 /// predecessor. Otherwise return a null pointer.215 VPBlockBase *getSinglePredecessor() const {216 return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);217 }218 219 size_t getNumSuccessors() const { return Successors.size(); }220 size_t getNumPredecessors() const { return Predecessors.size(); }221 222 /// Returns true if this block has any predecessors.223 bool hasPredecessors() const { return !Predecessors.empty(); }224 225 /// An Enclosing Block of a block B is any block containing B, including B226 /// itself. \return the closest enclosing block starting from "this", which227 /// has successors. \return the root enclosing block if all enclosing blocks228 /// have no successors.229 VPBlockBase *getEnclosingBlockWithSuccessors();230 231 /// \return the closest enclosing block starting from "this", which has232 /// predecessors. \return the root enclosing block if all enclosing blocks233 /// have no predecessors.234 VPBlockBase *getEnclosingBlockWithPredecessors();235 236 /// \return the successors either attached directly to this VPBlockBase or, if237 /// this VPBlockBase is the exit block of a VPRegionBlock and has no238 /// successors of its own, search recursively for the first enclosing239 /// VPRegionBlock that has successors and return them. If no such240 /// VPRegionBlock exists, return the (empty) successors of the topmost241 /// VPBlockBase reached.242 const VPBlocksTy &getHierarchicalSuccessors() {243 return getEnclosingBlockWithSuccessors()->getSuccessors();244 }245 246 /// \return the hierarchical successor of this VPBlockBase if it has a single247 /// hierarchical successor. Otherwise return a null pointer.248 VPBlockBase *getSingleHierarchicalSuccessor() {249 return getEnclosingBlockWithSuccessors()->getSingleSuccessor();250 }251 252 /// \return the predecessors either attached directly to this VPBlockBase or,253 /// if this VPBlockBase is the entry block of a VPRegionBlock and has no254 /// predecessors of its own, search recursively for the first enclosing255 /// VPRegionBlock that has predecessors and return them. If no such256 /// VPRegionBlock exists, return the (empty) predecessors of the topmost257 /// VPBlockBase reached.258 const VPBlocksTy &getHierarchicalPredecessors() {259 return getEnclosingBlockWithPredecessors()->getPredecessors();260 }261 262 /// \return the hierarchical predecessor of this VPBlockBase if it has a263 /// single hierarchical predecessor. Otherwise return a null pointer.264 VPBlockBase *getSingleHierarchicalPredecessor() {265 return getEnclosingBlockWithPredecessors()->getSinglePredecessor();266 }267 268 /// Set a given VPBlockBase \p Successor as the single successor of this269 /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.270 /// This VPBlockBase must have no successors.271 void setOneSuccessor(VPBlockBase *Successor) {272 assert(Successors.empty() && "Setting one successor when others exist.");273 assert(Successor->getParent() == getParent() &&274 "connected blocks must have the same parent");275 appendSuccessor(Successor);276 }277 278 /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two279 /// successors of this VPBlockBase. This VPBlockBase is not added as280 /// predecessor of \p IfTrue or \p IfFalse. This VPBlockBase must have no281 /// successors.282 void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {283 assert(Successors.empty() && "Setting two successors when others exist.");284 appendSuccessor(IfTrue);285 appendSuccessor(IfFalse);286 }287 288 /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.289 /// This VPBlockBase must have no predecessors. This VPBlockBase is not added290 /// as successor of any VPBasicBlock in \p NewPreds.291 void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) {292 assert(Predecessors.empty() && "Block predecessors already set.");293 for (auto *Pred : NewPreds)294 appendPredecessor(Pred);295 }296 297 /// Set each VPBasicBlock in \p NewSuccss as successor of this VPBlockBase.298 /// This VPBlockBase must have no successors. This VPBlockBase is not added299 /// as predecessor of any VPBasicBlock in \p NewSuccs.300 void setSuccessors(ArrayRef<VPBlockBase *> NewSuccs) {301 assert(Successors.empty() && "Block successors already set.");302 for (auto *Succ : NewSuccs)303 appendSuccessor(Succ);304 }305 306 /// Remove all the predecessor of this block.307 void clearPredecessors() { Predecessors.clear(); }308 309 /// Remove all the successors of this block.310 void clearSuccessors() { Successors.clear(); }311 312 /// Swap predecessors of the block. The block must have exactly 2313 /// predecessors.314 void swapPredecessors() {315 assert(Predecessors.size() == 2 && "must have 2 predecessors to swap");316 std::swap(Predecessors[0], Predecessors[1]);317 }318 319 /// Swap successors of the block. The block must have exactly 2 successors.320 // TODO: This should be part of introducing conditional branch recipes rather321 // than being independent.322 void swapSuccessors() {323 assert(Successors.size() == 2 && "must have 2 successors to swap");324 std::swap(Successors[0], Successors[1]);325 }326 327 /// Returns the index for \p Pred in the blocks predecessors list.328 unsigned getIndexForPredecessor(const VPBlockBase *Pred) const {329 assert(count(Predecessors, Pred) == 1 &&330 "must have Pred exactly once in Predecessors");331 return std::distance(Predecessors.begin(), find(Predecessors, Pred));332 }333 334 /// Returns the index for \p Succ in the blocks successor list.335 unsigned getIndexForSuccessor(const VPBlockBase *Succ) const {336 assert(count(Successors, Succ) == 1 &&337 "must have Succ exactly once in Successors");338 return std::distance(Successors.begin(), find(Successors, Succ));339 }340 341 /// The method which generates the output IR that correspond to this342 /// VPBlockBase, thereby "executing" the VPlan.343 virtual void execute(VPTransformState *State) = 0;344 345 /// Return the cost of the block.346 virtual InstructionCost cost(ElementCount VF, VPCostContext &Ctx) = 0;347 348#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)349 void printAsOperand(raw_ostream &OS, bool PrintType = false) const {350 OS << getName();351 }352 353 /// Print plain-text dump of this VPBlockBase to \p O, prefixing all lines354 /// with \p Indent. \p SlotTracker is used to print unnamed VPValue's using355 /// consequtive numbers.356 ///357 /// Note that the numbering is applied to the whole VPlan, so printing358 /// individual blocks is consistent with the whole VPlan printing.359 virtual void print(raw_ostream &O, const Twine &Indent,360 VPSlotTracker &SlotTracker) const = 0;361 362 /// Print plain-text dump of this VPlan to \p O.363 void print(raw_ostream &O) const;364 365 /// Print the successors of this block to \p O, prefixing all lines with \p366 /// Indent.367 void printSuccessors(raw_ostream &O, const Twine &Indent) const;368 369 /// Dump this VPBlockBase to dbgs().370 LLVM_DUMP_METHOD void dump() const { print(dbgs()); }371#endif372 373 /// Clone the current block and it's recipes without updating the operands of374 /// the cloned recipes, including all blocks in the single-entry single-exit375 /// region for VPRegionBlocks.376 virtual VPBlockBase *clone() = 0;377};378 379/// VPRecipeBase is a base class modeling a sequence of one or more output IR380/// instructions. VPRecipeBase owns the VPValues it defines through VPDef381/// and is responsible for deleting its defined values. Single-value382/// recipes must inherit from VPSingleDef instead of inheriting from both383/// VPRecipeBase and VPValue separately.384class LLVM_ABI_FOR_TEST VPRecipeBase385 : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,386 public VPDef,387 public VPUser {388 friend VPBasicBlock;389 friend class VPBlockUtils;390 391 /// Each VPRecipe belongs to a single VPBasicBlock.392 VPBasicBlock *Parent = nullptr;393 394 /// The debug location for the recipe.395 DebugLoc DL;396 397public:398 VPRecipeBase(const unsigned char SC, ArrayRef<VPValue *> Operands,399 DebugLoc DL = DebugLoc::getUnknown())400 : VPDef(SC), VPUser(Operands), DL(DL) {}401 402 ~VPRecipeBase() override = default;403 404 /// Clone the current recipe.405 virtual VPRecipeBase *clone() = 0;406 407 /// \return the VPBasicBlock which this VPRecipe belongs to.408 VPBasicBlock *getParent() { return Parent; }409 const VPBasicBlock *getParent() const { return Parent; }410 411 /// \return the VPRegionBlock which the recipe belongs to.412 VPRegionBlock *getRegion();413 const VPRegionBlock *getRegion() const;414 415 /// The method which generates the output IR instructions that correspond to416 /// this VPRecipe, thereby "executing" the VPlan.417 virtual void execute(VPTransformState &State) = 0;418 419 /// Return the cost of this recipe, taking into account if the cost420 /// computation should be skipped and the ForceTargetInstructionCost flag.421 /// Also takes care of printing the cost for debugging.422 InstructionCost cost(ElementCount VF, VPCostContext &Ctx);423 424 /// Insert an unlinked recipe into a basic block immediately before425 /// the specified recipe.426 void insertBefore(VPRecipeBase *InsertPos);427 /// Insert an unlinked recipe into \p BB immediately before the insertion428 /// point \p IP;429 void insertBefore(VPBasicBlock &BB, iplist<VPRecipeBase>::iterator IP);430 431 /// Insert an unlinked Recipe into a basic block immediately after432 /// the specified Recipe.433 void insertAfter(VPRecipeBase *InsertPos);434 435 /// Unlink this recipe from its current VPBasicBlock and insert it into436 /// the VPBasicBlock that MovePos lives in, right after MovePos.437 void moveAfter(VPRecipeBase *MovePos);438 439 /// Unlink this recipe and insert into BB before I.440 ///441 /// \pre I is a valid iterator into BB.442 void moveBefore(VPBasicBlock &BB, iplist<VPRecipeBase>::iterator I);443 444 /// This method unlinks 'this' from the containing basic block, but does not445 /// delete it.446 void removeFromParent();447 448 /// This method unlinks 'this' from the containing basic block and deletes it.449 ///450 /// \returns an iterator pointing to the element after the erased one451 iplist<VPRecipeBase>::iterator eraseFromParent();452 453 /// Method to support type inquiry through isa, cast, and dyn_cast.454 static inline bool classof(const VPDef *D) {455 // All VPDefs are also VPRecipeBases.456 return true;457 }458 459 static inline bool classof(const VPUser *U) { return true; }460 461 /// Returns true if the recipe may have side-effects.462 bool mayHaveSideEffects() const;463 464 /// Returns true for PHI-like recipes.465 bool isPhi() const;466 467 /// Returns true if the recipe may read from memory.468 bool mayReadFromMemory() const;469 470 /// Returns true if the recipe may write to memory.471 bool mayWriteToMemory() const;472 473 /// Returns true if the recipe may read from or write to memory.474 bool mayReadOrWriteMemory() const {475 return mayReadFromMemory() || mayWriteToMemory();476 }477 478 /// Returns the debug location of the recipe.479 DebugLoc getDebugLoc() const { return DL; }480 481 /// Return true if the recipe is a scalar cast.482 bool isScalarCast() const;483 484 /// Set the recipe's debug location to \p NewDL.485 void setDebugLoc(DebugLoc NewDL) { DL = NewDL; }486 487#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)488 /// Print the recipe, delegating to printRecipe().489 void print(raw_ostream &O, const Twine &Indent,490 VPSlotTracker &SlotTracker) const override final;491#endif492 493protected:494 /// Compute the cost of this recipe either using a recipe's specialized495 /// implementation or using the legacy cost model and the underlying496 /// instructions.497 virtual InstructionCost computeCost(ElementCount VF,498 VPCostContext &Ctx) const;499 500#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)501 /// Each concrete VPRecipe prints itself, without printing common information,502 /// like debug info or metadata.503 virtual void printRecipe(raw_ostream &O, const Twine &Indent,504 VPSlotTracker &SlotTracker) const = 0;505#endif506};507 508// Helper macro to define common classof implementations for recipes.509#define VP_CLASSOF_IMPL(VPDefID) \510 static inline bool classof(const VPDef *D) { \511 return D->getVPDefID() == VPDefID; \512 } \513 static inline bool classof(const VPValue *V) { \514 auto *R = V->getDefiningRecipe(); \515 return R && R->getVPDefID() == VPDefID; \516 } \517 static inline bool classof(const VPUser *U) { \518 auto *R = dyn_cast<VPRecipeBase>(U); \519 return R && R->getVPDefID() == VPDefID; \520 } \521 static inline bool classof(const VPRecipeBase *R) { \522 return R->getVPDefID() == VPDefID; \523 } \524 static inline bool classof(const VPSingleDefRecipe *R) { \525 return R->getVPDefID() == VPDefID; \526 }527 528/// VPSingleDef is a base class for recipes for modeling a sequence of one or529/// more output IR that define a single result VPValue.530/// Note that VPRecipeBase must be inherited from before VPValue.531class VPSingleDefRecipe : public VPRecipeBase, public VPValue {532public:533 VPSingleDefRecipe(const unsigned char SC, ArrayRef<VPValue *> Operands,534 DebugLoc DL = DebugLoc::getUnknown())535 : VPRecipeBase(SC, Operands, DL), VPValue(this) {}536 537 VPSingleDefRecipe(const unsigned char SC, ArrayRef<VPValue *> Operands,538 Value *UV, DebugLoc DL = DebugLoc::getUnknown())539 : VPRecipeBase(SC, Operands, DL), VPValue(this, UV) {}540 541 static inline bool classof(const VPRecipeBase *R) {542 switch (R->getVPDefID()) {543 case VPRecipeBase::VPDerivedIVSC:544 case VPRecipeBase::VPEVLBasedIVPHISC:545 case VPRecipeBase::VPExpandSCEVSC:546 case VPRecipeBase::VPExpressionSC:547 case VPRecipeBase::VPInstructionSC:548 case VPRecipeBase::VPReductionEVLSC:549 case VPRecipeBase::VPReductionSC:550 case VPRecipeBase::VPReplicateSC:551 case VPRecipeBase::VPScalarIVStepsSC:552 case VPRecipeBase::VPVectorPointerSC:553 case VPRecipeBase::VPVectorEndPointerSC:554 case VPRecipeBase::VPWidenCallSC:555 case VPRecipeBase::VPWidenCanonicalIVSC:556 case VPRecipeBase::VPWidenCastSC:557 case VPRecipeBase::VPWidenGEPSC:558 case VPRecipeBase::VPWidenIntrinsicSC:559 case VPRecipeBase::VPWidenSC:560 case VPRecipeBase::VPWidenSelectSC:561 case VPRecipeBase::VPBlendSC:562 case VPRecipeBase::VPPredInstPHISC:563 case VPRecipeBase::VPCanonicalIVPHISC:564 case VPRecipeBase::VPActiveLaneMaskPHISC:565 case VPRecipeBase::VPFirstOrderRecurrencePHISC:566 case VPRecipeBase::VPWidenPHISC:567 case VPRecipeBase::VPWidenIntOrFpInductionSC:568 case VPRecipeBase::VPWidenPointerInductionSC:569 case VPRecipeBase::VPReductionPHISC:570 return true;571 case VPRecipeBase::VPBranchOnMaskSC:572 case VPRecipeBase::VPInterleaveEVLSC:573 case VPRecipeBase::VPInterleaveSC:574 case VPRecipeBase::VPIRInstructionSC:575 case VPRecipeBase::VPWidenLoadEVLSC:576 case VPRecipeBase::VPWidenLoadSC:577 case VPRecipeBase::VPWidenStoreEVLSC:578 case VPRecipeBase::VPWidenStoreSC:579 case VPRecipeBase::VPHistogramSC:580 // TODO: Widened stores don't define a value, but widened loads do. Split581 // the recipes to be able to make widened loads VPSingleDefRecipes.582 return false;583 }584 llvm_unreachable("Unhandled VPDefID");585 }586 587 static inline bool classof(const VPUser *U) {588 auto *R = dyn_cast<VPRecipeBase>(U);589 return R && classof(R);590 }591 592 VPSingleDefRecipe *clone() override = 0;593 594 /// Returns the underlying instruction.595 Instruction *getUnderlyingInstr() {596 return cast<Instruction>(getUnderlyingValue());597 }598 const Instruction *getUnderlyingInstr() const {599 return cast<Instruction>(getUnderlyingValue());600 }601 602#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)603 /// Print this VPSingleDefRecipe to dbgs() (for debugging).604 LLVM_ABI_FOR_TEST LLVM_DUMP_METHOD void dump() const;605#endif606};607 608/// Class to record and manage LLVM IR flags.609class VPIRFlags {610 enum class OperationType : unsigned char {611 Cmp,612 FCmp,613 OverflowingBinOp,614 Trunc,615 DisjointOp,616 PossiblyExactOp,617 GEPOp,618 FPMathOp,619 NonNegOp,620 Other621 };622 623public:624 struct WrapFlagsTy {625 char HasNUW : 1;626 char HasNSW : 1;627 628 WrapFlagsTy(bool HasNUW, bool HasNSW) : HasNUW(HasNUW), HasNSW(HasNSW) {}629 };630 631 struct TruncFlagsTy {632 char HasNUW : 1;633 char HasNSW : 1;634 635 TruncFlagsTy(bool HasNUW, bool HasNSW) : HasNUW(HasNUW), HasNSW(HasNSW) {}636 };637 638 struct DisjointFlagsTy {639 char IsDisjoint : 1;640 DisjointFlagsTy(bool IsDisjoint) : IsDisjoint(IsDisjoint) {}641 };642 643 struct NonNegFlagsTy {644 char NonNeg : 1;645 NonNegFlagsTy(bool IsNonNeg) : NonNeg(IsNonNeg) {}646 };647 648private:649 struct ExactFlagsTy {650 char IsExact : 1;651 };652 struct FastMathFlagsTy {653 char AllowReassoc : 1;654 char NoNaNs : 1;655 char NoInfs : 1;656 char NoSignedZeros : 1;657 char AllowReciprocal : 1;658 char AllowContract : 1;659 char ApproxFunc : 1;660 661 LLVM_ABI_FOR_TEST FastMathFlagsTy(const FastMathFlags &FMF);662 };663 /// Holds both the predicate and fast-math flags for floating-point664 /// comparisons.665 struct FCmpFlagsTy {666 CmpInst::Predicate Pred;667 FastMathFlagsTy FMFs;668 };669 670 OperationType OpType;671 672 union {673 CmpInst::Predicate CmpPredicate;674 WrapFlagsTy WrapFlags;675 TruncFlagsTy TruncFlags;676 DisjointFlagsTy DisjointFlags;677 ExactFlagsTy ExactFlags;678 GEPNoWrapFlags GEPFlags;679 NonNegFlagsTy NonNegFlags;680 FastMathFlagsTy FMFs;681 FCmpFlagsTy FCmpFlags;682 unsigned AllFlags;683 };684 685public:686 VPIRFlags() : OpType(OperationType::Other), AllFlags(0) {}687 688 VPIRFlags(Instruction &I) {689 if (auto *FCmp = dyn_cast<FCmpInst>(&I)) {690 OpType = OperationType::FCmp;691 FCmpFlags.Pred = FCmp->getPredicate();692 FCmpFlags.FMFs = FCmp->getFastMathFlags();693 } else if (auto *Op = dyn_cast<CmpInst>(&I)) {694 OpType = OperationType::Cmp;695 CmpPredicate = Op->getPredicate();696 } else if (auto *Op = dyn_cast<PossiblyDisjointInst>(&I)) {697 OpType = OperationType::DisjointOp;698 DisjointFlags.IsDisjoint = Op->isDisjoint();699 } else if (auto *Op = dyn_cast<OverflowingBinaryOperator>(&I)) {700 OpType = OperationType::OverflowingBinOp;701 WrapFlags = {Op->hasNoUnsignedWrap(), Op->hasNoSignedWrap()};702 } else if (auto *Op = dyn_cast<TruncInst>(&I)) {703 OpType = OperationType::Trunc;704 TruncFlags = {Op->hasNoUnsignedWrap(), Op->hasNoSignedWrap()};705 } else if (auto *Op = dyn_cast<PossiblyExactOperator>(&I)) {706 OpType = OperationType::PossiblyExactOp;707 ExactFlags.IsExact = Op->isExact();708 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {709 OpType = OperationType::GEPOp;710 GEPFlags = GEP->getNoWrapFlags();711 } else if (auto *PNNI = dyn_cast<PossiblyNonNegInst>(&I)) {712 OpType = OperationType::NonNegOp;713 NonNegFlags.NonNeg = PNNI->hasNonNeg();714 } else if (auto *Op = dyn_cast<FPMathOperator>(&I)) {715 OpType = OperationType::FPMathOp;716 FMFs = Op->getFastMathFlags();717 } else {718 OpType = OperationType::Other;719 AllFlags = 0;720 }721 }722 723 VPIRFlags(CmpInst::Predicate Pred)724 : OpType(OperationType::Cmp), CmpPredicate(Pred) {}725 726 VPIRFlags(CmpInst::Predicate Pred, FastMathFlags FMFs)727 : OpType(OperationType::FCmp) {728 FCmpFlags.Pred = Pred;729 FCmpFlags.FMFs = FMFs;730 }731 732 VPIRFlags(WrapFlagsTy WrapFlags)733 : OpType(OperationType::OverflowingBinOp), WrapFlags(WrapFlags) {}734 735 VPIRFlags(TruncFlagsTy TruncFlags)736 : OpType(OperationType::Trunc), TruncFlags(TruncFlags) {}737 738 VPIRFlags(FastMathFlags FMFs) : OpType(OperationType::FPMathOp), FMFs(FMFs) {}739 740 VPIRFlags(DisjointFlagsTy DisjointFlags)741 : OpType(OperationType::DisjointOp), DisjointFlags(DisjointFlags) {}742 743 VPIRFlags(NonNegFlagsTy NonNegFlags)744 : OpType(OperationType::NonNegOp), NonNegFlags(NonNegFlags) {}745 746 VPIRFlags(GEPNoWrapFlags GEPFlags)747 : OpType(OperationType::GEPOp), GEPFlags(GEPFlags) {}748 749 void transferFlags(VPIRFlags &Other) {750 OpType = Other.OpType;751 AllFlags = Other.AllFlags;752 }753 754 /// Only keep flags also present in \p Other. \p Other must have the same755 /// OpType as the current object.756 void intersectFlags(const VPIRFlags &Other);757 758 /// Drop all poison-generating flags.759 void dropPoisonGeneratingFlags() {760 // NOTE: This needs to be kept in-sync with761 // Instruction::dropPoisonGeneratingFlags.762 switch (OpType) {763 case OperationType::OverflowingBinOp:764 WrapFlags.HasNUW = false;765 WrapFlags.HasNSW = false;766 break;767 case OperationType::Trunc:768 TruncFlags.HasNUW = false;769 TruncFlags.HasNSW = false;770 break;771 case OperationType::DisjointOp:772 DisjointFlags.IsDisjoint = false;773 break;774 case OperationType::PossiblyExactOp:775 ExactFlags.IsExact = false;776 break;777 case OperationType::GEPOp:778 GEPFlags = GEPNoWrapFlags::none();779 break;780 case OperationType::FPMathOp:781 case OperationType::FCmp:782 getFMFsRef().NoNaNs = false;783 getFMFsRef().NoInfs = false;784 break;785 case OperationType::NonNegOp:786 NonNegFlags.NonNeg = false;787 break;788 case OperationType::Cmp:789 case OperationType::Other:790 break;791 }792 }793 794 /// Apply the IR flags to \p I.795 void applyFlags(Instruction &I) const {796 switch (OpType) {797 case OperationType::OverflowingBinOp:798 I.setHasNoUnsignedWrap(WrapFlags.HasNUW);799 I.setHasNoSignedWrap(WrapFlags.HasNSW);800 break;801 case OperationType::Trunc:802 I.setHasNoUnsignedWrap(TruncFlags.HasNUW);803 I.setHasNoSignedWrap(TruncFlags.HasNSW);804 break;805 case OperationType::DisjointOp:806 cast<PossiblyDisjointInst>(&I)->setIsDisjoint(DisjointFlags.IsDisjoint);807 break;808 case OperationType::PossiblyExactOp:809 I.setIsExact(ExactFlags.IsExact);810 break;811 case OperationType::GEPOp:812 cast<GetElementPtrInst>(&I)->setNoWrapFlags(GEPFlags);813 break;814 case OperationType::FPMathOp:815 case OperationType::FCmp: {816 const FastMathFlagsTy &F = getFMFsRef();817 I.setHasAllowReassoc(F.AllowReassoc);818 I.setHasNoNaNs(F.NoNaNs);819 I.setHasNoInfs(F.NoInfs);820 I.setHasNoSignedZeros(F.NoSignedZeros);821 I.setHasAllowReciprocal(F.AllowReciprocal);822 I.setHasAllowContract(F.AllowContract);823 I.setHasApproxFunc(F.ApproxFunc);824 break;825 }826 case OperationType::NonNegOp:827 I.setNonNeg(NonNegFlags.NonNeg);828 break;829 case OperationType::Cmp:830 case OperationType::Other:831 break;832 }833 }834 835 CmpInst::Predicate getPredicate() const {836 assert((OpType == OperationType::Cmp || OpType == OperationType::FCmp) &&837 "recipe doesn't have a compare predicate");838 return OpType == OperationType::FCmp ? FCmpFlags.Pred : CmpPredicate;839 }840 841 void setPredicate(CmpInst::Predicate Pred) {842 assert((OpType == OperationType::Cmp || OpType == OperationType::FCmp) &&843 "recipe doesn't have a compare predicate");844 if (OpType == OperationType::FCmp)845 FCmpFlags.Pred = Pred;846 else847 CmpPredicate = Pred;848 }849 850 GEPNoWrapFlags getGEPNoWrapFlags() const { return GEPFlags; }851 852 /// Returns true if the recipe has a comparison predicate.853 bool hasPredicate() const {854 return OpType == OperationType::Cmp || OpType == OperationType::FCmp;855 }856 857 /// Returns true if the recipe has fast-math flags.858 bool hasFastMathFlags() const {859 return OpType == OperationType::FPMathOp || OpType == OperationType::FCmp;860 }861 862 LLVM_ABI_FOR_TEST FastMathFlags getFastMathFlags() const;863 864 /// Returns true if the recipe has non-negative flag.865 bool hasNonNegFlag() const { return OpType == OperationType::NonNegOp; }866 867 bool isNonNeg() const {868 assert(OpType == OperationType::NonNegOp &&869 "recipe doesn't have a NNEG flag");870 return NonNegFlags.NonNeg;871 }872 873 bool hasNoUnsignedWrap() const {874 switch (OpType) {875 case OperationType::OverflowingBinOp:876 return WrapFlags.HasNUW;877 case OperationType::Trunc:878 return TruncFlags.HasNUW;879 default:880 llvm_unreachable("recipe doesn't have a NUW flag");881 }882 }883 884 bool hasNoSignedWrap() const {885 switch (OpType) {886 case OperationType::OverflowingBinOp:887 return WrapFlags.HasNSW;888 case OperationType::Trunc:889 return TruncFlags.HasNSW;890 default:891 llvm_unreachable("recipe doesn't have a NSW flag");892 }893 }894 895 bool isDisjoint() const {896 assert(OpType == OperationType::DisjointOp &&897 "recipe cannot have a disjoing flag");898 return DisjointFlags.IsDisjoint;899 }900 901private:902 /// Get a reference to the fast-math flags for FPMathOp or FCmp.903 FastMathFlagsTy &getFMFsRef() {904 return OpType == OperationType::FCmp ? FCmpFlags.FMFs : FMFs;905 }906 const FastMathFlagsTy &getFMFsRef() const {907 return OpType == OperationType::FCmp ? FCmpFlags.FMFs : FMFs;908 }909 910public:911#if !defined(NDEBUG)912 /// Returns true if the set flags are valid for \p Opcode.913 bool flagsValidForOpcode(unsigned Opcode) const;914#endif915 916#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)917 void printFlags(raw_ostream &O) const;918#endif919};920 921/// A pure-virtual common base class for recipes defining a single VPValue and922/// using IR flags.923struct VPRecipeWithIRFlags : public VPSingleDefRecipe, public VPIRFlags {924 VPRecipeWithIRFlags(const unsigned char SC, ArrayRef<VPValue *> Operands,925 const VPIRFlags &Flags,926 DebugLoc DL = DebugLoc::getUnknown())927 : VPSingleDefRecipe(SC, Operands, DL), VPIRFlags(Flags) {}928 929 static inline bool classof(const VPRecipeBase *R) {930 return R->getVPDefID() == VPRecipeBase::VPInstructionSC ||931 R->getVPDefID() == VPRecipeBase::VPWidenSC ||932 R->getVPDefID() == VPRecipeBase::VPWidenGEPSC ||933 R->getVPDefID() == VPRecipeBase::VPWidenCallSC ||934 R->getVPDefID() == VPRecipeBase::VPWidenCastSC ||935 R->getVPDefID() == VPRecipeBase::VPWidenIntrinsicSC ||936 R->getVPDefID() == VPRecipeBase::VPWidenSelectSC ||937 R->getVPDefID() == VPRecipeBase::VPReductionSC ||938 R->getVPDefID() == VPRecipeBase::VPReductionEVLSC ||939 R->getVPDefID() == VPRecipeBase::VPReplicateSC ||940 R->getVPDefID() == VPRecipeBase::VPVectorEndPointerSC ||941 R->getVPDefID() == VPRecipeBase::VPVectorPointerSC;942 }943 944 static inline bool classof(const VPUser *U) {945 auto *R = dyn_cast<VPRecipeBase>(U);946 return R && classof(R);947 }948 949 static inline bool classof(const VPValue *V) {950 auto *R = dyn_cast_or_null<VPRecipeBase>(V->getDefiningRecipe());951 return R && classof(R);952 }953 954 VPRecipeWithIRFlags *clone() override = 0;955 956 static inline bool classof(const VPSingleDefRecipe *U) {957 auto *R = dyn_cast<VPRecipeBase>(U);958 return R && classof(R);959 }960 961 void execute(VPTransformState &State) override = 0;962 963 /// Compute the cost for this recipe for \p VF, using \p Opcode and \p Ctx.964 InstructionCost getCostForRecipeWithOpcode(unsigned Opcode, ElementCount VF,965 VPCostContext &Ctx) const;966};967 968/// Helper to access the operand that contains the unroll part for this recipe969/// after unrolling.970template <unsigned PartOpIdx> class LLVM_ABI_FOR_TEST VPUnrollPartAccessor {971protected:972 /// Return the VPValue operand containing the unroll part or null if there is973 /// no such operand.974 VPValue *getUnrollPartOperand(const VPUser &U) const;975 976 /// Return the unroll part.977 unsigned getUnrollPart(const VPUser &U) const;978};979 980/// Helper to manage IR metadata for recipes. It filters out metadata that981/// cannot be propagated.982class VPIRMetadata {983 SmallVector<std::pair<unsigned, MDNode *>> Metadata;984 985public:986 VPIRMetadata() = default;987 988 /// Adds metatadata that can be preserved from the original instruction989 /// \p I.990 VPIRMetadata(Instruction &I) { getMetadataToPropagate(&I, Metadata); }991 992 /// Copy constructor for cloning.993 VPIRMetadata(const VPIRMetadata &Other) = default;994 995 VPIRMetadata &operator=(const VPIRMetadata &Other) = default;996 997 /// Add all metadata to \p I.998 void applyMetadata(Instruction &I) const;999 1000 /// Set metadata with kind \p Kind to \p Node. If metadata with \p Kind1001 /// already exists, it will be replaced. Otherwise, it will be added.1002 void setMetadata(unsigned Kind, MDNode *Node) {1003 auto It =1004 llvm::find_if(Metadata, [Kind](const std::pair<unsigned, MDNode *> &P) {1005 return P.first == Kind;1006 });1007 if (It != Metadata.end())1008 It->second = Node;1009 else1010 Metadata.emplace_back(Kind, Node);1011 }1012 1013 /// Intersect this VPIRMetada object with \p MD, keeping only metadata1014 /// nodes that are common to both.1015 void intersect(const VPIRMetadata &MD);1016 1017 /// Get metadata of kind \p Kind. Returns nullptr if not found.1018 MDNode *getMetadata(unsigned Kind) const {1019 auto It =1020 find_if(Metadata, [Kind](const auto &P) { return P.first == Kind; });1021 return It != Metadata.end() ? It->second : nullptr;1022 }1023};1024 1025/// This is a concrete Recipe that models a single VPlan-level instruction.1026/// While as any Recipe it may generate a sequence of IR instructions when1027/// executed, these instructions would always form a single-def expression as1028/// the VPInstruction is also a single def-use vertex.1029class LLVM_ABI_FOR_TEST VPInstruction : public VPRecipeWithIRFlags,1030 public VPIRMetadata,1031 public VPUnrollPartAccessor<1> {1032 friend class VPlanSlp;1033 1034public:1035 /// VPlan opcodes, extending LLVM IR with idiomatics instructions.1036 enum {1037 FirstOrderRecurrenceSplice =1038 Instruction::OtherOpsEnd + 1, // Combines the incoming and previous1039 // values of a first-order recurrence.1040 Not,1041 SLPLoad,1042 SLPStore,1043 // Creates a mask where each lane is active (true) whilst the current1044 // counter (first operand + index) is less than the second operand. i.e.1045 // mask[i] = icmpt ult (op0 + i), op11046 // The size of the mask returned is VF * Multiplier (UF, third op).1047 ActiveLaneMask,1048 ExplicitVectorLength,1049 CalculateTripCountMinusVF,1050 // Increment the canonical IV separately for each unrolled part.1051 CanonicalIVIncrementForPart,1052 BranchOnCount,1053 BranchOnCond,1054 Broadcast,1055 /// Given operands of (the same) struct type, creates a struct of fixed-1056 /// width vectors each containing a struct field of all operands. The1057 /// number of operands matches the element count of every vector.1058 BuildStructVector,1059 /// Creates a fixed-width vector containing all operands. The number of1060 /// operands matches the vector element count.1061 BuildVector,1062 /// Extracts all lanes from its (non-scalable) vector operand. This is an1063 /// abstract VPInstruction whose single defined VPValue represents VF1064 /// scalars extracted from a vector, to be replaced by VF ExtractElement1065 /// VPInstructions.1066 Unpack,1067 /// Compute the final result of a AnyOf reduction with select(cmp(),x,y),1068 /// where one of (x,y) is loop invariant, and both x and y are integer type.1069 ComputeAnyOfResult,1070 ComputeFindIVResult,1071 ComputeReductionResult,1072 // Extracts the last lane from its operand if it is a vector, or the last1073 // part if scalar. In the latter case, the recipe will be removed during1074 // unrolling.1075 ExtractLastElement,1076 // Extracts the last lane for each part from its operand.1077 ExtractLastLanePerPart,1078 // Extracts the second-to-last lane from its operand or the second-to-last1079 // part if it is scalar. In the latter case, the recipe will be removed1080 // during unrolling.1081 ExtractPenultimateElement,1082 LogicalAnd, // Non-poison propagating logical And.1083 // Add an offset in bytes (second operand) to a base pointer (first1084 // operand). Only generates scalar values (either for the first lane only or1085 // for all lanes, depending on its uses).1086 PtrAdd,1087 // Add a vector offset in bytes (second operand) to a scalar base pointer1088 // (first operand).1089 WidePtrAdd,1090 // Returns a scalar boolean value, which is true if any lane of its1091 // (boolean) vector operands is true. It produces the reduced value across1092 // all unrolled iterations. Unrolling will add all copies of its original1093 // operand as additional operands. AnyOf is poison-safe as all operands1094 // will be frozen.1095 AnyOf,1096 // Calculates the first active lane index of the vector predicate operands.1097 // It produces the lane index across all unrolled iterations. Unrolling will1098 // add all copies of its original operand as additional operands.1099 // Implemented with @llvm.experimental.cttz.elts, but returns the expected1100 // result even with operands that are all zeroes.1101 FirstActiveLane,1102 // Calculates the last active lane index of the vector predicate operands.1103 // The predicates must be prefix-masks (all 1s before all 0s). Used when1104 // tail-folding to extract the correct live-out value from the last active1105 // iteration. It produces the lane index across all unrolled iterations.1106 // Unrolling will add all copies of its original operand as additional1107 // operands.1108 LastActiveLane,1109 1110 // The opcodes below are used for VPInstructionWithType.1111 //1112 /// Scale the first operand (vector step) by the second operand1113 /// (scalar-step). Casts both operands to the result type if needed.1114 WideIVStep,1115 /// Start vector for reductions with 3 operands: the original start value,1116 /// the identity value for the reduction and an integer indicating the1117 /// scaling factor.1118 ReductionStartVector,1119 // Creates a step vector starting from 0 to VF with a step of 1.1120 StepVector,1121 /// Extracts a single lane (first operand) from a set of vector operands.1122 /// The lane specifies an index into a vector formed by combining all vector1123 /// operands (all operands after the first one).1124 ExtractLane,1125 /// Explicit user for the resume phi of the canonical induction in the main1126 /// VPlan, used by the epilogue vector loop.1127 ResumeForEpilogue,1128 /// Returns the value for vscale.1129 VScale,1130 OpsEnd = VScale,1131 };1132 1133 /// Returns true if this VPInstruction generates scalar values for all lanes.1134 /// Most VPInstructions generate a single value per part, either vector or1135 /// scalar. VPReplicateRecipe takes care of generating multiple (scalar)1136 /// values per all lanes, stemming from an original ingredient. This method1137 /// identifies the (rare) cases of VPInstructions that do so as well, w/o an1138 /// underlying ingredient.1139 bool doesGeneratePerAllLanes() const;1140 1141private:1142 typedef unsigned char OpcodeTy;1143 OpcodeTy Opcode;1144 1145 /// An optional name that can be used for the generated IR instruction.1146 std::string Name;1147 1148 /// Returns true if we can generate a scalar for the first lane only if1149 /// needed.1150 bool canGenerateScalarForFirstLane() const;1151 1152 /// Utility methods serving execute(): generates a single vector instance of1153 /// the modeled instruction. \returns the generated value. . In some cases an1154 /// existing value is returned rather than a generated one.1155 Value *generate(VPTransformState &State);1156 1157#if !defined(NDEBUG)1158 /// Return the number of operands determined by the opcode of the1159 /// VPInstruction. Returns -1u if the number of operands cannot be determined1160 /// directly by the opcode.1161 static unsigned getNumOperandsForOpcode(unsigned Opcode);1162#endif1163 1164public:1165 VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands,1166 const VPIRFlags &Flags = {}, const VPIRMetadata &MD = {},1167 DebugLoc DL = DebugLoc::getUnknown(), const Twine &Name = "");1168 1169 VP_CLASSOF_IMPL(VPDef::VPInstructionSC)1170 1171 VPInstruction *clone() override {1172 auto *New = new VPInstruction(Opcode, operands(), *this, *this,1173 getDebugLoc(), Name);1174 if (getUnderlyingValue())1175 New->setUnderlyingValue(getUnderlyingInstr());1176 return New;1177 }1178 1179 unsigned getOpcode() const { return Opcode; }1180 1181 /// Generate the instruction.1182 /// TODO: We currently execute only per-part unless a specific instance is1183 /// provided.1184 void execute(VPTransformState &State) override;1185 1186 /// Return the cost of this VPInstruction.1187 InstructionCost computeCost(ElementCount VF,1188 VPCostContext &Ctx) const override;1189 1190#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1191 /// Print the VPInstruction to dbgs() (for debugging).1192 LLVM_DUMP_METHOD void dump() const;1193#endif1194 1195 bool hasResult() const {1196 // CallInst may or may not have a result, depending on the called function.1197 // Conservatively return calls have results for now.1198 switch (getOpcode()) {1199 case Instruction::Ret:1200 case Instruction::Br:1201 case Instruction::Store:1202 case Instruction::Switch:1203 case Instruction::IndirectBr:1204 case Instruction::Resume:1205 case Instruction::CatchRet:1206 case Instruction::Unreachable:1207 case Instruction::Fence:1208 case Instruction::AtomicRMW:1209 case VPInstruction::BranchOnCond:1210 case VPInstruction::BranchOnCount:1211 return false;1212 default:1213 return true;1214 }1215 }1216 1217 /// Returns true if the underlying opcode may read from or write to memory.1218 bool opcodeMayReadOrWriteFromMemory() const;1219 1220 /// Returns true if the recipe only uses the first lane of operand \p Op.1221 bool usesFirstLaneOnly(const VPValue *Op) const override;1222 1223 /// Returns true if the recipe only uses the first part of operand \p Op.1224 bool usesFirstPartOnly(const VPValue *Op) const override;1225 1226 /// Returns true if this VPInstruction produces a scalar value from a vector,1227 /// e.g. by performing a reduction or extracting a lane.1228 bool isVectorToScalar() const;1229 1230 /// Returns true if this VPInstruction's operands are single scalars and the1231 /// result is also a single scalar.1232 bool isSingleScalar() const;1233 1234 /// Returns the symbolic name assigned to the VPInstruction.1235 StringRef getName() const { return Name; }1236 1237 /// Set the symbolic name for the VPInstruction.1238 void setName(StringRef NewName) { Name = NewName.str(); }1239 1240protected:1241#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1242 /// Print the VPInstruction to \p O.1243 void printRecipe(raw_ostream &O, const Twine &Indent,1244 VPSlotTracker &SlotTracker) const override;1245#endif1246};1247 1248/// A specialization of VPInstruction augmenting it with a dedicated result1249/// type, to be used when the opcode and operands of the VPInstruction don't1250/// directly determine the result type. Note that there is no separate VPDef ID1251/// for VPInstructionWithType; it shares the same ID as VPInstruction and is1252/// distinguished purely by the opcode.1253class VPInstructionWithType : public VPInstruction {1254 /// Scalar result type produced by the recipe.1255 Type *ResultTy;1256 1257public:1258 VPInstructionWithType(unsigned Opcode, ArrayRef<VPValue *> Operands,1259 Type *ResultTy, const VPIRFlags &Flags = {},1260 const VPIRMetadata &Metadata = {},1261 DebugLoc DL = DebugLoc::getUnknown(),1262 const Twine &Name = "")1263 : VPInstruction(Opcode, Operands, Flags, Metadata, DL, Name),1264 ResultTy(ResultTy) {}1265 1266 static inline bool classof(const VPRecipeBase *R) {1267 // VPInstructionWithType are VPInstructions with specific opcodes requiring1268 // type information.1269 if (R->isScalarCast())1270 return true;1271 auto *VPI = dyn_cast<VPInstruction>(R);1272 if (!VPI)1273 return false;1274 switch (VPI->getOpcode()) {1275 case VPInstruction::WideIVStep:1276 case VPInstruction::StepVector:1277 case VPInstruction::VScale:1278 return true;1279 default:1280 return false;1281 }1282 }1283 1284 static inline bool classof(const VPUser *R) {1285 return isa<VPInstructionWithType>(cast<VPRecipeBase>(R));1286 }1287 1288 VPInstruction *clone() override {1289 auto *New =1290 new VPInstructionWithType(getOpcode(), operands(), getResultType(),1291 *this, *this, getDebugLoc(), getName());1292 New->setUnderlyingValue(getUnderlyingValue());1293 return New;1294 }1295 1296 void execute(VPTransformState &State) override;1297 1298 /// Return the cost of this VPInstruction.1299 InstructionCost computeCost(ElementCount VF,1300 VPCostContext &Ctx) const override {1301 // TODO: Compute accurate cost after retiring the legacy cost model.1302 return 0;1303 }1304 1305 Type *getResultType() const { return ResultTy; }1306 1307protected:1308#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1309 /// Print the recipe.1310 void printRecipe(raw_ostream &O, const Twine &Indent,1311 VPSlotTracker &SlotTracker) const override;1312#endif1313};1314 1315/// Helper type to provide functions to access incoming values and blocks for1316/// phi-like recipes.1317class VPPhiAccessors {1318protected:1319 /// Return a VPRecipeBase* to the current object.1320 virtual const VPRecipeBase *getAsRecipe() const = 0;1321 1322public:1323 virtual ~VPPhiAccessors() = default;1324 1325 /// Returns the incoming VPValue with index \p Idx.1326 VPValue *getIncomingValue(unsigned Idx) const {1327 return getAsRecipe()->getOperand(Idx);1328 }1329 1330 /// Returns the incoming block with index \p Idx.1331 const VPBasicBlock *getIncomingBlock(unsigned Idx) const;1332 1333 /// Returns the number of incoming values, also number of incoming blocks.1334 virtual unsigned getNumIncoming() const {1335 return getAsRecipe()->getNumOperands();1336 }1337 1338 /// Returns an interator range over the incoming values.1339 VPUser::const_operand_range incoming_values() const {1340 return make_range(getAsRecipe()->op_begin(),1341 getAsRecipe()->op_begin() + getNumIncoming());1342 }1343 1344 using const_incoming_blocks_range = iterator_range<mapped_iterator<1345 detail::index_iterator, std::function<const VPBasicBlock *(size_t)>>>;1346 1347 /// Returns an iterator range over the incoming blocks.1348 const_incoming_blocks_range incoming_blocks() const {1349 std::function<const VPBasicBlock *(size_t)> GetBlock = [this](size_t Idx) {1350 return getIncomingBlock(Idx);1351 };1352 return map_range(index_range(0, getNumIncoming()), GetBlock);1353 }1354 1355 /// Returns an iterator range over pairs of incoming values and corresponding1356 /// incoming blocks.1357 detail::zippy<llvm::detail::zip_first, VPUser::const_operand_range,1358 const_incoming_blocks_range>1359 incoming_values_and_blocks() const {1360 return zip_equal(incoming_values(), incoming_blocks());1361 }1362 1363 /// Removes the incoming value for \p IncomingBlock, which must be a1364 /// predecessor.1365 void removeIncomingValueFor(VPBlockBase *IncomingBlock) const;1366 1367#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1368 /// Print the recipe.1369 void printPhiOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;1370#endif1371};1372 1373struct LLVM_ABI_FOR_TEST VPPhi : public VPInstruction, public VPPhiAccessors {1374 VPPhi(ArrayRef<VPValue *> Operands, DebugLoc DL, const Twine &Name = "")1375 : VPInstruction(Instruction::PHI, Operands, {}, {}, DL, Name) {}1376 1377 static inline bool classof(const VPUser *U) {1378 auto *VPI = dyn_cast<VPInstruction>(U);1379 return VPI && VPI->getOpcode() == Instruction::PHI;1380 }1381 1382 static inline bool classof(const VPValue *V) {1383 auto *VPI = dyn_cast<VPInstruction>(V);1384 return VPI && VPI->getOpcode() == Instruction::PHI;1385 }1386 1387 static inline bool classof(const VPSingleDefRecipe *SDR) {1388 auto *VPI = dyn_cast<VPInstruction>(SDR);1389 return VPI && VPI->getOpcode() == Instruction::PHI;1390 }1391 1392 VPPhi *clone() override {1393 auto *PhiR = new VPPhi(operands(), getDebugLoc(), getName());1394 PhiR->setUnderlyingValue(getUnderlyingValue());1395 return PhiR;1396 }1397 1398 void execute(VPTransformState &State) override;1399 1400protected:1401#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1402 /// Print the recipe.1403 void printRecipe(raw_ostream &O, const Twine &Indent,1404 VPSlotTracker &SlotTracker) const override;1405#endif1406 1407 const VPRecipeBase *getAsRecipe() const override { return this; }1408};1409 1410/// A recipe to wrap on original IR instruction not to be modified during1411/// execution, except for PHIs. PHIs are modeled via the VPIRPhi subclass.1412/// Expect PHIs, VPIRInstructions cannot have any operands.1413class VPIRInstruction : public VPRecipeBase {1414 Instruction &I;1415 1416protected:1417 /// VPIRInstruction::create() should be used to create VPIRInstructions, as1418 /// subclasses may need to be created, e.g. VPIRPhi.1419 VPIRInstruction(Instruction &I)1420 : VPRecipeBase(VPDef::VPIRInstructionSC, ArrayRef<VPValue *>()), I(I) {}1421 1422public:1423 ~VPIRInstruction() override = default;1424 1425 /// Create a new VPIRPhi for \p \I, if it is a PHINode, otherwise create a1426 /// VPIRInstruction.1427 LLVM_ABI_FOR_TEST static VPIRInstruction *create(Instruction &I);1428 1429 VP_CLASSOF_IMPL(VPDef::VPIRInstructionSC)1430 1431 VPIRInstruction *clone() override {1432 auto *R = create(I);1433 for (auto *Op : operands())1434 R->addOperand(Op);1435 return R;1436 }1437 1438 void execute(VPTransformState &State) override;1439 1440 /// Return the cost of this VPIRInstruction.1441 LLVM_ABI_FOR_TEST InstructionCost1442 computeCost(ElementCount VF, VPCostContext &Ctx) const override;1443 1444 Instruction &getInstruction() const { return I; }1445 1446 bool usesScalars(const VPValue *Op) const override {1447 assert(is_contained(operands(), Op) &&1448 "Op must be an operand of the recipe");1449 return true;1450 }1451 1452 bool usesFirstPartOnly(const VPValue *Op) const override {1453 assert(is_contained(operands(), Op) &&1454 "Op must be an operand of the recipe");1455 return true;1456 }1457 1458 bool usesFirstLaneOnly(const VPValue *Op) const override {1459 assert(is_contained(operands(), Op) &&1460 "Op must be an operand of the recipe");1461 return true;1462 }1463 1464 /// Update the recipes first operand to the last lane of the operand using \p1465 /// Builder. Must only be used for VPIRInstructions with at least one operand1466 /// wrapping a PHINode.1467 void extractLastLaneOfFirstOperand(VPBuilder &Builder);1468 1469protected:1470#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1471 /// Print the recipe.1472 void printRecipe(raw_ostream &O, const Twine &Indent,1473 VPSlotTracker &SlotTracker) const override;1474#endif1475};1476 1477/// An overlay for VPIRInstructions wrapping PHI nodes enabling convenient use1478/// cast/dyn_cast/isa and execute() implementation. A single VPValue operand is1479/// allowed, and it is used to add a new incoming value for the single1480/// predecessor VPBB.1481struct LLVM_ABI_FOR_TEST VPIRPhi : public VPIRInstruction,1482 public VPPhiAccessors {1483 VPIRPhi(PHINode &PN) : VPIRInstruction(PN) {}1484 1485 static inline bool classof(const VPRecipeBase *U) {1486 auto *R = dyn_cast<VPIRInstruction>(U);1487 return R && isa<PHINode>(R->getInstruction());1488 }1489 1490 PHINode &getIRPhi() { return cast<PHINode>(getInstruction()); }1491 1492 void execute(VPTransformState &State) override;1493 1494protected:1495#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1496 /// Print the recipe.1497 void printRecipe(raw_ostream &O, const Twine &Indent,1498 VPSlotTracker &SlotTracker) const override;1499#endif1500 1501 const VPRecipeBase *getAsRecipe() const override { return this; }1502};1503 1504/// VPWidenRecipe is a recipe for producing a widened instruction using the1505/// opcode and operands of the recipe. This recipe covers most of the1506/// traditional vectorization cases where each recipe transforms into a1507/// vectorized version of itself.1508class LLVM_ABI_FOR_TEST VPWidenRecipe : public VPRecipeWithIRFlags,1509 public VPIRMetadata {1510 unsigned Opcode;1511 1512public:1513 VPWidenRecipe(unsigned Opcode, ArrayRef<VPValue *> Operands,1514 const VPIRFlags &Flags, const VPIRMetadata &Metadata,1515 DebugLoc DL)1516 : VPRecipeWithIRFlags(VPDef::VPWidenSC, Operands, Flags, DL),1517 VPIRMetadata(Metadata), Opcode(Opcode) {}1518 1519 VPWidenRecipe(Instruction &I, ArrayRef<VPValue *> Operands,1520 const VPIRFlags &Flags = {}, const VPIRMetadata &Metadata = {},1521 DebugLoc DL = {})1522 : VPRecipeWithIRFlags(VPDef::VPWidenSC, Operands, Flags, DL),1523 VPIRMetadata(Metadata), Opcode(I.getOpcode()) {1524 setUnderlyingValue(&I);1525 }1526 1527 ~VPWidenRecipe() override = default;1528 1529 VPWidenRecipe *clone() override {1530 auto *R =1531 new VPWidenRecipe(getOpcode(), operands(), *this, *this, getDebugLoc());1532 R->setUnderlyingValue(getUnderlyingValue());1533 return R;1534 }1535 1536 VP_CLASSOF_IMPL(VPDef::VPWidenSC)1537 1538 /// Produce a widened instruction using the opcode and operands of the recipe,1539 /// processing State.VF elements.1540 void execute(VPTransformState &State) override;1541 1542 /// Return the cost of this VPWidenRecipe.1543 InstructionCost computeCost(ElementCount VF,1544 VPCostContext &Ctx) const override;1545 1546 unsigned getOpcode() const { return Opcode; }1547 1548protected:1549#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1550 /// Print the recipe.1551 void printRecipe(raw_ostream &O, const Twine &Indent,1552 VPSlotTracker &SlotTracker) const override;1553#endif1554};1555 1556/// VPWidenCastRecipe is a recipe to create vector cast instructions.1557class VPWidenCastRecipe : public VPRecipeWithIRFlags, public VPIRMetadata {1558 /// Cast instruction opcode.1559 Instruction::CastOps Opcode;1560 1561 /// Result type for the cast.1562 Type *ResultTy;1563 1564public:1565 VPWidenCastRecipe(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy,1566 CastInst *CI = nullptr, const VPIRFlags &Flags = {},1567 const VPIRMetadata &Metadata = {},1568 DebugLoc DL = DebugLoc::getUnknown())1569 : VPRecipeWithIRFlags(VPDef::VPWidenCastSC, Op, Flags, DL),1570 VPIRMetadata(Metadata), Opcode(Opcode), ResultTy(ResultTy) {1571 assert(flagsValidForOpcode(Opcode) &&1572 "Set flags not supported for the provided opcode");1573 setUnderlyingValue(CI);1574 }1575 1576 ~VPWidenCastRecipe() override = default;1577 1578 VPWidenCastRecipe *clone() override {1579 return new VPWidenCastRecipe(Opcode, getOperand(0), ResultTy,1580 cast_or_null<CastInst>(getUnderlyingValue()),1581 *this, *this, getDebugLoc());1582 }1583 1584 VP_CLASSOF_IMPL(VPDef::VPWidenCastSC)1585 1586 /// Produce widened copies of the cast.1587 void execute(VPTransformState &State) override;1588 1589 /// Return the cost of this VPWidenCastRecipe.1590 InstructionCost computeCost(ElementCount VF,1591 VPCostContext &Ctx) const override;1592 1593 Instruction::CastOps getOpcode() const { return Opcode; }1594 1595 /// Returns the result type of the cast.1596 Type *getResultType() const { return ResultTy; }1597 1598protected:1599#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1600 /// Print the recipe.1601 void printRecipe(raw_ostream &O, const Twine &Indent,1602 VPSlotTracker &SlotTracker) const override;1603#endif1604};1605 1606/// A recipe for widening vector intrinsics.1607class VPWidenIntrinsicRecipe : public VPRecipeWithIRFlags, public VPIRMetadata {1608 /// ID of the vector intrinsic to widen.1609 Intrinsic::ID VectorIntrinsicID;1610 1611 /// Scalar return type of the intrinsic.1612 Type *ResultTy;1613 1614 /// True if the intrinsic may read from memory.1615 bool MayReadFromMemory;1616 1617 /// True if the intrinsic may read write to memory.1618 bool MayWriteToMemory;1619 1620 /// True if the intrinsic may have side-effects.1621 bool MayHaveSideEffects;1622 1623public:1624 VPWidenIntrinsicRecipe(CallInst &CI, Intrinsic::ID VectorIntrinsicID,1625 ArrayRef<VPValue *> CallArguments, Type *Ty,1626 const VPIRFlags &Flags = {},1627 const VPIRMetadata &MD = {},1628 DebugLoc DL = DebugLoc::getUnknown())1629 : VPRecipeWithIRFlags(VPDef::VPWidenIntrinsicSC, CallArguments, Flags,1630 DL),1631 VPIRMetadata(MD), VectorIntrinsicID(VectorIntrinsicID), ResultTy(Ty),1632 MayReadFromMemory(CI.mayReadFromMemory()),1633 MayWriteToMemory(CI.mayWriteToMemory()),1634 MayHaveSideEffects(CI.mayHaveSideEffects()) {1635 setUnderlyingValue(&CI);1636 }1637 1638 VPWidenIntrinsicRecipe(Intrinsic::ID VectorIntrinsicID,1639 ArrayRef<VPValue *> CallArguments, Type *Ty,1640 const VPIRFlags &Flags = {},1641 const VPIRMetadata &Metadata = {},1642 DebugLoc DL = DebugLoc::getUnknown())1643 : VPRecipeWithIRFlags(VPDef::VPWidenIntrinsicSC, CallArguments, Flags,1644 DL),1645 VPIRMetadata(Metadata), VectorIntrinsicID(VectorIntrinsicID),1646 ResultTy(Ty) {1647 LLVMContext &Ctx = Ty->getContext();1648 AttributeSet Attrs = Intrinsic::getFnAttributes(Ctx, VectorIntrinsicID);1649 MemoryEffects ME = Attrs.getMemoryEffects();1650 MayReadFromMemory = !ME.onlyWritesMemory();1651 MayWriteToMemory = !ME.onlyReadsMemory();1652 MayHaveSideEffects = MayWriteToMemory ||1653 !Attrs.hasAttribute(Attribute::NoUnwind) ||1654 !Attrs.hasAttribute(Attribute::WillReturn);1655 }1656 1657 ~VPWidenIntrinsicRecipe() override = default;1658 1659 VPWidenIntrinsicRecipe *clone() override {1660 if (Value *CI = getUnderlyingValue())1661 return new VPWidenIntrinsicRecipe(*cast<CallInst>(CI), VectorIntrinsicID,1662 operands(), ResultTy, *this, *this,1663 getDebugLoc());1664 return new VPWidenIntrinsicRecipe(VectorIntrinsicID, operands(), ResultTy,1665 *this, *this, getDebugLoc());1666 }1667 1668 VP_CLASSOF_IMPL(VPDef::VPWidenIntrinsicSC)1669 1670 /// Produce a widened version of the vector intrinsic.1671 void execute(VPTransformState &State) override;1672 1673 /// Return the cost of this vector intrinsic.1674 InstructionCost computeCost(ElementCount VF,1675 VPCostContext &Ctx) const override;1676 1677 /// Return the ID of the intrinsic.1678 Intrinsic::ID getVectorIntrinsicID() const { return VectorIntrinsicID; }1679 1680 /// Return the scalar return type of the intrinsic.1681 Type *getResultType() const { return ResultTy; }1682 1683 /// Return to name of the intrinsic as string.1684 StringRef getIntrinsicName() const;1685 1686 /// Returns true if the intrinsic may read from memory.1687 bool mayReadFromMemory() const { return MayReadFromMemory; }1688 1689 /// Returns true if the intrinsic may write to memory.1690 bool mayWriteToMemory() const { return MayWriteToMemory; }1691 1692 /// Returns true if the intrinsic may have side-effects.1693 bool mayHaveSideEffects() const { return MayHaveSideEffects; }1694 1695 bool usesFirstLaneOnly(const VPValue *Op) const override;1696 1697protected:1698#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1699 /// Print the recipe.1700 void printRecipe(raw_ostream &O, const Twine &Indent,1701 VPSlotTracker &SlotTracker) const override;1702#endif1703};1704 1705/// A recipe for widening Call instructions using library calls.1706class LLVM_ABI_FOR_TEST VPWidenCallRecipe : public VPRecipeWithIRFlags,1707 public VPIRMetadata {1708 /// Variant stores a pointer to the chosen function. There is a 1:1 mapping1709 /// between a given VF and the chosen vectorized variant, so there will be a1710 /// different VPlan for each VF with a valid variant.1711 Function *Variant;1712 1713public:1714 VPWidenCallRecipe(Value *UV, Function *Variant,1715 ArrayRef<VPValue *> CallArguments,1716 const VPIRFlags &Flags = {},1717 const VPIRMetadata &Metadata = {}, DebugLoc DL = {})1718 : VPRecipeWithIRFlags(VPDef::VPWidenCallSC, CallArguments, Flags, DL),1719 VPIRMetadata(Metadata), Variant(Variant) {1720 setUnderlyingValue(UV);1721 assert(1722 isa<Function>(getOperand(getNumOperands() - 1)->getLiveInIRValue()) &&1723 "last operand must be the called function");1724 }1725 1726 ~VPWidenCallRecipe() override = default;1727 1728 VPWidenCallRecipe *clone() override {1729 return new VPWidenCallRecipe(getUnderlyingValue(), Variant, operands(),1730 *this, *this, getDebugLoc());1731 }1732 1733 VP_CLASSOF_IMPL(VPDef::VPWidenCallSC)1734 1735 /// Produce a widened version of the call instruction.1736 void execute(VPTransformState &State) override;1737 1738 /// Return the cost of this VPWidenCallRecipe.1739 InstructionCost computeCost(ElementCount VF,1740 VPCostContext &Ctx) const override;1741 1742 Function *getCalledScalarFunction() const {1743 return cast<Function>(getOperand(getNumOperands() - 1)->getLiveInIRValue());1744 }1745 1746 operand_range args() { return drop_end(operands()); }1747 const_operand_range args() const { return drop_end(operands()); }1748 1749protected:1750#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1751 /// Print the recipe.1752 void printRecipe(raw_ostream &O, const Twine &Indent,1753 VPSlotTracker &SlotTracker) const override;1754#endif1755};1756 1757/// A recipe representing a sequence of load -> update -> store as part of1758/// a histogram operation. This means there may be aliasing between vector1759/// lanes, which is handled by the llvm.experimental.vector.histogram family1760/// of intrinsics. The only update operations currently supported are1761/// 'add' and 'sub' where the other term is loop-invariant.1762class VPHistogramRecipe : public VPRecipeBase {1763 /// Opcode of the update operation, currently either add or sub.1764 unsigned Opcode;1765 1766public:1767 VPHistogramRecipe(unsigned Opcode, ArrayRef<VPValue *> Operands,1768 DebugLoc DL = DebugLoc::getUnknown())1769 : VPRecipeBase(VPDef::VPHistogramSC, Operands, DL), Opcode(Opcode) {}1770 1771 ~VPHistogramRecipe() override = default;1772 1773 VPHistogramRecipe *clone() override {1774 return new VPHistogramRecipe(Opcode, operands(), getDebugLoc());1775 }1776 1777 VP_CLASSOF_IMPL(VPDef::VPHistogramSC);1778 1779 /// Produce a vectorized histogram operation.1780 void execute(VPTransformState &State) override;1781 1782 /// Return the cost of this VPHistogramRecipe.1783 InstructionCost computeCost(ElementCount VF,1784 VPCostContext &Ctx) const override;1785 1786 unsigned getOpcode() const { return Opcode; }1787 1788 /// Return the mask operand if one was provided, or a null pointer if all1789 /// lanes should be executed unconditionally.1790 VPValue *getMask() const {1791 return getNumOperands() == 3 ? getOperand(2) : nullptr;1792 }1793 1794protected:1795#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1796 /// Print the recipe1797 void printRecipe(raw_ostream &O, const Twine &Indent,1798 VPSlotTracker &SlotTracker) const override;1799#endif1800};1801 1802/// A recipe for widening select instructions. Supports both wide vector and1803/// single-scalar conditions, matching the behavior of LLVM IR's select1804/// instruction.1805struct LLVM_ABI_FOR_TEST VPWidenSelectRecipe : public VPRecipeWithIRFlags,1806 public VPIRMetadata {1807 VPWidenSelectRecipe(SelectInst *SI, ArrayRef<VPValue *> Operands,1808 const VPIRFlags &Flags = {}, const VPIRMetadata &MD = {},1809 DebugLoc DL = {})1810 : VPRecipeWithIRFlags(VPDef::VPWidenSelectSC, Operands, Flags, DL),1811 VPIRMetadata(MD) {1812 setUnderlyingValue(SI);1813 }1814 1815 ~VPWidenSelectRecipe() override = default;1816 1817 VPWidenSelectRecipe *clone() override {1818 return new VPWidenSelectRecipe(cast<SelectInst>(getUnderlyingInstr()),1819 operands(), *this, *this, getDebugLoc());1820 }1821 1822 VP_CLASSOF_IMPL(VPDef::VPWidenSelectSC)1823 1824 /// Produce a widened version of the select instruction.1825 void execute(VPTransformState &State) override;1826 1827 /// Return the cost of this VPWidenSelectRecipe.1828 InstructionCost computeCost(ElementCount VF,1829 VPCostContext &Ctx) const override;1830 1831 unsigned getOpcode() const { return Instruction::Select; }1832 1833 VPValue *getCond() const {1834 return getOperand(0);1835 }1836 1837 /// Returns true if the recipe only uses the first lane of operand \p Op.1838 bool usesFirstLaneOnly(const VPValue *Op) const override {1839 assert(is_contained(operands(), Op) &&1840 "Op must be an operand of the recipe");1841 return Op == getCond() && Op->isDefinedOutsideLoopRegions();1842 }1843 1844protected:1845#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1846 /// Print the recipe.1847 void printRecipe(raw_ostream &O, const Twine &Indent,1848 VPSlotTracker &SlotTracker) const override;1849#endif1850};1851 1852/// A recipe for handling GEP instructions.1853class LLVM_ABI_FOR_TEST VPWidenGEPRecipe : public VPRecipeWithIRFlags {1854 Type *SourceElementTy;1855 1856 bool isPointerLoopInvariant() const {1857 return getOperand(0)->isDefinedOutsideLoopRegions();1858 }1859 1860 bool isIndexLoopInvariant(unsigned I) const {1861 return getOperand(I + 1)->isDefinedOutsideLoopRegions();1862 }1863 1864public:1865 VPWidenGEPRecipe(GetElementPtrInst *GEP, ArrayRef<VPValue *> Operands,1866 const VPIRFlags &Flags = {},1867 DebugLoc DL = DebugLoc::getUnknown())1868 : VPRecipeWithIRFlags(VPDef::VPWidenGEPSC, Operands, Flags, DL),1869 SourceElementTy(GEP->getSourceElementType()) {1870 setUnderlyingValue(GEP);1871 SmallVector<std::pair<unsigned, MDNode *>> Metadata;1872 (void)Metadata;1873 getMetadataToPropagate(GEP, Metadata);1874 assert(Metadata.empty() && "unexpected metadata on GEP");1875 }1876 1877 ~VPWidenGEPRecipe() override = default;1878 1879 VPWidenGEPRecipe *clone() override {1880 return new VPWidenGEPRecipe(cast<GetElementPtrInst>(getUnderlyingInstr()),1881 operands(), *this, getDebugLoc());1882 }1883 1884 VP_CLASSOF_IMPL(VPDef::VPWidenGEPSC)1885 1886 /// This recipe generates a GEP instruction.1887 unsigned getOpcode() const { return Instruction::GetElementPtr; }1888 1889 /// Generate the gep nodes.1890 void execute(VPTransformState &State) override;1891 1892 Type *getSourceElementType() const { return SourceElementTy; }1893 1894 /// Return the cost of this VPWidenGEPRecipe.1895 InstructionCost computeCost(ElementCount VF,1896 VPCostContext &Ctx) const override {1897 // TODO: Compute accurate cost after retiring the legacy cost model.1898 return 0;1899 }1900 1901 /// Returns true if the recipe only uses the first lane of operand \p Op.1902 bool usesFirstLaneOnly(const VPValue *Op) const override;1903 1904protected:1905#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1906 /// Print the recipe.1907 void printRecipe(raw_ostream &O, const Twine &Indent,1908 VPSlotTracker &SlotTracker) const override;1909#endif1910};1911 1912/// A recipe to compute a pointer to the last element of each part of a widened1913/// memory access for widened memory accesses of IndexedTy. Used for1914/// VPWidenMemoryRecipes or VPInterleaveRecipes that are reversed.1915class VPVectorEndPointerRecipe : public VPRecipeWithIRFlags,1916 public VPUnrollPartAccessor<2> {1917 Type *IndexedTy;1918 1919 /// The constant stride of the pointer computed by this recipe, expressed in1920 /// units of IndexedTy.1921 int64_t Stride;1922 1923public:1924 VPVectorEndPointerRecipe(VPValue *Ptr, VPValue *VF, Type *IndexedTy,1925 int64_t Stride, GEPNoWrapFlags GEPFlags, DebugLoc DL)1926 : VPRecipeWithIRFlags(VPDef::VPVectorEndPointerSC,1927 ArrayRef<VPValue *>({Ptr, VF}), GEPFlags, DL),1928 IndexedTy(IndexedTy), Stride(Stride) {1929 assert(Stride < 0 && "Stride must be negative");1930 }1931 1932 VP_CLASSOF_IMPL(VPDef::VPVectorEndPointerSC)1933 1934 VPValue *getVFValue() { return getOperand(1); }1935 const VPValue *getVFValue() const { return getOperand(1); }1936 1937 void execute(VPTransformState &State) override;1938 1939 bool usesFirstLaneOnly(const VPValue *Op) const override {1940 assert(is_contained(operands(), Op) &&1941 "Op must be an operand of the recipe");1942 return true;1943 }1944 1945 /// Return the cost of this VPVectorPointerRecipe.1946 InstructionCost computeCost(ElementCount VF,1947 VPCostContext &Ctx) const override {1948 // TODO: Compute accurate cost after retiring the legacy cost model.1949 return 0;1950 }1951 1952 /// Returns true if the recipe only uses the first part of operand \p Op.1953 bool usesFirstPartOnly(const VPValue *Op) const override {1954 assert(is_contained(operands(), Op) &&1955 "Op must be an operand of the recipe");1956 assert(getNumOperands() <= 2 && "must have at most two operands");1957 return true;1958 }1959 1960 VPVectorEndPointerRecipe *clone() override {1961 return new VPVectorEndPointerRecipe(getOperand(0), getVFValue(), IndexedTy,1962 Stride, getGEPNoWrapFlags(),1963 getDebugLoc());1964 }1965 1966protected:1967#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1968 /// Print the recipe.1969 void printRecipe(raw_ostream &O, const Twine &Indent,1970 VPSlotTracker &SlotTracker) const override;1971#endif1972};1973 1974/// A recipe to compute the pointers for widened memory accesses of IndexTy.1975class VPVectorPointerRecipe : public VPRecipeWithIRFlags,1976 public VPUnrollPartAccessor<1> {1977 Type *SourceElementTy;1978 1979public:1980 VPVectorPointerRecipe(VPValue *Ptr, Type *SourceElementTy,1981 GEPNoWrapFlags GEPFlags, DebugLoc DL)1982 : VPRecipeWithIRFlags(VPDef::VPVectorPointerSC, ArrayRef<VPValue *>(Ptr),1983 GEPFlags, DL),1984 SourceElementTy(SourceElementTy) {}1985 1986 VP_CLASSOF_IMPL(VPDef::VPVectorPointerSC)1987 1988 void execute(VPTransformState &State) override;1989 1990 Type *getSourceElementType() const { return SourceElementTy; }1991 1992 bool usesFirstLaneOnly(const VPValue *Op) const override {1993 assert(is_contained(operands(), Op) &&1994 "Op must be an operand of the recipe");1995 return true;1996 }1997 1998 /// Returns true if the recipe only uses the first part of operand \p Op.1999 bool usesFirstPartOnly(const VPValue *Op) const override {2000 assert(is_contained(operands(), Op) &&2001 "Op must be an operand of the recipe");2002 assert(getNumOperands() <= 2 && "must have at most two operands");2003 return true;2004 }2005 2006 VPVectorPointerRecipe *clone() override {2007 return new VPVectorPointerRecipe(getOperand(0), SourceElementTy,2008 getGEPNoWrapFlags(), getDebugLoc());2009 }2010 2011 /// Return true if this VPVectorPointerRecipe corresponds to part 0. Note that2012 /// this is only accurate after the VPlan has been unrolled.2013 bool isFirstPart() const { return getUnrollPart(*this) == 0; }2014 2015 /// Return the cost of this VPHeaderPHIRecipe.2016 InstructionCost computeCost(ElementCount VF,2017 VPCostContext &Ctx) const override {2018 // TODO: Compute accurate cost after retiring the legacy cost model.2019 return 0;2020 }2021 2022protected:2023#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2024 /// Print the recipe.2025 void printRecipe(raw_ostream &O, const Twine &Indent,2026 VPSlotTracker &SlotTracker) const override;2027#endif2028};2029 2030/// A pure virtual base class for all recipes modeling header phis, including2031/// phis for first order recurrences, pointer inductions and reductions. The2032/// start value is the first operand of the recipe and the incoming value from2033/// the backedge is the second operand.2034///2035/// Inductions are modeled using the following sub-classes:2036/// * VPCanonicalIVPHIRecipe: Canonical scalar induction of the vector loop,2037/// starting at a specified value (zero for the main vector loop, the resume2038/// value for the epilogue vector loop) and stepping by 1. The induction2039/// controls exiting of the vector loop by comparing against the vector trip2040/// count. Produces a single scalar PHI for the induction value per2041/// iteration.2042/// * VPWidenIntOrFpInductionRecipe: Generates vector values for integer and2043/// floating point inductions with arbitrary start and step values. Produces2044/// a vector PHI per-part.2045/// * VPDerivedIVRecipe: Converts the canonical IV value to the corresponding2046/// value of an IV with different start and step values. Produces a single2047/// scalar value per iteration2048/// * VPScalarIVStepsRecipe: Generates scalar values per-lane based on a2049/// canonical or derived induction.2050/// * VPWidenPointerInductionRecipe: Generate vector and scalar values for a2051/// pointer induction. Produces either a vector PHI per-part or scalar values2052/// per-lane based on the canonical induction.2053class LLVM_ABI_FOR_TEST VPHeaderPHIRecipe : public VPSingleDefRecipe,2054 public VPPhiAccessors {2055protected:2056 VPHeaderPHIRecipe(unsigned char VPDefID, Instruction *UnderlyingInstr,2057 VPValue *Start, DebugLoc DL = DebugLoc::getUnknown())2058 : VPSingleDefRecipe(VPDefID, ArrayRef<VPValue *>({Start}),2059 UnderlyingInstr, DL) {}2060 2061 const VPRecipeBase *getAsRecipe() const override { return this; }2062 2063public:2064 ~VPHeaderPHIRecipe() override = default;2065 2066 /// Method to support type inquiry through isa, cast, and dyn_cast.2067 static inline bool classof(const VPRecipeBase *R) {2068 return R->getVPDefID() >= VPDef::VPFirstHeaderPHISC &&2069 R->getVPDefID() <= VPDef::VPLastHeaderPHISC;2070 }2071 static inline bool classof(const VPValue *V) {2072 return isa<VPHeaderPHIRecipe>(V->getDefiningRecipe());2073 }2074 static inline bool classof(const VPSingleDefRecipe *R) {2075 return isa<VPHeaderPHIRecipe>(static_cast<const VPRecipeBase *>(R));2076 }2077 2078 /// Generate the phi nodes.2079 void execute(VPTransformState &State) override = 0;2080 2081 /// Return the cost of this header phi recipe.2082 InstructionCost computeCost(ElementCount VF,2083 VPCostContext &Ctx) const override;2084 2085 /// Returns the start value of the phi, if one is set.2086 VPValue *getStartValue() {2087 return getNumOperands() == 0 ? nullptr : getOperand(0);2088 }2089 VPValue *getStartValue() const {2090 return getNumOperands() == 0 ? nullptr : getOperand(0);2091 }2092 2093 /// Update the start value of the recipe.2094 void setStartValue(VPValue *V) { setOperand(0, V); }2095 2096 /// Returns the incoming value from the loop backedge.2097 virtual VPValue *getBackedgeValue() {2098 return getOperand(1);2099 }2100 2101 /// Update the incoming value from the loop backedge.2102 void setBackedgeValue(VPValue *V) { setOperand(1, V); }2103 2104 /// Returns the backedge value as a recipe. The backedge value is guaranteed2105 /// to be a recipe.2106 virtual VPRecipeBase &getBackedgeRecipe() {2107 return *getBackedgeValue()->getDefiningRecipe();2108 }2109 2110protected:2111#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2112 /// Print the recipe.2113 void printRecipe(raw_ostream &O, const Twine &Indent,2114 VPSlotTracker &SlotTracker) const override = 0;2115#endif2116};2117 2118/// Base class for widened induction (VPWidenIntOrFpInductionRecipe and2119/// VPWidenPointerInductionRecipe), providing shared functionality, including2120/// retrieving the step value, induction descriptor and original phi node.2121class VPWidenInductionRecipe : public VPHeaderPHIRecipe {2122 const InductionDescriptor &IndDesc;2123 2124public:2125 VPWidenInductionRecipe(unsigned char Kind, PHINode *IV, VPValue *Start,2126 VPValue *Step, const InductionDescriptor &IndDesc,2127 DebugLoc DL)2128 : VPHeaderPHIRecipe(Kind, IV, Start, DL), IndDesc(IndDesc) {2129 addOperand(Step);2130 }2131 2132 static inline bool classof(const VPRecipeBase *R) {2133 return R->getVPDefID() == VPDef::VPWidenIntOrFpInductionSC ||2134 R->getVPDefID() == VPDef::VPWidenPointerInductionSC;2135 }2136 2137 static inline bool classof(const VPValue *V) {2138 auto *R = V->getDefiningRecipe();2139 return R && classof(R);2140 }2141 2142 static inline bool classof(const VPSingleDefRecipe *R) {2143 return classof(static_cast<const VPRecipeBase *>(R));2144 }2145 2146 void execute(VPTransformState &State) override = 0;2147 2148 /// Returns the step value of the induction.2149 VPValue *getStepValue() { return getOperand(1); }2150 const VPValue *getStepValue() const { return getOperand(1); }2151 2152 /// Update the step value of the recipe.2153 void setStepValue(VPValue *V) { setOperand(1, V); }2154 2155 VPValue *getVFValue() { return getOperand(2); }2156 const VPValue *getVFValue() const { return getOperand(2); }2157 2158 /// Returns the number of incoming values, also number of incoming blocks.2159 /// Note that at the moment, VPWidenPointerInductionRecipe only has a single2160 /// incoming value, its start value.2161 unsigned getNumIncoming() const override { return 1; }2162 2163 PHINode *getPHINode() const { return cast<PHINode>(getUnderlyingValue()); }2164 2165 /// Returns the induction descriptor for the recipe.2166 const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }2167 2168 VPValue *getBackedgeValue() override {2169 // TODO: All operands of base recipe must exist and be at same index in2170 // derived recipe.2171 llvm_unreachable(2172 "VPWidenIntOrFpInductionRecipe generates its own backedge value");2173 }2174 2175 VPRecipeBase &getBackedgeRecipe() override {2176 // TODO: All operands of base recipe must exist and be at same index in2177 // derived recipe.2178 llvm_unreachable(2179 "VPWidenIntOrFpInductionRecipe generates its own backedge value");2180 }2181 2182 /// Returns true if the recipe only uses the first lane of operand \p Op.2183 bool usesFirstLaneOnly(const VPValue *Op) const override {2184 assert(is_contained(operands(), Op) &&2185 "Op must be an operand of the recipe");2186 // The recipe creates its own wide start value, so it only requests the2187 // first lane of the operand.2188 // TODO: Remove once creating the start value is modeled separately.2189 return Op == getStartValue() || Op == getStepValue();2190 }2191};2192 2193/// A recipe for handling phi nodes of integer and floating-point inductions,2194/// producing their vector values. This is an abstract recipe and must be2195/// converted to concrete recipes before executing.2196class VPWidenIntOrFpInductionRecipe : public VPWidenInductionRecipe,2197 public VPIRFlags {2198 TruncInst *Trunc;2199 2200 // If this recipe is unrolled it will have 2 additional operands.2201 bool isUnrolled() const { return getNumOperands() == 5; }2202 2203public:2204 VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step,2205 VPValue *VF, const InductionDescriptor &IndDesc,2206 const VPIRFlags &Flags, DebugLoc DL)2207 : VPWidenInductionRecipe(VPDef::VPWidenIntOrFpInductionSC, IV, Start,2208 Step, IndDesc, DL),2209 VPIRFlags(Flags), Trunc(nullptr) {2210 addOperand(VF);2211 }2212 2213 VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step,2214 VPValue *VF, const InductionDescriptor &IndDesc,2215 TruncInst *Trunc, const VPIRFlags &Flags,2216 DebugLoc DL)2217 : VPWidenInductionRecipe(VPDef::VPWidenIntOrFpInductionSC, IV, Start,2218 Step, IndDesc, DL),2219 VPIRFlags(Flags), Trunc(Trunc) {2220 addOperand(VF);2221 SmallVector<std::pair<unsigned, MDNode *>> Metadata;2222 (void)Metadata;2223 if (Trunc)2224 getMetadataToPropagate(Trunc, Metadata);2225 assert(Metadata.empty() && "unexpected metadata on Trunc");2226 }2227 2228 ~VPWidenIntOrFpInductionRecipe() override = default;2229 2230 VPWidenIntOrFpInductionRecipe *clone() override {2231 return new VPWidenIntOrFpInductionRecipe(2232 getPHINode(), getStartValue(), getStepValue(), getVFValue(),2233 getInductionDescriptor(), Trunc, *this, getDebugLoc());2234 }2235 2236 VP_CLASSOF_IMPL(VPDef::VPWidenIntOrFpInductionSC)2237 2238 void execute(VPTransformState &State) override {2239 llvm_unreachable("cannot execute this recipe, should be expanded via "2240 "expandVPWidenIntOrFpInductionRecipe");2241 }2242 2243 VPValue *getSplatVFValue() {2244 // If the recipe has been unrolled return the VPValue for the induction2245 // increment.2246 return isUnrolled() ? getOperand(getNumOperands() - 2) : nullptr;2247 }2248 2249 /// Returns the number of incoming values, also number of incoming blocks.2250 /// Note that at the moment, VPWidenIntOrFpInductionRecipes only have a single2251 /// incoming value, its start value.2252 unsigned getNumIncoming() const override { return 1; }2253 2254 /// Returns the first defined value as TruncInst, if it is one or nullptr2255 /// otherwise.2256 TruncInst *getTruncInst() { return Trunc; }2257 const TruncInst *getTruncInst() const { return Trunc; }2258 2259 /// Returns true if the induction is canonical, i.e. starting at 0 and2260 /// incremented by UF * VF (= the original IV is incremented by 1) and has the2261 /// same type as the canonical induction.2262 bool isCanonical() const;2263 2264 /// Returns the scalar type of the induction.2265 Type *getScalarType() const {2266 return Trunc ? Trunc->getType()2267 : getStartValue()->getLiveInIRValue()->getType();2268 }2269 2270 /// Returns the VPValue representing the value of this induction at2271 /// the last unrolled part, if it exists. Returns itself if unrolling did not2272 /// take place.2273 VPValue *getLastUnrolledPartOperand() {2274 return isUnrolled() ? getOperand(getNumOperands() - 1) : this;2275 }2276 2277protected:2278#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2279 /// Print the recipe.2280 void printRecipe(raw_ostream &O, const Twine &Indent,2281 VPSlotTracker &SlotTracker) const override;2282#endif2283};2284 2285class VPWidenPointerInductionRecipe : public VPWidenInductionRecipe {2286public:2287 /// Create a new VPWidenPointerInductionRecipe for \p Phi with start value \p2288 /// Start and the number of elements unrolled \p NumUnrolledElems, typically2289 /// VF*UF.2290 VPWidenPointerInductionRecipe(PHINode *Phi, VPValue *Start, VPValue *Step,2291 VPValue *NumUnrolledElems,2292 const InductionDescriptor &IndDesc, DebugLoc DL)2293 : VPWidenInductionRecipe(VPDef::VPWidenPointerInductionSC, Phi, Start,2294 Step, IndDesc, DL) {2295 addOperand(NumUnrolledElems);2296 }2297 2298 ~VPWidenPointerInductionRecipe() override = default;2299 2300 VPWidenPointerInductionRecipe *clone() override {2301 return new VPWidenPointerInductionRecipe(2302 cast<PHINode>(getUnderlyingInstr()), getOperand(0), getOperand(1),2303 getOperand(2), getInductionDescriptor(), getDebugLoc());2304 }2305 2306 VP_CLASSOF_IMPL(VPDef::VPWidenPointerInductionSC)2307 2308 /// Generate vector values for the pointer induction.2309 void execute(VPTransformState &State) override {2310 llvm_unreachable("cannot execute this recipe, should be expanded via "2311 "expandVPWidenPointerInduction");2312 };2313 2314 /// Returns true if only scalar values will be generated.2315 bool onlyScalarsGenerated(bool IsScalable);2316 2317protected:2318#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2319 /// Print the recipe.2320 void printRecipe(raw_ostream &O, const Twine &Indent,2321 VPSlotTracker &SlotTracker) const override;2322#endif2323};2324 2325/// A recipe for widened phis. Incoming values are operands of the recipe and2326/// their operand index corresponds to the incoming predecessor block. If the2327/// recipe is placed in an entry block to a (non-replicate) region, it must have2328/// exactly 2 incoming values, the first from the predecessor of the region and2329/// the second from the exiting block of the region.2330class LLVM_ABI_FOR_TEST VPWidenPHIRecipe : public VPSingleDefRecipe,2331 public VPPhiAccessors {2332 /// Name to use for the generated IR instruction for the widened phi.2333 std::string Name;2334 2335public:2336 /// Create a new VPWidenPHIRecipe for \p Phi with start value \p Start and2337 /// debug location \p DL.2338 VPWidenPHIRecipe(PHINode *Phi, VPValue *Start = nullptr,2339 DebugLoc DL = DebugLoc::getUnknown(), const Twine &Name = "")2340 : VPSingleDefRecipe(VPDef::VPWidenPHISC, {}, Phi, DL), Name(Name.str()) {2341 if (Start)2342 addOperand(Start);2343 }2344 2345 VPWidenPHIRecipe *clone() override {2346 auto *C = new VPWidenPHIRecipe(cast<PHINode>(getUnderlyingValue()),2347 getOperand(0), getDebugLoc(), Name);2348 for (VPValue *Op : llvm::drop_begin(operands()))2349 C->addOperand(Op);2350 return C;2351 }2352 2353 ~VPWidenPHIRecipe() override = default;2354 2355 VP_CLASSOF_IMPL(VPDef::VPWidenPHISC)2356 2357 /// Generate the phi/select nodes.2358 void execute(VPTransformState &State) override;2359 2360protected:2361#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2362 /// Print the recipe.2363 void printRecipe(raw_ostream &O, const Twine &Indent,2364 VPSlotTracker &SlotTracker) const override;2365#endif2366 2367 const VPRecipeBase *getAsRecipe() const override { return this; }2368};2369 2370/// A recipe for handling first-order recurrence phis. The start value is the2371/// first operand of the recipe and the incoming value from the backedge is the2372/// second operand.2373struct VPFirstOrderRecurrencePHIRecipe : public VPHeaderPHIRecipe {2374 VPFirstOrderRecurrencePHIRecipe(PHINode *Phi, VPValue &Start)2375 : VPHeaderPHIRecipe(VPDef::VPFirstOrderRecurrencePHISC, Phi, &Start) {}2376 2377 VP_CLASSOF_IMPL(VPDef::VPFirstOrderRecurrencePHISC)2378 2379 VPFirstOrderRecurrencePHIRecipe *clone() override {2380 return new VPFirstOrderRecurrencePHIRecipe(2381 cast<PHINode>(getUnderlyingInstr()), *getOperand(0));2382 }2383 2384 void execute(VPTransformState &State) override;2385 2386 /// Return the cost of this first-order recurrence phi recipe.2387 InstructionCost computeCost(ElementCount VF,2388 VPCostContext &Ctx) const override;2389 2390 /// Returns true if the recipe only uses the first lane of operand \p Op.2391 bool usesFirstLaneOnly(const VPValue *Op) const override {2392 assert(is_contained(operands(), Op) &&2393 "Op must be an operand of the recipe");2394 return Op == getStartValue();2395 }2396 2397protected:2398#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2399 /// Print the recipe.2400 void printRecipe(raw_ostream &O, const Twine &Indent,2401 VPSlotTracker &SlotTracker) const override;2402#endif2403};2404 2405/// Possible variants of a reduction.2406 2407/// This reduction is ordered and in-loop.2408struct RdxOrdered {};2409/// This reduction is in-loop.2410struct RdxInLoop {};2411/// This reduction is unordered with the partial result scaled down by some2412/// factor.2413struct RdxUnordered {2414 unsigned VFScaleFactor;2415};2416using ReductionStyle = std::variant<RdxOrdered, RdxInLoop, RdxUnordered>;2417 2418inline ReductionStyle getReductionStyle(bool InLoop, bool Ordered,2419 unsigned ScaleFactor) {2420 assert((!Ordered || InLoop) && "Ordered implies in-loop");2421 if (Ordered)2422 return RdxOrdered{};2423 if (InLoop)2424 return RdxInLoop{};2425 return RdxUnordered{/*VFScaleFactor=*/ScaleFactor};2426}2427 2428/// A recipe for handling reduction phis. The start value is the first operand2429/// of the recipe and the incoming value from the backedge is the second2430/// operand.2431class VPReductionPHIRecipe : public VPHeaderPHIRecipe,2432 public VPUnrollPartAccessor<2> {2433 /// The recurrence kind of the reduction.2434 const RecurKind Kind;2435 2436 ReductionStyle Style;2437 2438 /// The phi is part of a multi-use reduction (e.g., used in FindLastIV2439 /// patterns for argmin/argmax).2440 /// TODO: Also support cases where the phi itself has a single use, but its2441 /// compare has multiple uses.2442 bool HasUsesOutsideReductionChain;2443 2444public:2445 /// Create a new VPReductionPHIRecipe for the reduction \p Phi.2446 VPReductionPHIRecipe(PHINode *Phi, RecurKind Kind, VPValue &Start,2447 ReductionStyle Style,2448 bool HasUsesOutsideReductionChain = false)2449 : VPHeaderPHIRecipe(VPDef::VPReductionPHISC, Phi, &Start), Kind(Kind),2450 Style(Style),2451 HasUsesOutsideReductionChain(HasUsesOutsideReductionChain) {}2452 2453 ~VPReductionPHIRecipe() override = default;2454 2455 VPReductionPHIRecipe *clone() override {2456 auto *R = new VPReductionPHIRecipe(2457 dyn_cast_or_null<PHINode>(getUnderlyingValue()), getRecurrenceKind(),2458 *getOperand(0), Style, HasUsesOutsideReductionChain);2459 R->addOperand(getBackedgeValue());2460 return R;2461 }2462 2463 VP_CLASSOF_IMPL(VPDef::VPReductionPHISC)2464 2465 /// Generate the phi/select nodes.2466 void execute(VPTransformState &State) override;2467 2468 /// Get the factor that the VF of this recipe's output should be scaled by, or2469 /// 1 if it isn't scaled.2470 unsigned getVFScaleFactor() const {2471 auto *Partial = std::get_if<RdxUnordered>(&Style);2472 return Partial ? Partial->VFScaleFactor : 1;2473 }2474 2475 /// Returns the number of incoming values, also number of incoming blocks.2476 /// Note that at the moment, VPWidenPointerInductionRecipe only has a single2477 /// incoming value, its start value.2478 unsigned getNumIncoming() const override { return 2; }2479 2480 /// Returns the recurrence kind of the reduction.2481 RecurKind getRecurrenceKind() const { return Kind; }2482 2483 /// Returns true, if the phi is part of an ordered reduction.2484 bool isOrdered() const { return std::holds_alternative<RdxOrdered>(Style); }2485 2486 /// Returns true if the phi is part of an in-loop reduction.2487 bool isInLoop() const {2488 return std::holds_alternative<RdxInLoop>(Style) ||2489 std::holds_alternative<RdxOrdered>(Style);2490 }2491 2492 /// Returns true if the reduction outputs a vector with a scaled down VF.2493 bool isPartialReduction() const { return getVFScaleFactor() > 1; }2494 2495 /// Returns true, if the phi is part of a multi-use reduction.2496 bool hasUsesOutsideReductionChain() const {2497 return HasUsesOutsideReductionChain;2498 }2499 2500 /// Returns true if the recipe only uses the first lane of operand \p Op.2501 bool usesFirstLaneOnly(const VPValue *Op) const override {2502 assert(is_contained(operands(), Op) &&2503 "Op must be an operand of the recipe");2504 return isOrdered() || isInLoop();2505 }2506 2507protected:2508#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2509 /// Print the recipe.2510 void printRecipe(raw_ostream &O, const Twine &Indent,2511 VPSlotTracker &SlotTracker) const override;2512#endif2513};2514 2515/// A recipe for vectorizing a phi-node as a sequence of mask-based select2516/// instructions.2517class LLVM_ABI_FOR_TEST VPBlendRecipe : public VPSingleDefRecipe {2518public:2519 /// The blend operation is a User of the incoming values and of their2520 /// respective masks, ordered [I0, M0, I1, M1, I2, M2, ...]. Note that M0 can2521 /// be omitted (implied by passing an odd number of operands) in which case2522 /// all other incoming values are merged into it.2523 VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands, DebugLoc DL)2524 : VPSingleDefRecipe(VPDef::VPBlendSC, Operands, Phi, DL) {2525 assert(Operands.size() > 0 && "Expected at least one operand!");2526 }2527 2528 VPBlendRecipe *clone() override {2529 return new VPBlendRecipe(cast_or_null<PHINode>(getUnderlyingValue()),2530 operands(), getDebugLoc());2531 }2532 2533 VP_CLASSOF_IMPL(VPDef::VPBlendSC)2534 2535 /// A normalized blend is one that has an odd number of operands, whereby the2536 /// first operand does not have an associated mask.2537 bool isNormalized() const { return getNumOperands() % 2; }2538 2539 /// Return the number of incoming values, taking into account when normalized2540 /// the first incoming value will have no mask.2541 unsigned getNumIncomingValues() const {2542 return (getNumOperands() + isNormalized()) / 2;2543 }2544 2545 /// Return incoming value number \p Idx.2546 VPValue *getIncomingValue(unsigned Idx) const {2547 return Idx == 0 ? getOperand(0) : getOperand(Idx * 2 - isNormalized());2548 }2549 2550 /// Return mask number \p Idx.2551 VPValue *getMask(unsigned Idx) const {2552 assert((Idx > 0 || !isNormalized()) && "First index has no mask!");2553 return Idx == 0 ? getOperand(1) : getOperand(Idx * 2 + !isNormalized());2554 }2555 2556 /// Set mask number \p Idx to \p V.2557 void setMask(unsigned Idx, VPValue *V) {2558 assert((Idx > 0 || !isNormalized()) && "First index has no mask!");2559 Idx == 0 ? setOperand(1, V) : setOperand(Idx * 2 + !isNormalized(), V);2560 }2561 2562 void execute(VPTransformState &State) override {2563 llvm_unreachable("VPBlendRecipe should be expanded by simplifyBlends");2564 }2565 2566 /// Return the cost of this VPWidenMemoryRecipe.2567 InstructionCost computeCost(ElementCount VF,2568 VPCostContext &Ctx) const override;2569 2570 /// Returns true if the recipe only uses the first lane of operand \p Op.2571 bool usesFirstLaneOnly(const VPValue *Op) const override {2572 assert(is_contained(operands(), Op) &&2573 "Op must be an operand of the recipe");2574 // Recursing through Blend recipes only, must terminate at header phi's the2575 // latest.2576 return all_of(users(),2577 [this](VPUser *U) { return U->usesFirstLaneOnly(this); });2578 }2579 2580protected:2581#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2582 /// Print the recipe.2583 void printRecipe(raw_ostream &O, const Twine &Indent,2584 VPSlotTracker &SlotTracker) const override;2585#endif2586};2587 2588/// A common base class for interleaved memory operations.2589/// An Interleaved memory operation is a memory access method that combines2590/// multiple strided loads/stores into a single wide load/store with shuffles.2591/// The first operand is the start address. The optional operands are, in order,2592/// the stored values and the mask.2593class LLVM_ABI_FOR_TEST VPInterleaveBase : public VPRecipeBase,2594 public VPIRMetadata {2595 const InterleaveGroup<Instruction> *IG;2596 2597 /// Indicates if the interleave group is in a conditional block and requires a2598 /// mask.2599 bool HasMask = false;2600 2601 /// Indicates if gaps between members of the group need to be masked out or if2602 /// unusued gaps can be loaded speculatively.2603 bool NeedsMaskForGaps = false;2604 2605protected:2606 VPInterleaveBase(const unsigned char SC,2607 const InterleaveGroup<Instruction> *IG,2608 ArrayRef<VPValue *> Operands,2609 ArrayRef<VPValue *> StoredValues, VPValue *Mask,2610 bool NeedsMaskForGaps, const VPIRMetadata &MD, DebugLoc DL)2611 : VPRecipeBase(SC, Operands, DL), VPIRMetadata(MD), IG(IG),2612 NeedsMaskForGaps(NeedsMaskForGaps) {2613 // TODO: extend the masked interleaved-group support to reversed access.2614 assert((!Mask || !IG->isReverse()) &&2615 "Reversed masked interleave-group not supported.");2616 for (unsigned I = 0; I < IG->getFactor(); ++I)2617 if (Instruction *Inst = IG->getMember(I)) {2618 if (Inst->getType()->isVoidTy())2619 continue;2620 new VPValue(Inst, this);2621 }2622 2623 for (auto *SV : StoredValues)2624 addOperand(SV);2625 if (Mask) {2626 HasMask = true;2627 addOperand(Mask);2628 }2629 }2630 2631public:2632 VPInterleaveBase *clone() override = 0;2633 2634 static inline bool classof(const VPRecipeBase *R) {2635 return R->getVPDefID() == VPRecipeBase::VPInterleaveSC ||2636 R->getVPDefID() == VPRecipeBase::VPInterleaveEVLSC;2637 }2638 2639 static inline bool classof(const VPUser *U) {2640 auto *R = dyn_cast<VPRecipeBase>(U);2641 return R && classof(R);2642 }2643 2644 /// Return the address accessed by this recipe.2645 VPValue *getAddr() const {2646 return getOperand(0); // Address is the 1st, mandatory operand.2647 }2648 2649 /// Return the mask used by this recipe. Note that a full mask is represented2650 /// by a nullptr.2651 VPValue *getMask() const {2652 // Mask is optional and the last operand.2653 return HasMask ? getOperand(getNumOperands() - 1) : nullptr;2654 }2655 2656 /// Return true if the access needs a mask because of the gaps.2657 bool needsMaskForGaps() const { return NeedsMaskForGaps; }2658 2659 const InterleaveGroup<Instruction> *getInterleaveGroup() const { return IG; }2660 2661 Instruction *getInsertPos() const { return IG->getInsertPos(); }2662 2663 void execute(VPTransformState &State) override {2664 llvm_unreachable("VPInterleaveBase should not be instantiated.");2665 }2666 2667 /// Return the cost of this recipe.2668 InstructionCost computeCost(ElementCount VF,2669 VPCostContext &Ctx) const override;2670 2671 /// Returns true if the recipe only uses the first lane of operand \p Op.2672 bool usesFirstLaneOnly(const VPValue *Op) const override = 0;2673 2674 /// Returns the number of stored operands of this interleave group. Returns 02675 /// for load interleave groups.2676 virtual unsigned getNumStoreOperands() const = 0;2677 2678 /// Return the VPValues stored by this interleave group. If it is a load2679 /// interleave group, return an empty ArrayRef.2680 ArrayRef<VPValue *> getStoredValues() const {2681 return ArrayRef<VPValue *>(op_end() -2682 (getNumStoreOperands() + (HasMask ? 1 : 0)),2683 getNumStoreOperands());2684 }2685};2686 2687/// VPInterleaveRecipe is a recipe for transforming an interleave group of load2688/// or stores into one wide load/store and shuffles. The first operand of a2689/// VPInterleave recipe is the address, followed by the stored values, followed2690/// by an optional mask.2691class LLVM_ABI_FOR_TEST VPInterleaveRecipe final : public VPInterleaveBase {2692public:2693 VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr,2694 ArrayRef<VPValue *> StoredValues, VPValue *Mask,2695 bool NeedsMaskForGaps, const VPIRMetadata &MD, DebugLoc DL)2696 : VPInterleaveBase(VPDef::VPInterleaveSC, IG, Addr, StoredValues, Mask,2697 NeedsMaskForGaps, MD, DL) {}2698 2699 ~VPInterleaveRecipe() override = default;2700 2701 VPInterleaveRecipe *clone() override {2702 return new VPInterleaveRecipe(getInterleaveGroup(), getAddr(),2703 getStoredValues(), getMask(),2704 needsMaskForGaps(), *this, getDebugLoc());2705 }2706 2707 VP_CLASSOF_IMPL(VPDef::VPInterleaveSC)2708 2709 /// Generate the wide load or store, and shuffles.2710 void execute(VPTransformState &State) override;2711 2712 bool usesFirstLaneOnly(const VPValue *Op) const override {2713 assert(is_contained(operands(), Op) &&2714 "Op must be an operand of the recipe");2715 return Op == getAddr() && !llvm::is_contained(getStoredValues(), Op);2716 }2717 2718 unsigned getNumStoreOperands() const override {2719 return getNumOperands() - (getMask() ? 2 : 1);2720 }2721 2722protected:2723#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2724 /// Print the recipe.2725 void printRecipe(raw_ostream &O, const Twine &Indent,2726 VPSlotTracker &SlotTracker) const override;2727#endif2728};2729 2730/// A recipe for interleaved memory operations with vector-predication2731/// intrinsics. The first operand is the address, the second operand is the2732/// explicit vector length. Stored values and mask are optional operands.2733class LLVM_ABI_FOR_TEST VPInterleaveEVLRecipe final : public VPInterleaveBase {2734public:2735 VPInterleaveEVLRecipe(VPInterleaveRecipe &R, VPValue &EVL, VPValue *Mask)2736 : VPInterleaveBase(VPDef::VPInterleaveEVLSC, R.getInterleaveGroup(),2737 ArrayRef<VPValue *>({R.getAddr(), &EVL}),2738 R.getStoredValues(), Mask, R.needsMaskForGaps(), R,2739 R.getDebugLoc()) {2740 assert(!getInterleaveGroup()->isReverse() &&2741 "Reversed interleave-group with tail folding is not supported.");2742 assert(!needsMaskForGaps() && "Interleaved access with gap mask is not "2743 "supported for scalable vector.");2744 }2745 2746 ~VPInterleaveEVLRecipe() override = default;2747 2748 VPInterleaveEVLRecipe *clone() override {2749 llvm_unreachable("cloning not implemented yet");2750 }2751 2752 VP_CLASSOF_IMPL(VPDef::VPInterleaveEVLSC)2753 2754 /// The VPValue of the explicit vector length.2755 VPValue *getEVL() const { return getOperand(1); }2756 2757 /// Generate the wide load or store, and shuffles.2758 void execute(VPTransformState &State) override;2759 2760 /// The recipe only uses the first lane of the address, and EVL operand.2761 bool usesFirstLaneOnly(const VPValue *Op) const override {2762 assert(is_contained(operands(), Op) &&2763 "Op must be an operand of the recipe");2764 return (Op == getAddr() && !llvm::is_contained(getStoredValues(), Op)) ||2765 Op == getEVL();2766 }2767 2768 unsigned getNumStoreOperands() const override {2769 return getNumOperands() - (getMask() ? 3 : 2);2770 }2771 2772protected:2773#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2774 /// Print the recipe.2775 void printRecipe(raw_ostream &O, const Twine &Indent,2776 VPSlotTracker &SlotTracker) const override;2777#endif2778};2779 2780/// A recipe to represent inloop, ordered or partial reduction operations. It2781/// performs a reduction on a vector operand into a scalar (vector in the case2782/// of a partial reduction) value, and adds the result to a chain. The Operands2783/// are {ChainOp, VecOp, [Condition]}.2784class LLVM_ABI_FOR_TEST VPReductionRecipe : public VPRecipeWithIRFlags {2785 2786 /// The recurrence kind for the reduction in question.2787 RecurKind RdxKind;2788 /// Whether the reduction is conditional.2789 bool IsConditional = false;2790 ReductionStyle Style;2791 2792protected:2793 VPReductionRecipe(const unsigned char SC, RecurKind RdxKind,2794 FastMathFlags FMFs, Instruction *I,2795 ArrayRef<VPValue *> Operands, VPValue *CondOp,2796 ReductionStyle Style, DebugLoc DL)2797 : VPRecipeWithIRFlags(SC, Operands, FMFs, DL), RdxKind(RdxKind),2798 Style(Style) {2799 if (CondOp) {2800 IsConditional = true;2801 addOperand(CondOp);2802 }2803 setUnderlyingValue(I);2804 }2805 2806public:2807 VPReductionRecipe(RecurKind RdxKind, FastMathFlags FMFs, Instruction *I,2808 VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,2809 ReductionStyle Style, DebugLoc DL = DebugLoc::getUnknown())2810 : VPReductionRecipe(VPDef::VPReductionSC, RdxKind, FMFs, I,2811 ArrayRef<VPValue *>({ChainOp, VecOp}), CondOp, Style,2812 DL) {}2813 2814 VPReductionRecipe(const RecurKind RdxKind, FastMathFlags FMFs,2815 VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,2816 ReductionStyle Style, DebugLoc DL = DebugLoc::getUnknown())2817 : VPReductionRecipe(VPDef::VPReductionSC, RdxKind, FMFs, nullptr,2818 ArrayRef<VPValue *>({ChainOp, VecOp}), CondOp, Style,2819 DL) {}2820 2821 ~VPReductionRecipe() override = default;2822 2823 VPReductionRecipe *clone() override {2824 return new VPReductionRecipe(RdxKind, getFastMathFlags(),2825 getUnderlyingInstr(), getChainOp(), getVecOp(),2826 getCondOp(), Style, getDebugLoc());2827 }2828 2829 static inline bool classof(const VPRecipeBase *R) {2830 return R->getVPDefID() == VPRecipeBase::VPReductionSC ||2831 R->getVPDefID() == VPRecipeBase::VPReductionEVLSC;2832 }2833 2834 static inline bool classof(const VPUser *U) {2835 auto *R = dyn_cast<VPRecipeBase>(U);2836 return R && classof(R);2837 }2838 2839 static inline bool classof(const VPValue *VPV) {2840 const VPRecipeBase *R = VPV->getDefiningRecipe();2841 return R && classof(R);2842 }2843 2844 static inline bool classof(const VPSingleDefRecipe *R) {2845 return classof(static_cast<const VPRecipeBase *>(R));2846 }2847 2848 /// Generate the reduction in the loop.2849 void execute(VPTransformState &State) override;2850 2851 /// Return the cost of VPReductionRecipe.2852 InstructionCost computeCost(ElementCount VF,2853 VPCostContext &Ctx) const override;2854 2855 /// Return the recurrence kind for the in-loop reduction.2856 RecurKind getRecurrenceKind() const { return RdxKind; }2857 /// Return true if the in-loop reduction is ordered.2858 bool isOrdered() const { return std::holds_alternative<RdxOrdered>(Style); };2859 /// Return true if the in-loop reduction is conditional.2860 bool isConditional() const { return IsConditional; };2861 /// Returns true if the reduction outputs a vector with a scaled down VF.2862 bool isPartialReduction() const { return getVFScaleFactor() > 1; }2863 /// Returns true if the reduction is in-loop.2864 bool isInLoop() const {2865 return std::holds_alternative<RdxInLoop>(Style) ||2866 std::holds_alternative<RdxOrdered>(Style);2867 }2868 /// The VPValue of the scalar Chain being accumulated.2869 VPValue *getChainOp() const { return getOperand(0); }2870 /// The VPValue of the vector value to be reduced.2871 VPValue *getVecOp() const { return getOperand(1); }2872 /// The VPValue of the condition for the block.2873 VPValue *getCondOp() const {2874 return isConditional() ? getOperand(getNumOperands() - 1) : nullptr;2875 }2876 /// Get the factor that the VF of this recipe's output should be scaled by, or2877 /// 1 if it isn't scaled.2878 unsigned getVFScaleFactor() const {2879 auto *Partial = std::get_if<RdxUnordered>(&Style);2880 return Partial ? Partial->VFScaleFactor : 1;2881 }2882 2883protected:2884#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2885 /// Print the recipe.2886 void printRecipe(raw_ostream &O, const Twine &Indent,2887 VPSlotTracker &SlotTracker) const override;2888#endif2889};2890 2891/// A recipe to represent inloop reduction operations with vector-predication2892/// intrinsics, performing a reduction on a vector operand with the explicit2893/// vector length (EVL) into a scalar value, and adding the result to a chain.2894/// The Operands are {ChainOp, VecOp, EVL, [Condition]}.2895class LLVM_ABI_FOR_TEST VPReductionEVLRecipe : public VPReductionRecipe {2896public:2897 VPReductionEVLRecipe(VPReductionRecipe &R, VPValue &EVL, VPValue *CondOp,2898 DebugLoc DL = DebugLoc::getUnknown())2899 : VPReductionRecipe(2900 VPDef::VPReductionEVLSC, R.getRecurrenceKind(),2901 R.getFastMathFlags(),2902 cast_or_null<Instruction>(R.getUnderlyingValue()),2903 ArrayRef<VPValue *>({R.getChainOp(), R.getVecOp(), &EVL}), CondOp,2904 getReductionStyle(/*InLoop=*/true, R.isOrdered(), 1), DL) {}2905 2906 ~VPReductionEVLRecipe() override = default;2907 2908 VPReductionEVLRecipe *clone() override {2909 llvm_unreachable("cloning not implemented yet");2910 }2911 2912 VP_CLASSOF_IMPL(VPDef::VPReductionEVLSC)2913 2914 /// Generate the reduction in the loop2915 void execute(VPTransformState &State) override;2916 2917 /// The VPValue of the explicit vector length.2918 VPValue *getEVL() const { return getOperand(2); }2919 2920 /// Returns true if the recipe only uses the first lane of operand \p Op.2921 bool usesFirstLaneOnly(const VPValue *Op) const override {2922 assert(is_contained(operands(), Op) &&2923 "Op must be an operand of the recipe");2924 return Op == getEVL();2925 }2926 2927protected:2928#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2929 /// Print the recipe.2930 void printRecipe(raw_ostream &O, const Twine &Indent,2931 VPSlotTracker &SlotTracker) const override;2932#endif2933};2934 2935/// VPReplicateRecipe replicates a given instruction producing multiple scalar2936/// copies of the original scalar type, one per lane, instead of producing a2937/// single copy of widened type for all lanes. If the instruction is known to be2938/// a single scalar, only one copy, per lane zero, will be generated.2939class LLVM_ABI_FOR_TEST VPReplicateRecipe : public VPRecipeWithIRFlags,2940 public VPIRMetadata {2941 /// Indicator if only a single replica per lane is needed.2942 bool IsSingleScalar;2943 2944 /// Indicator if the replicas are also predicated.2945 bool IsPredicated;2946 2947public:2948 VPReplicateRecipe(Instruction *I, ArrayRef<VPValue *> Operands,2949 bool IsSingleScalar, VPValue *Mask = nullptr,2950 const VPIRFlags &Flags = {}, VPIRMetadata Metadata = {},2951 DebugLoc DL = DebugLoc::getUnknown())2952 : VPRecipeWithIRFlags(VPDef::VPReplicateSC, Operands, Flags, DL),2953 VPIRMetadata(Metadata), IsSingleScalar(IsSingleScalar),2954 IsPredicated(Mask) {2955 setUnderlyingValue(I);2956 if (Mask)2957 addOperand(Mask);2958 }2959 2960 ~VPReplicateRecipe() override = default;2961 2962 VPReplicateRecipe *clone() override {2963 auto *Copy = new VPReplicateRecipe(2964 getUnderlyingInstr(), operands(), IsSingleScalar,2965 isPredicated() ? getMask() : nullptr, *this, *this, getDebugLoc());2966 Copy->transferFlags(*this);2967 return Copy;2968 }2969 2970 VP_CLASSOF_IMPL(VPDef::VPReplicateSC)2971 2972 /// Generate replicas of the desired Ingredient. Replicas will be generated2973 /// for all parts and lanes unless a specific part and lane are specified in2974 /// the \p State.2975 void execute(VPTransformState &State) override;2976 2977 /// Return the cost of this VPReplicateRecipe.2978 InstructionCost computeCost(ElementCount VF,2979 VPCostContext &Ctx) const override;2980 2981 bool isSingleScalar() const { return IsSingleScalar; }2982 2983 bool isPredicated() const { return IsPredicated; }2984 2985 /// Returns true if the recipe only uses the first lane of operand \p Op.2986 bool usesFirstLaneOnly(const VPValue *Op) const override {2987 assert(is_contained(operands(), Op) &&2988 "Op must be an operand of the recipe");2989 return isSingleScalar();2990 }2991 2992 /// Returns true if the recipe uses scalars of operand \p Op.2993 bool usesScalars(const VPValue *Op) const override {2994 assert(is_contained(operands(), Op) &&2995 "Op must be an operand of the recipe");2996 return true;2997 }2998 2999 /// Returns true if the recipe is used by a widened recipe via an intervening3000 /// VPPredInstPHIRecipe. In this case, the scalar values should also be packed3001 /// in a vector.3002 bool shouldPack() const;3003 3004 /// Return the mask of a predicated VPReplicateRecipe.3005 VPValue *getMask() {3006 assert(isPredicated() && "Trying to get the mask of a unpredicated recipe");3007 return getOperand(getNumOperands() - 1);3008 }3009 3010 unsigned getOpcode() const { return getUnderlyingInstr()->getOpcode(); }3011 3012protected:3013#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3014 /// Print the recipe.3015 void printRecipe(raw_ostream &O, const Twine &Indent,3016 VPSlotTracker &SlotTracker) const override;3017#endif3018};3019 3020/// A recipe for generating conditional branches on the bits of a mask.3021class LLVM_ABI_FOR_TEST VPBranchOnMaskRecipe : public VPRecipeBase {3022public:3023 VPBranchOnMaskRecipe(VPValue *BlockInMask, DebugLoc DL)3024 : VPRecipeBase(VPDef::VPBranchOnMaskSC, {BlockInMask}, DL) {}3025 3026 VPBranchOnMaskRecipe *clone() override {3027 return new VPBranchOnMaskRecipe(getOperand(0), getDebugLoc());3028 }3029 3030 VP_CLASSOF_IMPL(VPDef::VPBranchOnMaskSC)3031 3032 /// Generate the extraction of the appropriate bit from the block mask and the3033 /// conditional branch.3034 void execute(VPTransformState &State) override;3035 3036 /// Return the cost of this VPBranchOnMaskRecipe.3037 InstructionCost computeCost(ElementCount VF,3038 VPCostContext &Ctx) const override;3039 3040#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3041 /// Print the recipe.3042 void printRecipe(raw_ostream &O, const Twine &Indent,3043 VPSlotTracker &SlotTracker) const override {3044 O << Indent << "BRANCH-ON-MASK ";3045 printOperands(O, SlotTracker);3046 }3047#endif3048 3049 /// Returns true if the recipe uses scalars of operand \p Op.3050 bool usesScalars(const VPValue *Op) const override {3051 assert(is_contained(operands(), Op) &&3052 "Op must be an operand of the recipe");3053 return true;3054 }3055};3056 3057/// A recipe to combine multiple recipes into a single 'expression' recipe,3058/// which should be considered a single entity for cost-modeling and transforms.3059/// The recipe needs to be 'decomposed', i.e. replaced by its individual3060/// expression recipes, before execute. The individual expression recipes are3061/// completely disconnected from the def-use graph of other recipes not part of3062/// the expression. Def-use edges between pairs of expression recipes remain3063/// intact, whereas every edge between an expression recipe and a recipe outside3064/// the expression is elevated to connect the non-expression recipe with the3065/// VPExpressionRecipe itself.3066class VPExpressionRecipe : public VPSingleDefRecipe {3067 /// Recipes included in this VPExpressionRecipe. This could contain3068 /// duplicates.3069 SmallVector<VPSingleDefRecipe *> ExpressionRecipes;3070 3071 /// Temporary VPValues used for external operands of the expression, i.e.3072 /// operands not defined by recipes in the expression.3073 SmallVector<VPValue *> LiveInPlaceholders;3074 3075 enum class ExpressionTypes {3076 /// Represents an inloop extended reduction operation, performing a3077 /// reduction on an extended vector operand into a scalar value, and adding3078 /// the result to a chain.3079 ExtendedReduction,3080 /// Represent an inloop multiply-accumulate reduction, multiplying the3081 /// extended vector operands, performing a reduction.add on the result, and3082 /// adding the scalar result to a chain.3083 ExtMulAccReduction,3084 /// Represent an inloop multiply-accumulate reduction, multiplying the3085 /// vector operands, performing a reduction.add on the result, and adding3086 /// the scalar result to a chain.3087 MulAccReduction,3088 /// Represent an inloop multiply-accumulate reduction, multiplying the3089 /// extended vector operands, negating the multiplication, performing a3090 /// reduction.add on the result, and adding the scalar result to a chain.3091 ExtNegatedMulAccReduction,3092 };3093 3094 /// Type of the expression.3095 ExpressionTypes ExpressionType;3096 3097 /// Construct a new VPExpressionRecipe by internalizing recipes in \p3098 /// ExpressionRecipes. External operands (i.e. not defined by another recipe3099 /// in the expression) are replaced by temporary VPValues and the original3100 /// operands are transferred to the VPExpressionRecipe itself. Clone recipes3101 /// as needed (excluding last) to ensure they are only used by other recipes3102 /// in the expression.3103 VPExpressionRecipe(ExpressionTypes ExpressionType,3104 ArrayRef<VPSingleDefRecipe *> ExpressionRecipes);3105 3106public:3107 VPExpressionRecipe(VPWidenCastRecipe *Ext, VPReductionRecipe *Red)3108 : VPExpressionRecipe(ExpressionTypes::ExtendedReduction, {Ext, Red}) {}3109 VPExpressionRecipe(VPWidenRecipe *Mul, VPReductionRecipe *Red)3110 : VPExpressionRecipe(ExpressionTypes::MulAccReduction, {Mul, Red}) {}3111 VPExpressionRecipe(VPWidenCastRecipe *Ext0, VPWidenCastRecipe *Ext1,3112 VPWidenRecipe *Mul, VPReductionRecipe *Red)3113 : VPExpressionRecipe(ExpressionTypes::ExtMulAccReduction,3114 {Ext0, Ext1, Mul, Red}) {}3115 VPExpressionRecipe(VPWidenCastRecipe *Ext0, VPWidenCastRecipe *Ext1,3116 VPWidenRecipe *Mul, VPWidenRecipe *Sub,3117 VPReductionRecipe *Red)3118 : VPExpressionRecipe(ExpressionTypes::ExtNegatedMulAccReduction,3119 {Ext0, Ext1, Mul, Sub, Red}) {3120 assert(Mul->getOpcode() == Instruction::Mul && "Expected a mul");3121 assert(Red->getRecurrenceKind() == RecurKind::Add &&3122 "Expected an add reduction");3123 assert(getNumOperands() >= 3 && "Expected at least three operands");3124 [[maybe_unused]] auto *SubConst = dyn_cast<ConstantInt>(getOperand(2)->getLiveInIRValue());3125 assert(SubConst && SubConst->getValue() == 0 &&3126 Sub->getOpcode() == Instruction::Sub && "Expected a negating sub");3127 }3128 3129 ~VPExpressionRecipe() override {3130 SmallPtrSet<VPSingleDefRecipe *, 4> ExpressionRecipesSeen;3131 for (auto *R : reverse(ExpressionRecipes)) {3132 if (ExpressionRecipesSeen.insert(R).second)3133 delete R;3134 }3135 for (VPValue *T : LiveInPlaceholders)3136 delete T;3137 }3138 3139 VP_CLASSOF_IMPL(VPDef::VPExpressionSC)3140 3141 VPExpressionRecipe *clone() override {3142 assert(!ExpressionRecipes.empty() && "empty expressions should be removed");3143 SmallVector<VPSingleDefRecipe *> NewExpressiondRecipes;3144 for (auto *R : ExpressionRecipes)3145 NewExpressiondRecipes.push_back(R->clone());3146 for (auto *New : NewExpressiondRecipes) {3147 for (const auto &[Idx, Old] : enumerate(ExpressionRecipes))3148 New->replaceUsesOfWith(Old, NewExpressiondRecipes[Idx]);3149 // Update placeholder operands in the cloned recipe to use the external3150 // operands, to be internalized when the cloned expression is constructed.3151 for (const auto &[Placeholder, OutsideOp] :3152 zip(LiveInPlaceholders, operands()))3153 New->replaceUsesOfWith(Placeholder, OutsideOp);3154 }3155 return new VPExpressionRecipe(ExpressionType, NewExpressiondRecipes);3156 }3157 3158 /// Return the VPValue to use to infer the result type of the recipe.3159 VPValue *getOperandOfResultType() const {3160 unsigned OpIdx =3161 cast<VPReductionRecipe>(ExpressionRecipes.back())->isConditional() ? 23162 : 1;3163 return getOperand(getNumOperands() - OpIdx);3164 }3165 3166 /// Insert the recipes of the expression back into the VPlan, directly before3167 /// the current recipe. Leaves the expression recipe empty, which must be3168 /// removed before codegen.3169 void decompose();3170 3171 unsigned getVFScaleFactor() const {3172 auto *PR = dyn_cast<VPReductionRecipe>(ExpressionRecipes.back());3173 return PR ? PR->getVFScaleFactor() : 1;3174 }3175 3176 /// Method for generating code, must not be called as this recipe is abstract.3177 void execute(VPTransformState &State) override {3178 llvm_unreachable("recipe must be removed before execute");3179 }3180 3181 InstructionCost computeCost(ElementCount VF,3182 VPCostContext &Ctx) const override;3183 3184 /// Returns true if this expression contains recipes that may read from or3185 /// write to memory.3186 bool mayReadOrWriteMemory() const;3187 3188 /// Returns true if this expression contains recipes that may have side3189 /// effects.3190 bool mayHaveSideEffects() const;3191 3192 /// Returns true if the result of this VPExpressionRecipe is a single-scalar.3193 bool isSingleScalar() const;3194 3195protected:3196#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3197 /// Print the recipe.3198 void printRecipe(raw_ostream &O, const Twine &Indent,3199 VPSlotTracker &SlotTracker) const override;3200#endif3201};3202 3203/// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when3204/// control converges back from a Branch-on-Mask. The phi nodes are needed in3205/// order to merge values that are set under such a branch and feed their uses.3206/// The phi nodes can be scalar or vector depending on the users of the value.3207/// This recipe works in concert with VPBranchOnMaskRecipe.3208class LLVM_ABI_FOR_TEST VPPredInstPHIRecipe : public VPSingleDefRecipe {3209public:3210 /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi3211 /// nodes after merging back from a Branch-on-Mask.3212 VPPredInstPHIRecipe(VPValue *PredV, DebugLoc DL)3213 : VPSingleDefRecipe(VPDef::VPPredInstPHISC, PredV, DL) {}3214 ~VPPredInstPHIRecipe() override = default;3215 3216 VPPredInstPHIRecipe *clone() override {3217 return new VPPredInstPHIRecipe(getOperand(0), getDebugLoc());3218 }3219 3220 VP_CLASSOF_IMPL(VPDef::VPPredInstPHISC)3221 3222 /// Generates phi nodes for live-outs (from a replicate region) as needed to3223 /// retain SSA form.3224 void execute(VPTransformState &State) override;3225 3226 /// Return the cost of this VPPredInstPHIRecipe.3227 InstructionCost computeCost(ElementCount VF,3228 VPCostContext &Ctx) const override {3229 // TODO: Compute accurate cost after retiring the legacy cost model.3230 return 0;3231 }3232 3233 /// Returns true if the recipe uses scalars of operand \p Op.3234 bool usesScalars(const VPValue *Op) const override {3235 assert(is_contained(operands(), Op) &&3236 "Op must be an operand of the recipe");3237 return true;3238 }3239 3240protected:3241#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3242 /// Print the recipe.3243 void printRecipe(raw_ostream &O, const Twine &Indent,3244 VPSlotTracker &SlotTracker) const override;3245#endif3246};3247 3248/// A common base class for widening memory operations. An optional mask can be3249/// provided as the last operand.3250class LLVM_ABI_FOR_TEST VPWidenMemoryRecipe : public VPRecipeBase,3251 public VPIRMetadata {3252protected:3253 Instruction &Ingredient;3254 3255 /// Alignment information for this memory access.3256 Align Alignment;3257 3258 /// Whether the accessed addresses are consecutive.3259 bool Consecutive;3260 3261 /// Whether the consecutive accessed addresses are in reverse order.3262 bool Reverse;3263 3264 /// Whether the memory access is masked.3265 bool IsMasked = false;3266 3267 void setMask(VPValue *Mask) {3268 assert(!IsMasked && "cannot re-set mask");3269 if (!Mask)3270 return;3271 addOperand(Mask);3272 IsMasked = true;3273 }3274 3275 VPWidenMemoryRecipe(const char unsigned SC, Instruction &I,3276 std::initializer_list<VPValue *> Operands,3277 bool Consecutive, bool Reverse,3278 const VPIRMetadata &Metadata, DebugLoc DL)3279 : VPRecipeBase(SC, Operands, DL), VPIRMetadata(Metadata), Ingredient(I),3280 Alignment(getLoadStoreAlignment(&I)), Consecutive(Consecutive),3281 Reverse(Reverse) {3282 assert((Consecutive || !Reverse) && "Reverse implies consecutive");3283 assert((isa<VPVectorEndPointerRecipe>(getAddr()) || !Reverse) &&3284 "Reversed acccess without VPVectorEndPointerRecipe address?");3285 }3286 3287public:3288 VPWidenMemoryRecipe *clone() override {3289 llvm_unreachable("cloning not supported");3290 }3291 3292 static inline bool classof(const VPRecipeBase *R) {3293 return R->getVPDefID() == VPRecipeBase::VPWidenLoadSC ||3294 R->getVPDefID() == VPRecipeBase::VPWidenStoreSC ||3295 R->getVPDefID() == VPRecipeBase::VPWidenLoadEVLSC ||3296 R->getVPDefID() == VPRecipeBase::VPWidenStoreEVLSC;3297 }3298 3299 static inline bool classof(const VPUser *U) {3300 auto *R = dyn_cast<VPRecipeBase>(U);3301 return R && classof(R);3302 }3303 3304 /// Return whether the loaded-from / stored-to addresses are consecutive.3305 bool isConsecutive() const { return Consecutive; }3306 3307 /// Return whether the consecutive loaded/stored addresses are in reverse3308 /// order.3309 bool isReverse() const { return Reverse; }3310 3311 /// Return the address accessed by this recipe.3312 VPValue *getAddr() const { return getOperand(0); }3313 3314 /// Returns true if the recipe is masked.3315 bool isMasked() const { return IsMasked; }3316 3317 /// Return the mask used by this recipe. Note that a full mask is represented3318 /// by a nullptr.3319 VPValue *getMask() const {3320 // Mask is optional and therefore the last operand.3321 return isMasked() ? getOperand(getNumOperands() - 1) : nullptr;3322 }3323 3324 /// Returns the alignment of the memory access.3325 Align getAlign() const { return Alignment; }3326 3327 /// Generate the wide load/store.3328 void execute(VPTransformState &State) override {3329 llvm_unreachable("VPWidenMemoryRecipe should not be instantiated.");3330 }3331 3332 /// Return the cost of this VPWidenMemoryRecipe.3333 InstructionCost computeCost(ElementCount VF,3334 VPCostContext &Ctx) const override;3335 3336 Instruction &getIngredient() const { return Ingredient; }3337};3338 3339/// A recipe for widening load operations, using the address to load from and an3340/// optional mask.3341struct LLVM_ABI_FOR_TEST VPWidenLoadRecipe final : public VPWidenMemoryRecipe,3342 public VPValue {3343 VPWidenLoadRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask,3344 bool Consecutive, bool Reverse,3345 const VPIRMetadata &Metadata, DebugLoc DL)3346 : VPWidenMemoryRecipe(VPDef::VPWidenLoadSC, Load, {Addr}, Consecutive,3347 Reverse, Metadata, DL),3348 VPValue(this, &Load) {3349 setMask(Mask);3350 }3351 3352 VPWidenLoadRecipe *clone() override {3353 return new VPWidenLoadRecipe(cast<LoadInst>(Ingredient), getAddr(),3354 getMask(), Consecutive, Reverse, *this,3355 getDebugLoc());3356 }3357 3358 VP_CLASSOF_IMPL(VPDef::VPWidenLoadSC);3359 3360 /// Generate a wide load or gather.3361 void execute(VPTransformState &State) override;3362 3363 /// Returns true if the recipe only uses the first lane of operand \p Op.3364 bool usesFirstLaneOnly(const VPValue *Op) const override {3365 assert(is_contained(operands(), Op) &&3366 "Op must be an operand of the recipe");3367 // Widened, consecutive loads operations only demand the first lane of3368 // their address.3369 return Op == getAddr() && isConsecutive();3370 }3371 3372protected:3373#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3374 /// Print the recipe.3375 void printRecipe(raw_ostream &O, const Twine &Indent,3376 VPSlotTracker &SlotTracker) const override;3377#endif3378};3379 3380/// A recipe for widening load operations with vector-predication intrinsics,3381/// using the address to load from, the explicit vector length and an optional3382/// mask.3383struct VPWidenLoadEVLRecipe final : public VPWidenMemoryRecipe, public VPValue {3384 VPWidenLoadEVLRecipe(VPWidenLoadRecipe &L, VPValue *Addr, VPValue &EVL,3385 VPValue *Mask)3386 : VPWidenMemoryRecipe(VPDef::VPWidenLoadEVLSC, L.getIngredient(),3387 {Addr, &EVL}, L.isConsecutive(), L.isReverse(), L,3388 L.getDebugLoc()),3389 VPValue(this, &getIngredient()) {3390 setMask(Mask);3391 }3392 3393 VP_CLASSOF_IMPL(VPDef::VPWidenLoadEVLSC)3394 3395 /// Return the EVL operand.3396 VPValue *getEVL() const { return getOperand(1); }3397 3398 /// Generate the wide load or gather.3399 void execute(VPTransformState &State) override;3400 3401 /// Return the cost of this VPWidenLoadEVLRecipe.3402 InstructionCost computeCost(ElementCount VF,3403 VPCostContext &Ctx) const override;3404 3405 /// Returns true if the recipe only uses the first lane of operand \p Op.3406 bool usesFirstLaneOnly(const VPValue *Op) const override {3407 assert(is_contained(operands(), Op) &&3408 "Op must be an operand of the recipe");3409 // Widened loads only demand the first lane of EVL and consecutive loads3410 // only demand the first lane of their address.3411 return Op == getEVL() || (Op == getAddr() && isConsecutive());3412 }3413 3414protected:3415#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3416 /// Print the recipe.3417 void printRecipe(raw_ostream &O, const Twine &Indent,3418 VPSlotTracker &SlotTracker) const override;3419#endif3420};3421 3422/// A recipe for widening store operations, using the stored value, the address3423/// to store to and an optional mask.3424struct LLVM_ABI_FOR_TEST VPWidenStoreRecipe final : public VPWidenMemoryRecipe {3425 VPWidenStoreRecipe(StoreInst &Store, VPValue *Addr, VPValue *StoredVal,3426 VPValue *Mask, bool Consecutive, bool Reverse,3427 const VPIRMetadata &Metadata, DebugLoc DL)3428 : VPWidenMemoryRecipe(VPDef::VPWidenStoreSC, Store, {Addr, StoredVal},3429 Consecutive, Reverse, Metadata, DL) {3430 setMask(Mask);3431 }3432 3433 VPWidenStoreRecipe *clone() override {3434 return new VPWidenStoreRecipe(cast<StoreInst>(Ingredient), getAddr(),3435 getStoredValue(), getMask(), Consecutive,3436 Reverse, *this, getDebugLoc());3437 }3438 3439 VP_CLASSOF_IMPL(VPDef::VPWidenStoreSC);3440 3441 /// Return the value stored by this recipe.3442 VPValue *getStoredValue() const { return getOperand(1); }3443 3444 /// Generate a wide store or scatter.3445 void execute(VPTransformState &State) override;3446 3447 /// Returns true if the recipe only uses the first lane of operand \p Op.3448 bool usesFirstLaneOnly(const VPValue *Op) const override {3449 assert(is_contained(operands(), Op) &&3450 "Op must be an operand of the recipe");3451 // Widened, consecutive stores only demand the first lane of their address,3452 // unless the same operand is also stored.3453 return Op == getAddr() && isConsecutive() && Op != getStoredValue();3454 }3455 3456protected:3457#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3458 /// Print the recipe.3459 void printRecipe(raw_ostream &O, const Twine &Indent,3460 VPSlotTracker &SlotTracker) const override;3461#endif3462};3463 3464/// A recipe for widening store operations with vector-predication intrinsics,3465/// using the value to store, the address to store to, the explicit vector3466/// length and an optional mask.3467struct VPWidenStoreEVLRecipe final : public VPWidenMemoryRecipe {3468 VPWidenStoreEVLRecipe(VPWidenStoreRecipe &S, VPValue *Addr, VPValue &EVL,3469 VPValue *Mask)3470 : VPWidenMemoryRecipe(VPDef::VPWidenStoreEVLSC, S.getIngredient(),3471 {Addr, S.getStoredValue(), &EVL}, S.isConsecutive(),3472 S.isReverse(), S, S.getDebugLoc()) {3473 setMask(Mask);3474 }3475 3476 VP_CLASSOF_IMPL(VPDef::VPWidenStoreEVLSC)3477 3478 /// Return the address accessed by this recipe.3479 VPValue *getStoredValue() const { return getOperand(1); }3480 3481 /// Return the EVL operand.3482 VPValue *getEVL() const { return getOperand(2); }3483 3484 /// Generate the wide store or scatter.3485 void execute(VPTransformState &State) override;3486 3487 /// Return the cost of this VPWidenStoreEVLRecipe.3488 InstructionCost computeCost(ElementCount VF,3489 VPCostContext &Ctx) const override;3490 3491 /// Returns true if the recipe only uses the first lane of operand \p Op.3492 bool usesFirstLaneOnly(const VPValue *Op) const override {3493 assert(is_contained(operands(), Op) &&3494 "Op must be an operand of the recipe");3495 if (Op == getEVL()) {3496 assert(getStoredValue() != Op && "unexpected store of EVL");3497 return true;3498 }3499 // Widened, consecutive memory operations only demand the first lane of3500 // their address, unless the same operand is also stored. That latter can3501 // happen with opaque pointers.3502 return Op == getAddr() && isConsecutive() && Op != getStoredValue();3503 }3504 3505protected:3506#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3507 /// Print the recipe.3508 void printRecipe(raw_ostream &O, const Twine &Indent,3509 VPSlotTracker &SlotTracker) const override;3510#endif3511};3512 3513/// Recipe to expand a SCEV expression.3514class VPExpandSCEVRecipe : public VPSingleDefRecipe {3515 const SCEV *Expr;3516 3517public:3518 VPExpandSCEVRecipe(const SCEV *Expr)3519 : VPSingleDefRecipe(VPDef::VPExpandSCEVSC, {}), Expr(Expr) {}3520 3521 ~VPExpandSCEVRecipe() override = default;3522 3523 VPExpandSCEVRecipe *clone() override { return new VPExpandSCEVRecipe(Expr); }3524 3525 VP_CLASSOF_IMPL(VPDef::VPExpandSCEVSC)3526 3527 void execute(VPTransformState &State) override {3528 llvm_unreachable("SCEV expressions must be expanded before final execute");3529 }3530 3531 /// Return the cost of this VPExpandSCEVRecipe.3532 InstructionCost computeCost(ElementCount VF,3533 VPCostContext &Ctx) const override {3534 // TODO: Compute accurate cost after retiring the legacy cost model.3535 return 0;3536 }3537 3538 const SCEV *getSCEV() const { return Expr; }3539 3540protected:3541#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3542 /// Print the recipe.3543 void printRecipe(raw_ostream &O, const Twine &Indent,3544 VPSlotTracker &SlotTracker) const override;3545#endif3546};3547 3548/// Canonical scalar induction phi of the vector loop. Starting at the specified3549/// start value (either 0 or the resume value when vectorizing the epilogue3550/// loop). VPWidenCanonicalIVRecipe represents the vector version of the3551/// canonical induction variable.3552class VPCanonicalIVPHIRecipe : public VPHeaderPHIRecipe {3553public:3554 VPCanonicalIVPHIRecipe(VPValue *StartV, DebugLoc DL)3555 : VPHeaderPHIRecipe(VPDef::VPCanonicalIVPHISC, nullptr, StartV, DL) {}3556 3557 ~VPCanonicalIVPHIRecipe() override = default;3558 3559 VPCanonicalIVPHIRecipe *clone() override {3560 auto *R = new VPCanonicalIVPHIRecipe(getOperand(0), getDebugLoc());3561 R->addOperand(getBackedgeValue());3562 return R;3563 }3564 3565 VP_CLASSOF_IMPL(VPDef::VPCanonicalIVPHISC)3566 3567 void execute(VPTransformState &State) override {3568 llvm_unreachable("cannot execute this recipe, should be replaced by a "3569 "scalar phi recipe");3570 }3571 3572 /// Returns the scalar type of the induction.3573 Type *getScalarType() const {3574 return getStartValue()->getLiveInIRValue()->getType();3575 }3576 3577 /// Returns true if the recipe only uses the first lane of operand \p Op.3578 bool usesFirstLaneOnly(const VPValue *Op) const override {3579 assert(is_contained(operands(), Op) &&3580 "Op must be an operand of the recipe");3581 return true;3582 }3583 3584 /// Returns true if the recipe only uses the first part of operand \p Op.3585 bool usesFirstPartOnly(const VPValue *Op) const override {3586 assert(is_contained(operands(), Op) &&3587 "Op must be an operand of the recipe");3588 return true;3589 }3590 3591 /// Return the cost of this VPCanonicalIVPHIRecipe.3592 InstructionCost computeCost(ElementCount VF,3593 VPCostContext &Ctx) const override {3594 // For now, match the behavior of the legacy cost model.3595 return 0;3596 }3597 3598protected:3599#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3600 /// Print the recipe.3601 LLVM_ABI_FOR_TEST void printRecipe(raw_ostream &O, const Twine &Indent,3602 VPSlotTracker &SlotTracker) const override;3603#endif3604};3605 3606/// A recipe for generating the active lane mask for the vector loop that is3607/// used to predicate the vector operations.3608/// TODO: It would be good to use the existing VPWidenPHIRecipe instead and3609/// remove VPActiveLaneMaskPHIRecipe.3610class VPActiveLaneMaskPHIRecipe : public VPHeaderPHIRecipe {3611public:3612 VPActiveLaneMaskPHIRecipe(VPValue *StartMask, DebugLoc DL)3613 : VPHeaderPHIRecipe(VPDef::VPActiveLaneMaskPHISC, nullptr, StartMask,3614 DL) {}3615 3616 ~VPActiveLaneMaskPHIRecipe() override = default;3617 3618 VPActiveLaneMaskPHIRecipe *clone() override {3619 auto *R = new VPActiveLaneMaskPHIRecipe(getOperand(0), getDebugLoc());3620 if (getNumOperands() == 2)3621 R->addOperand(getOperand(1));3622 return R;3623 }3624 3625 VP_CLASSOF_IMPL(VPDef::VPActiveLaneMaskPHISC)3626 3627 /// Generate the active lane mask phi of the vector loop.3628 void execute(VPTransformState &State) override;3629 3630protected:3631#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3632 /// Print the recipe.3633 void printRecipe(raw_ostream &O, const Twine &Indent,3634 VPSlotTracker &SlotTracker) const override;3635#endif3636};3637 3638/// A recipe for generating the phi node for the current index of elements,3639/// adjusted in accordance with EVL value. It starts at the start value of the3640/// canonical induction and gets incremented by EVL in each iteration of the3641/// vector loop.3642class VPEVLBasedIVPHIRecipe : public VPHeaderPHIRecipe {3643public:3644 VPEVLBasedIVPHIRecipe(VPValue *StartIV, DebugLoc DL)3645 : VPHeaderPHIRecipe(VPDef::VPEVLBasedIVPHISC, nullptr, StartIV, DL) {}3646 3647 ~VPEVLBasedIVPHIRecipe() override = default;3648 3649 VPEVLBasedIVPHIRecipe *clone() override {3650 llvm_unreachable("cloning not implemented yet");3651 }3652 3653 VP_CLASSOF_IMPL(VPDef::VPEVLBasedIVPHISC)3654 3655 void execute(VPTransformState &State) override {3656 llvm_unreachable("cannot execute this recipe, should be replaced by a "3657 "scalar phi recipe");3658 }3659 3660 /// Return the cost of this VPEVLBasedIVPHIRecipe.3661 InstructionCost computeCost(ElementCount VF,3662 VPCostContext &Ctx) const override {3663 // For now, match the behavior of the legacy cost model.3664 return 0;3665 }3666 3667 /// Returns true if the recipe only uses the first lane of operand \p Op.3668 bool usesFirstLaneOnly(const VPValue *Op) const override {3669 assert(is_contained(operands(), Op) &&3670 "Op must be an operand of the recipe");3671 return true;3672 }3673 3674protected:3675#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3676 /// Print the recipe.3677 LLVM_ABI_FOR_TEST void printRecipe(raw_ostream &O, const Twine &Indent,3678 VPSlotTracker &SlotTracker) const override;3679#endif3680};3681 3682/// A Recipe for widening the canonical induction variable of the vector loop.3683class VPWidenCanonicalIVRecipe : public VPSingleDefRecipe,3684 public VPUnrollPartAccessor<1> {3685public:3686 VPWidenCanonicalIVRecipe(VPCanonicalIVPHIRecipe *CanonicalIV)3687 : VPSingleDefRecipe(VPDef::VPWidenCanonicalIVSC, {CanonicalIV}) {}3688 3689 ~VPWidenCanonicalIVRecipe() override = default;3690 3691 VPWidenCanonicalIVRecipe *clone() override {3692 return new VPWidenCanonicalIVRecipe(3693 cast<VPCanonicalIVPHIRecipe>(getOperand(0)));3694 }3695 3696 VP_CLASSOF_IMPL(VPDef::VPWidenCanonicalIVSC)3697 3698 /// Generate a canonical vector induction variable of the vector loop, with3699 /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and3700 /// step = <VF*UF, VF*UF, ..., VF*UF>.3701 void execute(VPTransformState &State) override;3702 3703 /// Return the cost of this VPWidenCanonicalIVPHIRecipe.3704 InstructionCost computeCost(ElementCount VF,3705 VPCostContext &Ctx) const override {3706 // TODO: Compute accurate cost after retiring the legacy cost model.3707 return 0;3708 }3709 3710protected:3711#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3712 /// Print the recipe.3713 void printRecipe(raw_ostream &O, const Twine &Indent,3714 VPSlotTracker &SlotTracker) const override;3715#endif3716};3717 3718/// A recipe for converting the input value \p IV value to the corresponding3719/// value of an IV with different start and step values, using Start + IV *3720/// Step.3721class VPDerivedIVRecipe : public VPSingleDefRecipe {3722 /// Kind of the induction.3723 const InductionDescriptor::InductionKind Kind;3724 /// If not nullptr, the floating point induction binary operator. Must be set3725 /// for floating point inductions.3726 const FPMathOperator *FPBinOp;3727 3728 /// Name to use for the generated IR instruction for the derived IV.3729 std::string Name;3730 3731public:3732 VPDerivedIVRecipe(const InductionDescriptor &IndDesc, VPValue *Start,3733 VPCanonicalIVPHIRecipe *CanonicalIV, VPValue *Step,3734 const Twine &Name = "")3735 : VPDerivedIVRecipe(3736 IndDesc.getKind(),3737 dyn_cast_or_null<FPMathOperator>(IndDesc.getInductionBinOp()),3738 Start, CanonicalIV, Step, Name) {}3739 3740 VPDerivedIVRecipe(InductionDescriptor::InductionKind Kind,3741 const FPMathOperator *FPBinOp, VPValue *Start, VPValue *IV,3742 VPValue *Step, const Twine &Name = "")3743 : VPSingleDefRecipe(VPDef::VPDerivedIVSC, {Start, IV, Step}), Kind(Kind),3744 FPBinOp(FPBinOp), Name(Name.str()) {}3745 3746 ~VPDerivedIVRecipe() override = default;3747 3748 VPDerivedIVRecipe *clone() override {3749 return new VPDerivedIVRecipe(Kind, FPBinOp, getStartValue(), getOperand(1),3750 getStepValue());3751 }3752 3753 VP_CLASSOF_IMPL(VPDef::VPDerivedIVSC)3754 3755 /// Generate the transformed value of the induction at offset StartValue (1.3756 /// operand) + IV (2. operand) * StepValue (3, operand).3757 void execute(VPTransformState &State) override;3758 3759 /// Return the cost of this VPDerivedIVRecipe.3760 InstructionCost computeCost(ElementCount VF,3761 VPCostContext &Ctx) const override {3762 // TODO: Compute accurate cost after retiring the legacy cost model.3763 return 0;3764 }3765 3766 Type *getScalarType() const {3767 return getStartValue()->getLiveInIRValue()->getType();3768 }3769 3770 VPValue *getStartValue() const { return getOperand(0); }3771 VPValue *getStepValue() const { return getOperand(2); }3772 3773 /// Returns true if the recipe only uses the first lane of operand \p Op.3774 bool usesFirstLaneOnly(const VPValue *Op) const override {3775 assert(is_contained(operands(), Op) &&3776 "Op must be an operand of the recipe");3777 return true;3778 }3779 3780protected:3781#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3782 /// Print the recipe.3783 void printRecipe(raw_ostream &O, const Twine &Indent,3784 VPSlotTracker &SlotTracker) const override;3785#endif3786};3787 3788/// A recipe for handling phi nodes of integer and floating-point inductions,3789/// producing their scalar values.3790class LLVM_ABI_FOR_TEST VPScalarIVStepsRecipe : public VPRecipeWithIRFlags,3791 public VPUnrollPartAccessor<3> {3792 Instruction::BinaryOps InductionOpcode;3793 3794public:3795 VPScalarIVStepsRecipe(VPValue *IV, VPValue *Step, VPValue *VF,3796 Instruction::BinaryOps Opcode, FastMathFlags FMFs,3797 DebugLoc DL)3798 : VPRecipeWithIRFlags(VPDef::VPScalarIVStepsSC,3799 ArrayRef<VPValue *>({IV, Step, VF}), FMFs, DL),3800 InductionOpcode(Opcode) {}3801 3802 VPScalarIVStepsRecipe(const InductionDescriptor &IndDesc, VPValue *IV,3803 VPValue *Step, VPValue *VF,3804 DebugLoc DL = DebugLoc::getUnknown())3805 : VPScalarIVStepsRecipe(3806 IV, Step, VF, IndDesc.getInductionOpcode(),3807 dyn_cast_or_null<FPMathOperator>(IndDesc.getInductionBinOp())3808 ? IndDesc.getInductionBinOp()->getFastMathFlags()3809 : FastMathFlags(),3810 DL) {}3811 3812 ~VPScalarIVStepsRecipe() override = default;3813 3814 VPScalarIVStepsRecipe *clone() override {3815 return new VPScalarIVStepsRecipe(3816 getOperand(0), getOperand(1), getOperand(2), InductionOpcode,3817 hasFastMathFlags() ? getFastMathFlags() : FastMathFlags(),3818 getDebugLoc());3819 }3820 3821 /// Return true if this VPScalarIVStepsRecipe corresponds to part 0. Note that3822 /// this is only accurate after the VPlan has been unrolled.3823 bool isPart0() const { return getUnrollPart(*this) == 0; }3824 3825 VP_CLASSOF_IMPL(VPDef::VPScalarIVStepsSC)3826 3827 /// Generate the scalarized versions of the phi node as needed by their users.3828 void execute(VPTransformState &State) override;3829 3830 /// Return the cost of this VPScalarIVStepsRecipe.3831 InstructionCost computeCost(ElementCount VF,3832 VPCostContext &Ctx) const override {3833 // TODO: Compute accurate cost after retiring the legacy cost model.3834 return 0;3835 }3836 3837 VPValue *getStepValue() const { return getOperand(1); }3838 3839 /// Returns true if the recipe only uses the first lane of operand \p Op.3840 bool usesFirstLaneOnly(const VPValue *Op) const override {3841 assert(is_contained(operands(), Op) &&3842 "Op must be an operand of the recipe");3843 return true;3844 }3845 3846protected:3847#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3848 /// Print the recipe.3849 void printRecipe(raw_ostream &O, const Twine &Indent,3850 VPSlotTracker &SlotTracker) const override;3851#endif3852};3853 3854/// Casting from VPRecipeBase -> VPPhiAccessors is supported for all recipe3855/// types implementing VPPhiAccessors. Used by isa<> & co.3856template <> struct CastIsPossible<VPPhiAccessors, const VPRecipeBase *> {3857 static inline bool isPossible(const VPRecipeBase *f) {3858 // TODO: include VPPredInstPHIRecipe too, once it implements VPPhiAccessors.3859 return isa<VPIRPhi, VPHeaderPHIRecipe, VPWidenPHIRecipe, VPPhi>(f);3860 }3861};3862/// Support casting from VPRecipeBase -> VPPhiAccessors, by down-casting to the3863/// recipe types implementing VPPhiAccessors. Used by cast<>, dyn_cast<> & co.3864template <typename SrcTy>3865struct CastInfoVPPhiAccessors : public CastIsPossible<VPPhiAccessors, SrcTy> {3866 3867 using Self = CastInfo<VPPhiAccessors, SrcTy>;3868 3869 /// doCast is used by cast<>.3870 static inline VPPhiAccessors *doCast(SrcTy R) {3871 return const_cast<VPPhiAccessors *>([R]() -> const VPPhiAccessors * {3872 switch (R->getVPDefID()) {3873 case VPDef::VPInstructionSC:3874 return cast<VPPhi>(R);3875 case VPDef::VPIRInstructionSC:3876 return cast<VPIRPhi>(R);3877 case VPDef::VPWidenPHISC:3878 return cast<VPWidenPHIRecipe>(R);3879 default:3880 return cast<VPHeaderPHIRecipe>(R);3881 }3882 }());3883 }3884 3885 /// doCastIfPossible is used by dyn_cast<>.3886 static inline VPPhiAccessors *doCastIfPossible(SrcTy f) {3887 if (!Self::isPossible(f))3888 return nullptr;3889 return doCast(f);3890 }3891};3892template <>3893struct CastInfo<VPPhiAccessors, VPRecipeBase *>3894 : CastInfoVPPhiAccessors<VPRecipeBase *> {};3895template <>3896struct CastInfo<VPPhiAccessors, const VPRecipeBase *>3897 : CastInfoVPPhiAccessors<const VPRecipeBase *> {};3898 3899/// Casting from (const) VPRecipeBase -> (const) VPIRMetadata is supported for3900/// all recipe types implementing VPIRMetadata. Used by isa<> & co.3901namespace detail {3902template <typename DstTy, typename RecipeBasePtrTy>3903static inline auto castToVPIRMetadata(RecipeBasePtrTy R) -> DstTy {3904 switch (R->getVPDefID()) {3905 case VPDef::VPInstructionSC:3906 return cast<VPInstruction>(R);3907 case VPDef::VPWidenSC:3908 return cast<VPWidenRecipe>(R);3909 case VPDef::VPWidenCastSC:3910 return cast<VPWidenCastRecipe>(R);3911 case VPDef::VPWidenIntrinsicSC:3912 return cast<VPWidenIntrinsicRecipe>(R);3913 case VPDef::VPWidenCallSC:3914 return cast<VPWidenCallRecipe>(R);3915 case VPDef::VPWidenSelectSC:3916 return cast<VPWidenSelectRecipe>(R);3917 case VPDef::VPReplicateSC:3918 return cast<VPReplicateRecipe>(R);3919 case VPDef::VPInterleaveSC:3920 case VPDef::VPInterleaveEVLSC:3921 return cast<VPInterleaveBase>(R);3922 case VPDef::VPWidenLoadSC:3923 case VPDef::VPWidenLoadEVLSC:3924 case VPDef::VPWidenStoreSC:3925 case VPDef::VPWidenStoreEVLSC:3926 return cast<VPWidenMemoryRecipe>(R);3927 default:3928 llvm_unreachable("invalid recipe for VPIRMetadata cast");3929 }3930}3931} // namespace detail3932 3933/// Support casting from VPRecipeBase -> VPIRMetadata, by down-casting to the3934/// recipe types implementing VPIRMetadata. Used by cast<>, dyn_cast<> & co.3935template <typename DstTy, typename SrcTy>3936struct CastInfoVPIRMetadata : public CastIsPossible<DstTy, SrcTy> {3937 static inline bool isPossible(SrcTy R) {3938 // NOTE: Each recipe inheriting from VPIRMetadata must be listed here and3939 // also handled in castToVPIRMetadata.3940 return isa<VPInstruction, VPWidenRecipe, VPWidenCastRecipe,3941 VPWidenIntrinsicRecipe, VPWidenCallRecipe, VPWidenSelectRecipe,3942 VPReplicateRecipe, VPInterleaveRecipe, VPInterleaveEVLRecipe,3943 VPWidenLoadRecipe, VPWidenLoadEVLRecipe, VPWidenStoreRecipe,3944 VPWidenStoreEVLRecipe>(R);3945 }3946 3947 using RetTy = DstTy *;3948 3949 /// doCast is used by cast<>.3950 static inline RetTy doCast(SrcTy R) {3951 return detail::castToVPIRMetadata<RetTy, SrcTy>(R);3952 }3953 3954 /// doCastIfPossible is used by dyn_cast<>.3955 static inline RetTy doCastIfPossible(SrcTy R) {3956 if (!isPossible(R))3957 return nullptr;3958 return doCast(R);3959 }3960};3961template <>3962struct CastInfo<VPIRMetadata, VPRecipeBase *>3963 : CastInfoVPIRMetadata<VPIRMetadata, VPRecipeBase *> {};3964template <>3965struct CastInfo<VPIRMetadata, const VPRecipeBase *>3966 : CastInfoVPIRMetadata<const VPIRMetadata, const VPRecipeBase *> {};3967 3968/// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It3969/// holds a sequence of zero or more VPRecipe's each representing a sequence of3970/// output IR instructions. All PHI-like recipes must come before any non-PHI recipes.3971class LLVM_ABI_FOR_TEST VPBasicBlock : public VPBlockBase {3972 friend class VPlan;3973 3974 /// Use VPlan::createVPBasicBlock to create VPBasicBlocks.3975 VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)3976 : VPBlockBase(VPBasicBlockSC, Name.str()) {3977 if (Recipe)3978 appendRecipe(Recipe);3979 }3980 3981public:3982 using RecipeListTy = iplist<VPRecipeBase>;3983 3984protected:3985 /// The VPRecipes held in the order of output instructions to generate.3986 RecipeListTy Recipes;3987 3988 VPBasicBlock(const unsigned char BlockSC, const Twine &Name = "")3989 : VPBlockBase(BlockSC, Name.str()) {}3990 3991public:3992 ~VPBasicBlock() override {3993 while (!Recipes.empty())3994 Recipes.pop_back();3995 }3996 3997 /// Instruction iterators...3998 using iterator = RecipeListTy::iterator;3999 using const_iterator = RecipeListTy::const_iterator;4000 using reverse_iterator = RecipeListTy::reverse_iterator;4001 using const_reverse_iterator = RecipeListTy::const_reverse_iterator;4002 4003 //===--------------------------------------------------------------------===//4004 /// Recipe iterator methods4005 ///4006 inline iterator begin() { return Recipes.begin(); }4007 inline const_iterator begin() const { return Recipes.begin(); }4008 inline iterator end() { return Recipes.end(); }4009 inline const_iterator end() const { return Recipes.end(); }4010 4011 inline reverse_iterator rbegin() { return Recipes.rbegin(); }4012 inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }4013 inline reverse_iterator rend() { return Recipes.rend(); }4014 inline const_reverse_iterator rend() const { return Recipes.rend(); }4015 4016 inline size_t size() const { return Recipes.size(); }4017 inline bool empty() const { return Recipes.empty(); }4018 inline const VPRecipeBase &front() const { return Recipes.front(); }4019 inline VPRecipeBase &front() { return Recipes.front(); }4020 inline const VPRecipeBase &back() const { return Recipes.back(); }4021 inline VPRecipeBase &back() { return Recipes.back(); }4022 4023 /// Returns a reference to the list of recipes.4024 RecipeListTy &getRecipeList() { return Recipes; }4025 4026 /// Returns a pointer to a member of the recipe list.4027 static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) {4028 return &VPBasicBlock::Recipes;4029 }4030 4031 /// Method to support type inquiry through isa, cast, and dyn_cast.4032 static inline bool classof(const VPBlockBase *V) {4033 return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC ||4034 V->getVPBlockID() == VPBlockBase::VPIRBasicBlockSC;4035 }4036 4037 void insert(VPRecipeBase *Recipe, iterator InsertPt) {4038 assert(Recipe && "No recipe to append.");4039 assert(!Recipe->Parent && "Recipe already in VPlan");4040 Recipe->Parent = this;4041 Recipes.insert(InsertPt, Recipe);4042 }4043 4044 /// Augment the existing recipes of a VPBasicBlock with an additional4045 /// \p Recipe as the last recipe.4046 void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }4047 4048 /// The method which generates the output IR instructions that correspond to4049 /// this VPBasicBlock, thereby "executing" the VPlan.4050 void execute(VPTransformState *State) override;4051 4052 /// Return the cost of this VPBasicBlock.4053 InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override;4054 4055 /// Return the position of the first non-phi node recipe in the block.4056 iterator getFirstNonPhi();4057 4058 /// Returns an iterator range over the PHI-like recipes in the block.4059 iterator_range<iterator> phis() {4060 return make_range(begin(), getFirstNonPhi());4061 }4062 4063 /// Split current block at \p SplitAt by inserting a new block between the4064 /// current block and its successors and moving all recipes starting at4065 /// SplitAt to the new block. Returns the new block.4066 VPBasicBlock *splitAt(iterator SplitAt);4067 4068 VPRegionBlock *getEnclosingLoopRegion();4069 const VPRegionBlock *getEnclosingLoopRegion() const;4070 4071#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4072 /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p4073 /// SlotTracker is used to print unnamed VPValue's using consequtive numbers.4074 ///4075 /// Note that the numbering is applied to the whole VPlan, so printing4076 /// individual blocks is consistent with the whole VPlan printing.4077 void print(raw_ostream &O, const Twine &Indent,4078 VPSlotTracker &SlotTracker) const override;4079 using VPBlockBase::print; // Get the print(raw_stream &O) version.4080#endif4081 4082 /// If the block has multiple successors, return the branch recipe terminating4083 /// the block. If there are no or only a single successor, return nullptr;4084 VPRecipeBase *getTerminator();4085 const VPRecipeBase *getTerminator() const;4086 4087 /// Returns true if the block is exiting it's parent region.4088 bool isExiting() const;4089 4090 /// Clone the current block and it's recipes, without updating the operands of4091 /// the cloned recipes.4092 VPBasicBlock *clone() override;4093 4094 /// Returns the predecessor block at index \p Idx with the predecessors as per4095 /// the corresponding plain CFG. If the block is an entry block to a region,4096 /// the first predecessor is the single predecessor of a region, and the4097 /// second predecessor is the exiting block of the region.4098 const VPBasicBlock *getCFGPredecessor(unsigned Idx) const;4099 4100protected:4101 /// Execute the recipes in the IR basic block \p BB.4102 void executeRecipes(VPTransformState *State, BasicBlock *BB);4103 4104 /// Connect the VPBBs predecessors' in the VPlan CFG to the IR basic block4105 /// generated for this VPBB.4106 void connectToPredecessors(VPTransformState &State);4107 4108private:4109 /// Create an IR BasicBlock to hold the output instructions generated by this4110 /// VPBasicBlock, and return it. Update the CFGState accordingly.4111 BasicBlock *createEmptyBasicBlock(VPTransformState &State);4112};4113 4114inline const VPBasicBlock *4115VPPhiAccessors::getIncomingBlock(unsigned Idx) const {4116 return getAsRecipe()->getParent()->getCFGPredecessor(Idx);4117}4118 4119/// A special type of VPBasicBlock that wraps an existing IR basic block.4120/// Recipes of the block get added before the first non-phi instruction in the4121/// wrapped block.4122/// Note: At the moment, VPIRBasicBlock can only be used to wrap VPlan's4123/// preheader block.4124class VPIRBasicBlock : public VPBasicBlock {4125 friend class VPlan;4126 4127 BasicBlock *IRBB;4128 4129 /// Use VPlan::createVPIRBasicBlock to create VPIRBasicBlocks.4130 VPIRBasicBlock(BasicBlock *IRBB)4131 : VPBasicBlock(VPIRBasicBlockSC,4132 (Twine("ir-bb<") + IRBB->getName() + Twine(">")).str()),4133 IRBB(IRBB) {}4134 4135public:4136 ~VPIRBasicBlock() override = default;4137 4138 static inline bool classof(const VPBlockBase *V) {4139 return V->getVPBlockID() == VPBlockBase::VPIRBasicBlockSC;4140 }4141 4142 /// The method which generates the output IR instructions that correspond to4143 /// this VPBasicBlock, thereby "executing" the VPlan.4144 void execute(VPTransformState *State) override;4145 4146 VPIRBasicBlock *clone() override;4147 4148 BasicBlock *getIRBasicBlock() const { return IRBB; }4149};4150 4151/// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks4152/// which form a Single-Entry-Single-Exiting subgraph of the output IR CFG.4153/// A VPRegionBlock may indicate that its contents are to be replicated several4154/// times. This is designed to support predicated scalarization, in which a4155/// scalar if-then code structure needs to be generated VF * UF times. Having4156/// this replication indicator helps to keep a single model for multiple4157/// candidate VF's. The actual replication takes place only once the desired VF4158/// and UF have been determined.4159class LLVM_ABI_FOR_TEST VPRegionBlock : public VPBlockBase {4160 friend class VPlan;4161 4162 /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.4163 VPBlockBase *Entry;4164 4165 /// Hold the Single Exiting block of the SESE region modelled by the4166 /// VPRegionBlock.4167 VPBlockBase *Exiting;4168 4169 /// An indicator whether this region is to generate multiple replicated4170 /// instances of output IR corresponding to its VPBlockBases.4171 bool IsReplicator;4172 4173 /// Use VPlan::createVPRegionBlock to create VPRegionBlocks.4174 VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exiting,4175 const std::string &Name = "", bool IsReplicator = false)4176 : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exiting(Exiting),4177 IsReplicator(IsReplicator) {4178 assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");4179 assert(Exiting->getSuccessors().empty() && "Exit block has successors.");4180 Entry->setParent(this);4181 Exiting->setParent(this);4182 }4183 VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)4184 : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exiting(nullptr),4185 IsReplicator(IsReplicator) {}4186 4187public:4188 ~VPRegionBlock() override = default;4189 4190 /// Method to support type inquiry through isa, cast, and dyn_cast.4191 static inline bool classof(const VPBlockBase *V) {4192 return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;4193 }4194 4195 const VPBlockBase *getEntry() const { return Entry; }4196 VPBlockBase *getEntry() { return Entry; }4197 4198 /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p4199 /// EntryBlock must have no predecessors.4200 void setEntry(VPBlockBase *EntryBlock) {4201 assert(EntryBlock->getPredecessors().empty() &&4202 "Entry block cannot have predecessors.");4203 Entry = EntryBlock;4204 EntryBlock->setParent(this);4205 }4206 4207 const VPBlockBase *getExiting() const { return Exiting; }4208 VPBlockBase *getExiting() { return Exiting; }4209 4210 /// Set \p ExitingBlock as the exiting VPBlockBase of this VPRegionBlock. \p4211 /// ExitingBlock must have no successors.4212 void setExiting(VPBlockBase *ExitingBlock) {4213 assert(ExitingBlock->getSuccessors().empty() &&4214 "Exit block cannot have successors.");4215 Exiting = ExitingBlock;4216 ExitingBlock->setParent(this);4217 }4218 4219 /// Returns the pre-header VPBasicBlock of the loop region.4220 VPBasicBlock *getPreheaderVPBB() {4221 assert(!isReplicator() && "should only get pre-header of loop regions");4222 return getSinglePredecessor()->getExitingBasicBlock();4223 }4224 4225 /// An indicator whether this region is to generate multiple replicated4226 /// instances of output IR corresponding to its VPBlockBases.4227 bool isReplicator() const { return IsReplicator; }4228 4229 /// The method which generates the output IR instructions that correspond to4230 /// this VPRegionBlock, thereby "executing" the VPlan.4231 void execute(VPTransformState *State) override;4232 4233 // Return the cost of this region.4234 InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override;4235 4236#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4237 /// Print this VPRegionBlock to \p O (recursively), prefixing all lines with4238 /// \p Indent. \p SlotTracker is used to print unnamed VPValue's using4239 /// consequtive numbers.4240 ///4241 /// Note that the numbering is applied to the whole VPlan, so printing4242 /// individual regions is consistent with the whole VPlan printing.4243 void print(raw_ostream &O, const Twine &Indent,4244 VPSlotTracker &SlotTracker) const override;4245 using VPBlockBase::print; // Get the print(raw_stream &O) version.4246#endif4247 4248 /// Clone all blocks in the single-entry single-exit region of the block and4249 /// their recipes without updating the operands of the cloned recipes.4250 VPRegionBlock *clone() override;4251 4252 /// Remove the current region from its VPlan, connecting its predecessor to4253 /// its entry, and its exiting block to its successor.4254 void dissolveToCFGLoop();4255 4256 /// Returns the canonical induction recipe of the region.4257 VPCanonicalIVPHIRecipe *getCanonicalIV() {4258 VPBasicBlock *EntryVPBB = getEntryBasicBlock();4259 if (EntryVPBB->empty()) {4260 // VPlan native path. TODO: Unify both code paths.4261 EntryVPBB = cast<VPBasicBlock>(EntryVPBB->getSingleSuccessor());4262 }4263 return cast<VPCanonicalIVPHIRecipe>(&*EntryVPBB->begin());4264 }4265 const VPCanonicalIVPHIRecipe *getCanonicalIV() const {4266 return const_cast<VPRegionBlock *>(this)->getCanonicalIV();4267 }4268 4269 /// Return the type of the canonical IV for loop regions.4270 Type *getCanonicalIVType() { return getCanonicalIV()->getScalarType(); }4271 const Type *getCanonicalIVType() const {4272 return getCanonicalIV()->getScalarType();4273 }4274};4275 4276inline VPRegionBlock *VPRecipeBase::getRegion() {4277 return getParent()->getParent();4278}4279 4280inline const VPRegionBlock *VPRecipeBase::getRegion() const {4281 return getParent()->getParent();4282}4283 4284/// VPlan models a candidate for vectorization, encoding various decisions take4285/// to produce efficient output IR, including which branches, basic-blocks and4286/// output IR instructions to generate, and their cost. VPlan holds a4287/// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry4288/// VPBasicBlock.4289class VPlan {4290 friend class VPlanPrinter;4291 friend class VPSlotTracker;4292 4293 /// VPBasicBlock corresponding to the original preheader. Used to place4294 /// VPExpandSCEV recipes for expressions used during skeleton creation and the4295 /// rest of VPlan execution.4296 /// When this VPlan is used for the epilogue vector loop, the entry will be4297 /// replaced by a new entry block created during skeleton creation.4298 VPBasicBlock *Entry;4299 4300 /// VPIRBasicBlock wrapping the header of the original scalar loop.4301 VPIRBasicBlock *ScalarHeader;4302 4303 /// Immutable list of VPIRBasicBlocks wrapping the exit blocks of the original4304 /// scalar loop. Note that some exit blocks may be unreachable at the moment,4305 /// e.g. if the scalar epilogue always executes.4306 SmallVector<VPIRBasicBlock *, 2> ExitBlocks;4307 4308 /// Holds the VFs applicable to this VPlan.4309 SmallSetVector<ElementCount, 2> VFs;4310 4311 /// Holds the UFs applicable to this VPlan. If empty, the VPlan is valid for4312 /// any UF.4313 SmallSetVector<unsigned, 2> UFs;4314 4315 /// Holds the name of the VPlan, for printing.4316 std::string Name;4317 4318 /// Represents the trip count of the original loop, for folding4319 /// the tail.4320 VPValue *TripCount = nullptr;4321 4322 /// Represents the backedge taken count of the original loop, for folding4323 /// the tail. It equals TripCount - 1.4324 VPValue *BackedgeTakenCount = nullptr;4325 4326 /// Represents the vector trip count.4327 VPValue VectorTripCount;4328 4329 /// Represents the vectorization factor of the loop.4330 VPValue VF;4331 4332 /// Represents the loop-invariant VF * UF of the vector loop region.4333 VPValue VFxUF;4334 4335 /// Holds a mapping between Values and their corresponding VPValue inside4336 /// VPlan.4337 Value2VPValueTy Value2VPValue;4338 4339 /// Contains all the external definitions created for this VPlan. External4340 /// definitions are VPValues that hold a pointer to their underlying IR.4341 SmallVector<VPValue *, 16> VPLiveIns;4342 4343 /// Blocks allocated and owned by the VPlan. They will be deleted once the4344 /// VPlan is destroyed.4345 SmallVector<VPBlockBase *> CreatedBlocks;4346 4347 /// Construct a VPlan with \p Entry to the plan and with \p ScalarHeader4348 /// wrapping the original header of the scalar loop.4349 VPlan(VPBasicBlock *Entry, VPIRBasicBlock *ScalarHeader)4350 : Entry(Entry), ScalarHeader(ScalarHeader) {4351 Entry->setPlan(this);4352 assert(ScalarHeader->getNumSuccessors() == 0 &&4353 "scalar header must be a leaf node");4354 }4355 4356public:4357 /// Construct a VPlan for \p L. This will create VPIRBasicBlocks wrapping the4358 /// original preheader and scalar header of \p L, to be used as entry and4359 /// scalar header blocks of the new VPlan.4360 VPlan(Loop *L);4361 4362 /// Construct a VPlan with a new VPBasicBlock as entry, a VPIRBasicBlock4363 /// wrapping \p ScalarHeaderBB and a trip count of \p TC.4364 VPlan(BasicBlock *ScalarHeaderBB) {4365 setEntry(createVPBasicBlock("preheader"));4366 ScalarHeader = createVPIRBasicBlock(ScalarHeaderBB);4367 }4368 4369 LLVM_ABI_FOR_TEST ~VPlan();4370 4371 void setEntry(VPBasicBlock *VPBB) {4372 Entry = VPBB;4373 VPBB->setPlan(this);4374 }4375 4376 /// Generate the IR code for this VPlan.4377 void execute(VPTransformState *State);4378 4379 /// Return the cost of this plan.4380 InstructionCost cost(ElementCount VF, VPCostContext &Ctx);4381 4382 VPBasicBlock *getEntry() { return Entry; }4383 const VPBasicBlock *getEntry() const { return Entry; }4384 4385 /// Returns the preheader of the vector loop region, if one exists, or null4386 /// otherwise.4387 VPBasicBlock *getVectorPreheader() {4388 VPRegionBlock *VectorRegion = getVectorLoopRegion();4389 return VectorRegion4390 ? cast<VPBasicBlock>(VectorRegion->getSinglePredecessor())4391 : nullptr;4392 }4393 4394 /// Returns the VPRegionBlock of the vector loop.4395 LLVM_ABI_FOR_TEST VPRegionBlock *getVectorLoopRegion();4396 LLVM_ABI_FOR_TEST const VPRegionBlock *getVectorLoopRegion() const;4397 4398 /// Returns the 'middle' block of the plan, that is the block that selects4399 /// whether to execute the scalar tail loop or the exit block from the loop4400 /// latch. If there is an early exit from the vector loop, the middle block4401 /// conceptully has the early exit block as third successor, split accross 24402 /// VPBBs. In that case, the second VPBB selects whether to execute the scalar4403 /// tail loop or the exit bock. If the scalar tail loop or exit block are4404 /// known to always execute, the middle block may branch directly to that4405 /// block. This function cannot be called once the vector loop region has been4406 /// removed.4407 VPBasicBlock *getMiddleBlock() {4408 VPRegionBlock *LoopRegion = getVectorLoopRegion();4409 assert(4410 LoopRegion &&4411 "cannot call the function after vector loop region has been removed");4412 auto *RegionSucc = cast<VPBasicBlock>(LoopRegion->getSingleSuccessor());4413 if (RegionSucc->getSingleSuccessor() ||4414 is_contained(RegionSucc->getSuccessors(), getScalarPreheader()))4415 return RegionSucc;4416 // There is an early exit. The successor of RegionSucc is the middle block.4417 return cast<VPBasicBlock>(RegionSucc->getSuccessors()[1]);4418 }4419 4420 const VPBasicBlock *getMiddleBlock() const {4421 return const_cast<VPlan *>(this)->getMiddleBlock();4422 }4423 4424 /// Return the VPBasicBlock for the preheader of the scalar loop.4425 VPBasicBlock *getScalarPreheader() const {4426 return cast<VPBasicBlock>(getScalarHeader()->getSinglePredecessor());4427 }4428 4429 /// Return the VPIRBasicBlock wrapping the header of the scalar loop.4430 VPIRBasicBlock *getScalarHeader() const { return ScalarHeader; }4431 4432 /// Return an ArrayRef containing VPIRBasicBlocks wrapping the exit blocks of4433 /// the original scalar loop.4434 ArrayRef<VPIRBasicBlock *> getExitBlocks() const { return ExitBlocks; }4435 4436 /// Return the VPIRBasicBlock corresponding to \p IRBB. \p IRBB must be an4437 /// exit block.4438 VPIRBasicBlock *getExitBlock(BasicBlock *IRBB) const;4439 4440 /// Returns true if \p VPBB is an exit block.4441 bool isExitBlock(VPBlockBase *VPBB);4442 4443 /// The trip count of the original loop.4444 VPValue *getTripCount() const {4445 assert(TripCount && "trip count needs to be set before accessing it");4446 return TripCount;4447 }4448 4449 /// Set the trip count assuming it is currently null; if it is not - use4450 /// resetTripCount().4451 void setTripCount(VPValue *NewTripCount) {4452 assert(!TripCount && NewTripCount && "TripCount should not be set yet.");4453 TripCount = NewTripCount;4454 }4455 4456 /// Resets the trip count for the VPlan. The caller must make sure all uses of4457 /// the original trip count have been replaced.4458 void resetTripCount(VPValue *NewTripCount) {4459 assert(TripCount && NewTripCount && TripCount->getNumUsers() == 0 &&4460 "TripCount must be set when resetting");4461 TripCount = NewTripCount;4462 }4463 4464 /// The backedge taken count of the original loop.4465 VPValue *getOrCreateBackedgeTakenCount() {4466 if (!BackedgeTakenCount)4467 BackedgeTakenCount = new VPValue();4468 return BackedgeTakenCount;4469 }4470 VPValue *getBackedgeTakenCount() const { return BackedgeTakenCount; }4471 4472 /// The vector trip count.4473 VPValue &getVectorTripCount() { return VectorTripCount; }4474 4475 /// Returns the VF of the vector loop region.4476 VPValue &getVF() { return VF; };4477 const VPValue &getVF() const { return VF; };4478 4479 /// Returns VF * UF of the vector loop region.4480 VPValue &getVFxUF() { return VFxUF; }4481 4482 LLVMContext &getContext() const {4483 return getScalarHeader()->getIRBasicBlock()->getContext();4484 }4485 4486 void addVF(ElementCount VF) { VFs.insert(VF); }4487 4488 void setVF(ElementCount VF) {4489 assert(hasVF(VF) && "Cannot set VF not already in plan");4490 VFs.clear();4491 VFs.insert(VF);4492 }4493 4494 bool hasVF(ElementCount VF) const { return VFs.count(VF); }4495 bool hasScalableVF() const {4496 return any_of(VFs, [](ElementCount VF) { return VF.isScalable(); });4497 }4498 4499 /// Returns an iterator range over all VFs of the plan.4500 iterator_range<SmallSetVector<ElementCount, 2>::iterator>4501 vectorFactors() const {4502 return VFs;4503 }4504 4505 bool hasScalarVFOnly() const {4506 bool HasScalarVFOnly = VFs.size() == 1 && VFs[0].isScalar();4507 assert(HasScalarVFOnly == hasVF(ElementCount::getFixed(1)) &&4508 "Plan with scalar VF should only have a single VF");4509 return HasScalarVFOnly;4510 }4511 4512 bool hasUF(unsigned UF) const { return UFs.empty() || UFs.contains(UF); }4513 4514 unsigned getUF() const {4515 assert(UFs.size() == 1 && "Expected a single UF");4516 return UFs[0];4517 }4518 4519 void setUF(unsigned UF) {4520 assert(hasUF(UF) && "Cannot set the UF not already in plan");4521 UFs.clear();4522 UFs.insert(UF);4523 }4524 4525 /// Returns true if the VPlan already has been unrolled, i.e. it has a single4526 /// concrete UF.4527 bool isUnrolled() const { return UFs.size() == 1; }4528 4529 /// Return a string with the name of the plan and the applicable VFs and UFs.4530 std::string getName() const;4531 4532 void setName(const Twine &newName) { Name = newName.str(); }4533 4534 /// Gets the live-in VPValue for \p V or adds a new live-in (if none exists4535 /// yet) for \p V.4536 VPValue *getOrAddLiveIn(Value *V) {4537 assert(V && "Trying to get or add the VPValue of a null Value");4538 auto [It, Inserted] = Value2VPValue.try_emplace(V);4539 if (Inserted) {4540 VPValue *VPV = new VPValue(V);4541 VPLiveIns.push_back(VPV);4542 assert(VPV->isLiveIn() && "VPV must be a live-in.");4543 It->second = VPV;4544 }4545 4546 assert(It->second->isLiveIn() && "Only live-ins should be in mapping");4547 return It->second;4548 }4549 4550 /// Return a VPValue wrapping i1 true.4551 VPValue *getTrue() { return getConstantInt(1, 1); }4552 4553 /// Return a VPValue wrapping i1 false.4554 VPValue *getFalse() { return getConstantInt(1, 0); }4555 4556 /// Return a VPValue wrapping a ConstantInt with the given type and value.4557 VPValue *getConstantInt(Type *Ty, uint64_t Val, bool IsSigned = false) {4558 return getOrAddLiveIn(ConstantInt::get(Ty, Val, IsSigned));4559 }4560 4561 /// Return a VPValue wrapping a ConstantInt with the given bitwidth and value.4562 VPValue *getConstantInt(unsigned BitWidth, uint64_t Val,4563 bool IsSigned = false) {4564 return getConstantInt(APInt(BitWidth, Val, IsSigned));4565 }4566 4567 /// Return a VPValue wrapping a ConstantInt with the given APInt value.4568 VPValue *getConstantInt(const APInt &Val) {4569 return getOrAddLiveIn(ConstantInt::get(getContext(), Val));4570 }4571 4572 /// Return the live-in VPValue for \p V, if there is one or nullptr otherwise.4573 VPValue *getLiveIn(Value *V) const { return Value2VPValue.lookup(V); }4574 4575 /// Return the list of live-in VPValues available in the VPlan.4576 ArrayRef<VPValue *> getLiveIns() const {4577 assert(all_of(Value2VPValue,4578 [this](const auto &P) {4579 return is_contained(VPLiveIns, P.second);4580 }) &&4581 "all VPValues in Value2VPValue must also be in VPLiveIns");4582 return VPLiveIns;4583 }4584 4585#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4586 /// Print the live-ins of this VPlan to \p O.4587 void printLiveIns(raw_ostream &O) const;4588 4589 /// Print this VPlan to \p O.4590 LLVM_ABI_FOR_TEST void print(raw_ostream &O) const;4591 4592 /// Print this VPlan in DOT format to \p O.4593 LLVM_ABI_FOR_TEST void printDOT(raw_ostream &O) const;4594 4595 /// Dump the plan to stderr (for debugging).4596 LLVM_DUMP_METHOD void dump() const;4597#endif4598 4599 /// Clone the current VPlan, update all VPValues of the new VPlan and cloned4600 /// recipes to refer to the clones, and return it.4601 LLVM_ABI_FOR_TEST VPlan *duplicate();4602 4603 /// Create a new VPBasicBlock with \p Name and containing \p Recipe if4604 /// present. The returned block is owned by the VPlan and deleted once the4605 /// VPlan is destroyed.4606 VPBasicBlock *createVPBasicBlock(const Twine &Name,4607 VPRecipeBase *Recipe = nullptr) {4608 auto *VPB = new VPBasicBlock(Name, Recipe);4609 CreatedBlocks.push_back(VPB);4610 return VPB;4611 }4612 4613 /// Create a new loop region with \p Name and entry and exiting blocks set4614 /// to \p Entry and \p Exiting respectively, if set. The returned block is4615 /// owned by the VPlan and deleted once the VPlan is destroyed.4616 VPRegionBlock *createLoopRegion(const std::string &Name = "",4617 VPBlockBase *Entry = nullptr,4618 VPBlockBase *Exiting = nullptr) {4619 auto *VPB = Entry ? new VPRegionBlock(Entry, Exiting, Name)4620 : new VPRegionBlock(Name);4621 CreatedBlocks.push_back(VPB);4622 return VPB;4623 }4624 4625 /// Create a new replicate region with \p Entry, \p Exiting and \p Name. The4626 /// returned block is owned by the VPlan and deleted once the VPlan is4627 /// destroyed.4628 VPRegionBlock *createReplicateRegion(VPBlockBase *Entry, VPBlockBase *Exiting,4629 const std::string &Name = "") {4630 auto *VPB = new VPRegionBlock(Entry, Exiting, Name, true);4631 CreatedBlocks.push_back(VPB);4632 return VPB;4633 }4634 4635 /// Create a VPIRBasicBlock wrapping \p IRBB, but do not create4636 /// VPIRInstructions wrapping the instructions in t\p IRBB. The returned4637 /// block is owned by the VPlan and deleted once the VPlan is destroyed.4638 VPIRBasicBlock *createEmptyVPIRBasicBlock(BasicBlock *IRBB);4639 4640 /// Create a VPIRBasicBlock from \p IRBB containing VPIRInstructions for all4641 /// instructions in \p IRBB, except its terminator which is managed by the4642 /// successors of the block in VPlan. The returned block is owned by the VPlan4643 /// and deleted once the VPlan is destroyed.4644 LLVM_ABI_FOR_TEST VPIRBasicBlock *createVPIRBasicBlock(BasicBlock *IRBB);4645 4646 /// Returns true if the VPlan is based on a loop with an early exit. That is4647 /// the case if the VPlan has either more than one exit block or a single exit4648 /// block with multiple predecessors (one for the exit via the latch and one4649 /// via the other early exit).4650 bool hasEarlyExit() const {4651 return count_if(ExitBlocks,4652 [](VPIRBasicBlock *EB) { return EB->hasPredecessors(); }) >4653 1 ||4654 (ExitBlocks.size() == 1 && ExitBlocks[0]->getNumPredecessors() > 1);4655 }4656 4657 /// Returns true if the scalar tail may execute after the vector loop. Note4658 /// that this relies on unneeded branches to the scalar tail loop being4659 /// removed.4660 bool hasScalarTail() const {4661 return !(!getScalarPreheader()->hasPredecessors() ||4662 getScalarPreheader()->getSinglePredecessor() == getEntry());4663 }4664};4665 4666#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4667inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) {4668 Plan.print(OS);4669 return OS;4670}4671#endif4672 4673} // end namespace llvm4674 4675#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H4676