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