| //===- VPlan.h - Represent A Vectorizer Plan --------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| /// \file |
| /// This file contains the declarations of the Vectorization Plan base classes: |
| /// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual |
| /// VPBlockBase, together implementing a Hierarchical CFG; |
| /// 2. Specializations of GraphTraits that allow VPBlockBase graphs to be |
| /// treated as proper graphs for generic algorithms; |
| /// 3. Pure virtual VPRecipeBase serving as the base class for recipes contained |
| /// within VPBasicBlocks; |
| /// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned |
| /// instruction; |
| /// 5. The VPlan class holding a candidate for vectorization; |
| /// 6. The VPlanPrinter class providing a way to print a plan in dot format; |
| /// These are documented in docs/VectorizationPlan.rst. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H |
| #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H |
| |
| #include "VPlanLoopInfo.h" |
| #include "VPlanValue.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/DepthFirstIterator.h" |
| #include "llvm/ADT/GraphTraits.h" |
| #include "llvm/ADT/Optional.h" |
| #include "llvm/ADT/SmallBitVector.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/Twine.h" |
| #include "llvm/ADT/ilist.h" |
| #include "llvm/ADT/ilist_node.h" |
| #include "llvm/Analysis/VectorUtils.h" |
| #include "llvm/IR/IRBuilder.h" |
| #include "llvm/Support/InstructionCost.h" |
| #include <algorithm> |
| #include <cassert> |
| #include <cstddef> |
| #include <map> |
| #include <string> |
| |
| namespace llvm { |
| |
| class BasicBlock; |
| class DominatorTree; |
| class InnerLoopVectorizer; |
| class LoopInfo; |
| class raw_ostream; |
| class RecurrenceDescriptor; |
| class Value; |
| class VPBasicBlock; |
| class VPRegionBlock; |
| class VPlan; |
| class VPReplicateRecipe; |
| class VPlanSlp; |
| |
| /// Returns a calculation for the total number of elements for a given \p VF. |
| /// For fixed width vectors this value is a constant, whereas for scalable |
| /// vectors it is an expression determined at runtime. |
| Value *getRuntimeVF(IRBuilder<> &B, Type *Ty, ElementCount VF); |
| |
| /// A range of powers-of-2 vectorization factors with fixed start and |
| /// adjustable end. The range includes start and excludes end, e.g.,: |
| /// [1, 9) = {1, 2, 4, 8} |
| struct VFRange { |
| // A power of 2. |
| const ElementCount Start; |
| |
| // Need not be a power of 2. If End <= Start range is empty. |
| ElementCount End; |
| |
| bool isEmpty() const { |
| return End.getKnownMinValue() <= Start.getKnownMinValue(); |
| } |
| |
| VFRange(const ElementCount &Start, const ElementCount &End) |
| : Start(Start), End(End) { |
| assert(Start.isScalable() == End.isScalable() && |
| "Both Start and End should have the same scalable flag"); |
| assert(isPowerOf2_32(Start.getKnownMinValue()) && |
| "Expected Start to be a power of 2"); |
| } |
| }; |
| |
| using VPlanPtr = std::unique_ptr<VPlan>; |
| |
| /// In what follows, the term "input IR" refers to code that is fed into the |
| /// vectorizer whereas the term "output IR" refers to code that is generated by |
| /// the vectorizer. |
| |
| /// VPLane provides a way to access lanes in both fixed width and scalable |
| /// vectors, where for the latter the lane index sometimes needs calculating |
| /// as a runtime expression. |
| class VPLane { |
| public: |
| /// Kind describes how to interpret Lane. |
| enum class Kind : uint8_t { |
| /// For First, Lane is the index into the first N elements of a |
| /// fixed-vector <N x <ElTy>> or a scalable vector <vscale x N x <ElTy>>. |
| First, |
| /// For ScalableLast, Lane is the offset from the start of the last |
| /// N-element subvector in a scalable vector <vscale x N x <ElTy>>. For |
| /// example, a Lane of 0 corresponds to lane `(vscale - 1) * N`, a Lane of |
| /// 1 corresponds to `((vscale - 1) * N) + 1`, etc. |
| ScalableLast |
| }; |
| |
| private: |
| /// in [0..VF) |
| unsigned Lane; |
| |
| /// Indicates how the Lane should be interpreted, as described above. |
| Kind LaneKind; |
| |
| public: |
| VPLane(unsigned Lane, Kind LaneKind) : Lane(Lane), LaneKind(LaneKind) {} |
| |
| static VPLane getFirstLane() { return VPLane(0, VPLane::Kind::First); } |
| |
| static VPLane getLastLaneForVF(const ElementCount &VF) { |
| unsigned LaneOffset = VF.getKnownMinValue() - 1; |
| Kind LaneKind; |
| if (VF.isScalable()) |
| // In this case 'LaneOffset' refers to the offset from the start of the |
| // last subvector with VF.getKnownMinValue() elements. |
| LaneKind = VPLane::Kind::ScalableLast; |
| else |
| LaneKind = VPLane::Kind::First; |
| return VPLane(LaneOffset, LaneKind); |
| } |
| |
| /// Returns a compile-time known value for the lane index and asserts if the |
| /// lane can only be calculated at runtime. |
| unsigned getKnownLane() const { |
| assert(LaneKind == Kind::First); |
| return Lane; |
| } |
| |
| /// Returns an expression describing the lane index that can be used at |
| /// runtime. |
| Value *getAsRuntimeExpr(IRBuilder<> &Builder, const ElementCount &VF) const; |
| |
| /// Returns the Kind of lane offset. |
| Kind getKind() const { return LaneKind; } |
| |
| /// Returns true if this is the first lane of the whole vector. |
| bool isFirstLane() const { return Lane == 0 && LaneKind == Kind::First; } |
| |
| /// Maps the lane to a cache index based on \p VF. |
| unsigned mapToCacheIndex(const ElementCount &VF) const { |
| switch (LaneKind) { |
| case VPLane::Kind::ScalableLast: |
| assert(VF.isScalable() && Lane < VF.getKnownMinValue()); |
| return VF.getKnownMinValue() + Lane; |
| default: |
| assert(Lane < VF.getKnownMinValue()); |
| return Lane; |
| } |
| } |
| |
| /// Returns the maxmimum number of lanes that we are able to consider |
| /// caching for \p VF. |
| static unsigned getNumCachedLanes(const ElementCount &VF) { |
| return VF.getKnownMinValue() * (VF.isScalable() ? 2 : 1); |
| } |
| }; |
| |
| /// VPIteration represents a single point in the iteration space of the output |
| /// (vectorized and/or unrolled) IR loop. |
| struct VPIteration { |
| /// in [0..UF) |
| unsigned Part; |
| |
| VPLane Lane; |
| |
| VPIteration(unsigned Part, unsigned Lane, |
| VPLane::Kind Kind = VPLane::Kind::First) |
| : Part(Part), Lane(Lane, Kind) {} |
| |
| VPIteration(unsigned Part, const VPLane &Lane) : Part(Part), Lane(Lane) {} |
| |
| bool isFirstIteration() const { return Part == 0 && Lane.isFirstLane(); } |
| }; |
| |
| /// VPTransformState holds information passed down when "executing" a VPlan, |
| /// needed for generating the output IR. |
| struct VPTransformState { |
| VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, |
| DominatorTree *DT, IRBuilder<> &Builder, |
| InnerLoopVectorizer *ILV, VPlan *Plan) |
| : VF(VF), UF(UF), Instance(), LI(LI), DT(DT), Builder(Builder), ILV(ILV), |
| Plan(Plan) {} |
| |
| /// The chosen Vectorization and Unroll Factors of the loop being vectorized. |
| ElementCount VF; |
| unsigned UF; |
| |
| /// Hold the indices to generate specific scalar instructions. Null indicates |
| /// that all instances are to be generated, using either scalar or vector |
| /// instructions. |
| Optional<VPIteration> Instance; |
| |
| struct DataState { |
| /// A type for vectorized values in the new loop. Each value from the |
| /// original loop, when vectorized, is represented by UF vector values in |
| /// the new unrolled loop, where UF is the unroll factor. |
| typedef SmallVector<Value *, 2> PerPartValuesTy; |
| |
| DenseMap<VPValue *, PerPartValuesTy> PerPartOutput; |
| |
| using ScalarsPerPartValuesTy = SmallVector<SmallVector<Value *, 4>, 2>; |
| DenseMap<VPValue *, ScalarsPerPartValuesTy> PerPartScalars; |
| } Data; |
| |
| /// Get the generated Value for a given VPValue and a given Part. Note that |
| /// as some Defs are still created by ILV and managed in its ValueMap, this |
| /// method will delegate the call to ILV in such cases in order to provide |
| /// callers a consistent API. |
| /// \see set. |
| Value *get(VPValue *Def, unsigned Part); |
| |
| /// Get the generated Value for a given VPValue and given Part and Lane. |
| Value *get(VPValue *Def, const VPIteration &Instance); |
| |
| bool hasVectorValue(VPValue *Def, unsigned Part) { |
| auto I = Data.PerPartOutput.find(Def); |
| return I != Data.PerPartOutput.end() && Part < I->second.size() && |
| I->second[Part]; |
| } |
| |
| bool hasAnyVectorValue(VPValue *Def) const { |
| return Data.PerPartOutput.find(Def) != Data.PerPartOutput.end(); |
| } |
| |
| bool hasScalarValue(VPValue *Def, VPIteration Instance) { |
| auto I = Data.PerPartScalars.find(Def); |
| if (I == Data.PerPartScalars.end()) |
| return false; |
| unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF); |
| return Instance.Part < I->second.size() && |
| CacheIdx < I->second[Instance.Part].size() && |
| I->second[Instance.Part][CacheIdx]; |
| } |
| |
| /// Set the generated Value for a given VPValue and a given Part. |
| void set(VPValue *Def, Value *V, unsigned Part) { |
| if (!Data.PerPartOutput.count(Def)) { |
| DataState::PerPartValuesTy Entry(UF); |
| Data.PerPartOutput[Def] = Entry; |
| } |
| Data.PerPartOutput[Def][Part] = V; |
| } |
| /// Reset an existing vector value for \p Def and a given \p Part. |
| void reset(VPValue *Def, Value *V, unsigned Part) { |
| auto Iter = Data.PerPartOutput.find(Def); |
| assert(Iter != Data.PerPartOutput.end() && |
| "need to overwrite existing value"); |
| Iter->second[Part] = V; |
| } |
| |
| /// Set the generated scalar \p V for \p Def and the given \p Instance. |
| void set(VPValue *Def, Value *V, const VPIteration &Instance) { |
| auto Iter = Data.PerPartScalars.insert({Def, {}}); |
| auto &PerPartVec = Iter.first->second; |
| while (PerPartVec.size() <= Instance.Part) |
| PerPartVec.emplace_back(); |
| auto &Scalars = PerPartVec[Instance.Part]; |
| unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF); |
| while (Scalars.size() <= CacheIdx) |
| Scalars.push_back(nullptr); |
| assert(!Scalars[CacheIdx] && "should overwrite existing value"); |
| Scalars[CacheIdx] = V; |
| } |
| |
| /// Reset an existing scalar value for \p Def and a given \p Instance. |
| void reset(VPValue *Def, Value *V, const VPIteration &Instance) { |
| auto Iter = Data.PerPartScalars.find(Def); |
| assert(Iter != Data.PerPartScalars.end() && |
| "need to overwrite existing value"); |
| assert(Instance.Part < Iter->second.size() && |
| "need to overwrite existing value"); |
| unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF); |
| assert(CacheIdx < Iter->second[Instance.Part].size() && |
| "need to overwrite existing value"); |
| Iter->second[Instance.Part][CacheIdx] = V; |
| } |
| |
| /// Hold state information used when constructing the CFG of the output IR, |
| /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks. |
| struct CFGState { |
| /// The previous VPBasicBlock visited. Initially set to null. |
| VPBasicBlock *PrevVPBB = nullptr; |
| |
| /// The previous IR BasicBlock created or used. Initially set to the new |
| /// header BasicBlock. |
| BasicBlock *PrevBB = nullptr; |
| |
| /// The last IR BasicBlock in the output IR. Set to the new latch |
| /// BasicBlock, used for placing the newly created BasicBlocks. |
| BasicBlock *LastBB = nullptr; |
| |
| /// The IR BasicBlock that is the preheader of the vector loop in the output |
| /// IR. |
| /// FIXME: The vector preheader should also be modeled in VPlan, so any code |
| /// that needs to be added to the preheader gets directly generated by |
| /// VPlan. There should be no need to manage a pointer to the IR BasicBlock. |
| BasicBlock *VectorPreHeader = nullptr; |
| |
| /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case |
| /// of replication, maps the BasicBlock of the last replica created. |
| SmallDenseMap<VPBasicBlock *, BasicBlock *> VPBB2IRBB; |
| |
| /// Vector of VPBasicBlocks whose terminator instruction needs to be fixed |
| /// up at the end of vector code generation. |
| SmallVector<VPBasicBlock *, 8> VPBBsToFix; |
| |
| CFGState() = default; |
| } CFG; |
| |
| /// Hold a pointer to LoopInfo to register new basic blocks in the loop. |
| LoopInfo *LI; |
| |
| /// Hold a pointer to Dominator Tree to register new basic blocks in the loop. |
| DominatorTree *DT; |
| |
| /// Hold a reference to the IRBuilder used to generate output IR code. |
| IRBuilder<> &Builder; |
| |
| VPValue2ValueTy VPValue2Value; |
| |
| /// Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF). |
| Value *CanonicalIV = nullptr; |
| |
| /// Hold the trip count of the scalar loop. |
| Value *TripCount = nullptr; |
| |
| /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods. |
| InnerLoopVectorizer *ILV; |
| |
| /// Pointer to the VPlan code is generated for. |
| VPlan *Plan; |
| |
| /// Holds recipes that may generate a poison value that is used after |
| /// vectorization, even when their operands are not poison. |
| SmallPtrSet<VPRecipeBase *, 16> MayGeneratePoisonRecipes; |
| }; |
| |
| /// VPUsers instance used by VPBlockBase to manage CondBit and the block |
| /// predicate. Currently VPBlockUsers are used in VPBlockBase for historical |
| /// reasons, but in the future the only VPUsers should either be recipes or |
| /// live-outs.VPBlockBase uses. |
| struct VPBlockUser : public VPUser { |
| VPBlockUser() : VPUser({}, VPUserID::Block) {} |
| |
| VPValue *getSingleOperandOrNull() { |
| if (getNumOperands() == 1) |
| return getOperand(0); |
| |
| return nullptr; |
| } |
| const VPValue *getSingleOperandOrNull() const { |
| if (getNumOperands() == 1) |
| return getOperand(0); |
| |
| return nullptr; |
| } |
| |
| void resetSingleOpUser(VPValue *NewVal) { |
| assert(getNumOperands() <= 1 && "Didn't expect more than one operand!"); |
| if (!NewVal) { |
| if (getNumOperands() == 1) |
| removeLastOperand(); |
| return; |
| } |
| |
| if (getNumOperands() == 1) |
| setOperand(0, NewVal); |
| else |
| addOperand(NewVal); |
| } |
| }; |
| |
| /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph. |
| /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock. |
| class VPBlockBase { |
| friend class VPBlockUtils; |
| |
| const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast). |
| |
| /// An optional name for the block. |
| std::string Name; |
| |
| /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if |
| /// it is a topmost VPBlockBase. |
| VPRegionBlock *Parent = nullptr; |
| |
| /// List of predecessor blocks. |
| SmallVector<VPBlockBase *, 1> Predecessors; |
| |
| /// List of successor blocks. |
| SmallVector<VPBlockBase *, 1> Successors; |
| |
| /// Successor selector managed by a VPUser. For blocks with zero or one |
| /// successors, there is no operand. Otherwise there is exactly one operand |
| /// which is the branch condition. |
| VPBlockUser CondBitUser; |
| |
| /// If the block is predicated, its predicate is stored as an operand of this |
| /// VPUser to maintain the def-use relations. Otherwise there is no operand |
| /// here. |
| VPBlockUser PredicateUser; |
| |
| /// VPlan containing the block. Can only be set on the entry block of the |
| /// plan. |
| VPlan *Plan = nullptr; |
| |
| /// Add \p Successor as the last successor to this block. |
| void appendSuccessor(VPBlockBase *Successor) { |
| assert(Successor && "Cannot add nullptr successor!"); |
| Successors.push_back(Successor); |
| } |
| |
| /// Add \p Predecessor as the last predecessor to this block. |
| void appendPredecessor(VPBlockBase *Predecessor) { |
| assert(Predecessor && "Cannot add nullptr predecessor!"); |
| Predecessors.push_back(Predecessor); |
| } |
| |
| /// Remove \p Predecessor from the predecessors of this block. |
| void removePredecessor(VPBlockBase *Predecessor) { |
| auto Pos = find(Predecessors, Predecessor); |
| assert(Pos && "Predecessor does not exist"); |
| Predecessors.erase(Pos); |
| } |
| |
| /// Remove \p Successor from the successors of this block. |
| void removeSuccessor(VPBlockBase *Successor) { |
| auto Pos = find(Successors, Successor); |
| assert(Pos && "Successor does not exist"); |
| Successors.erase(Pos); |
| } |
| |
| protected: |
| VPBlockBase(const unsigned char SC, const std::string &N) |
| : SubclassID(SC), Name(N) {} |
| |
| public: |
| /// An enumeration for keeping track of the concrete subclass of VPBlockBase |
| /// that are actually instantiated. Values of this enumeration are kept in the |
| /// SubclassID field of the VPBlockBase objects. They are used for concrete |
| /// type identification. |
| using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC }; |
| |
| using VPBlocksTy = SmallVectorImpl<VPBlockBase *>; |
| |
| virtual ~VPBlockBase() = default; |
| |
| const std::string &getName() const { return Name; } |
| |
| void setName(const Twine &newName) { Name = newName.str(); } |
| |
| /// \return an ID for the concrete type of this object. |
| /// This is used to implement the classof checks. This should not be used |
| /// for any other purpose, as the values may change as LLVM evolves. |
| unsigned getVPBlockID() const { return SubclassID; } |
| |
| VPRegionBlock *getParent() { return Parent; } |
| const VPRegionBlock *getParent() const { return Parent; } |
| |
| /// \return A pointer to the plan containing the current block. |
| VPlan *getPlan(); |
| const VPlan *getPlan() const; |
| |
| /// Sets the pointer of the plan containing the block. The block must be the |
| /// entry block into the VPlan. |
| void setPlan(VPlan *ParentPlan); |
| |
| void setParent(VPRegionBlock *P) { Parent = P; } |
| |
| /// \return the VPBasicBlock that is the entry of this VPBlockBase, |
| /// recursively, if the latter is a VPRegionBlock. Otherwise, if this |
| /// VPBlockBase is a VPBasicBlock, it is returned. |
| const VPBasicBlock *getEntryBasicBlock() const; |
| VPBasicBlock *getEntryBasicBlock(); |
| |
| /// \return the VPBasicBlock that is the exit of this VPBlockBase, |
| /// recursively, if the latter is a VPRegionBlock. Otherwise, if this |
| /// VPBlockBase is a VPBasicBlock, it is returned. |
| const VPBasicBlock *getExitBasicBlock() const; |
| VPBasicBlock *getExitBasicBlock(); |
| |
| const VPBlocksTy &getSuccessors() const { return Successors; } |
| VPBlocksTy &getSuccessors() { return Successors; } |
| |
| const VPBlocksTy &getPredecessors() const { return Predecessors; } |
| VPBlocksTy &getPredecessors() { return Predecessors; } |
| |
| /// \return the successor of this VPBlockBase if it has a single successor. |
| /// Otherwise return a null pointer. |
| VPBlockBase *getSingleSuccessor() const { |
| return (Successors.size() == 1 ? *Successors.begin() : nullptr); |
| } |
| |
| /// \return the predecessor of this VPBlockBase if it has a single |
| /// predecessor. Otherwise return a null pointer. |
| VPBlockBase *getSinglePredecessor() const { |
| return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr); |
| } |
| |
| size_t getNumSuccessors() const { return Successors.size(); } |
| size_t getNumPredecessors() const { return Predecessors.size(); } |
| |
| /// An Enclosing Block of a block B is any block containing B, including B |
| /// itself. \return the closest enclosing block starting from "this", which |
| /// has successors. \return the root enclosing block if all enclosing blocks |
| /// have no successors. |
| VPBlockBase *getEnclosingBlockWithSuccessors(); |
| |
| /// \return the closest enclosing block starting from "this", which has |
| /// predecessors. \return the root enclosing block if all enclosing blocks |
| /// have no predecessors. |
| VPBlockBase *getEnclosingBlockWithPredecessors(); |
| |
| /// \return the successors either attached directly to this VPBlockBase or, if |
| /// this VPBlockBase is the exit block of a VPRegionBlock and has no |
| /// successors of its own, search recursively for the first enclosing |
| /// VPRegionBlock that has successors and return them. If no such |
| /// VPRegionBlock exists, return the (empty) successors of the topmost |
| /// VPBlockBase reached. |
| const VPBlocksTy &getHierarchicalSuccessors() { |
| return getEnclosingBlockWithSuccessors()->getSuccessors(); |
| } |
| |
| /// \return the hierarchical successor of this VPBlockBase if it has a single |
| /// hierarchical successor. Otherwise return a null pointer. |
| VPBlockBase *getSingleHierarchicalSuccessor() { |
| return getEnclosingBlockWithSuccessors()->getSingleSuccessor(); |
| } |
| |
| /// \return the predecessors either attached directly to this VPBlockBase or, |
| /// if this VPBlockBase is the entry block of a VPRegionBlock and has no |
| /// predecessors of its own, search recursively for the first enclosing |
| /// VPRegionBlock that has predecessors and return them. If no such |
| /// VPRegionBlock exists, return the (empty) predecessors of the topmost |
| /// VPBlockBase reached. |
| const VPBlocksTy &getHierarchicalPredecessors() { |
| return getEnclosingBlockWithPredecessors()->getPredecessors(); |
| } |
| |
| /// \return the hierarchical predecessor of this VPBlockBase if it has a |
| /// single hierarchical predecessor. Otherwise return a null pointer. |
| VPBlockBase *getSingleHierarchicalPredecessor() { |
| return getEnclosingBlockWithPredecessors()->getSinglePredecessor(); |
| } |
| |
| /// \return the condition bit selecting the successor. |
| VPValue *getCondBit(); |
| /// \return the condition bit selecting the successor. |
| const VPValue *getCondBit() const; |
| /// Set the condition bit selecting the successor. |
| void setCondBit(VPValue *CV); |
| |
| /// \return the block's predicate. |
| VPValue *getPredicate(); |
| /// \return the block's predicate. |
| const VPValue *getPredicate() const; |
| /// Set the block's predicate. |
| void setPredicate(VPValue *Pred); |
| |
| /// Set a given VPBlockBase \p Successor as the single successor of this |
| /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor. |
| /// This VPBlockBase must have no successors. |
| void setOneSuccessor(VPBlockBase *Successor) { |
| assert(Successors.empty() && "Setting one successor when others exist."); |
| appendSuccessor(Successor); |
| } |
| |
| /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two |
| /// successors of this VPBlockBase. \p Condition is set as the successor |
| /// selector. This VPBlockBase is not added as predecessor of \p IfTrue or \p |
| /// IfFalse. This VPBlockBase must have no successors. |
| void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse, |
| VPValue *Condition) { |
| assert(Successors.empty() && "Setting two successors when others exist."); |
| assert(Condition && "Setting two successors without condition!"); |
| setCondBit(Condition); |
| appendSuccessor(IfTrue); |
| appendSuccessor(IfFalse); |
| } |
| |
| /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase. |
| /// This VPBlockBase must have no predecessors. This VPBlockBase is not added |
| /// as successor of any VPBasicBlock in \p NewPreds. |
| void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) { |
| assert(Predecessors.empty() && "Block predecessors already set."); |
| for (auto *Pred : NewPreds) |
| appendPredecessor(Pred); |
| } |
| |
| /// Remove all the predecessor of this block. |
| void clearPredecessors() { Predecessors.clear(); } |
| |
| /// Remove all the successors of this block and set to null its condition bit |
| void clearSuccessors() { |
| Successors.clear(); |
| setCondBit(nullptr); |
| } |
| |
| /// The method which generates the output IR that correspond to this |
| /// VPBlockBase, thereby "executing" the VPlan. |
| virtual void execute(struct VPTransformState *State) = 0; |
| |
| /// Delete all blocks reachable from a given VPBlockBase, inclusive. |
| static void deleteCFG(VPBlockBase *Entry); |
| |
| /// Return true if it is legal to hoist instructions into this block. |
| bool isLegalToHoistInto() { |
| // There are currently no constraints that prevent an instruction to be |
| // hoisted into a VPBlockBase. |
| return true; |
| } |
| |
| /// Replace all operands of VPUsers in the block with \p NewValue and also |
| /// replaces all uses of VPValues defined in the block with NewValue. |
| virtual void dropAllReferences(VPValue *NewValue) = 0; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| void printAsOperand(raw_ostream &OS, bool PrintType) const { |
| OS << getName(); |
| } |
| |
| /// Print plain-text dump of this VPBlockBase to \p O, prefixing all lines |
| /// with \p Indent. \p SlotTracker is used to print unnamed VPValue's using |
| /// consequtive numbers. |
| /// |
| /// Note that the numbering is applied to the whole VPlan, so printing |
| /// individual blocks is consistent with the whole VPlan printing. |
| virtual void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const = 0; |
| |
| /// Print plain-text dump of this VPlan to \p O. |
| void print(raw_ostream &O) const { |
| VPSlotTracker SlotTracker(getPlan()); |
| print(O, "", SlotTracker); |
| } |
| |
| /// Print the successors of this block to \p O, prefixing all lines with \p |
| /// Indent. |
| void printSuccessors(raw_ostream &O, const Twine &Indent) const; |
| |
| /// Dump this VPBlockBase to dbgs(). |
| LLVM_DUMP_METHOD void dump() const { print(dbgs()); } |
| #endif |
| }; |
| |
| /// VPRecipeBase is a base class modeling a sequence of one or more output IR |
| /// instructions. VPRecipeBase owns the the VPValues it defines through VPDef |
| /// and is responsible for deleting its defined values. Single-value |
| /// VPRecipeBases that also inherit from VPValue must make sure to inherit from |
| /// VPRecipeBase before VPValue. |
| class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>, |
| public VPDef, |
| public VPUser { |
| friend VPBasicBlock; |
| friend class VPBlockUtils; |
| |
| /// Each VPRecipe belongs to a single VPBasicBlock. |
| VPBasicBlock *Parent = nullptr; |
| |
| public: |
| VPRecipeBase(const unsigned char SC, ArrayRef<VPValue *> Operands) |
| : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {} |
| |
| template <typename IterT> |
| VPRecipeBase(const unsigned char SC, iterator_range<IterT> Operands) |
| : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {} |
| virtual ~VPRecipeBase() = default; |
| |
| /// \return the VPBasicBlock which this VPRecipe belongs to. |
| VPBasicBlock *getParent() { return Parent; } |
| const VPBasicBlock *getParent() const { return Parent; } |
| |
| /// The method which generates the output IR instructions that correspond to |
| /// this VPRecipe, thereby "executing" the VPlan. |
| virtual void execute(struct VPTransformState &State) = 0; |
| |
| /// Insert an unlinked recipe into a basic block immediately before |
| /// the specified recipe. |
| void insertBefore(VPRecipeBase *InsertPos); |
| |
| /// Insert an unlinked Recipe into a basic block immediately after |
| /// the specified Recipe. |
| void insertAfter(VPRecipeBase *InsertPos); |
| |
| /// Unlink this recipe from its current VPBasicBlock and insert it into |
| /// the VPBasicBlock that MovePos lives in, right after MovePos. |
| void moveAfter(VPRecipeBase *MovePos); |
| |
| /// Unlink this recipe and insert into BB before I. |
| /// |
| /// \pre I is a valid iterator into BB. |
| void moveBefore(VPBasicBlock &BB, iplist<VPRecipeBase>::iterator I); |
| |
| /// This method unlinks 'this' from the containing basic block, but does not |
| /// delete it. |
| void removeFromParent(); |
| |
| /// This method unlinks 'this' from the containing basic block and deletes it. |
| /// |
| /// \returns an iterator pointing to the element after the erased one |
| iplist<VPRecipeBase>::iterator eraseFromParent(); |
| |
| /// Returns the underlying instruction, if the recipe is a VPValue or nullptr |
| /// otherwise. |
| Instruction *getUnderlyingInstr() { |
| return cast<Instruction>(getVPSingleValue()->getUnderlyingValue()); |
| } |
| const Instruction *getUnderlyingInstr() const { |
| return cast<Instruction>(getVPSingleValue()->getUnderlyingValue()); |
| } |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| // All VPDefs are also VPRecipeBases. |
| return true; |
| } |
| |
| static inline bool classof(const VPUser *U) { |
| return U->getVPUserID() == VPUser::VPUserID::Recipe; |
| } |
| |
| /// Returns true if the recipe may have side-effects. |
| bool mayHaveSideEffects() const; |
| |
| /// Returns true for PHI-like recipes. |
| bool isPhi() const { |
| return getVPDefID() >= VPFirstPHISC && getVPDefID() <= VPLastPHISC; |
| } |
| |
| /// Returns true if the recipe may read from memory. |
| bool mayReadFromMemory() const; |
| |
| /// Returns true if the recipe may write to memory. |
| bool mayWriteToMemory() const; |
| |
| /// Returns true if the recipe may read from or write to memory. |
| bool mayReadOrWriteMemory() const { |
| return mayReadFromMemory() || mayWriteToMemory(); |
| } |
| }; |
| |
| inline bool VPUser::classof(const VPDef *Def) { |
| return Def->getVPDefID() == VPRecipeBase::VPInstructionSC || |
| Def->getVPDefID() == VPRecipeBase::VPWidenSC || |
| Def->getVPDefID() == VPRecipeBase::VPWidenCallSC || |
| Def->getVPDefID() == VPRecipeBase::VPWidenSelectSC || |
| Def->getVPDefID() == VPRecipeBase::VPWidenGEPSC || |
| Def->getVPDefID() == VPRecipeBase::VPBlendSC || |
| Def->getVPDefID() == VPRecipeBase::VPInterleaveSC || |
| Def->getVPDefID() == VPRecipeBase::VPReplicateSC || |
| Def->getVPDefID() == VPRecipeBase::VPReductionSC || |
| Def->getVPDefID() == VPRecipeBase::VPBranchOnMaskSC || |
| Def->getVPDefID() == VPRecipeBase::VPWidenMemoryInstructionSC; |
| } |
| |
| /// This is a concrete Recipe that models a single VPlan-level instruction. |
| /// While as any Recipe it may generate a sequence of IR instructions when |
| /// executed, these instructions would always form a single-def expression as |
| /// the VPInstruction is also a single def-use vertex. |
| class VPInstruction : public VPRecipeBase, public VPValue { |
| friend class VPlanSlp; |
| |
| public: |
| /// VPlan opcodes, extending LLVM IR with idiomatics instructions. |
| enum { |
| FirstOrderRecurrenceSplice = |
| Instruction::OtherOpsEnd + 1, // Combines the incoming and previous |
| // values of a first-order recurrence. |
| Not, |
| ICmpULE, |
| SLPLoad, |
| SLPStore, |
| ActiveLaneMask, |
| }; |
| |
| private: |
| typedef unsigned char OpcodeTy; |
| OpcodeTy Opcode; |
| FastMathFlags FMF; |
| |
| /// Utility method serving execute(): generates a single instance of the |
| /// modeled instruction. |
| void generateInstruction(VPTransformState &State, unsigned Part); |
| |
| protected: |
| void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); } |
| |
| public: |
| VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands) |
| : VPRecipeBase(VPRecipeBase::VPInstructionSC, Operands), |
| VPValue(VPValue::VPVInstructionSC, nullptr, this), Opcode(Opcode) {} |
| |
| VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands) |
| : VPInstruction(Opcode, ArrayRef<VPValue *>(Operands)) {} |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPValue *V) { |
| return V->getVPValueID() == VPValue::VPVInstructionSC; |
| } |
| |
| VPInstruction *clone() const { |
| SmallVector<VPValue *, 2> Operands(operands()); |
| return new VPInstruction(Opcode, Operands); |
| } |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *R) { |
| return R->getVPDefID() == VPRecipeBase::VPInstructionSC; |
| } |
| |
| unsigned getOpcode() const { return Opcode; } |
| |
| /// Generate the instruction. |
| /// TODO: We currently execute only per-part unless a specific instance is |
| /// provided. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the VPInstruction to \p O. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| |
| /// Print the VPInstruction to dbgs() (for debugging). |
| LLVM_DUMP_METHOD void dump() const; |
| #endif |
| |
| /// Return true if this instruction may modify memory. |
| bool mayWriteToMemory() const { |
| // TODO: we can use attributes of the called function to rule out memory |
| // modifications. |
| return Opcode == Instruction::Store || Opcode == Instruction::Call || |
| Opcode == Instruction::Invoke || Opcode == SLPStore; |
| } |
| |
| bool hasResult() const { |
| // CallInst may or may not have a result, depending on the called function. |
| // Conservatively return calls have results for now. |
| switch (getOpcode()) { |
| case Instruction::Ret: |
| case Instruction::Br: |
| case Instruction::Store: |
| case Instruction::Switch: |
| case Instruction::IndirectBr: |
| case Instruction::Resume: |
| case Instruction::CatchRet: |
| case Instruction::Unreachable: |
| case Instruction::Fence: |
| case Instruction::AtomicRMW: |
| return false; |
| default: |
| return true; |
| } |
| } |
| |
| /// Set the fast-math flags. |
| void setFastMathFlags(FastMathFlags FMFNew); |
| }; |
| |
| /// VPWidenRecipe is a recipe for producing a copy of vector type its |
| /// ingredient. This recipe covers most of the traditional vectorization cases |
| /// where each ingredient transforms into a vectorized version of itself. |
| class VPWidenRecipe : public VPRecipeBase, public VPValue { |
| public: |
| template <typename IterT> |
| VPWidenRecipe(Instruction &I, iterator_range<IterT> Operands) |
| : VPRecipeBase(VPRecipeBase::VPWidenSC, Operands), |
| VPValue(VPValue::VPVWidenSC, &I, this) {} |
| |
| ~VPWidenRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPWidenSC; |
| } |
| static inline bool classof(const VPValue *V) { |
| return V->getVPValueID() == VPValue::VPVWidenSC; |
| } |
| |
| /// Produce widened copies of all Ingredients. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// A recipe for widening Call instructions. |
| class VPWidenCallRecipe : public VPRecipeBase, public VPValue { |
| |
| public: |
| template <typename IterT> |
| VPWidenCallRecipe(CallInst &I, iterator_range<IterT> CallArguments) |
| : VPRecipeBase(VPRecipeBase::VPWidenCallSC, CallArguments), |
| VPValue(VPValue::VPVWidenCallSC, &I, this) {} |
| |
| ~VPWidenCallRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPWidenCallSC; |
| } |
| |
| /// Produce a widened version of the call instruction. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// A recipe for widening select instructions. |
| class VPWidenSelectRecipe : public VPRecipeBase, public VPValue { |
| |
| /// Is the condition of the select loop invariant? |
| bool InvariantCond; |
| |
| public: |
| template <typename IterT> |
| VPWidenSelectRecipe(SelectInst &I, iterator_range<IterT> Operands, |
| bool InvariantCond) |
| : VPRecipeBase(VPRecipeBase::VPWidenSelectSC, Operands), |
| VPValue(VPValue::VPVWidenSelectSC, &I, this), |
| InvariantCond(InvariantCond) {} |
| |
| ~VPWidenSelectRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPWidenSelectSC; |
| } |
| |
| /// Produce a widened version of the select instruction. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// A recipe for handling GEP instructions. |
| class VPWidenGEPRecipe : public VPRecipeBase, public VPValue { |
| bool IsPtrLoopInvariant; |
| SmallBitVector IsIndexLoopInvariant; |
| |
| public: |
| template <typename IterT> |
| VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands) |
| : VPRecipeBase(VPRecipeBase::VPWidenGEPSC, Operands), |
| VPValue(VPWidenGEPSC, GEP, this), |
| IsIndexLoopInvariant(GEP->getNumIndices(), false) {} |
| |
| template <typename IterT> |
| VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands, |
| Loop *OrigLoop) |
| : VPRecipeBase(VPRecipeBase::VPWidenGEPSC, Operands), |
| VPValue(VPValue::VPVWidenGEPSC, GEP, this), |
| IsIndexLoopInvariant(GEP->getNumIndices(), false) { |
| IsPtrLoopInvariant = OrigLoop->isLoopInvariant(GEP->getPointerOperand()); |
| for (auto Index : enumerate(GEP->indices())) |
| IsIndexLoopInvariant[Index.index()] = |
| OrigLoop->isLoopInvariant(Index.value().get()); |
| } |
| ~VPWidenGEPRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPWidenGEPSC; |
| } |
| |
| /// Generate the gep nodes. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// A recipe for handling phi nodes of integer and floating-point inductions, |
| /// producing their vector and scalar values. |
| class VPWidenIntOrFpInductionRecipe : public VPRecipeBase { |
| PHINode *IV; |
| |
| public: |
| VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, Instruction *Cast, |
| TruncInst *Trunc = nullptr) |
| : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), IV(IV) { |
| if (Trunc) |
| new VPValue(Trunc, this); |
| else |
| new VPValue(IV, this); |
| |
| if (Cast) |
| new VPValue(Cast, this); |
| } |
| ~VPWidenIntOrFpInductionRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPWidenIntOrFpInductionSC; |
| } |
| |
| /// Generate the vectorized and scalarized versions of the phi node as |
| /// needed by their users. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| |
| /// Returns the start value of the induction. |
| VPValue *getStartValue() { return getOperand(0); } |
| |
| /// Returns the cast VPValue, if one is attached, or nullptr otherwise. |
| VPValue *getCastValue() { |
| if (getNumDefinedValues() != 2) |
| return nullptr; |
| return getVPValue(1); |
| } |
| |
| /// Returns the first defined value as TruncInst, if it is one or nullptr |
| /// otherwise. |
| TruncInst *getTruncInst() { |
| return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue()); |
| } |
| const TruncInst *getTruncInst() const { |
| return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue()); |
| } |
| }; |
| |
| /// A recipe for handling first order recurrences and pointer inductions. For |
| /// first-order recurrences, the start value is the first operand of the recipe |
| /// and the incoming value from the backedge is the second operand. It also |
| /// serves as base class for VPReductionPHIRecipe. In the VPlan native path, all |
| /// incoming VPValues & VPBasicBlock pairs are managed in the recipe directly. |
| class VPWidenPHIRecipe : public VPRecipeBase, public VPValue { |
| /// List of incoming blocks. Only used in the VPlan native path. |
| SmallVector<VPBasicBlock *, 2> IncomingBlocks; |
| |
| protected: |
| VPWidenPHIRecipe(unsigned char VPVID, unsigned char VPDefID, PHINode *Phi, |
| VPValue *Start = nullptr) |
| : VPRecipeBase(VPDefID, {}), VPValue(VPVID, Phi, this) { |
| if (Start) |
| addOperand(Start); |
| } |
| |
| public: |
| /// Create a VPWidenPHIRecipe for \p Phi |
| VPWidenPHIRecipe(PHINode *Phi) |
| : VPWidenPHIRecipe(VPVWidenPHISC, VPWidenPHISC, Phi) {} |
| |
| /// Create a new VPWidenPHIRecipe for \p Phi with start value \p Start. |
| VPWidenPHIRecipe(PHINode *Phi, VPValue &Start) : VPWidenPHIRecipe(Phi) { |
| addOperand(&Start); |
| } |
| |
| ~VPWidenPHIRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPRecipeBase *B) { |
| return B->getVPDefID() == VPRecipeBase::VPWidenPHISC || |
| B->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC || |
| B->getVPDefID() == VPRecipeBase::VPReductionPHISC; |
| } |
| static inline bool classof(const VPValue *V) { |
| return V->getVPValueID() == VPValue::VPVWidenPHISC || |
| V->getVPValueID() == VPValue::VPVFirstOrderRecurrencePHISC || |
| V->getVPValueID() == VPValue::VPVReductionPHISC; |
| } |
| |
| /// Generate the phi/select nodes. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| |
| /// Returns the start value of the phi, if it is a reduction or first-order |
| /// recurrence. |
| VPValue *getStartValue() { |
| return getNumOperands() == 0 ? nullptr : getOperand(0); |
| } |
| |
| /// Returns the incoming value from the loop backedge, if it is a reduction or |
| /// first-order recurrence. |
| VPValue *getBackedgeValue() { |
| return getOperand(1); |
| } |
| |
| /// Returns the backedge value as a recipe. The backedge value is guaranteed |
| /// to be a recipe. |
| VPRecipeBase *getBackedgeRecipe() { |
| return cast<VPRecipeBase>(getBackedgeValue()->getDef()); |
| } |
| |
| /// Adds a pair (\p IncomingV, \p IncomingBlock) to the phi. |
| void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock) { |
| addOperand(IncomingV); |
| IncomingBlocks.push_back(IncomingBlock); |
| } |
| |
| /// Returns the \p I th incoming VPValue. |
| VPValue *getIncomingValue(unsigned I) { return getOperand(I); } |
| |
| /// Returns the \p I th incoming VPBasicBlock. |
| VPBasicBlock *getIncomingBlock(unsigned I) { return IncomingBlocks[I]; } |
| }; |
| |
| /// A recipe for handling first-order recurrence phis. The start value is the |
| /// first operand of the recipe and the incoming value from the backedge is the |
| /// second operand. |
| struct VPFirstOrderRecurrencePHIRecipe : public VPWidenPHIRecipe { |
| VPFirstOrderRecurrencePHIRecipe(PHINode *Phi, VPValue &Start) |
| : VPWidenPHIRecipe(VPVFirstOrderRecurrencePHISC, |
| VPFirstOrderRecurrencePHISC, Phi, &Start) {} |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPRecipeBase *R) { |
| return R->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC; |
| } |
| static inline bool classof(const VPWidenPHIRecipe *D) { |
| return D->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC; |
| } |
| static inline bool classof(const VPValue *V) { |
| return V->getVPValueID() == VPValue::VPVFirstOrderRecurrencePHISC; |
| } |
| |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// A recipe for handling reduction phis. The start value is the first operand |
| /// of the recipe and the incoming value from the backedge is the second |
| /// operand. |
| class VPReductionPHIRecipe : public VPWidenPHIRecipe { |
| /// Descriptor for the reduction. |
| RecurrenceDescriptor &RdxDesc; |
| |
| /// The phi is part of an in-loop reduction. |
| bool IsInLoop; |
| |
| /// The phi is part of an ordered reduction. Requires IsInLoop to be true. |
| bool IsOrdered; |
| |
| public: |
| /// Create a new VPReductionPHIRecipe for the reduction \p Phi described by \p |
| /// RdxDesc. |
| VPReductionPHIRecipe(PHINode *Phi, RecurrenceDescriptor &RdxDesc, |
| VPValue &Start, bool IsInLoop = false, |
| bool IsOrdered = false) |
| : VPWidenPHIRecipe(VPVReductionPHISC, VPReductionPHISC, Phi, &Start), |
| RdxDesc(RdxDesc), IsInLoop(IsInLoop), IsOrdered(IsOrdered) { |
| assert((!IsOrdered || IsInLoop) && "IsOrdered requires IsInLoop"); |
| } |
| |
| ~VPReductionPHIRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPRecipeBase *R) { |
| return R->getVPDefID() == VPRecipeBase::VPReductionPHISC; |
| } |
| static inline bool classof(const VPValue *V) { |
| return V->getVPValueID() == VPValue::VPVReductionPHISC; |
| } |
| static inline bool classof(const VPWidenPHIRecipe *R) { |
| return R->getVPDefID() == VPRecipeBase::VPReductionPHISC; |
| } |
| |
| /// Generate the phi/select nodes. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| |
| RecurrenceDescriptor &getRecurrenceDescriptor() { return RdxDesc; } |
| |
| /// Returns true, if the phi is part of an ordered reduction. |
| bool isOrdered() const { return IsOrdered; } |
| |
| /// Returns true, if the phi is part of an in-loop reduction. |
| bool isInLoop() const { return IsInLoop; } |
| }; |
| |
| /// A recipe for vectorizing a phi-node as a sequence of mask-based select |
| /// instructions. |
| class VPBlendRecipe : public VPRecipeBase, public VPValue { |
| PHINode *Phi; |
| |
| public: |
| /// The blend operation is a User of the incoming values and of their |
| /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value |
| /// might be incoming with a full mask for which there is no VPValue. |
| VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands) |
| : VPRecipeBase(VPBlendSC, Operands), |
| VPValue(VPValue::VPVBlendSC, Phi, this), Phi(Phi) { |
| assert(Operands.size() > 0 && |
| ((Operands.size() == 1) || (Operands.size() % 2 == 0)) && |
| "Expected either a single incoming value or a positive even number " |
| "of operands"); |
| } |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPBlendSC; |
| } |
| |
| /// Return the number of incoming values, taking into account that a single |
| /// incoming value has no mask. |
| unsigned getNumIncomingValues() const { return (getNumOperands() + 1) / 2; } |
| |
| /// Return incoming value number \p Idx. |
| VPValue *getIncomingValue(unsigned Idx) const { return getOperand(Idx * 2); } |
| |
| /// Return mask number \p Idx. |
| VPValue *getMask(unsigned Idx) const { return getOperand(Idx * 2 + 1); } |
| |
| /// Generate the phi/select nodes. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// VPInterleaveRecipe is a recipe for transforming an interleave group of load |
| /// or stores into one wide load/store and shuffles. The first operand of a |
| /// VPInterleave recipe is the address, followed by the stored values, followed |
| /// by an optional mask. |
| class VPInterleaveRecipe : public VPRecipeBase { |
| const InterleaveGroup<Instruction> *IG; |
| |
| bool HasMask = false; |
| |
| public: |
| VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr, |
| ArrayRef<VPValue *> StoredValues, VPValue *Mask) |
| : VPRecipeBase(VPInterleaveSC, {Addr}), IG(IG) { |
| for (unsigned i = 0; i < IG->getFactor(); ++i) |
| if (Instruction *I = IG->getMember(i)) { |
| if (I->getType()->isVoidTy()) |
| continue; |
| new VPValue(I, this); |
| } |
| |
| for (auto *SV : StoredValues) |
| addOperand(SV); |
| if (Mask) { |
| HasMask = true; |
| addOperand(Mask); |
| } |
| } |
| ~VPInterleaveRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPInterleaveSC; |
| } |
| |
| /// Return the address accessed by this recipe. |
| VPValue *getAddr() const { |
| return getOperand(0); // Address is the 1st, mandatory operand. |
| } |
| |
| /// Return the mask used by this recipe. Note that a full mask is represented |
| /// by a nullptr. |
| VPValue *getMask() const { |
| // Mask is optional and therefore the last, currently 2nd operand. |
| return HasMask ? getOperand(getNumOperands() - 1) : nullptr; |
| } |
| |
| /// Return the VPValues stored by this interleave group. If it is a load |
| /// interleave group, return an empty ArrayRef. |
| ArrayRef<VPValue *> getStoredValues() const { |
| // The first operand is the address, followed by the stored values, followed |
| // by an optional mask. |
| return ArrayRef<VPValue *>(op_begin(), getNumOperands()) |
| .slice(1, getNumStoreOperands()); |
| } |
| |
| /// Generate the wide load or store, and shuffles. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| |
| const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; } |
| |
| /// Returns the number of stored operands of this interleave group. Returns 0 |
| /// for load interleave groups. |
| unsigned getNumStoreOperands() const { |
| return getNumOperands() - (HasMask ? 2 : 1); |
| } |
| }; |
| |
| /// A recipe to represent inloop reduction operations, performing a reduction on |
| /// a vector operand into a scalar value, and adding the result to a chain. |
| /// The Operands are {ChainOp, VecOp, [Condition]}. |
| class VPReductionRecipe : public VPRecipeBase, public VPValue { |
| /// The recurrence decriptor for the reduction in question. |
| RecurrenceDescriptor *RdxDesc; |
| /// Pointer to the TTI, needed to create the target reduction |
| const TargetTransformInfo *TTI; |
| |
| public: |
| VPReductionRecipe(RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp, |
| VPValue *VecOp, VPValue *CondOp, |
| const TargetTransformInfo *TTI) |
| : VPRecipeBase(VPRecipeBase::VPReductionSC, {ChainOp, VecOp}), |
| VPValue(VPValue::VPVReductionSC, I, this), RdxDesc(R), TTI(TTI) { |
| if (CondOp) |
| addOperand(CondOp); |
| } |
| |
| ~VPReductionRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPValue *V) { |
| return V->getVPValueID() == VPValue::VPVReductionSC; |
| } |
| |
| /// Generate the reduction in the loop |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| |
| /// The VPValue of the scalar Chain being accumulated. |
| VPValue *getChainOp() const { return getOperand(0); } |
| /// The VPValue of the vector value to be reduced. |
| VPValue *getVecOp() const { return getOperand(1); } |
| /// The VPValue of the condition for the block. |
| VPValue *getCondOp() const { |
| return getNumOperands() > 2 ? getOperand(2) : nullptr; |
| } |
| }; |
| |
| /// VPReplicateRecipe replicates a given instruction producing multiple scalar |
| /// copies of the original scalar type, one per lane, instead of producing a |
| /// single copy of widened type for all lanes. If the instruction is known to be |
| /// uniform only one copy, per lane zero, will be generated. |
| class VPReplicateRecipe : public VPRecipeBase, public VPValue { |
| /// Indicator if only a single replica per lane is needed. |
| bool IsUniform; |
| |
| /// Indicator if the replicas are also predicated. |
| bool IsPredicated; |
| |
| /// Indicator if the scalar values should also be packed into a vector. |
| bool AlsoPack; |
| |
| public: |
| template <typename IterT> |
| VPReplicateRecipe(Instruction *I, iterator_range<IterT> Operands, |
| bool IsUniform, bool IsPredicated = false) |
| : VPRecipeBase(VPReplicateSC, Operands), VPValue(VPVReplicateSC, I, this), |
| IsUniform(IsUniform), IsPredicated(IsPredicated) { |
| // Retain the previous behavior of predicateInstructions(), where an |
| // insert-element of a predicated instruction got hoisted into the |
| // predicated basic block iff it was its only user. This is achieved by |
| // having predicated instructions also pack their values into a vector by |
| // default unless they have a replicated user which uses their scalar value. |
| AlsoPack = IsPredicated && !I->use_empty(); |
| } |
| |
| ~VPReplicateRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPReplicateSC; |
| } |
| |
| static inline bool classof(const VPValue *V) { |
| return V->getVPValueID() == VPValue::VPVReplicateSC; |
| } |
| |
| /// Generate replicas of the desired Ingredient. Replicas will be generated |
| /// for all parts and lanes unless a specific part and lane are specified in |
| /// the \p State. |
| void execute(VPTransformState &State) override; |
| |
| void setAlsoPack(bool Pack) { AlsoPack = Pack; } |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| |
| bool isUniform() const { return IsUniform; } |
| |
| bool isPacked() const { return AlsoPack; } |
| |
| bool isPredicated() const { return IsPredicated; } |
| }; |
| |
| /// A recipe for generating conditional branches on the bits of a mask. |
| class VPBranchOnMaskRecipe : public VPRecipeBase { |
| public: |
| VPBranchOnMaskRecipe(VPValue *BlockInMask) |
| : VPRecipeBase(VPBranchOnMaskSC, {}) { |
| if (BlockInMask) // nullptr means all-one mask. |
| addOperand(BlockInMask); |
| } |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPBranchOnMaskSC; |
| } |
| |
| /// Generate the extraction of the appropriate bit from the block mask and the |
| /// conditional branch. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override { |
| O << Indent << "BRANCH-ON-MASK "; |
| if (VPValue *Mask = getMask()) |
| Mask->printAsOperand(O, SlotTracker); |
| else |
| O << " All-One"; |
| } |
| #endif |
| |
| /// Return the mask used by this recipe. Note that a full mask is represented |
| /// by a nullptr. |
| VPValue *getMask() const { |
| assert(getNumOperands() <= 1 && "should have either 0 or 1 operands"); |
| // Mask is optional. |
| return getNumOperands() == 1 ? getOperand(0) : nullptr; |
| } |
| }; |
| |
| /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when |
| /// control converges back from a Branch-on-Mask. The phi nodes are needed in |
| /// order to merge values that are set under such a branch and feed their uses. |
| /// The phi nodes can be scalar or vector depending on the users of the value. |
| /// This recipe works in concert with VPBranchOnMaskRecipe. |
| class VPPredInstPHIRecipe : public VPRecipeBase, public VPValue { |
| public: |
| /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi |
| /// nodes after merging back from a Branch-on-Mask. |
| VPPredInstPHIRecipe(VPValue *PredV) |
| : VPRecipeBase(VPPredInstPHISC, PredV), |
| VPValue(VPValue::VPVPredInstPHI, nullptr, this) {} |
| ~VPPredInstPHIRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPPredInstPHISC; |
| } |
| |
| /// Generates phi nodes for live-outs as needed to retain SSA form. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// A Recipe for widening load/store operations. |
| /// The recipe uses the following VPValues: |
| /// - For load: Address, optional mask |
| /// - For store: Address, stored value, optional mask |
| /// TODO: We currently execute only per-part unless a specific instance is |
| /// provided. |
| class VPWidenMemoryInstructionRecipe : public VPRecipeBase, public VPValue { |
| Instruction &Ingredient; |
| |
| // Whether the loaded-from / stored-to addresses are consecutive. |
| bool Consecutive; |
| |
| // Whether the consecutive loaded/stored addresses are in reverse order. |
| bool Reverse; |
| |
| void setMask(VPValue *Mask) { |
| if (!Mask) |
| return; |
| addOperand(Mask); |
| } |
| |
| bool isMasked() const { |
| return isStore() ? getNumOperands() == 3 : getNumOperands() == 2; |
| } |
| |
| public: |
| VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask, |
| bool Consecutive, bool Reverse) |
| : VPRecipeBase(VPWidenMemoryInstructionSC, {Addr}), |
| VPValue(VPValue::VPVMemoryInstructionSC, &Load, this), Ingredient(Load), |
| Consecutive(Consecutive), Reverse(Reverse) { |
| assert((Consecutive || !Reverse) && "Reverse implies consecutive"); |
| setMask(Mask); |
| } |
| |
| VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr, |
| VPValue *StoredValue, VPValue *Mask, |
| bool Consecutive, bool Reverse) |
| : VPRecipeBase(VPWidenMemoryInstructionSC, {Addr, StoredValue}), |
| VPValue(VPValue::VPVMemoryInstructionSC, &Store, this), |
| Ingredient(Store), Consecutive(Consecutive), Reverse(Reverse) { |
| assert((Consecutive || !Reverse) && "Reverse implies consecutive"); |
| setMask(Mask); |
| } |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPWidenMemoryInstructionSC; |
| } |
| |
| /// Return the address accessed by this recipe. |
| VPValue *getAddr() const { |
| return getOperand(0); // Address is the 1st, mandatory operand. |
| } |
| |
| /// Return the mask used by this recipe. Note that a full mask is represented |
| /// by a nullptr. |
| VPValue *getMask() const { |
| // Mask is optional and therefore the last operand. |
| return isMasked() ? getOperand(getNumOperands() - 1) : nullptr; |
| } |
| |
| /// Returns true if this recipe is a store. |
| bool isStore() const { return isa<StoreInst>(Ingredient); } |
| |
| /// Return the address accessed by this recipe. |
| VPValue *getStoredValue() const { |
| assert(isStore() && "Stored value only available for store instructions"); |
| return getOperand(1); // Stored value is the 2nd, mandatory operand. |
| } |
| |
| // Return whether the loaded-from / stored-to addresses are consecutive. |
| bool isConsecutive() const { return Consecutive; } |
| |
| // Return whether the consecutive loaded/stored addresses are in reverse |
| // order. |
| bool isReverse() const { return Reverse; } |
| |
| /// Generate the wide load/store. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// A Recipe for widening the canonical induction variable of the vector loop. |
| class VPWidenCanonicalIVRecipe : public VPRecipeBase, public VPValue { |
| public: |
| VPWidenCanonicalIVRecipe() |
| : VPRecipeBase(VPWidenCanonicalIVSC, {}), |
| VPValue(VPValue::VPVWidenCanonicalIVSC, nullptr, this) {} |
| |
| ~VPWidenCanonicalIVRecipe() override = default; |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPDef *D) { |
| return D->getVPDefID() == VPRecipeBase::VPWidenCanonicalIVSC; |
| } |
| |
| /// Generate a canonical vector induction variable of the vector loop, with |
| /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and |
| /// step = <VF*UF, VF*UF, ..., VF*UF>. |
| void execute(VPTransformState &State) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print the recipe. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| #endif |
| }; |
| |
| /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It |
| /// holds a sequence of zero or more VPRecipe's each representing a sequence of |
| /// output IR instructions. All PHI-like recipes must come before any non-PHI recipes. |
| class VPBasicBlock : public VPBlockBase { |
| public: |
| using RecipeListTy = iplist<VPRecipeBase>; |
| |
| private: |
| /// The VPRecipes held in the order of output instructions to generate. |
| RecipeListTy Recipes; |
| |
| public: |
| VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr) |
| : VPBlockBase(VPBasicBlockSC, Name.str()) { |
| if (Recipe) |
| appendRecipe(Recipe); |
| } |
| |
| ~VPBasicBlock() override { |
| while (!Recipes.empty()) |
| Recipes.pop_back(); |
| } |
| |
| /// Instruction iterators... |
| using iterator = RecipeListTy::iterator; |
| using const_iterator = RecipeListTy::const_iterator; |
| using reverse_iterator = RecipeListTy::reverse_iterator; |
| using const_reverse_iterator = RecipeListTy::const_reverse_iterator; |
| |
| //===--------------------------------------------------------------------===// |
| /// Recipe iterator methods |
| /// |
| inline iterator begin() { return Recipes.begin(); } |
| inline const_iterator begin() const { return Recipes.begin(); } |
| inline iterator end() { return Recipes.end(); } |
| inline const_iterator end() const { return Recipes.end(); } |
| |
| inline reverse_iterator rbegin() { return Recipes.rbegin(); } |
| inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); } |
| inline reverse_iterator rend() { return Recipes.rend(); } |
| inline const_reverse_iterator rend() const { return Recipes.rend(); } |
| |
| inline size_t size() const { return Recipes.size(); } |
| inline bool empty() const { return Recipes.empty(); } |
| inline const VPRecipeBase &front() const { return Recipes.front(); } |
| inline VPRecipeBase &front() { return Recipes.front(); } |
| inline const VPRecipeBase &back() const { return Recipes.back(); } |
| inline VPRecipeBase &back() { return Recipes.back(); } |
| |
| /// Returns a reference to the list of recipes. |
| RecipeListTy &getRecipeList() { return Recipes; } |
| |
| /// Returns a pointer to a member of the recipe list. |
| static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) { |
| return &VPBasicBlock::Recipes; |
| } |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPBlockBase *V) { |
| return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC; |
| } |
| |
| void insert(VPRecipeBase *Recipe, iterator InsertPt) { |
| assert(Recipe && "No recipe to append."); |
| assert(!Recipe->Parent && "Recipe already in VPlan"); |
| Recipe->Parent = this; |
| Recipes.insert(InsertPt, Recipe); |
| } |
| |
| /// Augment the existing recipes of a VPBasicBlock with an additional |
| /// \p Recipe as the last recipe. |
| void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); } |
| |
| /// The method which generates the output IR instructions that correspond to |
| /// this VPBasicBlock, thereby "executing" the VPlan. |
| void execute(struct VPTransformState *State) override; |
| |
| /// Return the position of the first non-phi node recipe in the block. |
| iterator getFirstNonPhi(); |
| |
| /// Returns an iterator range over the PHI-like recipes in the block. |
| iterator_range<iterator> phis() { |
| return make_range(begin(), getFirstNonPhi()); |
| } |
| |
| void dropAllReferences(VPValue *NewValue) override; |
| |
| /// Split current block at \p SplitAt by inserting a new block between the |
| /// current block and its successors and moving all recipes starting at |
| /// SplitAt to the new block. Returns the new block. |
| VPBasicBlock *splitAt(iterator SplitAt); |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p |
| /// SlotTracker is used to print unnamed VPValue's using consequtive numbers. |
| /// |
| /// Note that the numbering is applied to the whole VPlan, so printing |
| /// individual blocks is consistent with the whole VPlan printing. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| using VPBlockBase::print; // Get the print(raw_stream &O) version. |
| #endif |
| |
| private: |
| /// Create an IR BasicBlock to hold the output instructions generated by this |
| /// VPBasicBlock, and return it. Update the CFGState accordingly. |
| BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG); |
| }; |
| |
| /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks |
| /// which form a Single-Entry-Single-Exit subgraph of the output IR CFG. |
| /// A VPRegionBlock may indicate that its contents are to be replicated several |
| /// times. This is designed to support predicated scalarization, in which a |
| /// scalar if-then code structure needs to be generated VF * UF times. Having |
| /// this replication indicator helps to keep a single model for multiple |
| /// candidate VF's. The actual replication takes place only once the desired VF |
| /// and UF have been determined. |
| class VPRegionBlock : public VPBlockBase { |
| /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock. |
| VPBlockBase *Entry; |
| |
| /// Hold the Single Exit of the SESE region modelled by the VPRegionBlock. |
| VPBlockBase *Exit; |
| |
| /// An indicator whether this region is to generate multiple replicated |
| /// instances of output IR corresponding to its VPBlockBases. |
| bool IsReplicator; |
| |
| public: |
| VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exit, |
| const std::string &Name = "", bool IsReplicator = false) |
| : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exit(Exit), |
| IsReplicator(IsReplicator) { |
| assert(Entry->getPredecessors().empty() && "Entry block has predecessors."); |
| assert(Exit->getSuccessors().empty() && "Exit block has successors."); |
| Entry->setParent(this); |
| Exit->setParent(this); |
| } |
| VPRegionBlock(const std::string &Name = "", bool IsReplicator = false) |
| : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exit(nullptr), |
| IsReplicator(IsReplicator) {} |
| |
| ~VPRegionBlock() override { |
| if (Entry) { |
| VPValue DummyValue; |
| Entry->dropAllReferences(&DummyValue); |
| deleteCFG(Entry); |
| } |
| } |
| |
| /// Method to support type inquiry through isa, cast, and dyn_cast. |
| static inline bool classof(const VPBlockBase *V) { |
| return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC; |
| } |
| |
| const VPBlockBase *getEntry() const { return Entry; } |
| VPBlockBase *getEntry() { return Entry; } |
| |
| /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p |
| /// EntryBlock must have no predecessors. |
| void setEntry(VPBlockBase *EntryBlock) { |
| assert(EntryBlock->getPredecessors().empty() && |
| "Entry block cannot have predecessors."); |
| Entry = EntryBlock; |
| EntryBlock->setParent(this); |
| } |
| |
| // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a |
| // specific interface of llvm::Function, instead of using |
| // GraphTraints::getEntryNode. We should add a new template parameter to |
| // DominatorTreeBase representing the Graph type. |
| VPBlockBase &front() const { return *Entry; } |
| |
| const VPBlockBase *getExit() const { return Exit; } |
| VPBlockBase *getExit() { return Exit; } |
| |
| /// Set \p ExitBlock as the exit VPBlockBase of this VPRegionBlock. \p |
| /// ExitBlock must have no successors. |
| void setExit(VPBlockBase *ExitBlock) { |
| assert(ExitBlock->getSuccessors().empty() && |
| "Exit block cannot have successors."); |
| Exit = ExitBlock; |
| ExitBlock->setParent(this); |
| } |
| |
| /// An indicator whether this region is to generate multiple replicated |
| /// instances of output IR corresponding to its VPBlockBases. |
| bool isReplicator() const { return IsReplicator; } |
| |
| /// The method which generates the output IR instructions that correspond to |
| /// this VPRegionBlock, thereby "executing" the VPlan. |
| void execute(struct VPTransformState *State) override; |
| |
| void dropAllReferences(VPValue *NewValue) override; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print this VPRegionBlock to \p O (recursively), prefixing all lines with |
| /// \p Indent. \p SlotTracker is used to print unnamed VPValue's using |
| /// consequtive numbers. |
| /// |
| /// Note that the numbering is applied to the whole VPlan, so printing |
| /// individual regions is consistent with the whole VPlan printing. |
| void print(raw_ostream &O, const Twine &Indent, |
| VPSlotTracker &SlotTracker) const override; |
| using VPBlockBase::print; // Get the print(raw_stream &O) version. |
| #endif |
| }; |
| |
| //===----------------------------------------------------------------------===// |
| // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs // |
| //===----------------------------------------------------------------------===// |
| |
| // The following set of template specializations implement GraphTraits to treat |
| // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note |
| // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the |
| // VPBlockBase is a VPRegionBlock, this specialization provides access to its |
| // successors/predecessors but not to the blocks inside the region. |
| |
| template <> struct GraphTraits<VPBlockBase *> { |
| using NodeRef = VPBlockBase *; |
| using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator; |
| |
| static NodeRef getEntryNode(NodeRef N) { return N; } |
| |
| static inline ChildIteratorType child_begin(NodeRef N) { |
| return N->getSuccessors().begin(); |
| } |
| |
| static inline ChildIteratorType child_end(NodeRef N) { |
| return N->getSuccessors().end(); |
| } |
| }; |
| |
| template <> struct GraphTraits<const VPBlockBase *> { |
| using NodeRef = const VPBlockBase *; |
| using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator; |
| |
| static NodeRef getEntryNode(NodeRef N) { return N; } |
| |
| static inline ChildIteratorType child_begin(NodeRef N) { |
| return N->getSuccessors().begin(); |
| } |
| |
| static inline ChildIteratorType child_end(NodeRef N) { |
| return N->getSuccessors().end(); |
| } |
| }; |
| |
| // Inverse order specialization for VPBasicBlocks. Predecessors are used instead |
| // of successors for the inverse traversal. |
| template <> struct GraphTraits<Inverse<VPBlockBase *>> { |
| using NodeRef = VPBlockBase *; |
| using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator; |
| |
| static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; } |
| |
| static inline ChildIteratorType child_begin(NodeRef N) { |
| return N->getPredecessors().begin(); |
| } |
| |
| static inline ChildIteratorType child_end(NodeRef N) { |
| return N->getPredecessors().end(); |
| } |
| }; |
| |
| // The following set of template specializations implement GraphTraits to |
| // treat VPRegionBlock as a graph and recurse inside its nodes. It's important |
| // to note that the blocks inside the VPRegionBlock are treated as VPBlockBases |
| // (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so |
| // there won't be automatic recursion into other VPBlockBases that turn to be |
| // VPRegionBlocks. |
| |
| template <> |
| struct GraphTraits<VPRegionBlock *> : public GraphTraits<VPBlockBase *> { |
| using GraphRef = VPRegionBlock *; |
| using nodes_iterator = df_iterator<NodeRef>; |
| |
| static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); } |
| |
| static nodes_iterator nodes_begin(GraphRef N) { |
| return nodes_iterator::begin(N->getEntry()); |
| } |
| |
| static nodes_iterator nodes_end(GraphRef N) { |
| // df_iterator::end() returns an empty iterator so the node used doesn't |
| // matter. |
| return nodes_iterator::end(N); |
| } |
| }; |
| |
| template <> |
| struct GraphTraits<const VPRegionBlock *> |
| : public GraphTraits<const VPBlockBase *> { |
| using GraphRef = const VPRegionBlock *; |
| using nodes_iterator = df_iterator<NodeRef>; |
| |
| static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); } |
| |
| static nodes_iterator nodes_begin(GraphRef N) { |
| return nodes_iterator::begin(N->getEntry()); |
| } |
| |
| static nodes_iterator nodes_end(GraphRef N) { |
| // df_iterator::end() returns an empty iterator so the node used doesn't |
| // matter. |
| return nodes_iterator::end(N); |
| } |
| }; |
| |
| template <> |
| struct GraphTraits<Inverse<VPRegionBlock *>> |
| : public GraphTraits<Inverse<VPBlockBase *>> { |
| using GraphRef = VPRegionBlock *; |
| using nodes_iterator = df_iterator<NodeRef>; |
| |
| static NodeRef getEntryNode(Inverse<GraphRef> N) { |
| return N.Graph->getExit(); |
| } |
| |
| static nodes_iterator nodes_begin(GraphRef N) { |
| return nodes_iterator::begin(N->getExit()); |
| } |
| |
| static nodes_iterator nodes_end(GraphRef N) { |
| // df_iterator::end() returns an empty iterator so the node used doesn't |
| // matter. |
| return nodes_iterator::end(N); |
| } |
| }; |
| |
| /// Iterator to traverse all successors of a VPBlockBase node. This includes the |
| /// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their |
| /// parent region's successors. This ensures all blocks in a region are visited |
| /// before any blocks in a successor region when doing a reverse post-order |
| // traversal of the graph. |
| template <typename BlockPtrTy> |
| class VPAllSuccessorsIterator |
| : public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>, |
| std::forward_iterator_tag, VPBlockBase> { |
| BlockPtrTy Block; |
| /// Index of the current successor. For VPBasicBlock nodes, this simply is the |
| /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is |
| /// used for the region's entry block, and SuccessorIdx - 1 are the indices |
| /// for the successor array. |
| size_t SuccessorIdx; |
| |
| static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) { |
| while (Current && Current->getNumSuccessors() == 0) |
| Current = Current->getParent(); |
| return Current; |
| } |
| |
| /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by |
| /// both the const and non-const operator* implementations. |
| template <typename T1> static T1 deref(T1 Block, unsigned SuccIdx) { |
| if (auto *R = dyn_cast<VPRegionBlock>(Block)) { |
| if (SuccIdx == 0) |
| return R->getEntry(); |
| SuccIdx--; |
| } |
| |
| // For exit blocks, use the next parent region with successors. |
| return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx]; |
| } |
| |
| public: |
| VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0) |
| : Block(Block), SuccessorIdx(Idx) {} |
| VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other) |
| : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {} |
| |
| VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) { |
| Block = R.Block; |
| SuccessorIdx = R.SuccessorIdx; |
| return *this; |
| } |
| |
| static VPAllSuccessorsIterator end(BlockPtrTy Block) { |
| BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block); |
| unsigned NumSuccessors = ParentWithSuccs |
| ? ParentWithSuccs->getNumSuccessors() |
| : Block->getNumSuccessors(); |
| |
| if (auto *R = dyn_cast<VPRegionBlock>(Block)) |
| return {R, NumSuccessors + 1}; |
| return {Block, NumSuccessors}; |
| } |
| |
| bool operator==(const VPAllSuccessorsIterator &R) const { |
| return Block == R.Block && SuccessorIdx == R.SuccessorIdx; |
| } |
| |
| const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); } |
| |
| BlockPtrTy operator*() { return deref(Block, SuccessorIdx); } |
| |
| VPAllSuccessorsIterator &operator++() { |
| SuccessorIdx++; |
| return *this; |
| } |
| |
| VPAllSuccessorsIterator operator++(int X) { |
| VPAllSuccessorsIterator Orig = *this; |
| SuccessorIdx++; |
| return Orig; |
| } |
| }; |
| |
| /// Helper for GraphTraits specialization that traverses through VPRegionBlocks. |
| template <typename BlockTy> class VPBlockRecursiveTraversalWrapper { |
| BlockTy Entry; |
| |
| public: |
| VPBlockRecursiveTraversalWrapper(BlockTy Entry) : Entry(Entry) {} |
| BlockTy getEntry() { return Entry; } |
| }; |
| |
| /// GraphTraits specialization to recursively traverse VPBlockBase nodes, |
| /// including traversing through VPRegionBlocks. Exit blocks of a region |
| /// implicitly have their parent region's successors. This ensures all blocks in |
| /// a region are visited before any blocks in a successor region when doing a |
| /// reverse post-order traversal of the graph. |
| template <> |
| struct GraphTraits<VPBlockRecursiveTraversalWrapper<VPBlockBase *>> { |
| using NodeRef = VPBlockBase *; |
| using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>; |
| |
| static NodeRef |
| getEntryNode(VPBlockRecursiveTraversalWrapper<VPBlockBase *> N) { |
| return N.getEntry(); |
| } |
| |
| static inline ChildIteratorType child_begin(NodeRef N) { |
| return ChildIteratorType(N); |
| } |
| |
| static inline ChildIteratorType child_end(NodeRef N) { |
| return ChildIteratorType::end(N); |
| } |
| }; |
| |
| template <> |
| struct GraphTraits<VPBlockRecursiveTraversalWrapper<const VPBlockBase *>> { |
| using NodeRef = const VPBlockBase *; |
| using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>; |
| |
| static NodeRef |
| getEntryNode(VPBlockRecursiveTraversalWrapper<const VPBlockBase *> N) { |
| return N.getEntry(); |
| } |
| |
| static inline ChildIteratorType child_begin(NodeRef N) { |
| return ChildIteratorType(N); |
| } |
| |
| static inline ChildIteratorType child_end(NodeRef N) { |
| return ChildIteratorType::end(N); |
| } |
| }; |
| |
| /// VPlan models a candidate for vectorization, encoding various decisions take |
| /// to produce efficient output IR, including which branches, basic-blocks and |
| /// output IR instructions to generate, and their cost. VPlan holds a |
| /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry |
| /// VPBlock. |
| class VPlan { |
| friend class VPlanPrinter; |
| friend class VPSlotTracker; |
| |
| /// Hold the single entry to the Hierarchical CFG of the VPlan. |
| VPBlockBase *Entry; |
| |
| /// Holds the VFs applicable to this VPlan. |
| SmallSetVector<ElementCount, 2> VFs; |
| |
| /// Holds the name of the VPlan, for printing. |
| std::string Name; |
| |
| /// Holds all the external definitions created for this VPlan. |
| // TODO: Introduce a specific representation for external definitions in |
| // VPlan. External definitions must be immutable and hold a pointer to its |
| // underlying IR that will be used to implement its structural comparison |
| // (operators '==' and '<'). |
| SetVector<VPValue *> VPExternalDefs; |
| |
| /// Represents the backedge taken count of the original loop, for folding |
| /// the tail. |
| VPValue *BackedgeTakenCount = nullptr; |
| |
| /// Holds a mapping between Values and their corresponding VPValue inside |
| /// VPlan. |
| Value2VPValueTy Value2VPValue; |
| |
| /// Contains all VPValues that been allocated by addVPValue directly and need |
| /// to be free when the plan's destructor is called. |
| SmallVector<VPValue *, 16> VPValuesToFree; |
| |
| /// Holds the VPLoopInfo analysis for this VPlan. |
| VPLoopInfo VPLInfo; |
| |
| /// Indicates whether it is safe use the Value2VPValue mapping or if the |
| /// mapping cannot be used any longer, because it is stale. |
| bool Value2VPValueEnabled = true; |
| |
| public: |
| VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) { |
| if (Entry) |
| Entry->setPlan(this); |
| } |
| |
| ~VPlan() { |
| if (Entry) { |
| VPValue DummyValue; |
| for (VPBlockBase *Block : depth_first(Entry)) |
| Block->dropAllReferences(&DummyValue); |
| |
| VPBlockBase::deleteCFG(Entry); |
| } |
| for (VPValue *VPV : VPValuesToFree) |
| delete VPV; |
| if (BackedgeTakenCount) |
| delete BackedgeTakenCount; |
| for (VPValue *Def : VPExternalDefs) |
| delete Def; |
| } |
| |
| /// Generate the IR code for this VPlan. |
| void execute(struct VPTransformState *State); |
| |
| VPBlockBase *getEntry() { return Entry; } |
| const VPBlockBase *getEntry() const { return Entry; } |
| |
| VPBlockBase *setEntry(VPBlockBase *Block) { |
| Entry = Block; |
| Block->setPlan(this); |
| return Entry; |
| } |
| |
| /// The backedge taken count of the original loop. |
| VPValue *getOrCreateBackedgeTakenCount() { |
| if (!BackedgeTakenCount) |
| BackedgeTakenCount = new VPValue(); |
| return BackedgeTakenCount; |
| } |
| |
| /// Mark the plan to indicate that using Value2VPValue is not safe any |
| /// longer, because it may be stale. |
| void disableValue2VPValue() { Value2VPValueEnabled = false; } |
| |
| void addVF(ElementCount VF) { VFs.insert(VF); } |
| |
| bool hasVF(ElementCount VF) { return VFs.count(VF); } |
| |
| const std::string &getName() const { return Name; } |
| |
| void setName(const Twine &newName) { Name = newName.str(); } |
| |
| /// Add \p VPVal to the pool of external definitions if it's not already |
| /// in the pool. |
| void addExternalDef(VPValue *VPVal) { VPExternalDefs.insert(VPVal); } |
| |
| void addVPValue(Value *V) { |
| assert(Value2VPValueEnabled && |
| "IR value to VPValue mapping may be out of date!"); |
| assert(V && "Trying to add a null Value to VPlan"); |
| assert(!Value2VPValue.count(V) && "Value already exists in VPlan"); |
| VPValue *VPV = new VPValue(V); |
| Value2VPValue[V] = VPV; |
| VPValuesToFree.push_back(VPV); |
| } |
| |
| void addVPValue(Value *V, VPValue *VPV) { |
| assert(Value2VPValueEnabled && "Value2VPValue mapping may be out of date!"); |
| assert(V && "Trying to add a null Value to VPlan"); |
| assert(!Value2VPValue.count(V) && "Value already exists in VPlan"); |
| Value2VPValue[V] = VPV; |
| } |
| |
| /// Returns the VPValue for \p V. \p OverrideAllowed can be used to disable |
| /// checking whether it is safe to query VPValues using IR Values. |
| VPValue *getVPValue(Value *V, bool OverrideAllowed = false) { |
| assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) && |
| "Value2VPValue mapping may be out of date!"); |
| assert(V && "Trying to get the VPValue of a null Value"); |
| assert(Value2VPValue.count(V) && "Value does not exist in VPlan"); |
| return Value2VPValue[V]; |
| } |
| |
| /// Gets the VPValue or adds a new one (if none exists yet) for \p V. \p |
| /// OverrideAllowed can be used to disable checking whether it is safe to |
| /// query VPValues using IR Values. |
| VPValue *getOrAddVPValue(Value *V, bool OverrideAllowed = false) { |
| assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) && |
| "Value2VPValue mapping may be out of date!"); |
| assert(V && "Trying to get or add the VPValue of a null Value"); |
| if (!Value2VPValue.count(V)) |
| addVPValue(V); |
| return getVPValue(V); |
| } |
| |
| void removeVPValueFor(Value *V) { |
| assert(Value2VPValueEnabled && |
| "IR value to VPValue mapping may be out of date!"); |
| Value2VPValue.erase(V); |
| } |
| |
| /// Return the VPLoopInfo analysis for this VPlan. |
| VPLoopInfo &getVPLoopInfo() { return VPLInfo; } |
| const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; } |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print this VPlan to \p O. |
| void print(raw_ostream &O) const; |
| |
| /// Print this VPlan in DOT format to \p O. |
| void printDOT(raw_ostream &O) const; |
| |
| /// Dump the plan to stderr (for debugging). |
| LLVM_DUMP_METHOD void dump() const; |
| #endif |
| |
| /// Returns a range mapping the values the range \p Operands to their |
| /// corresponding VPValues. |
| iterator_range<mapped_iterator<Use *, std::function<VPValue *(Value *)>>> |
| mapToVPValues(User::op_range Operands) { |
| std::function<VPValue *(Value *)> Fn = [this](Value *Op) { |
| return getOrAddVPValue(Op); |
| }; |
| return map_range(Operands, Fn); |
| } |
| |
| private: |
| /// Add to the given dominator tree the header block and every new basic block |
| /// that was created between it and the latch block, inclusive. |
| static void updateDominatorTree(DominatorTree *DT, BasicBlock *LoopLatchBB, |
| BasicBlock *LoopPreHeaderBB, |
| BasicBlock *LoopExitBB); |
| }; |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// VPlanPrinter prints a given VPlan to a given output stream. The printing is |
| /// indented and follows the dot format. |
| class VPlanPrinter { |
| raw_ostream &OS; |
| const VPlan &Plan; |
| unsigned Depth = 0; |
| unsigned TabWidth = 2; |
| std::string Indent; |
| unsigned BID = 0; |
| SmallDenseMap<const VPBlockBase *, unsigned> BlockID; |
| |
| VPSlotTracker SlotTracker; |
| |
| /// Handle indentation. |
| void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); } |
| |
| /// Print a given \p Block of the Plan. |
| void dumpBlock(const VPBlockBase *Block); |
| |
| /// Print the information related to the CFG edges going out of a given |
| /// \p Block, followed by printing the successor blocks themselves. |
| void dumpEdges(const VPBlockBase *Block); |
| |
| /// Print a given \p BasicBlock, including its VPRecipes, followed by printing |
| /// its successor blocks. |
| void dumpBasicBlock(const VPBasicBlock *BasicBlock); |
| |
| /// Print a given \p Region of the Plan. |
| void dumpRegion(const VPRegionBlock *Region); |
| |
| unsigned getOrCreateBID(const VPBlockBase *Block) { |
| return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++; |
| } |
| |
| Twine getOrCreateName(const VPBlockBase *Block); |
| |
| Twine getUID(const VPBlockBase *Block); |
| |
| /// Print the information related to a CFG edge between two VPBlockBases. |
| void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden, |
| const Twine &Label); |
| |
| public: |
| VPlanPrinter(raw_ostream &O, const VPlan &P) |
| : OS(O), Plan(P), SlotTracker(&P) {} |
| |
| LLVM_DUMP_METHOD void dump(); |
| }; |
| |
| struct VPlanIngredient { |
| const Value *V; |
| |
| VPlanIngredient(const Value *V) : V(V) {} |
| |
| void print(raw_ostream &O) const; |
| }; |
| |
| inline raw_ostream &operator<<(raw_ostream &OS, const VPlanIngredient &I) { |
| I.print(OS); |
| return OS; |
| } |
| |
| inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) { |
| Plan.print(OS); |
| return OS; |
| } |
| #endif |
| |
| //===----------------------------------------------------------------------===// |
| // VPlan Utilities |
| //===----------------------------------------------------------------------===// |
| |
| /// Class that provides utilities for VPBlockBases in VPlan. |
| class VPBlockUtils { |
| public: |
| VPBlockUtils() = delete; |
| |
| /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p |
| /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p |
| /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. If \p BlockPtr |
| /// has more than one successor, its conditional bit is propagated to \p |
| /// NewBlock. \p NewBlock must have neither successors nor predecessors. |
| static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) { |
| assert(NewBlock->getSuccessors().empty() && |
| "Can't insert new block with successors."); |
| // TODO: move successors from BlockPtr to NewBlock when this functionality |
| // is necessary. For now, setBlockSingleSuccessor will assert if BlockPtr |
| // already has successors. |
| BlockPtr->setOneSuccessor(NewBlock); |
| NewBlock->setPredecessors({BlockPtr}); |
| NewBlock->setParent(BlockPtr->getParent()); |
| } |
| |
| /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p |
| /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p |
| /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr |
| /// parent to \p IfTrue and \p IfFalse. \p Condition is set as the successor |
| /// selector. \p BlockPtr must have no successors and \p IfTrue and \p IfFalse |
| /// must have neither successors nor predecessors. |
| static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, |
| VPValue *Condition, VPBlockBase *BlockPtr) { |
| assert(IfTrue->getSuccessors().empty() && |
| "Can't insert IfTrue with successors."); |
| assert(IfFalse->getSuccessors().empty() && |
| "Can't insert IfFalse with successors."); |
| BlockPtr->setTwoSuccessors(IfTrue, IfFalse, Condition); |
| IfTrue->setPredecessors({BlockPtr}); |
| IfFalse->setPredecessors({BlockPtr}); |
| IfTrue->setParent(BlockPtr->getParent()); |
| IfFalse->setParent(BlockPtr->getParent()); |
| } |
| |
| /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to |
| /// the successors of \p From and \p From to the predecessors of \p To. Both |
| /// VPBlockBases must have the same parent, which can be null. Both |
| /// VPBlockBases can be already connected to other VPBlockBases. |
| static void connectBlocks(VPBlockBase *From, VPBlockBase *To) { |
| assert((From->getParent() == To->getParent()) && |
| "Can't connect two block with different parents"); |
| assert(From->getNumSuccessors() < 2 && |
| "Blocks can't have more than two successors."); |
| From->appendSuccessor(To); |
| To->appendPredecessor(From); |
| } |
| |
| /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To |
| /// from the successors of \p From and \p From from the predecessors of \p To. |
| static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) { |
| assert(To && "Successor to disconnect is null."); |
| From->removeSuccessor(To); |
| To->removePredecessor(From); |
| } |
| |
| /// Returns true if the edge \p FromBlock -> \p ToBlock is a back-edge. |
| static bool isBackEdge(const VPBlockBase *FromBlock, |
| const VPBlockBase *ToBlock, const VPLoopInfo *VPLI) { |
| assert(FromBlock->getParent() == ToBlock->getParent() && |
| FromBlock->getParent() && "Must be in same region"); |
| const VPLoop *FromLoop = VPLI->getLoopFor(FromBlock); |
| const VPLoop *ToLoop = VPLI->getLoopFor(ToBlock); |
| if (!FromLoop || !ToLoop || FromLoop != ToLoop) |
| return false; |
| |
| // A back-edge is a branch from the loop latch to its header. |
| return ToLoop->isLoopLatch(FromBlock) && ToBlock == ToLoop->getHeader(); |
| } |
| |
| /// Returns true if \p Block is a loop latch |
| static bool blockIsLoopLatch(const VPBlockBase *Block, |
| const VPLoopInfo *VPLInfo) { |
| if (const VPLoop *ParentVPL = VPLInfo->getLoopFor(Block)) |
| return ParentVPL->isLoopLatch(Block); |
| |
| return false; |
| } |
| |
| /// Count and return the number of succesors of \p PredBlock excluding any |
| /// backedges. |
| static unsigned countSuccessorsNoBE(VPBlockBase *PredBlock, |
| VPLoopInfo *VPLI) { |
| unsigned Count = 0; |
| for (VPBlockBase *SuccBlock : PredBlock->getSuccessors()) { |
| if (!VPBlockUtils::isBackEdge(PredBlock, SuccBlock, VPLI)) |
| Count++; |
| } |
| return Count; |
| } |
| |
| /// Return an iterator range over \p Range which only includes \p BlockTy |
| /// blocks. The accesses are casted to \p BlockTy. |
| template <typename BlockTy, typename T> |
| static auto blocksOnly(const T &Range) { |
| // Create BaseTy with correct const-ness based on BlockTy. |
| using BaseTy = |
| typename std::conditional<std::is_const<BlockTy>::value, |
| const VPBlockBase, VPBlockBase>::type; |
| |
| // We need to first create an iterator range over (const) BlocktTy & instead |
| // of (const) BlockTy * for filter_range to work properly. |
| auto Mapped = |
| map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; }); |
| auto Filter = make_filter_range( |
| Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); }); |
| return map_range(Filter, [](BaseTy &Block) -> BlockTy * { |
| return cast<BlockTy>(&Block); |
| }); |
| } |
| }; |
| |
| class VPInterleavedAccessInfo { |
| DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *> |
| InterleaveGroupMap; |
| |
| /// Type for mapping of instruction based interleave groups to VPInstruction |
| /// interleave groups |
| using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *, |
| InterleaveGroup<VPInstruction> *>; |
| |
| /// Recursively \p Region and populate VPlan based interleave groups based on |
| /// \p IAI. |
| void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New, |
| InterleavedAccessInfo &IAI); |
| /// Recursively traverse \p Block and populate VPlan based interleave groups |
| /// based on \p IAI. |
| void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New, |
| InterleavedAccessInfo &IAI); |
| |
| public: |
| VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI); |
| |
| ~VPInterleavedAccessInfo() { |
| SmallPtrSet<InterleaveGroup<VPInstruction> *, 4> DelSet; |
| // Avoid releasing a pointer twice. |
| for (auto &I : InterleaveGroupMap) |
| DelSet.insert(I.second); |
| for (auto *Ptr : DelSet) |
| delete Ptr; |
| } |
| |
| /// Get the interleave group that \p Instr belongs to. |
| /// |
| /// \returns nullptr if doesn't have such group. |
| InterleaveGroup<VPInstruction> * |
| getInterleaveGroup(VPInstruction *Instr) const { |
| return InterleaveGroupMap.lookup(Instr); |
| } |
| }; |
| |
| /// Class that maps (parts of) an existing VPlan to trees of combined |
| /// VPInstructions. |
| class VPlanSlp { |
| enum class OpMode { Failed, Load, Opcode }; |
| |
| /// A DenseMapInfo implementation for using SmallVector<VPValue *, 4> as |
| /// DenseMap keys. |
| struct BundleDenseMapInfo { |
| static SmallVector<VPValue *, 4> getEmptyKey() { |
| return {reinterpret_cast<VPValue *>(-1)}; |
| } |
| |
| static SmallVector<VPValue *, 4> getTombstoneKey() { |
| return {reinterpret_cast<VPValue *>(-2)}; |
| } |
| |
| static unsigned getHashValue(const SmallVector<VPValue *, 4> &V) { |
| return static_cast<unsigned>(hash_combine_range(V.begin(), V.end())); |
| } |
| |
| static bool isEqual(const SmallVector<VPValue *, 4> &LHS, |
| const SmallVector<VPValue *, 4> &RHS) { |
| return LHS == RHS; |
| } |
| }; |
| |
| /// Mapping of values in the original VPlan to a combined VPInstruction. |
| DenseMap<SmallVector<VPValue *, 4>, VPInstruction *, BundleDenseMapInfo> |
| BundleToCombined; |
| |
| VPInterleavedAccessInfo &IAI; |
| |
| /// Basic block to operate on. For now, only instructions in a single BB are |
| /// considered. |
| const VPBasicBlock &BB; |
| |
| /// Indicates whether we managed to combine all visited instructions or not. |
| bool CompletelySLP = true; |
| |
| /// Width of the widest combined bundle in bits. |
| unsigned WidestBundleBits = 0; |
| |
| using MultiNodeOpTy = |
| typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>; |
| |
| // Input operand bundles for the current multi node. Each multi node operand |
| // bundle contains values not matching the multi node's opcode. They will |
| // be reordered in reorderMultiNodeOps, once we completed building a |
| // multi node. |
| SmallVector<MultiNodeOpTy, 4> MultiNodeOps; |
| |
| /// Indicates whether we are building a multi node currently. |
| bool MultiNodeActive = false; |
| |
| /// Check if we can vectorize Operands together. |
| bool areVectorizable(ArrayRef<VPValue *> Operands) const; |
| |
| /// Add combined instruction \p New for the bundle \p Operands. |
| void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New); |
| |
| /// Indicate we hit a bundle we failed to combine. Returns nullptr for now. |
| VPInstruction *markFailed(); |
| |
| /// Reorder operands in the multi node to maximize sequential memory access |
| /// and commutative operations. |
| SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps(); |
| |
| /// Choose the best candidate to use for the lane after \p Last. The set of |
| /// candidates to choose from are values with an opcode matching \p Last's |
| /// or loads consecutive to \p Last. |
| std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last, |
| SmallPtrSetImpl<VPValue *> &Candidates, |
| VPInterleavedAccessInfo &IAI); |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| /// Print bundle \p Values to dbgs(). |
| void dumpBundle(ArrayRef<VPValue *> Values); |
| #endif |
| |
| public: |
| VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {} |
| |
| ~VPlanSlp() = default; |
| |
| /// Tries to build an SLP tree rooted at \p Operands and returns a |
| /// VPInstruction combining \p Operands, if they can be combined. |
| VPInstruction *buildGraph(ArrayRef<VPValue *> Operands); |
| |
| /// Return the width of the widest combined bundle in bits. |
| unsigned getWidestBundleBits() const { return WidestBundleBits; } |
| |
| /// Return true if all visited instruction can be combined. |
| bool isCompletelySLP() const { return CompletelySLP; } |
| }; |
| } // end namespace llvm |
| |
| #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H |