LLVM 17.0.0git
VPlan.h
Go to the documentation of this file.
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. VPInstruction, a concrete Recipe and VPUser modeling a single planned
16/// instruction;
17/// 4. The VPlan class holding a candidate for vectorization;
18/// 5. The VPlanPrinter class providing a way to print a plan in dot format;
19/// These are documented in docs/VectorizationPlan.rst.
20//
21//===----------------------------------------------------------------------===//
22
23#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
24#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
25
26#include "VPlanValue.h"
27#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/MapVector.h"
32#include "llvm/ADT/Twine.h"
33#include "llvm/ADT/ilist.h"
34#include "llvm/ADT/ilist_node.h"
38#include "llvm/IR/DebugLoc.h"
39#include "llvm/IR/FMF.h"
40#include "llvm/IR/Operator.h"
41#include <algorithm>
42#include <cassert>
43#include <cstddef>
44#include <string>
45
46namespace llvm {
47
48class BasicBlock;
49class DominatorTree;
50class InnerLoopVectorizer;
51class IRBuilderBase;
52class LoopInfo;
53class PredicateScalarEvolution;
54class raw_ostream;
55class RecurrenceDescriptor;
56class SCEV;
57class Type;
58class VPBasicBlock;
59class VPRegionBlock;
60class VPlan;
61class VPReplicateRecipe;
62class VPlanSlp;
63class Value;
64class LoopVersioning;
65
66namespace Intrinsic {
67typedef unsigned ID;
68}
69
70/// Returns a calculation for the total number of elements for a given \p VF.
71/// For fixed width vectors this value is a constant, whereas for scalable
72/// vectors it is an expression determined at runtime.
73Value *getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF);
74
75/// Return a value for Step multiplied by VF.
76Value *createStepForVF(IRBuilderBase &B, Type *Ty, ElementCount VF,
77 int64_t Step);
78
79const SCEV *createTripCountSCEV(Type *IdxTy, PredicatedScalarEvolution &PSE,
80 Loop *CurLoop = nullptr);
81
82/// A range of powers-of-2 vectorization factors with fixed start and
83/// adjustable end. The range includes start and excludes end, e.g.,:
84/// [1, 16) = {1, 2, 4, 8}
85struct VFRange {
86 // A power of 2.
88
89 // A power of 2. If End <= Start range is empty.
91
92 bool isEmpty() const {
94 }
95
97 : Start(Start), End(End) {
99 "Both Start and End should have the same scalable flag");
101 "Expected Start to be a power of 2");
103 "Expected End to be a power of 2");
104 }
105
106 /// Iterator to iterate over vectorization factors in a VFRange.
108 : public iterator_facade_base<iterator, std::forward_iterator_tag,
109 ElementCount> {
110 ElementCount VF;
111
112 public:
113 iterator(ElementCount VF) : VF(VF) {}
114
115 bool operator==(const iterator &Other) const { return VF == Other.VF; }
116
117 ElementCount operator*() const { return VF; }
118
120 VF *= 2;
121 return *this;
122 }
123 };
124
128 return iterator(End);
129 }
130};
131
132using VPlanPtr = std::unique_ptr<VPlan>;
133
134/// In what follows, the term "input IR" refers to code that is fed into the
135/// vectorizer whereas the term "output IR" refers to code that is generated by
136/// the vectorizer.
137
138/// VPLane provides a way to access lanes in both fixed width and scalable
139/// vectors, where for the latter the lane index sometimes needs calculating
140/// as a runtime expression.
141class VPLane {
142public:
143 /// Kind describes how to interpret Lane.
144 enum class Kind : uint8_t {
145 /// For First, Lane is the index into the first N elements of a
146 /// fixed-vector <N x <ElTy>> or a scalable vector <vscale x N x <ElTy>>.
147 First,
148 /// For ScalableLast, Lane is the offset from the start of the last
149 /// N-element subvector in a scalable vector <vscale x N x <ElTy>>. For
150 /// example, a Lane of 0 corresponds to lane `(vscale - 1) * N`, a Lane of
151 /// 1 corresponds to `((vscale - 1) * N) + 1`, etc.
153 };
154
155private:
156 /// in [0..VF)
157 unsigned Lane;
158
159 /// Indicates how the Lane should be interpreted, as described above.
160 Kind LaneKind;
161
162public:
163 VPLane(unsigned Lane, Kind LaneKind) : Lane(Lane), LaneKind(LaneKind) {}
164
166
168 unsigned LaneOffset = VF.getKnownMinValue() - 1;
169 Kind LaneKind;
170 if (VF.isScalable())
171 // In this case 'LaneOffset' refers to the offset from the start of the
172 // last subvector with VF.getKnownMinValue() elements.
174 else
175 LaneKind = VPLane::Kind::First;
176 return VPLane(LaneOffset, LaneKind);
177 }
178
179 /// Returns a compile-time known value for the lane index and asserts if the
180 /// lane can only be calculated at runtime.
181 unsigned getKnownLane() const {
182 assert(LaneKind == Kind::First);
183 return Lane;
184 }
185
186 /// Returns an expression describing the lane index that can be used at
187 /// runtime.
188 Value *getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const;
189
190 /// Returns the Kind of lane offset.
191 Kind getKind() const { return LaneKind; }
192
193 /// Returns true if this is the first lane of the whole vector.
194 bool isFirstLane() const { return Lane == 0 && LaneKind == Kind::First; }
195
196 /// Maps the lane to a cache index based on \p VF.
197 unsigned mapToCacheIndex(const ElementCount &VF) const {
198 switch (LaneKind) {
200 assert(VF.isScalable() && Lane < VF.getKnownMinValue());
201 return VF.getKnownMinValue() + Lane;
202 default:
203 assert(Lane < VF.getKnownMinValue());
204 return Lane;
205 }
206 }
207
208 /// Returns the maxmimum number of lanes that we are able to consider
209 /// caching for \p VF.
210 static unsigned getNumCachedLanes(const ElementCount &VF) {
211 return VF.getKnownMinValue() * (VF.isScalable() ? 2 : 1);
212 }
213};
214
215/// VPIteration represents a single point in the iteration space of the output
216/// (vectorized and/or unrolled) IR loop.
218 /// in [0..UF)
219 unsigned Part;
220
222
223 VPIteration(unsigned Part, unsigned Lane,
225 : Part(Part), Lane(Lane, Kind) {}
226
227 VPIteration(unsigned Part, const VPLane &Lane) : Part(Part), Lane(Lane) {}
228
229 bool isFirstIteration() const { return Part == 0 && Lane.isFirstLane(); }
230};
231
232/// VPTransformState holds information passed down when "executing" a VPlan,
233/// needed for generating the output IR.
238 : VF(VF), UF(UF), LI(LI), DT(DT), Builder(Builder), ILV(ILV), Plan(Plan),
239 LVer(nullptr) {}
240
241 /// The chosen Vectorization and Unroll Factors of the loop being vectorized.
243 unsigned UF;
244
245 /// Hold the indices to generate specific scalar instructions. Null indicates
246 /// that all instances are to be generated, using either scalar or vector
247 /// instructions.
248 std::optional<VPIteration> Instance;
249
250 struct DataState {
251 /// A type for vectorized values in the new loop. Each value from the
252 /// original loop, when vectorized, is represented by UF vector values in
253 /// the new unrolled loop, where UF is the unroll factor.
255
257
261
262 /// Get the generated Value for a given VPValue and a given Part. Note that
263 /// as some Defs are still created by ILV and managed in its ValueMap, this
264 /// method will delegate the call to ILV in such cases in order to provide
265 /// callers a consistent API.
266 /// \see set.
267 Value *get(VPValue *Def, unsigned Part);
268
269 /// Get the generated Value for a given VPValue and given Part and Lane.
270 Value *get(VPValue *Def, const VPIteration &Instance);
271
272 bool hasVectorValue(VPValue *Def, unsigned Part) {
273 auto I = Data.PerPartOutput.find(Def);
274 return I != Data.PerPartOutput.end() && Part < I->second.size() &&
275 I->second[Part];
276 }
277
278 bool hasAnyVectorValue(VPValue *Def) const {
279 return Data.PerPartOutput.contains(Def);
280 }
281
283 auto I = Data.PerPartScalars.find(Def);
284 if (I == Data.PerPartScalars.end())
285 return false;
286 unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
287 return Instance.Part < I->second.size() &&
288 CacheIdx < I->second[Instance.Part].size() &&
289 I->second[Instance.Part][CacheIdx];
290 }
291
292 /// Set the generated Value for a given VPValue and a given Part.
293 void set(VPValue *Def, Value *V, unsigned Part) {
294 if (!Data.PerPartOutput.count(Def)) {
296 Data.PerPartOutput[Def] = Entry;
297 }
298 Data.PerPartOutput[Def][Part] = V;
299 }
300 /// Reset an existing vector value for \p Def and a given \p Part.
301 void reset(VPValue *Def, Value *V, unsigned Part) {
302 auto Iter = Data.PerPartOutput.find(Def);
303 assert(Iter != Data.PerPartOutput.end() &&
304 "need to overwrite existing value");
305 Iter->second[Part] = V;
306 }
307
308 /// Set the generated scalar \p V for \p Def and the given \p Instance.
309 void set(VPValue *Def, Value *V, const VPIteration &Instance) {
310 auto Iter = Data.PerPartScalars.insert({Def, {}});
311 auto &PerPartVec = Iter.first->second;
312 while (PerPartVec.size() <= Instance.Part)
313 PerPartVec.emplace_back();
314 auto &Scalars = PerPartVec[Instance.Part];
315 unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
316 while (Scalars.size() <= CacheIdx)
317 Scalars.push_back(nullptr);
318 assert(!Scalars[CacheIdx] && "should overwrite existing value");
319 Scalars[CacheIdx] = V;
320 }
321
322 /// Reset an existing scalar value for \p Def and a given \p Instance.
323 void reset(VPValue *Def, Value *V, const VPIteration &Instance) {
324 auto Iter = Data.PerPartScalars.find(Def);
325 assert(Iter != Data.PerPartScalars.end() &&
326 "need to overwrite existing value");
327 assert(Instance.Part < Iter->second.size() &&
328 "need to overwrite existing value");
329 unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
330 assert(CacheIdx < Iter->second[Instance.Part].size() &&
331 "need to overwrite existing value");
332 Iter->second[Instance.Part][CacheIdx] = V;
333 }
334
335 /// Add additional metadata to \p To that was not present on \p Orig.
336 ///
337 /// Currently this is used to add the noalias annotations based on the
338 /// inserted memchecks. Use this for instructions that are *cloned* into the
339 /// vector loop.
340 void addNewMetadata(Instruction *To, const Instruction *Orig);
341
342 /// Add metadata from one instruction to another.
343 ///
344 /// This includes both the original MDs from \p From and additional ones (\see
345 /// addNewMetadata). Use this for *newly created* instructions in the vector
346 /// loop.
348
349 /// Similar to the previous function but it adds the metadata to a
350 /// vector of instructions.
352
353 /// Set the debug location in the builder using the debug location in \p V.
354 void setDebugLocFromInst(const Value *V);
355
356 /// Hold state information used when constructing the CFG of the output IR,
357 /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
358 struct CFGState {
359 /// The previous VPBasicBlock visited. Initially set to null.
361
362 /// The previous IR BasicBlock created or used. Initially set to the new
363 /// header BasicBlock.
364 BasicBlock *PrevBB = nullptr;
365
366 /// The last IR BasicBlock in the output IR. Set to the exit block of the
367 /// vector loop.
368 BasicBlock *ExitBB = nullptr;
369
370 /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
371 /// of replication, maps the BasicBlock of the last replica created.
373
374 CFGState() = default;
375
376 /// Returns the BasicBlock* mapped to the pre-header of the loop region
377 /// containing \p R.
380
381 /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
383
384 /// Hold a pointer to Dominator Tree to register new basic blocks in the loop.
386
387 /// Hold a reference to the IRBuilder used to generate output IR code.
389
391
392 /// Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
393 Value *CanonicalIV = nullptr;
394
395 /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
397
398 /// Pointer to the VPlan code is generated for.
400
401 /// The loop object for the current parent region, or nullptr.
403
404 /// LoopVersioning. It's only set up (non-null) if memchecks were
405 /// used.
406 ///
407 /// This is currently only used to add no-alias metadata based on the
408 /// memchecks. The actually versioning is performed manually.
410
411 /// Map SCEVs to their expanded values. Populated when executing
412 /// VPExpandSCEVRecipes.
414};
415
416/// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
417/// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
419 friend class VPBlockUtils;
420
421 const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
422
423 /// An optional name for the block.
424 std::string Name;
425
426 /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
427 /// it is a topmost VPBlockBase.
428 VPRegionBlock *Parent = nullptr;
429
430 /// List of predecessor blocks.
432
433 /// List of successor blocks.
435
436 /// VPlan containing the block. Can only be set on the entry block of the
437 /// plan.
438 VPlan *Plan = nullptr;
439
440 /// Add \p Successor as the last successor to this block.
441 void appendSuccessor(VPBlockBase *Successor) {
442 assert(Successor && "Cannot add nullptr successor!");
443 Successors.push_back(Successor);
444 }
445
446 /// Add \p Predecessor as the last predecessor to this block.
447 void appendPredecessor(VPBlockBase *Predecessor) {
448 assert(Predecessor && "Cannot add nullptr predecessor!");
449 Predecessors.push_back(Predecessor);
450 }
451
452 /// Remove \p Predecessor from the predecessors of this block.
453 void removePredecessor(VPBlockBase *Predecessor) {
454 auto Pos = find(Predecessors, Predecessor);
455 assert(Pos && "Predecessor does not exist");
456 Predecessors.erase(Pos);
457 }
458
459 /// Remove \p Successor from the successors of this block.
460 void removeSuccessor(VPBlockBase *Successor) {
461 auto Pos = find(Successors, Successor);
462 assert(Pos && "Successor does not exist");
463 Successors.erase(Pos);
464 }
465
466protected:
467 VPBlockBase(const unsigned char SC, const std::string &N)
468 : SubclassID(SC), Name(N) {}
469
470public:
471 /// An enumeration for keeping track of the concrete subclass of VPBlockBase
472 /// that are actually instantiated. Values of this enumeration are kept in the
473 /// SubclassID field of the VPBlockBase objects. They are used for concrete
474 /// type identification.
475 using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
476
478
479 virtual ~VPBlockBase() = default;
480
481 const std::string &getName() const { return Name; }
482
483 void setName(const Twine &newName) { Name = newName.str(); }
484
485 /// \return an ID for the concrete type of this object.
486 /// This is used to implement the classof checks. This should not be used
487 /// for any other purpose, as the values may change as LLVM evolves.
488 unsigned getVPBlockID() const { return SubclassID; }
489
490 VPRegionBlock *getParent() { return Parent; }
491 const VPRegionBlock *getParent() const { return Parent; }
492
493 /// \return A pointer to the plan containing the current block.
494 VPlan *getPlan();
495 const VPlan *getPlan() const;
496
497 /// Sets the pointer of the plan containing the block. The block must be the
498 /// entry block into the VPlan.
499 void setPlan(VPlan *ParentPlan);
500
501 void setParent(VPRegionBlock *P) { Parent = P; }
502
503 /// \return the VPBasicBlock that is the entry of this VPBlockBase,
504 /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
505 /// VPBlockBase is a VPBasicBlock, it is returned.
506 const VPBasicBlock *getEntryBasicBlock() const;
508
509 /// \return the VPBasicBlock that is the exiting this VPBlockBase,
510 /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
511 /// VPBlockBase is a VPBasicBlock, it is returned.
512 const VPBasicBlock *getExitingBasicBlock() const;
514
515 const VPBlocksTy &getSuccessors() const { return Successors; }
516 VPBlocksTy &getSuccessors() { return Successors; }
517
519
520 const VPBlocksTy &getPredecessors() const { return Predecessors; }
521 VPBlocksTy &getPredecessors() { return Predecessors; }
522
523 /// \return the successor of this VPBlockBase if it has a single successor.
524 /// Otherwise return a null pointer.
526 return (Successors.size() == 1 ? *Successors.begin() : nullptr);
527 }
528
529 /// \return the predecessor of this VPBlockBase if it has a single
530 /// predecessor. Otherwise return a null pointer.
532 return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
533 }
534
535 size_t getNumSuccessors() const { return Successors.size(); }
536 size_t getNumPredecessors() const { return Predecessors.size(); }
537
538 /// An Enclosing Block of a block B is any block containing B, including B
539 /// itself. \return the closest enclosing block starting from "this", which
540 /// has successors. \return the root enclosing block if all enclosing blocks
541 /// have no successors.
543
544 /// \return the closest enclosing block starting from "this", which has
545 /// predecessors. \return the root enclosing block if all enclosing blocks
546 /// have no predecessors.
548
549 /// \return the successors either attached directly to this VPBlockBase or, if
550 /// this VPBlockBase is the exit block of a VPRegionBlock and has no
551 /// successors of its own, search recursively for the first enclosing
552 /// VPRegionBlock that has successors and return them. If no such
553 /// VPRegionBlock exists, return the (empty) successors of the topmost
554 /// VPBlockBase reached.
557 }
558
559 /// \return the hierarchical successor of this VPBlockBase if it has a single
560 /// hierarchical successor. Otherwise return a null pointer.
563 }
564
565 /// \return the predecessors either attached directly to this VPBlockBase or,
566 /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
567 /// predecessors of its own, search recursively for the first enclosing
568 /// VPRegionBlock that has predecessors and return them. If no such
569 /// VPRegionBlock exists, return the (empty) predecessors of the topmost
570 /// VPBlockBase reached.
573 }
574
575 /// \return the hierarchical predecessor of this VPBlockBase if it has a
576 /// single hierarchical predecessor. Otherwise return a null pointer.
579 }
580
581 /// Set a given VPBlockBase \p Successor as the single successor of this
582 /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
583 /// This VPBlockBase must have no successors.
585 assert(Successors.empty() && "Setting one successor when others exist.");
586 appendSuccessor(Successor);
587 }
588
589 /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
590 /// successors of this VPBlockBase. This VPBlockBase is not added as
591 /// predecessor of \p IfTrue or \p IfFalse. This VPBlockBase must have no
592 /// successors.
593 void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {
594 assert(Successors.empty() && "Setting two successors when others exist.");
595 appendSuccessor(IfTrue);
596 appendSuccessor(IfFalse);
597 }
598
599 /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
600 /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
601 /// as successor of any VPBasicBlock in \p NewPreds.
603 assert(Predecessors.empty() && "Block predecessors already set.");
604 for (auto *Pred : NewPreds)
605 appendPredecessor(Pred);
606 }
607
608 /// Remove all the predecessor of this block.
609 void clearPredecessors() { Predecessors.clear(); }
610
611 /// Remove all the successors of this block.
612 void clearSuccessors() { Successors.clear(); }
613
614 /// The method which generates the output IR that correspond to this
615 /// VPBlockBase, thereby "executing" the VPlan.
616 virtual void execute(VPTransformState *State) = 0;
617
618 /// Delete all blocks reachable from a given VPBlockBase, inclusive.
619 static void deleteCFG(VPBlockBase *Entry);
620
621 /// Return true if it is legal to hoist instructions into this block.
623 // There are currently no constraints that prevent an instruction to be
624 // hoisted into a VPBlockBase.
625 return true;
626 }
627
628 /// Replace all operands of VPUsers in the block with \p NewValue and also
629 /// replaces all uses of VPValues defined in the block with NewValue.
630 virtual void dropAllReferences(VPValue *NewValue) = 0;
631
632#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
633 void printAsOperand(raw_ostream &OS, bool PrintType) const {
634 OS << getName();
635 }
636
637 /// Print plain-text dump of this VPBlockBase to \p O, prefixing all lines
638 /// with \p Indent. \p SlotTracker is used to print unnamed VPValue's using
639 /// consequtive numbers.
640 ///
641 /// Note that the numbering is applied to the whole VPlan, so printing
642 /// individual blocks is consistent with the whole VPlan printing.
643 virtual void print(raw_ostream &O, const Twine &Indent,
644 VPSlotTracker &SlotTracker) const = 0;
645
646 /// Print plain-text dump of this VPlan to \p O.
647 void print(raw_ostream &O) const {
649 print(O, "", SlotTracker);
650 }
651
652 /// Print the successors of this block to \p O, prefixing all lines with \p
653 /// Indent.
654 void printSuccessors(raw_ostream &O, const Twine &Indent) const;
655
656 /// Dump this VPBlockBase to dbgs().
657 LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
658#endif
659};
660
661/// A value that is used outside the VPlan. The operand of the user needs to be
662/// added to the associated LCSSA phi node.
663class VPLiveOut : public VPUser {
664 PHINode *Phi;
665
666public:
668 : VPUser({Op}, VPUser::VPUserID::LiveOut), Phi(Phi) {}
669
670 static inline bool classof(const VPUser *U) {
671 return U->getVPUserID() == VPUser::VPUserID::LiveOut;
672 }
673
674 /// Fixup the wrapped LCSSA phi node in the unique exit block. This simply
675 /// means we need to add the appropriate incoming value from the middle
676 /// block as exiting edges from the scalar epilogue loop (if present) are
677 /// already in place, and we exit the vector loop exclusively to the middle
678 /// block.
679 void fixPhi(VPlan &Plan, VPTransformState &State);
680
681 /// Returns true if the VPLiveOut uses scalars of operand \p Op.
682 bool usesScalars(const VPValue *Op) const override {
684 "Op must be an operand of the recipe");
685 return true;
686 }
687
688 PHINode *getPhi() const { return Phi; }
689
690#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
691 /// Print the VPLiveOut to \p O.
693#endif
694};
695
696/// VPRecipeBase is a base class modeling a sequence of one or more output IR
697/// instructions. VPRecipeBase owns the the VPValues it defines through VPDef
698/// and is responsible for deleting its defined values. Single-value
699/// VPRecipeBases that also inherit from VPValue must make sure to inherit from
700/// VPRecipeBase before VPValue.
701class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,
702 public VPDef,
703 public VPUser {
704 friend VPBasicBlock;
705 friend class VPBlockUtils;
706
707 /// Each VPRecipe belongs to a single VPBasicBlock.
708 VPBasicBlock *Parent = nullptr;
709
710public:
713
714 template <typename IterT>
717 virtual ~VPRecipeBase() = default;
718
719 /// \return the VPBasicBlock which this VPRecipe belongs to.
720 VPBasicBlock *getParent() { return Parent; }
721 const VPBasicBlock *getParent() const { return Parent; }
722
723 /// The method which generates the output IR instructions that correspond to
724 /// this VPRecipe, thereby "executing" the VPlan.
725 virtual void execute(VPTransformState &State) = 0;
726
727 /// Insert an unlinked recipe into a basic block immediately before
728 /// the specified recipe.
729 void insertBefore(VPRecipeBase *InsertPos);
730 /// Insert an unlinked recipe into \p BB immediately before the insertion
731 /// point \p IP;
733
734 /// Insert an unlinked Recipe into a basic block immediately after
735 /// the specified Recipe.
736 void insertAfter(VPRecipeBase *InsertPos);
737
738 /// Unlink this recipe from its current VPBasicBlock and insert it into
739 /// the VPBasicBlock that MovePos lives in, right after MovePos.
740 void moveAfter(VPRecipeBase *MovePos);
741
742 /// Unlink this recipe and insert into BB before I.
743 ///
744 /// \pre I is a valid iterator into BB.
746
747 /// This method unlinks 'this' from the containing basic block, but does not
748 /// delete it.
749 void removeFromParent();
750
751 /// This method unlinks 'this' from the containing basic block and deletes it.
752 ///
753 /// \returns an iterator pointing to the element after the erased one
755
756 /// Returns the underlying instruction, if the recipe is a VPValue or nullptr
757 /// otherwise.
759 return cast<Instruction>(getVPSingleValue()->getUnderlyingValue());
760 }
762 return cast<Instruction>(getVPSingleValue()->getUnderlyingValue());
763 }
764
765 /// Method to support type inquiry through isa, cast, and dyn_cast.
766 static inline bool classof(const VPDef *D) {
767 // All VPDefs are also VPRecipeBases.
768 return true;
769 }
770
771 static inline bool classof(const VPUser *U) {
772 return U->getVPUserID() == VPUser::VPUserID::Recipe;
773 }
774
775 /// Returns true if the recipe may have side-effects.
776 bool mayHaveSideEffects() const;
777
778 /// Returns true for PHI-like recipes.
779 bool isPhi() const {
780 return getVPDefID() >= VPFirstPHISC && getVPDefID() <= VPLastPHISC;
781 }
782
783 /// Returns true if the recipe may read from memory.
784 bool mayReadFromMemory() const;
785
786 /// Returns true if the recipe may write to memory.
787 bool mayWriteToMemory() const;
788
789 /// Returns true if the recipe may read from or write to memory.
790 bool mayReadOrWriteMemory() const {
792 }
793};
794
795// Helper macro to define common classof implementations for recipes.
796#define VP_CLASSOF_IMPL(VPDefID) \
797 static inline bool classof(const VPDef *D) { \
798 return D->getVPDefID() == VPDefID; \
799 } \
800 static inline bool classof(const VPValue *V) { \
801 auto *R = V->getDefiningRecipe(); \
802 return R && R->getVPDefID() == VPDefID; \
803 } \
804 static inline bool classof(const VPUser *U) { \
805 auto *R = dyn_cast<VPRecipeBase>(U); \
806 return R && R->getVPDefID() == VPDefID; \
807 } \
808 static inline bool classof(const VPRecipeBase *R) { \
809 return R->getVPDefID() == VPDefID; \
810 }
811
812/// This is a concrete Recipe that models a single VPlan-level instruction.
813/// While as any Recipe it may generate a sequence of IR instructions when
814/// executed, these instructions would always form a single-def expression as
815/// the VPInstruction is also a single def-use vertex.
816class VPInstruction : public VPRecipeBase, public VPValue {
817 friend class VPlanSlp;
818
819public:
820 /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
821 enum {
823 Instruction::OtherOpsEnd + 1, // Combines the incoming and previous
824 // values of a first-order recurrence.
833 // The next two are similar to the above, but instead increment the
834 // canonical IV separately for each unrolled part.
839 };
840
841private:
842 typedef unsigned char OpcodeTy;
843 OpcodeTy Opcode;
844 FastMathFlags FMF;
845 DebugLoc DL;
846
847 /// An optional name that can be used for the generated IR instruction.
848 const std::string Name;
849
850 /// Utility method serving execute(): generates a single instance of the
851 /// modeled instruction.
852 void generateInstruction(VPTransformState &State, unsigned Part);
853
854protected:
856
857public:
859 const Twine &Name = "")
860 : VPRecipeBase(VPDef::VPInstructionSC, Operands), VPValue(this),
861 Opcode(Opcode), DL(DL), Name(Name.str()) {}
862
863 VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands,
864 DebugLoc DL = {}, const Twine &Name = "")
866
867 VP_CLASSOF_IMPL(VPDef::VPInstructionSC)
868
871 return new VPInstruction(Opcode, Operands, DL, Name);
872 }
873
874 unsigned getOpcode() const { return Opcode; }
875
876 /// Generate the instruction.
877 /// TODO: We currently execute only per-part unless a specific instance is
878 /// provided.
879 void execute(VPTransformState &State) override;
880
881#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
882 /// Print the VPInstruction to \p O.
883 void print(raw_ostream &O, const Twine &Indent,
884 VPSlotTracker &SlotTracker) const override;
885
886 /// Print the VPInstruction to dbgs() (for debugging).
887 LLVM_DUMP_METHOD void dump() const;
888#endif
889
890 /// Return true if this instruction may modify memory.
891 bool mayWriteToMemory() const {
892 // TODO: we can use attributes of the called function to rule out memory
893 // modifications.
894 return Opcode == Instruction::Store || Opcode == Instruction::Call ||
895 Opcode == Instruction::Invoke || Opcode == SLPStore;
896 }
897
898 bool hasResult() const {
899 // CallInst may or may not have a result, depending on the called function.
900 // Conservatively return calls have results for now.
901 switch (getOpcode()) {
902 case Instruction::Ret:
903 case Instruction::Br:
904 case Instruction::Store:
905 case Instruction::Switch:
906 case Instruction::IndirectBr:
907 case Instruction::Resume:
908 case Instruction::CatchRet:
909 case Instruction::Unreachable:
910 case Instruction::Fence:
911 case Instruction::AtomicRMW:
914 return false;
915 default:
916 return true;
917 }
918 }
919
920 /// Set the fast-math flags.
921 void setFastMathFlags(FastMathFlags FMFNew);
922
923 /// Returns true if the recipe only uses the first lane of operand \p Op.
924 bool onlyFirstLaneUsed(const VPValue *Op) const override {
926 "Op must be an operand of the recipe");
927 if (getOperand(0) != Op)
928 return false;
929 switch (getOpcode()) {
930 default:
931 return false;
939 return true;
940 };
941 llvm_unreachable("switch should return");
942 }
943};
944
945/// Class to record LLVM IR flag for a recipe along with it.
947 enum class OperationType : unsigned char {
948 OverflowingBinOp,
949 PossiblyExactOp,
950 GEPOp,
951 FPMathOp,
952 Other
953 };
954 struct WrapFlagsTy {
955 char HasNUW : 1;
956 char HasNSW : 1;
957 };
958 struct ExactFlagsTy {
959 char IsExact : 1;
960 };
961 struct GEPFlagsTy {
962 char IsInBounds : 1;
963 };
964 struct FastMathFlagsTy {
965 char AllowReassoc : 1;
966 char NoNaNs : 1;
967 char NoInfs : 1;
968 char NoSignedZeros : 1;
969 char AllowReciprocal : 1;
970 char AllowContract : 1;
971 char ApproxFunc : 1;
972 };
973
974 OperationType OpType;
975
976 union {
977 WrapFlagsTy WrapFlags;
978 ExactFlagsTy ExactFlags;
979 GEPFlagsTy GEPFlags;
980 FastMathFlagsTy FMFs;
981 unsigned char AllFlags;
982 };
983
984public:
985 template <typename IterT>
986 VPRecipeWithIRFlags(const unsigned char SC, iterator_range<IterT> Operands)
987 : VPRecipeBase(SC, Operands) {
988 OpType = OperationType::Other;
989 AllFlags = 0;
990 }
991
992 template <typename IterT>
993 VPRecipeWithIRFlags(const unsigned char SC, iterator_range<IterT> Operands,
994 Instruction &I)
996 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(&I)) {
997 OpType = OperationType::OverflowingBinOp;
998 WrapFlags.HasNUW = Op->hasNoUnsignedWrap();
999 WrapFlags.HasNSW = Op->hasNoSignedWrap();
1000 } else if (auto *Op = dyn_cast<PossiblyExactOperator>(&I)) {
1001 OpType = OperationType::PossiblyExactOp;
1002 ExactFlags.IsExact = Op->isExact();
1003 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1004 OpType = OperationType::GEPOp;
1005 GEPFlags.IsInBounds = GEP->isInBounds();
1006 } else if (auto *Op = dyn_cast<FPMathOperator>(&I)) {
1007 OpType = OperationType::FPMathOp;
1008 FastMathFlags FMF = Op->getFastMathFlags();
1009 FMFs.AllowReassoc = FMF.allowReassoc();
1010 FMFs.NoNaNs = FMF.noNaNs();
1011 FMFs.NoInfs = FMF.noInfs();
1012 FMFs.NoSignedZeros = FMF.noSignedZeros();
1013 FMFs.AllowReciprocal = FMF.allowReciprocal();
1014 FMFs.AllowContract = FMF.allowContract();
1015 FMFs.ApproxFunc = FMF.approxFunc();
1016 }
1017 }
1018
1019 static inline bool classof(const VPRecipeBase *R) {
1020 return R->getVPDefID() == VPRecipeBase::VPWidenSC ||
1021 R->getVPDefID() == VPRecipeBase::VPWidenGEPSC ||
1022 R->getVPDefID() == VPRecipeBase::VPReplicateSC;
1023 }
1024
1025 /// Drop all poison-generating flags.
1027 // NOTE: This needs to be kept in-sync with
1028 // Instruction::dropPoisonGeneratingFlags.
1029 switch (OpType) {
1030 case OperationType::OverflowingBinOp:
1031 WrapFlags.HasNUW = false;
1032 WrapFlags.HasNSW = false;
1033 break;
1034 case OperationType::PossiblyExactOp:
1035 ExactFlags.IsExact = false;
1036 break;
1037 case OperationType::GEPOp:
1038 GEPFlags.IsInBounds = false;
1039 break;
1040 case OperationType::FPMathOp:
1041 FMFs.NoNaNs = false;
1042 FMFs.NoInfs = false;
1043 break;
1044 case OperationType::Other:
1045 break;
1046 }
1047 }
1048
1049 /// Set the IR flags for \p I.
1050 void setFlags(Instruction *I) const {
1051 switch (OpType) {
1052 case OperationType::OverflowingBinOp:
1053 I->setHasNoUnsignedWrap(WrapFlags.HasNUW);
1054 I->setHasNoSignedWrap(WrapFlags.HasNSW);
1055 break;
1056 case OperationType::PossiblyExactOp:
1057 I->setIsExact(ExactFlags.IsExact);
1058 break;
1059 case OperationType::GEPOp:
1060 cast<GetElementPtrInst>(I)->setIsInBounds(GEPFlags.IsInBounds);
1061 break;
1062 case OperationType::FPMathOp:
1063 I->setHasAllowReassoc(FMFs.AllowReassoc);
1064 I->setHasNoNaNs(FMFs.NoNaNs);
1065 I->setHasNoInfs(FMFs.NoInfs);
1066 I->setHasNoSignedZeros(FMFs.NoSignedZeros);
1067 I->setHasAllowReciprocal(FMFs.AllowReciprocal);
1068 I->setHasAllowContract(FMFs.AllowContract);
1069 I->setHasApproxFunc(FMFs.ApproxFunc);
1070 break;
1071 case OperationType::Other:
1072 break;
1073 }
1074 }
1075
1076 bool isInBounds() const {
1077 assert(OpType == OperationType::GEPOp &&
1078 "recipe doesn't have inbounds flag");
1079 return GEPFlags.IsInBounds;
1080 }
1081
1082#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1084 FastMathFlags Res;
1085 Res.setAllowReassoc(FMFs.AllowReassoc);
1086 Res.setNoNaNs(FMFs.NoNaNs);
1087 Res.setNoInfs(FMFs.NoInfs);
1088 Res.setNoSignedZeros(FMFs.NoSignedZeros);
1089 Res.setAllowReciprocal(FMFs.AllowReciprocal);
1090 Res.setAllowContract(FMFs.AllowContract);
1091 Res.setApproxFunc(FMFs.ApproxFunc);
1092 return Res;
1093 }
1094
1095 void printFlags(raw_ostream &O) const;
1096#endif
1097};
1098
1099/// VPWidenRecipe is a recipe for producing a copy of vector type its
1100/// ingredient. This recipe covers most of the traditional vectorization cases
1101/// where each ingredient transforms into a vectorized version of itself.
1103
1104public:
1105 template <typename IterT>
1107 : VPRecipeWithIRFlags(VPDef::VPWidenSC, Operands, I), VPValue(this, &I) {}
1108
1109 ~VPWidenRecipe() override = default;
1110
1111 VP_CLASSOF_IMPL(VPDef::VPWidenSC)
1112
1113 /// Produce widened copies of all Ingredients.
1114 void execute(VPTransformState &State) override;
1115
1116#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1117 /// Print the recipe.
1118 void print(raw_ostream &O, const Twine &Indent,
1119 VPSlotTracker &SlotTracker) const override;
1120#endif
1121};
1122
1123/// VPWidenCastRecipe is a recipe to create vector cast instructions.
1125 /// Cast instruction opcode.
1126 Instruction::CastOps Opcode;
1127
1128 /// Result type for the cast.
1129 Type *ResultTy;
1130
1131public:
1133 CastInst *UI = nullptr)
1134 : VPRecipeBase(VPDef::VPWidenCastSC, Op), VPValue(this, UI),
1135 Opcode(Opcode), ResultTy(ResultTy) {
1136 assert((!UI || UI->getOpcode() == Opcode) &&
1137 "opcode of underlying cast doesn't match");
1138 assert((!UI || UI->getType() == ResultTy) &&
1139 "result type of underlying cast doesn't match");
1140 }
1141
1142 ~VPWidenCastRecipe() override = default;
1143
1144 VP_CLASSOF_IMPL(VPDef::VPWidenCastSC)
1145
1146 /// Produce widened copies of the cast.
1147 void execute(VPTransformState &State) override;
1148
1149#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1150 /// Print the recipe.
1151 void print(raw_ostream &O, const Twine &Indent,
1152 VPSlotTracker &SlotTracker) const override;
1153#endif
1154
1155 Instruction::CastOps getOpcode() const { return Opcode; }
1156
1157 /// Returns the result type of the cast.
1158 Type *getResultType() const { return ResultTy; }
1159};
1160
1161/// A recipe for widening Call instructions.
1163 /// ID of the vector intrinsic to call when widening the call. If set the
1164 /// Intrinsic::not_intrinsic, a library call will be used instead.
1165 Intrinsic::ID VectorIntrinsicID;
1166 /// If this recipe represents a library call, Variant stores a pointer to
1167 /// the chosen function. There is a 1:1 mapping between a given VF and the
1168 /// chosen vectorized variant, so there will be a different vplan for each
1169 /// VF with a valid variant.
1170 Function *Variant;
1171
1172public:
1173 template <typename IterT>
1175 Intrinsic::ID VectorIntrinsicID,
1176 Function *Variant = nullptr)
1177 : VPRecipeBase(VPDef::VPWidenCallSC, CallArguments), VPValue(this, &I),
1178 VectorIntrinsicID(VectorIntrinsicID), Variant(Variant) {}
1179
1180 ~VPWidenCallRecipe() override = default;
1181
1182 VP_CLASSOF_IMPL(VPDef::VPWidenCallSC)
1183
1184 /// Produce a widened version of the call instruction.
1185 void execute(VPTransformState &State) override;
1186
1187#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1188 /// Print the recipe.
1189 void print(raw_ostream &O, const Twine &Indent,
1190 VPSlotTracker &SlotTracker) const override;
1191#endif
1192};
1193
1194/// A recipe for widening select instructions.
1196 template <typename IterT>
1198 : VPRecipeBase(VPDef::VPWidenSelectSC, Operands), VPValue(this, &I) {}
1199
1200 ~VPWidenSelectRecipe() override = default;
1201
1202 VP_CLASSOF_IMPL(VPDef::VPWidenSelectSC)
1203
1204 /// Produce a widened version of the select instruction.
1205 void execute(VPTransformState &State) override;
1206
1207#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1208 /// Print the recipe.
1209 void print(raw_ostream &O, const Twine &Indent,
1210 VPSlotTracker &SlotTracker) const override;
1211#endif
1212
1213 VPValue *getCond() const {
1214 return getOperand(0);
1215 }
1216
1217 bool isInvariantCond() const {
1219 }
1220};
1221
1222/// A recipe for handling GEP instructions.
1224 bool isPointerLoopInvariant() const {
1226 }
1227
1228 bool isIndexLoopInvariant(unsigned I) const {
1230 }
1231
1232 bool areAllOperandsInvariant() const {
1233 return all_of(operands(), [](VPValue *Op) {
1234 return Op->isDefinedOutsideVectorRegions();
1235 });
1236 }
1237
1238public:
1239 template <typename IterT>
1241 : VPRecipeWithIRFlags(VPDef::VPWidenGEPSC, Operands, *GEP),
1242 VPValue(this, GEP) {}
1243
1244 ~VPWidenGEPRecipe() override = default;
1245
1246 VP_CLASSOF_IMPL(VPDef::VPWidenGEPSC)
1247
1248 /// Generate the gep nodes.
1249 void execute(VPTransformState &State) override;
1250
1251#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1252 /// Print the recipe.
1253 void print(raw_ostream &O, const Twine &Indent,
1254 VPSlotTracker &SlotTracker) const override;
1255#endif
1256};
1257
1258/// A pure virtual base class for all recipes modeling header phis, including
1259/// phis for first order recurrences, pointer inductions and reductions. The
1260/// start value is the first operand of the recipe and the incoming value from
1261/// the backedge is the second operand.
1262///
1263/// Inductions are modeled using the following sub-classes:
1264/// * VPCanonicalIVPHIRecipe: Canonical scalar induction of the vector loop,
1265/// starting at a specified value (zero for the main vector loop, the resume
1266/// value for the epilogue vector loop) and stepping by 1. The induction
1267/// controls exiting of the vector loop by comparing against the vector trip
1268/// count. Produces a single scalar PHI for the induction value per
1269/// iteration.
1270/// * VPWidenIntOrFpInductionRecipe: Generates vector values for integer and
1271/// floating point inductions with arbitrary start and step values. Produces
1272/// a vector PHI per-part.
1273/// * VPDerivedIVRecipe: Converts the canonical IV value to the corresponding
1274/// value of an IV with different start and step values. Produces a single
1275/// scalar value per iteration
1276/// * VPScalarIVStepsRecipe: Generates scalar values per-lane based on a
1277/// canonical or derived induction.
1278/// * VPWidenPointerInductionRecipe: Generate vector and scalar values for a
1279/// pointer induction. Produces either a vector PHI per-part or scalar values
1280/// per-lane based on the canonical induction.
1282protected:
1283 VPHeaderPHIRecipe(unsigned char VPDefID, Instruction *UnderlyingInstr,
1284 VPValue *Start = nullptr)
1285 : VPRecipeBase(VPDefID, {}), VPValue(this, UnderlyingInstr) {
1286 if (Start)
1287 addOperand(Start);
1288 }
1289
1290public:
1291 ~VPHeaderPHIRecipe() override = default;
1292
1293 /// Method to support type inquiry through isa, cast, and dyn_cast.
1294 static inline bool classof(const VPRecipeBase *B) {
1295 return B->getVPDefID() >= VPDef::VPFirstHeaderPHISC &&
1296 B->getVPDefID() <= VPDef::VPLastHeaderPHISC;
1297 }
1298 static inline bool classof(const VPValue *V) {
1299 auto *B = V->getDefiningRecipe();
1300 return B && B->getVPDefID() >= VPRecipeBase::VPFirstHeaderPHISC &&
1301 B->getVPDefID() <= VPRecipeBase::VPLastHeaderPHISC;
1302 }
1303
1304 /// Generate the phi nodes.
1305 void execute(VPTransformState &State) override = 0;
1306
1307#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1308 /// Print the recipe.
1309 void print(raw_ostream &O, const Twine &Indent,
1310 VPSlotTracker &SlotTracker) const override = 0;
1311#endif
1312
1313 /// Returns the start value of the phi, if one is set.
1315 return getNumOperands() == 0 ? nullptr : getOperand(0);
1316 }
1318 return getNumOperands() == 0 ? nullptr : getOperand(0);
1319 }
1320
1321 /// Update the start value of the recipe.
1323
1324 /// Returns the incoming value from the loop backedge.
1326 return getOperand(1);
1327 }
1328
1329 /// Returns the backedge value as a recipe. The backedge value is guaranteed
1330 /// to be a recipe.
1333 }
1334};
1335
1336/// A recipe for handling phi nodes of integer and floating-point inductions,
1337/// producing their vector values.
1339 PHINode *IV;
1340 TruncInst *Trunc;
1341 const InductionDescriptor &IndDesc;
1342
1343public:
1345 const InductionDescriptor &IndDesc)
1346 : VPHeaderPHIRecipe(VPDef::VPWidenIntOrFpInductionSC, IV, Start), IV(IV),
1347 Trunc(nullptr), IndDesc(IndDesc) {
1348 addOperand(Step);
1349 }
1350
1352 const InductionDescriptor &IndDesc,
1353 TruncInst *Trunc)
1354 : VPHeaderPHIRecipe(VPDef::VPWidenIntOrFpInductionSC, Trunc, Start),
1355 IV(IV), Trunc(Trunc), IndDesc(IndDesc) {
1356 addOperand(Step);
1357 }
1358
1360
1361 VP_CLASSOF_IMPL(VPDef::VPWidenIntOrFpInductionSC)
1362
1363 /// Generate the vectorized and scalarized versions of the phi node as
1364 /// needed by their users.
1365 void execute(VPTransformState &State) override;
1366
1367#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1368 /// Print the recipe.
1369 void print(raw_ostream &O, const Twine &Indent,
1370 VPSlotTracker &SlotTracker) const override;
1371#endif
1372
1374 // TODO: All operands of base recipe must exist and be at same index in
1375 // derived recipe.
1377 "VPWidenIntOrFpInductionRecipe generates its own backedge value");
1378 }
1379
1381 // TODO: All operands of base recipe must exist and be at same index in
1382 // derived recipe.
1384 "VPWidenIntOrFpInductionRecipe generates its own backedge value");
1385 }
1386
1387 /// Returns the step value of the induction.
1389 const VPValue *getStepValue() const { return getOperand(1); }
1390
1391 /// Returns the first defined value as TruncInst, if it is one or nullptr
1392 /// otherwise.
1393 TruncInst *getTruncInst() { return Trunc; }
1394 const TruncInst *getTruncInst() const { return Trunc; }
1395
1396 PHINode *getPHINode() { return IV; }
1397
1398 /// Returns the induction descriptor for the recipe.
1399 const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
1400
1401 /// Returns true if the induction is canonical, i.e. starting at 0 and
1402 /// incremented by UF * VF (= the original IV is incremented by 1).
1403 bool isCanonical() const;
1404
1405 /// Returns the scalar type of the induction.
1406 const Type *getScalarType() const {
1407 return Trunc ? Trunc->getType() : IV->getType();
1408 }
1409};
1410
1412 const InductionDescriptor &IndDesc;
1413
1414 bool IsScalarAfterVectorization;
1415
1416public:
1417 /// Create a new VPWidenPointerInductionRecipe for \p Phi with start value \p
1418 /// Start.
1420 const InductionDescriptor &IndDesc,
1421 bool IsScalarAfterVectorization)
1422 : VPHeaderPHIRecipe(VPDef::VPWidenPointerInductionSC, Phi),
1423 IndDesc(IndDesc),
1424 IsScalarAfterVectorization(IsScalarAfterVectorization) {
1425 addOperand(Start);
1426 addOperand(Step);
1427 }
1428
1430
1431 VP_CLASSOF_IMPL(VPDef::VPWidenPointerInductionSC)
1432
1433 /// Generate vector values for the pointer induction.
1434 void execute(VPTransformState &State) override;
1435
1436 /// Returns true if only scalar values will be generated.
1438
1439 /// Returns the induction descriptor for the recipe.
1440 const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
1441
1442#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1443 /// Print the recipe.
1444 void print(raw_ostream &O, const Twine &Indent,
1445 VPSlotTracker &SlotTracker) const override;
1446#endif
1447};
1448
1449/// A recipe for handling header phis that are widened in the vector loop.
1450/// In the VPlan native path, all incoming VPValues & VPBasicBlock pairs are
1451/// managed in the recipe directly.
1453 /// List of incoming blocks. Only used in the VPlan native path.
1454 SmallVector<VPBasicBlock *, 2> IncomingBlocks;
1455
1456public:
1457 /// Create a new VPWidenPHIRecipe for \p Phi with start value \p Start.
1458 VPWidenPHIRecipe(PHINode *Phi, VPValue *Start = nullptr)
1459 : VPHeaderPHIRecipe(VPDef::VPWidenPHISC, Phi) {
1460 if (Start)
1461 addOperand(Start);
1462 }
1463
1464 ~VPWidenPHIRecipe() override = default;
1465
1466 VP_CLASSOF_IMPL(VPDef::VPWidenPHISC)
1467
1468 /// Generate the phi/select nodes.
1469 void execute(VPTransformState &State) override;
1470
1471#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1472 /// Print the recipe.
1473 void print(raw_ostream &O, const Twine &Indent,
1474 VPSlotTracker &SlotTracker) const override;
1475#endif
1476
1477 /// Adds a pair (\p IncomingV, \p IncomingBlock) to the phi.
1478 void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock) {
1479 addOperand(IncomingV);
1480 IncomingBlocks.push_back(IncomingBlock);
1481 }
1482
1483 /// Returns the \p I th incoming VPBasicBlock.
1484 VPBasicBlock *getIncomingBlock(unsigned I) { return IncomingBlocks[I]; }
1485
1486 /// Returns the \p I th incoming VPValue.
1487 VPValue *getIncomingValue(unsigned I) { return getOperand(I); }
1488};
1489
1490/// A recipe for handling first-order recurrence phis. The start value is the
1491/// first operand of the recipe and the incoming value from the backedge is the
1492/// second operand.
1495 : VPHeaderPHIRecipe(VPDef::VPFirstOrderRecurrencePHISC, Phi, &Start) {}
1496
1497 VP_CLASSOF_IMPL(VPDef::VPFirstOrderRecurrencePHISC)
1498
1500 return R->getVPDefID() == VPDef::VPFirstOrderRecurrencePHISC;
1501 }
1502
1503 void execute(VPTransformState &State) override;
1504
1505#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1506 /// Print the recipe.
1507 void print(raw_ostream &O, const Twine &Indent,
1508 VPSlotTracker &SlotTracker) const override;
1509#endif
1510};
1511
1512/// A recipe for handling reduction phis. The start value is the first operand
1513/// of the recipe and the incoming value from the backedge is the second
1514/// operand.
1516 /// Descriptor for the reduction.
1517 const RecurrenceDescriptor &RdxDesc;
1518
1519 /// The phi is part of an in-loop reduction.
1520 bool IsInLoop;
1521
1522 /// The phi is part of an ordered reduction. Requires IsInLoop to be true.
1523 bool IsOrdered;
1524
1525public:
1526 /// Create a new VPReductionPHIRecipe for the reduction \p Phi described by \p
1527 /// RdxDesc.
1529 VPValue &Start, bool IsInLoop = false,
1530 bool IsOrdered = false)
1531 : VPHeaderPHIRecipe(VPDef::VPReductionPHISC, Phi, &Start),
1532 RdxDesc(RdxDesc), IsInLoop(IsInLoop), IsOrdered(IsOrdered) {
1533 assert((!IsOrdered || IsInLoop) && "IsOrdered requires IsInLoop");
1534 }
1535
1536 ~VPReductionPHIRecipe() override = default;
1537
1538 VP_CLASSOF_IMPL(VPDef::VPReductionPHISC)
1539
1541 return R->getVPDefID() == VPDef::VPReductionPHISC;
1542 }
1543
1544 /// Generate the phi/select nodes.
1545 void execute(VPTransformState &State) override;
1546
1547#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1548 /// Print the recipe.
1549 void print(raw_ostream &O, const Twine &Indent,
1550 VPSlotTracker &SlotTracker) const override;
1551#endif
1552
1554 return RdxDesc;
1555 }
1556
1557 /// Returns true, if the phi is part of an ordered reduction.
1558 bool isOrdered() const { return IsOrdered; }
1559
1560 /// Returns true, if the phi is part of an in-loop reduction.
1561 bool isInLoop() const { return IsInLoop; }
1562};
1563
1564/// A recipe for vectorizing a phi-node as a sequence of mask-based select
1565/// instructions.
1566class VPBlendRecipe : public VPRecipeBase, public VPValue {
1567 PHINode *Phi;
1568
1569public:
1570 /// The blend operation is a User of the incoming values and of their
1571 /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value
1572 /// might be incoming with a full mask for which there is no VPValue.
1574 : VPRecipeBase(VPDef::VPBlendSC, Operands), VPValue(this, Phi), Phi(Phi) {
1575 assert(Operands.size() > 0 &&
1576 ((Operands.size() == 1) || (Operands.size() % 2 == 0)) &&
1577 "Expected either a single incoming value or a positive even number "
1578 "of operands");
1579 }
1580
1581 VP_CLASSOF_IMPL(VPDef::VPBlendSC)
1582
1583 /// Return the number of incoming values, taking into account that a single
1584 /// incoming value has no mask.
1585 unsigned getNumIncomingValues() const { return (getNumOperands() + 1) / 2; }
1586
1587 /// Return incoming value number \p Idx.
1588 VPValue *getIncomingValue(unsigned Idx) const { return getOperand(Idx * 2); }
1589
1590 /// Return mask number \p Idx.
1591 VPValue *getMask(unsigned Idx) const { return getOperand(Idx * 2 + 1); }
1592
1593 /// Generate the phi/select nodes.
1594 void execute(VPTransformState &State) override;
1595
1596#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1597 /// Print the recipe.
1598 void print(raw_ostream &O, const Twine &Indent,
1599 VPSlotTracker &SlotTracker) const override;
1600#endif
1601
1602 /// Returns true if the recipe only uses the first lane of operand \p Op.
1603 bool onlyFirstLaneUsed(const VPValue *Op) const override {
1604 assert(is_contained(operands(), Op) &&
1605 "Op must be an operand of the recipe");
1606 // Recursing through Blend recipes only, must terminate at header phi's the
1607 // latest.
1608 return all_of(users(),
1609 [this](VPUser *U) { return U->onlyFirstLaneUsed(this); });
1610 }
1611};
1612
1613/// VPInterleaveRecipe is a recipe for transforming an interleave group of load
1614/// or stores into one wide load/store and shuffles. The first operand of a
1615/// VPInterleave recipe is the address, followed by the stored values, followed
1616/// by an optional mask.
1619
1620 /// Indicates if the interleave group is in a conditional block and requires a
1621 /// mask.
1622 bool HasMask = false;
1623
1624 /// Indicates if gaps between members of the group need to be masked out or if
1625 /// unusued gaps can be loaded speculatively.
1626 bool NeedsMaskForGaps = false;
1627
1628public:
1630 ArrayRef<VPValue *> StoredValues, VPValue *Mask,
1631 bool NeedsMaskForGaps)
1632 : VPRecipeBase(VPDef::VPInterleaveSC, {Addr}), IG(IG),
1633 NeedsMaskForGaps(NeedsMaskForGaps) {
1634 for (unsigned i = 0; i < IG->getFactor(); ++i)
1635 if (Instruction *I = IG->getMember(i)) {
1636 if (I->getType()->isVoidTy())
1637 continue;
1638 new VPValue(I, this);
1639 }
1640
1641 for (auto *SV : StoredValues)
1642 addOperand(SV);
1643 if (Mask) {
1644 HasMask = true;
1645 addOperand(Mask);
1646 }
1647 }
1648 ~VPInterleaveRecipe() override = default;
1649
1650 VP_CLASSOF_IMPL(VPDef::VPInterleaveSC)
1651
1652 /// Return the address accessed by this recipe.
1653 VPValue *getAddr() const {
1654 return getOperand(0); // Address is the 1st, mandatory operand.
1655 }
1656
1657 /// Return the mask used by this recipe. Note that a full mask is represented
1658 /// by a nullptr.
1659 VPValue *getMask() const {
1660 // Mask is optional and therefore the last, currently 2nd operand.
1661 return HasMask ? getOperand(getNumOperands() - 1) : nullptr;
1662 }
1663
1664 /// Return the VPValues stored by this interleave group. If it is a load
1665 /// interleave group, return an empty ArrayRef.
1667 // The first operand is the address, followed by the stored values, followed
1668 // by an optional mask.
1671 }
1672
1673 /// Generate the wide load or store, and shuffles.
1674 void execute(VPTransformState &State) override;
1675
1676#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1677 /// Print the recipe.
1678 void print(raw_ostream &O, const Twine &Indent,
1679 VPSlotTracker &SlotTracker) const override;
1680#endif
1681
1683
1684 /// Returns the number of stored operands of this interleave group. Returns 0
1685 /// for load interleave groups.
1686 unsigned getNumStoreOperands() const {
1687 return getNumOperands() - (HasMask ? 2 : 1);
1688 }
1689
1690 /// The recipe only uses the first lane of the address.
1691 bool onlyFirstLaneUsed(const VPValue *Op) const override {
1692 assert(is_contained(operands(), Op) &&
1693 "Op must be an operand of the recipe");
1694 return Op == getAddr() && !llvm::is_contained(getStoredValues(), Op);
1695 }
1696};
1697
1698/// A recipe to represent inloop reduction operations, performing a reduction on
1699/// a vector operand into a scalar value, and adding the result to a chain.
1700/// The Operands are {ChainOp, VecOp, [Condition]}.
1702 /// The recurrence decriptor for the reduction in question.
1703 const RecurrenceDescriptor *RdxDesc;
1704 /// Pointer to the TTI, needed to create the target reduction
1705 const TargetTransformInfo *TTI;
1706
1707public:
1709 VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,
1710 const TargetTransformInfo *TTI)
1711 : VPRecipeBase(VPDef::VPReductionSC, {ChainOp, VecOp}), VPValue(this, I),
1712 RdxDesc(R), TTI(TTI) {
1713 if (CondOp)
1714 addOperand(CondOp);
1715 }
1716
1717 ~VPReductionRecipe() override = default;
1718
1719 VP_CLASSOF_IMPL(VPDef::VPReductionSC)
1720
1721 /// Generate the reduction in the loop
1722 void execute(VPTransformState &State) override;
1723
1724#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1725 /// Print the recipe.
1726 void print(raw_ostream &O, const Twine &Indent,
1727 VPSlotTracker &SlotTracker) const override;
1728#endif
1729
1730 /// The VPValue of the scalar Chain being accumulated.
1731 VPValue *getChainOp() const { return getOperand(0); }
1732 /// The VPValue of the vector value to be reduced.
1733 VPValue *getVecOp() const { return getOperand(1); }
1734 /// The VPValue of the condition for the block.
1736 return getNumOperands() > 2 ? getOperand(2) : nullptr;
1737 }
1738};
1739
1740/// VPReplicateRecipe replicates a given instruction producing multiple scalar
1741/// copies of the original scalar type, one per lane, instead of producing a
1742/// single copy of widened type for all lanes. If the instruction is known to be
1743/// uniform only one copy, per lane zero, will be generated.
1745 /// Indicator if only a single replica per lane is needed.
1746 bool IsUniform;
1747
1748 /// Indicator if the replicas are also predicated.
1749 bool IsPredicated;
1750
1751public:
1752 template <typename IterT>
1754 bool IsUniform, VPValue *Mask = nullptr)
1755 : VPRecipeWithIRFlags(VPDef::VPReplicateSC, Operands, *I),
1756 VPValue(this, I), IsUniform(IsUniform), IsPredicated(Mask) {
1757 if (Mask)
1758 addOperand(Mask);
1759 }
1760
1761 ~VPReplicateRecipe() override = default;
1762
1763 VP_CLASSOF_IMPL(VPDef::VPReplicateSC)
1764
1765 /// Generate replicas of the desired Ingredient. Replicas will be generated
1766 /// for all parts and lanes unless a specific part and lane are specified in
1767 /// the \p State.
1768 void execute(VPTransformState &State) override;
1769
1770#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1771 /// Print the recipe.
1772 void print(raw_ostream &O, const Twine &Indent,
1773 VPSlotTracker &SlotTracker) const override;
1774#endif
1775
1776 bool isUniform() const { return IsUniform; }
1777
1778 bool isPredicated() const { return IsPredicated; }
1779
1780 /// Returns true if the recipe only uses the first lane of operand \p Op.
1781 bool onlyFirstLaneUsed(const VPValue *Op) const override {
1782 assert(is_contained(operands(), Op) &&
1783 "Op must be an operand of the recipe");
1784 return isUniform();
1785 }
1786
1787 /// Returns true if the recipe uses scalars of operand \p Op.
1788 bool usesScalars(const VPValue *Op) const override {
1789 assert(is_contained(operands(), Op) &&
1790 "Op must be an operand of the recipe");
1791 return true;
1792 }
1793
1794 /// Returns true if the recipe is used by a widened recipe via an intervening
1795 /// VPPredInstPHIRecipe. In this case, the scalar values should also be packed
1796 /// in a vector.
1797 bool shouldPack() const;
1798
1799 /// Return the mask of a predicated VPReplicateRecipe.
1801 assert(isPredicated() && "Trying to get the mask of a unpredicated recipe");
1802 return getOperand(getNumOperands() - 1);
1803 }
1804};
1805
1806/// A recipe for generating conditional branches on the bits of a mask.
1808public:
1810 : VPRecipeBase(VPDef::VPBranchOnMaskSC, {}) {
1811 if (BlockInMask) // nullptr means all-one mask.
1812 addOperand(BlockInMask);
1813 }
1814
1815 VP_CLASSOF_IMPL(VPDef::VPBranchOnMaskSC)
1816
1817 /// Generate the extraction of the appropriate bit from the block mask and the
1818 /// conditional branch.
1819 void execute(VPTransformState &State) override;
1820
1821#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1822 /// Print the recipe.
1823 void print(raw_ostream &O, const Twine &Indent,
1824 VPSlotTracker &SlotTracker) const override {
1825 O << Indent << "BRANCH-ON-MASK ";
1826 if (VPValue *Mask = getMask())
1827 Mask->printAsOperand(O, SlotTracker);
1828 else
1829 O << " All-One";
1830 }
1831#endif
1832
1833 /// Return the mask used by this recipe. Note that a full mask is represented
1834 /// by a nullptr.
1835 VPValue *getMask() const {
1836 assert(getNumOperands() <= 1 && "should have either 0 or 1 operands");
1837 // Mask is optional.
1838 return getNumOperands() == 1 ? getOperand(0) : nullptr;
1839 }
1840
1841 /// Returns true if the recipe uses scalars of operand \p Op.
1842 bool usesScalars(const VPValue *Op) const override {
1843 assert(is_contained(operands(), Op) &&
1844 "Op must be an operand of the recipe");
1845 return true;
1846 }
1847};
1848
1849/// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
1850/// control converges back from a Branch-on-Mask. The phi nodes are needed in
1851/// order to merge values that are set under such a branch and feed their uses.
1852/// The phi nodes can be scalar or vector depending on the users of the value.
1853/// This recipe works in concert with VPBranchOnMaskRecipe.
1855public:
1856 /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
1857 /// nodes after merging back from a Branch-on-Mask.
1859 : VPRecipeBase(VPDef::VPPredInstPHISC, PredV), VPValue(this) {}
1860 ~VPPredInstPHIRecipe() override = default;
1861
1862 VP_CLASSOF_IMPL(VPDef::VPPredInstPHISC)
1863
1864 /// Generates phi nodes for live-outs as needed to retain SSA form.
1865 void execute(VPTransformState &State) override;
1866
1867#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1868 /// Print the recipe.
1869 void print(raw_ostream &O, const Twine &Indent,
1870 VPSlotTracker &SlotTracker) const override;
1871#endif
1872
1873 /// Returns true if the recipe uses scalars of operand \p Op.
1874 bool usesScalars(const VPValue *Op) const override {
1875 assert(is_contained(operands(), Op) &&
1876 "Op must be an operand of the recipe");
1877 return true;
1878 }
1879};
1880
1881/// A Recipe for widening load/store operations.
1882/// The recipe uses the following VPValues:
1883/// - For load: Address, optional mask
1884/// - For store: Address, stored value, optional mask
1885/// TODO: We currently execute only per-part unless a specific instance is
1886/// provided.
1888 Instruction &Ingredient;
1889
1890 // Whether the loaded-from / stored-to addresses are consecutive.
1891 bool Consecutive;
1892
1893 // Whether the consecutive loaded/stored addresses are in reverse order.
1894 bool Reverse;
1895
1896 void setMask(VPValue *Mask) {
1897 if (!Mask)
1898 return;
1899 addOperand(Mask);
1900 }
1901
1902 bool isMasked() const {
1903 return isStore() ? getNumOperands() == 3 : getNumOperands() == 2;
1904 }
1905
1906public:
1908 bool Consecutive, bool Reverse)
1909 : VPRecipeBase(VPDef::VPWidenMemoryInstructionSC, {Addr}),
1910 Ingredient(Load), Consecutive(Consecutive), Reverse(Reverse) {
1911 assert((Consecutive || !Reverse) && "Reverse implies consecutive");
1912 new VPValue(this, &Load);
1913 setMask(Mask);
1914 }
1915
1917 VPValue *StoredValue, VPValue *Mask,
1918 bool Consecutive, bool Reverse)
1919 : VPRecipeBase(VPDef::VPWidenMemoryInstructionSC, {Addr, StoredValue}),
1920 Ingredient(Store), Consecutive(Consecutive), Reverse(Reverse) {
1921 assert((Consecutive || !Reverse) && "Reverse implies consecutive");
1922 setMask(Mask);
1923 }
1924
1925 VP_CLASSOF_IMPL(VPDef::VPWidenMemoryInstructionSC)
1926
1927 /// Return the address accessed by this recipe.
1928 VPValue *getAddr() const {
1929 return getOperand(0); // Address is the 1st, mandatory operand.
1930 }
1931
1932 /// Return the mask used by this recipe. Note that a full mask is represented
1933 /// by a nullptr.
1934 VPValue *getMask() const {
1935 // Mask is optional and therefore the last operand.
1936 return isMasked() ? getOperand(getNumOperands() - 1) : nullptr;
1937 }
1938
1939 /// Returns true if this recipe is a store.
1940 bool isStore() const { return isa<StoreInst>(Ingredient); }
1941
1942 /// Return the address accessed by this recipe.
1944 assert(isStore() && "Stored value only available for store instructions");
1945 return getOperand(1); // Stored value is the 2nd, mandatory operand.
1946 }
1947
1948 // Return whether the loaded-from / stored-to addresses are consecutive.
1949 bool isConsecutive() const { return Consecutive; }
1950
1951 // Return whether the consecutive loaded/stored addresses are in reverse
1952 // order.
1953 bool isReverse() const { return Reverse; }
1954
1955 /// Generate the wide load/store.
1956 void execute(VPTransformState &State) override;
1957
1958#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1959 /// Print the recipe.
1960 void print(raw_ostream &O, const Twine &Indent,
1961 VPSlotTracker &SlotTracker) const override;
1962#endif
1963
1964 /// Returns true if the recipe only uses the first lane of operand \p Op.
1965 bool onlyFirstLaneUsed(const VPValue *Op) const override {
1966 assert(is_contained(operands(), Op) &&
1967 "Op must be an operand of the recipe");
1968
1969 // Widened, consecutive memory operations only demand the first lane of
1970 // their address, unless the same operand is also stored. That latter can
1971 // happen with opaque pointers.
1972 return Op == getAddr() && isConsecutive() &&
1973 (!isStore() || Op != getStoredValue());
1974 }
1975
1976 Instruction &getIngredient() const { return Ingredient; }
1977};
1978
1979/// Recipe to expand a SCEV expression.
1981 const SCEV *Expr;
1982 ScalarEvolution &SE;
1983
1984public:
1986 : VPRecipeBase(VPDef::VPExpandSCEVSC, {}), VPValue(this), Expr(Expr),
1987 SE(SE) {}
1988
1989 ~VPExpandSCEVRecipe() override = default;
1990
1991 VP_CLASSOF_IMPL(VPDef::VPExpandSCEVSC)
1992
1993 /// Generate a canonical vector induction variable of the vector loop, with
1994 void execute(VPTransformState &State) override;
1995
1996#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1997 /// Print the recipe.
1998 void print(raw_ostream &O, const Twine &Indent,
1999 VPSlotTracker &SlotTracker) const override;
2000#endif
2001
2002 const SCEV *getSCEV() const { return Expr; }
2003};
2004
2005/// Canonical scalar induction phi of the vector loop. Starting at the specified
2006/// start value (either 0 or the resume value when vectorizing the epilogue
2007/// loop). VPWidenCanonicalIVRecipe represents the vector version of the
2008/// canonical induction variable.
2010 DebugLoc DL;
2011
2012public:
2014 : VPHeaderPHIRecipe(VPDef::VPCanonicalIVPHISC, nullptr, StartV), DL(DL) {}
2015
2016 ~VPCanonicalIVPHIRecipe() override = default;
2017
2018 VP_CLASSOF_IMPL(VPDef::VPCanonicalIVPHISC)
2019
2021 return D->getVPDefID() == VPDef::VPCanonicalIVPHISC;
2022 }
2023
2024 /// Generate the canonical scalar induction phi of the vector loop.
2025 void execute(VPTransformState &State) override;
2026
2027#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2028 /// Print the recipe.
2029 void print(raw_ostream &O, const Twine &Indent,
2030 VPSlotTracker &SlotTracker) const override;
2031#endif
2032
2033 /// Returns the scalar type of the induction.
2034 const Type *getScalarType() const {
2035 return getOperand(0)->getLiveInIRValue()->getType();
2036 }
2037
2038 /// Returns true if the recipe only uses the first lane of operand \p Op.
2039 bool onlyFirstLaneUsed(const VPValue *Op) const override {
2040 assert(is_contained(operands(), Op) &&
2041 "Op must be an operand of the recipe");
2042 return true;
2043 }
2044
2045 /// Check if the induction described by \p Kind, /p Start and \p Step is
2046 /// canonical, i.e. has the same start, step (of 1), and type as the
2047 /// canonical IV.
2049 VPValue *Step, Type *Ty) const;
2050};
2051
2052/// A recipe for generating the active lane mask for the vector loop that is
2053/// used to predicate the vector operations.
2054/// TODO: It would be good to use the existing VPWidenPHIRecipe instead and
2055/// remove VPActiveLaneMaskPHIRecipe.
2057 DebugLoc DL;
2058
2059public:
2061 : VPHeaderPHIRecipe(VPDef::VPActiveLaneMaskPHISC, nullptr, StartMask),
2062 DL(DL) {}
2063
2064 ~VPActiveLaneMaskPHIRecipe() override = default;
2065
2066 VP_CLASSOF_IMPL(VPDef::VPActiveLaneMaskPHISC)
2067
2069 return D->getVPDefID() == VPDef::VPActiveLaneMaskPHISC;
2070 }
2071
2072 /// Generate the active lane mask phi of the vector loop.
2073 void execute(VPTransformState &State) override;
2074
2075#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2076 /// Print the recipe.
2077 void print(raw_ostream &O, const Twine &Indent,
2078 VPSlotTracker &SlotTracker) const override;
2079#endif
2080};
2081
2082/// A Recipe for widening the canonical induction variable of the vector loop.
2084public:
2086 : VPRecipeBase(VPDef::VPWidenCanonicalIVSC, {CanonicalIV}),
2087 VPValue(this) {}
2088
2089 ~VPWidenCanonicalIVRecipe() override = default;
2090
2091 VP_CLASSOF_IMPL(VPDef::VPWidenCanonicalIVSC)
2092
2093 /// Generate a canonical vector induction variable of the vector loop, with
2094 /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and
2095 /// step = <VF*UF, VF*UF, ..., VF*UF>.
2096 void execute(VPTransformState &State) override;
2097
2098#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2099 /// Print the recipe.
2100 void print(raw_ostream &O, const Twine &Indent,
2101 VPSlotTracker &SlotTracker) const override;
2102#endif
2103
2104 /// Returns the scalar type of the induction.
2105 const Type *getScalarType() const {
2106 return cast<VPCanonicalIVPHIRecipe>(getOperand(0)->getDefiningRecipe())
2107 ->getScalarType();
2108 }
2109};
2110
2111/// A recipe for converting the canonical IV value to the corresponding value of
2112/// an IV with different start and step values, using Start + CanonicalIV *
2113/// Step.
2115 /// The type of the result value. It may be smaller than the type of the
2116 /// induction and in this case it will get truncated to ResultTy.
2117 Type *ResultTy;
2118
2119 /// Induction descriptor for the induction the canonical IV is transformed to.
2120 const InductionDescriptor &IndDesc;
2121
2122public:
2124 VPCanonicalIVPHIRecipe *CanonicalIV, VPValue *Step,
2125 Type *ResultTy)
2126 : VPRecipeBase(VPDef::VPDerivedIVSC, {Start, CanonicalIV, Step}),
2127 VPValue(this), ResultTy(ResultTy), IndDesc(IndDesc) {}
2128
2129 ~VPDerivedIVRecipe() override = default;
2130
2131 VP_CLASSOF_IMPL(VPDef::VPDerivedIVSC)
2132
2133 /// Generate the transformed value of the induction at offset StartValue (1.
2134 /// operand) + IV (2. operand) * StepValue (3, operand).
2135 void execute(VPTransformState &State) override;
2136
2137#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2138 /// Print the recipe.
2139 void print(raw_ostream &O, const Twine &Indent,
2140 VPSlotTracker &SlotTracker) const override;
2141#endif
2142
2143 VPValue *getStartValue() const { return getOperand(0); }
2144 VPValue *getCanonicalIV() const { return getOperand(1); }
2145 VPValue *getStepValue() const { return getOperand(2); }
2146
2147 /// Returns true if the recipe only uses the first lane of operand \p Op.
2148 bool onlyFirstLaneUsed(const VPValue *Op) const override {
2149 assert(is_contained(operands(), Op) &&
2150 "Op must be an operand of the recipe");
2151 return true;
2152 }
2153};
2154
2155/// A recipe for handling phi nodes of integer and floating-point inductions,
2156/// producing their scalar values.
2158 const InductionDescriptor &IndDesc;
2159
2160public:
2162 VPValue *Step)
2163 : VPRecipeBase(VPDef::VPScalarIVStepsSC, {IV, Step}), VPValue(this),
2164 IndDesc(IndDesc) {}
2165
2166 ~VPScalarIVStepsRecipe() override = default;
2167
2168 VP_CLASSOF_IMPL(VPDef::VPScalarIVStepsSC)
2169
2170 /// Generate the scalarized versions of the phi node as needed by their users.
2171 void execute(VPTransformState &State) override;
2172
2173#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2174 /// Print the recipe.
2175 void print(raw_ostream &O, const Twine &Indent,
2176 VPSlotTracker &SlotTracker) const override;
2177#endif
2178
2179 VPValue *getStepValue() const { return getOperand(1); }
2180
2181 /// Returns true if the recipe only uses the first lane of operand \p Op.
2182 bool onlyFirstLaneUsed(const VPValue *Op) const override {
2183 assert(is_contained(operands(), Op) &&
2184 "Op must be an operand of the recipe");
2185 return true;
2186 }
2187};
2188
2189/// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
2190/// holds a sequence of zero or more VPRecipe's each representing a sequence of
2191/// output IR instructions. All PHI-like recipes must come before any non-PHI recipes.
2193public:
2195
2196private:
2197 /// The VPRecipes held in the order of output instructions to generate.
2198 RecipeListTy Recipes;
2199
2200public:
2201 VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
2202 : VPBlockBase(VPBasicBlockSC, Name.str()) {
2203 if (Recipe)
2204 appendRecipe(Recipe);
2205 }
2206
2207 ~VPBasicBlock() override {
2208 while (!Recipes.empty())
2209 Recipes.pop_back();
2210 }
2211
2212 /// Instruction iterators...
2217
2218 //===--------------------------------------------------------------------===//
2219 /// Recipe iterator methods
2220 ///
2221 inline iterator begin() { return Recipes.begin(); }
2222 inline const_iterator begin() const { return Recipes.begin(); }
2223 inline iterator end() { return Recipes.end(); }
2224 inline const_iterator end() const { return Recipes.end(); }
2225
2226 inline reverse_iterator rbegin() { return Recipes.rbegin(); }
2227 inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
2228 inline reverse_iterator rend() { return Recipes.rend(); }
2229 inline const_reverse_iterator rend() const { return Recipes.rend(); }
2230
2231 inline size_t size() const { return Recipes.size(); }
2232 inline bool empty() const { return Recipes.empty(); }
2233 inline const VPRecipeBase &front() const { return Recipes.front(); }
2234 inline VPRecipeBase &front() { return Recipes.front(); }
2235 inline const VPRecipeBase &back() const { return Recipes.back(); }
2236 inline VPRecipeBase &back() { return Recipes.back(); }
2237
2238 /// Returns a reference to the list of recipes.
2239 RecipeListTy &getRecipeList() { return Recipes; }
2240
2241 /// Returns a pointer to a member of the recipe list.
2243 return &VPBasicBlock::Recipes;
2244 }
2245
2246 /// Method to support type inquiry through isa, cast, and dyn_cast.
2247 static inline bool classof(const VPBlockBase *V) {
2248 return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
2249 }
2250
2251 void insert(VPRecipeBase *Recipe, iterator InsertPt) {
2252 assert(Recipe && "No recipe to append.");
2253 assert(!Recipe->Parent && "Recipe already in VPlan");
2254 Recipe->Parent = this;
2255 Recipes.insert(InsertPt, Recipe);
2256 }
2257
2258 /// Augment the existing recipes of a VPBasicBlock with an additional
2259 /// \p Recipe as the last recipe.
2260 void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
2261
2262 /// The method which generates the output IR instructions that correspond to
2263 /// this VPBasicBlock, thereby "executing" the VPlan.
2264 void execute(VPTransformState *State) override;
2265
2266 /// Return the position of the first non-phi node recipe in the block.
2268
2269 /// Returns an iterator range over the PHI-like recipes in the block.
2271 return make_range(begin(), getFirstNonPhi());
2272 }
2273
2274 void dropAllReferences(VPValue *NewValue) override;
2275
2276 /// Split current block at \p SplitAt by inserting a new block between the
2277 /// current block and its successors and moving all recipes starting at
2278 /// SplitAt to the new block. Returns the new block.
2279 VPBasicBlock *splitAt(iterator SplitAt);
2280
2282
2283#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2284 /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p
2285 /// SlotTracker is used to print unnamed VPValue's using consequtive numbers.
2286 ///
2287 /// Note that the numbering is applied to the whole VPlan, so printing
2288 /// individual blocks is consistent with the whole VPlan printing.
2289 void print(raw_ostream &O, const Twine &Indent,
2290 VPSlotTracker &SlotTracker) const override;
2291 using VPBlockBase::print; // Get the print(raw_stream &O) version.
2292#endif
2293
2294 /// If the block has multiple successors, return the branch recipe terminating
2295 /// the block. If there are no or only a single successor, return nullptr;
2297 const VPRecipeBase *getTerminator() const;
2298
2299 /// Returns true if the block is exiting it's parent region.
2300 bool isExiting() const;
2301
2302private:
2303 /// Create an IR BasicBlock to hold the output instructions generated by this
2304 /// VPBasicBlock, and return it. Update the CFGState accordingly.
2305 BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
2306};
2307
2308/// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
2309/// which form a Single-Entry-Single-Exiting subgraph of the output IR CFG.
2310/// A VPRegionBlock may indicate that its contents are to be replicated several
2311/// times. This is designed to support predicated scalarization, in which a
2312/// scalar if-then code structure needs to be generated VF * UF times. Having
2313/// this replication indicator helps to keep a single model for multiple
2314/// candidate VF's. The actual replication takes place only once the desired VF
2315/// and UF have been determined.
2317 /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
2318 VPBlockBase *Entry;
2319
2320 /// Hold the Single Exiting block of the SESE region modelled by the
2321 /// VPRegionBlock.
2322 VPBlockBase *Exiting;
2323
2324 /// An indicator whether this region is to generate multiple replicated
2325 /// instances of output IR corresponding to its VPBlockBases.
2326 bool IsReplicator;
2327
2328public:
2330 const std::string &Name = "", bool IsReplicator = false)
2331 : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exiting(Exiting),
2332 IsReplicator(IsReplicator) {
2333 assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
2334 assert(Exiting->getSuccessors().empty() && "Exit block has successors.");
2335 Entry->setParent(this);
2336 Exiting->setParent(this);
2337 }
2338 VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
2339 : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exiting(nullptr),
2340 IsReplicator(IsReplicator) {}
2341
2342 ~VPRegionBlock() override {
2343 if (Entry) {
2344 VPValue DummyValue;
2345 Entry->dropAllReferences(&DummyValue);
2346 deleteCFG(Entry);
2347 }
2348 }
2349
2350 /// Method to support type inquiry through isa, cast, and dyn_cast.
2351 static inline bool classof(const VPBlockBase *V) {
2352 return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
2353 }
2354
2355 const VPBlockBase *getEntry() const { return Entry; }
2356 VPBlockBase *getEntry() { return Entry; }
2357
2358 /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
2359 /// EntryBlock must have no predecessors.
2360 void setEntry(VPBlockBase *EntryBlock) {
2361 assert(EntryBlock->getPredecessors().empty() &&
2362 "Entry block cannot have predecessors.");
2363 Entry = EntryBlock;
2364 EntryBlock->setParent(this);
2365 }
2366
2367 const VPBlockBase *getExiting() const { return Exiting; }
2368 VPBlockBase *getExiting() { return Exiting; }
2369
2370 /// Set \p ExitingBlock as the exiting VPBlockBase of this VPRegionBlock. \p
2371 /// ExitingBlock must have no successors.
2372 void setExiting(VPBlockBase *ExitingBlock) {
2373 assert(ExitingBlock->getSuccessors().empty() &&
2374 "Exit block cannot have successors.");
2375 Exiting = ExitingBlock;
2376 ExitingBlock->setParent(this);
2377 }
2378
2379 /// Returns the pre-header VPBasicBlock of the loop region.
2381 assert(!isReplicator() && "should only get pre-header of loop regions");
2383 }
2384
2385 /// An indicator whether this region is to generate multiple replicated
2386 /// instances of output IR corresponding to its VPBlockBases.
2387 bool isReplicator() const { return IsReplicator; }
2388
2389 /// The method which generates the output IR instructions that correspond to
2390 /// this VPRegionBlock, thereby "executing" the VPlan.
2391 void execute(VPTransformState *State) override;
2392
2393 void dropAllReferences(VPValue *NewValue) override;
2394
2395#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2396 /// Print this VPRegionBlock to \p O (recursively), prefixing all lines with
2397 /// \p Indent. \p SlotTracker is used to print unnamed VPValue's using
2398 /// consequtive numbers.
2399 ///
2400 /// Note that the numbering is applied to the whole VPlan, so printing
2401 /// individual regions is consistent with the whole VPlan printing.
2402 void print(raw_ostream &O, const Twine &Indent,
2403 VPSlotTracker &SlotTracker) const override;
2404 using VPBlockBase::print; // Get the print(raw_stream &O) version.
2405#endif
2406};
2407
2408/// VPlan models a candidate for vectorization, encoding various decisions take
2409/// to produce efficient output IR, including which branches, basic-blocks and
2410/// output IR instructions to generate, and their cost. VPlan holds a
2411/// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
2412/// VPBasicBlock.
2413class VPlan {
2414 friend class VPlanPrinter;
2415 friend class VPSlotTracker;
2416
2417 /// Hold the single entry to the Hierarchical CFG of the VPlan, i.e. the
2418 /// preheader of the vector loop.
2419 VPBasicBlock *Entry;
2420
2421 /// VPBasicBlock corresponding to the original preheader. Used to place
2422 /// VPExpandSCEV recipes for expressions used during skeleton creation and the
2423 /// rest of VPlan execution.
2424 VPBasicBlock *Preheader;
2425
2426 /// Holds the VFs applicable to this VPlan.
2428
2429 /// Holds the UFs applicable to this VPlan. If empty, the VPlan is valid for
2430 /// any UF.
2432
2433 /// Holds the name of the VPlan, for printing.
2434 std::string Name;
2435
2436 /// Represents the trip count of the original loop, for folding
2437 /// the tail.
2438 VPValue *TripCount = nullptr;
2439
2440 /// Represents the backedge taken count of the original loop, for folding
2441 /// the tail. It equals TripCount - 1.
2442 VPValue *BackedgeTakenCount = nullptr;
2443
2444 /// Represents the vector trip count.
2445 VPValue VectorTripCount;
2446
2447 /// Holds a mapping between Values and their corresponding VPValue inside
2448 /// VPlan.
2449 Value2VPValueTy Value2VPValue;
2450
2451 /// Contains all the external definitions created for this VPlan. External
2452 /// definitions are VPValues that hold a pointer to their underlying IR.
2453 SmallVector<VPValue *, 16> VPLiveInsToFree;
2454
2455 /// Indicates whether it is safe use the Value2VPValue mapping or if the
2456 /// mapping cannot be used any longer, because it is stale.
2457 bool Value2VPValueEnabled = true;
2458
2459 /// Values used outside the plan.
2461
2462 /// Mapping from SCEVs to the VPValues representing their expansions.
2463 /// NOTE: This mapping is temporary and will be removed once all users have
2464 /// been modeled in VPlan directly.
2465 DenseMap<const SCEV *, VPValue *> SCEVToExpansion;
2466
2467public:
2468 /// Construct a VPlan with original preheader \p Preheader, trip count \p TC
2469 /// and \p Entry to the plan. At the moment, \p Preheader and \p Entry need to
2470 /// be disconnected, as the bypass blocks between them are not yet modeled in
2471 /// VPlan.
2472 VPlan(VPBasicBlock *Preheader, VPValue *TC, VPBasicBlock *Entry)
2473 : VPlan(Preheader, Entry) {
2474 TripCount = TC;
2475 }
2476
2477 /// Construct a VPlan with original preheader \p Preheader and \p Entry to
2478 /// the plan. At the moment, \p Preheader and \p Entry need to be
2479 /// disconnected, as the bypass blocks between them are not yet modeled in
2480 /// VPlan.
2481 VPlan(VPBasicBlock *Preheader, VPBasicBlock *Entry)
2482 : Entry(Entry), Preheader(Preheader) {
2483 Entry->setPlan(this);
2484 Preheader->setPlan(this);
2485 assert(Preheader->getNumSuccessors() == 0 &&
2486 Preheader->getNumPredecessors() == 0 &&
2487 "preheader must be disconnected");
2488 }
2489
2490 ~VPlan();
2491
2492 /// Create an initial VPlan with preheader and entry blocks. Creates a
2493 /// VPExpandSCEVRecipe for \p TripCount and uses it as plan's trip count.
2494 static VPlanPtr createInitialVPlan(const SCEV *TripCount,
2495 ScalarEvolution &PSE);
2496
2497 /// Prepare the plan for execution, setting up the required live-in values.
2498 void prepareToExecute(Value *TripCount, Value *VectorTripCount,
2499 Value *CanonicalIVStartValue, VPTransformState &State,
2500 bool IsEpilogueVectorization);
2501
2502 /// Generate the IR code for this VPlan.
2503 void execute(VPTransformState *State);
2504
2505 VPBasicBlock *getEntry() { return Entry; }
2506 const VPBasicBlock *getEntry() const { return Entry; }
2507
2508 /// The trip count of the original loop.
2510 assert(TripCount && "trip count needs to be set before accessing it");
2511 return TripCount;
2512 }
2513
2514 /// The backedge taken count of the original loop.
2516 if (!BackedgeTakenCount)
2517 BackedgeTakenCount = new VPValue();
2518 return BackedgeTakenCount;
2519 }
2520
2521 /// The vector trip count.
2522 VPValue &getVectorTripCount() { return VectorTripCount; }
2523
2524 /// Mark the plan to indicate that using Value2VPValue is not safe any
2525 /// longer, because it may be stale.
2526 void disableValue2VPValue() { Value2VPValueEnabled = false; }
2527
2528 void addVF(ElementCount VF) { VFs.insert(VF); }
2529
2531 assert(hasVF(VF) && "Cannot set VF not already in plan");
2532 VFs.clear();
2533 VFs.insert(VF);
2534 }
2535
2536 bool hasVF(ElementCount VF) { return VFs.count(VF); }
2537
2538 bool hasScalarVFOnly() const { return VFs.size() == 1 && VFs[0].isScalar(); }
2539
2540 bool hasUF(unsigned UF) const { return UFs.empty() || UFs.contains(UF); }
2541
2542 void setUF(unsigned UF) {
2543 assert(hasUF(UF) && "Cannot set the UF not already in plan");
2544 UFs.clear();
2545 UFs.insert(UF);
2546 }
2547
2548 /// Return a string with the name of the plan and the applicable VFs and UFs.
2549 std::string getName() const;
2550
2551 void setName(const Twine &newName) { Name = newName.str(); }
2552
2553 void addVPValue(Value *V, VPValue *VPV) {
2554 assert((Value2VPValueEnabled || VPV->isLiveIn()) &&
2555 "Value2VPValue mapping may be out of date!");
2556 assert(V && "Trying to add a null Value to VPlan");
2557 assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
2558 Value2VPValue[V] = VPV;
2559 }
2560
2561 /// Returns the VPValue for \p V. \p OverrideAllowed can be used to disable
2562 /// /// checking whether it is safe to query VPValues using IR Values.
2563 VPValue *getVPValue(Value *V, bool OverrideAllowed = false) {
2564 assert(V && "Trying to get the VPValue of a null Value");
2565 assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
2566 assert((Value2VPValueEnabled || OverrideAllowed ||
2567 Value2VPValue[V]->isLiveIn()) &&
2568 "Value2VPValue mapping may be out of date!");
2569 return Value2VPValue[V];
2570 }
2571
2572 /// Gets the VPValue for \p V or adds a new live-in (if none exists yet) for
2573 /// \p V.
2575 assert(V && "Trying to get or add the VPValue of a null Value");
2576 if (!Value2VPValue.count(V)) {
2577 VPValue *VPV = new VPValue(V);
2578 VPLiveInsToFree.push_back(VPV);
2579 addVPValue(V, VPV);
2580 }
2581
2582 return getVPValue(V);
2583 }
2584
2586 assert(Value2VPValueEnabled &&
2587 "IR value to VPValue mapping may be out of date!");
2588 Value2VPValue.erase(V);
2589 }
2590
2591#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2592 /// Print this VPlan to \p O.
2593 void print(raw_ostream &O) const;
2594
2595 /// Print this VPlan in DOT format to \p O.
2596 void printDOT(raw_ostream &O) const;
2597
2598 /// Dump the plan to stderr (for debugging).
2599 LLVM_DUMP_METHOD void dump() const;
2600#endif
2601
2602 /// Returns a range mapping the values the range \p Operands to their
2603 /// corresponding VPValues.
2604 iterator_range<mapped_iterator<Use *, std::function<VPValue *(Value *)>>>
2606 std::function<VPValue *(Value *)> Fn = [this](Value *Op) {
2607 return getVPValueOrAddLiveIn(Op);
2608 };
2609 return map_range(Operands, Fn);
2610 }
2611
2612 /// Returns the VPRegionBlock of the vector loop.
2614 return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
2615 }
2617 return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
2618 }
2619
2620 /// Returns the canonical induction recipe of the vector loop.
2623 if (EntryVPBB->empty()) {
2624 // VPlan native path.
2625 EntryVPBB = cast<VPBasicBlock>(EntryVPBB->getSingleSuccessor());
2626 }
2627 return cast<VPCanonicalIVPHIRecipe>(&*EntryVPBB->begin());
2628 }
2629
2630 /// Find and return the VPActiveLaneMaskPHIRecipe from the header - there
2631 /// be only one at most. If there isn't one, then return nullptr.
2633
2634 void addLiveOut(PHINode *PN, VPValue *V);
2635
2637 delete LiveOuts[PN];
2638 LiveOuts.erase(PN);
2639 }
2640
2642 return LiveOuts;
2643 }
2644
2645 VPValue *getSCEVExpansion(const SCEV *S) const {
2646 auto I = SCEVToExpansion.find(S);
2647 if (I == SCEVToExpansion.end())
2648 return nullptr;
2649 return I->second;
2650 }
2651
2652 void addSCEVExpansion(const SCEV *S, VPValue *V) {
2653 assert(!SCEVToExpansion.contains(S) && "SCEV already expanded");
2654 SCEVToExpansion[S] = V;
2655 }
2656
2657 /// \return The block corresponding to the original preheader.
2658 VPBasicBlock *getPreheader() { return Preheader; }
2659 const VPBasicBlock *getPreheader() const { return Preheader; }
2660
2661private:
2662 /// Add to the given dominator tree the header block and every new basic block
2663 /// that was created between it and the latch block, inclusive.
2664 static void updateDominatorTree(DominatorTree *DT, BasicBlock *LoopLatchBB,
2665 BasicBlock *LoopPreHeaderBB,
2666 BasicBlock *LoopExitBB);
2667};
2668
2669#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2670/// VPlanPrinter prints a given VPlan to a given output stream. The printing is
2671/// indented and follows the dot format.
2673 raw_ostream &OS;
2674 const VPlan &Plan;
2675 unsigned Depth = 0;
2676 unsigned TabWidth = 2;
2677 std::string Indent;
2678 unsigned BID = 0;
2680
2682
2683 /// Handle indentation.
2684 void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
2685
2686 /// Print a given \p Block of the Plan.
2687 void dumpBlock(const VPBlockBase *Block);
2688
2689 /// Print the information related to the CFG edges going out of a given
2690 /// \p Block, followed by printing the successor blocks themselves.
2691 void dumpEdges(const VPBlockBase *Block);
2692
2693 /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
2694 /// its successor blocks.
2695 void dumpBasicBlock(const VPBasicBlock *BasicBlock);
2696
2697 /// Print a given \p Region of the Plan.
2698 void dumpRegion(const VPRegionBlock *Region);
2699
2700 unsigned getOrCreateBID(const VPBlockBase *Block) {
2701 return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
2702 }
2703
2704 Twine getOrCreateName(const VPBlockBase *Block);
2705
2706 Twine getUID(const VPBlockBase *Block);
2707
2708 /// Print the information related to a CFG edge between two VPBlockBases.
2709 void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
2710 const Twine &Label);
2711
2712public:
2714 : OS(O), Plan(P), SlotTracker(&P) {}
2715
2716 LLVM_DUMP_METHOD void dump();
2717};
2718
2720 const Value *V;
2721
2722 VPlanIngredient(const Value *V) : V(V) {}
2723
2724 void print(raw_ostream &O) const;
2725};
2726
2728 I.print(OS);
2729 return OS;
2730}
2731
2733 Plan.print(OS);
2734 return OS;
2735}
2736#endif
2737
2738//===----------------------------------------------------------------------===//
2739// VPlan Utilities
2740//===----------------------------------------------------------------------===//
2741
2742/// Class that provides utilities for VPBlockBases in VPlan.
2744public:
2745 VPBlockUtils() = delete;
2746
2747 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
2748 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
2749 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
2750 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
2751 /// have neither successors nor predecessors.
2752 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
2753 assert(NewBlock->getSuccessors().empty() &&
2754 NewBlock->getPredecessors().empty() &&
2755 "Can't insert new block with predecessors or successors.");
2756 NewBlock->setParent(BlockPtr->getParent());
2757 SmallVector<VPBlockBase *> Succs(BlockPtr->successors());
2758 for (VPBlockBase *Succ : Succs) {
2759 disconnectBlocks(BlockPtr, Succ);
2760 connectBlocks(NewBlock, Succ);
2761 }
2762 connectBlocks(BlockPtr, NewBlock);
2763 }
2764
2765 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
2766 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
2767 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
2768 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
2769 /// and \p IfTrue and \p IfFalse must have neither successors nor
2770 /// predecessors.
2771 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
2772 VPBlockBase *BlockPtr) {
2773 assert(IfTrue->getSuccessors().empty() &&
2774 "Can't insert IfTrue with successors.");
2775 assert(IfFalse->getSuccessors().empty() &&
2776 "Can't insert IfFalse with successors.");
2777 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
2778 IfTrue->setPredecessors({BlockPtr});
2779 IfFalse->setPredecessors({BlockPtr});
2780 IfTrue->setParent(BlockPtr->getParent());
2781 IfFalse->setParent(BlockPtr->getParent());
2782 }
2783
2784 /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
2785 /// the successors of \p From and \p From to the predecessors of \p To. Both
2786 /// VPBlockBases must have the same parent, which can be null. Both
2787 /// VPBlockBases can be already connected to other VPBlockBases.
2789 assert((From->getParent() == To->getParent()) &&
2790 "Can't connect two block with different parents");
2791 assert(From->getNumSuccessors() < 2 &&
2792 "Blocks can't have more than two successors.");
2793 From->appendSuccessor(To);
2794 To->appendPredecessor(From);
2795 }
2796
2797 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
2798 /// from the successors of \p From and \p From from the predecessors of \p To.
2800 assert(To && "Successor to disconnect is null.");
2801 From->removeSuccessor(To);
2802 To->removePredecessor(From);
2803 }
2804
2805 /// Return an iterator range over \p Range which only includes \p BlockTy
2806 /// blocks. The accesses are casted to \p BlockTy.
2807 template <typename BlockTy, typename T>
2808 static auto blocksOnly(const T &Range) {
2809 // Create BaseTy with correct const-ness based on BlockTy.
2810 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
2811 const VPBlockBase, VPBlockBase>;
2812
2813 // We need to first create an iterator range over (const) BlocktTy & instead
2814 // of (const) BlockTy * for filter_range to work properly.
2815 auto Mapped =
2816 map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
2818 Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
2819 return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
2820 return cast<BlockTy>(&Block);
2821 });
2822 }
2823};
2824
2827 InterleaveGroupMap;
2828
2829 /// Type for mapping of instruction based interleave groups to VPInstruction
2830 /// interleave groups
2833
2834 /// Recursively \p Region and populate VPlan based interleave groups based on
2835 /// \p IAI.
2836 void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,
2838 /// Recursively traverse \p Block and populate VPlan based interleave groups
2839 /// based on \p IAI.
2840 void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
2842
2843public:
2845
2848 // Avoid releasing a pointer twice.
2849 for (auto &I : InterleaveGroupMap)
2850 DelSet.insert(I.second);
2851 for (auto *Ptr : DelSet)
2852 delete Ptr;
2853 }
2854
2855 /// Get the interleave group that \p Instr belongs to.
2856 ///
2857 /// \returns nullptr if doesn't have such group.
2860 return InterleaveGroupMap.lookup(Instr);
2861 }
2862};
2863
2864/// Class that maps (parts of) an existing VPlan to trees of combined
2865/// VPInstructions.
2867 enum class OpMode { Failed, Load, Opcode };
2868
2869 /// A DenseMapInfo implementation for using SmallVector<VPValue *, 4> as
2870 /// DenseMap keys.
2871 struct BundleDenseMapInfo {
2872 static SmallVector<VPValue *, 4> getEmptyKey() {
2873 return {reinterpret_cast<VPValue *>(-1)};
2874 }
2875
2876 static SmallVector<VPValue *, 4> getTombstoneKey() {
2877 return {reinterpret_cast<VPValue *>(-2)};
2878 }
2879
2880 static unsigned getHashValue(const SmallVector<VPValue *, 4> &V) {
2881 return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
2882 }
2883
2884 static bool isEqual(const SmallVector<VPValue *, 4> &LHS,
2886 return LHS == RHS;
2887 }
2888 };
2889
2890 /// Mapping of values in the original VPlan to a combined VPInstruction.
2892 BundleToCombined;
2893
2895
2896 /// Basic block to operate on. For now, only instructions in a single BB are
2897 /// considered.
2898 const VPBasicBlock &BB;
2899
2900 /// Indicates whether we managed to combine all visited instructions or not.
2901 bool CompletelySLP = true;
2902
2903 /// Width of the widest combined bundle in bits.
2904 unsigned WidestBundleBits = 0;
2905
2906 using MultiNodeOpTy =
2907 typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;
2908
2909 // Input operand bundles for the current multi node. Each multi node operand
2910 // bundle contains values not matching the multi node's opcode. They will
2911 // be reordered in reorderMultiNodeOps, once we completed building a
2912 // multi node.
2913 SmallVector<MultiNodeOpTy, 4> MultiNodeOps;
2914
2915 /// Indicates whether we are building a multi node currently.
2916 bool MultiNodeActive = false;
2917
2918 /// Check if we can vectorize Operands together.
2919 bool areVectorizable(ArrayRef<VPValue *> Operands) const;
2920
2921 /// Add combined instruction \p New for the bundle \p Operands.
2922 void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);
2923
2924 /// Indicate we hit a bundle we failed to combine. Returns nullptr for now.
2925 VPInstruction *markFailed();
2926
2927 /// Reorder operands in the multi node to maximize sequential memory access
2928 /// and commutative operations.
2929 SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();
2930
2931 /// Choose the best candidate to use for the lane after \p Last. The set of
2932 /// candidates to choose from are values with an opcode matching \p Last's
2933 /// or loads consecutive to \p Last.
2934 std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,
2935 SmallPtrSetImpl<VPValue *> &Candidates,
2937
2938#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2939 /// Print bundle \p Values to dbgs().
2940 void dumpBundle(ArrayRef<VPValue *> Values);
2941#endif
2942
2943public:
2944 VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {}
2945
2946 ~VPlanSlp() = default;
2947
2948 /// Tries to build an SLP tree rooted at \p Operands and returns a
2949 /// VPInstruction combining \p Operands, if they can be combined.
2951
2952 /// Return the width of the widest combined bundle in bits.
2953 unsigned getWidestBundleBits() const { return WidestBundleBits; }
2954
2955 /// Return true if all visited instruction can be combined.
2956 bool isCompletelySLP() const { return CompletelySLP; }
2957};
2958
2959namespace vputils {
2960
2961/// Returns true if only the first lane of \p Def is used.
2962bool onlyFirstLaneUsed(VPValue *Def);
2963
2964/// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p
2965/// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in
2966/// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's
2967/// pre-header already contains a recipe expanding \p Expr, return it. If not,
2968/// create a new one.
2970 ScalarEvolution &SE);
2971
2972/// Returns true if \p VPV is uniform after vectorization.
2974 // A value defined outside the vector region must be uniform after
2975 // vectorization inside a vector region.
2977 return true;
2978 VPRecipeBase *Def = VPV->getDefiningRecipe();
2979 assert(Def && "Must have definition for value defined inside vector region");
2980 if (auto Rep = dyn_cast<VPReplicateRecipe>(Def))
2981 return Rep->isUniform();
2982 return false;
2983}
2984} // end namespace vputils
2985
2986} // end namespace llvm
2987
2988#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
aarch64 promote const
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
always inline
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
RelocType Type
Definition: COFFYAML.cpp:391
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
uint64_t Addr
std::string Name
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1269
Flatten the CFG
Hexagon Common GEP
std::pair< BasicBlock *, unsigned > BlockTy
A pair of (basic block, score).
#define I(x, y, z)
Definition: MD5.cpp:58
mir Rename Register Operands
This file implements a map that provides insertion order iteration.
#define P(N)
static cl::opt< RegAllocEvictionAdvisorAnalysis::AdvisorMode > Mode("regalloc-enable-advisor", cl::Hidden, cl::init(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default), cl::desc("Enable regalloc advisor mode"), cl::values(clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default, "default", "Default"), clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release, "release", "precompiled"), clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development, "development", "for training")))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file implements the SmallBitVector class.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file contains the declarations of the entities induced by Vectorization Plans,...
#define VP_CLASSOF_IMPL(VPDefID)
Definition: VPlan.h:796
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:77
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
Definition: ArrayRef.h:193
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:428
A debug info location.
Definition: DebugLoc.h:33
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:145
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:20
void setAllowContract(bool B=true)
Definition: FMF.h:91
bool noSignedZeros() const
Definition: FMF.h:68
bool noInfs() const
Definition: FMF.h:67
void setAllowReciprocal(bool B=true)
Definition: FMF.h:88
bool allowReciprocal() const
Definition: FMF.h:69
void setNoSignedZeros(bool B=true)
Definition: FMF.h:85
bool allowReassoc() const
Flag queries.
Definition: FMF.h:65
bool approxFunc() const
Definition: FMF.h:71
void setNoNaNs(bool B=true)
Definition: FMF.h:79
void setAllowReassoc(bool B=true)
Flag setters.
Definition: FMF.h:76
bool noNaNs() const
Definition: FMF.h:66
void setApproxFunc(bool B=true)
Definition: FMF.h:94
void setNoInfs(bool B=true)
Definition: FMF.h:82
bool allowContract() const
Definition: FMF.h:70
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
A struct for saving information about induction variables.
InductionKind
This enum represents the kinds of inductions that we support.
InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization ...
The group of interleaved loads/stores sharing the same stride and close to each other.
Definition: VectorUtils.h:636
uint32_t getFactor() const
Definition: VectorUtils.h:652
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
Definition: VectorUtils.h:706
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:778
An instruction for reading from memory.
Definition: Instructions.h:177
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
Definition: MapVector.h:173
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:69
This class represents an analyzed expression in the program.
The main scalar evolution driver.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:88
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:219
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:213
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
void clear()
Completely clear the SetVector.
Definition: SetVector.h:224
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:83
This class provides computation of slot numbers for LLVM Assembly writing.
Definition: AsmWriter.cpp:678
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:312
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This class represents a truncation of integer types.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:348
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Iterator to iterate over vectorization factors in a VFRange.
Definition: VPlan.h:109
ElementCount operator*() const
Definition: VPlan.h:117
iterator & operator++()
Definition: VPlan.h:119
iterator(ElementCount VF)
Definition: VPlan.h:113
bool operator==(const iterator &Other) const
Definition: VPlan.h:115
A recipe for generating the active lane mask for the vector loop that is used to predicate the vector...
Definition: VPlan.h:2056
void execute(VPTransformState &State) override
Generate the active lane mask phi of the vector loop.
static bool classof(const VPHeaderPHIRecipe *D)
Definition: VPlan.h:2068
VPActiveLaneMaskPHIRecipe(VPValue *StartMask, DebugLoc DL)
Definition: VPlan.h:2060
~VPActiveLaneMaskPHIRecipe() override=default
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2192
RecipeListTy::const_iterator const_iterator
Definition: VPlan.h:2214
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2260
RecipeListTy::const_reverse_iterator const_reverse_iterator
Definition: VPlan.h:2216
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:2213
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
Definition: VPlan.cpp:334
RecipeListTy & getRecipeList()
Returns a reference to the list of recipes.
Definition: VPlan.h:2239
iterator end()
Definition: VPlan.h:2223
VPBasicBlock(const Twine &Name="", VPRecipeBase *Recipe=nullptr)
Definition: VPlan.h:2201
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:2221
RecipeListTy::reverse_iterator reverse_iterator
Definition: VPlan.h:2215
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
Definition: VPlan.h:2270
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:208
~VPBasicBlock() override
Definition: VPlan.h:2207
VPRegionBlock * getEnclosingLoopRegion()
Definition: VPlan.cpp:436
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
Definition: VPlan.cpp:401
const_reverse_iterator rbegin() const
Definition: VPlan.h:2227
reverse_iterator rend()
Definition: VPlan.h:2228
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:411
VPRecipeBase & back()
Definition: VPlan.h:2236
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPBsicBlock to O, prefixing all lines with Indent.
Definition: VPlan.cpp:504
const VPRecipeBase & front() const
Definition: VPlan.h:2233
const_iterator begin() const
Definition: VPlan.h:2222
VPRecipeBase & front()
Definition: VPlan.h:2234
bool isExiting() const
Returns true if the block is exiting it's parent region.
Definition: VPlan.cpp:487
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition: VPlan.cpp:475
const VPRecipeBase & back() const
Definition: VPlan.h:2235
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:2251
bool empty() const
Definition: VPlan.h:2232
const_iterator end() const
Definition: VPlan.h:2224
static bool classof(const VPBlockBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:2247
static RecipeListTy VPBasicBlock::* getSublistAccess(VPRecipeBase *)
Returns a pointer to a member of the recipe list.
Definition: VPlan.h:2242
reverse_iterator rbegin()
Definition: VPlan.h:2226
size_t size() const
Definition: VPlan.h:2231
const_reverse_iterator rend() const
Definition: VPlan.h:2229
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
Definition: VPlan.h:1566
VPBlendRecipe(PHINode *Phi, ArrayRef< VPValue * > Operands)
The blend operation is a User of the incoming values and of their respective masks,...
Definition: VPlan.h:1573
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:1603
VPValue * getIncomingValue(unsigned Idx) const
Return incoming value number Idx.
Definition: VPlan.h:1588
VPValue * getMask(unsigned Idx) const
Return mask number Idx.
Definition: VPlan.h:1591
unsigned getNumIncomingValues() const
Return the number of incoming values, taking into account that a single incoming value has no mask.
Definition: VPlan.h:1585
void execute(VPTransformState &State) override
Generate the phi/select nodes.
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:418
VPRegionBlock * getParent()
Definition: VPlan.h:490
VPBlocksTy & getPredecessors()
Definition: VPlan.h:521
const VPBasicBlock * getExitingBasicBlock() const
Definition: VPlan.cpp:173
LLVM_DUMP_METHOD void dump() const
Dump this VPBlockBase to dbgs().
Definition: VPlan.h:657
void setName(const Twine &newName)
Definition: VPlan.h:483
size_t getNumSuccessors() const
Definition: VPlan.h:535
iterator_range< VPBlockBase ** > successors()
Definition: VPlan.h:518
virtual void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const =0
Print plain-text dump of this VPBlockBase to O, prefixing all lines with Indent.
void printSuccessors(raw_ostream &O, const Twine &Indent) const
Print the successors of this block to O, prefixing all lines with Indent.
Definition: VPlan.cpp:492
bool isLegalToHoistInto()
Return true if it is legal to hoist instructions into this block.
Definition: VPlan.h:622
virtual ~VPBlockBase()=default
void print(raw_ostream &O) const
Print plain-text dump of this VPlan to O.
Definition: VPlan.h:647
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:571
size_t getNumPredecessors() const
Definition: VPlan.h:536
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:602
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:195
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:520
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:203
VPlan * getPlan()
Definition: VPlan.cpp:146
void setPlan(VPlan *ParentPlan)
Sets the pointer of the plan containing the block.
Definition: VPlan.cpp:165
const VPRegionBlock * getParent() const
Definition: VPlan.h:491
void printAsOperand(raw_ostream &OS, bool PrintType) const
Definition: VPlan.h:633
const std::string & getName() const
Definition: VPlan.h:481
void clearSuccessors()
Remove all the successors of this block.
Definition: VPlan.h:612
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:561
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition: VPlan.h:593
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:531
virtual void execute(VPTransformState *State)=0
The method which generates the output IR that correspond to this VPBlockBase, thereby "executing" the...
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:555
void clearPredecessors()
Remove all the predecessor of this block.
Definition: VPlan.h:609
enum { VPBasicBlockSC, VPRegionBlockSC } VPBlockTy
An enumeration for keeping track of the concrete subclass of VPBlockBase that are actually instantiat...
Definition: VPlan.h:475
unsigned getVPBlockID() const
Definition: VPlan.h:488
VPBlockBase(const unsigned char SC, const std::string &N)
Definition: VPlan.h:467
VPBlocksTy & getSuccessors()
Definition: VPlan.h:516
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:187
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:151
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
Definition: VPlan.h:584
void setParent(VPRegionBlock *P)
Definition: VPlan.h:501
virtual void dropAllReferences(VPValue *NewValue)=0
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:577
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:525
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:515
Class that provides utilities for VPBlockBases in VPlan.
Definition: VPlan.h:2743
static auto blocksOnly(const T &Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition: VPlan.h:2808
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition: VPlan.h:2752
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition: VPlan.h:2771
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2799
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2788
A recipe for generating conditional branches on the bits of a mask.
Definition: VPlan.h:1807
VPValue * getMask() const
Return the mask used by this recipe.
Definition: VPlan.h:1835
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.h:1823
VPBranchOnMaskRecipe(VPValue *BlockInMask)
Definition: VPlan.h:1809
bool usesScalars(const VPValue *Op) const override
Returns true if the recipe uses scalars of operand Op.
Definition: VPlan.h:1842
void execute(VPTransformState &State) override
Generate the extraction of the appropriate bit from the block mask and the conditional branch.
Canonical scalar induction phi of the vector loop.
Definition: VPlan.h:2009
bool isCanonical(InductionDescriptor::InductionKind Kind, VPValue *Start, VPValue *Step, Type *Ty) const
Check if the induction described by Kind, /p Start and Step is canonical, i.e.
~VPCanonicalIVPHIRecipe() override=default
static bool classof(const VPHeaderPHIRecipe *D)
Definition: VPlan.h:2020
VPCanonicalIVPHIRecipe(VPValue *StartV, DebugLoc DL)
Definition: VPlan.h:2013
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:2039
void execute(VPTransformState &State) override
Generate the canonical scalar induction phi of the vector loop.
const Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:2034
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
This class augments a recipe with a set of VPValues defined by the recipe.
Definition: VPlanValue.h:306
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:388
unsigned getVPDefID() const
Definition: VPlanValue.h:420
A recipe for converting the canonical IV value to the corresponding value of an IV with different sta...
Definition: VPlan.h:2114
void execute(VPTransformState &State) override
Generate the transformed value of the induction at offset StartValue (1.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPDerivedIVRecipe(const InductionDescriptor &IndDesc, VPValue *Start, VPCanonicalIVPHIRecipe *CanonicalIV, VPValue *Step, Type *ResultTy)
Definition: VPlan.h:2123
VPValue * getStepValue() const
Definition: VPlan.h:2145
VPValue * getCanonicalIV() const
Definition: VPlan.h:2144
~VPDerivedIVRecipe() override=default
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:2148
VPValue * getStartValue() const
Definition: VPlan.h:2143
Recipe to expand a SCEV expression.
Definition: VPlan.h:1980
VPExpandSCEVRecipe(const SCEV *Expr, ScalarEvolution &SE)
Definition: VPlan.h:1985
const SCEV * getSCEV() const
Definition: VPlan.h:2002
void execute(VPTransformState &State) override
Generate a canonical vector induction variable of the vector loop, with.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
~VPExpandSCEVRecipe() override=default
A pure virtual base class for all recipes modeling header phis, including phis for first order recurr...
Definition: VPlan.h:1281
static bool classof(const VPValue *V)
Definition: VPlan.h:1298
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override=0
Print the recipe.
virtual VPValue * getBackedgeValue()
Returns the incoming value from the loop backedge.
Definition: VPlan.h:1325
VPValue * getStartValue()
Returns the start value of the phi, if one is set.
Definition: VPlan.h:1314
void setStartValue(VPValue *V)
Update the start value of the recipe.
Definition: VPlan.h:1322
VPValue * getStartValue() const
Definition: VPlan.h:1317
static bool classof(const VPRecipeBase *B)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1294
void execute(VPTransformState &State) override=0
Generate the phi nodes.
virtual VPRecipeBase & getBackedgeRecipe()
Returns the backedge value as a recipe.
Definition: VPlan.h:1331
VPHeaderPHIRecipe(unsigned char VPDefID, Instruction *UnderlyingInstr, VPValue *Start=nullptr)
Definition: VPlan.h:1283
~VPHeaderPHIRecipe() override=default
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:816
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:924
VPInstruction * clone() const
Definition: VPlan.h:869
VPInstruction(unsigned Opcode, ArrayRef< VPValue * > Operands, DebugLoc DL, const Twine &Name="")
Definition: VPlan.h:858
@ CanonicalIVIncrementForPartNUW
Definition: VPlan.h:836
@ FirstOrderRecurrenceSplice
Definition: VPlan.h:822
@ CanonicalIVIncrementNUW
Definition: VPlan.h:832
@ CanonicalIVIncrementForPart
Definition: VPlan.h:835
@ CalculateTripCountMinusVF
Definition: VPlan.h:830
bool hasResult() const
Definition: VPlan.h:898
void setUnderlyingInstr(Instruction *I)
Definition: VPlan.h:855
LLVM_DUMP_METHOD void dump() const
Print the VPInstruction to dbgs() (for debugging).
unsigned getOpcode() const
Definition: VPlan.h:874
VPInstruction(unsigned Opcode, std::initializer_list< VPValue * > Operands, DebugLoc DL={}, const Twine &Name="")
Definition: VPlan.h:863
void setFastMathFlags(FastMathFlags FMFNew)
Set the fast-math flags.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the VPInstruction to O.
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: VPlan.h:891
void execute(VPTransformState &State) override
Generate the instruction.
VPInterleaveRecipe is a recipe for transforming an interleave group of load or stores into one wide l...
Definition: VPlan.h:1617
bool onlyFirstLaneUsed(const VPValue *Op) const override
The recipe only uses the first lane of the address.
Definition: VPlan.h:1691
~VPInterleaveRecipe() override=default
VPValue * getAddr() const
Return the address accessed by this recipe.
Definition: VPlan.h:1653
VPInterleaveRecipe(const InterleaveGroup< Instruction > *IG, VPValue *Addr, ArrayRef< VPValue * > StoredValues, VPValue *Mask, bool NeedsMaskForGaps)
Definition: VPlan.h:1629
VPValue * getMask() const
Return the mask used by this recipe.
Definition: VPlan.h:1659
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate the wide load or store, and shuffles.
ArrayRef< VPValue * > getStoredValues() const
Return the VPValues stored by this interleave group.
Definition: VPlan.h:1666
const InterleaveGroup< Instruction > * getInterleaveGroup()
Definition: VPlan.h:1682
unsigned getNumStoreOperands() const
Returns the number of stored operands of this interleave group.
Definition: VPlan.h:1686
InterleaveGroup< VPInstruction > * getInterleaveGroup(VPInstruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VPlan.h:2859
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
Definition: VPlan.h:141
static VPLane getLastLaneForVF(const ElementCount &VF)
Definition: VPlan.h:167
static unsigned getNumCachedLanes(const ElementCount &VF)
Returns the maxmimum number of lanes that we are able to consider caching for VF.
Definition: VPlan.h:210
Value * getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const
Returns an expression describing the lane index that can be used at runtime.
Definition: VPlan.cpp:66
VPLane(unsigned Lane, Kind LaneKind)
Definition: VPlan.h:163
Kind getKind() const
Returns the Kind of lane offset.
Definition: VPlan.h:191
bool isFirstLane() const
Returns true if this is the first lane of the whole vector.
Definition: VPlan.h:194
unsigned getKnownLane() const
Returns a compile-time known value for the lane index and asserts if the lane can only be calculated ...
Definition: VPlan.h:181
static VPLane getFirstLane()
Definition: VPlan.h:165
Kind
Kind describes how to interpret Lane.
Definition: VPlan.h:144
@ ScalableLast
For ScalableLast, Lane is the offset from the start of the last N-element subvector in a scalable vec...
@ First
For First, Lane is the index into the first N elements of a fixed-vector <N x <ElTy>> or a scalable v...
unsigned mapToCacheIndex(const ElementCount &VF) const
Maps the lane to a cache index based on VF.
Definition: VPlan.h:197
A value that is used outside the VPlan.
Definition: VPlan.h:663
VPLiveOut(PHINode *Phi, VPValue *Op)
Definition: VPlan.h:667
static bool classof(const VPUser *U)
Definition: VPlan.h:670
bool usesScalars(const VPValue *Op) const override
Returns true if the VPLiveOut uses scalars of operand Op.
Definition: VPlan.h:682
void print(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print the VPLiveOut to O.
PHINode * getPhi() const
Definition: VPlan.h:688
void fixPhi(VPlan &Plan, VPTransformState &State)
Fixup the wrapped LCSSA phi node in the unique exit block.
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
Definition: VPlan.h:1854
~VPPredInstPHIRecipe() override=default
bool usesScalars(const VPValue *Op) const override
Returns true if the recipe uses scalars of operand Op.
Definition: VPlan.h:1874
VPPredInstPHIRecipe(VPValue *PredV)
Construct a VPPredInstPHIRecipe given PredInst whose value needs a phi nodes after merging back from ...
Definition: VPlan.h:1858
void execute(VPTransformState &State) override
Generates phi nodes for live-outs as needed to retain SSA form.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:703
bool mayReadFromMemory() const
Returns true if the recipe may read from memory.
VPRecipeBase(const unsigned char SC, ArrayRef< VPValue * > Operands)
Definition: VPlan.h:711
bool mayReadOrWriteMemory() const
Returns true if the recipe may read from or write to memory.
Definition: VPlan.h:790
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
Instruction * getUnderlyingInstr()
Returns the underlying instruction, if the recipe is a VPValue or nullptr otherwise.
Definition: VPlan.h:758
bool mayWriteToMemory() const
Returns true if the recipe may write to memory.
virtual ~VPRecipeBase()=default
VPBasicBlock * getParent()
Definition: VPlan.h:720
virtual void execute(VPTransformState &State)=0
The method which generates the output IR instructions that correspond to this VPRecipe,...
void moveBefore(VPBasicBlock &BB, iplist< VPRecipeBase >::iterator I)
Unlink this recipe and insert into BB before I.
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
void insertAfter(VPRecipeBase *InsertPos)
Insert an unlinked Recipe into a basic block immediately after the specified Recipe.
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:766
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
VPRecipeBase(const unsigned char SC, iterator_range< IterT > Operands)
Definition: VPlan.h:715
const VPBasicBlock * getParent() const
Definition: VPlan.h:721
const Instruction * getUnderlyingInstr() const
Definition: VPlan.h:761
static bool classof(const VPUser *U)
Definition: VPlan.h:771
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
bool isPhi() const
Returns true for PHI-like recipes.
Definition: VPlan.h:779
void moveAfter(VPRecipeBase *MovePos)
Unlink this recipe from its current VPBasicBlock and insert it into the VPBasicBlock that MovePos liv...
Class to record LLVM IR flag for a recipe along with it.
Definition: VPlan.h:946
ExactFlagsTy ExactFlags
Definition: VPlan.h:978
FastMathFlagsTy FMFs
Definition: VPlan.h:980
VPRecipeWithIRFlags(const unsigned char SC, iterator_range< IterT > Operands)
Definition: VPlan.h:986
void setFlags(Instruction *I) const
Set the IR flags for I.
Definition: VPlan.h:1050
bool isInBounds() const
Definition: VPlan.h:1076
unsigned char AllFlags
Definition: VPlan.h:981
GEPFlagsTy GEPFlags
Definition: VPlan.h:979
static bool classof(const VPRecipeBase *R)
Definition: VPlan.h:1019
void dropPoisonGeneratingFlags()
Drop all poison-generating flags.
Definition: VPlan.h:1026
VPRecipeWithIRFlags(const unsigned char SC, iterator_range< IterT > Operands, Instruction &I)
Definition: VPlan.h:993
FastMathFlags getFastMathFlags() const
Definition: VPlan.h:1083
WrapFlagsTy WrapFlags
Definition: VPlan.h:977
void printFlags(raw_ostream &O) const
A recipe for handling reduction phis.
Definition: VPlan.h:1515
VPReductionPHIRecipe(PHINode *Phi, const RecurrenceDescriptor &RdxDesc, VPValue &Start, bool IsInLoop=false, bool IsOrdered=false)
Create a new VPReductionPHIRecipe for the reduction Phi described by RdxDesc.
Definition: VPlan.h:1528
bool isOrdered() const
Returns true, if the phi is part of an ordered reduction.
Definition: VPlan.h:1558
~VPReductionPHIRecipe() override=default
bool isInLoop() const
Returns true, if the phi is part of an in-loop reduction.
Definition: VPlan.h:1561
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate the phi/select nodes.
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1540
const RecurrenceDescriptor & getRecurrenceDescriptor() const
Definition: VPlan.h:1553
A recipe to represent inloop reduction operations, performing a reduction on a vector operand into a ...
Definition: VPlan.h:1701
VPValue * getVecOp() const
The VPValue of the vector value to be reduced.
Definition: VPlan.h:1733
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPValue * getCondOp() const
The VPValue of the condition for the block.
Definition: VPlan.h:1735
~VPReductionRecipe() override=default
VPValue * getChainOp() const
The VPValue of the scalar Chain being accumulated.
Definition: VPlan.h:1731
VPReductionRecipe(const RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp, const TargetTransformInfo *TTI)
Definition: VPlan.h:1708
void execute(VPTransformState &State) override
Generate the reduction in the loop.
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2316
const VPBlockBase * getEntry() const
Definition: VPlan.h:2355
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:2387
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
Definition: VPlan.cpp:518
void setExiting(VPBlockBase *ExitingBlock)
Set ExitingBlock as the exiting VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:2372
VPBlockBase * getExiting()
Definition: VPlan.h:2368
void setEntry(VPBlockBase *EntryBlock)
Set EntryBlock as the entry VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:2360
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPRegionBlock to O (recursively), prefixing all lines with Indent.
Definition: VPlan.cpp:577
VPRegionBlock(const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:2338
VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exiting, const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:2329
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPRegionBlock,...
Definition: VPlan.cpp:525
const VPBlockBase * getExiting() const
Definition: VPlan.h:2367
VPBlockBase * getEntry()
Definition: VPlan.h:2356
VPBasicBlock * getPreheaderVPBB()
Returns the pre-header VPBasicBlock of the loop region.
Definition: VPlan.h:2380
~VPRegionBlock() override
Definition: VPlan.h:2342
static bool classof(const VPBlockBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:2351
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:1744
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate replicas of the desired Ingredient.
~VPReplicateRecipe() override=default
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:1781
bool usesScalars(const VPValue *Op) const override
Returns true if the recipe uses scalars of operand Op.
Definition: VPlan.h:1788
bool isUniform() const
Definition: VPlan.h:1776
bool isPredicated() const
Definition: VPlan.h:1778
VPReplicateRecipe(Instruction *I, iterator_range< IterT > Operands, bool IsUniform, VPValue *Mask=nullptr)
Definition: VPlan.h:1753
VPValue * getMask()
Return the mask of a predicated VPReplicateRecipe.
Definition: VPlan.h:1800
bool shouldPack() const
Returns true if the recipe is used by a widened recipe via an intervening VPPredInstPHIRecipe.
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition: VPlan.h:2157
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:2182
VPValue * getStepValue() const
Definition: VPlan.h:2179
VPScalarIVStepsRecipe(const InductionDescriptor &IndDesc, VPValue *IV, VPValue *Step)
Definition: VPlan.h:2161
~VPScalarIVStepsRecipe() override=default
void execute(VPTransformState &State) override
Generate the scalarized versions of the phi node as needed by their users.
This class can be used to assign consecutive numbers to all VPValues in a VPlan and allows querying t...
Definition: VPlanValue.h:438
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:204
operand_range operands()
Definition: VPlanValue.h:279
void setOperand(unsigned I, VPValue *New)
Definition: VPlanValue.h:259
unsigned getNumOperands() const
Definition: VPlanValue.h:253
operand_iterator op_begin()
Definition: VPlanValue.h:275
VPValue * getOperand(unsigned N) const
Definition: VPlanValue.h:254
VPUserID
Subclass identifier (for isa/dyn_cast).
Definition: VPlanValue.h:207
void addOperand(VPValue *Operand)
Definition: VPlanValue.h:248
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition: VPlan.cpp:116
friend class VPInstruction
Definition: VPlanValue.h:47
void setUnderlyingValue(Value *Val)
Definition: VPlanValue.h:77
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
Definition: VPlanValue.h:180
bool isLiveIn() const
Returns true if this VPValue is a live-in, i.e. defined outside the VPlan.
Definition: VPlanValue.h:175
user_range users()
Definition: VPlanValue.h:147
bool isDefinedOutsideVectorRegions() const
Returns true if the VPValue is defined outside any vector regions, i.e.
Definition: VPlanValue.h:194
A recipe for widening Call instructions.
Definition: VPlan.h:1162
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Produce a widened version of the call instruction.
VPWidenCallRecipe(CallInst &I, iterator_range< IterT > CallArguments, Intrinsic::ID VectorIntrinsicID, Function *Variant=nullptr)
Definition: VPlan.h:1174
~VPWidenCallRecipe() override=default
A Recipe for widening the canonical induction variable of the vector loop.
Definition: VPlan.h:2083
void execute(VPTransformState &State) override
Generate a canonical vector induction variable of the vector loop, with start = {<Part*VF,...
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
~VPWidenCanonicalIVRecipe() override=default
VPWidenCanonicalIVRecipe(VPCanonicalIVPHIRecipe *CanonicalIV)
Definition: VPlan.h:2085
const Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:2105
VPWidenCastRecipe is a recipe to create vector cast instructions.
Definition: VPlan.h:1124
Instruction::CastOps getOpcode() const
Definition: VPlan.h:1155
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Type * getResultType() const
Returns the result type of the cast.
Definition: VPlan.h:1158
void execute(VPTransformState &State) override
Produce widened copies of the cast.
VPWidenCastRecipe(Instruction::CastOps Opcode, VPValue *Op, Type *ResultTy, CastInst *UI=nullptr)
Definition: VPlan.h:1132
~VPWidenCastRecipe() override=default
A recipe for handling GEP instructions.
Definition: VPlan.h:1223
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate the gep nodes.
~VPWidenGEPRecipe() override=default
VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range< IterT > Operands)
Definition: VPlan.h:1240
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
Definition: VPlan.h:1338
VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step, const InductionDescriptor &IndDesc, TruncInst *Trunc)
Definition: VPlan.h:1351
const TruncInst * getTruncInst() const
Definition: VPlan.h:1394
VPRecipeBase & getBackedgeRecipe() override
Returns the backedge value as a recipe.
Definition: VPlan.h:1380
~VPWidenIntOrFpInductionRecipe() override=default
TruncInst * getTruncInst()
Returns the first defined value as TruncInst, if it is one or nullptr otherwise.
Definition: VPlan.h:1393
void execute(VPTransformState &State) override
Generate the vectorized and scalarized versions of the phi node as needed by their users.
VPValue * getStepValue()
Returns the step value of the induction.
Definition: VPlan.h:1388
const Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:1406
VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step, const InductionDescriptor &IndDesc)
Definition: VPlan.h:1344
const VPValue * getStepValue() const
Definition: VPlan.h:1389
VPValue * getBackedgeValue() override
Returns the incoming value from the loop backedge.
Definition: VPlan.h:1373
bool isCanonical() const
Returns true if the induction is canonical, i.e.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
const InductionDescriptor & getInductionDescriptor() const
Returns the induction descriptor for the recipe.
Definition: VPlan.h:1399
A Recipe for widening load/store operations.
Definition: VPlan.h:1887
VPValue * getMask() const
Return the mask used by this recipe.
Definition: VPlan.h:1934
VPValue * getAddr() const
Return the address accessed by this recipe.
Definition: VPlan.h:1928
Instruction & getIngredient() const
Definition: VPlan.h:1976
VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr, VPValue *StoredValue, VPValue *Mask, bool Consecutive, bool Reverse)
Definition: VPlan.h:1916
void execute(VPTransformState &State) override
Generate the wide load/store.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask, bool Consecutive, bool Reverse)
Definition: VPlan.h:1907
VPValue * getStoredValue() const
Return the address accessed by this recipe.
Definition: VPlan.h:1943
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:1965
bool isStore() const
Returns true if this recipe is a store.
Definition: VPlan.h:1940
A recipe for handling header phis that are widened in the vector loop.
Definition: VPlan.h:1452
void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock)
Adds a pair (IncomingV, IncomingBlock) to the phi.
Definition: VPlan.h:1478
VPValue * getIncomingValue(unsigned I)
Returns the I th incoming VPValue.
Definition: VPlan.h:1487
VPWidenPHIRecipe(PHINode *Phi, VPValue *Start=nullptr)
Create a new VPWidenPHIRecipe for Phi with start value Start.
Definition: VPlan.h:1458
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
~VPWidenPHIRecipe() override=default
VPBasicBlock * getIncomingBlock(unsigned I)
Returns the I th incoming VPBasicBlock.
Definition: VPlan.h:1484
void execute(VPTransformState &State) override
Generate the phi/select nodes.
bool onlyScalarsGenerated(ElementCount VF)
Returns true if only scalar values will be generated.
const InductionDescriptor & getInductionDescriptor() const
Returns the induction descriptor for the recipe.
Definition: VPlan.h:1440
~VPWidenPointerInductionRecipe() override=default
void execute(VPTransformState &State) override
Generate vector values for the pointer induction.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPWidenPointerInductionRecipe(PHINode *Phi, VPValue *Start, VPValue *Step, const InductionDescriptor &IndDesc, bool IsScalarAfterVectorization)
Create a new VPWidenPointerInductionRecipe for Phi with start value Start.
Definition: VPlan.h:1419
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:1102
void execute(VPTransformState &State) override
Produce widened copies of all Ingredients.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
~VPWidenRecipe() override=default
VPWidenRecipe(Instruction &I, iterator_range< IterT > Operands)
Definition: VPlan.h:1106
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:2672
VPlanPrinter(raw_ostream &O, const VPlan &P)
Definition: VPlan.h:2713
LLVM_DUMP_METHOD void dump()
Definition: VPlan.cpp:890
Class that maps (parts of) an existing VPlan to trees of combined VPInstructions.
Definition: VPlan.h:2866
VPInstruction * buildGraph(ArrayRef< VPValue * > Operands)
Tries to build an SLP tree rooted at Operands and returns a VPInstruction combining Operands,...
Definition: VPlanSLP.cpp:359
bool isCompletelySLP() const
Return true if all visited instruction can be combined.
Definition: VPlan.h:2956
~VPlanSlp()=default
VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB)
Definition: VPlan.h:2944
unsigned getWidestBundleBits() const
Return the width of the widest combined bundle in bits.
Definition: VPlan.h:2953
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2413
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
Definition: VPlan.cpp:824
std::string getName() const
Return a string with the name of the plan and the applicable VFs and UFs.
Definition: VPlan.cpp:800
VPBasicBlock * getEntry()
Definition: VPlan.h:2505
void addVPValue(Value *V, VPValue *VPV)
Definition: VPlan.h:2553
VPValue & getVectorTripCount()
The vector trip count.
Definition: VPlan.h:2522
void setName(const Twine &newName)
Definition: VPlan.h:2551
VPValue * getTripCount() const
The trip count of the original loop.
Definition: VPlan.h:2509
void removeVPValueFor(Value *V)
Definition: VPlan.h:2585
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition: VPlan.h:2515
void removeLiveOut(PHINode *PN)
Definition: VPlan.h:2636
void addLiveOut(PHINode *PN, VPValue *V)
Definition: VPlan.cpp:833
const VPBasicBlock * getEntry() const
Definition: VPlan.h:2506
void prepareToExecute(Value *TripCount, Value *VectorTripCount, Value *CanonicalIVStartValue, VPTransformState &State, bool IsEpilogueVectorization)
Prepare the plan for execution, setting up the required live-in values.
Definition: VPlan.cpp:630
VPlan(VPBasicBlock *Preheader, VPValue *TC, VPBasicBlock *Entry)
Construct a VPlan with original preheader Preheader, trip count TC and Entry to the plan.
Definition: VPlan.h:2472
VPBasicBlock * getPreheader()
Definition: VPlan.h:2658
VPValue * getVPValueOrAddLiveIn(Value *V)
Gets the VPValue for V or adds a new live-in (if none exists yet) for V.
Definition: VPlan.h:2574
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:2613
const VPRegionBlock * getVectorLoopRegion() const
Definition: VPlan.h:2616
static VPlanPtr createInitialVPlan(const SCEV *TripCount, ScalarEvolution &PSE)
Create an initial VPlan with preheader and entry blocks.
Definition: VPlan.cpp:612
bool hasVF(ElementCount VF)
Definition: VPlan.h:2536
void addSCEVExpansion(const SCEV *S, VPValue *V)
Definition: VPlan.h:2652
bool hasUF(unsigned UF) const
Definition: VPlan.h:2540
void setVF(ElementCount VF)
Definition: VPlan.h:2530
VPValue * getVPValue(Value *V, bool OverrideAllowed=false)
Returns the VPValue for V.
Definition: VPlan.h:2563
VPlan(VPBasicBlock *Preheader, VPBasicBlock *Entry)
Construct a VPlan with original preheader Preheader and Entry to the plan.
Definition: VPlan.h:2481
void disableValue2VPValue()
Mark the plan to indicate that using Value2VPValue is not safe any longer, because it may be stale.
Definition: VPlan.h:2526
const VPBasicBlock * getPreheader() const
Definition: VPlan.h:2659
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
Definition: VPlan.cpp:830
bool hasScalarVFOnly() const
Definition: VPlan.h:2538
iterator_range< mapped_iterator< Use *, std::function< VPValue *(Value *)> > > mapToVPValues(User::op_range Operands)
Returns a range mapping the values the range Operands to their corresponding VPValues.
Definition: VPlan.h:2605
void execute(VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:676
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
Definition: VPlan.h:2621
const MapVector< PHINode *, VPLiveOut * > & getLiveOuts() const
Definition: VPlan.h:2641
VPActiveLaneMaskPHIRecipe * getActiveLaneMaskPhi()
Find and return the VPActiveLaneMaskPHIRecipe from the header - there be only one at most.
Definition: VPlan.cpp:621
void print(raw_ostream &O) const
Print this VPlan to O.
Definition: VPlan.cpp:757
void addVF(ElementCount VF)
Definition: VPlan.h:2528
VPValue * getSCEVExpansion(const SCEV *S) const
Definition: VPlan.h:2645
void setUF(unsigned UF)
Definition: VPlan.h:2542
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:166
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition: TypeSize.h:163
Iterator for intrusive lists based on ilist_node.
An ilist node that can access its parent list.
Definition: ilist_node.h:257
base_list_type::const_reverse_iterator const_reverse_iterator
Definition: ilist.h:125
void pop_back()
Definition: ilist.h:255
base_list_type::reverse_iterator reverse_iterator
Definition: ilist.h:123
base_list_type::const_iterator const_iterator
Definition: ilist.h:122
base_list_type::iterator iterator
Definition: ilist.h:121
iterator insert(iterator where, pointer New)
Definition: ilist.h:165
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This file defines classes to implement an intrusive doubly linked list class (i.e.
This file defines the ilist_node class template, which is a convenient base class for creating classe...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
Definition: VPlan.cpp:1141
bool isUniformAfterVectorization(VPValue *VPV)
Returns true if VPV is uniform after vectorization.
Definition: VPlan.h:2973
bool onlyFirstLaneUsed(VPValue *Def)
Returns true if only the first lane of Def is used.
Definition: VPlan.cpp:1136
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1839
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
const SCEV * createTripCountSCEV(Type *IdxTy, PredicatedScalarEvolution &PSE, Loop *OrigLoop)
testing::Matcher< const detail::ErrorHolder & > Failed()
Definition: Error.h:198
Value * getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF)
Return the runtime value for VF.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto map_range(ContainerTy &&C, FuncTy F)
Definition: STLExtras.h:461
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:292
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:132
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:664
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
Value * createStepForVF(IRBuilderBase &B, Type *Ty, ElementCount VF, int64_t Step)
Return a value for Step multiplied by VF.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1976
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:491
#define N
A range of powers-of-2 vectorization factors with fixed start and adjustable end.
Definition: VPlan.h:85
iterator end()
Definition: VPlan.h:126
const ElementCount Start
Definition: VPlan.h:87
ElementCount End
Definition: VPlan.h:90
iterator begin()
Definition: VPlan.h:125
bool isEmpty() const
Definition: VPlan.h:92
VFRange(const ElementCount &Start, const ElementCount &End)
Definition: VPlan.h:96
A recipe for handling first-order recurrence phis.
Definition: VPlan.h:1493
void execute(VPTransformState &State) override
Generate the phi nodes.
VPFirstOrderRecurrencePHIRecipe(PHINode *Phi, VPValue &Start)
Definition: VPlan.h:1494
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1499
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPIteration represents a single point in the iteration space of the output (vectorized and/or unrolle...
Definition: VPlan.h:217
VPIteration(unsigned Part, const VPLane &Lane)
Definition: VPlan.h:227
unsigned Part
in [0..UF)
Definition: VPlan.h:219
VPLane Lane
Definition: VPlan.h:221
VPIteration(unsigned Part, unsigned Lane, VPLane::Kind Kind=VPLane::Kind::First)
Definition: VPlan.h:223
bool isFirstIteration() const
Definition: VPlan.h:229
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:358
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:364
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:372
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:360
BasicBlock * ExitBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:368
BasicBlock * getPreheaderBBFor(VPRecipeBase *R)
Returns the BasicBlock* mapped to the pre-header of the loop region containing R.
Definition: VPlan.cpp:236
SmallVector< Value *, 2 > PerPartValuesTy
A type for vectorized values in the new loop.
Definition: VPlan.h:254
DenseMap< VPValue *, ScalarsPerPartValuesTy > PerPartScalars
Definition: VPlan.h:259
DenseMap< VPValue *, PerPartValuesTy > PerPartOutput
Definition: VPlan.h:256
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:234
VPValue2ValueTy VPValue2Value
Definition: VPlan.h:390
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:382
VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilderBase &Builder, InnerLoopVectorizer *ILV, VPlan *Plan)
Definition: VPlan.h:235
DenseMap< const SCEV *, Value * > ExpandedSCEVs
Map SCEVs to their expanded values.
Definition: VPlan.h:413
void addMetadata(Instruction *To, Instruction *From)
Add metadata from one instruction to another.
Definition: VPlan.cpp:249
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
struct llvm::VPTransformState::DataState Data
void setDebugLocFromInst(const Value *V)
Set the debug location in the builder using the debug location in V.
Definition: VPlan.cpp:269
void reset(VPValue *Def, Value *V, unsigned Part)
Reset an existing vector value for Def and a given Part.
Definition: VPlan.h:301
struct llvm::VPTransformState::CFGState CFG
void reset(VPValue *Def, Value *V, const VPIteration &Instance)
Reset an existing scalar value for Def and a given Instance.
Definition: VPlan.h:323
LoopVersioning * LVer
LoopVersioning.
Definition: VPlan.h:409
void addNewMetadata(Instruction *To, const Instruction *Orig)
Add additional metadata to To that was not present on Orig.
Definition: VPlan.cpp:241
bool hasAnyVectorValue(VPValue *Def) const
Definition: VPlan.h:278
void set(VPValue *Def, Value *V, const VPIteration &Instance)
Set the generated scalar V for Def and the given Instance.
Definition: VPlan.h:309
std::optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:248
IRBuilderBase & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:388
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:385
bool hasScalarValue(VPValue *Def, VPIteration Instance)
Definition: VPlan.h:282
VPlan * Plan
Pointer to the VPlan code is generated for.
Definition: VPlan.h:399
InnerLoopVectorizer * ILV
Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
Definition: VPlan.h:396
Value * CanonicalIV
Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
Definition: VPlan.h:393
bool hasVectorValue(VPValue *Def, unsigned Part)
Definition: VPlan.h:272
ElementCount VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:242
Loop * CurrentVectorLoop
The loop object for the current parent region, or nullptr.
Definition: VPlan.h:402
void set(VPValue *Def, Value *V, unsigned Part)
Set the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:293
A recipe for widening select instructions.
Definition: VPlan.h:1195
bool isInvariantCond() const
Definition: VPlan.h:1217
VPWidenSelectRecipe(SelectInst &I, iterator_range< IterT > Operands)
Definition: VPlan.h:1197
VPValue * getCond() const
Definition: VPlan.h:1213
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Produce a widened version of the select instruction.
~VPWidenSelectRecipe() override=default
VPlanIngredient(const Value *V)
Definition: VPlan.h:2722
const Value * V
Definition: VPlan.h:2720
void print(raw_ostream &O) const
Definition: VPlan.cpp:1001