mirror of
https://github.com/RPCS3/llvm-mirror.git
synced 2024-11-22 02:33:06 +01:00
ca0aa2b075
This reverts the revert commit b1777b04dc4b1a9fee0e7effa7e177892ab32ef0. The patch originally got reverted due to a crash: https://bugs.chromium.org/p/chromium/issues/detail?id=1232798#c2 The underlying issue was that we were not using the stored values from the modified memory recipes, but the out-of-date values directly from the IR (accessed via the VPlan). This should be fixed in d995d6376. A reduced version of the reproducer has been added in 93664503be6b.
2538 lines
91 KiB
C++
2538 lines
91 KiB
C++
//===- 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 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;
|
|
};
|
|
|
|
/// 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;
|
|
|
|
/// 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, ArrayRef<VPInstruction *> Operands)
|
|
: VPRecipeBase(VPRecipeBase::VPInstructionSC, {}),
|
|
VPValue(VPValue::VPVInstructionSC, nullptr, this), Opcode(Opcode) {
|
|
for (auto *I : Operands)
|
|
addOperand(I->getVPSingleValue());
|
|
}
|
|
|
|
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;
|
|
}
|
|
}
|
|
};
|
|
|
|
/// 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, getNumOperands() - (HasMask ? 2 : 1));
|
|
}
|
|
|
|
/// 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; }
|
|
};
|
|
|
|
/// 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 {
|
|
Instruction &Ingredient;
|
|
|
|
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)
|
|
: VPRecipeBase(VPWidenMemoryInstructionSC, {Addr}), Ingredient(Load) {
|
|
new VPValue(VPValue::VPVMemoryInstructionSC, &Load, this);
|
|
setMask(Mask);
|
|
}
|
|
|
|
VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr,
|
|
VPValue *StoredValue, VPValue *Mask)
|
|
: VPRecipeBase(VPWidenMemoryInstructionSC, {Addr, StoredValue}),
|
|
Ingredient(Store) {
|
|
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.
|
|
}
|
|
|
|
/// 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:
|
|
VPWidenCanonicalIVRecipe() : VPRecipeBase(VPWidenCanonicalIVSC, {}) {
|
|
new VPValue(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;
|
|
|
|
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;
|
|
}
|
|
|
|
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(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(V && "Trying to add a null Value to VPlan");
|
|
assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
|
|
Value2VPValue[V] = VPV;
|
|
}
|
|
|
|
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];
|
|
}
|
|
|
|
VPValue *getOrAddVPValue(Value *V) {
|
|
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) { 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++;
|
|
}
|
|
|
|
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);
|
|
|
|
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
|