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