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