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