diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Vectorize/VPlan.h')
| -rw-r--r-- | contrib/llvm/lib/Transforms/Vectorize/VPlan.h | 1688 |
1 files changed, 0 insertions, 1688 deletions
diff --git a/contrib/llvm/lib/Transforms/Vectorize/VPlan.h b/contrib/llvm/lib/Transforms/Vectorize/VPlan.h deleted file mode 100644 index 8a06412ad590..000000000000 --- a/contrib/llvm/lib/Transforms/Vectorize/VPlan.h +++ /dev/null @@ -1,1688 +0,0 @@ -//===- 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/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 <algorithm> -#include <cassert> -#include <cstddef> -#include <map> -#include <string> - -namespace llvm { - -class LoopVectorizationLegality; -class LoopVectorizationCostModel; -class BasicBlock; -class DominatorTree; -class InnerLoopVectorizer; -template <class T> class InterleaveGroup; -class LoopInfo; -class raw_ostream; -class Value; -class VPBasicBlock; -class VPRegionBlock; -class VPlan; -class VPlanSlp; - -/// 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 unsigned Start; - - // Need not be a power of 2. If End <= Start range is empty. - unsigned End; -}; - -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. - -/// 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; - - /// in [0..VF) - unsigned Lane; -}; - -/// This is a helper struct for maintaining vectorization state. It's used for -/// mapping values from the original loop to their corresponding values in -/// the new loop. Two mappings are maintained: one for vectorized values and -/// one for scalarized values. Vectorized values are represented with UF -/// vector values in the new loop, and scalarized values are represented with -/// UF x VF scalar values in the new loop. UF and VF are the unroll and -/// vectorization factors, respectively. -/// -/// Entries can be added to either map with setVectorValue and setScalarValue, -/// which assert that an entry was not already added before. If an entry is to -/// replace an existing one, call resetVectorValue and resetScalarValue. This is -/// currently needed to modify the mapped values during "fix-up" operations that -/// occur once the first phase of widening is complete. These operations include -/// type truncation and the second phase of recurrence widening. -/// -/// Entries from either map can be retrieved using the getVectorValue and -/// getScalarValue functions, which assert that the desired value exists. -struct VectorizerValueMap { - friend struct VPTransformState; - -private: - /// The unroll factor. Each entry in the vector map contains UF vector values. - unsigned UF; - - /// The vectorization factor. Each entry in the scalar map contains UF x VF - /// scalar values. - unsigned VF; - - /// The vector and scalar map storage. We use std::map and not DenseMap - /// because insertions to DenseMap invalidate its iterators. - using VectorParts = SmallVector<Value *, 2>; - using ScalarParts = SmallVector<SmallVector<Value *, 4>, 2>; - std::map<Value *, VectorParts> VectorMapStorage; - std::map<Value *, ScalarParts> ScalarMapStorage; - -public: - /// Construct an empty map with the given unroll and vectorization factors. - VectorizerValueMap(unsigned UF, unsigned VF) : UF(UF), VF(VF) {} - - /// \return True if the map has any vector entry for \p Key. - bool hasAnyVectorValue(Value *Key) const { - return VectorMapStorage.count(Key); - } - - /// \return True if the map has a vector entry for \p Key and \p Part. - bool hasVectorValue(Value *Key, unsigned Part) const { - assert(Part < UF && "Queried Vector Part is too large."); - if (!hasAnyVectorValue(Key)) - return false; - const VectorParts &Entry = VectorMapStorage.find(Key)->second; - assert(Entry.size() == UF && "VectorParts has wrong dimensions."); - return Entry[Part] != nullptr; - } - - /// \return True if the map has any scalar entry for \p Key. - bool hasAnyScalarValue(Value *Key) const { - return ScalarMapStorage.count(Key); - } - - /// \return True if the map has a scalar entry for \p Key and \p Instance. - bool hasScalarValue(Value *Key, const VPIteration &Instance) const { - assert(Instance.Part < UF && "Queried Scalar Part is too large."); - assert(Instance.Lane < VF && "Queried Scalar Lane is too large."); - if (!hasAnyScalarValue(Key)) - return false; - const ScalarParts &Entry = ScalarMapStorage.find(Key)->second; - assert(Entry.size() == UF && "ScalarParts has wrong dimensions."); - assert(Entry[Instance.Part].size() == VF && - "ScalarParts has wrong dimensions."); - return Entry[Instance.Part][Instance.Lane] != nullptr; - } - - /// Retrieve the existing vector value that corresponds to \p Key and - /// \p Part. - Value *getVectorValue(Value *Key, unsigned Part) { - assert(hasVectorValue(Key, Part) && "Getting non-existent value."); - return VectorMapStorage[Key][Part]; - } - - /// Retrieve the existing scalar value that corresponds to \p Key and - /// \p Instance. - Value *getScalarValue(Value *Key, const VPIteration &Instance) { - assert(hasScalarValue(Key, Instance) && "Getting non-existent value."); - return ScalarMapStorage[Key][Instance.Part][Instance.Lane]; - } - - /// Set a vector value associated with \p Key and \p Part. Assumes such a - /// value is not already set. If it is, use resetVectorValue() instead. - void setVectorValue(Value *Key, unsigned Part, Value *Vector) { - assert(!hasVectorValue(Key, Part) && "Vector value already set for part"); - if (!VectorMapStorage.count(Key)) { - VectorParts Entry(UF); - VectorMapStorage[Key] = Entry; - } - VectorMapStorage[Key][Part] = Vector; - } - - /// Set a scalar value associated with \p Key and \p Instance. Assumes such a - /// value is not already set. - void setScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar) { - assert(!hasScalarValue(Key, Instance) && "Scalar value already set"); - if (!ScalarMapStorage.count(Key)) { - ScalarParts Entry(UF); - // TODO: Consider storing uniform values only per-part, as they occupy - // lane 0 only, keeping the other VF-1 redundant entries null. - for (unsigned Part = 0; Part < UF; ++Part) - Entry[Part].resize(VF, nullptr); - ScalarMapStorage[Key] = Entry; - } - ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar; - } - - /// Reset the vector value associated with \p Key for the given \p Part. - /// This function can be used to update values that have already been - /// vectorized. This is the case for "fix-up" operations including type - /// truncation and the second phase of recurrence vectorization. - void resetVectorValue(Value *Key, unsigned Part, Value *Vector) { - assert(hasVectorValue(Key, Part) && "Vector value not set for part"); - VectorMapStorage[Key][Part] = Vector; - } - - /// Reset the scalar value associated with \p Key for \p Part and \p Lane. - /// This function can be used to update values that have already been - /// scalarized. This is the case for "fix-up" operations including scalar phi - /// nodes for scalarized and predicated instructions. - void resetScalarValue(Value *Key, const VPIteration &Instance, - Value *Scalar) { - assert(hasScalarValue(Key, Instance) && - "Scalar value not set for part and lane"); - ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar; - } -}; - -/// This class is used to enable the VPlan to invoke a method of ILV. This is -/// needed until the method is refactored out of ILV and becomes reusable. -struct VPCallback { - virtual ~VPCallback() {} - virtual Value *getOrCreateVectorValues(Value *V, unsigned Part) = 0; -}; - -/// VPTransformState holds information passed down when "executing" a VPlan, -/// needed for generating the output IR. -struct VPTransformState { - VPTransformState(unsigned VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, - IRBuilder<> &Builder, VectorizerValueMap &ValueMap, - InnerLoopVectorizer *ILV, VPCallback &Callback) - : VF(VF), UF(UF), Instance(), LI(LI), DT(DT), Builder(Builder), - ValueMap(ValueMap), ILV(ILV), Callback(Callback) {} - - /// The chosen Vectorization and Unroll Factors of the loop being vectorized. - unsigned 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; - } 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) { - // If Values have been set for this Def return the one relevant for \p Part. - if (Data.PerPartOutput.count(Def)) - return Data.PerPartOutput[Def][Part]; - // Def is managed by ILV: bring the Values from ValueMap. - return Callback.getOrCreateVectorValues(VPValue2Value[Def], Part); - } - - /// 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; - } - - /// 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; - - /// 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; - - /// Hold a reference to the Value state information used when generating the - /// Values of the output IR. - VectorizerValueMap &ValueMap; - - /// Hold a reference to a mapping between VPValues in VPlan and original - /// Values they correspond to. - VPValue2ValueTy VPValue2Value; - - /// Hold the trip count of the scalar loop. - Value *TripCount = nullptr; - - /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods. - InnerLoopVectorizer *ILV; - - VPCallback &Callback; -}; - -/// 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; - -private: - 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, null for zero or single successor blocks. - VPValue *CondBit = nullptr; - - /// Current block predicate - null if the block does not need a predicate. - VPValue *Predicate = 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 = std::find(Predecessors.begin(), Predecessors.end(), 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 = std::find(Successors.begin(), Successors.end(), 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; } - - 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 CondBit; } - - const VPValue *getCondBit() const { return CondBit; } - - void setCondBit(VPValue *CV) { CondBit = CV; } - - VPValue *getPredicate() { return Predicate; } - - const VPValue *getPredicate() const { return Predicate; } - - void setPredicate(VPValue *Pred) { Predicate = 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!"); - CondBit = 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(); - CondBit = 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); - - void printAsOperand(raw_ostream &OS, bool PrintType) const { - OS << getName(); - } - - void print(raw_ostream &OS) const { - // TODO: Only printing VPBB name for now since we only have dot printing - // support for VPInstructions/Recipes. - printAsOperand(OS, false); - } - - /// 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; - } -}; - -/// VPRecipeBase is a base class modeling a sequence of one or more output IR -/// instructions. -class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> { - friend VPBasicBlock; - -private: - const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast). - - /// Each VPRecipe belongs to a single VPBasicBlock. - VPBasicBlock *Parent = nullptr; - -public: - /// An enumeration for keeping track of the concrete subclass of VPRecipeBase - /// that is actually instantiated. Values of this enumeration are kept in the - /// SubclassID field of the VPRecipeBase objects. They are used for concrete - /// type identification. - using VPRecipeTy = enum { - VPBlendSC, - VPBranchOnMaskSC, - VPInstructionSC, - VPInterleaveSC, - VPPredInstPHISC, - VPReplicateSC, - VPWidenIntOrFpInductionSC, - VPWidenMemoryInstructionSC, - VPWidenPHISC, - VPWidenSC, - }; - - VPRecipeBase(const unsigned char SC) : SubclassID(SC) {} - virtual ~VPRecipeBase() = default; - - /// \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 getVPRecipeID() const { return SubclassID; } - - /// \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; - - /// Each recipe prints itself. - virtual void print(raw_ostream &O, const Twine &Indent) const = 0; - - /// Insert an unlinked recipe into a basic block immediately before - /// the specified recipe. - void insertBefore(VPRecipeBase *InsertPos); - - /// 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(); -}; - -/// 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 VPUser, public VPRecipeBase { - friend class VPlanHCFGTransforms; - friend class VPlanSlp; - -public: - /// VPlan opcodes, extending LLVM IR with idiomatics instructions. - enum { - Not = Instruction::OtherOpsEnd + 1, - ICmpULE, - SLPLoad, - SLPStore, - }; - -private: - typedef unsigned char OpcodeTy; - OpcodeTy Opcode; - - /// Utility method serving execute(): generates a single instance of the - /// modeled instruction. - void generateInstruction(VPTransformState &State, unsigned Part); - -protected: - Instruction *getUnderlyingInstr() { - return cast_or_null<Instruction>(getUnderlyingValue()); - } - - void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); } - -public: - VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands) - : VPUser(VPValue::VPInstructionSC, Operands), - VPRecipeBase(VPRecipeBase::VPInstructionSC), 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::VPInstructionSC; - } - - 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 VPRecipeBase *R) { - return R->getVPRecipeID() == 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; - - /// Print the Recipe. - void print(raw_ostream &O, const Twine &Indent) const override; - - /// Print the VPInstruction. - void print(raw_ostream &O) const; - - /// 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; - } -}; - -/// VPWidenRecipe is a recipe for producing a copy of vector type for each -/// Instruction in its ingredients independently, in order. This recipe covers -/// most of the traditional vectorization cases where each ingredient transforms -/// into a vectorized version of itself. -class VPWidenRecipe : public VPRecipeBase { -private: - /// Hold the ingredients by pointing to their original BasicBlock location. - BasicBlock::iterator Begin; - BasicBlock::iterator End; - -public: - VPWidenRecipe(Instruction *I) : VPRecipeBase(VPWidenSC) { - End = I->getIterator(); - Begin = End++; - } - - ~VPWidenRecipe() override = default; - - /// Method to support type inquiry through isa, cast, and dyn_cast. - static inline bool classof(const VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPWidenSC; - } - - /// Produce widened copies of all Ingredients. - void execute(VPTransformState &State) override; - - /// Augment the recipe to include Instr, if it lies at its End. - bool appendInstruction(Instruction *Instr) { - if (End != Instr->getIterator()) - return false; - End++; - return true; - } - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override; -}; - -/// A recipe for handling phi nodes of integer and floating-point inductions, -/// producing their vector and scalar values. -class VPWidenIntOrFpInductionRecipe : public VPRecipeBase { -private: - PHINode *IV; - TruncInst *Trunc; - -public: - VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc = nullptr) - : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {} - ~VPWidenIntOrFpInductionRecipe() override = default; - - /// Method to support type inquiry through isa, cast, and dyn_cast. - static inline bool classof(const VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC; - } - - /// Generate the vectorized and scalarized versions of the phi node as - /// needed by their users. - void execute(VPTransformState &State) override; - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override; -}; - -/// A recipe for handling all phi nodes except for integer and FP inductions. -class VPWidenPHIRecipe : public VPRecipeBase { -private: - PHINode *Phi; - -public: - VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {} - ~VPWidenPHIRecipe() override = default; - - /// Method to support type inquiry through isa, cast, and dyn_cast. - static inline bool classof(const VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC; - } - - /// Generate the phi/select nodes. - void execute(VPTransformState &State) override; - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override; -}; - -/// A recipe for vectorizing a phi-node as a sequence of mask-based select -/// instructions. -class VPBlendRecipe : public VPRecipeBase { -private: - PHINode *Phi; - - /// The blend operation is a User of a mask, if not null. - std::unique_ptr<VPUser> User; - -public: - VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Masks) - : VPRecipeBase(VPBlendSC), Phi(Phi) { - assert((Phi->getNumIncomingValues() == 1 || - Phi->getNumIncomingValues() == Masks.size()) && - "Expected the same number of incoming values and masks"); - if (!Masks.empty()) - User.reset(new VPUser(Masks)); - } - - /// Method to support type inquiry through isa, cast, and dyn_cast. - static inline bool classof(const VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPBlendSC; - } - - /// Generate the phi/select nodes. - void execute(VPTransformState &State) override; - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override; -}; - -/// VPInterleaveRecipe is a recipe for transforming an interleave group of load -/// or stores into one wide load/store and shuffles. -class VPInterleaveRecipe : public VPRecipeBase { -private: - const InterleaveGroup<Instruction> *IG; - std::unique_ptr<VPUser> User; - -public: - VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Mask) - : VPRecipeBase(VPInterleaveSC), IG(IG) { - if (Mask) // Create a VPInstruction to register as a user of the mask. - User.reset(new VPUser({Mask})); - } - ~VPInterleaveRecipe() override = default; - - /// Method to support type inquiry through isa, cast, and dyn_cast. - static inline bool classof(const VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC; - } - - /// Generate the wide load or store, and shuffles. - void execute(VPTransformState &State) override; - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override; - - const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; } -}; - -/// 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 { -private: - /// The instruction being replicated. - Instruction *Ingredient; - - /// 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: - VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated = false) - : VPRecipeBase(VPReplicateSC), Ingredient(I), 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 VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC; - } - - /// 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; } - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override; -}; - -/// A recipe for generating conditional branches on the bits of a mask. -class VPBranchOnMaskRecipe : public VPRecipeBase { -private: - std::unique_ptr<VPUser> User; - -public: - VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) { - if (BlockInMask) // nullptr means all-one mask. - User.reset(new VPUser({BlockInMask})); - } - - /// Method to support type inquiry through isa, cast, and dyn_cast. - static inline bool classof(const VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC; - } - - /// Generate the extraction of the appropriate bit from the block mask and the - /// conditional branch. - void execute(VPTransformState &State) override; - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override { - O << " +\n" << Indent << "\"BRANCH-ON-MASK "; - if (User) - O << *User->getOperand(0); - else - O << " All-One"; - O << "\\l\""; - } -}; - -/// 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 { -private: - Instruction *PredInst; - -public: - /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi - /// nodes after merging back from a Branch-on-Mask. - VPPredInstPHIRecipe(Instruction *PredInst) - : VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {} - ~VPPredInstPHIRecipe() override = default; - - /// Method to support type inquiry through isa, cast, and dyn_cast. - static inline bool classof(const VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC; - } - - /// Generates phi nodes for live-outs as needed to retain SSA form. - void execute(VPTransformState &State) override; - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override; -}; - -/// A Recipe for widening load/store operations. -/// TODO: We currently execute only per-part unless a specific instance is -/// provided. -class VPWidenMemoryInstructionRecipe : public VPRecipeBase { -private: - Instruction &Instr; - std::unique_ptr<VPUser> User; - -public: - VPWidenMemoryInstructionRecipe(Instruction &Instr, VPValue *Mask) - : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Instr) { - if (Mask) // Create a VPInstruction to register as a user of the mask. - User.reset(new VPUser({Mask})); - } - - /// Method to support type inquiry through isa, cast, and dyn_cast. - static inline bool classof(const VPRecipeBase *V) { - return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC; - } - - /// Generate the wide load/store. - void execute(VPTransformState &State) override; - - /// Print the recipe. - void print(raw_ostream &O, const Twine &Indent) const override; -}; - -/// 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. -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 { Recipes.clear(); } - - /// 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; - -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 { -private: - /// 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) - 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; -}; - -/// 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; - -private: - /// Hold the single entry to the Hierarchical CFG of the VPlan. - VPBlockBase *Entry; - - /// Holds the VFs applicable to this VPlan. - SmallSet<unsigned, 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 '<'). - SmallPtrSet<VPValue *, 16> 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; - - /// Holds the VPLoopInfo analysis for this VPlan. - VPLoopInfo VPLInfo; - - /// Holds the condition bit values built during VPInstruction to VPRecipe transformation. - SmallVector<VPValue *, 4> VPCBVs; - -public: - VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {} - - ~VPlan() { - if (Entry) - VPBlockBase::deleteCFG(Entry); - for (auto &MapEntry : Value2VPValue) - if (MapEntry.second != BackedgeTakenCount) - delete MapEntry.second; - if (BackedgeTakenCount) - delete BackedgeTakenCount; // Delete once, if in Value2VPValue or not. - for (VPValue *Def : VPExternalDefs) - delete Def; - for (VPValue *CBV : VPCBVs) - delete CBV; - } - - /// 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) { return Entry = Block; } - - /// The backedge taken count of the original loop. - VPValue *getOrCreateBackedgeTakenCount() { - if (!BackedgeTakenCount) - BackedgeTakenCount = new VPValue(); - return BackedgeTakenCount; - } - - void addVF(unsigned VF) { VFs.insert(VF); } - - bool hasVF(unsigned 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); - } - - /// Add \p CBV to the vector of condition bit values. - void addCBV(VPValue *CBV) { - VPCBVs.push_back(CBV); - } - - void addVPValue(Value *V) { - assert(V && "Trying to add a null Value to VPlan"); - assert(!Value2VPValue.count(V) && "Value already exists in VPlan"); - Value2VPValue[V] = new VPValue(); - } - - VPValue *getVPValue(Value *V) { - assert(V && "Trying to get the VPValue of a null Value"); - assert(Value2VPValue.count(V) && "Value does not exist in VPlan"); - return Value2VPValue[V]; - } - - /// Return the VPLoopInfo analysis for this VPlan. - VPLoopInfo &getVPLoopInfo() { return VPLInfo; } - const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; } - -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 *LoopPreHeaderBB, - BasicBlock *LoopLatchBB); -}; - -/// VPlanPrinter prints a given VPlan to a given output stream. The printing is -/// indented and follows the dot format. -class VPlanPrinter { - friend inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan); - friend inline raw_ostream &operator<<(raw_ostream &OS, - const struct VPlanIngredient &I); - -private: - raw_ostream &OS; - VPlan &Plan; - unsigned Depth; - unsigned TabWidth = 2; - std::string Indent; - unsigned BID = 0; - SmallDenseMap<const VPBlockBase *, unsigned> BlockID; - - VPlanPrinter(raw_ostream &O, VPlan &P) : OS(O), Plan(P) {} - - /// 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++; - } - - const Twine getOrCreateName(const VPBlockBase *Block); - - const 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); - - void dump(); - - static void printAsIngredient(raw_ostream &O, Value *V); -}; - -struct VPlanIngredient { - Value *V; - - VPlanIngredient(Value *V) : V(V) {} -}; - -inline raw_ostream &operator<<(raw_ostream &OS, const VPlanIngredient &I) { - VPlanPrinter::printAsIngredient(OS, I.V); - return OS; -} - -inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan) { - VPlanPrinter Printer(OS, Plan); - Printer.dump(); - return OS; -} - -//===----------------------------------------------------------------------===// -// 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); - } -}; - -//===----------------------------------------------------------------------===// -// 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; - } -}; - -class VPInterleavedAccessInfo { -private: - 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 { - if (InterleaveGroupMap.count(Instr)) - return InterleaveGroupMap.find(Instr)->second; - return nullptr; - } -}; - -/// Class that maps (parts of) an existing VPlan to trees of combined -/// VPInstructions. -class VPlanSlp { -private: - 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); - - /// Print bundle \p Values to dbgs(). - void dumpBundle(ArrayRef<VPValue *> Values); - -public: - VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {} - - ~VPlanSlp() { - for (auto &KV : BundleToCombined) - delete KV.second; - } - - /// 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 |