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