1//===- VPlan.h - Represent A Vectorizer Plan --------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// This file contains the declarations of the Vectorization Plan base classes:
11/// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual
12/// VPBlockBase, together implementing a Hierarchical CFG;
13/// 2. Pure virtual VPRecipeBase serving as the base class for recipes contained
14/// within VPBasicBlocks;
15/// 3. Pure virtual VPSingleDefRecipe serving as a base class for recipes that
16/// also inherit from VPValue.
17/// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned
18/// instruction;
19/// 5. The VPlan class holding a candidate for vectorization;
20/// These are documented in docs/VectorizationPlan.rst.
21//
22//===----------------------------------------------------------------------===//
23
24#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
25#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
26
27#include "VPlanValue.h"
28#include "llvm/ADT/Bitfields.h"
29#include "llvm/ADT/MapVector.h"
30#include "llvm/ADT/SetVector.h"
31#include "llvm/ADT/SmallPtrSet.h"
32#include "llvm/ADT/SmallVector.h"
33#include "llvm/ADT/Twine.h"
34#include "llvm/ADT/ilist.h"
35#include "llvm/ADT/ilist_node.h"
36#include "llvm/Analysis/IVDescriptors.h"
37#include "llvm/Analysis/MemoryLocation.h"
38#include "llvm/Analysis/VectorUtils.h"
39#include "llvm/IR/Attributes.h"
40#include "llvm/IR/DebugLoc.h"
41#include "llvm/IR/FMF.h"
42#include "llvm/IR/Operator.h"
43#include "llvm/Support/BlockFrequency.h"
44#include "llvm/Support/Compiler.h"
45#include "llvm/Support/InstructionCost.h"
46#include <cassert>
47#include <cstddef>
48#include <functional>
49#include <optional>
50#include <string>
51#include <utility>
52#include <variant>
53
54namespace llvm {
55
56class BasicBlock;
57class DominatorTree;
58struct VPTransformState;
59class raw_ostream;
60class SCEV;
61class SCEVPredicate;
62class Type;
63class VPBasicBlock;
64struct VPBuilderDefaultInserter;
65template <typename InserterTy = VPBuilderDefaultInserter> class VPBuilderBase;
66using VPBuilder = VPBuilderBase<>;
67class VPDominatorTree;
68class VPRegionBlock;
69class VPlan;
70class VPReplicateRecipe;
71class Value;
72class LoopVectorizationCostModel;
73
74struct VPCostContext;
75
76using VPlanPtr = std::unique_ptr<VPlan>;
77
78/// \enum UncountableExitStyle
79/// Different methods of handling early exits.
80///
81enum class UncountableExitStyle {
82 /// No side effects to worry about, so we can process any uncountable exits
83 /// in the loop and branch either to the middle block if the trip count was
84 /// reached, or an early exitblock to determine which exit was taken.
85 ReadOnly,
86 /// All memory operations other than the load(s) required to determine whether
87 /// an uncountable exit occurre will be masked based on that condition. If an
88 /// uncountable exit is taken, then all lanes before the exiting lane will
89 /// complete, leaving just the final lane to execute in the scalar tail.
90 MaskedHandleExitInScalarLoop,
91};
92
93/// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
94/// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
95class LLVM_ABI_FOR_TEST VPBlockBase {
96 friend class VPBlockUtils;
97
98protected:
99 /// An enumeration for keeping track of the concrete subclass of VPBlockBase
100 /// that are actually instantiated. Values of this enumeration are kept in the
101 /// SubclassID field of the VPBlockBase objects. They are used for concrete
102 /// type identification.
103 using VPBlockTy = enum : unsigned char {
104 VPRegionBlockSC,
105 VPBasicBlockSC,
106 VPIRBasicBlockSC
107 };
108
109private:
110 /// An optional name for the block.
111 std::string Name;
112
113 /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
114 /// it is a topmost VPBlockBase.
115 VPRegionBlock *Parent = nullptr;
116
117 /// List of predecessor blocks.
118 SmallVector<VPBlockBase *, 1> Predecessors;
119
120 /// List of successor blocks.
121 SmallVector<VPBlockBase *, 1> Successors;
122
123 /// VPlan containing the block. Set when the block is created via VPlan
124 /// helpers.
125 VPlan *Plan = nullptr;
126
127 /// Subclass identifier (for isa/dyn_cast).
128 const VPBlockTy SubclassID;
129
130 /// Unique number, used as node number in the dominator tree.
131 unsigned Number;
132
133 /// Add \p Successor as the last successor to this block.
134 void appendSuccessor(VPBlockBase *Successor) {
135 assert(Successor && "Cannot add nullptr successor!");
136 Successors.push_back(Elt: Successor);
137 }
138
139 /// Add \p Predecessor as the last predecessor to this block.
140 void appendPredecessor(VPBlockBase *Predecessor) {
141 assert(Predecessor && "Cannot add nullptr predecessor!");
142 Predecessors.push_back(Elt: Predecessor);
143 }
144
145 /// Remove \p Predecessor from the predecessors of this block.
146 void removePredecessor(VPBlockBase *Predecessor) {
147 auto Pos = find(Range&: Predecessors, Val: Predecessor);
148 assert(Pos && "Predecessor does not exist");
149 Predecessors.erase(CI: Pos);
150 }
151
152 /// Remove \p Successor from the successors of this block.
153 void removeSuccessor(VPBlockBase *Successor) {
154 auto Pos = find(Range&: Successors, Val: Successor);
155 assert(Pos && "Successor does not exist");
156 Successors.erase(CI: Pos);
157 }
158
159 /// This function replaces one predecessor with another, useful when
160 /// trying to replace an old block in the CFG with a new one.
161 void replacePredecessor(VPBlockBase *Old, VPBlockBase *New) {
162 auto I = find(Range&: Predecessors, Val: Old);
163 assert(I != Predecessors.end());
164 assert(Old->getParent() == New->getParent() &&
165 "replaced predecessor must have the same parent");
166 *I = New;
167 }
168
169 /// This function replaces one successor with another, useful when
170 /// trying to replace an old block in the CFG with a new one.
171 void replaceSuccessor(VPBlockBase *Old, VPBlockBase *New) {
172 auto I = find(Range&: Successors, Val: Old);
173 assert(I != Successors.end());
174 assert(Old->getParent() == New->getParent() &&
175 "replaced successor must have the same parent");
176 *I = New;
177 }
178
179public:
180 using VPBlocksTy = SmallVectorImpl<VPBlockBase *>;
181
182 virtual ~VPBlockBase() = default;
183
184 const std::string &getName() const { return Name; }
185
186 void setName(const Twine &newName) { Name = newName.str(); }
187
188 /// \return an ID for the concrete type of this object.
189 /// This is used to implement the classof checks. This should not be used
190 /// for any other purpose, as the values may change as LLVM evolves.
191 unsigned getVPBlockID() const { return SubclassID; }
192
193 VPRegionBlock *getParent() { return Parent; }
194 const VPRegionBlock *getParent() const { return Parent; }
195
196 /// \return A pointer to the plan containing the current block.
197 VPlan *getPlan() { return Plan; }
198 const VPlan *getPlan() const { return Plan; }
199
200 /// Sets the pointer of the plan containing the block.
201 void setPlan(VPlan *ParentPlan) { Plan = ParentPlan; }
202
203 void setParent(VPRegionBlock *P) { Parent = P; }
204
205 /// \return the VPBasicBlock that is the entry of this VPBlockBase,
206 /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
207 /// VPBlockBase is a VPBasicBlock, it is returned.
208 const VPBasicBlock *getEntryBasicBlock() const;
209 VPBasicBlock *getEntryBasicBlock();
210
211 /// \return the VPBasicBlock that is the exiting this VPBlockBase,
212 /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
213 /// VPBlockBase is a VPBasicBlock, it is returned.
214 const VPBasicBlock *getExitingBasicBlock() const;
215 VPBasicBlock *getExitingBasicBlock();
216
217 const VPBlocksTy &getSuccessors() const { return Successors; }
218 VPBlocksTy &getSuccessors() { return Successors; }
219
220 /// Returns true if this block has any successors.
221 bool hasSuccessors() const { return !Successors.empty(); }
222 /// Returns true if this block has any predecessors.
223 bool hasPredecessors() const { return !Predecessors.empty(); }
224
225 iterator_range<VPBlockBase **> successors() { return Successors; }
226 iterator_range<VPBlockBase **> predecessors() { return Predecessors; }
227
228 const VPBlocksTy &getPredecessors() const { return Predecessors; }
229 VPBlocksTy &getPredecessors() { return Predecessors; }
230
231 /// \return the successor of this VPBlockBase if it has a single successor.
232 /// Otherwise return a null pointer.
233 VPBlockBase *getSingleSuccessor() const {
234 return (Successors.size() == 1 ? *Successors.begin() : nullptr);
235 }
236
237 /// \return the predecessor of this VPBlockBase if it has a single
238 /// predecessor. Otherwise return a null pointer.
239 VPBlockBase *getSinglePredecessor() const {
240 return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
241 }
242
243 size_t getNumSuccessors() const { return Successors.size(); }
244 size_t getNumPredecessors() const { return Predecessors.size(); }
245
246 /// An Enclosing Block of a block B is any block containing B, including B
247 /// itself. \return the closest enclosing block starting from "this", which
248 /// has successors. \return the root enclosing block if all enclosing blocks
249 /// have no successors.
250 VPBlockBase *getEnclosingBlockWithSuccessors();
251
252 /// \return the closest enclosing block starting from "this", which has
253 /// predecessors. \return the root enclosing block if all enclosing blocks
254 /// have no predecessors.
255 VPBlockBase *getEnclosingBlockWithPredecessors();
256
257 /// \return the successors either attached directly to this VPBlockBase or, if
258 /// this VPBlockBase is the exit block of a VPRegionBlock and has no
259 /// successors of its own, search recursively for the first enclosing
260 /// VPRegionBlock that has successors and return them. If no such
261 /// VPRegionBlock exists, return the (empty) successors of the topmost
262 /// VPBlockBase reached.
263 const VPBlocksTy &getHierarchicalSuccessors() {
264 return getEnclosingBlockWithSuccessors()->getSuccessors();
265 }
266
267 /// \return the hierarchical predecessor of this VPBlockBase if it has a
268 /// single hierarchical predecessor. Otherwise return a null pointer.
269 VPBlockBase *getSingleHierarchicalPredecessor() {
270 return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
271 }
272
273 /// Set a given VPBlockBase \p Successor as the single successor of this
274 /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
275 /// This VPBlockBase must have no successors.
276 void setOneSuccessor(VPBlockBase *Successor) {
277 assert(Successors.empty() && "Setting one successor when others exist.");
278 assert(Successor->getParent() == getParent() &&
279 "connected blocks must have the same parent");
280 appendSuccessor(Successor);
281 }
282
283 /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
284 /// successors of this VPBlockBase. This VPBlockBase is not added as
285 /// predecessor of \p IfTrue or \p IfFalse. This VPBlockBase must have no
286 /// successors.
287 void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {
288 assert(Successors.empty() && "Setting two successors when others exist.");
289 appendSuccessor(Successor: IfTrue);
290 appendSuccessor(Successor: IfFalse);
291 }
292
293 /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
294 /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
295 /// as successor of any VPBasicBlock in \p NewPreds.
296 void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) {
297 assert(Predecessors.empty() && "Block predecessors already set.");
298 for (auto *Pred : NewPreds)
299 appendPredecessor(Predecessor: Pred);
300 }
301
302 /// Set each VPBasicBlock in \p NewSuccss as successor of this VPBlockBase.
303 /// This VPBlockBase must have no successors. This VPBlockBase is not added
304 /// as predecessor of any VPBasicBlock in \p NewSuccs.
305 void setSuccessors(ArrayRef<VPBlockBase *> NewSuccs) {
306 assert(Successors.empty() && "Block successors already set.");
307 for (auto *Succ : NewSuccs)
308 appendSuccessor(Successor: Succ);
309 }
310
311 /// Remove all the predecessor of this block.
312 void clearPredecessors() { Predecessors.clear(); }
313
314 /// Remove all the successors of this block.
315 void clearSuccessors() { Successors.clear(); }
316
317 /// Swap predecessors of the block. The block must have exactly 2
318 /// predecessors.
319 void swapPredecessors() {
320 assert(Predecessors.size() == 2 && "must have 2 predecessors to swap");
321 std::swap(a&: Predecessors[0], b&: Predecessors[1]);
322 }
323
324 /// Swap successors of the block. The block must have exactly 2 successors.
325 // TODO: This should be part of introducing conditional branch recipes rather
326 // than being independent.
327 void swapSuccessors() {
328 assert(Successors.size() == 2 && "must have 2 successors to swap");
329 std::swap(a&: Successors[0], b&: Successors[1]);
330 }
331
332 /// Returns the index for \p Pred in the blocks predecessors list.
333 unsigned getIndexForPredecessor(const VPBlockBase *Pred) const {
334 assert(count(Predecessors, Pred) == 1 &&
335 "must have Pred exactly once in Predecessors");
336 return std::distance(first: Predecessors.begin(), last: find(Range: Predecessors, Val: Pred));
337 }
338
339 /// Returns the index for \p Succ in the blocks successor list.
340 unsigned getIndexForSuccessor(const VPBlockBase *Succ) const {
341 assert(count(Successors, Succ) == 1 &&
342 "must have Succ exactly once in Successors");
343 return std::distance(first: Successors.begin(), last: find(Range: Successors, Val: Succ));
344 }
345
346 /// Return the unique number of the block.
347 unsigned getNumber() const { return Number; }
348
349 /// Set the unique number of the block, used for dominator tree.
350 void setNumber(unsigned N) { Number = N; }
351
352 /// The method which generates the output IR that correspond to this
353 /// VPBlockBase, thereby "executing" the VPlan.
354 virtual void execute(VPTransformState *State) = 0;
355
356 /// Return the cost of the block.
357 virtual InstructionCost cost(ElementCount VF, VPCostContext &Ctx) = 0;
358
359 void printAsOperand(raw_ostream &OS, bool PrintType = false) const {
360 OS << getName();
361 }
362
363#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
364 /// Print plain-text dump of this VPBlockBase to \p O, prefixing all lines
365 /// with \p Indent. \p SlotTracker is used to print unnamed VPValue's using
366 /// consequtive numbers.
367 ///
368 /// Note that the numbering is applied to the whole VPlan, so printing
369 /// individual blocks is consistent with the whole VPlan printing.
370 virtual void print(raw_ostream &O, const Twine &Indent,
371 VPSlotTracker &SlotTracker) const = 0;
372
373 /// Print plain-text dump of this VPlan to \p O.
374 void print(raw_ostream &O) const;
375
376 /// Print the successors of this block to \p O, prefixing all lines with \p
377 /// Indent.
378 void printSuccessors(raw_ostream &O, const Twine &Indent) const;
379
380 /// Dump this VPBlockBase to dbgs().
381 LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
382#endif
383
384 /// Clone the current block and it's recipes without updating the operands of
385 /// the cloned recipes, including all blocks in the single-entry single-exit
386 /// region for VPRegionBlocks.
387 virtual VPBlockBase *clone() = 0;
388
389protected:
390 VPBlockBase(VPBlockTy SC, const std::string &N) : Name(N), SubclassID(SC) {}
391};
392
393/// VPRecipeBase is a base class modeling a sequence of one or more output IR
394/// instructions. VPRecipeBase owns the VPValues it defines through VPDef
395/// and is responsible for deleting its defined values. Single-value
396/// recipes must inherit from VPSingleDef instead of inheriting from both
397/// VPRecipeBase and VPValue separately.
398class LLVM_ABI_FOR_TEST VPRecipeBase
399 : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock,
400 ilist_parent<VPBasicBlock>>,
401 public VPDef,
402 public VPUser {
403 friend VPBasicBlock;
404 friend class VPBlockUtils;
405
406 /// The debug location for the recipe.
407 DebugLoc DL;
408
409public:
410 /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
411 /// that is actually instantiated. Values of this enumeration are kept in the
412 /// SubclassID field of the VPRecipeBase objects. They are used for concrete
413 /// type identification.
414 using VPRecipeTy = enum : unsigned char {
415 VPBranchOnMaskSC,
416 VPDerivedIVSC,
417 VPExpandSCEVSC,
418 VPExpressionSC,
419 VPIRInstructionSC,
420 VPInstructionSC,
421 VPInterleaveEVLSC,
422 VPInterleaveSC,
423 VPReductionEVLSC,
424 VPReductionSC,
425 VPReplicateSC,
426 VPScalarIVStepsSC,
427 VPVectorPointerSC,
428 VPVectorEndPointerSC,
429 VPWidenCallSC,
430 VPWidenCanonicalIVSC,
431 VPWidenCastSC,
432 VPWidenGEPSC,
433 VPWidenIntrinsicSC,
434 VPWidenMemIntrinsicSC,
435 VPWidenLoadEVLSC,
436 VPWidenLoadSC,
437 VPWidenStoreEVLSC,
438 VPWidenStoreSC,
439 VPWidenSC,
440 VPBlendSC,
441 VPHistogramSC,
442 // START: Phi-like recipes. Need to be kept together.
443 VPWidenPHISC,
444 VPPredInstPHISC,
445 // START: SubclassID for recipes that inherit VPHeaderPHIRecipe.
446 // VPHeaderPHIRecipe need to be kept together.
447 VPCurrentIterationPHISC,
448 VPActiveLaneMaskPHISC,
449 VPFirstOrderRecurrencePHISC,
450 VPWidenIntOrFpInductionSC,
451 VPWidenPointerInductionSC,
452 VPReductionPHISC,
453 VPConditionalInductionPHISC,
454 // END: SubclassID for recipes that inherit VPHeaderPHIRecipe
455 // END: Phi-like recipes
456 VPFirstPHISC = VPWidenPHISC,
457 VPFirstHeaderPHISC = VPCurrentIterationPHISC,
458 VPLastHeaderPHISC = VPConditionalInductionPHISC,
459 VPLastPHISC = VPConditionalInductionPHISC,
460 };
461
462 VPRecipeBase(VPRecipeTy SC, ArrayRef<VPValue *> Operands,
463 DebugLoc DL = DebugLoc::getUnknown())
464 : VPDef(), VPUser(Operands), DL(DL), SubclassID(SC) {}
465
466 ~VPRecipeBase() override = default;
467
468 /// Clone the current recipe.
469 virtual VPRecipeBase *clone() = 0;
470
471 /// The list type holding the recipes of a VPBasicBlock. Each node, including
472 /// the sentinel, stores its parent VPBasicBlock.
473 using RecipeListTy = iplist<VPRecipeBase, ilist_parent<VPBasicBlock>>;
474
475 /// \return the VPRegionBlock which the recipe belongs to.
476 VPRegionBlock *getRegion();
477 const VPRegionBlock *getRegion() const;
478
479 /// The method which generates the output IR instructions that correspond to
480 /// this VPRecipe, thereby "executing" the VPlan.
481 virtual void execute(VPTransformState &State) = 0;
482
483 /// Return the cost of this recipe, taking into account if the cost
484 /// computation should be skipped and the ForceTargetInstructionCost flag.
485 /// Also takes care of printing the cost for debugging.
486 InstructionCost cost(ElementCount VF, VPCostContext &Ctx);
487
488 /// Insert an unlinked recipe into a basic block immediately before
489 /// the specified recipe.
490 void insertBefore(VPRecipeBase *InsertPos);
491 /// Insert an unlinked recipe immediately before the insertion point \p IP.
492 void insertBefore(RecipeListTy::iterator IP);
493
494 /// Insert an unlinked Recipe into a basic block immediately after
495 /// the specified Recipe.
496 void insertAfter(VPRecipeBase *InsertPos);
497
498 /// Unlink this recipe from its current VPBasicBlock and insert it into
499 /// the VPBasicBlock that MovePos lives in, right after MovePos.
500 void moveAfter(VPRecipeBase *MovePos);
501
502 /// Unlink this recipe and insert it before \p I.
503 void moveBefore(RecipeListTy::iterator I);
504
505 /// This method unlinks 'this' from the containing basic block, but does not
506 /// delete it.
507 void removeFromParent();
508
509 /// This method unlinks 'this' from the containing basic block and deletes it.
510 ///
511 /// \returns an iterator pointing to the element after the erased one
512 RecipeListTy::iterator eraseFromParent();
513
514 /// \return an ID for the concrete type of this object.
515 VPRecipeTy getVPRecipeID() const { return SubclassID; }
516
517 /// Method to support type inquiry through isa, cast, and dyn_cast.
518 static inline bool classof(const VPDef *D) {
519 // All VPDefs are also VPRecipeBases.
520 return true;
521 }
522
523 static inline bool classof(const VPUser *U) { return true; }
524
525 /// Returns true if the recipe may have side-effects.
526 bool mayHaveSideEffects() const;
527
528 /// Return true if we can safely execute this recipe unconditionally even if
529 /// it is masked originally.
530 bool isSafeToSpeculativelyExecute() const;
531
532 /// Returns true for PHI-like recipes.
533 bool isPhi() const;
534
535 /// Returns true if the recipe may read from memory.
536 bool mayReadFromMemory() const;
537
538 /// Returns true if the recipe may write to memory.
539 bool mayWriteToMemory() const;
540
541 /// Returns true if the recipe may read from or write to memory.
542 bool mayReadOrWriteMemory() const {
543 return mayReadFromMemory() || mayWriteToMemory();
544 }
545
546 /// Returns the debug location of the recipe.
547 DebugLoc getDebugLoc() const { return DL; }
548
549 /// Set the recipe's debug location to \p NewDL.
550 void setDebugLoc(DebugLoc NewDL) { DL = NewDL; }
551
552#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
553 /// Dump the recipe to stderr (for debugging).
554 void dump() const;
555
556 /// Print the recipe, delegating to printRecipe().
557 void print(raw_ostream &O, const Twine &Indent,
558 VPSlotTracker &SlotTracker) const;
559#endif
560
561private:
562 /// Subclass identifier (for isa/dyn_cast).
563 const VPRecipeTy SubclassID;
564
565protected:
566 /// Compute the cost of this recipe either using a recipe's specialized
567 /// implementation or using the legacy cost model and the underlying
568 /// instructions.
569 virtual InstructionCost computeCost(ElementCount VF,
570 VPCostContext &Ctx) const;
571
572#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
573 /// Each concrete VPRecipe prints itself, without printing common information,
574 /// like debug info or metadata.
575 virtual void printRecipe(raw_ostream &O, const Twine &Indent,
576 VPSlotTracker &SlotTracker) const = 0;
577#endif
578};
579
580// Helper macro to define common classof implementations for recipes.
581#define VP_CLASSOF_IMPL(VPRecipeID) \
582 static inline bool classof(const VPRecipeBase *R) { \
583 return R->getVPRecipeID() == VPRecipeID; \
584 } \
585 static inline bool classof(const VPValue *V) { \
586 auto *R = V->getDefiningRecipe(); \
587 return R && R->getVPRecipeID() == VPRecipeID; \
588 } \
589 static inline bool classof(const VPUser *U) { \
590 auto *R = dyn_cast<VPRecipeBase>(U); \
591 return R && R->getVPRecipeID() == VPRecipeID; \
592 } \
593 static inline bool classof(const VPSingleDefRecipe *R) { \
594 return R->getVPRecipeID() == VPRecipeID; \
595 }
596
597/// Compute the scalar result type for an IR \p Opcode given \p Operands.
598LLVM_ABI Type *computeScalarTypeForInstruction(unsigned Opcode,
599 ArrayRef<VPValue *> Operands);
600
601/// VPSingleDefRecipe is a base class for recipes that model a sequence of one
602/// or more output IR that define a single result VPValue. Note that
603/// VPSingleDefRecipe must inherit from VPRecipeBase before VPSingleDefValue.
604class LLVM_ABI_FOR_TEST VPSingleDefRecipe : public VPRecipeBase,
605 public VPSingleDefValue {
606public:
607 VPSingleDefRecipe(VPRecipeTy SC, ArrayRef<VPValue *> Operands, Type *ResultTy,
608 Value *UV = nullptr, DebugLoc DL = DebugLoc::getUnknown())
609 : VPRecipeBase(SC, Operands, DL), VPSingleDefValue(this, UV, ResultTy) {}
610
611 static inline bool classof(const VPRecipeBase *R) {
612 switch (R->getVPRecipeID()) {
613 case VPRecipeBase::VPDerivedIVSC:
614 case VPRecipeBase::VPExpandSCEVSC:
615 case VPRecipeBase::VPExpressionSC:
616 case VPRecipeBase::VPInstructionSC:
617 case VPRecipeBase::VPReductionEVLSC:
618 case VPRecipeBase::VPReductionSC:
619 case VPRecipeBase::VPReplicateSC:
620 case VPRecipeBase::VPScalarIVStepsSC:
621 case VPRecipeBase::VPVectorPointerSC:
622 case VPRecipeBase::VPVectorEndPointerSC:
623 case VPRecipeBase::VPWidenCallSC:
624 case VPRecipeBase::VPWidenCanonicalIVSC:
625 case VPRecipeBase::VPWidenCastSC:
626 case VPRecipeBase::VPWidenGEPSC:
627 case VPRecipeBase::VPWidenIntrinsicSC:
628 case VPRecipeBase::VPWidenMemIntrinsicSC:
629 case VPRecipeBase::VPWidenSC:
630 case VPRecipeBase::VPBlendSC:
631 case VPRecipeBase::VPPredInstPHISC:
632 case VPRecipeBase::VPCurrentIterationPHISC:
633 case VPRecipeBase::VPActiveLaneMaskPHISC:
634 case VPRecipeBase::VPFirstOrderRecurrencePHISC:
635 case VPRecipeBase::VPWidenPHISC:
636 case VPRecipeBase::VPWidenIntOrFpInductionSC:
637 case VPRecipeBase::VPWidenPointerInductionSC:
638 case VPRecipeBase::VPReductionPHISC:
639 case VPRecipeBase::VPWidenLoadEVLSC:
640 case VPRecipeBase::VPWidenLoadSC:
641 case VPRecipeBase::VPConditionalInductionPHISC:
642 return true;
643 case VPRecipeBase::VPBranchOnMaskSC:
644 case VPRecipeBase::VPInterleaveEVLSC:
645 case VPRecipeBase::VPInterleaveSC:
646 case VPRecipeBase::VPIRInstructionSC:
647 case VPRecipeBase::VPWidenStoreEVLSC:
648 case VPRecipeBase::VPWidenStoreSC:
649 case VPRecipeBase::VPHistogramSC:
650 return false;
651 }
652 llvm_unreachable("Unhandled VPRecipeID");
653 }
654
655 static inline bool classof(const VPValue *V) {
656 auto *R = V->getDefiningRecipe();
657 return R && classof(R);
658 }
659
660 static inline bool classof(const VPUser *U) {
661 auto *R = dyn_cast<VPRecipeBase>(Val: U);
662 return R && classof(R);
663 }
664
665 VPSingleDefRecipe *clone() override = 0;
666
667 /// Returns the underlying instruction.
668 Instruction *getUnderlyingInstr() {
669 return cast<Instruction>(Val: getUnderlyingValue());
670 }
671 const Instruction *getUnderlyingInstr() const {
672 return cast<Instruction>(Val: getUnderlyingValue());
673 }
674
675#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
676 /// Print this VPSingleDefRecipe to dbgs() (for debugging).
677 LLVM_DUMP_METHOD void dump() const;
678#endif
679};
680
681/// Class to record and manage LLVM IR flags.
682LLVM_PACKED_START
683class VPIRFlags {
684 enum class OperationType : unsigned char {
685 Cmp,
686 FCmp,
687 OverflowingBinOp,
688 Trunc,
689 DisjointOp,
690 PossiblyExactOp,
691 GEPOp,
692 FPMathOp,
693 NonNegOp,
694 ReductionOp,
695 Other
696 };
697
698public:
699 struct WrapFlagsTy {
700 char HasNUW : 1;
701 char HasNSW : 1;
702
703 WrapFlagsTy(bool HasNUW, bool HasNSW) : HasNUW(HasNUW), HasNSW(HasNSW) {}
704 WrapFlagsTy() : HasNUW(false), HasNSW(false) {}
705 WrapFlagsTy withoutNoSignedWrap() {
706 return {static_cast<bool>(HasNUW), false};
707 }
708 };
709
710 struct TruncFlagsTy {
711 char HasNUW : 1;
712 char HasNSW : 1;
713
714 TruncFlagsTy(bool HasNUW, bool HasNSW) : HasNUW(HasNUW), HasNSW(HasNSW) {}
715 };
716
717 struct DisjointFlagsTy {
718 char IsDisjoint : 1;
719 DisjointFlagsTy(bool IsDisjoint) : IsDisjoint(IsDisjoint) {}
720 };
721
722 struct NonNegFlagsTy {
723 char NonNeg : 1;
724 NonNegFlagsTy(bool IsNonNeg) : NonNeg(IsNonNeg) {}
725 };
726
727private:
728 struct ExactFlagsTy {
729 char IsExact : 1;
730 ExactFlagsTy(bool Exact) : IsExact(Exact) {}
731 };
732 struct FastMathFlagsTy {
733 char AllowReassoc : 1;
734 char NoNaNs : 1;
735 char NoInfs : 1;
736 char NoSignedZeros : 1;
737 char AllowReciprocal : 1;
738 char AllowContract : 1;
739 char ApproxFunc : 1;
740
741 LLVM_ABI_FOR_TEST FastMathFlagsTy(const FastMathFlags &FMF);
742 };
743 /// Holds both the predicate and fast-math flags for floating-point
744 /// comparisons.
745 struct FCmpFlagsTy {
746 uint8_t CmpPredStorage;
747 FastMathFlagsTy FMFs;
748 };
749 /// Holds reduction-specific flags: RecurKind, IsOrdered, IsInLoop, and FMFs.
750 struct ReductionFlagsTy {
751 // RecurKind has ~26 values, needs 5 bits but uses 6 bits to account for
752 // additional kinds.
753 unsigned char Kind : 6;
754 // TODO: Derive order/in-loop from plan and remove here.
755 unsigned char IsOrdered : 1;
756 unsigned char IsInLoop : 1;
757 FastMathFlagsTy FMFs;
758
759 ReductionFlagsTy(RecurKind Kind, bool IsOrdered, bool IsInLoop,
760 FastMathFlags FMFs)
761 : Kind(static_cast<unsigned char>(Kind)), IsOrdered(IsOrdered),
762 IsInLoop(IsInLoop), FMFs(FMFs) {}
763 };
764
765 OperationType OpType;
766
767 union {
768 uint8_t CmpPredStorage;
769 WrapFlagsTy WrapFlags;
770 TruncFlagsTy TruncFlags;
771 DisjointFlagsTy DisjointFlags;
772 ExactFlagsTy ExactFlags;
773 uint8_t GEPFlagsStorage;
774 NonNegFlagsTy NonNegFlags;
775 FastMathFlagsTy FMFs;
776 FCmpFlagsTy FCmpFlags;
777 ReductionFlagsTy ReductionFlags;
778 uint8_t AllFlags[2];
779 };
780
781public:
782 VPIRFlags() : OpType(OperationType::Other), AllFlags() {}
783
784 VPIRFlags(Instruction &I) : VPIRFlags() {
785 if (auto *FCmp = dyn_cast<FCmpInst>(Val: &I)) {
786 OpType = OperationType::FCmp;
787 Bitfield::set<CmpInst::PredicateField>(Packed&: FCmpFlags.CmpPredStorage,
788 Value: FCmp->getPredicate());
789 assert(getPredicate() == FCmp->getPredicate() && "predicate truncated");
790 FCmpFlags.FMFs = FCmp->getFastMathFlags();
791 } else if (auto *Op = dyn_cast<CmpInst>(Val: &I)) {
792 OpType = OperationType::Cmp;
793 Bitfield::set<CmpInst::PredicateField>(Packed&: CmpPredStorage,
794 Value: Op->getPredicate());
795 assert(getPredicate() == Op->getPredicate() && "predicate truncated");
796 } else if (auto *Op = dyn_cast<PossiblyDisjointInst>(Val: &I)) {
797 OpType = OperationType::DisjointOp;
798 DisjointFlags.IsDisjoint = Op->isDisjoint();
799 } else if (auto *Op = dyn_cast<OverflowingBinaryOperator>(Val: &I)) {
800 OpType = OperationType::OverflowingBinOp;
801 WrapFlags = {Op->hasNoUnsignedWrap(), Op->hasNoSignedWrap()};
802 } else if (auto *Op = dyn_cast<TruncInst>(Val: &I)) {
803 OpType = OperationType::Trunc;
804 TruncFlags = {Op->hasNoUnsignedWrap(), Op->hasNoSignedWrap()};
805 } else if (auto *Op = dyn_cast<PossiblyExactOperator>(Val: &I)) {
806 OpType = OperationType::PossiblyExactOp;
807 ExactFlags.IsExact = Op->isExact();
808 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: &I)) {
809 OpType = OperationType::GEPOp;
810 GEPFlagsStorage = GEP->getNoWrapFlags().getRaw();
811 assert(getGEPNoWrapFlags() == GEP->getNoWrapFlags() &&
812 "wrap flags truncated");
813 } else if (auto *PNNI = dyn_cast<PossiblyNonNegInst>(Val: &I)) {
814 OpType = OperationType::NonNegOp;
815 NonNegFlags.NonNeg = PNNI->hasNonNeg();
816 } else if (auto *Op = dyn_cast<FPMathOperator>(Val: &I)) {
817 OpType = OperationType::FPMathOp;
818 FMFs = Op->getFastMathFlags();
819 }
820 }
821
822 VPIRFlags(CmpInst::Predicate Pred) : OpType(OperationType::Cmp), AllFlags() {
823 Bitfield::set<CmpInst::PredicateField>(Packed&: CmpPredStorage, Value: Pred);
824 assert(getPredicate() == Pred && "predicate truncated");
825 }
826
827 VPIRFlags(CmpInst::Predicate Pred, FastMathFlags FMFs)
828 : OpType(OperationType::FCmp), AllFlags() {
829 Bitfield::set<CmpInst::PredicateField>(Packed&: FCmpFlags.CmpPredStorage, Value: Pred);
830 assert(getPredicate() == Pred && "predicate truncated");
831 FCmpFlags.FMFs = FMFs;
832 }
833
834 VPIRFlags(WrapFlagsTy WrapFlags)
835 : OpType(OperationType::OverflowingBinOp), AllFlags() {
836 this->WrapFlags = WrapFlags;
837 }
838
839 VPIRFlags(TruncFlagsTy TruncFlags)
840 : OpType(OperationType::Trunc), AllFlags() {
841 this->TruncFlags = TruncFlags;
842 }
843
844 VPIRFlags(FastMathFlags FMFs) : OpType(OperationType::FPMathOp), AllFlags() {
845 this->FMFs = FMFs;
846 }
847
848 VPIRFlags(DisjointFlagsTy DisjointFlags)
849 : OpType(OperationType::DisjointOp), AllFlags() {
850 this->DisjointFlags = DisjointFlags;
851 }
852
853 VPIRFlags(NonNegFlagsTy NonNegFlags)
854 : OpType(OperationType::NonNegOp), AllFlags() {
855 this->NonNegFlags = NonNegFlags;
856 }
857
858 VPIRFlags(ExactFlagsTy ExactFlags)
859 : OpType(OperationType::PossiblyExactOp), AllFlags() {
860 this->ExactFlags = ExactFlags;
861 }
862
863 VPIRFlags(GEPNoWrapFlags GEPFlags)
864 : OpType(OperationType::GEPOp), AllFlags() {
865 GEPFlagsStorage = GEPFlags.getRaw();
866 }
867
868 VPIRFlags(RecurKind Kind, bool IsOrdered, bool IsInLoop, FastMathFlags FMFs)
869 : OpType(OperationType::ReductionOp), AllFlags() {
870 ReductionFlags = ReductionFlagsTy(Kind, IsOrdered, IsInLoop, FMFs);
871 }
872
873 /// Only keep flags also present in \p Other. \p Other must have the same
874 /// OpType as the current object.
875 void intersectFlags(const VPIRFlags &Other);
876
877 /// Drop all poison-generating flags.
878 void dropPoisonGeneratingFlags() {
879 // NOTE: This needs to be kept in-sync with
880 // Instruction::dropPoisonGeneratingFlags.
881 switch (OpType) {
882 case OperationType::OverflowingBinOp:
883 WrapFlags.HasNUW = false;
884 WrapFlags.HasNSW = false;
885 break;
886 case OperationType::Trunc:
887 TruncFlags.HasNUW = false;
888 TruncFlags.HasNSW = false;
889 break;
890 case OperationType::DisjointOp:
891 DisjointFlags.IsDisjoint = false;
892 break;
893 case OperationType::PossiblyExactOp:
894 ExactFlags.IsExact = false;
895 break;
896 case OperationType::GEPOp:
897 GEPFlagsStorage = 0;
898 break;
899 case OperationType::FPMathOp:
900 case OperationType::FCmp:
901 case OperationType::ReductionOp:
902 getFMFsRef().NoNaNs = false;
903 getFMFsRef().NoInfs = false;
904 break;
905 case OperationType::NonNegOp:
906 NonNegFlags.NonNeg = false;
907 break;
908 case OperationType::Cmp:
909 case OperationType::Other:
910 break;
911 }
912 }
913
914 /// Apply the IR flags to \p I.
915 void applyFlags(Instruction &I) const {
916 switch (OpType) {
917 case OperationType::OverflowingBinOp:
918 I.setHasNoUnsignedWrap(WrapFlags.HasNUW);
919 I.setHasNoSignedWrap(WrapFlags.HasNSW);
920 break;
921 case OperationType::Trunc:
922 I.setHasNoUnsignedWrap(TruncFlags.HasNUW);
923 I.setHasNoSignedWrap(TruncFlags.HasNSW);
924 break;
925 case OperationType::DisjointOp:
926 cast<PossiblyDisjointInst>(Val: &I)->setIsDisjoint(DisjointFlags.IsDisjoint);
927 break;
928 case OperationType::PossiblyExactOp:
929 I.setIsExact(ExactFlags.IsExact);
930 break;
931 case OperationType::GEPOp:
932 cast<GetElementPtrInst>(Val: &I)->setNoWrapFlags(
933 GEPNoWrapFlags::fromRaw(Flags: GEPFlagsStorage));
934 break;
935 case OperationType::FPMathOp:
936 case OperationType::FCmp:
937 I.copyFastMathFlags(FMF: getFastMathFlagsOrNone());
938 break;
939 case OperationType::NonNegOp:
940 I.setNonNeg(NonNegFlags.NonNeg);
941 break;
942 case OperationType::ReductionOp:
943 llvm_unreachable("reduction ops should not use applyFlags");
944 case OperationType::Cmp:
945 case OperationType::Other:
946 break;
947 }
948 }
949
950 CmpInst::Predicate getPredicate() const {
951 assert((OpType == OperationType::Cmp || OpType == OperationType::FCmp) &&
952 "recipe doesn't have a compare predicate");
953 uint8_t Storage = OpType == OperationType::FCmp ? FCmpFlags.CmpPredStorage
954 : CmpPredStorage;
955 return Bitfield::get<CmpInst::PredicateField>(Packed: Storage);
956 }
957
958 void setPredicate(CmpInst::Predicate Pred) {
959 assert((OpType == OperationType::Cmp || OpType == OperationType::FCmp) &&
960 "recipe doesn't have a compare predicate");
961 if (OpType == OperationType::FCmp)
962 Bitfield::set<CmpInst::PredicateField>(Packed&: FCmpFlags.CmpPredStorage, Value: Pred);
963 else
964 Bitfield::set<CmpInst::PredicateField>(Packed&: CmpPredStorage, Value: Pred);
965 assert(getPredicate() == Pred && "predicate truncated");
966 }
967
968 GEPNoWrapFlags getGEPNoWrapFlags() const {
969 return GEPNoWrapFlags::fromRaw(Flags: GEPFlagsStorage);
970 }
971
972 /// Returns true if the recipe has a comparison predicate.
973 bool hasPredicate() const {
974 return OpType == OperationType::Cmp || OpType == OperationType::FCmp;
975 }
976
977 /// Returns true if the recipe has fast-math flags.
978 bool hasFastMathFlags() const {
979 return OpType == OperationType::FPMathOp || OpType == OperationType::FCmp ||
980 OpType == OperationType::ReductionOp;
981 }
982
983 LLVM_ABI_FOR_TEST FastMathFlags getFastMathFlagsOrNone() const;
984
985 bool hasNoUnsignedWrap() const {
986 switch (OpType) {
987 case OperationType::OverflowingBinOp:
988 return WrapFlags.HasNUW;
989 case OperationType::Trunc:
990 return TruncFlags.HasNUW;
991 default:
992 llvm_unreachable("recipe doesn't have a NUW flag");
993 }
994 }
995
996 bool hasNoSignedWrap() const {
997 switch (OpType) {
998 case OperationType::OverflowingBinOp:
999 return WrapFlags.HasNSW;
1000 case OperationType::Trunc:
1001 return TruncFlags.HasNSW;
1002 default:
1003 llvm_unreachable("recipe doesn't have a NSW flag");
1004 }
1005 }
1006
1007 WrapFlagsTy getNoWrapFlagsOrNone() const {
1008 switch (OpType) {
1009 case OperationType::OverflowingBinOp:
1010 case OperationType::Trunc:
1011 return {hasNoUnsignedWrap(), hasNoSignedWrap()};
1012 default:
1013 return {};
1014 }
1015 }
1016
1017 WrapFlagsTy getNoWrapFlags() const {
1018 return {hasNoUnsignedWrap(), hasNoSignedWrap()};
1019 }
1020
1021 bool isDisjoint() const {
1022 assert(OpType == OperationType::DisjointOp &&
1023 "recipe cannot have a disjoing flag");
1024 return DisjointFlags.IsDisjoint;
1025 }
1026
1027 RecurKind getRecurKind() const {
1028 assert(OpType == OperationType::ReductionOp &&
1029 "recipe doesn't have reduction flags");
1030 return static_cast<RecurKind>(ReductionFlags.Kind);
1031 }
1032
1033 bool isReductionOrdered() const {
1034 assert(OpType == OperationType::ReductionOp &&
1035 "recipe doesn't have reduction flags");
1036 return ReductionFlags.IsOrdered;
1037 }
1038
1039 bool isReductionInLoop() const {
1040 assert(OpType == OperationType::ReductionOp &&
1041 "recipe doesn't have reduction flags");
1042 return ReductionFlags.IsInLoop;
1043 }
1044
1045private:
1046 /// Get a reference to the fast-math flags for FPMathOp, FCmp or ReductionOp.
1047 FastMathFlagsTy &getFMFsRef() {
1048 if (OpType == OperationType::FCmp)
1049 return FCmpFlags.FMFs;
1050 if (OpType == OperationType::ReductionOp)
1051 return ReductionFlags.FMFs;
1052 return FMFs;
1053 }
1054 const FastMathFlagsTy &getFMFsRef() const {
1055 if (OpType == OperationType::FCmp)
1056 return FCmpFlags.FMFs;
1057 if (OpType == OperationType::ReductionOp)
1058 return ReductionFlags.FMFs;
1059 return FMFs;
1060 }
1061
1062public:
1063 /// Returns default flags for \p Opcode and scalar \p ResultTy for opcodes
1064 /// that support it, asserts otherwise. Opcodes not supporting default flags
1065 /// include compares and ComputeReductionResult.
1066 LLVM_ABI_FOR_TEST static VPIRFlags getDefaultFlags(unsigned Opcode,
1067 Type *ResultTy = nullptr);
1068
1069#if !defined(NDEBUG)
1070 /// Returns true if the set flags are valid for \p Opcode.
1071 LLVM_ABI_FOR_TEST bool flagsValidForOpcode(unsigned Opcode) const;
1072
1073 /// Returns true if \p Opcode with scalar result type \p ResultTy has its
1074 /// required flags set.
1075 LLVM_ABI_FOR_TEST bool hasRequiredFlagsForOpcode(unsigned Opcode,
1076 Type *ResultTy) const;
1077#endif
1078
1079#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1080 void printFlags(raw_ostream &O) const;
1081#endif
1082};
1083LLVM_PACKED_END
1084
1085static_assert(sizeof(VPIRFlags) <= 3, "VPIRFlags should not grow");
1086
1087/// A pure-virtual common base class for recipes defining a single VPValue and
1088/// using IR flags.
1089struct VPRecipeWithIRFlags : public VPSingleDefRecipe, public VPIRFlags {
1090 VPRecipeWithIRFlags(VPRecipeTy SC, ArrayRef<VPValue *> Operands,
1091 Type *ResultTy, const VPIRFlags &Flags,
1092 DebugLoc DL = DebugLoc::getUnknown())
1093 : VPSingleDefRecipe(SC, Operands, ResultTy, /*UV=*/nullptr, DL),
1094 VPIRFlags(Flags) {}
1095
1096 static inline bool classof(const VPRecipeBase *R) {
1097 return R->getVPRecipeID() == VPRecipeBase::VPBlendSC ||
1098 R->getVPRecipeID() == VPRecipeBase::VPInstructionSC ||
1099 R->getVPRecipeID() == VPRecipeBase::VPWidenSC ||
1100 R->getVPRecipeID() == VPRecipeBase::VPWidenGEPSC ||
1101 R->getVPRecipeID() == VPRecipeBase::VPWidenCallSC ||
1102 R->getVPRecipeID() == VPRecipeBase::VPWidenCastSC ||
1103 R->getVPRecipeID() == VPRecipeBase::VPWidenIntrinsicSC ||
1104 R->getVPRecipeID() == VPRecipeBase::VPWidenMemIntrinsicSC ||
1105 R->getVPRecipeID() == VPRecipeBase::VPReductionSC ||
1106 R->getVPRecipeID() == VPRecipeBase::VPReductionEVLSC ||
1107 R->getVPRecipeID() == VPRecipeBase::VPReplicateSC ||
1108 R->getVPRecipeID() == VPRecipeBase::VPVectorEndPointerSC ||
1109 R->getVPRecipeID() == VPRecipeBase::VPVectorPointerSC ||
1110 R->getVPRecipeID() == VPRecipeBase::VPWidenCanonicalIVSC ||
1111 R->getVPRecipeID() == VPRecipeBase::VPDerivedIVSC;
1112 }
1113
1114 static inline bool classof(const VPUser *U) {
1115 auto *R = dyn_cast<VPRecipeBase>(Val: U);
1116 return R && classof(R);
1117 }
1118
1119 static inline bool classof(const VPValue *V) {
1120 auto *R = V->getDefiningRecipe();
1121 return R && classof(R);
1122 }
1123
1124 VPRecipeWithIRFlags *clone() override = 0;
1125
1126 static inline bool classof(const VPSingleDefRecipe *R) {
1127 return classof(R: static_cast<const VPRecipeBase *>(R));
1128 }
1129
1130 void execute(VPTransformState &State) override = 0;
1131
1132 /// Compute the cost for this recipe for \p VF, using \p Opcode and \p Ctx.
1133 InstructionCost getCostForRecipeWithOpcode(unsigned Opcode, ElementCount VF,
1134 VPCostContext &Ctx) const;
1135};
1136
1137/// The frequency with which a recipe executes, relative to the entry of the
1138/// loop region. IsEstimated is set if any branch weight it was composed from
1139/// was estimated from static heuristics.
1140struct VPExecutionFrequency {
1141 const BlockFrequency Freq;
1142 const bool IsEstimated;
1143
1144 VPExecutionFrequency(BlockFrequency Freq, bool IsEstimated)
1145 : Freq(Freq), IsEstimated(IsEstimated) {
1146 assert(Freq > BlockFrequency() && "execution frequency must be non-zero");
1147 }
1148};
1149
1150/// Helper to manage IR metadata for recipes. It filters out metadata that
1151/// cannot be propagated.
1152class LLVM_ABI_FOR_TEST VPIRMetadata {
1153 SmallVector<std::pair<unsigned, MDNode *>> Metadata;
1154
1155 /// Name of the VPlan-internal metadata kind holding the execution frequency.
1156 static constexpr StringLiteral ExecutionFrequencyMDName =
1157 "vplan.execution.frequency";
1158
1159 /// Name of the VPlan-internal metadata kind holding estimated branch weights.
1160 static constexpr StringLiteral EstimatedProfileMDName =
1161 "vplan.prof.estimated";
1162
1163 /// Returns the ID of the metadata kind named \p Kind, taking the context from
1164 /// any attached node; all belong to the context of the VPlan's function.
1165 unsigned getMDKindID(StringRef Kind) const {
1166 assert(!Metadata.empty() && "no node to take the context from");
1167 return Metadata.front().second->getContext().getMDKindID(Name: Kind);
1168 }
1169
1170 /// Returns the node attached under the VPlan-internal metadata kind named
1171 /// \p Kind, or nullptr if there is none.
1172 MDNode *getInternalMetadata(StringRef Kind) const {
1173 return Metadata.empty() ? nullptr : getMetadata(Kind: getMDKindID(Kind));
1174 }
1175
1176public:
1177 VPIRMetadata() = default;
1178
1179 /// Adds metatadata that can be preserved from the original instruction
1180 /// \p I.
1181 VPIRMetadata(Instruction &I) {
1182 getMetadataToPropagate(Inst: &I, Metadata);
1183 // Retain the branch weights of terminators. They are used to compute the
1184 // frequencies with which the blocks of the original loop execute. Also
1185 // retain !prof on selects.
1186 if (I.isTerminator() || isa<SelectInst>(Val: &I))
1187 if (MDNode *BW = I.getMetadata(KindID: LLVMContext::MD_prof))
1188 Metadata.emplace_back(Args: LLVMContext::MD_prof, Args&: BW);
1189 }
1190
1191 /// Copy constructor for cloning.
1192 VPIRMetadata(const VPIRMetadata &Other) = default;
1193
1194 VPIRMetadata &operator=(const VPIRMetadata &Other) = default;
1195
1196 /// Add all metadata to \p I.
1197 void applyMetadata(Instruction &I) const;
1198
1199 /// Set metadata with kind \p Kind to \p Node. If metadata with \p Kind
1200 /// already exists, it will be replaced. Otherwise, it will be added.
1201 void setMetadata(unsigned Kind, MDNode *Node) {
1202 auto It =
1203 llvm::find_if(Range&: Metadata, P: [Kind](const std::pair<unsigned, MDNode *> &P) {
1204 return P.first == Kind;
1205 });
1206 if (It != Metadata.end())
1207 It->second = Node;
1208 else
1209 Metadata.emplace_back(Args&: Kind, Args&: Node);
1210 }
1211
1212 /// Remove the metadata of kind \p Kind, if present.
1213 void eraseMetadata(unsigned Kind) {
1214 erase_if(C&: Metadata, P: [Kind](const auto &P) { return P.first == Kind; });
1215 }
1216
1217 /// Intersect this VPIRMetadata object with \p MD, keeping only metadata
1218 /// nodes that are common to both.
1219 void intersect(const VPIRMetadata &MD);
1220
1221 /// Get metadata of kind \p Kind. Returns nullptr if not found.
1222 MDNode *getMetadata(unsigned Kind) const {
1223 auto It =
1224 find_if(Range: Metadata, P: [Kind](const auto &P) { return P.first == Kind; });
1225 return It != Metadata.end() ? It->second : nullptr;
1226 }
1227
1228 /// Record that the recipe executes with frequency \p Freq, relative to the
1229 /// entry of the loop region.
1230 void setExecutionFrequency(std::optional<VPExecutionFrequency> Freq,
1231 LLVMContext &Ctx);
1232
1233 /// Returns the frequency recorded by setExecutionFrequency, if any.
1234 std::optional<VPExecutionFrequency> getExecutionFrequency() const;
1235
1236 /// Drop the frequency recorded by setExecutionFrequency, if any.
1237 void clearExecutionFrequency();
1238
1239 /// Returns the branch weights recorded for this terminator, preferring real
1240 /// profile data over an estimate, or nullptr if there are none.
1241 MDNode *getBranchWeights() const {
1242 MDNode *Node = getMetadata(Kind: LLVMContext::MD_prof);
1243 return Node ? Node : getInternalMetadata(Kind: EstimatedProfileMDName);
1244 }
1245
1246 /// Returns true if the weights returned by getBranchWeights are estimated.
1247 bool hasEstimatedBranchWeights() const {
1248 return getInternalMetadata(Kind: EstimatedProfileMDName);
1249 }
1250
1251 /// Set estimated branch weights to \p Node.
1252 void setEstimatedBranchWeights(MDNode *Node) {
1253 assert(!getMetadata(LLVMContext::MD_prof) &&
1254 "real profile data takes precedence over an estimate");
1255 setMetadata(Kind: Node->getContext().getMDKindID(Name: EstimatedProfileMDName), Node);
1256 }
1257
1258#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1259 /// Print metadata with node IDs.
1260 void print(raw_ostream &O, VPSlotTracker &SlotTracker) const;
1261#endif
1262};
1263
1264class VPInstruction;
1265
1266/// Manage IR attributes for call recipes. Call VPInstructions store all
1267/// call-site attributes. Widened calls only store return and per-argument
1268/// attributes that are valid to propagate to the widened call.
1269class VPIRAttributes {
1270 AttributeList CallAttrs;
1271
1272public:
1273 VPIRAttributes() = default;
1274
1275 explicit VPIRAttributes(AttributeList CallAttrs) : CallAttrs(CallAttrs) {}
1276
1277 /// Stores the return and per-arg attributes of the call VPInstruction \p
1278 /// Call that are valid for a widened call with type \p WideTy. If \p Call is
1279 /// masked, the scalar call only executes for some lanes, so argument
1280 /// attributes are only kept for widened arguments passed to a masked variant.
1281 VPIRAttributes(const VPInstruction &Call, FunctionType *WideTy);
1282
1283 /// Keep only the attributes valid for both this and \p Other.
1284 void intersectAttrs(const VPIRAttributes &Other, LLVMContext &Ctx);
1285
1286 /// Apply the stored attributes to the widened call \p WideCall.
1287 void applyAttrs(CallInst &WideCall) const {
1288 WideCall.setAttributes(CallAttrs);
1289 }
1290
1291 /// Returns the memory effects of a call with these attributes to a callee
1292 /// with function attributes \p CalleeFnAttrs.
1293 MemoryEffects getMemoryEffects(AttributeSet CalleeFnAttrs) const {
1294 return CallAttrs.getMemoryEffects() & CalleeFnAttrs.getMemoryEffects();
1295 }
1296
1297 /// Returns true if the call site or \p CalleeFnAttrs has \p Kind.
1298 bool hasFnAttr(Attribute::AttrKind Kind, AttributeSet CalleeFnAttrs) const {
1299 return CallAttrs.hasFnAttr(Kind) || CalleeFnAttrs.hasAttribute(Kind);
1300 }
1301
1302#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1303 /// Print return-value attributes carried with this object.
1304 void printRetAttrs(raw_ostream &O) const;
1305
1306 /// Print per-arg attributes for argument \p ArgIdx.
1307 void printParamAttrs(raw_ostream &O, unsigned ArgIdx) const;
1308
1309 /// Print function attributes carried with this object.
1310 void printFnAttrs(raw_ostream &O) const;
1311#endif
1312};
1313
1314/// This is a concrete Recipe that models a single VPlan-level instruction.
1315/// While as any Recipe it may generate a sequence of IR instructions when
1316/// executed, these instructions would always form a single-def expression as
1317/// the VPInstruction is also a single def-use vertex. Most VPInstruction
1318/// opcodes can take an optional mask. Masks may be assigned during
1319/// predication.
1320class LLVM_ABI_FOR_TEST VPInstruction : public VPRecipeWithIRFlags,
1321 public VPIRMetadata,
1322 public VPIRAttributes {
1323public:
1324 /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
1325 enum {
1326 FirstOrderRecurrenceSplice = Instruction::OtherOpsEnd +
1327 1, // Combines the incoming and previous
1328 // values of a first-order recurrence.
1329 Not,
1330 // Creates a mask where each lane is active (true) whilst the current
1331 // counter (first operand + index) is less than the second operand. i.e.
1332 // mask[i] = icmpt ult (op0 + i), op1
1333 // ActiveLaneMask is used for early-exit loops with stores, plus tail
1334 // folding for all styles except DataAndControlFlow. The size of the
1335 // mask returned is VF. When unrolled, ActiveLaneMask is duplicated.
1336 ActiveLaneMask,
1337 // As above, but takes an additional operand (Multiplier). The size of
1338 // the mask returned is VF * Multiplier (UF, op2).
1339 // WideActiveLaneMask is used for control flow and is unrolled by widening,
1340 // with one extract vector created per unroll part.
1341 WideActiveLaneMask,
1342 // Signature: Vectors... -> WideVector
1343 // Concatenates all vector operands to a single wide vector.
1344 ConcatVectors,
1345 // Signature: (Multiplier, Address, Align) -> Vector
1346 // Loads a single wide vector of `Multiplier * VF` elements.
1347 WideVectorLoad,
1348 // Signature: (Multiplier, Address, Alignment, Vector)
1349 // Stores a single wide vector of `Multiplier * VF` elements.
1350 WideVectorStore,
1351 // Extracts each unrolled part of a (VF * UF) widened vector/mask.
1352 ExtractVectorForPart,
1353 ExplicitVectorLength,
1354 // Represents the incoming loop-invariant alias-mask. All memory accesses
1355 // in the loop must stay within the active lanes.
1356 IncomingAliasMask,
1357 // Increment the canonical IV separately for each unrolled part.
1358 CanonicalIVIncrementForPart,
1359 // Abstract instruction that compares two values and branches. This is
1360 // lowered to ICmp + BranchOnCond during VPlan to VPlan transformation.
1361 BranchOnCount,
1362 BranchOnCond,
1363 // Branch with 2 boolean condition operands and 3 successors. If condition
1364 // 0 is true, branches to successor 0; if condition 1 is true, branches to
1365 // successor 1; otherwise branches to successor 2. Expanded after region
1366 // dissolution into: (1) an OR of the two conditions branching to
1367 // middle.split or successor 2, and (2) middle.split branching to successor
1368 // 0 or successor 1 based on condition 0.
1369 BranchOnTwoConds,
1370 Broadcast,
1371 /// Creates a fixed-width vector containing all operands. The number of
1372 /// operands matches the vector element count.
1373 BuildVector,
1374 /// Extracts all lanes from its (non-scalable) vector operand. This is an
1375 /// abstract VPInstruction whose single defined VPValue represents VF
1376 /// scalars extracted from a vector, to be replaced by VF ExtractElement
1377 /// VPInstructions.
1378 Unpack,
1379 /// Reduce the operands to the final reduction result using the operation
1380 /// specified via the operation's VPIRFlags.
1381 ComputeReductionResult,
1382 // Extracts the last part of its operand. Removed during unrolling.
1383 ExtractLastPart,
1384 // Extracts the last lane of its vector operand, per part.
1385 ExtractLastLane,
1386 // Extracts the second-to-last lane from its operand or the second-to-last
1387 // part if it is scalar. In the latter case, the recipe will be removed
1388 // during unrolling.
1389 ExtractPenultimateElement,
1390 LogicalAnd, // Non-poison propagating logical And.
1391 LogicalOr, // Non-poison propagating logical Or.
1392 NumActiveLanes, // Counts the number of active lanes in a mask.
1393 // Add an offset in bytes (second operand) to a base pointer (first
1394 // operand). Only generates scalar values (either for the first lane only or
1395 // for all lanes, depending on its uses).
1396 PtrAdd,
1397 // Add a vector offset in bytes (second operand) to a scalar base pointer
1398 // (first operand).
1399 WidePtrAdd,
1400 // Returns a scalar boolean value, which is true if any lane of its
1401 // (boolean) vector operands is true. It produces the reduced value across
1402 // all unrolled iterations. Unrolling will add all copies of its original
1403 // operand as additional operands. Note does not block poison propagation.
1404 AnyOf,
1405 // Calculates the first active lane index of the vector predicate operands.
1406 // It produces the lane index across all unrolled iterations. Unrolling will
1407 // add all copies of its original operand as additional operands.
1408 // Implemented with @llvm.experimental.cttz.elts, but returns the expected
1409 // result even with operands that are all zeroes.
1410 FirstActiveLane,
1411 // Calculates the last active lane index of the vector predicate operands.
1412 // The predicates must be prefix-masks (all 1s before all 0s). Used when
1413 // tail-folding to extract the correct live-out value from the last active
1414 // iteration. It produces the lane index across all unrolled iterations.
1415 // Unrolling will add all copies of its original operand as additional
1416 // operands.
1417 LastActiveLane,
1418 // Returns a reversed vector for the operand.
1419 Reverse,
1420 /// Start vector for reductions with 3 operands: the original start value,
1421 /// the identity value for the reduction and an integer indicating the
1422 /// scaling factor.
1423 ReductionStartVector,
1424 /// Extracts a single lane (first operand) from a set of vector operands.
1425 /// The lane specifies an index into a vector formed by combining all vector
1426 /// operands (all operands after the first one).
1427 ExtractLane,
1428 /// Explicit user for values in the main VPlan, used by the epilogue vector
1429 /// loop. Operands are the resume value from the main vector loop and bypass
1430 /// value.
1431 ResumeForEpilogue,
1432 /// Extracts the last active lane from a set of vectors. The first operand
1433 /// is the default value if no lanes in the masks are active. Conceptually,
1434 /// this concatenates all data vectors (odd operands), concatenates all
1435 /// masks (even operands -- ignoring the default value), and returns the
1436 /// last active value from the combined data vector using the combined mask.
1437 ExtractLastActive,
1438 /// Compute the exiting value of a wide induction after vectorization, that
1439 /// is the value of the last lane of the induction increment (i.e. its
1440 /// backedge value). Has the wide induction recipe as operand.
1441 ExitingIVValue,
1442 MaskedCond,
1443 /// Scale the first operand (vector step) by the second operand
1444 /// (scalar-step). Casts both operands to the result type if needed.
1445 WideIVStep,
1446 // Creates a step vector starting from 0 to VF with a step of 1.
1447 StepVector,
1448 /// Calls a scalar intrinsic. The intrinsic ID is the last operand.
1449 Intrinsic,
1450
1451 OpsEnd = Intrinsic,
1452 };
1453
1454 /// Returns true if this recipe produces scalar values for all VF lanes.
1455 bool doesGeneratePerAllLanes() const;
1456
1457 /// Return the number of operands determined by the opcode of the
1458 /// VPInstruction, excluding mask. Returns -1u if the number of operands
1459 /// cannot be determined directly by the opcode.
1460 unsigned getNumOperandsForOpcode() const;
1461
1462private:
1463 typedef unsigned char OpcodeTy;
1464 OpcodeTy Opcode;
1465
1466 /// An optional name that can be used for the generated IR instruction.
1467 std::string Name;
1468
1469 /// Returns true if we can generate a scalar for the first lane only if
1470 /// needed.
1471 bool doesGenerateSingleScalar() const;
1472
1473 /// Utility method serving execute: Generates either a single-scalar or vector
1474 /// value. \p GenerateSingleScalar determines whether to generate a
1475 /// single-scalar value.
1476 Value *generate(VPTransformState &State, bool GenerateSingleScalar);
1477
1478 /// Returns true if the VPInstruction does not need masking.
1479 bool alwaysUnmasked() const {
1480 assert(Opcode != VPInstruction::MaskedCond &&
1481 "Should be expanded in VPlanPredicator");
1482
1483 // These VPInstruction can be (optionally) masked.
1484 if (Opcode == VPInstruction::WideVectorLoad ||
1485 Opcode == VPInstruction::WideVectorStore)
1486 return false;
1487
1488 // For now only VPInstructions with underlying values use masks.
1489 // TODO: provide masks to VPInstructions w/o underlying values.
1490 if (!getUnderlyingValue())
1491 return true;
1492
1493 return Instruction::isCast(Opcode) || Opcode == Instruction::PHI ||
1494 Opcode == Instruction::GetElementPtr ||
1495 Opcode == Instruction::ExtractValue;
1496 }
1497
1498 /// Returns true if this is an abstract instruction that can't be executed.
1499 bool isAbstract() const {
1500 return isMasked() && Opcode != VPInstruction::WideVectorLoad &&
1501 Opcode != VPInstruction::WideVectorStore;
1502 }
1503
1504public:
1505 VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands,
1506 const VPIRFlags &Flags = {}, const VPIRMetadata &MD = {},
1507 DebugLoc DL = DebugLoc::getUnknown(), const Twine &Name = "",
1508 Type *ResultTy = nullptr, const VPIRAttributes &Attrs = {});
1509
1510 VP_CLASSOF_IMPL(VPRecipeBase::VPInstructionSC)
1511
1512 VPInstruction *clone() override {
1513 return cloneWithOperands(NewOperands: operands(), ResultTy: getScalarType());
1514 }
1515
1516 VPInstruction *cloneWithOperands(ArrayRef<VPValue *> NewOperands,
1517 Type *ResultTy = nullptr) {
1518 auto *New = new VPInstruction(Opcode, NewOperands, *this, *this,
1519 getDebugLoc(), Name, ResultTy, *this);
1520 if (getUnderlyingValue())
1521 New->setUnderlyingValue(getUnderlyingInstr());
1522 return New;
1523 }
1524
1525 unsigned getOpcode() const { return Opcode; }
1526
1527 /// Add \p Op as operand of this VPInstruction. Only supported for AnyOf,
1528 /// ComputeReductionResult, BuildVector, ExtractLane,
1529 /// ExtractLastActive, FirstActiveLane, LastActiveLane.
1530 void addOperand(VPValue *Op);
1531
1532 void execute(VPTransformState &State) override;
1533
1534 /// Return the cost of this VPInstruction.
1535 InstructionCost computeCost(ElementCount VF,
1536 VPCostContext &Ctx) const override;
1537
1538#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1539 /// Print the VPInstruction to dbgs() (for debugging).
1540 LLVM_DUMP_METHOD void dump() const;
1541#endif
1542
1543 bool hasResult() const { return !getScalarType()->isVoidTy(); }
1544
1545 /// Returns true if the VPInstruction has a mask operand.
1546 bool isMasked() const {
1547 unsigned NumOpsForOpcode = getNumOperandsForOpcode();
1548 // VPInstructions without a fixed number of operands cannot be masked.
1549 if (NumOpsForOpcode == -1u)
1550 return false;
1551 return NumOpsForOpcode + 1 == getNumOperands();
1552 }
1553
1554 /// Returns the number of operands, excluding the mask if the VPInstruction is
1555 /// masked.
1556 unsigned getNumOperandsWithoutMask() const {
1557 return getNumOperands() - isMasked();
1558 }
1559
1560 /// Add mask \p Mask to an unmasked VPInstruction, if it needs masking.
1561 void addMask(VPValue *Mask) {
1562 assert(!isMasked() && "recipe is already masked");
1563 if (alwaysUnmasked())
1564 return;
1565 assert(Mask->getScalarType()->isIntegerTy(1) &&
1566 "Mask must be an i1 (vector)");
1567 VPUser::addOperand(Operand: Mask);
1568 }
1569
1570 /// Returns the mask for the VPInstruction. Returns nullptr for unmasked
1571 /// VPInstructions.
1572 VPValue *getMask() const { return isMasked() ? getLastOperand() : nullptr; }
1573
1574 /// Returns an iterator range over the operands excluding the mask operand
1575 /// if present.
1576 iterator_range<operand_iterator> operandsWithoutMask() {
1577 return make_range(x: op_begin(), y: op_begin() + getNumOperandsWithoutMask());
1578 }
1579 iterator_range<const_operand_iterator> operandsWithoutMask() const {
1580 return make_range(x: op_begin(), y: op_begin() + getNumOperandsWithoutMask());
1581 }
1582
1583 /// Returns true if the underlying opcode may read from or write to memory.
1584 bool opcodeMayReadOrWriteFromMemory() const;
1585
1586 /// Returns true if the recipe only uses the first lane of operand \p Op.
1587 bool usesFirstLaneOnly(const VPValue *Op) const override;
1588
1589 /// Returns true if the recipe only uses scalars of operand \p Op.
1590 bool usesScalars(const VPValue *Op) const override {
1591 return isSingleScalar() || getOpcode() == VPInstruction::PtrAdd ||
1592 usesFirstLaneOnly(Op);
1593 }
1594
1595 /// Returns true if the recipe only uses the first part of all operands.
1596 bool usesFirstPartOnly() const override;
1597
1598 /// Returns true if this VPInstruction produces a scalar value from a vector,
1599 /// e.g. by performing a reduction or extracting a lane.
1600 bool isVectorToScalar() const;
1601
1602 /// Returns true if the recipe produces a single scalar value.
1603 bool isSingleScalar() const;
1604
1605 /// Returns the symbolic name assigned to the VPInstruction.
1606 StringRef getName() const { return Name; }
1607
1608 /// Set the symbolic name for the VPInstruction.
1609 void setName(StringRef NewName) { Name = NewName.str(); }
1610
1611protected:
1612#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1613 /// Print the VPInstruction to \p O.
1614 void printRecipe(raw_ostream &O, const Twine &Indent,
1615 VPSlotTracker &SlotTracker) const override;
1616#endif
1617};
1618
1619/// Helper type to provide functions to access incoming values and blocks for
1620/// phi-like recipes.
1621class VPPhiAccessors {
1622protected:
1623 /// Return a VPRecipeBase* to the current object.
1624 virtual const VPRecipeBase *getAsRecipe() const = 0;
1625
1626public:
1627 virtual ~VPPhiAccessors() = default;
1628
1629 /// Returns the incoming VPValue with index \p Idx.
1630 VPValue *getIncomingValue(unsigned Idx) const {
1631 return getAsRecipe()->getOperand(N: Idx);
1632 }
1633
1634 /// Returns the incoming block with index \p Idx.
1635 const VPBasicBlock *getIncomingBlock(unsigned Idx) const;
1636
1637 /// Returns the incoming value for \p VPBB. \p VPBB must be an incoming block.
1638 LLVM_ABI_FOR_TEST VPValue *
1639 getIncomingValueForBlock(const VPBasicBlock *VPBB) const;
1640
1641 /// Sets the incoming value for \p VPBB to \p V. \p VPBB must be an incoming
1642 /// block.
1643 void setIncomingValueForBlock(const VPBasicBlock *VPBB, VPValue *V) const;
1644
1645 /// Returns the number of incoming values, also number of incoming blocks.
1646 virtual unsigned getNumIncoming() const {
1647 return getAsRecipe()->getNumOperands();
1648 }
1649
1650 /// Returns an interator range over the incoming values.
1651 VPUser::const_operand_range incoming_values() const {
1652 return make_range(x: getAsRecipe()->op_begin(),
1653 y: getAsRecipe()->op_begin() + getNumIncoming());
1654 }
1655
1656 using const_incoming_blocks_range = iterator_range<mapped_iterator<
1657 detail::index_iterator, std::function<const VPBasicBlock *(size_t)>>>;
1658
1659 /// Returns an iterator range over the incoming blocks.
1660 const_incoming_blocks_range incoming_blocks() const {
1661 std::function<const VPBasicBlock *(size_t)> GetBlock = [this](size_t Idx) {
1662 return getIncomingBlock(Idx);
1663 };
1664 return map_range(C: index_range(0, getNumIncoming()), F: GetBlock);
1665 }
1666
1667 /// Returns an iterator range over pairs of incoming values and corresponding
1668 /// incoming blocks.
1669 detail::zippy<llvm::detail::zip_first, VPUser::const_operand_range,
1670 const_incoming_blocks_range>
1671 incoming_values_and_blocks() const {
1672 return zip_equal(t: incoming_values(), u: incoming_blocks());
1673 }
1674
1675 /// Removes the incoming value for \p IncomingBlock, which must be a
1676 /// predecessor.
1677 void removeIncomingValueFor(VPBlockBase *IncomingBlock) const;
1678
1679 /// Append \p IncomingV as an incoming value to the phi-like recipe.
1680 void addIncoming(VPValue *IncomingV) {
1681 auto *R = const_cast<VPRecipeBase *>(getAsRecipe());
1682 assert((R->getNumOperands() == 0 ||
1683 IncomingV->getScalarType() == R->getOperand(0)->getScalarType()) &&
1684 "all incoming values must have the same type");
1685 R->addOperand(Operand: IncomingV);
1686 }
1687
1688#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1689 /// Print the recipe.
1690 void printPhiOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
1691#endif
1692};
1693
1694struct LLVM_ABI_FOR_TEST VPPhi : public VPInstruction, public VPPhiAccessors {
1695 VPPhi(ArrayRef<VPValue *> Operands, const VPIRFlags &Flags, DebugLoc DL,
1696 const Twine &Name = "", Type *ResultTy = nullptr)
1697 : VPInstruction(Instruction::PHI, Operands, Flags, {}, DL, Name,
1698 ResultTy) {}
1699
1700 static inline bool classof(const VPUser *U) {
1701 auto *VPI = dyn_cast<VPInstruction>(Val: U);
1702 return VPI && VPI->getOpcode() == Instruction::PHI;
1703 }
1704
1705 static inline bool classof(const VPValue *V) {
1706 auto *VPI = dyn_cast<VPInstruction>(Val: V);
1707 return VPI && VPI->getOpcode() == Instruction::PHI;
1708 }
1709
1710 static inline bool classof(const VPSingleDefRecipe *SDR) {
1711 auto *VPI = dyn_cast<VPInstruction>(Val: SDR);
1712 return VPI && VPI->getOpcode() == Instruction::PHI;
1713 }
1714
1715 VPPhi *clone() override {
1716 auto *PhiR = new VPPhi(operands(), *this, getDebugLoc(), getName());
1717 PhiR->setUnderlyingValue(getUnderlyingValue());
1718 return PhiR;
1719 }
1720
1721 void execute(VPTransformState &State) override;
1722
1723protected:
1724#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1725 /// Print the recipe.
1726 void printRecipe(raw_ostream &O, const Twine &Indent,
1727 VPSlotTracker &SlotTracker) const override;
1728#endif
1729
1730 const VPRecipeBase *getAsRecipe() const override { return this; }
1731};
1732
1733/// A recipe to wrap on original IR instruction not to be modified during
1734/// execution, except for PHIs. PHIs are modeled via the VPIRPhi subclass.
1735/// Expect PHIs, VPIRInstructions cannot have any operands.
1736class VPIRInstruction : public VPRecipeBase {
1737 Instruction &I;
1738
1739protected:
1740 /// VPIRInstruction::create() should be used to create VPIRInstructions, as
1741 /// subclasses may need to be created, e.g. VPIRPhi.
1742 VPIRInstruction(Instruction &I)
1743 : VPRecipeBase(VPRecipeBase::VPIRInstructionSC, {}), I(I) {}
1744
1745public:
1746 ~VPIRInstruction() override = default;
1747
1748 /// Create a new VPIRPhi for \p \I, if it is a PHINode, otherwise create a
1749 /// VPIRInstruction.
1750 LLVM_ABI_FOR_TEST static VPIRInstruction *create(Instruction &I);
1751
1752 VP_CLASSOF_IMPL(VPRecipeBase::VPIRInstructionSC)
1753
1754 VPIRInstruction *clone() override {
1755 auto *R = create(I);
1756 for (auto *Op : operands())
1757 R->addOperand(Operand: Op);
1758 return R;
1759 }
1760
1761 void execute(VPTransformState &State) override;
1762
1763 /// Return the cost of this VPIRInstruction.
1764 LLVM_ABI_FOR_TEST InstructionCost
1765 computeCost(ElementCount VF, VPCostContext &Ctx) const override;
1766
1767 Instruction &getInstruction() const { return I; }
1768
1769 bool usesScalars(const VPValue *Op) const override {
1770 assert(is_contained(operands(), Op) &&
1771 "Op must be an operand of the recipe");
1772 return true;
1773 }
1774
1775 /// Returns true if the recipe only uses the first part of all operands.
1776 bool usesFirstPartOnly() const override { return true; }
1777
1778 bool usesFirstLaneOnly(const VPValue *Op) const override {
1779 assert(is_contained(operands(), Op) &&
1780 "Op must be an operand of the recipe");
1781 return true;
1782 }
1783
1784protected:
1785#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1786 /// Print the recipe.
1787 void printRecipe(raw_ostream &O, const Twine &Indent,
1788 VPSlotTracker &SlotTracker) const override;
1789#endif
1790};
1791
1792/// An overlay for VPIRInstructions wrapping PHI nodes enabling convenient use
1793/// cast/dyn_cast/isa and execute() implementation. A single VPValue operand is
1794/// allowed, and it is used to add a new incoming value for the single
1795/// predecessor VPBB.
1796struct LLVM_ABI_FOR_TEST VPIRPhi : public VPIRInstruction,
1797 public VPPhiAccessors {
1798 VPIRPhi(PHINode &PN) : VPIRInstruction(PN) {}
1799
1800 static inline bool classof(const VPRecipeBase *U) {
1801 auto *R = dyn_cast<VPIRInstruction>(Val: U);
1802 return R && isa<PHINode>(Val: R->getInstruction());
1803 }
1804
1805 static inline bool classof(const VPUser *U) {
1806 auto *R = dyn_cast<VPRecipeBase>(Val: U);
1807 return R && classof(U: R);
1808 }
1809
1810 PHINode &getIRPhi() const { return cast<PHINode>(Val&: getInstruction()); }
1811
1812 void execute(VPTransformState &State) override;
1813
1814protected:
1815#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1816 /// Print the recipe.
1817 void printRecipe(raw_ostream &O, const Twine &Indent,
1818 VPSlotTracker &SlotTracker) const override;
1819#endif
1820
1821 const VPRecipeBase *getAsRecipe() const override { return this; }
1822};
1823
1824/// VPWidenRecipe is a recipe for producing a widened instruction using the
1825/// opcode and operands of the recipe. This recipe covers most of the
1826/// traditional vectorization cases where each recipe transforms into a
1827/// vectorized version of itself.
1828class LLVM_ABI_FOR_TEST VPWidenRecipe : public VPRecipeWithIRFlags,
1829 public VPIRMetadata {
1830 unsigned Opcode;
1831
1832public:
1833 VPWidenRecipe(Instruction &I, ArrayRef<VPValue *> Operands,
1834 const VPIRFlags &Flags = {}, const VPIRMetadata &Metadata = {},
1835 DebugLoc DL = {})
1836 : VPWidenRecipe(I.getOpcode(), Operands, Flags, Metadata, DL) {
1837 setUnderlyingValue(&I);
1838 }
1839
1840 VPWidenRecipe(unsigned Opcode, ArrayRef<VPValue *> Operands,
1841 const VPIRFlags &Flags = {}, const VPIRMetadata &Metadata = {},
1842 DebugLoc DL = {})
1843 : VPRecipeWithIRFlags(VPRecipeBase::VPWidenSC, Operands,
1844 computeScalarTypeForInstruction(Opcode, Operands),
1845 Flags, DL),
1846 VPIRMetadata(Metadata), Opcode(Opcode) {
1847 assert(flagsValidForOpcode(Opcode) &&
1848 "Set flags not supported for the provided opcode");
1849 assert(hasRequiredFlagsForOpcode(Opcode, getScalarType()) &&
1850 "Opcode requires specific flags to be set");
1851 }
1852
1853 ~VPWidenRecipe() override = default;
1854
1855 VPWidenRecipe *clone() override { return cloneWithOperands(NewOperands: operands()); }
1856
1857 VPWidenRecipe *cloneWithOperands(ArrayRef<VPValue *> NewOperands) {
1858 if (auto *UV = getUnderlyingValue())
1859 return new VPWidenRecipe(*cast<Instruction>(Val: UV), NewOperands, *this,
1860 *this, getDebugLoc());
1861 return new VPWidenRecipe(Opcode, NewOperands, *this, *this, getDebugLoc());
1862 }
1863
1864 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenSC)
1865
1866 /// Produce a widened instruction using the opcode and operands of the recipe,
1867 /// processing State.VF elements.
1868 void execute(VPTransformState &State) override;
1869
1870 /// Return the cost of this VPWidenRecipe.
1871 InstructionCost computeCost(ElementCount VF,
1872 VPCostContext &Ctx) const override;
1873
1874 unsigned getOpcode() const { return Opcode; }
1875
1876protected:
1877#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1878 /// Print the recipe.
1879 void printRecipe(raw_ostream &O, const Twine &Indent,
1880 VPSlotTracker &SlotTracker) const override;
1881#endif
1882
1883 /// Returns true if the recipe only uses the first lane of operand \p Op.
1884 bool usesFirstLaneOnly(const VPValue *Op) const override {
1885 assert(is_contained(operands(), Op) &&
1886 "Op must be an operand of the recipe");
1887 return Opcode == Instruction::Select && Op == getOperand(N: 0) &&
1888 isa<VPIRValue>(Val: Op);
1889 }
1890};
1891
1892/// VPWidenCastRecipe is a recipe to create vector cast instructions.
1893/// TODO: Merge with VPWidenRecipe now that type is associated to every
1894/// VPRecipeValue.
1895class LLVM_ABI_FOR_TEST VPWidenCastRecipe : public VPRecipeWithIRFlags,
1896 public VPIRMetadata {
1897 /// Cast instruction opcode.
1898 Instruction::CastOps Opcode;
1899
1900public:
1901 VPWidenCastRecipe(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy,
1902 CastInst *CI = nullptr, const VPIRFlags &Flags = {},
1903 const VPIRMetadata &Metadata = {},
1904 DebugLoc DL = DebugLoc::getUnknown())
1905 : VPRecipeWithIRFlags(VPRecipeBase::VPWidenCastSC, Op, ResultTy, Flags,
1906 DL),
1907 VPIRMetadata(Metadata), Opcode(Opcode) {
1908 assert(flagsValidForOpcode(Opcode) &&
1909 "Set flags not supported for the provided opcode");
1910 assert(hasRequiredFlagsForOpcode(Opcode, ResultTy) &&
1911 "Opcode requires specific flags to be set");
1912 setUnderlyingValue(CI);
1913 }
1914
1915 ~VPWidenCastRecipe() override = default;
1916
1917 VPWidenCastRecipe *clone() override {
1918 return new VPWidenCastRecipe(Opcode, getOperand(N: 0), getScalarType(),
1919 cast_or_null<CastInst>(Val: getUnderlyingValue()),
1920 *this, *this, getDebugLoc());
1921 }
1922
1923 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenCastSC)
1924
1925 /// Produce widened copies of the cast.
1926 void execute(VPTransformState &State) override;
1927
1928 /// Return the cost of this VPWidenCastRecipe.
1929 InstructionCost computeCost(ElementCount VF,
1930 VPCostContext &Ctx) const override;
1931
1932 Instruction::CastOps getOpcode() const { return Opcode; }
1933
1934protected:
1935#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1936 /// Print the recipe.
1937 void printRecipe(raw_ostream &O, const Twine &Indent,
1938 VPSlotTracker &SlotTracker) const override;
1939#endif
1940};
1941
1942/// A recipe for widening vector intrinsics.
1943class LLVM_ABI_FOR_TEST VPWidenIntrinsicRecipe : public VPRecipeWithIRFlags,
1944 public VPIRMetadata {
1945 /// ID of the vector intrinsic to widen.
1946 Intrinsic::ID VectorIntrinsicID;
1947
1948 /// True if the intrinsic may read from memory.
1949 bool MayReadFromMemory;
1950
1951 /// True if the intrinsic may read write to memory.
1952 bool MayWriteToMemory;
1953
1954 /// True if the intrinsic may have side-effects.
1955 bool MayHaveSideEffects;
1956
1957protected:
1958 VPWidenIntrinsicRecipe(VPRecipeTy SC, Intrinsic::ID VectorIntrinsicID,
1959 ArrayRef<VPValue *> CallArguments, Type *Ty,
1960 const VPIRFlags &Flags = {},
1961 const VPIRMetadata &MD = {},
1962 DebugLoc DL = DebugLoc::getUnknown())
1963 : VPRecipeWithIRFlags(SC, CallArguments, Ty, Flags, DL), VPIRMetadata(MD),
1964 VectorIntrinsicID(VectorIntrinsicID) {
1965 LLVMContext &Ctx = Ty->getContext();
1966 AttributeSet Attrs = Intrinsic::getFnAttributes(C&: Ctx, id: VectorIntrinsicID);
1967 MemoryEffects ME = Attrs.getMemoryEffects();
1968 MayReadFromMemory = !ME.onlyWritesMemory();
1969 MayWriteToMemory = !ME.onlyReadsMemory();
1970 MayHaveSideEffects = MayWriteToMemory ||
1971 !Attrs.hasAttribute(Kind: Attribute::NoUnwind) ||
1972 !Attrs.hasAttribute(Kind: Attribute::WillReturn);
1973 }
1974
1975 /// Helper function to produce the widened intrinsic call.
1976 CallInst *createVectorCall(VPTransformState &State);
1977
1978public:
1979 VPWidenIntrinsicRecipe(CallInst &CI, Intrinsic::ID VectorIntrinsicID,
1980 ArrayRef<VPValue *> CallArguments, Type *Ty,
1981 const VPIRFlags &Flags = {},
1982 const VPIRMetadata &MD = {},
1983 DebugLoc DL = DebugLoc::getUnknown())
1984 : VPRecipeWithIRFlags(VPRecipeBase::VPWidenIntrinsicSC, CallArguments, Ty,
1985 Flags, DL),
1986 VPIRMetadata(MD), VectorIntrinsicID(VectorIntrinsicID),
1987 MayReadFromMemory(CI.mayReadFromMemory()),
1988 MayWriteToMemory(CI.mayWriteToMemory()),
1989 MayHaveSideEffects(CI.mayHaveSideEffects()) {
1990 setUnderlyingValue(&CI);
1991 }
1992
1993 VPWidenIntrinsicRecipe(Intrinsic::ID VectorIntrinsicID,
1994 ArrayRef<VPValue *> CallArguments, Type *Ty,
1995 const VPIRFlags &Flags = {},
1996 const VPIRMetadata &Metadata = {},
1997 DebugLoc DL = DebugLoc::getUnknown())
1998 : VPWidenIntrinsicRecipe(VPRecipeBase::VPWidenIntrinsicSC,
1999 VectorIntrinsicID, CallArguments, Ty, Flags,
2000 Metadata, DL) {}
2001
2002 ~VPWidenIntrinsicRecipe() override = default;
2003
2004 VPWidenIntrinsicRecipe *clone() override {
2005 if (Value *CI = getUnderlyingValue())
2006 return new VPWidenIntrinsicRecipe(*cast<CallInst>(Val: CI), VectorIntrinsicID,
2007 operands(), getScalarType(), *this,
2008 *this, getDebugLoc());
2009 return new VPWidenIntrinsicRecipe(VectorIntrinsicID, operands(),
2010 getScalarType(), *this, *this,
2011 getDebugLoc());
2012 }
2013
2014 static inline bool classof(const VPRecipeBase *R) {
2015 return R->getVPRecipeID() == VPRecipeBase::VPWidenIntrinsicSC ||
2016 R->getVPRecipeID() == VPRecipeBase::VPWidenMemIntrinsicSC;
2017 }
2018
2019 static inline bool classof(const VPUser *U) {
2020 auto *R = dyn_cast<VPRecipeBase>(Val: U);
2021 return R && classof(R);
2022 }
2023
2024 static inline bool classof(const VPValue *V) {
2025 auto *R = V->getDefiningRecipe();
2026 return R && classof(R);
2027 }
2028
2029 static inline bool classof(const VPSingleDefRecipe *R) {
2030 return classof(R: static_cast<const VPRecipeBase *>(R));
2031 }
2032
2033 /// Produce a widened version of the vector intrinsic.
2034 void execute(VPTransformState &State) override;
2035
2036 /// Compute the cost of a vector intrinsic with \p ID and \p Operands.
2037 static InstructionCost computeCallCost(Intrinsic::ID ID,
2038 ArrayRef<const VPValue *> Operands,
2039 const VPRecipeWithIRFlags &R,
2040 ElementCount VF, VPCostContext &Ctx);
2041
2042 /// Return the cost of this vector intrinsic.
2043 InstructionCost computeCost(ElementCount VF,
2044 VPCostContext &Ctx) const override;
2045
2046 /// Return the ID of the intrinsic.
2047 Intrinsic::ID getVectorIntrinsicID() const { return VectorIntrinsicID; }
2048
2049 /// Return to name of the intrinsic as string.
2050 StringRef getIntrinsicName() const;
2051
2052 /// Returns true if the intrinsic may read from memory.
2053 bool mayReadFromMemory() const { return MayReadFromMemory; }
2054
2055 /// Returns true if the intrinsic may write to memory.
2056 bool mayWriteToMemory() const { return MayWriteToMemory; }
2057
2058 /// Returns true if the intrinsic may have side-effects.
2059 bool mayHaveSideEffects() const { return MayHaveSideEffects; }
2060
2061 bool usesFirstLaneOnly(const VPValue *Op) const override;
2062
2063protected:
2064#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2065 /// Print the recipe.
2066 void printRecipe(raw_ostream &O, const Twine &Indent,
2067 VPSlotTracker &SlotTracker) const override;
2068#endif
2069};
2070
2071/// A recipe for widening vector memory intrinsics.
2072class LLVM_ABI_FOR_TEST VPWidenMemIntrinsicRecipe final
2073 : public VPWidenIntrinsicRecipe {
2074 /// Alignment information for this memory access.
2075 Align Alignment;
2076
2077public:
2078 VPWidenMemIntrinsicRecipe(Intrinsic::ID VectorIntrinsicID,
2079 ArrayRef<VPValue *> CallArguments, Type *Ty,
2080 Align Alignment, const VPIRMetadata &MD = {},
2081 DebugLoc DL = DebugLoc::getUnknown())
2082 : VPWidenIntrinsicRecipe(VPRecipeBase::VPWidenMemIntrinsicSC,
2083 VectorIntrinsicID, CallArguments, Ty, {}, MD,
2084 DL),
2085 Alignment(Alignment) {
2086 assert(getVectorMemoryIntrinsicPointerArgIdx(VectorIntrinsicID) &&
2087 getVectorIntrinsicMaskArgIdx(VectorIntrinsicID) &&
2088 "Expected a masked vector load/store intrinsic");
2089 assert((!Ty->isVoidTy() ||
2090 getVectorStoreIntrinsicDataArgIdx(VectorIntrinsicID)) &&
2091 "Expected data argument for store intrinsic");
2092 }
2093
2094 ~VPWidenMemIntrinsicRecipe() override = default;
2095
2096 VPWidenMemIntrinsicRecipe *clone() override {
2097 return new VPWidenMemIntrinsicRecipe(getVectorIntrinsicID(), operands(),
2098 getScalarType(), Alignment, *this,
2099 getDebugLoc());
2100 }
2101
2102 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenMemIntrinsicSC)
2103
2104 /// Produce a widened version of the vector memory intrinsic.
2105 void execute(VPTransformState &State) override;
2106
2107 /// Returns the address operand index of the VPWidenMemIntrinsicRecipe.
2108 unsigned getAddrOpIdx() const;
2109
2110 /// Returns the mask of a predicated VPWidenMemIntrinsicRecipe.
2111 VPValue *getMask() const;
2112
2113 /// Returns the data type of the memory access at \p VF.
2114 Type *getAccessType(ElementCount VF) const;
2115
2116 /// Helper function for computing the cost of vector memory intrinsic.
2117 static InstructionCost computeMemIntrinsicCost(Intrinsic::ID IID, Type *Ty,
2118 bool IsMasked, Align Alignment,
2119 VPCostContext &Ctx);
2120
2121 /// Return the cost of this vector memory intrinsic.
2122 InstructionCost computeCost(ElementCount VF,
2123 VPCostContext &Ctx) const override;
2124};
2125
2126/// A recipe for widening Call instructions using library calls.
2127class LLVM_ABI_FOR_TEST VPWidenCallRecipe : public VPRecipeWithIRFlags,
2128 public VPIRMetadata,
2129 public VPIRAttributes {
2130 /// Variant stores a pointer to the chosen function. There is a 1:1 mapping
2131 /// between a given VF and the chosen vectorized variant, so there will be a
2132 /// different VPlan for each VF with a valid variant.
2133 Function *Variant;
2134
2135public:
2136 VPWidenCallRecipe(Value *UV, Function *Variant,
2137 ArrayRef<VPValue *> CallArguments,
2138 const VPIRFlags &Flags = {},
2139 const VPIRMetadata &Metadata = {},
2140 const VPIRAttributes &Attrs = {}, DebugLoc DL = {})
2141 : VPRecipeWithIRFlags(VPRecipeBase::VPWidenCallSC, CallArguments,
2142 toScalarizedTy(Ty: Variant->getReturnType()), Flags,
2143 DL),
2144 VPIRMetadata(Metadata), VPIRAttributes(Attrs), Variant(Variant) {
2145 setUnderlyingValue(UV);
2146 assert(isa<Function>(getLastOperand()->getLiveInIRValue()) &&
2147 "last operand must be the called function");
2148 assert(cast<Function>(CallArguments.back()->getLiveInIRValue())
2149 ->getReturnType() == getScalarType() &&
2150 "Scalar type must match return type of called scalar function");
2151 }
2152
2153 ~VPWidenCallRecipe() override = default;
2154
2155 VPWidenCallRecipe *clone() override {
2156 return new VPWidenCallRecipe(getUnderlyingValue(), Variant, operands(),
2157 *this, *this, *this, getDebugLoc());
2158 }
2159
2160 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenCallSC)
2161
2162 /// Produce a widened version of the call instruction.
2163 void execute(VPTransformState &State) override;
2164
2165 /// Return the cost of this VPWidenCallRecipe.
2166 InstructionCost computeCost(ElementCount VF,
2167 VPCostContext &Ctx) const override;
2168
2169 /// Return the cost of widening a call using the vector function \p Variant.
2170 static InstructionCost computeCallCost(Function *Variant, VPCostContext &Ctx);
2171
2172 Function *getCalledScalarFunction() const {
2173 return cast<Function>(Val: getLastOperand()->getLiveInIRValue());
2174 }
2175
2176 operand_range args() { return drop_end(RangeOrContainer: operands()); }
2177 const_operand_range args() const { return drop_end(RangeOrContainer: operands()); }
2178
2179 /// Returns true if the recipe only uses the first lane of operand \p Op.
2180 bool usesFirstLaneOnly(const VPValue *Op) const override;
2181
2182protected:
2183#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2184 /// Print the recipe.
2185 void printRecipe(raw_ostream &O, const Twine &Indent,
2186 VPSlotTracker &SlotTracker) const override;
2187#endif
2188};
2189
2190/// A recipe representing a sequence of load -> update -> store as part of
2191/// a histogram operation. This means there may be aliasing between vector
2192/// lanes, which is handled by the llvm.experimental.vector.histogram family
2193/// of intrinsics. Supported update operations are: add, sub, uadd.sat, umax,
2194/// and umin, where the other term is loop-invariant.
2195class VPHistogramRecipe : public VPRecipeBase, public VPIRMetadata {
2196 /// The update operation kind for this histogram.
2197 HistogramUpdateKind UpdateKind;
2198
2199public:
2200 VPHistogramRecipe(HistogramUpdateKind UpdateKind,
2201 ArrayRef<VPValue *> Operands,
2202 const VPIRMetadata &Metadata = {},
2203 DebugLoc DL = DebugLoc::getUnknown())
2204 : VPRecipeBase(VPRecipeBase::VPHistogramSC, Operands, DL),
2205 VPIRMetadata(Metadata), UpdateKind(UpdateKind) {}
2206
2207 ~VPHistogramRecipe() override = default;
2208
2209 VPHistogramRecipe *clone() override {
2210 return new VPHistogramRecipe(UpdateKind, operands(), *this, getDebugLoc());
2211 }
2212
2213 VP_CLASSOF_IMPL(VPRecipeBase::VPHistogramSC);
2214
2215 /// Produce a vectorized histogram operation.
2216 void execute(VPTransformState &State) override;
2217
2218 /// Return the cost of this VPHistogramRecipe.
2219 InstructionCost computeCost(ElementCount VF,
2220 VPCostContext &Ctx) const override;
2221
2222 /// Return the mask operand if one was provided, or a null pointer if all
2223 /// lanes should be executed unconditionally.
2224 VPValue *getMask() const {
2225 return getNumOperands() == 3 ? getOperand(N: 2) : nullptr;
2226 }
2227
2228 /// Returns true if the recipe only uses the first lane of operand \p Op.
2229 bool usesFirstLaneOnly(const VPValue *Op) const override {
2230 assert(is_contained(operands(), Op) &&
2231 "Op must be an operand of the recipe");
2232 return Op == getOperand(N: 1);
2233 }
2234
2235private:
2236 /// Return the histogram intrinsic ID for this recipe's update kind.
2237 Intrinsic::ID getHistogramIntrinsicID() const;
2238
2239 /// Return true if the increment should be negated before passing to the
2240 /// histogram intrinsic (only for Sub).
2241 bool mustNegateIncrement() const {
2242 return UpdateKind == HistogramUpdateKind::Sub;
2243 }
2244
2245protected:
2246#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2247 /// Print the recipe
2248 void printRecipe(raw_ostream &O, const Twine &Indent,
2249 VPSlotTracker &SlotTracker) const override;
2250#endif
2251};
2252
2253/// A recipe for handling GEP instructions.
2254class LLVM_ABI_FOR_TEST VPWidenGEPRecipe : public VPRecipeWithIRFlags {
2255 Type *SourceElementTy;
2256
2257public:
2258 VPWidenGEPRecipe(Type *SourceElementTy, ArrayRef<VPValue *> Operands,
2259 const VPIRFlags &Flags = {},
2260 DebugLoc DL = DebugLoc::getUnknown(),
2261 GetElementPtrInst *UV = nullptr)
2262 : VPRecipeWithIRFlags(VPRecipeBase::VPWidenGEPSC, Operands,
2263 Operands[0]->getScalarType(), Flags, DL),
2264 SourceElementTy(SourceElementTy) {
2265 if (UV) {
2266 setUnderlyingValue(UV);
2267 [[maybe_unused]] SmallVector<std::pair<unsigned, MDNode *>> Metadata;
2268 getMetadataToPropagate(Inst: UV, Metadata);
2269 assert(Metadata.empty() && "unexpected metadata on GEP");
2270 }
2271 }
2272
2273 ~VPWidenGEPRecipe() override = default;
2274
2275 VPWidenGEPRecipe *clone() override {
2276 return new VPWidenGEPRecipe(
2277 getSourceElementType(), operands(), *this, getDebugLoc(),
2278 cast_or_null<GetElementPtrInst>(Val: getUnderlyingValue()));
2279 }
2280
2281 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenGEPSC)
2282
2283 /// This recipe generates a GEP instruction.
2284 unsigned getOpcode() const { return Instruction::GetElementPtr; }
2285
2286 /// Generate the gep nodes.
2287 void execute(VPTransformState &State) override;
2288
2289 Type *getSourceElementType() const { return SourceElementTy; }
2290
2291 /// Return the cost of this VPWidenGEPRecipe.
2292 InstructionCost computeCost(ElementCount VF,
2293 VPCostContext &Ctx) const override {
2294 // TODO: Compute accurate cost after retiring the legacy cost model.
2295 return 0;
2296 }
2297
2298 /// Returns true if the recipe only uses the first lane of operand \p Op.
2299 bool usesFirstLaneOnly(const VPValue *Op) const override;
2300
2301protected:
2302#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2303 /// Print the recipe.
2304 void printRecipe(raw_ostream &O, const Twine &Indent,
2305 VPSlotTracker &SlotTracker) const override;
2306#endif
2307};
2308
2309/// A recipe to compute a pointer to the last element of each part of a widened
2310/// memory access for widened memory accesses of SourceElementTy. Used for
2311/// VPWidenMemoryRecipes or VPInterleaveRecipes that are reversed. An extra
2312/// Offset operand is added by convertToConcreteRecipes when UF = 1, and by the
2313/// unroller otherwise.
2314class VPVectorEndPointerRecipe : public VPRecipeWithIRFlags {
2315 Type *SourceElementTy;
2316
2317 /// The constant stride of the pointer computed by this recipe, expressed in
2318 /// units of SourceElementTy.
2319 int64_t Stride;
2320
2321public:
2322 VPVectorEndPointerRecipe(VPValue *Ptr, VPValue *VF, Type *SourceElementTy,
2323 int64_t Stride, GEPNoWrapFlags GEPFlags, DebugLoc DL)
2324 : VPRecipeWithIRFlags(VPRecipeBase::VPVectorEndPointerSC, {Ptr, VF},
2325 Ptr->getScalarType(), GEPFlags, DL),
2326 SourceElementTy(SourceElementTy), Stride(Stride) {
2327 assert(Stride < 0 && "Stride must be negative");
2328 }
2329
2330 VP_CLASSOF_IMPL(VPRecipeBase::VPVectorEndPointerSC)
2331
2332 Type *getSourceElementType() const { return SourceElementTy; }
2333 int64_t getStride() const { return Stride; }
2334 VPValue *getPointer() const { return getOperand(N: 0); }
2335 VPValue *getVFValue() const { return getOperand(N: 1); }
2336 VPValue *getOffset() const {
2337 return getNumOperands() == 3 ? getOperand(N: 2) : nullptr;
2338 }
2339
2340 /// Adds the offset operand to the recipe.
2341 /// Offset = Stride * (VF - 1) + Part * Stride * VF.
2342 void materializeOffset(unsigned Part = 0);
2343
2344 /// Append \p Offset as the offset operand. The offset is an integer index
2345 /// expressed in units of SourceElementTy.
2346 void addOffset(VPValue *Offset) {
2347 assert(Offset->getScalarType()->isIntegerTy() &&
2348 "offset must be an integer index");
2349 VPUser::addOperand(Operand: Offset);
2350 }
2351
2352 void execute(VPTransformState &State) override;
2353
2354 bool usesFirstLaneOnly(const VPValue *Op) const override {
2355 assert(is_contained(operands(), Op) &&
2356 "Op must be an operand of the recipe");
2357 return true;
2358 }
2359
2360 /// Return the cost of this VPVectorPointerRecipe.
2361 InstructionCost computeCost(ElementCount VF,
2362 VPCostContext &Ctx) const override {
2363 // TODO: Compute accurate cost after retiring the legacy cost model.
2364 return 0;
2365 }
2366
2367 /// Returns true if the recipe only uses the first part of all operands.
2368 bool usesFirstPartOnly() const override {
2369 assert(getNumOperands() <= 2 && "must have at most two operands");
2370 return true;
2371 }
2372
2373 VPVectorEndPointerRecipe *clone() override {
2374 auto *VEPR = new VPVectorEndPointerRecipe(
2375 getPointer(), getVFValue(), getSourceElementType(), getStride(),
2376 getGEPNoWrapFlags(), getDebugLoc());
2377 if (auto *Offset = getOffset())
2378 VEPR->addOffset(Offset);
2379 return VEPR;
2380 }
2381
2382protected:
2383#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2384 /// Print the recipe.
2385 void printRecipe(raw_ostream &O, const Twine &Indent,
2386 VPSlotTracker &SlotTracker) const override;
2387#endif
2388};
2389
2390/// A recipe to compute the pointers for widened memory accesses of \p
2391/// SourceElementTy, with the \p Stride expressed in units of \p
2392/// SourceElementTy. Unrolling adds an extra \p VFxPart operand for unrolled
2393/// parts > 0 and it produces `GEP SourceElementTy Ptr, VFxPart * Stride`.
2394class VPVectorPointerRecipe : public VPRecipeWithIRFlags {
2395 Type *SourceElementTy;
2396
2397public:
2398 VPVectorPointerRecipe(VPValue *Ptr, Type *SourceElementTy, VPValue *Stride,
2399 GEPNoWrapFlags GEPFlags, DebugLoc DL)
2400 : VPRecipeWithIRFlags(VPRecipeBase::VPVectorPointerSC,
2401 ArrayRef<VPValue *>({Ptr, Stride}),
2402 Ptr->getScalarType(), GEPFlags, DL),
2403 SourceElementTy(SourceElementTy) {}
2404
2405 VP_CLASSOF_IMPL(VPRecipeBase::VPVectorPointerSC)
2406
2407 VPValue *getStride() const { return getOperand(N: 1); }
2408
2409 VPValue *getVFxPart() const {
2410 return getNumOperands() > 2 ? getOperand(N: 2) : nullptr;
2411 }
2412
2413 /// Add the per-part offset (VFxPart) used for unrolled parts > 0.
2414 void addPerPartOffset(VPValue *VFxPart) {
2415 assert(VFxPart->getScalarType()->isIntegerTy() &&
2416 "per-part offset must be an integer index");
2417 VPUser::addOperand(Operand: VFxPart);
2418 }
2419
2420 void execute(VPTransformState &State) override;
2421
2422 Type *getSourceElementType() const { return SourceElementTy; }
2423
2424 bool usesFirstLaneOnly(const VPValue *Op) const override {
2425 assert(is_contained(operands(), Op) &&
2426 "Op must be an operand of the recipe");
2427 return true;
2428 }
2429
2430 /// Returns true if the recipe only uses the first part of all operands.
2431 bool usesFirstPartOnly() const override {
2432 assert(getNumOperands() <= 2 && "must have at most two operands");
2433 return true;
2434 }
2435
2436 VPVectorPointerRecipe *clone() override {
2437 auto *Clone =
2438 new VPVectorPointerRecipe(getOperand(N: 0), SourceElementTy, getStride(),
2439 getGEPNoWrapFlags(), getDebugLoc());
2440 if (auto *VFxPart = getVFxPart())
2441 Clone->addPerPartOffset(VFxPart);
2442 return Clone;
2443 }
2444
2445 /// Return the cost of this VPHeaderPHIRecipe.
2446 InstructionCost computeCost(ElementCount VF,
2447 VPCostContext &Ctx) const override {
2448 // TODO: Compute accurate cost after retiring the legacy cost model.
2449 return 0;
2450 }
2451
2452protected:
2453#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2454 /// Print the recipe.
2455 void printRecipe(raw_ostream &O, const Twine &Indent,
2456 VPSlotTracker &SlotTracker) const override;
2457#endif
2458};
2459
2460/// A pure virtual base class for all recipes modeling header phis, including
2461/// phis for first order recurrences, pointer inductions and reductions. The
2462/// start value is the first operand of the recipe and the incoming value from
2463/// the backedge is the second operand.
2464///
2465/// Inductions are modeled using the following sub-classes:
2466/// * VPWidenIntOrFpInductionRecipe: Generates vector values for integer and
2467/// floating point inductions with arbitrary start and step values. Produces
2468/// a vector PHI per-part.
2469/// * VPWidenPointerInductionRecipe: Generate vector and scalar values for a
2470/// pointer induction. Produces either a vector PHI per-part or scalar values
2471/// per-lane based on the canonical induction.
2472/// * VPFirstOrderRecurrencePHIRecipe
2473/// * VPReductionPHIRecipe
2474/// * VPActiveLaneMaskPHIRecipe
2475/// * VPEVLBasedIVPHIRecipe
2476///
2477/// Note that the canonical IV is modeled as a VPRegionValue associated with
2478/// its loop region.
2479class LLVM_ABI_FOR_TEST VPHeaderPHIRecipe : public VPSingleDefRecipe,
2480 public VPPhiAccessors {
2481protected:
2482 VPHeaderPHIRecipe(VPRecipeTy VPRecipeID, Instruction *UnderlyingInstr,
2483 VPValue *Start, Type *ResultTy,
2484 DebugLoc DL = DebugLoc::getUnknown())
2485 : VPSingleDefRecipe(VPRecipeID, Start, ResultTy, UnderlyingInstr, DL) {}
2486
2487 const VPRecipeBase *getAsRecipe() const override { return this; }
2488
2489public:
2490 ~VPHeaderPHIRecipe() override = default;
2491
2492 /// Method to support type inquiry through isa, cast, and dyn_cast.
2493 static inline bool classof(const VPRecipeBase *R) {
2494 return R->getVPRecipeID() >= VPRecipeBase::VPFirstHeaderPHISC &&
2495 R->getVPRecipeID() <= VPRecipeBase::VPLastHeaderPHISC;
2496 }
2497 static inline bool classof(const VPValue *V) {
2498 return isa<VPHeaderPHIRecipe>(Val: V->getDefiningRecipe());
2499 }
2500 static inline bool classof(const VPSingleDefRecipe *R) {
2501 return isa<VPHeaderPHIRecipe>(Val: static_cast<const VPRecipeBase *>(R));
2502 }
2503
2504 /// Generate the phi nodes.
2505 void execute(VPTransformState &State) override = 0;
2506
2507 /// Return the cost of this header phi recipe.
2508 InstructionCost computeCost(ElementCount VF,
2509 VPCostContext &Ctx) const override;
2510
2511 /// Returns the start value of the phi, if one is set.
2512 VPValue *getStartValue() {
2513 return getNumOperands() == 0 ? nullptr : getOperand(N: 0);
2514 }
2515 VPValue *getStartValue() const {
2516 return getNumOperands() == 0 ? nullptr : getOperand(N: 0);
2517 }
2518
2519 /// Update the start value of the recipe.
2520 void setStartValue(VPValue *V) { setOperand(I: 0, New: V); }
2521
2522 /// Returns the incoming value from the loop backedge.
2523 virtual VPValue *getBackedgeValue() { return getOperand(N: 1); }
2524
2525 /// Update the incoming value from the loop backedge.
2526 void setBackedgeValue(VPValue *V) { setOperand(I: 1, New: V); }
2527
2528 /// Add \p V as the incoming value from the loop backedge.
2529 void addBackedgeValue(VPValue *V) {
2530 assert(getNumOperands() == 1 &&
2531 "backedge value must be appended right after construction");
2532 assert(V->getScalarType() == getScalarType() &&
2533 "backedge value must have the same type as the start value");
2534 VPUser::addOperand(Operand: V);
2535 }
2536
2537protected:
2538#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2539 /// Print the recipe.
2540 void printRecipe(raw_ostream &O, const Twine &Indent,
2541 VPSlotTracker &SlotTracker) const override = 0;
2542#endif
2543};
2544
2545/// Base class for widened induction (VPWidenIntOrFpInductionRecipe and
2546/// VPWidenPointerInductionRecipe), providing shared functionality, including
2547/// retrieving the step value, induction descriptor and original phi node.
2548class VPWidenInductionRecipe : public VPHeaderPHIRecipe {
2549 InductionDescriptor IndDesc;
2550
2551public:
2552 VPWidenInductionRecipe(VPRecipeTy Kind, PHINode *IV, VPValue *Start,
2553 VPValue *Step, const InductionDescriptor &IndDesc,
2554 Type *ResultTy, DebugLoc DL)
2555 : VPHeaderPHIRecipe(Kind, IV, Start, ResultTy, DL), IndDesc(IndDesc) {
2556 addOperand(Operand: Step);
2557 }
2558
2559 /// After unrolling, append the splat-VF step (`VF * step`) and the value of
2560 /// the induction at the last unrolled part.
2561 void addUnrolledPartOperands(VPValue *SplatVFStep, VPValue *LastPart) {
2562 assert(LastPart->getScalarType() == getScalarType() &&
2563 "last-part value must match the induction recipe's scalar type");
2564 assert((getScalarType()->isPointerTy()
2565 ? SplatVFStep->getScalarType()->isIntegerTy()
2566 : SplatVFStep->getScalarType() == getScalarType()) &&
2567 "splat-step must match the induction type for non-pointer "
2568 "inductions, or be an integer index for pointer inductions");
2569 VPUser::addOperand(Operand: SplatVFStep);
2570 VPUser::addOperand(Operand: LastPart);
2571 }
2572
2573 static inline bool classof(const VPRecipeBase *R) {
2574 return R->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC ||
2575 R->getVPRecipeID() == VPRecipeBase::VPWidenPointerInductionSC;
2576 }
2577
2578 static inline bool classof(const VPValue *V) {
2579 auto *R = V->getDefiningRecipe();
2580 return R && classof(R);
2581 }
2582
2583 static inline bool classof(const VPSingleDefRecipe *R) {
2584 return classof(R: static_cast<const VPRecipeBase *>(R));
2585 }
2586
2587 void execute(VPTransformState &State) override = 0;
2588
2589 /// Returns the step value of the induction.
2590 VPValue *getStepValue() { return getOperand(N: 1); }
2591 const VPValue *getStepValue() const { return getOperand(N: 1); }
2592
2593 VPValue *getVFValue() { return getOperand(N: 2); }
2594 const VPValue *getVFValue() const { return getOperand(N: 2); }
2595
2596 /// Returns the number of incoming values, also number of incoming blocks.
2597 /// Note that at the moment, VPWidenPointerInductionRecipe only has a single
2598 /// incoming value, its start value.
2599 unsigned getNumIncoming() const override { return 1; }
2600
2601 /// Returns the underlying PHINode if one exists, or null otherwise.
2602 PHINode *getPHINode() const {
2603 return cast_if_present<PHINode>(Val: getUnderlyingValue());
2604 }
2605
2606 /// Returns the induction descriptor for the recipe.
2607 const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
2608
2609 /// Returns the SCEV predicates associated with this induction.
2610 ArrayRef<const SCEVPredicate *> getNoWrapPredicates() const {
2611 return IndDesc.getNoWrapPredicates();
2612 }
2613
2614 VPValue *getBackedgeValue() override {
2615 // TODO: All operands of base recipe must exist and be at same index in
2616 // derived recipe.
2617 llvm_unreachable(
2618 "VPWidenIntOrFpInductionRecipe generates its own backedge value");
2619 }
2620
2621 /// Returns true if the recipe only uses the first lane of operand \p Op.
2622 bool usesFirstLaneOnly(const VPValue *Op) const override {
2623 assert(is_contained(operands(), Op) &&
2624 "Op must be an operand of the recipe");
2625 // The recipe creates its own wide start value, so it only requests the
2626 // first lane of the operand.
2627 // TODO: Remove once creating the start value is modeled separately.
2628 return Op == getStartValue() || Op == getStepValue();
2629 }
2630};
2631
2632/// A recipe for handling phi nodes of integer and floating-point inductions,
2633/// producing their vector values. This is an abstract recipe and must be
2634/// converted to concrete recipes before executing.
2635class VPWidenIntOrFpInductionRecipe : public VPWidenInductionRecipe,
2636 public VPIRFlags {
2637 // If this recipe is unrolled it will have 2 additional operands.
2638 bool isUnrolled() const { return getNumOperands() == 5; }
2639
2640public:
2641 VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step,
2642 VPValue *VF, const InductionDescriptor &IndDesc,
2643 const VPIRFlags &Flags, DebugLoc DL)
2644 : VPWidenInductionRecipe(VPRecipeBase::VPWidenIntOrFpInductionSC, IV,
2645 Start, Step, IndDesc, Start->getScalarType(),
2646 DL),
2647 VPIRFlags(Flags) {
2648 addOperand(Operand: VF);
2649 }
2650
2651 VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step,
2652 VPValue *VF, const InductionDescriptor &IndDesc,
2653 Type *ResultTy, const VPIRFlags &Flags,
2654 DebugLoc DL)
2655 : VPWidenInductionRecipe(VPRecipeBase::VPWidenIntOrFpInductionSC, IV,
2656 Start, Step, IndDesc, ResultTy, DL),
2657 VPIRFlags(Flags) {
2658 addOperand(Operand: VF);
2659 }
2660
2661 ~VPWidenIntOrFpInductionRecipe() override = default;
2662
2663 VPWidenIntOrFpInductionRecipe *clone() override {
2664 return new VPWidenIntOrFpInductionRecipe(
2665 getPHINode(), getStartValue(), getStepValue(), getVFValue(),
2666 getInductionDescriptor(), getScalarType(), *this, getDebugLoc());
2667 }
2668
2669 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenIntOrFpInductionSC)
2670
2671 void execute(VPTransformState &State) override {
2672 llvm_unreachable("cannot execute this recipe, should be expanded via "
2673 "expandVPWidenIntOrFpInductionRecipe");
2674 }
2675
2676 /// If the recipe has been unrolled, return the VPValue for the induction
2677 /// increment, otherwise return null.
2678 VPValue *getSplatVFValue() const {
2679 return isUnrolled() ? getOperand(N: getNumOperands() - 2) : nullptr;
2680 }
2681
2682 /// Returns the number of incoming values, also number of incoming blocks.
2683 /// Note that at the moment, VPWidenIntOrFpInductionRecipes only have a single
2684 /// incoming value, its start value.
2685 unsigned getNumIncoming() const override { return 1; }
2686
2687 /// Returns true if this induction is evaluated in a narrower type than the
2688 /// start value.
2689 bool isTruncated() const {
2690 return getStartValue() && getScalarType()->isIntegerTy() &&
2691 getScalarType()->getPrimitiveSizeInBits() <
2692 getStartValue()->getScalarType()->getPrimitiveSizeInBits();
2693 }
2694
2695 /// Return the cost of this VPWidenIntOrFpInductionRecipe.
2696 InstructionCost computeCost(ElementCount VF,
2697 VPCostContext &Ctx) const override;
2698
2699 /// Returns true if the induction is canonical, i.e. starting at 0 and
2700 /// incremented by UF * VF (= the original IV is incremented by 1) and has the
2701 /// same type as the canonical induction.
2702 bool isCanonical() const;
2703
2704 /// Returns the VPValue representing the value of this induction at
2705 /// the last unrolled part, if it exists. Returns itself if unrolling did not
2706 /// take place.
2707 VPValue *getLastUnrolledPartOperand() {
2708 return isUnrolled() ? getLastOperand() : this;
2709 }
2710
2711protected:
2712#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2713 /// Print the recipe.
2714 void printRecipe(raw_ostream &O, const Twine &Indent,
2715 VPSlotTracker &SlotTracker) const override;
2716#endif
2717};
2718
2719class VPWidenPointerInductionRecipe : public VPWidenInductionRecipe {
2720public:
2721 /// Create a new VPWidenPointerInductionRecipe for \p Phi with start value \p
2722 /// Start and the number of elements unrolled \p NumUnrolledElems, typically
2723 /// VF*UF.
2724 VPWidenPointerInductionRecipe(PHINode *Phi, VPValue *Start, VPValue *Step,
2725 VPValue *NumUnrolledElems,
2726 const InductionDescriptor &IndDesc, DebugLoc DL)
2727 : VPWidenInductionRecipe(VPRecipeBase::VPWidenPointerInductionSC, Phi,
2728 Start, Step, IndDesc, Start->getScalarType(),
2729 DL) {
2730 addOperand(Operand: NumUnrolledElems);
2731 }
2732
2733 ~VPWidenPointerInductionRecipe() override = default;
2734
2735 VPWidenPointerInductionRecipe *clone() override {
2736 return new VPWidenPointerInductionRecipe(
2737 cast<PHINode>(Val: getUnderlyingInstr()), getOperand(N: 0), getOperand(N: 1),
2738 getOperand(N: 2), getInductionDescriptor(), getDebugLoc());
2739 }
2740
2741 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenPointerInductionSC)
2742
2743 /// Generate vector values for the pointer induction.
2744 void execute(VPTransformState &State) override {
2745 llvm_unreachable("cannot execute this recipe, should be expanded via "
2746 "expandVPWidenPointerInduction");
2747 };
2748
2749 /// Returns true if only scalar values will be generated.
2750 bool onlyScalarsGenerated(bool IsScalable);
2751
2752 /// Return the cost of this VPWidenPointerInductionRecipe.
2753 InstructionCost computeCost(ElementCount VF,
2754 VPCostContext &Ctx) const override;
2755
2756protected:
2757#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2758 /// Print the recipe.
2759 void printRecipe(raw_ostream &O, const Twine &Indent,
2760 VPSlotTracker &SlotTracker) const override;
2761#endif
2762};
2763
2764/// A recipe for widened phis. Incoming values are operands of the recipe and
2765/// their operand index corresponds to the incoming predecessor block. If the
2766/// recipe is placed in an entry block to a (non-replicate) region, it must have
2767/// exactly 2 incoming values, the first from the predecessor of the region and
2768/// the second from the exiting block of the region.
2769class LLVM_ABI_FOR_TEST VPWidenPHIRecipe : public VPSingleDefRecipe,
2770 public VPPhiAccessors {
2771 /// Name to use for the generated IR instruction for the widened phi.
2772 std::string Name;
2773
2774public:
2775 /// Create a new VPWidenPHIRecipe with incoming values \p IncomingValues,
2776 /// debug location \p DL and \p Name.
2777 VPWidenPHIRecipe(ArrayRef<VPValue *> IncomingValues,
2778 DebugLoc DL = DebugLoc::getUnknown(), const Twine &Name = "")
2779 : VPSingleDefRecipe(VPRecipeBase::VPWidenPHISC, IncomingValues,
2780 IncomingValues[0]->getScalarType(),
2781 /*UV=*/nullptr, DL),
2782 Name(Name.str()) {
2783 assert(all_of(IncomingValues,
2784 [this](VPValue *VPV) {
2785 return VPV->getScalarType() == getScalarType();
2786 }) &&
2787 "all incoming values must have the same type");
2788 }
2789
2790 VPWidenPHIRecipe *clone() override {
2791 return new VPWidenPHIRecipe(operands(), getDebugLoc(), Name);
2792 }
2793
2794 ~VPWidenPHIRecipe() override = default;
2795
2796 /// This recipe generates a PHI.
2797 unsigned getOpcode() const { return Instruction::PHI; }
2798
2799 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenPHISC)
2800
2801 /// Generate the phi/select nodes.
2802 void execute(VPTransformState &State) override;
2803
2804 /// Return the cost of this VPWidenPHIRecipe.
2805 InstructionCost computeCost(ElementCount VF,
2806 VPCostContext &Ctx) const override;
2807
2808protected:
2809#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2810 /// Print the recipe.
2811 void printRecipe(raw_ostream &O, const Twine &Indent,
2812 VPSlotTracker &SlotTracker) const override;
2813#endif
2814
2815 const VPRecipeBase *getAsRecipe() const override { return this; }
2816};
2817
2818/// A recipe for handling first-order recurrence phis. The start value is the
2819/// first operand of the recipe and the incoming value from the backedge is the
2820/// second operand.
2821struct VPFirstOrderRecurrencePHIRecipe : public VPHeaderPHIRecipe {
2822 VPFirstOrderRecurrencePHIRecipe(PHINode *Phi, VPValue &Start,
2823 VPValue &BackedgeValue)
2824 : VPHeaderPHIRecipe(VPRecipeBase::VPFirstOrderRecurrencePHISC, Phi,
2825 &Start, Start.getScalarType()) {
2826 addOperand(Operand: &BackedgeValue);
2827 }
2828
2829 VP_CLASSOF_IMPL(VPRecipeBase::VPFirstOrderRecurrencePHISC)
2830
2831 VPFirstOrderRecurrencePHIRecipe *clone() override {
2832 return new VPFirstOrderRecurrencePHIRecipe(
2833 cast<PHINode>(Val: getUnderlyingInstr()), *getOperand(N: 0), *getOperand(N: 1));
2834 }
2835
2836 void execute(VPTransformState &State) override;
2837
2838 /// Return the cost of this first-order recurrence phi recipe.
2839 InstructionCost computeCost(ElementCount VF,
2840 VPCostContext &Ctx) const override;
2841
2842 /// Returns true if the recipe only uses the first lane of operand \p Op.
2843 bool usesFirstLaneOnly(const VPValue *Op) const override {
2844 assert(is_contained(operands(), Op) &&
2845 "Op must be an operand of the recipe");
2846 return Op == getStartValue();
2847 }
2848
2849protected:
2850#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2851 /// Print the recipe.
2852 void printRecipe(raw_ostream &O, const Twine &Indent,
2853 VPSlotTracker &SlotTracker) const override;
2854#endif
2855};
2856
2857/// Possible variants of a reduction.
2858
2859/// This reduction is ordered and in-loop.
2860struct RdxOrdered {};
2861/// This reduction is in-loop.
2862struct RdxInLoop {};
2863/// This reduction is unordered with the partial result scaled down by some
2864/// factor.
2865struct RdxUnordered {
2866 unsigned VFScaleFactor;
2867};
2868using ReductionStyle = std::variant<RdxOrdered, RdxInLoop, RdxUnordered>;
2869
2870inline ReductionStyle getReductionStyle(bool InLoop, bool Ordered,
2871 unsigned ScaleFactor) {
2872 assert((!Ordered || InLoop) && "Ordered implies in-loop");
2873 if (Ordered)
2874 return RdxOrdered{};
2875 if (InLoop)
2876 return RdxInLoop{};
2877 return RdxUnordered{/*VFScaleFactor=*/.VFScaleFactor: ScaleFactor};
2878}
2879
2880/// A recipe for handling reduction phis. The start value is the first operand
2881/// of the recipe and the incoming value from the backedge is the second
2882/// operand.
2883class VPReductionPHIRecipe : public VPHeaderPHIRecipe, public VPIRFlags {
2884 /// The recurrence kind of the reduction.
2885 const RecurKind Kind;
2886
2887 ReductionStyle Style;
2888
2889 /// The phi is part of a multi-use reduction (e.g., used in FindIV
2890 /// patterns for argmin/argmax).
2891 /// TODO: Also support cases where the phi itself has a single use, but its
2892 /// compare has multiple uses.
2893 bool HasUsesOutsideReductionChain;
2894
2895 /// Temporary flag indicating that the FindIV reduction expression has been
2896 /// sunk. While this is true, epilogue vectorization is disabled to avoid
2897 /// applying the sunk expression twice (once in the main vector loop and again
2898 /// in the epilogue), which can produce incorrect results by applying the sunk
2899 /// operation twice.
2900 /// TODO: Remove this flag once epilogue vectorization properly supports
2901 /// sunk FindIV expressions.
2902 bool ExpressionSunk = false;
2903
2904public:
2905 /// Create a new VPReductionPHIRecipe for the reduction \p Phi.
2906 VPReductionPHIRecipe(PHINode *Phi, RecurKind Kind, VPValue &Start,
2907 VPValue &BackedgeValue, ReductionStyle Style,
2908 const VPIRFlags &Flags,
2909 bool HasUsesOutsideReductionChain = false)
2910 : VPHeaderPHIRecipe(VPRecipeBase::VPReductionPHISC, Phi, &Start,
2911 Start.getScalarType()),
2912 VPIRFlags(Flags), Kind(Kind), Style(Style),
2913 HasUsesOutsideReductionChain(HasUsesOutsideReductionChain) {
2914 addOperand(Operand: &BackedgeValue);
2915 }
2916
2917 ~VPReductionPHIRecipe() override = default;
2918
2919 VPReductionPHIRecipe *cloneWithOperands(VPValue *Start,
2920 VPValue *BackedgeValue) {
2921 auto *Clone = new VPReductionPHIRecipe(
2922 dyn_cast_or_null<PHINode>(Val: getUnderlyingValue()), getRecurrenceKind(),
2923 *Start, *BackedgeValue, Style, *this, HasUsesOutsideReductionChain);
2924 Clone->ExpressionSunk = ExpressionSunk;
2925 return Clone;
2926 }
2927
2928 VPReductionPHIRecipe *clone() override {
2929 return cloneWithOperands(Start: getOperand(N: 0), BackedgeValue: getBackedgeValue());
2930 }
2931
2932 VP_CLASSOF_IMPL(VPRecipeBase::VPReductionPHISC)
2933
2934 /// Generate the phi/select nodes.
2935 void execute(VPTransformState &State) override;
2936
2937 /// Get the factor that the VF of this recipe's output should be scaled by, or
2938 /// 1 if it isn't scaled.
2939 unsigned getVFScaleFactor() const {
2940 auto *Partial = std::get_if<RdxUnordered>(ptr: &Style);
2941 return Partial ? Partial->VFScaleFactor : 1;
2942 }
2943
2944 /// Set the VFScaleFactor for this reduction phi. Can only be set to a factor
2945 /// > 1.
2946 void setVFScaleFactor(unsigned ScaleFactor) {
2947 assert(ScaleFactor > 1 && "must set to scale factor > 1");
2948 Style = RdxUnordered{.VFScaleFactor: ScaleFactor};
2949 }
2950
2951 /// Returns the recurrence kind of the reduction.
2952 RecurKind getRecurrenceKind() const { return Kind; }
2953
2954 /// Returns true, if the phi is part of an ordered reduction.
2955 bool isOrdered() const { return std::holds_alternative<RdxOrdered>(v: Style); }
2956
2957 /// Returns true if the phi is part of an in-loop reduction.
2958 bool isInLoop() const {
2959 return std::holds_alternative<RdxInLoop>(v: Style) ||
2960 std::holds_alternative<RdxOrdered>(v: Style);
2961 }
2962
2963 /// Returns true, if the phi is part of a multi-use reduction.
2964 bool hasUsesOutsideReductionChain() const {
2965 return HasUsesOutsideReductionChain;
2966 }
2967
2968 void setExpressionSunk() { ExpressionSunk = true; }
2969
2970 bool isExpressionSunk() const { return ExpressionSunk; }
2971
2972 /// Returns true if the recipe only uses the first lane of operand \p Op.
2973 bool usesFirstLaneOnly(const VPValue *Op) const override {
2974 assert(is_contained(operands(), Op) &&
2975 "Op must be an operand of the recipe");
2976 return isOrdered() || isInLoop();
2977 }
2978
2979protected:
2980#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2981 /// Print the recipe.
2982 void printRecipe(raw_ostream &O, const Twine &Indent,
2983 VPSlotTracker &SlotTracker) const override;
2984#endif
2985};
2986
2987/// A recipe for handling scalar conditional induction PHIs. The start value is
2988/// the first operand of the recipe and the incoming value from the backedge is
2989/// the second operand.
2990class VPConditionalInductionPHIRecipe : public VPHeaderPHIRecipe {
2991 const SCEV *StepSCEV = nullptr;
2992
2993public:
2994 VPConditionalInductionPHIRecipe(PHINode &Phi, VPValue &Start,
2995 VPValue &BackedgeValue, const SCEV *StepSCEV)
2996 : VPHeaderPHIRecipe(VPRecipeBase::VPConditionalInductionPHISC, &Phi,
2997 &Start, Start.getScalarType()),
2998 StepSCEV(StepSCEV) {
2999 addOperand(Operand: &BackedgeValue);
3000 }
3001
3002 ~VPConditionalInductionPHIRecipe() override = default;
3003
3004 /// Returns the underlying PHINode.
3005 PHINode *getPHINode() const { return cast<PHINode>(Val: getUnderlyingValue()); }
3006
3007 /// Returns the conditional induction step SCEV expression.
3008 const SCEV *getStepSCEV() const { return StepSCEV; }
3009
3010 VPConditionalInductionPHIRecipe *clone() override {
3011 return new VPConditionalInductionPHIRecipe(
3012 *getPHINode(), *getStartValue(), *getBackedgeValue(), getStepSCEV());
3013 }
3014
3015 VP_CLASSOF_IMPL(VPRecipeBase::VPConditionalInductionPHISC)
3016
3017 static inline bool classof(const VPHeaderPHIRecipe *R) {
3018 return R->getVPRecipeID() == VPRecipeBase::VPConditionalInductionPHISC;
3019 }
3020
3021 void execute(VPTransformState &) override {
3022 llvm_unreachable("must be expanded before final execute");
3023 }
3024
3025 InstructionCost computeCost(ElementCount VF,
3026 VPCostContext &Ctx) const override;
3027
3028#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3029 /// Print the recipe.
3030 void printRecipe(raw_ostream &O, const Twine &Indent,
3031 VPSlotTracker &SlotTracker) const override;
3032#endif
3033
3034 /// Returns true if the recipe only uses the first lane of operand \p Op.
3035 bool usesFirstLaneOnly(const VPValue *Op) const override {
3036 assert(is_contained(operands(), Op) &&
3037 "Op must be an operand of the recipe");
3038 return true;
3039 }
3040};
3041
3042/// A recipe for vectorizing a phi-node as a sequence of mask-based select
3043/// instructions.
3044class LLVM_ABI_FOR_TEST VPBlendRecipe : public VPRecipeWithIRFlags {
3045public:
3046 /// The blend operation is a User of the incoming values and of their
3047 /// respective masks, ordered [I0, M0, I1, M1, I2, M2, ...]. Note that M0 can
3048 /// be omitted (implied by passing an odd number of operands) in which case
3049 /// all other incoming values are merged into it.
3050 VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands,
3051 const VPIRFlags &Flags, DebugLoc DL)
3052 : VPRecipeWithIRFlags(VPRecipeBase::VPBlendSC, Operands,
3053 Operands[0]->getScalarType(), Flags, DL) {
3054 assert(Operands.size() >= 2 && "Expected at least two operands!");
3055 assert(all_of(seq<unsigned>(0, getNumIncomingValues()),
3056 [this](unsigned I) {
3057 return getIncomingValue(I)->getScalarType() ==
3058 getScalarType();
3059 }) &&
3060 "all incoming values must have the same type");
3061 assert(all_of(seq<unsigned>(isNormalized(), getNumIncomingValues()),
3062 [this](unsigned I) {
3063 return getMask(I)->getScalarType()->isIntegerTy(1);
3064 }) &&
3065 "masks must be a bool");
3066 assert(hasRequiredFlagsForOpcode(Instruction::PHI, getScalarType()) &&
3067 "blends require the flags of the phi they replace");
3068 setUnderlyingValue(Phi);
3069 }
3070
3071 VPBlendRecipe *clone() override { return cloneWithOperands(NewOperands: operands()); }
3072
3073 VPBlendRecipe *cloneWithOperands(ArrayRef<VPValue *> NewOperands) {
3074 return new VPBlendRecipe(cast_or_null<PHINode>(Val: getUnderlyingValue()),
3075 NewOperands, *this, getDebugLoc());
3076 }
3077
3078 VP_CLASSOF_IMPL(VPRecipeBase::VPBlendSC)
3079
3080 /// A normalized blend is one that has an odd number of operands, whereby the
3081 /// first operand does not have an associated mask.
3082 bool isNormalized() const { return getNumOperands() % 2; }
3083
3084 /// Return the number of incoming values, taking into account when normalized
3085 /// the first incoming value will have no mask.
3086 unsigned getNumIncomingValues() const {
3087 return (getNumOperands() + isNormalized()) / 2;
3088 }
3089
3090 /// Return incoming value number \p Idx.
3091 VPValue *getIncomingValue(unsigned Idx) const {
3092 return Idx == 0 ? getOperand(N: 0) : getOperand(N: Idx * 2 - isNormalized());
3093 }
3094
3095 /// Return mask number \p Idx.
3096 VPValue *getMask(unsigned Idx) const {
3097 assert((Idx > 0 || !isNormalized()) && "First index has no mask!");
3098 return Idx == 0 ? getOperand(N: 1) : getOperand(N: Idx * 2 + !isNormalized());
3099 }
3100
3101 /// Set mask number \p Idx to \p V.
3102 void setMask(unsigned Idx, VPValue *V) {
3103 assert((Idx > 0 || !isNormalized()) && "First index has no mask!");
3104 assert(V->getScalarType()->isIntegerTy(1) && "Mask must be an i1 (vector)");
3105 Idx == 0 ? setOperand(I: 1, New: V) : setOperand(I: Idx * 2 + !isNormalized(), New: V);
3106 }
3107
3108 void execute(VPTransformState &State) override {
3109 llvm_unreachable("VPBlendRecipe should be expanded by simplifyBlends");
3110 }
3111
3112 /// Return the cost of this VPWidenMemoryRecipe.
3113 InstructionCost computeCost(ElementCount VF,
3114 VPCostContext &Ctx) const override;
3115
3116 /// Returns true if the recipe only uses the first lane of operand \p Op.
3117 bool usesFirstLaneOnly(const VPValue *Op) const override;
3118
3119protected:
3120#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3121 /// Print the recipe.
3122 void printRecipe(raw_ostream &O, const Twine &Indent,
3123 VPSlotTracker &SlotTracker) const override;
3124#endif
3125};
3126
3127/// A common base class for interleaved memory operations.
3128/// An Interleaved memory operation is a memory access method that combines
3129/// multiple strided loads/stores into a single wide load/store with shuffles.
3130/// The first operand is the start address. The optional operands are, in order,
3131/// the stored values and the mask.
3132class LLVM_ABI_FOR_TEST VPInterleaveBase : public VPRecipeBase,
3133 public VPIRMetadata {
3134 const InterleaveGroup<Instruction> *IG;
3135
3136 /// Indicates if the interleave group is in a conditional block and requires a
3137 /// mask.
3138 bool HasMask = false;
3139
3140 /// Indicates if gaps between members of the group need to be masked out or if
3141 /// unusued gaps can be loaded speculatively.
3142 bool NeedsMaskForGaps = false;
3143
3144protected:
3145 VPInterleaveBase(VPRecipeTy SC, const InterleaveGroup<Instruction> *IG,
3146 ArrayRef<VPValue *> Operands,
3147 ArrayRef<VPValue *> StoredValues, VPValue *Mask,
3148 bool NeedsMaskForGaps, const VPIRMetadata &MD, DebugLoc DL)
3149 : VPRecipeBase(SC, Operands, DL), VPIRMetadata(MD), IG(IG),
3150 NeedsMaskForGaps(NeedsMaskForGaps) {
3151 // TODO: extend the masked interleaved-group support to reversed access.
3152 assert((!Mask || !IG->isReverse()) &&
3153 "Reversed masked interleave-group not supported.");
3154 if (StoredValues.empty()) {
3155 for (Instruction *Inst : IG->members()) {
3156 assert(!Inst->getType()->isVoidTy() && "must have result");
3157 new VPMultiDefValue(this, Inst, Inst->getType());
3158 }
3159 } else {
3160 for (auto *SV : StoredValues)
3161 addOperand(Operand: SV);
3162 }
3163 if (Mask) {
3164 HasMask = true;
3165 addOperand(Operand: Mask);
3166 }
3167 }
3168
3169public:
3170 VPInterleaveBase *clone() override = 0;
3171
3172 static inline bool classof(const VPRecipeBase *R) {
3173 return R->getVPRecipeID() == VPRecipeBase::VPInterleaveSC ||
3174 R->getVPRecipeID() == VPRecipeBase::VPInterleaveEVLSC;
3175 }
3176
3177 static inline bool classof(const VPUser *U) {
3178 auto *R = dyn_cast<VPRecipeBase>(Val: U);
3179 return R && classof(R);
3180 }
3181
3182 /// Return the address accessed by this recipe.
3183 VPValue *getAddr() const {
3184 return getOperand(N: 0); // Address is the 1st, mandatory operand.
3185 }
3186
3187 /// Return the mask used by this recipe. Note that a full mask is represented
3188 /// by a nullptr.
3189 VPValue *getMask() const {
3190 // Mask is optional and the last operand.
3191 return HasMask ? getLastOperand() : nullptr;
3192 }
3193
3194 /// Return true if the access needs a mask because of the gaps.
3195 bool needsMaskForGaps() const { return NeedsMaskForGaps; }
3196
3197 const InterleaveGroup<Instruction> *getInterleaveGroup() const { return IG; }
3198
3199 Instruction *getInsertPos() const { return IG->getInsertPos(); }
3200
3201 void execute(VPTransformState &State) override {
3202 llvm_unreachable("VPInterleaveBase should not be instantiated.");
3203 }
3204
3205 /// Return the cost of this recipe.
3206 InstructionCost computeCost(ElementCount VF,
3207 VPCostContext &Ctx) const override;
3208
3209 /// Returns true if the recipe only uses the first lane of operand \p Op.
3210 bool usesFirstLaneOnly(const VPValue *Op) const override = 0;
3211
3212 /// Returns the number of stored operands of this interleave group. Returns 0
3213 /// for load interleave groups.
3214 virtual unsigned getNumStoreOperands() const = 0;
3215
3216 /// Return the VPValues stored by this interleave group. If it is a load
3217 /// interleave group, return an empty ArrayRef.
3218 ArrayRef<VPValue *> getStoredValues() const {
3219 return {op_end() - (getNumStoreOperands() + (HasMask ? 1 : 0)),
3220 getNumStoreOperands()};
3221 }
3222};
3223
3224/// VPInterleaveRecipe is a recipe for transforming an interleave group of load
3225/// or stores into one wide load/store and shuffles. The first operand of a
3226/// VPInterleave recipe is the address, followed by the stored values, followed
3227/// by an optional mask.
3228class LLVM_ABI_FOR_TEST VPInterleaveRecipe final : public VPInterleaveBase {
3229public:
3230 VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr,
3231 ArrayRef<VPValue *> StoredValues, VPValue *Mask,
3232 bool NeedsMaskForGaps, const VPIRMetadata &MD, DebugLoc DL)
3233 : VPInterleaveBase(VPRecipeBase::VPInterleaveSC, IG, Addr, StoredValues,
3234 Mask, NeedsMaskForGaps, MD, DL) {}
3235
3236 ~VPInterleaveRecipe() override = default;
3237
3238 VPInterleaveRecipe *clone() override {
3239 return new VPInterleaveRecipe(getInterleaveGroup(), getAddr(),
3240 getStoredValues(), getMask(),
3241 needsMaskForGaps(), *this, getDebugLoc());
3242 }
3243
3244 VP_CLASSOF_IMPL(VPRecipeBase::VPInterleaveSC)
3245
3246 /// Generate the wide load or store, and shuffles.
3247 void execute(VPTransformState &State) override;
3248
3249 bool usesFirstLaneOnly(const VPValue *Op) const override {
3250 assert(is_contained(operands(), Op) &&
3251 "Op must be an operand of the recipe");
3252 return Op == getAddr() && !llvm::is_contained(Range: getStoredValues(), Element: Op);
3253 }
3254
3255 unsigned getNumStoreOperands() const override {
3256 return getNumOperands() - (getMask() ? 2 : 1);
3257 }
3258
3259protected:
3260#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3261 /// Print the recipe.
3262 void printRecipe(raw_ostream &O, const Twine &Indent,
3263 VPSlotTracker &SlotTracker) const override;
3264#endif
3265};
3266
3267/// A recipe for interleaved memory operations with vector-predication
3268/// intrinsics. The first operand is the address, the second operand is the
3269/// explicit vector length. Stored values and mask are optional operands.
3270class LLVM_ABI_FOR_TEST VPInterleaveEVLRecipe final : public VPInterleaveBase {
3271public:
3272 VPInterleaveEVLRecipe(VPInterleaveRecipe &R, VPValue &EVL, VPValue *Mask)
3273 : VPInterleaveBase(VPRecipeBase::VPInterleaveEVLSC,
3274 R.getInterleaveGroup(), {R.getAddr(), &EVL},
3275 R.getStoredValues(), Mask, R.needsMaskForGaps(), R,
3276 R.getDebugLoc()) {
3277 assert(!getInterleaveGroup()->isReverse() &&
3278 "Reversed interleave-group with tail folding is not supported.");
3279 assert(!needsMaskForGaps() && "Interleaved access with gap mask is not "
3280 "supported for scalable vector.");
3281 }
3282
3283 ~VPInterleaveEVLRecipe() override = default;
3284
3285 VPInterleaveEVLRecipe *clone() override {
3286 llvm_unreachable("cloning not implemented yet");
3287 }
3288
3289 VP_CLASSOF_IMPL(VPRecipeBase::VPInterleaveEVLSC)
3290
3291 /// The VPValue of the explicit vector length.
3292 VPValue *getEVL() const { return getOperand(N: 1); }
3293
3294 /// Generate the wide load or store, and shuffles.
3295 void execute(VPTransformState &State) override;
3296
3297 /// The recipe only uses the first lane of the address, and EVL operand.
3298 bool usesFirstLaneOnly(const VPValue *Op) const override {
3299 assert(is_contained(operands(), Op) &&
3300 "Op must be an operand of the recipe");
3301 return (Op == getAddr() && !llvm::is_contained(Range: getStoredValues(), Element: Op)) ||
3302 Op == getEVL();
3303 }
3304
3305 unsigned getNumStoreOperands() const override {
3306 return getNumOperands() - (getMask() ? 3 : 2);
3307 }
3308
3309protected:
3310#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3311 /// Print the recipe.
3312 void printRecipe(raw_ostream &O, const Twine &Indent,
3313 VPSlotTracker &SlotTracker) const override;
3314#endif
3315};
3316
3317/// A recipe to represent inloop, ordered or partial reduction operations. It
3318/// performs a reduction on a vector operand into a scalar (vector in the case
3319/// of a partial reduction) value, and adds the result to a chain. The Operands
3320/// are {ChainOp, VecOp, [Condition]}.
3321class LLVM_ABI_FOR_TEST VPReductionRecipe : public VPRecipeWithIRFlags {
3322
3323 /// The recurrence kind for the reduction in question.
3324 RecurKind RdxKind;
3325 /// Whether the reduction is conditional.
3326 bool IsConditional = false;
3327 ReductionStyle Style;
3328
3329protected:
3330 VPReductionRecipe(VPRecipeTy SC, RecurKind RdxKind, FastMathFlags FMFs,
3331 Instruction *I, ArrayRef<VPValue *> Operands,
3332 VPValue *CondOp, ReductionStyle Style, DebugLoc DL)
3333 : VPRecipeWithIRFlags(SC, Operands, Operands[0]->getScalarType(), FMFs,
3334 DL),
3335 RdxKind(RdxKind), Style(Style) {
3336 assert(all_of(Operands,
3337 [this](VPValue *VPV) {
3338 return VPV->getScalarType() == getScalarType() ||
3339 (isa<VPInstruction>(VPV) &&
3340 cast<VPInstruction>(VPV)->getOpcode() ==
3341 VPInstruction::ExplicitVectorLength);
3342 }) &&
3343 "all incoming values must have the same type");
3344 if (CondOp) {
3345 assert(CondOp->getScalarType()->isIntegerTy(1) &&
3346 "CondOp must be a bool");
3347 IsConditional = true;
3348 addOperand(Operand: CondOp);
3349 }
3350 setUnderlyingValue(I);
3351 }
3352
3353public:
3354 VPReductionRecipe(RecurKind RdxKind, FastMathFlags FMFs, Instruction *I,
3355 VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,
3356 ReductionStyle Style, DebugLoc DL = DebugLoc::getUnknown())
3357 : VPReductionRecipe(VPRecipeBase::VPReductionSC, RdxKind, FMFs, I,
3358 {ChainOp, VecOp}, CondOp, Style, DL) {}
3359
3360 VPReductionRecipe(const RecurKind RdxKind, FastMathFlags FMFs,
3361 VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,
3362 ReductionStyle Style, DebugLoc DL = DebugLoc::getUnknown())
3363 : VPReductionRecipe(VPRecipeBase::VPReductionSC, RdxKind, FMFs, nullptr,
3364 {ChainOp, VecOp}, CondOp, Style, DL) {}
3365
3366 ~VPReductionRecipe() override = default;
3367
3368 VPReductionRecipe *clone() override {
3369 return new VPReductionRecipe(RdxKind, getFastMathFlagsOrNone(),
3370 getUnderlyingInstr(), getChainOp(), getVecOp(),
3371 getCondOp(), Style, getDebugLoc());
3372 }
3373
3374 static inline bool classof(const VPRecipeBase *R) {
3375 return R->getVPRecipeID() == VPRecipeBase::VPReductionSC ||
3376 R->getVPRecipeID() == VPRecipeBase::VPReductionEVLSC;
3377 }
3378
3379 static inline bool classof(const VPUser *U) {
3380 auto *R = dyn_cast<VPRecipeBase>(Val: U);
3381 return R && classof(R);
3382 }
3383
3384 static inline bool classof(const VPValue *VPV) {
3385 const VPRecipeBase *R = VPV->getDefiningRecipe();
3386 return R && classof(R);
3387 }
3388
3389 static inline bool classof(const VPSingleDefRecipe *R) {
3390 return classof(R: static_cast<const VPRecipeBase *>(R));
3391 }
3392
3393 /// Generate the reduction in the loop.
3394 void execute(VPTransformState &State) override;
3395
3396 /// Return the cost of VPReductionRecipe.
3397 InstructionCost computeCost(ElementCount VF,
3398 VPCostContext &Ctx) const override;
3399
3400 /// Return the recurrence kind for the in-loop reduction.
3401 RecurKind getRecurrenceKind() const { return RdxKind; }
3402 /// Return true if the in-loop reduction is ordered.
3403 bool isOrdered() const { return std::holds_alternative<RdxOrdered>(v: Style); };
3404 /// Return true if the in-loop reduction is conditional.
3405 bool isConditional() const { return IsConditional; };
3406 /// Returns true if the reduction outputs a vector with a scaled down VF.
3407 bool isPartialReduction() const {
3408 return std::holds_alternative<RdxUnordered>(v: Style);
3409 }
3410 /// Returns true if the reduction is in-loop.
3411 bool isInLoop() const {
3412 return std::holds_alternative<RdxInLoop>(v: Style) ||
3413 std::holds_alternative<RdxOrdered>(v: Style);
3414 }
3415 /// The VPValue of the scalar Chain being accumulated.
3416 VPValue *getChainOp() const { return getOperand(N: 0); }
3417 /// The VPValue of the vector value to be reduced.
3418 VPValue *getVecOp() const { return getOperand(N: 1); }
3419 /// The VPValue of the condition for the block.
3420 VPValue *getCondOp() const {
3421 return isConditional() ? getLastOperand() : nullptr;
3422 }
3423 /// Get the factor that the VF of this recipe's output should be scaled by, or
3424 /// 1 if it isn't scaled.
3425 unsigned getVFScaleFactor() const {
3426 auto *Partial = std::get_if<RdxUnordered>(ptr: &Style);
3427 return Partial ? Partial->VFScaleFactor : 1;
3428 }
3429
3430protected:
3431#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3432 /// Print the recipe.
3433 void printRecipe(raw_ostream &O, const Twine &Indent,
3434 VPSlotTracker &SlotTracker) const override;
3435#endif
3436};
3437
3438/// A recipe to represent inloop reduction operations with vector-predication
3439/// intrinsics, performing a reduction on a vector operand with the explicit
3440/// vector length (EVL) into a scalar value, and adding the result to a chain.
3441/// The Operands are {ChainOp, VecOp, EVL, [Condition]}.
3442class LLVM_ABI_FOR_TEST VPReductionEVLRecipe : public VPReductionRecipe {
3443public:
3444 VPReductionEVLRecipe(VPReductionRecipe &R, VPValue &EVL, VPValue *CondOp,
3445 DebugLoc DL = DebugLoc::getUnknown())
3446 : VPReductionRecipe(VPRecipeBase::VPReductionEVLSC, R.getRecurrenceKind(),
3447 R.getFastMathFlagsOrNone(),
3448 cast_or_null<Instruction>(Val: R.getUnderlyingValue()),
3449 {R.getChainOp(), R.getVecOp(), &EVL}, CondOp,
3450 getReductionStyle(InLoop: R.isInLoop(), Ordered: R.isOrdered(),
3451 ScaleFactor: R.getVFScaleFactor()),
3452 DL) {}
3453
3454 ~VPReductionEVLRecipe() override = default;
3455
3456 VPReductionEVLRecipe *clone() override {
3457 llvm_unreachable("cloning not implemented yet");
3458 }
3459
3460 VP_CLASSOF_IMPL(VPRecipeBase::VPReductionEVLSC)
3461
3462 /// Generate the reduction in the loop
3463 void execute(VPTransformState &State) override;
3464
3465 /// The VPValue of the explicit vector length.
3466 VPValue *getEVL() const { return getOperand(N: 2); }
3467
3468 /// Returns true if the recipe only uses the first lane of operand \p Op.
3469 bool usesFirstLaneOnly(const VPValue *Op) const override {
3470 assert(is_contained(operands(), Op) &&
3471 "Op must be an operand of the recipe");
3472 return Op == getEVL();
3473 }
3474
3475protected:
3476#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3477 /// Print the recipe.
3478 void printRecipe(raw_ostream &O, const Twine &Indent,
3479 VPSlotTracker &SlotTracker) const override;
3480#endif
3481};
3482
3483/// VPReplicateRecipe replicates a given instruction producing multiple scalar
3484/// copies of the original scalar type, one per lane, instead of producing a
3485/// single copy of widened type for all lanes. If the instruction is known to be
3486/// a single scalar, only one copy will be generated.
3487class LLVM_ABI_FOR_TEST VPReplicateRecipe : public VPRecipeWithIRFlags,
3488 public VPIRMetadata {
3489 /// Indicator if only a single replica per lane is needed.
3490 bool IsSingleScalar;
3491
3492 /// Indicator if the replicas are also predicated.
3493 bool IsPredicated;
3494
3495public:
3496 VPReplicateRecipe(Instruction *I, ArrayRef<VPValue *> Operands,
3497 bool IsSingleScalar, VPValue *Mask = nullptr,
3498 const VPIRFlags &Flags = {}, VPIRMetadata Metadata = {},
3499 DebugLoc DL = DebugLoc::getUnknown())
3500 : VPRecipeWithIRFlags(VPRecipeBase::VPReplicateSC, Operands,
3501 computeScalarType(I, Operands), Flags, DL),
3502 VPIRMetadata(Metadata), IsSingleScalar(IsSingleScalar),
3503 IsPredicated(Mask) {
3504 assert((!IsSingleScalar || !I->isCast()) &&
3505 "Single-scalar casts should use VPInstruction");
3506 setUnderlyingValue(I);
3507 if (Mask)
3508 addOperand(Operand: Mask);
3509 }
3510
3511 ~VPReplicateRecipe() override = default;
3512
3513 /// Compute the scalar result type for a VPReplicateRecipe wrapping \p I with
3514 /// \p Operands (excluding any predicate mask).
3515 static Type *computeScalarType(const Instruction *I,
3516 ArrayRef<VPValue *> Operands);
3517
3518 VPReplicateRecipe *clone() override { return cloneWithOperands(NewOperands: operands()); }
3519
3520 VPReplicateRecipe *cloneWithOperands(ArrayRef<VPValue *> NewOperands) {
3521 return new VPReplicateRecipe(
3522 getUnderlyingInstr(), NewOperands, IsSingleScalar,
3523 isPredicated() ? getMask() : nullptr, *this, *this, getDebugLoc());
3524 }
3525
3526 VP_CLASSOF_IMPL(VPRecipeBase::VPReplicateSC)
3527
3528 /// Generate replicas of the desired Ingredient. Replicas will be generated
3529 /// for all parts and lanes unless a specific part and lane are specified in
3530 /// the \p State.
3531 void execute(VPTransformState &State) override;
3532
3533 /// Return the cost of this VPReplicateRecipe.
3534 InstructionCost computeCost(ElementCount VF,
3535 VPCostContext &Ctx) const override;
3536
3537 /// Return the cost of scalarizing a call to \p CalledFn with argument
3538 /// operands \p ArgOps for a given \p VF.
3539 static InstructionCost computeCallCost(Function *CalledFn, Type *ResultTy,
3540 ArrayRef<const VPValue *> ArgOps,
3541 bool IsSingleScalar, ElementCount VF,
3542 VPCostContext &Ctx);
3543
3544 /// Returns true if the recipe produces a single scalar value.
3545 bool isSingleScalar() const { return IsSingleScalar; }
3546
3547 /// Returns true if the recipe produces scalar values for all VF lanes.
3548 bool doesGeneratePerAllLanes() const { return !IsSingleScalar; }
3549
3550 bool isPredicated() const { return IsPredicated; }
3551
3552 /// Returns true if the recipe only uses the first lane of operand \p Op.
3553 bool usesFirstLaneOnly(const VPValue *Op) const override {
3554 assert(is_contained(operands(), Op) &&
3555 "Op must be an operand of the recipe");
3556 return isSingleScalar();
3557 }
3558
3559 /// Returns true if the recipe uses scalars of operand \p Op.
3560 bool usesScalars(const VPValue *Op) const override {
3561 assert(is_contained(operands(), Op) &&
3562 "Op must be an operand of the recipe");
3563 return true;
3564 }
3565
3566 /// Return the mask of a predicated VPReplicateRecipe.
3567 VPValue *getMask() {
3568 assert(isPredicated() && "Trying to get the mask of a unpredicated recipe");
3569 return getLastOperand();
3570 }
3571
3572 /// Return the recipe's operands, excluding the mask of a predicated recipe.
3573 operand_range operandsWithoutMask() {
3574 return isPredicated() ? drop_end(RangeOrContainer: operands()) : operands();
3575 }
3576
3577 /// Returns the number of operands, excluding the mask if the recipe is
3578 /// predicated.
3579 unsigned getNumOperandsWithoutMask() const {
3580 return getNumOperands() - isPredicated();
3581 }
3582
3583 unsigned getOpcode() const { return getUnderlyingInstr()->getOpcode(); }
3584
3585protected:
3586#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3587 /// Print the recipe.
3588 void printRecipe(raw_ostream &O, const Twine &Indent,
3589 VPSlotTracker &SlotTracker) const override;
3590#endif
3591};
3592
3593/// A recipe for generating conditional branches on the bits of a mask.
3594class LLVM_ABI_FOR_TEST VPBranchOnMaskRecipe : public VPRecipeBase,
3595 public VPIRMetadata {
3596public:
3597 VPBranchOnMaskRecipe(VPValue *BlockInMask, DebugLoc DL,
3598 const VPIRMetadata &Metadata = {})
3599 : VPRecipeBase(VPRecipeBase::VPBranchOnMaskSC, {BlockInMask}, DL),
3600 VPIRMetadata(Metadata) {}
3601
3602 VPBranchOnMaskRecipe *clone() override {
3603 return new VPBranchOnMaskRecipe(getOperand(N: 0), getDebugLoc(), *this);
3604 }
3605
3606 VP_CLASSOF_IMPL(VPRecipeBase::VPBranchOnMaskSC)
3607
3608 /// Generate the extraction of the appropriate bit from the block mask and the
3609 /// conditional branch.
3610 void execute(VPTransformState &State) override;
3611
3612 /// Return the cost of this VPBranchOnMaskRecipe.
3613 InstructionCost computeCost(ElementCount VF,
3614 VPCostContext &Ctx) const override;
3615
3616#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3617 /// Print the recipe.
3618 void printRecipe(raw_ostream &O, const Twine &Indent,
3619 VPSlotTracker &SlotTracker) const override {
3620 O << Indent << "BRANCH-ON-MASK ";
3621 printOperands(O, SlotTracker);
3622 }
3623#endif
3624
3625 /// Returns true if the recipe uses scalars of operand \p Op.
3626 bool usesScalars(const VPValue *Op) const override {
3627 assert(is_contained(operands(), Op) &&
3628 "Op must be an operand of the recipe");
3629 return true;
3630 }
3631};
3632
3633/// A recipe to combine multiple recipes into a single 'expression' recipe,
3634/// which should be considered a single entity for cost-modeling and transforms.
3635/// The recipe needs to be 'decomposed', i.e. replaced by its individual
3636/// expression recipes, before execute. The individual expression recipes are
3637/// completely disconnected from the def-use graph of other recipes not part of
3638/// the expression. Def-use edges between pairs of expression recipes remain
3639/// intact, whereas every edge between an expression recipe and a recipe outside
3640/// the expression is elevated to connect the non-expression recipe with the
3641/// VPExpressionRecipe itself.
3642class VPExpressionRecipe : public VPSingleDefRecipe {
3643 /// Recipes included in this VPExpressionRecipe. This could contain
3644 /// duplicates.
3645 SmallVector<VPSingleDefRecipe *> ExpressionRecipes;
3646
3647 /// Temporary VPValues used for external operands of the expression, i.e.
3648 /// operands not defined by recipes in the expression.
3649 SmallVector<VPValue *> LiveInPlaceholders;
3650
3651 enum class ExpressionTypes {
3652 /// Represents an inloop extended reduction operation, performing a
3653 /// reduction on an extended vector operand into a scalar value, and adding
3654 /// the result to a chain.
3655 ExtendedReduction,
3656 /// Represents an inloop extended reduction operation, which is negated,
3657 /// then reduced before adding the result to a chain.
3658 NegatedExtendedReduction,
3659 /// Represent an inloop multiply-accumulate reduction, multiplying the
3660 /// extended vector operands, performing a reduction.add on the result, and
3661 /// adding the scalar result to a chain.
3662 ExtMulAccReduction,
3663 /// Represent an inloop multiply-accumulate reduction, multiplying the
3664 /// vector operands, performing a reduction.add on the result, and adding
3665 /// the scalar result to a chain.
3666 MulAccReduction,
3667 /// Represent an inloop multiply-accumulate reduction, multiplying the
3668 /// extended vector operands, negating the multiplication, performing a
3669 /// reduction.add on the result, and adding the scalar result to a chain.
3670 ExtNegatedMulAccReduction,
3671 /// Represent a chain of recipes whose last recipe will be optimized away.
3672 /// Currently only supports folding vp.merge with an in-loop operation, so
3673 /// LV does not account for the cost or register pressure of vp.merge.
3674 FoldedVPMerge,
3675 };
3676
3677 /// Type of the expression.
3678 ExpressionTypes ExpressionType;
3679
3680public:
3681 /// Construct a new VPExpressionRecipe by internalizing recipes in \p
3682 /// ExpressionRecipes. External operands (i.e. not defined by another recipe
3683 /// in the expression) are replaced by temporary VPValues and the original
3684 /// operands are transferred to the VPExpressionRecipe itself. Clone recipes
3685 /// as needed (excluding last) to ensure they are only used by other recipes
3686 /// in the expression.
3687 VPExpressionRecipe(ExpressionTypes ExpressionType,
3688 ArrayRef<VPSingleDefRecipe *> ExpressionRecipes);
3689
3690 VPExpressionRecipe(VPWidenCastRecipe *Ext, VPReductionRecipe *Red)
3691 : VPExpressionRecipe(ExpressionTypes::ExtendedReduction, {Ext, Red}) {}
3692 VPExpressionRecipe(VPWidenCastRecipe *Ext, VPWidenRecipe *Neg,
3693 VPReductionRecipe *Red)
3694 : VPExpressionRecipe(ExpressionTypes::NegatedExtendedReduction,
3695 {Ext, Neg, Red}) {
3696 assert((Red->getRecurrenceKind() == RecurKind::Add ||
3697 Red->getRecurrenceKind() == RecurKind::FAdd ||
3698 Red->getRecurrenceKind() == RecurKind::AddChainWithSubs) &&
3699 "Expected an add or add-chain-with-subs reduction");
3700 if (Neg->getOpcode() == Instruction::Sub) {
3701 [[maybe_unused]] auto *SubConst = dyn_cast<VPConstantInt>(Val: getOperand(N: 1));
3702 assert(SubConst && SubConst->isZero() && "Expected a negating sub");
3703 } else
3704 assert(Neg->getOpcode() == Instruction::FNeg && "Unexpected opcode");
3705 }
3706 VPExpressionRecipe(VPWidenRecipe *Mul, VPReductionRecipe *Red)
3707 : VPExpressionRecipe(ExpressionTypes::MulAccReduction, {Mul, Red}) {}
3708 VPExpressionRecipe(VPWidenCastRecipe *Ext0, VPWidenCastRecipe *Ext1,
3709 VPWidenRecipe *Mul, VPReductionRecipe *Red)
3710 : VPExpressionRecipe(ExpressionTypes::ExtMulAccReduction,
3711 {Ext0, Ext1, Mul, Red}) {}
3712 VPExpressionRecipe(VPWidenCastRecipe *Ext0, VPWidenCastRecipe *Ext1,
3713 VPWidenRecipe *Mul, VPWidenRecipe *Neg,
3714 VPReductionRecipe *Red)
3715 : VPExpressionRecipe(ExpressionTypes::ExtNegatedMulAccReduction,
3716 {Ext0, Ext1, Mul, Neg, Red}) {
3717 assert((Mul->getOpcode() == Instruction::Mul ||
3718 Mul->getOpcode() == Instruction::FMul) &&
3719 "Expected a mul");
3720 assert((Red->getRecurrenceKind() == RecurKind::Add ||
3721 Red->getRecurrenceKind() == RecurKind::FAdd ||
3722 Red->getRecurrenceKind() == RecurKind::AddChainWithSubs) &&
3723 "Expected an add or add-chain-with-subs reduction");
3724 assert(getNumOperands() >= 3 && "Expected at least three operands");
3725 if (Neg->getOpcode() == Instruction::Sub) {
3726 [[maybe_unused]] auto *SubConst = dyn_cast<VPConstantInt>(Val: getOperand(N: 2));
3727 assert(SubConst && SubConst->isZero() &&
3728 Neg->getOpcode() == Instruction::Sub && "Expected a negating sub");
3729 } else
3730 assert(Neg->getOpcode() == Instruction::FNeg && "Unexpected opcode");
3731 }
3732 VPExpressionRecipe(VPSingleDefRecipe *InLoopOp,
3733 VPWidenIntrinsicRecipe *VPMerge)
3734 : VPExpressionRecipe(ExpressionTypes::FoldedVPMerge,
3735 {InLoopOp, VPMerge}) {
3736 assert(VPMerge->getVectorIntrinsicID() == Intrinsic::vp_merge &&
3737 "Expected a vp.merge");
3738 }
3739
3740 ~VPExpressionRecipe() override {
3741 SmallPtrSet<VPSingleDefRecipe *, 4> ExpressionRecipesSeen;
3742 for (auto *R : reverse(C&: ExpressionRecipes)) {
3743 if (ExpressionRecipesSeen.insert(Ptr: R).second)
3744 delete R;
3745 }
3746 for (VPValue *T : LiveInPlaceholders)
3747 delete T;
3748 }
3749
3750 VP_CLASSOF_IMPL(VPRecipeBase::VPExpressionSC)
3751
3752 VPExpressionRecipe *clone() override {
3753 assert(!ExpressionRecipes.empty() && "empty expressions should be removed");
3754 SmallVector<VPSingleDefRecipe *> NewExpressiondRecipes;
3755 for (auto *R : ExpressionRecipes)
3756 NewExpressiondRecipes.push_back(Elt: R->clone());
3757 for (auto *New : NewExpressiondRecipes) {
3758 for (const auto &[Idx, Old] : enumerate(First&: ExpressionRecipes))
3759 New->replaceUsesOfWith(From: Old, To: NewExpressiondRecipes[Idx]);
3760 // Update placeholder operands in the cloned recipe to use the external
3761 // operands, to be internalized when the cloned expression is constructed.
3762 for (const auto &[Placeholder, OutsideOp] :
3763 zip(t&: LiveInPlaceholders, u: operands()))
3764 New->replaceUsesOfWith(From: Placeholder, To: OutsideOp);
3765 }
3766 return new VPExpressionRecipe(ExpressionType, NewExpressiondRecipes);
3767 }
3768
3769 /// Return and insert the recipes of the expression back into the VPlan,
3770 /// directly before the current recipe. Leaves the expression recipe empty,
3771 /// which must be removed before codegen.
3772 SmallVector<VPSingleDefRecipe *> decompose();
3773
3774 /// Returns the expression type of this recipe.
3775 ExpressionTypes getExpressionType() const { return ExpressionType; }
3776
3777 unsigned getVFScaleFactor() const {
3778 auto *PR = dyn_cast<VPReductionRecipe>(Val: ExpressionRecipes.back());
3779 return PR ? PR->getVFScaleFactor() : 1;
3780 }
3781
3782 /// Method for generating code, must not be called as this recipe is abstract.
3783 void execute(VPTransformState &State) override {
3784 llvm_unreachable("recipe must be removed before execute");
3785 }
3786
3787 InstructionCost computeCost(ElementCount VF,
3788 VPCostContext &Ctx) const override;
3789
3790 /// Returns true if the recipe only uses the first lane of operand \p Op.
3791 bool usesFirstLaneOnly(const VPValue *Op) const override;
3792
3793 /// Returns true if this expression contains recipes that may read from or
3794 /// write to memory.
3795 bool mayReadOrWriteMemory() const;
3796
3797 /// Returns true if this expression contains recipes that may have side
3798 /// effects.
3799 bool mayHaveSideEffects() const;
3800
3801 /// Returns true if this VPExpressionRecipe produces a single scalar.
3802 bool isVectorToScalar() const;
3803
3804protected:
3805#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3806 /// Print the recipe.
3807 void printRecipe(raw_ostream &O, const Twine &Indent,
3808 VPSlotTracker &SlotTracker) const override;
3809#endif
3810};
3811
3812/// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
3813/// control converges back from a Branch-on-Mask. The phi nodes are needed in
3814/// order to merge values that are set under such a branch and feed their uses.
3815/// The phi nodes can be scalar or vector depending on the users of the value.
3816/// This recipe works in concert with VPBranchOnMaskRecipe.
3817class LLVM_ABI_FOR_TEST VPPredInstPHIRecipe : public VPSingleDefRecipe {
3818public:
3819 /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
3820 /// nodes after merging back from a Branch-on-Mask.
3821 VPPredInstPHIRecipe(VPValue *PredV, DebugLoc DL)
3822 : VPSingleDefRecipe(VPRecipeBase::VPPredInstPHISC, PredV,
3823 PredV->getScalarType(), /*UV=*/nullptr, DL) {}
3824 ~VPPredInstPHIRecipe() override = default;
3825
3826 VPPredInstPHIRecipe *clone() override {
3827 return new VPPredInstPHIRecipe(getOperand(N: 0), getDebugLoc());
3828 }
3829
3830 VP_CLASSOF_IMPL(VPRecipeBase::VPPredInstPHISC)
3831
3832 /// Generates phi nodes for live-outs (from a replicate region) as needed to
3833 /// retain SSA form.
3834 void execute(VPTransformState &State) override;
3835
3836 /// Return the cost of this VPPredInstPHIRecipe.
3837 InstructionCost computeCost(ElementCount VF,
3838 VPCostContext &Ctx) const override {
3839 // TODO: Compute accurate cost after retiring the legacy cost model.
3840 return 0;
3841 }
3842
3843protected:
3844#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3845 /// Print the recipe.
3846 void printRecipe(raw_ostream &O, const Twine &Indent,
3847 VPSlotTracker &SlotTracker) const override;
3848#endif
3849};
3850
3851/// A common mixin class for widening memory operations. An optional mask can be
3852/// provided as the last operand.
3853class LLVM_ABI_FOR_TEST VPWidenMemoryRecipe : public VPIRMetadata {
3854protected:
3855 Instruction &Ingredient;
3856
3857 /// Alignment information for this memory access.
3858 Align Alignment;
3859
3860 /// Whether the accessed addresses are consecutive.
3861 bool Consecutive;
3862
3863 /// Whether the memory access is masked.
3864 bool IsMasked = false;
3865
3866 void setMask(VPValue *Mask) {
3867 assert(!IsMasked && "cannot re-set mask");
3868 if (!Mask)
3869 return;
3870 assert(Mask->getScalarType()->isIntegerTy(1) &&
3871 "Mask must be an i1 (vector)");
3872 getAsRecipe()->addOperand(Operand: Mask);
3873 IsMasked = true;
3874 }
3875
3876 VPWidenMemoryRecipe(Instruction &I, Align Alignment, bool Consecutive,
3877 const VPIRMetadata &Metadata)
3878 : VPIRMetadata(Metadata), Ingredient(I), Alignment(Alignment),
3879 Consecutive(Consecutive) {}
3880
3881public:
3882 virtual ~VPWidenMemoryRecipe() = default;
3883
3884 /// Return a VPRecipeBase* to the current object.
3885 virtual VPRecipeBase *getAsRecipe() = 0;
3886 virtual const VPRecipeBase *getAsRecipe() const = 0;
3887
3888 /// Return whether the loaded-from / stored-to addresses are consecutive.
3889 bool isConsecutive() const { return Consecutive; }
3890
3891 /// Return the address accessed by this recipe.
3892 VPValue *getAddr() const { return getAsRecipe()->getOperand(N: 0); }
3893
3894 /// Returns true if the recipe is masked.
3895 bool isMasked() const { return IsMasked; }
3896
3897 /// Return the mask used by this recipe. Note that a full mask is represented
3898 /// by a nullptr.
3899 VPValue *getMask() const {
3900 // Mask is optional and therefore the last operand.
3901 const VPRecipeBase *R = getAsRecipe();
3902 return isMasked() ? R->getLastOperand() : nullptr;
3903 }
3904
3905 /// Returns the alignment of the memory access.
3906 Align getAlign() const { return Alignment; }
3907
3908 /// Return the cost of this VPWidenMemoryRecipe.
3909 InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const;
3910
3911 Instruction &getIngredient() const { return Ingredient; }
3912};
3913
3914/// A recipe for widening load operations, using the address to load from and an
3915/// optional mask.
3916struct LLVM_ABI_FOR_TEST VPWidenLoadRecipe final : public VPSingleDefRecipe,
3917 public VPWidenMemoryRecipe {
3918 VPWidenLoadRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask,
3919 bool Consecutive, Align Alignment,
3920 const VPIRMetadata &Metadata, DebugLoc DL)
3921 : VPSingleDefRecipe(VPRecipeBase::VPWidenLoadSC, {Addr}, Load.getType(),
3922 &Load, DL),
3923 VPWidenMemoryRecipe(Load, Alignment, Consecutive, Metadata) {
3924 setMask(Mask);
3925 }
3926
3927 VPWidenLoadRecipe *clone() override {
3928 return new VPWidenLoadRecipe(cast<LoadInst>(Val&: Ingredient), getAddr(),
3929 getMask(), Consecutive, getAlign(), *this,
3930 getDebugLoc());
3931 }
3932
3933 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenLoadSC);
3934
3935 /// Returns the opcode of the widened load.
3936 unsigned getOpcode() const { return Instruction::Load; }
3937
3938 /// Generate a wide load or gather.
3939 void execute(VPTransformState &State) override;
3940
3941 /// Return the cost of this VPWidenLoadRecipe.
3942 InstructionCost computeCost(ElementCount VF,
3943 VPCostContext &Ctx) const override {
3944 return VPWidenMemoryRecipe::computeCost(VF, Ctx);
3945 }
3946
3947 /// Returns true if the recipe only uses the first lane of operand \p Op.
3948 bool usesFirstLaneOnly(const VPValue *Op) const override {
3949 assert(is_contained(operands(), Op) &&
3950 "Op must be an operand of the recipe");
3951 // Widened, consecutive loads operations only demand the first lane of
3952 // their address.
3953 return Op == getAddr() && isConsecutive();
3954 }
3955
3956protected:
3957 VPRecipeBase *getAsRecipe() override;
3958 const VPRecipeBase *getAsRecipe() const override;
3959
3960#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3961 /// Print the recipe.
3962 void printRecipe(raw_ostream &O, const Twine &Indent,
3963 VPSlotTracker &SlotTracker) const override;
3964#endif
3965};
3966
3967/// A recipe for widening load operations with vector-predication intrinsics,
3968/// using the address to load from, the explicit vector length and an optional
3969/// mask.
3970struct LLVM_ABI_FOR_TEST VPWidenLoadEVLRecipe final
3971 : public VPSingleDefRecipe,
3972 public VPWidenMemoryRecipe {
3973 VPWidenLoadEVLRecipe(VPWidenLoadRecipe &L, VPValue *Addr, VPValue &EVL,
3974 VPValue *Mask)
3975 : VPSingleDefRecipe(VPRecipeBase::VPWidenLoadEVLSC, {Addr, &EVL},
3976 L.getIngredient().getType(), &L.getIngredient(),
3977 L.getDebugLoc()),
3978 VPWidenMemoryRecipe(L.getIngredient(), L.getAlign(), L.isConsecutive(),
3979 L) {
3980 setMask(Mask);
3981 }
3982
3983 VPWidenLoadEVLRecipe *clone() override {
3984 llvm_unreachable("cloning not supported");
3985 }
3986
3987 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenLoadEVLSC)
3988
3989 /// Returns the opcode of the widened load.
3990 unsigned getOpcode() const { return Instruction::Load; }
3991
3992 /// Return the EVL operand.
3993 VPValue *getEVL() const { return getOperand(N: 1); }
3994
3995 /// Generate the wide load or gather.
3996 void execute(VPTransformState &State) override;
3997
3998 /// Return the cost of this VPWidenLoadEVLRecipe.
3999 InstructionCost computeCost(ElementCount VF,
4000 VPCostContext &Ctx) const override;
4001
4002 /// Returns true if the recipe only uses the first lane of operand \p Op.
4003 bool usesFirstLaneOnly(const VPValue *Op) const override {
4004 assert(is_contained(operands(), Op) &&
4005 "Op must be an operand of the recipe");
4006 // Widened loads only demand the first lane of EVL and consecutive loads
4007 // only demand the first lane of their address.
4008 return Op == getEVL() || (Op == getAddr() && isConsecutive());
4009 }
4010
4011protected:
4012 VPRecipeBase *getAsRecipe() override;
4013 const VPRecipeBase *getAsRecipe() const override;
4014
4015#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4016 /// Print the recipe.
4017 void printRecipe(raw_ostream &O, const Twine &Indent,
4018 VPSlotTracker &SlotTracker) const override;
4019#endif
4020};
4021
4022/// A recipe for widening store operations, using the stored value, the address
4023/// to store to and an optional mask.
4024struct LLVM_ABI_FOR_TEST VPWidenStoreRecipe final : public VPRecipeBase,
4025 public VPWidenMemoryRecipe {
4026 VPWidenStoreRecipe(StoreInst &Store, VPValue *Addr, VPValue *StoredVal,
4027 VPValue *Mask, bool Consecutive, Align Alignment,
4028 const VPIRMetadata &Metadata, DebugLoc DL)
4029 : VPRecipeBase(VPRecipeBase::VPWidenStoreSC, {Addr, StoredVal}, DL),
4030 VPWidenMemoryRecipe(Store, Alignment, Consecutive, Metadata) {
4031 setMask(Mask);
4032 }
4033
4034 VPWidenStoreRecipe *clone() override {
4035 return new VPWidenStoreRecipe(cast<StoreInst>(Val&: Ingredient), getAddr(),
4036 getStoredValue(), getMask(), Consecutive,
4037 getAlign(), *this, getDebugLoc());
4038 }
4039
4040 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenStoreSC);
4041
4042 /// Return the value stored by this recipe.
4043 VPValue *getStoredValue() const { return getOperand(N: 1); }
4044
4045 /// Generate a wide store or scatter.
4046 void execute(VPTransformState &State) override;
4047
4048 /// Return the cost of this VPWidenStoreRecipe.
4049 InstructionCost computeCost(ElementCount VF,
4050 VPCostContext &Ctx) const override {
4051 return VPWidenMemoryRecipe::computeCost(VF, Ctx);
4052 }
4053
4054 /// Returns true if the recipe only uses the first lane of operand \p Op.
4055 bool usesFirstLaneOnly(const VPValue *Op) const override {
4056 assert(is_contained(operands(), Op) &&
4057 "Op must be an operand of the recipe");
4058 // Widened, consecutive stores only demand the first lane of their address,
4059 // unless the same operand is also stored.
4060 return Op == getAddr() && isConsecutive() && Op != getStoredValue();
4061 }
4062
4063protected:
4064 VPRecipeBase *getAsRecipe() override;
4065 const VPRecipeBase *getAsRecipe() const override;
4066
4067#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4068 /// Print the recipe.
4069 void printRecipe(raw_ostream &O, const Twine &Indent,
4070 VPSlotTracker &SlotTracker) const override;
4071#endif
4072};
4073
4074/// A recipe for widening store operations with vector-predication intrinsics,
4075/// using the value to store, the address to store to, the explicit vector
4076/// length and an optional mask.
4077struct LLVM_ABI_FOR_TEST VPWidenStoreEVLRecipe final
4078 : public VPRecipeBase,
4079 public VPWidenMemoryRecipe {
4080 VPWidenStoreEVLRecipe(VPWidenStoreRecipe &S, VPValue *Addr,
4081 VPValue *StoredVal, VPValue &EVL, VPValue *Mask)
4082 : VPRecipeBase(VPRecipeBase::VPWidenStoreEVLSC, {Addr, StoredVal, &EVL},
4083 S.getDebugLoc()),
4084 VPWidenMemoryRecipe(S.getIngredient(), S.getAlign(), S.isConsecutive(),
4085 S) {
4086 setMask(Mask);
4087 }
4088
4089 VPWidenStoreEVLRecipe *clone() override {
4090 llvm_unreachable("cloning not supported");
4091 }
4092
4093 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenStoreEVLSC)
4094
4095 /// Return the address accessed by this recipe.
4096 VPValue *getStoredValue() const { return getOperand(N: 1); }
4097
4098 /// Return the EVL operand.
4099 VPValue *getEVL() const { return getOperand(N: 2); }
4100
4101 /// Generate the wide store or scatter.
4102 void execute(VPTransformState &State) override;
4103
4104 /// Return the cost of this VPWidenStoreEVLRecipe.
4105 InstructionCost computeCost(ElementCount VF,
4106 VPCostContext &Ctx) const override;
4107
4108 /// Returns true if the recipe only uses the first lane of operand \p Op.
4109 bool usesFirstLaneOnly(const VPValue *Op) const override {
4110 assert(is_contained(operands(), Op) &&
4111 "Op must be an operand of the recipe");
4112 if (Op == getEVL()) {
4113 assert(getStoredValue() != Op && "unexpected store of EVL");
4114 return true;
4115 }
4116 // Widened, consecutive memory operations only demand the first lane of
4117 // their address, unless the same operand is also stored. That latter can
4118 // happen with opaque pointers.
4119 return Op == getAddr() && isConsecutive() && Op != getStoredValue();
4120 }
4121
4122protected:
4123 VPRecipeBase *getAsRecipe() override;
4124 const VPRecipeBase *getAsRecipe() const override;
4125
4126#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4127 /// Print the recipe.
4128 void printRecipe(raw_ostream &O, const Twine &Indent,
4129 VPSlotTracker &SlotTracker) const override;
4130#endif
4131};
4132
4133/// Recipe to expand a SCEV expression.
4134class VPExpandSCEVRecipe : public VPSingleDefRecipe {
4135 const SCEV *Expr;
4136
4137 /// Whether \p Expr must be expanded in IR, which hoists it out of the loops
4138 /// it is invariant in, instead of as VPInstructions.
4139 bool ExpandInIR;
4140
4141public:
4142 VPExpandSCEVRecipe(const SCEV *Expr, bool ExpandInIR = false);
4143
4144 ~VPExpandSCEVRecipe() override = default;
4145
4146 VPExpandSCEVRecipe *clone() override {
4147 return new VPExpandSCEVRecipe(Expr, ExpandInIR);
4148 }
4149
4150 VP_CLASSOF_IMPL(VPRecipeBase::VPExpandSCEVSC)
4151
4152 void execute(VPTransformState &State) override {
4153 llvm_unreachable("SCEV expressions must be expanded before final execute");
4154 }
4155
4156 /// Return the cost of this VPExpandSCEVRecipe.
4157 InstructionCost computeCost(ElementCount VF,
4158 VPCostContext &Ctx) const override {
4159 // TODO: Compute accurate cost after retiring the legacy cost model.
4160 return 0;
4161 }
4162
4163 const SCEV *getSCEV() const { return Expr; }
4164
4165 bool expandInIR() const { return ExpandInIR; }
4166
4167protected:
4168#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4169 /// Print the recipe.
4170 void printRecipe(raw_ostream &O, const Twine &Indent,
4171 VPSlotTracker &SlotTracker) const override;
4172#endif
4173};
4174
4175/// A recipe for generating the active lane mask for the vector loop that is
4176/// used to predicate the vector operations.
4177class VPActiveLaneMaskPHIRecipe : public VPHeaderPHIRecipe {
4178public:
4179 VPActiveLaneMaskPHIRecipe(VPValue *StartMask, DebugLoc DL)
4180 : VPHeaderPHIRecipe(VPRecipeBase::VPActiveLaneMaskPHISC, nullptr,
4181 StartMask, StartMask->getScalarType(), DL) {}
4182
4183 ~VPActiveLaneMaskPHIRecipe() override = default;
4184
4185 VPActiveLaneMaskPHIRecipe *clone() override {
4186 auto *R = new VPActiveLaneMaskPHIRecipe(getOperand(N: 0), getDebugLoc());
4187 if (getNumOperands() == 2)
4188 R->addBackedgeValue(V: getOperand(N: 1));
4189 return R;
4190 }
4191
4192 VP_CLASSOF_IMPL(VPRecipeBase::VPActiveLaneMaskPHISC)
4193
4194 /// Generate the active lane mask phi of the vector loop.
4195 void execute(VPTransformState &State) override;
4196
4197protected:
4198#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4199 /// Print the recipe.
4200 void printRecipe(raw_ostream &O, const Twine &Indent,
4201 VPSlotTracker &SlotTracker) const override;
4202#endif
4203};
4204
4205/// A recipe for generating the phi node tracking the current scalar iteration
4206/// index. It starts at the start value of the canonical induction and gets
4207/// incremented by the number of scalar iterations processed by the vector loop
4208/// iteration. The increment does not have to be loop invariant.
4209class LLVM_ABI_FOR_TEST VPCurrentIterationPHIRecipe : public VPHeaderPHIRecipe {
4210public:
4211 VPCurrentIterationPHIRecipe(VPValue *StartIV, DebugLoc DL)
4212 : VPHeaderPHIRecipe(VPRecipeBase::VPCurrentIterationPHISC, nullptr,
4213 StartIV, StartIV->getScalarType(), DL) {}
4214
4215 ~VPCurrentIterationPHIRecipe() override = default;
4216
4217 VPCurrentIterationPHIRecipe *clone() override {
4218 llvm_unreachable("cloning not implemented yet");
4219 }
4220
4221 VP_CLASSOF_IMPL(VPRecipeBase::VPCurrentIterationPHISC)
4222
4223 void execute(VPTransformState &State) override {
4224 llvm_unreachable("cannot execute this recipe, should be replaced by a "
4225 "scalar phi recipe");
4226 }
4227
4228 /// Return the cost of this VPCurrentIterationPHIRecipe.
4229 InstructionCost computeCost(ElementCount VF,
4230 VPCostContext &Ctx) const override {
4231 // For now, match the behavior of the legacy cost model.
4232 return 0;
4233 }
4234
4235 /// Returns true if the recipe only uses the first lane of operand \p Op.
4236 bool usesFirstLaneOnly(const VPValue *Op) const override {
4237 assert(is_contained(operands(), Op) &&
4238 "Op must be an operand of the recipe");
4239 return true;
4240 }
4241
4242protected:
4243#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4244 /// Print the recipe.
4245 void printRecipe(raw_ostream &O, const Twine &Indent,
4246 VPSlotTracker &SlotTracker) const override;
4247#endif
4248};
4249
4250/// A Recipe for widening the canonical induction variable of the vector loop.
4251/// First operand is the canonical IV recipe, a second step operand (VF * Part)
4252/// is added during unrolling.
4253class VPWidenCanonicalIVRecipe : public VPRecipeWithIRFlags {
4254public:
4255 VPWidenCanonicalIVRecipe(VPRegionValue *CanonicalIV,
4256 const VPIRFlags::WrapFlagsTy &Flags = {})
4257 : VPRecipeWithIRFlags(VPRecipeBase::VPWidenCanonicalIVSC, CanonicalIV,
4258 CanonicalIV->getType(), Flags) {}
4259
4260 ~VPWidenCanonicalIVRecipe() override = default;
4261
4262 VPWidenCanonicalIVRecipe *clone() override {
4263 auto *WideCanIV =
4264 new VPWidenCanonicalIVRecipe(getCanonicalIV(), getNoWrapFlags());
4265 if (VPValue *Step = getStepValue())
4266 WideCanIV->addPerPartStep(Step);
4267 return WideCanIV;
4268 }
4269
4270 VP_CLASSOF_IMPL(VPRecipeBase::VPWidenCanonicalIVSC)
4271
4272 void execute(VPTransformState &State) override {
4273 llvm_unreachable("Expected prior expansion of WidenCanonicalIV recipes");
4274 }
4275
4276 /// Return the cost of this VPWidenCanonicalIVPHIRecipe.
4277 InstructionCost computeCost(ElementCount VF,
4278 VPCostContext &Ctx) const override {
4279 // TODO: Compute accurate cost after retiring the legacy cost model.
4280 return 0;
4281 }
4282
4283 /// Return the canonical IV being widened.
4284 VPRegionValue *getCanonicalIV() const {
4285 return cast<VPRegionValue>(Val: getOperand(N: 0));
4286 }
4287
4288 VPValue *getStepValue() const {
4289 return getNumOperands() == 2 ? getOperand(N: 1) : nullptr;
4290 }
4291
4292 /// Add the per-part step (VF * Part) used for unrolled parts.
4293 void addPerPartStep(VPValue *Step) {
4294 assert(Step->getScalarType() == getScalarType() &&
4295 "per-part step must have the same type as the canonical IV");
4296 VPUser::addOperand(Operand: Step);
4297 }
4298
4299protected:
4300#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4301 /// Print the recipe.
4302 void printRecipe(raw_ostream &O, const Twine &Indent,
4303 VPSlotTracker &SlotTracker) const override;
4304#endif
4305};
4306
4307/// A recipe for converting \p Current into \p Start + \p Current * \p Step.
4308/// FastMathFlags are derived from the \p FPBinOp in the case of FP inductions,
4309/// and the passed NoWrap \p Flags apply in the case of Ptr and Int inductions.
4310class LLVM_ABI_FOR_TEST VPDerivedIVRecipe : public VPRecipeWithIRFlags {
4311 /// Kind of the induction.
4312 const InductionDescriptor::InductionKind Kind;
4313 /// If not nullptr, the floating point induction binary operator. Must be set
4314 /// for floating point inductions.
4315 const FPMathOperator *FPBinOp;
4316
4317public:
4318 VPDerivedIVRecipe(InductionDescriptor::InductionKind Kind,
4319 const FPMathOperator *FPBinOp, VPValue *Start,
4320 VPValue *Current, VPValue *Step,
4321 const VPIRFlags::WrapFlagsTy &Flags = {})
4322 : VPRecipeWithIRFlags(VPRecipeBase::VPDerivedIVSC, {Start, Current, Step},
4323 Start->getScalarType(), Flags),
4324 Kind(Kind), FPBinOp(FPBinOp) {}
4325
4326 ~VPDerivedIVRecipe() override = default;
4327
4328 VPDerivedIVRecipe *clone() override {
4329 return new VPDerivedIVRecipe(Kind, FPBinOp, getStartValue(), getOperand(N: 1),
4330 getStepValue(), getNoWrapFlags());
4331 }
4332
4333 VP_CLASSOF_IMPL(VPRecipeBase::VPDerivedIVSC)
4334
4335 void execute(VPTransformState &State) override {
4336 llvm_unreachable("Expected prior expansion of this recipe");
4337 }
4338
4339 /// Return the cost of this VPDerivedIVRecipe.
4340 InstructionCost computeCost(ElementCount VF,
4341 VPCostContext &Ctx) const override;
4342
4343 VPValue *getStartValue() const { return getOperand(N: 0); }
4344 VPValue *getIndex() const { return getOperand(N: 1); }
4345 VPValue *getStepValue() const { return getOperand(N: 2); }
4346 const FPMathOperator *getFPBinOp() const { return FPBinOp; }
4347 InductionDescriptor::InductionKind getInductionKind() const { return Kind; }
4348
4349 /// Returns true if the recipe only uses the first lane of operand \p Op.
4350 bool usesFirstLaneOnly(const VPValue *Op) const override {
4351 assert(is_contained(operands(), Op) &&
4352 "Op must be an operand of the recipe");
4353 return true;
4354 }
4355
4356protected:
4357#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4358 /// Print the recipe.
4359 void printRecipe(raw_ostream &O, const Twine &Indent,
4360 VPSlotTracker &SlotTracker) const override;
4361#endif
4362};
4363
4364/// A recipe for handling phi nodes of integer and floating-point inductions,
4365/// producing their scalar values. Before unrolling by UF the recipe represents
4366/// the VF*UF scalar values to be produced, or UF scalar values if only first
4367/// lane is used, and has 3 operands: IV, step and VF. Unrolling adds one extra
4368/// operand StartIndex to all unroll parts except part 0, as the recipe
4369/// represents the VF scalar values (this number of values is taken from
4370/// State.VF rather than from the VF operand) starting at IV + StartIndex.
4371class LLVM_ABI_FOR_TEST VPScalarIVStepsRecipe : public VPRecipeWithIRFlags {
4372 Instruction::BinaryOps InductionOpcode;
4373
4374public:
4375 VPScalarIVStepsRecipe(VPValue *IV, VPValue *Step, VPValue *VF,
4376 Instruction::BinaryOps Opcode, FastMathFlags FMFs = {},
4377 DebugLoc DL = DebugLoc::getUnknown())
4378 : VPRecipeWithIRFlags(VPRecipeBase::VPScalarIVStepsSC, {IV, Step, VF},
4379 IV->getScalarType(), FMFs, DL),
4380 InductionOpcode(Opcode) {}
4381
4382 ~VPScalarIVStepsRecipe() override = default;
4383
4384 VPScalarIVStepsRecipe *clone() override {
4385 auto *NewR = new VPScalarIVStepsRecipe(
4386 getOperand(N: 0), getOperand(N: 1), getOperand(N: 2), InductionOpcode,
4387 getFastMathFlagsOrNone(), getDebugLoc());
4388 if (VPValue *StartIndex = getStartIndex())
4389 NewR->setStartIndex(StartIndex);
4390 return NewR;
4391 }
4392
4393 VP_CLASSOF_IMPL(VPRecipeBase::VPScalarIVStepsSC)
4394
4395 /// Generate the scalarized versions of the phi node as needed by their users.
4396 void execute(VPTransformState &State) override;
4397
4398 /// Return the cost of this VPScalarIVStepsRecipe.
4399 InstructionCost computeCost(ElementCount VF,
4400 VPCostContext &Ctx) const override;
4401
4402 VPValue *getStepValue() const { return getOperand(N: 1); }
4403
4404 /// Return the number of scalars to produce per unroll part, used to compute
4405 /// StartIndex during unrolling.
4406 VPValue *getVFValue() const { return getOperand(N: 2); }
4407
4408 /// Return the StartIndex, or null if known to be zero, valid only after
4409 /// unrolling.
4410 VPValue *getStartIndex() const {
4411 return getNumOperands() == 4 ? getOperand(N: 3) : nullptr;
4412 }
4413
4414 /// Set or add the StartIndex operand.
4415 void setStartIndex(VPValue *StartIndex) {
4416 if (getNumOperands() == 4)
4417 setOperand(I: 3, New: StartIndex);
4418 else
4419 addOperand(Operand: StartIndex);
4420 }
4421
4422 /// Returns true if this recipe produces scalar values for all VF lanes.
4423 bool doesGeneratePerAllLanes() const;
4424
4425 /// Returns true if the recipe only uses the first lane of operand \p Op.
4426 bool usesFirstLaneOnly(const VPValue *Op) const override {
4427 assert(is_contained(operands(), Op) &&
4428 "Op must be an operand of the recipe");
4429 return true;
4430 }
4431
4432 Instruction::BinaryOps getInductionOpcode() const { return InductionOpcode; }
4433
4434protected:
4435#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4436 /// Print the recipe.
4437 void printRecipe(raw_ostream &O, const Twine &Indent,
4438 VPSlotTracker &SlotTracker) const override;
4439#endif
4440};
4441
4442/// CastInfo helper for casting from VPRecipeBase to a mixin class that is not
4443/// part of the VPRecipeBase class hierarchy (e.g. VPPhiAccessors,
4444/// VPIRMetadata).
4445namespace vpdetail {
4446template <typename VPMixin, typename... RecipeTys>
4447struct CastInfoMixinImpl
4448 : public DefaultDoCastIfPossible<VPMixin *, VPRecipeBase *,
4449 CastInfoMixinImpl<VPMixin, RecipeTys...>> {
4450 static_assert((std::is_base_of_v<VPMixin, RecipeTys> && ...),
4451 "Each type in RecipeTys must derive from VPMixin");
4452
4453 /// Used by isa.
4454 static bool isPossible(VPRecipeBase *R) { return isa<RecipeTys...>(R); }
4455
4456 /// Used by cast.
4457 static VPMixin *doCast(VPRecipeBase *R) {
4458 VPMixin *Out = nullptr;
4459 ((Out = dyn_cast<RecipeTys>(R)) || ...);
4460 assert(Out && "Illegal recipe for cast");
4461 return Out;
4462 }
4463 static VPMixin *castFailed() { return nullptr; }
4464};
4465} // namespace vpdetail
4466
4467/// Support casting from VPRecipeBase -> VPPhiAccessors.
4468template <>
4469struct CastInfo<VPPhiAccessors, VPRecipeBase *>
4470 : vpdetail::CastInfoMixinImpl<VPPhiAccessors, VPPhi, VPIRPhi,
4471 VPWidenPHIRecipe, VPHeaderPHIRecipe,
4472 VPConditionalInductionPHIRecipe> {};
4473
4474template <>
4475struct CastInfo<VPPhiAccessors, const VPRecipeBase *>
4476 : public ConstStrippingForwardingCast<
4477 VPPhiAccessors, const VPRecipeBase *,
4478 CastInfo<VPPhiAccessors, VPRecipeBase *>> {};
4479template <>
4480struct CastInfo<VPPhiAccessors, VPRecipeBase>
4481 : public ForwardToPointerCast<VPPhiAccessors, VPRecipeBase *,
4482 CastInfo<VPPhiAccessors, VPRecipeBase *>> {};
4483
4484/// Support casting from VPRecipeBase / VPUser -> VPWidenMemoryRecipe.
4485template <>
4486struct CastInfo<VPWidenMemoryRecipe, VPRecipeBase *>
4487 : vpdetail::CastInfoMixinImpl<VPWidenMemoryRecipe, VPWidenLoadRecipe,
4488 VPWidenLoadEVLRecipe, VPWidenStoreRecipe,
4489 VPWidenStoreEVLRecipe> {};
4490template <>
4491struct CastInfo<VPWidenMemoryRecipe, const VPRecipeBase *>
4492 : public ConstStrippingForwardingCast<
4493 VPWidenMemoryRecipe, const VPRecipeBase *,
4494 CastInfo<VPWidenMemoryRecipe, VPRecipeBase *>> {};
4495
4496/// Support casting from VPSingleDefRecipe -> VPWidenMemoryRecipe (loads only).
4497template <>
4498struct CastInfo<VPWidenMemoryRecipe, VPSingleDefRecipe *>
4499 : vpdetail::CastInfoMixinImpl<VPWidenMemoryRecipe, VPWidenLoadRecipe,
4500 VPWidenLoadEVLRecipe> {};
4501template <>
4502struct CastInfo<VPWidenMemoryRecipe, const VPSingleDefRecipe *>
4503 : public ConstStrippingForwardingCast<
4504 VPWidenMemoryRecipe, const VPSingleDefRecipe *,
4505 CastInfo<VPWidenMemoryRecipe, VPSingleDefRecipe *>> {};
4506
4507/// Support casting from VPRecipeBase -> VPIRMetadata.
4508template <>
4509struct CastInfo<VPIRMetadata, VPRecipeBase *>
4510 : vpdetail::CastInfoMixinImpl<VPIRMetadata, VPInstruction, VPWidenRecipe,
4511 VPWidenCastRecipe, VPWidenIntrinsicRecipe,
4512 VPWidenCallRecipe, VPReplicateRecipe,
4513 VPInterleaveBase, VPWidenMemoryRecipe,
4514 VPHistogramRecipe, VPBranchOnMaskRecipe> {};
4515
4516template <>
4517struct CastInfo<VPIRMetadata, const VPRecipeBase *>
4518 : public ConstStrippingForwardingCast<
4519 VPIRMetadata, const VPRecipeBase *,
4520 CastInfo<VPIRMetadata, VPRecipeBase *>> {};
4521template <>
4522struct CastInfo<VPIRMetadata, VPRecipeBase>
4523 : public ForwardToPointerCast<VPIRMetadata, VPRecipeBase *,
4524 CastInfo<VPIRMetadata, VPRecipeBase *>> {};
4525
4526/// Support casting from VPSingleDefRecipe -> VPIRMetadata.
4527template <>
4528struct CastInfo<VPIRMetadata, VPSingleDefRecipe *>
4529 : CastInfo<VPIRMetadata, VPRecipeBase *> {};
4530template <>
4531struct CastInfo<VPIRMetadata, const VPSingleDefRecipe *>
4532 : public ConstStrippingForwardingCast<
4533 VPIRMetadata, const VPSingleDefRecipe *,
4534 CastInfo<VPIRMetadata, VPSingleDefRecipe *>> {};
4535
4536/// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
4537/// holds a sequence of zero or more VPRecipe's each representing a sequence of
4538/// output IR instructions. All PHI-like recipes must come before any non-PHI
4539/// recipes.
4540class LLVM_ABI_FOR_TEST VPBasicBlock : public VPBlockBase {
4541 friend class VPlan;
4542
4543 /// Use VPlan::createVPBasicBlock to create VPBasicBlocks.
4544 VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
4545 : VPBasicBlock(VPBasicBlockSC, Name) {
4546 if (Recipe)
4547 appendRecipe(Recipe);
4548 }
4549
4550public:
4551 using RecipeListTy = VPRecipeBase::RecipeListTy;
4552
4553protected:
4554 /// The VPRecipes held in the order of output instructions to generate.
4555 RecipeListTy Recipes;
4556
4557 VPBasicBlock(VPBlockTy BlockSC, const Twine &Name = "")
4558 : VPBlockBase(BlockSC, Name.str()) {
4559 // Set the parent of the list's sentinel, so end() iterators know their
4560 // block.
4561 Recipes.end().getNodePtr()->setParent(this);
4562 }
4563
4564public:
4565 ~VPBasicBlock() override {
4566 while (!Recipes.empty())
4567 Recipes.pop_back();
4568 }
4569
4570 /// Instruction iterators...
4571 using iterator = RecipeListTy::iterator;
4572 using const_iterator = RecipeListTy::const_iterator;
4573 using reverse_iterator = RecipeListTy::reverse_iterator;
4574 using const_reverse_iterator = RecipeListTy::const_reverse_iterator;
4575
4576 //===--------------------------------------------------------------------===//
4577 /// Recipe iterator methods
4578 ///
4579 inline iterator begin() { return Recipes.begin(); }
4580 inline const_iterator begin() const { return Recipes.begin(); }
4581 inline iterator end() { return Recipes.end(); }
4582 inline const_iterator end() const { return Recipes.end(); }
4583
4584 inline reverse_iterator rbegin() { return Recipes.rbegin(); }
4585 inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
4586 inline reverse_iterator rend() { return Recipes.rend(); }
4587 inline const_reverse_iterator rend() const { return Recipes.rend(); }
4588
4589 inline size_t size() const { return Recipes.size(); }
4590 inline bool empty() const { return Recipes.empty(); }
4591 inline const VPRecipeBase &front() const { return Recipes.front(); }
4592 inline VPRecipeBase &front() { return Recipes.front(); }
4593 inline const VPRecipeBase &back() const { return Recipes.back(); }
4594 inline VPRecipeBase &back() { return Recipes.back(); }
4595
4596 /// Returns a reference to the list of recipes.
4597 RecipeListTy &getRecipeList() { return Recipes; }
4598
4599 /// Returns a pointer to a member of the recipe list.
4600 static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) {
4601 return &VPBasicBlock::Recipes;
4602 }
4603
4604 /// Method to support type inquiry through isa, cast, and dyn_cast.
4605 static inline bool classof(const VPBlockBase *V) {
4606 return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC ||
4607 V->getVPBlockID() == VPBlockBase::VPIRBasicBlockSC;
4608 }
4609
4610 void insert(VPRecipeBase *Recipe, iterator InsertPt) {
4611 assert(Recipe && "No recipe to append.");
4612 assert(!Recipe->getParent() && "Recipe already in VPlan");
4613 assert(InsertPt.getNodeParent() == this &&
4614 "Insertion position not in this VPBasicBlock");
4615 Recipe->setParent(this);
4616 Recipes.insert(where: InsertPt, New: Recipe);
4617 }
4618
4619 /// Augment the existing recipes of a VPBasicBlock with an additional
4620 /// \p Recipe as the last recipe.
4621 void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, InsertPt: end()); }
4622
4623 /// The method which generates the output IR instructions that correspond to
4624 /// this VPBasicBlock, thereby "executing" the VPlan.
4625 void execute(VPTransformState *State) override;
4626
4627 /// Return the cost of this VPBasicBlock.
4628 InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override;
4629
4630 /// Return the position of the first non-phi node recipe in the block.
4631 iterator getFirstNonPhi();
4632
4633 /// Returns an iterator range over the PHI-like recipes in the block.
4634 iterator_range<iterator> phis() {
4635 return make_range(x: begin(), y: getFirstNonPhi());
4636 }
4637
4638 /// Split current block at \p SplitAt by inserting a new block between the
4639 /// current block and its successors and moving all recipes starting at
4640 /// SplitAt to the new block. Returns the new block.
4641 VPBasicBlock *splitAt(iterator SplitAt);
4642
4643 VPRegionBlock *getEnclosingLoopRegion();
4644 const VPRegionBlock *getEnclosingLoopRegion() const;
4645
4646#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4647 /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p
4648 /// SlotTracker is used to print unnamed VPValue's using consequtive numbers.
4649 ///
4650 /// Note that the numbering is applied to the whole VPlan, so printing
4651 /// individual blocks is consistent with the whole VPlan printing.
4652 void print(raw_ostream &O, const Twine &Indent,
4653 VPSlotTracker &SlotTracker) const override;
4654 using VPBlockBase::print; // Get the print(raw_stream &O) version.
4655#endif
4656
4657 /// If the block has multiple successors, return the branch recipe terminating
4658 /// the block. If there are no or only a single successor, return nullptr;
4659 VPRecipeBase *getTerminator();
4660 const VPRecipeBase *getTerminator() const;
4661
4662 /// Returns true if the block is exiting it's parent region.
4663 bool isExiting() const;
4664
4665 /// Clone the current block and it's recipes, without updating the operands of
4666 /// the cloned recipes.
4667 VPBasicBlock *clone() override;
4668
4669 /// Returns the predecessor block at index \p Idx with the predecessors as per
4670 /// the corresponding plain CFG. If the block is an entry block to a region,
4671 /// the first predecessor is the single predecessor of a region, and the
4672 /// second predecessor is the exiting block of the region.
4673 const VPBasicBlock *getCFGPredecessor(unsigned Idx) const;
4674
4675protected:
4676 /// Execute the recipes in the IR basic block \p BB.
4677 void executeRecipes(VPTransformState *State, BasicBlock *BB);
4678
4679 /// Connect the VPBBs predecessors' in the VPlan CFG to the IR basic block
4680 /// generated for this VPBB.
4681 void connectToPredecessors(VPTransformState &State);
4682
4683private:
4684 /// Create an IR BasicBlock to hold the output instructions generated by this
4685 /// VPBasicBlock, and return it. Update the CFGState accordingly.
4686 BasicBlock *createEmptyBasicBlock(VPTransformState &State);
4687};
4688
4689inline const VPBasicBlock *
4690VPPhiAccessors::getIncomingBlock(unsigned Idx) const {
4691 return getAsRecipe()->getParent()->getCFGPredecessor(Idx);
4692}
4693
4694/// A special type of VPBasicBlock that wraps an existing IR basic block.
4695/// Recipes of the block get added before the first non-phi instruction in the
4696/// wrapped block.
4697/// Note: At the moment, VPIRBasicBlock can only be used to wrap VPlan's
4698/// preheader block.
4699class VPIRBasicBlock : public VPBasicBlock {
4700 friend class VPlan;
4701
4702 BasicBlock *IRBB;
4703
4704 /// Use VPlan::createVPIRBasicBlock to create VPIRBasicBlocks.
4705 VPIRBasicBlock(BasicBlock *IRBB)
4706 : VPBasicBlock(VPIRBasicBlockSC,
4707 (Twine("ir-bb<") + IRBB->getName() + Twine(">")).str()),
4708 IRBB(IRBB) {}
4709
4710public:
4711 ~VPIRBasicBlock() override = default;
4712
4713 static inline bool classof(const VPBlockBase *V) {
4714 return V->getVPBlockID() == VPBlockBase::VPIRBasicBlockSC;
4715 }
4716
4717 /// The method which generates the output IR instructions that correspond to
4718 /// this VPBasicBlock, thereby "executing" the VPlan.
4719 void execute(VPTransformState *State) override;
4720
4721 VPIRBasicBlock *clone() override;
4722
4723 BasicBlock *getIRBasicBlock() const { return IRBB; }
4724};
4725
4726/// Track information about the canonical IV and header mask of a loop region.
4727/// TODO: Have it also track the canonical IV increment, subject of NUW flag.
4728class VPCanonicalIVInfo {
4729 /// VPRegionValue for the canonical IV, whose allocation is managed by
4730 /// VPCanonicalIVInfo.
4731 std::unique_ptr<VPRegionValue> CanIV;
4732
4733 /// Optional VPRegionValue for the header mask, set when tail folding.
4734 std::unique_ptr<VPRegionValue> HeaderMask;
4735
4736 /// Whether the increment of the canonical IV may unsigned wrap or not.
4737 bool HasNUW = true;
4738
4739public:
4740 VPCanonicalIVInfo(Type *Ty, DebugLoc DL, VPRegionBlock *Region)
4741 : CanIV(std::make_unique<VPRegionValue>(args&: Ty, args&: DL, args&: Region)) {}
4742
4743 VPRegionValue *getRegionValue() { return CanIV.get(); }
4744 const VPRegionValue *getRegionValue() const { return CanIV.get(); }
4745
4746 VPRegionValue *getHeaderMask() const { return HeaderMask.get(); }
4747
4748 /// Create the header mask for the region and return it. Must only be called
4749 /// when no header mask exists yet.
4750 VPRegionValue *createHeaderMask() {
4751 assert(!HeaderMask && "Header mask already created");
4752 HeaderMask = std::make_unique<VPRegionValue>(
4753 args: Type::getInt1Ty(C&: CanIV->getType()->getContext()), args: DebugLoc::getUnknown(),
4754 args: CanIV->getDefiningRegion());
4755 return HeaderMask.get();
4756 }
4757
4758 bool hasNUW() const { return HasNUW; }
4759
4760 void clearNUW() { HasNUW = false; }
4761};
4762
4763/// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
4764/// which form a Single-Entry-Single-Exiting subgraph of the output IR CFG.
4765/// A VPRegionBlock may indicate that its contents are to be replicated several
4766/// times. This is designed to support predicated scalarization, in which a
4767/// scalar if-then code structure needs to be generated VF * UF times. Having
4768/// this replication indicator helps to keep a single model for multiple
4769/// candidate VF's. The actual replication takes place only once the desired VF
4770/// and UF have been determined.
4771class LLVM_ABI_FOR_TEST VPRegionBlock : public VPBlockBase {
4772 friend class VPlan;
4773
4774 /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
4775 VPBlockBase *Entry;
4776
4777 /// Hold the Single Exiting block of the SESE region modelled by the
4778 /// VPRegionBlock.
4779 VPBlockBase *Exiting;
4780
4781 /// Holds the Canonical IV of the loop region along with additional
4782 /// information. If CanIVInfo is nullptr, the region is a replicating region.
4783 /// Loop regions retain their canonical IVs until they are dissolved, even if
4784 /// the canonical IV has no users.
4785 std::unique_ptr<VPCanonicalIVInfo> CanIVInfo;
4786
4787 /// Use VPlan::createLoopRegion() and VPlan::createReplicateRegion() to create
4788 /// VPRegionBlocks.
4789 VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exiting,
4790 const std::string &Name = "")
4791 : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exiting(Exiting) {
4792 if (Entry) {
4793 assert(!Entry->hasPredecessors() && "Entry block has predecessors.");
4794 assert(Exiting && "Must also pass Exiting if Entry is passed.");
4795 assert(!Exiting->hasSuccessors() && "Exit block has successors.");
4796 Entry->setParent(this);
4797 Exiting->setParent(this);
4798 }
4799 }
4800
4801 VPRegionBlock(Type *CanIVTy, DebugLoc DL, VPBlockBase *Entry,
4802 VPBlockBase *Exiting, const std::string &Name = "")
4803 : VPRegionBlock(Entry, Exiting, Name) {
4804 CanIVInfo = std::make_unique<VPCanonicalIVInfo>(args&: CanIVTy, args&: DL, args: this);
4805 }
4806
4807public:
4808 ~VPRegionBlock() override = default;
4809
4810 /// Method to support type inquiry through isa, cast, and dyn_cast.
4811 static inline bool classof(const VPBlockBase *V) {
4812 return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
4813 }
4814
4815 const VPBlockBase *getEntry() const { return Entry; }
4816 VPBlockBase *getEntry() { return Entry; }
4817
4818 /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
4819 /// EntryBlock must have no predecessors.
4820 void setEntry(VPBlockBase *EntryBlock) {
4821 assert(!EntryBlock->hasPredecessors() &&
4822 "Entry block cannot have predecessors.");
4823 Entry = EntryBlock;
4824 EntryBlock->setParent(this);
4825 }
4826
4827 const VPBlockBase *getExiting() const { return Exiting; }
4828 VPBlockBase *getExiting() { return Exiting; }
4829
4830 /// Set \p ExitingBlock as the exiting VPBlockBase of this VPRegionBlock. \p
4831 /// ExitingBlock must have no successors.
4832 void setExiting(VPBlockBase *ExitingBlock) {
4833 assert(!ExitingBlock->hasSuccessors() &&
4834 "Exit block cannot have successors.");
4835 Exiting = ExitingBlock;
4836 ExitingBlock->setParent(this);
4837 }
4838
4839 /// Returns the pre-header VPBasicBlock of the loop region.
4840 VPBasicBlock *getPreheaderVPBB() {
4841 assert(!isReplicator() && "should only get pre-header of loop regions");
4842 return getSinglePredecessor()->getExitingBasicBlock();
4843 }
4844
4845 /// An indicator whether this region is to generate multiple replicated
4846 /// instances of output IR corresponding to its VPBlockBases.
4847 bool isReplicator() const { return !CanIVInfo; }
4848
4849 /// Return the VPBranchOnMaskRecipe from the entry block of this replicating
4850 /// region.
4851 const VPBranchOnMaskRecipe *getEntryBranchOnMask() const;
4852 VPBranchOnMaskRecipe *getEntryBranchOnMask() {
4853 return const_cast<VPBranchOnMaskRecipe *>(
4854 static_cast<const VPRegionBlock *>(this)->getEntryBranchOnMask());
4855 }
4856
4857 /// The method which generates the output IR instructions that correspond to
4858 /// this VPRegionBlock, thereby "executing" the VPlan.
4859 void execute(VPTransformState *State) override;
4860
4861 // Return the cost of this region.
4862 InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override;
4863
4864#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4865 /// Print this VPRegionBlock to \p O (recursively), prefixing all lines with
4866 /// \p Indent. \p SlotTracker is used to print unnamed VPValue's using
4867 /// consequtive numbers.
4868 ///
4869 /// Note that the numbering is applied to the whole VPlan, so printing
4870 /// individual regions is consistent with the whole VPlan printing.
4871 void print(raw_ostream &O, const Twine &Indent,
4872 VPSlotTracker &SlotTracker) const override;
4873 using VPBlockBase::print; // Get the print(raw_stream &O) version.
4874#endif
4875
4876 /// Clone all blocks in the single-entry single-exit region of the block and
4877 /// their recipes without updating the operands of the cloned recipes.
4878 VPRegionBlock *clone() override;
4879
4880 /// Remove the current region from its VPlan, connecting its predecessor to
4881 /// its entry, and its exiting block to its successor.
4882 void dissolveToCFGLoop();
4883
4884 /// Get the canonical IV increment instruction if it exists. Otherwise, create
4885 /// a new increment before the terminator and return it. The canonical IV
4886 /// increment is subject to DCE if unused, unlike the canonical IV itself.
4887 VPInstruction *getOrCreateCanonicalIVIncrement();
4888
4889 /// Return the canonical induction variable of the region, null for
4890 /// replicating regions.
4891 VPRegionValue *getCanonicalIV() {
4892 return CanIVInfo ? CanIVInfo->getRegionValue() : nullptr;
4893 }
4894 const VPRegionValue *getCanonicalIV() const {
4895 return CanIVInfo ? CanIVInfo->getRegionValue() : nullptr;
4896 }
4897
4898 /// Return the type of the canonical IV for loop regions.
4899 Type *getCanonicalIVType() const {
4900 return CanIVInfo->getRegionValue()->getType();
4901 }
4902
4903 /// Return the header mask of the region, or null if not set.
4904 VPRegionValue *getHeaderMask() const {
4905 return CanIVInfo ? CanIVInfo->getHeaderMask() : nullptr;
4906 }
4907
4908 /// Return the header mask if it exists and is used, or null otherwise. The
4909 /// mask is materialized into concrete recipes only after costing, so cost and
4910 /// codegen accounting sites use this to skip an unused mask.
4911 VPRegionValue *getUsedHeaderMask() const {
4912 VPRegionValue *HeaderMask = getHeaderMask();
4913 return HeaderMask && HeaderMask->getNumUsers() > 0 ? HeaderMask : nullptr;
4914 }
4915
4916 /// Create the header mask for the region and return it. Must only be called
4917 /// on loop regions that don't already have a header mask.
4918 VPRegionValue *createHeaderMask() {
4919 assert(CanIVInfo && "Can only create header mask for loop regions");
4920 return CanIVInfo->createHeaderMask();
4921 }
4922
4923 /// Return the region values of the loop region (canonical IV, header mask)
4924 /// or an empty vector for replicate regions.
4925 SmallVector<VPRegionValue *, 2> getRegionValues() const {
4926 if (!CanIVInfo)
4927 return {};
4928 SmallVector<VPRegionValue *, 2> R = {CanIVInfo->getRegionValue()};
4929 if (auto *HM = CanIVInfo->getHeaderMask())
4930 R.push_back(Elt: HM);
4931 return R;
4932 }
4933
4934 /// Indicates if NUW is set for the canonical IV increment, for loop regions.
4935 bool hasCanonicalIVNUW() const { return CanIVInfo->hasNUW(); }
4936
4937 /// Unsets NUW for the canonical IV increment \p Increment, for loop regions.
4938 void clearCanonicalIVNUW(VPInstruction *Increment) {
4939 assert(Increment && "Must provide increment to clear");
4940 Increment->dropPoisonGeneratingFlags();
4941 CanIVInfo->clearNUW();
4942 }
4943};
4944
4945inline VPRegionBlock *VPRecipeBase::getRegion() {
4946 return getParent()->getParent();
4947}
4948
4949inline const VPRegionBlock *VPRecipeBase::getRegion() const {
4950 return getParent()->getParent();
4951}
4952
4953/// VPlan models a candidate for vectorization, encoding various decisions take
4954/// to produce efficient output IR, including which branches, basic-blocks and
4955/// output IR instructions to generate, and their cost. VPlan holds a
4956/// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
4957/// VPBasicBlock.
4958class VPlan {
4959 friend class VPlanPrinter;
4960 friend class VPSlotTracker;
4961
4962 /// VPBasicBlock corresponding to the original preheader. Used to place
4963 /// VPExpandSCEV recipes for expressions used during VPlan execution.
4964 /// When this VPlan is used for the epilogue vector loop, the entry models the
4965 /// main plan's entry and its edges move to the epilogue iteration check (see
4966 /// VPlanTransforms::modelGeneratedMainLoopBlocks).
4967 VPBasicBlock *Entry;
4968
4969 /// VPIRBasicBlock wrapping the header of the original scalar loop.
4970 VPIRBasicBlock *ScalarHeader;
4971
4972 /// Immutable list of VPIRBasicBlocks wrapping the exit blocks of the original
4973 /// scalar loop. Note that some exit blocks may be unreachable at the moment,
4974 /// e.g. if the scalar epilogue always executes.
4975 SmallVector<VPIRBasicBlock *, 2> ExitBlocks;
4976
4977 /// Holds the VFs applicable to this VPlan.
4978 SmallSetVector<ElementCount, 2> VFs;
4979
4980 /// Holds the UFs applicable to this VPlan. If empty, the VPlan is valid for
4981 /// any UF.
4982 SmallSetVector<unsigned, 2> UFs;
4983
4984 /// Holds the name of the VPlan, for printing.
4985 std::string Name;
4986
4987 /// Represents the trip count of the original loop, for folding
4988 /// the tail.
4989 VPValue *TripCount = nullptr;
4990
4991 /// Represents the vector trip count.
4992 VPSymbolicValue VectorTripCount;
4993
4994 /// Represents the vectorization factor of the loop.
4995 VPSymbolicValue VF;
4996
4997 /// Represents the unroll factor of the loop.
4998 VPSymbolicValue UF;
4999
5000 /// Represents the loop-invariant VF * UF of the vector loop region.
5001 VPSymbolicValue VFxUF;
5002
5003 /// Contains all the external definitions created for this VPlan, as a mapping
5004 /// from IR Values to VPIRValues.
5005 SmallMapVector<Value *, VPIRValue *, 16> LiveIns;
5006
5007 /// Blocks allocated and owned by the VPlan. They will be deleted once the
5008 /// VPlan is destroyed.
5009 SmallVector<VPBlockBase *> CreatedBlocks;
5010
5011 /// Construct a VPlan with \p Entry to the plan and with \p ScalarHeader
5012 /// wrapping the original header of the scalar loop. The vector loop will have
5013 /// index type \p IdxTy.
5014 VPlan(VPBasicBlock *Entry, VPIRBasicBlock *ScalarHeader, Type *IdxTy)
5015 : Entry(Entry), ScalarHeader(ScalarHeader), VectorTripCount(IdxTy),
5016 VF(IdxTy), UF(IdxTy), VFxUF(IdxTy) {
5017 Entry->setPlan(this);
5018 assert(ScalarHeader->getNumSuccessors() == 0 &&
5019 "scalar header must be a leaf node");
5020 }
5021
5022public:
5023 /// Construct a VPlan for \p L. This will create VPIRBasicBlocks wrapping the
5024 /// original preheader and scalar header of \p L, to be used as entry and
5025 /// scalar header blocks of the new VPlan. The vector loop will have index
5026 /// type \p IdxTy.
5027 VPlan(Loop *L, Type *IdxTy);
5028
5029 /// Construct a VPlan with a new VPBasicBlock as entry, a VPIRBasicBlock
5030 /// wrapping \p ScalarHeaderBB and vector loop index of type \p IdxTy.
5031 VPlan(BasicBlock *ScalarHeaderBB, Type *IdxTy)
5032 : VectorTripCount(IdxTy), VF(IdxTy), UF(IdxTy), VFxUF(IdxTy) {
5033 setEntry(createVPBasicBlock(Name: "preheader"));
5034 ScalarHeader = createVPIRBasicBlock(IRBB: ScalarHeaderBB);
5035 }
5036
5037 LLVM_ABI_FOR_TEST ~VPlan();
5038
5039 void setEntry(VPBasicBlock *VPBB) {
5040 Entry = VPBB;
5041 VPBB->setPlan(this);
5042 }
5043
5044 /// Generate the IR code for this VPlan.
5045 void execute(VPTransformState *State);
5046
5047 /// Return the cost of this plan.
5048 InstructionCost cost(ElementCount VF, VPCostContext &Ctx);
5049
5050 VPBasicBlock *getEntry() { return Entry; }
5051 const VPBasicBlock *getEntry() const { return Entry; }
5052
5053 /// Returns the preheader of the vector loop region, if one exists, or null
5054 /// otherwise.
5055 VPBasicBlock *getVectorPreheader() const {
5056 const VPRegionBlock *VectorRegion = getVectorLoopRegion();
5057 return VectorRegion
5058 ? cast<VPBasicBlock>(Val: VectorRegion->getSinglePredecessor())
5059 : nullptr;
5060 }
5061
5062 /// Returns the VPRegionBlock of the vector loop.
5063 LLVM_ABI_FOR_TEST VPRegionBlock *getVectorLoopRegion();
5064 LLVM_ABI_FOR_TEST const VPRegionBlock *getVectorLoopRegion() const;
5065
5066 /// Returns true if this VPlan is for an outer loop, i.e., its vector
5067 /// loop region contains a nested loop region.
5068 LLVM_ABI_FOR_TEST bool isOuterLoop() const;
5069
5070 /// Returns true if the vector loop region is tail-folded.
5071 bool hasTailFolded() const {
5072 const VPRegionBlock *LoopRegion = getVectorLoopRegion();
5073 return LoopRegion && LoopRegion->getHeaderMask();
5074 }
5075
5076 /// Returns true if the plan requires a scalar epilogue after the vector
5077 /// loop. Must be called before removeBranchOnConst.
5078 bool requiresScalarEpilogue() const {
5079 const VPBasicBlock *MiddleVPBB = getMiddleBlock();
5080 return MiddleVPBB->getSingleSuccessor() == getScalarPreheader();
5081 }
5082
5083 /// Returns the 'middle' block of the plan, that is the block that selects
5084 /// whether to execute the scalar tail loop or the exit block from the loop
5085 /// latch. If there is an early exit from the vector loop, the middle block
5086 /// conceptully has the early exit block as third successor, split accross 2
5087 /// VPBBs. In that case, the second VPBB selects whether to execute the scalar
5088 /// tail loop or the exit block. If the scalar tail loop or exit block are
5089 /// known to always execute, the middle block may branch directly to that
5090 /// block. This function cannot be called once the vector loop region has been
5091 /// removed.
5092 VPBasicBlock *getMiddleBlock() {
5093 VPRegionBlock *LoopRegion = getVectorLoopRegion();
5094 assert(
5095 LoopRegion &&
5096 "cannot call the function after vector loop region has been removed");
5097 // The middle block is always the last successor of the region.
5098 return cast<VPBasicBlock>(Val: LoopRegion->getSuccessors().back());
5099 }
5100
5101 const VPBasicBlock *getMiddleBlock() const {
5102 return const_cast<VPlan *>(this)->getMiddleBlock();
5103 }
5104
5105 /// Return the VPBasicBlock for the preheader of the scalar loop.
5106 VPBasicBlock *getScalarPreheader() const {
5107 return dyn_cast_or_null<VPBasicBlock>(
5108 Val: getScalarHeader()->getSinglePredecessor());
5109 }
5110
5111 /// Return the VPIRBasicBlock wrapping the header of the scalar loop.
5112 VPIRBasicBlock *getScalarHeader() const { return ScalarHeader; }
5113
5114 /// Return an ArrayRef containing VPIRBasicBlocks wrapping the exit blocks of
5115 /// the original scalar loop.
5116 ArrayRef<VPIRBasicBlock *> getExitBlocks() const { return ExitBlocks; }
5117
5118 /// Returns true if \p VPBB is an exit block.
5119 bool isExitBlock(VPBlockBase *VPBB);
5120
5121 /// The trip count of the original loop.
5122 VPValue *getTripCount() const {
5123 assert(TripCount && "trip count needs to be set before accessing it");
5124 return TripCount;
5125 }
5126
5127 /// Set the trip count assuming it is currently null; if it is not - use
5128 /// resetTripCount().
5129 void setTripCount(VPValue *NewTripCount) {
5130 assert(!TripCount && NewTripCount && "TripCount should not be set yet.");
5131 TripCount = NewTripCount;
5132 }
5133
5134 /// Resets the trip count for the VPlan. The caller must make sure all uses of
5135 /// the original trip count have been replaced.
5136 void resetTripCount(VPValue *NewTripCount) {
5137 assert(TripCount && NewTripCount && TripCount->user_empty() &&
5138 "TripCount must be set when resetting");
5139 TripCount = NewTripCount;
5140 }
5141
5142 /// The vector trip count.
5143 VPSymbolicValue &getVectorTripCount() { return VectorTripCount; }
5144
5145 /// Returns the VF of the vector loop region.
5146 VPSymbolicValue &getVF() { return VF; };
5147 const VPSymbolicValue &getVF() const { return VF; };
5148
5149 /// Returns the UF of the vector loop region.
5150 VPSymbolicValue &getUF() { return UF; };
5151
5152 /// Returns VF * UF of the vector loop region.
5153 VPSymbolicValue &getVFxUF() { return VFxUF; }
5154
5155 LLVMContext &getContext() const {
5156 return getScalarHeader()->getIRBasicBlock()->getContext();
5157 }
5158
5159 const DataLayout &getDataLayout() const {
5160 return getScalarHeader()->getIRBasicBlock()->getDataLayout();
5161 }
5162
5163 Function *getIRFunction() const {
5164 return getScalarHeader()->getIRBasicBlock()->getParent();
5165 }
5166
5167 void addVF(ElementCount VF) { VFs.insert(X: VF); }
5168
5169 void setVF(ElementCount VF) {
5170 assert(hasVF(VF) && "Cannot set VF not already in plan");
5171 VFs.clear();
5172 VFs.insert(X: VF);
5173 }
5174
5175 /// Remove \p VF from the plan.
5176 void removeVF(ElementCount VF) {
5177 assert(hasVF(VF) && "tried to remove VF not present in plan");
5178 VFs.remove(X: VF);
5179 }
5180
5181 bool hasVF(ElementCount VF) const { return VFs.count(key: VF); }
5182 bool hasScalableVF() const {
5183 return any_of(Range: VFs, P: [](ElementCount VF) { return VF.isScalable(); });
5184 }
5185
5186 /// Returns an iterator range over all VFs of the plan.
5187 iterator_range<SmallSetVector<ElementCount, 2>::iterator>
5188 vectorFactors() const {
5189 return VFs;
5190 }
5191
5192 /// Returns the single VF of the plan, asserting that the plan has exactly
5193 /// one VF.
5194 ElementCount getSingleVF() const {
5195 assert(VFs.size() == 1 && "expected plan with single VF");
5196 return VFs[0];
5197 }
5198
5199 bool hasScalarVFOnly() const {
5200 bool HasScalarVFOnly = VFs.size() == 1 && VFs[0].isScalar();
5201 assert(HasScalarVFOnly == hasVF(ElementCount::getFixed(1)) &&
5202 "Plan with scalar VF should only have a single VF");
5203 return HasScalarVFOnly;
5204 }
5205
5206 bool hasUF(unsigned UF) const { return UFs.empty() || UFs.contains(key: UF); }
5207
5208 /// Returns the concrete UF of the plan, after unrolling.
5209 unsigned getConcreteUF() const {
5210 assert(UFs.size() == 1 && "Expected a single UF");
5211 return UFs[0];
5212 }
5213
5214 void setUF(unsigned UF) {
5215 assert(hasUF(UF) && "Cannot set the UF not already in plan");
5216 UFs.clear();
5217 UFs.insert(X: UF);
5218 }
5219
5220 /// Returns true if the VPlan already has been unrolled, i.e. it has a single
5221 /// concrete UF.
5222 bool isUnrolled() const { return UFs.size() == 1; }
5223
5224 /// Return a string with the name of the plan and the applicable VFs and UFs.
5225 std::string getName() const;
5226
5227 void setName(const Twine &newName) { Name = newName.str(); }
5228
5229 /// Gets the live-in VPIRValue for \p V or adds a new live-in (if none exists
5230 /// yet) for \p V.
5231 VPIRValue *getOrAddLiveIn(Value *V) {
5232 assert(V && "Trying to get or add the VPIRValue of a null Value");
5233 auto [It, Inserted] = LiveIns.try_emplace(Key: V);
5234 if (Inserted) {
5235 if (auto *CI = dyn_cast<ConstantInt>(Val: V))
5236 It->second = new VPConstantInt(CI);
5237 else
5238 It->second = new VPIRValue(V);
5239 }
5240
5241 assert(isa<VPIRValue>(It->second) &&
5242 "Only VPIRValues should be in mapping");
5243 return It->second;
5244 }
5245 VPIRValue *getOrAddLiveIn(VPIRValue *V) {
5246 assert(V && "Trying to get or add the VPIRValue of a null VPIRValue");
5247 return getOrAddLiveIn(V: V->getValue());
5248 }
5249
5250 /// Return a VPIRValue wrapping i1 true.
5251 VPIRValue *getTrue() { return getConstantInt(BitWidth: 1, Val: 1); }
5252
5253 /// Return a VPIRValue wrapping i1 false.
5254 VPIRValue *getFalse() { return getConstantInt(BitWidth: 1, Val: 0); }
5255
5256 /// Return a VPIRValue wrapping the null value of type \p Ty.
5257 VPIRValue *getZero(Type *Ty) { return getConstantInt(Ty, Val: 0); }
5258
5259 /// Return a VPIRValue wrapping the AllOnes value of type \p Ty.
5260 VPIRValue *getAllOnesValue(Type *Ty) {
5261 return getConstantInt(Val: APInt::getAllOnes(numBits: Ty->getIntegerBitWidth()));
5262 }
5263
5264 /// Return a VPIRValue wrapping a ConstantInt with the given type and value.
5265 VPIRValue *getConstantInt(Type *Ty, uint64_t Val, bool IsSigned = false) {
5266 return getOrAddLiveIn(V: ConstantInt::get(Ty, V: Val, IsSigned));
5267 }
5268
5269 /// Return a VPIRValue wrapping a ConstantInt with the given bitwidth and
5270 /// value.
5271 VPIRValue *getConstantInt(unsigned BitWidth, uint64_t Val,
5272 bool IsSigned = false) {
5273 return getConstantInt(Val: APInt(BitWidth, Val, IsSigned));
5274 }
5275
5276 /// Return a VPIRValue wrapping a ConstantInt with the given APInt value.
5277 VPIRValue *getConstantInt(const APInt &Val) {
5278 return getOrAddLiveIn(V: ConstantInt::get(Context&: getContext(), V: Val));
5279 }
5280
5281 /// Return a VPIRValue wrapping a poison value of type \p Ty.
5282 VPIRValue *getPoison(Type *Ty) {
5283 return getOrAddLiveIn(V: PoisonValue::get(T: Ty));
5284 }
5285
5286 /// Return the live-in VPIRValue for \p V, if there is one or nullptr
5287 /// otherwise.
5288 VPIRValue *getLiveIn(Value *V) const { return LiveIns.lookup(Key: V); }
5289
5290 /// Return the list of live-in VPValues available in the VPlan.
5291 auto getLiveIns() const { return LiveIns.values(); }
5292
5293#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5294 /// Print the live-ins of this VPlan to \p O.
5295 void printLiveIns(raw_ostream &O) const;
5296
5297 /// Print this VPlan to \p O.
5298 LLVM_ABI_FOR_TEST void print(raw_ostream &O) const;
5299
5300 /// Print this VPlan in DOT format to \p O.
5301 LLVM_ABI_FOR_TEST void printDOT(raw_ostream &O) const;
5302
5303 /// Dump the plan to stderr (for debugging).
5304 LLVM_DUMP_METHOD void dump() const;
5305#endif
5306
5307 /// Clone the current VPlan, update all VPValues of the new VPlan and cloned
5308 /// recipes to refer to the clones, and return it.
5309 LLVM_ABI_FOR_TEST VPlan *duplicate();
5310
5311 /// Create a new VPBasicBlock with \p Name and containing \p Recipe if
5312 /// present. The returned block is owned by the VPlan and deleted once the
5313 /// VPlan is destroyed.
5314 VPBasicBlock *createVPBasicBlock(const Twine &Name,
5315 VPRecipeBase *Recipe = nullptr) {
5316 auto *VPB = new VPBasicBlock(Name, Recipe);
5317 VPB->setPlan(this);
5318 VPB->setNumber(CreatedBlocks.size());
5319 CreatedBlocks.push_back(Elt: VPB);
5320 return VPB;
5321 }
5322
5323 /// Create a new loop region with a canonical IV using \p CanIVTy and
5324 /// \p DL. Use \p Name as the region's name and set entry and exiting blocks
5325 /// to \p Entry and \p Exiting respectively, if provided. The returned block
5326 /// is owned by the VPlan and deleted once the VPlan is destroyed.
5327 VPRegionBlock *createLoopRegion(Type *CanIVTy, DebugLoc DL,
5328 const std::string &Name = "",
5329 VPBlockBase *Entry = nullptr,
5330 VPBlockBase *Exiting = nullptr) {
5331 auto *VPB = new VPRegionBlock(CanIVTy, DL, Entry, Exiting, Name);
5332 VPB->setPlan(this);
5333 VPB->setNumber(CreatedBlocks.size());
5334 CreatedBlocks.push_back(Elt: VPB);
5335 return VPB;
5336 }
5337
5338 /// Create a new replicate region with \p Entry, \p Exiting and \p Name. The
5339 /// returned block is owned by the VPlan and deleted once the VPlan is
5340 /// destroyed.
5341 VPRegionBlock *createReplicateRegion(VPBlockBase *Entry, VPBlockBase *Exiting,
5342 const std::string &Name = "") {
5343 auto *VPB = new VPRegionBlock(Entry, Exiting, Name);
5344 VPB->setPlan(this);
5345 VPB->setNumber(CreatedBlocks.size());
5346 CreatedBlocks.push_back(Elt: VPB);
5347 return VPB;
5348 }
5349
5350 /// Create a VPIRBasicBlock wrapping \p IRBB, but do not create
5351 /// VPIRInstructions wrapping the instructions in t\p IRBB. The returned
5352 /// block is owned by the VPlan and deleted once the VPlan is destroyed.
5353 VPIRBasicBlock *createEmptyVPIRBasicBlock(BasicBlock *IRBB);
5354
5355 /// Create a VPIRBasicBlock from \p IRBB containing VPIRInstructions for all
5356 /// instructions in \p IRBB, except its terminator which is managed by the
5357 /// successors of the block in VPlan. The returned block is owned by the VPlan
5358 /// and deleted once the VPlan is destroyed.
5359 LLVM_ABI_FOR_TEST VPIRBasicBlock *createVPIRBasicBlock(BasicBlock *IRBB);
5360
5361 unsigned getMaxBlockNumber() const { return CreatedBlocks.size(); }
5362
5363 /// Returns true if the VPlan is based on a loop with an early exit. Must be
5364 /// called before regions are dissolved.
5365 bool hasEarlyExit() const {
5366 // An early exit plan uses BranchOnTwoConds in the vector loop region latch.
5367 const VPRegionBlock *LoopRegion = getVectorLoopRegion();
5368 assert(LoopRegion && "vector loop region already dissolved");
5369 return LoopRegion->getNumSuccessors() > 1;
5370 }
5371
5372 /// Returns true if the scalar tail may execute after the vector loop, i.e.
5373 /// if the middle block is a predecessor of the scalar preheader. Note that
5374 /// this relies on unneeded branches to the scalar tail loop being removed.
5375 bool hasScalarTail() const {
5376 auto *ScalarPH = getScalarPreheader();
5377 return ScalarPH &&
5378 is_contained(Range&: ScalarPH->getPredecessors(), Element: getMiddleBlock());
5379 }
5380
5381 /// The type of the canonical induction variable of the vector loop.
5382 Type *getIndexType() const { return VF.getType(); }
5383};
5384
5385#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5386inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) {
5387 Plan.print(OS);
5388 return OS;
5389}
5390#endif
5391
5392} // end namespace llvm
5393
5394#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
5395