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