blob: 44b5e1df08399fc4ac4eac4f21a8018b451baf9a [file] [log] [blame]
//===- VPlan.cpp - Vectorizer Plan ----------------------------------------===//
//
// 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 is the LLVM vectorization plan. It represents a candidate for
/// vectorization, allowing to plan and optimize how to vectorize a given loop
/// before generating LLVM-IR.
/// The vectorizer uses vectorization plans to estimate the costs of potential
/// candidates and if profitable to execute the desired plan, generating vector
/// LLVM-IR code.
///
//===----------------------------------------------------------------------===//
#include "VPlan.h"
#include "VPlanDominatorTree.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GenericDomTreeConstruction.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include <cassert>
#include <iterator>
#include <string>
#include <vector>
using namespace llvm;
extern cl::opt<bool> EnableVPlanNativePath;
#define DEBUG_TYPE "vplan"
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
VPSlotTracker SlotTracker(
(Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
V.print(OS, SlotTracker);
return OS;
}
#endif
Value *VPLane::getAsRuntimeExpr(IRBuilder<> &Builder,
const ElementCount &VF) const {
switch (LaneKind) {
case VPLane::Kind::ScalableLast:
// Lane = RuntimeVF - VF.getKnownMinValue() + Lane
return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),
Builder.getInt32(VF.getKnownMinValue() - Lane));
case VPLane::Kind::First:
return Builder.getInt32(Lane);
}
llvm_unreachable("Unknown lane kind");
}
VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
: SubclassID(SC), UnderlyingVal(UV), Def(Def) {
if (Def)
Def->addDefinedValue(this);
}
VPValue::~VPValue() {
assert(Users.empty() && "trying to delete a VPValue with remaining users");
if (Def)
Def->removeDefinedValue(this);
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const {
if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def))
R->print(OS, "", SlotTracker);
else
printAsOperand(OS, SlotTracker);
}
void VPValue::dump() const {
const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def);
VPSlotTracker SlotTracker(
(Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
print(dbgs(), SlotTracker);
dbgs() << "\n";
}
void VPDef::dump() const {
const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);
VPSlotTracker SlotTracker(
(Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
print(dbgs(), "", SlotTracker);
dbgs() << "\n";
}
#endif
// Get the top-most entry block of \p Start. This is the entry block of the
// containing VPlan. This function is templated to support both const and non-const blocks
template <typename T> static T *getPlanEntry(T *Start) {
T *Next = Start;
T *Current = Start;
while ((Next = Next->getParent()))
Current = Next;
SmallSetVector<T *, 8> WorkList;
WorkList.insert(Current);
for (unsigned i = 0; i < WorkList.size(); i++) {
T *Current = WorkList[i];
if (Current->getNumPredecessors() == 0)
return Current;
auto &Predecessors = Current->getPredecessors();
WorkList.insert(Predecessors.begin(), Predecessors.end());
}
llvm_unreachable("VPlan without any entry node without predecessors");
}
VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
/// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
const VPBlockBase *Block = this;
while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
Block = Region->getEntry();
return cast<VPBasicBlock>(Block);
}
VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
VPBlockBase *Block = this;
while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
Block = Region->getEntry();
return cast<VPBasicBlock>(Block);
}
void VPBlockBase::setPlan(VPlan *ParentPlan) {
assert(ParentPlan->getEntry() == this &&
"Can only set plan on its entry block.");
Plan = ParentPlan;
}
/// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
const VPBasicBlock *VPBlockBase::getExitBasicBlock() const {
const VPBlockBase *Block = this;
while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
Block = Region->getExit();
return cast<VPBasicBlock>(Block);
}
VPBasicBlock *VPBlockBase::getExitBasicBlock() {
VPBlockBase *Block = this;
while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
Block = Region->getExit();
return cast<VPBasicBlock>(Block);
}
VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
if (!Successors.empty() || !Parent)
return this;
assert(Parent->getExit() == this &&
"Block w/o successors not the exit of its parent.");
return Parent->getEnclosingBlockWithSuccessors();
}
VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
if (!Predecessors.empty() || !Parent)
return this;
assert(Parent->getEntry() == this &&
"Block w/o predecessors not the entry of its parent.");
return Parent->getEnclosingBlockWithPredecessors();
}
VPValue *VPBlockBase::getCondBit() {
return CondBitUser.getSingleOperandOrNull();
}
const VPValue *VPBlockBase::getCondBit() const {
return CondBitUser.getSingleOperandOrNull();
}
void VPBlockBase::setCondBit(VPValue *CV) { CondBitUser.resetSingleOpUser(CV); }
VPValue *VPBlockBase::getPredicate() {
return PredicateUser.getSingleOperandOrNull();
}
const VPValue *VPBlockBase::getPredicate() const {
return PredicateUser.getSingleOperandOrNull();
}
void VPBlockBase::setPredicate(VPValue *CV) {
PredicateUser.resetSingleOpUser(CV);
}
void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
SmallVector<VPBlockBase *, 8> Blocks(depth_first(Entry));
for (VPBlockBase *Block : Blocks)
delete Block;
}
VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
iterator It = begin();
while (It != end() && It->isPhi())
It++;
return It;
}
Value *VPTransformState::get(VPValue *Def, const VPIteration &Instance) {
if (!Def->getDef())
return Def->getLiveInIRValue();
if (hasScalarValue(Def, Instance)) {
return Data
.PerPartScalars[Def][Instance.Part][Instance.Lane.mapToCacheIndex(VF)];
}
assert(hasVectorValue(Def, Instance.Part));
auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
if (!VecPart->getType()->isVectorTy()) {
assert(Instance.Lane.isFirstLane() && "cannot get lane > 0 for scalar");
return VecPart;
}
// TODO: Cache created scalar values.
Value *Lane = Instance.Lane.getAsRuntimeExpr(Builder, VF);
auto *Extract = Builder.CreateExtractElement(VecPart, Lane);
// set(Def, Extract, Instance);
return Extract;
}
BasicBlock *
VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
// BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
// Pred stands for Predessor. Prev stands for Previous - last visited/created.
BasicBlock *PrevBB = CFG.PrevBB;
BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
PrevBB->getParent(), CFG.LastBB);
LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
// Hook up the new basic block to its predecessors.
for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
auto &PredVPSuccessors = PredVPBB->getSuccessors();
BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
// In outer loop vectorization scenario, the predecessor BBlock may not yet
// be visited(backedge). Mark the VPBasicBlock for fixup at the end of
// vectorization. We do not encounter this case in inner loop vectorization
// as we start out by building a loop skeleton with the vector loop header
// and latch blocks. As a result, we never enter this function for the
// header block in the non VPlan-native path.
if (!PredBB) {
assert(EnableVPlanNativePath &&
"Unexpected null predecessor in non VPlan-native path");
CFG.VPBBsToFix.push_back(PredVPBB);
continue;
}
assert(PredBB && "Predecessor basic-block not found building successor.");
auto *PredBBTerminator = PredBB->getTerminator();
LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
if (isa<UnreachableInst>(PredBBTerminator)) {
assert(PredVPSuccessors.size() == 1 &&
"Predecessor ending w/o branch must have single successor.");
PredBBTerminator->eraseFromParent();
BranchInst::Create(NewBB, PredBB);
} else {
assert(PredVPSuccessors.size() == 2 &&
"Predecessor ending with branch must have two successors.");
unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
assert(!PredBBTerminator->getSuccessor(idx) &&
"Trying to reset an existing successor block.");
PredBBTerminator->setSuccessor(idx, NewBB);
}
}
return NewBB;
}
void VPBasicBlock::execute(VPTransformState *State) {
bool Replica = State->Instance && !State->Instance->isFirstIteration();
VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
VPBlockBase *SingleHPred = nullptr;
BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
// 1. Create an IR basic block, or reuse the last one if possible.
// The last IR basic block is reused, as an optimization, in three cases:
// A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
// B. when the current VPBB has a single (hierarchical) predecessor which
// is PrevVPBB and the latter has a single (hierarchical) successor; and
// C. when the current VPBB is an entry of a region replica - where PrevVPBB
// is the exit of this region from a previous instance, or the predecessor
// of this region.
if (PrevVPBB && /* A */
!((SingleHPred = getSingleHierarchicalPredecessor()) &&
SingleHPred->getExitBasicBlock() == PrevVPBB &&
PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
!(Replica && getPredecessors().empty())) { /* C */
NewBB = createEmptyBasicBlock(State->CFG);
State->Builder.SetInsertPoint(NewBB);
// Temporarily terminate with unreachable until CFG is rewired.
UnreachableInst *Terminator = State->Builder.CreateUnreachable();
State->Builder.SetInsertPoint(Terminator);
// Register NewBB in its loop. In innermost loops its the same for all BB's.
Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
L->addBasicBlockToLoop(NewBB, *State->LI);
State->CFG.PrevBB = NewBB;
}
// 2. Fill the IR basic block with IR instructions.
LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
<< " in BB:" << NewBB->getName() << '\n');
State->CFG.VPBB2IRBB[this] = NewBB;
State->CFG.PrevVPBB = this;
for (VPRecipeBase &Recipe : Recipes)
Recipe.execute(*State);
VPValue *CBV;
if (EnableVPlanNativePath && (CBV = getCondBit())) {
assert(CBV->getUnderlyingValue() &&
"Unexpected null underlying value for condition bit");
// Condition bit value in a VPBasicBlock is used as the branch selector. In
// the VPlan-native path case, since all branches are uniform we generate a
// branch instruction using the condition value from vector lane 0 and dummy
// successors. The successors are fixed later when the successor blocks are
// visited.
Value *NewCond = State->get(CBV, {0, 0});
// Replace the temporary unreachable terminator with the new conditional
// branch.
auto *CurrentTerminator = NewBB->getTerminator();
assert(isa<UnreachableInst>(CurrentTerminator) &&
"Expected to replace unreachable terminator with conditional "
"branch.");
auto *CondBr = BranchInst::Create(NewBB, nullptr, NewCond);
CondBr->setSuccessor(0, nullptr);
ReplaceInstWithInst(CurrentTerminator, CondBr);
}
LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
}
void VPBasicBlock::dropAllReferences(VPValue *NewValue) {
for (VPRecipeBase &R : Recipes) {
for (auto *Def : R.definedValues())
Def->replaceAllUsesWith(NewValue);
for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
R.setOperand(I, NewValue);
}
}
VPBasicBlock *VPBasicBlock::splitAt(iterator SplitAt) {
assert((SplitAt == end() || SplitAt->getParent() == this) &&
"can only split at a position in the same block");
SmallVector<VPBlockBase *, 2> Succs(getSuccessors().begin(),
getSuccessors().end());
// First, disconnect the current block from its successors.
for (VPBlockBase *Succ : Succs)
VPBlockUtils::disconnectBlocks(this, Succ);
// Create new empty block after the block to split.
auto *SplitBlock = new VPBasicBlock(getName() + ".split");
VPBlockUtils::insertBlockAfter(SplitBlock, this);
// Add successors for block to split to new block.
for (VPBlockBase *Succ : Succs)
VPBlockUtils::connectBlocks(SplitBlock, Succ);
// Finally, move the recipes starting at SplitAt to new block.
for (VPRecipeBase &ToMove :
make_early_inc_range(make_range(SplitAt, this->end())))
ToMove.moveBefore(*SplitBlock, SplitBlock->end());
return SplitBlock;
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
if (getSuccessors().empty()) {
O << Indent << "No successors\n";
} else {
O << Indent << "Successor(s): ";
ListSeparator LS;
for (auto *Succ : getSuccessors())
O << LS << Succ->getName();
O << '\n';
}
}
void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << getName() << ":\n";
if (const VPValue *Pred = getPredicate()) {
O << Indent << "BlockPredicate:";
Pred->printAsOperand(O, SlotTracker);
if (const auto *PredInst = dyn_cast<VPInstruction>(Pred))
O << " (" << PredInst->getParent()->getName() << ")";
O << '\n';
}
auto RecipeIndent = Indent + " ";
for (const VPRecipeBase &Recipe : *this) {
Recipe.print(O, RecipeIndent, SlotTracker);
O << '\n';
}
printSuccessors(O, Indent);
if (const VPValue *CBV = getCondBit()) {
O << Indent << "CondBit: ";
CBV->printAsOperand(O, SlotTracker);
if (const auto *CBI = dyn_cast<VPInstruction>(CBV))
O << " (" << CBI->getParent()->getName() << ")";
O << '\n';
}
}
#endif
void VPRegionBlock::dropAllReferences(VPValue *NewValue) {
for (VPBlockBase *Block : depth_first(Entry))
// Drop all references in VPBasicBlocks and replace all uses with
// DummyValue.
Block->dropAllReferences(NewValue);
}
void VPRegionBlock::execute(VPTransformState *State) {
ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
if (!isReplicator()) {
// Visit the VPBlocks connected to "this", starting from it.
for (VPBlockBase *Block : RPOT) {
if (EnableVPlanNativePath) {
// The inner loop vectorization path does not represent loop preheader
// and exit blocks as part of the VPlan. In the VPlan-native path, skip
// vectorizing loop preheader block. In future, we may replace this
// check with the check for loop preheader.
if (Block->getNumPredecessors() == 0)
continue;
// Skip vectorizing loop exit block. In future, we may replace this
// check with the check for loop exit.
if (Block->getNumSuccessors() == 0)
continue;
}
LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
Block->execute(State);
}
return;
}
assert(!State->Instance && "Replicating a Region with non-null instance.");
// Enter replicating mode.
State->Instance = VPIteration(0, 0);
for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
State->Instance->Part = Part;
assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
++Lane) {
State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
// Visit the VPBlocks connected to \p this, starting from it.
for (VPBlockBase *Block : RPOT) {
LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
Block->execute(State);
}
}
}
// Exit replicating mode.
State->Instance.reset();
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPRegionBlock::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
auto NewIndent = Indent + " ";
for (auto *BlockBase : depth_first(Entry)) {
O << '\n';
BlockBase->print(O, NewIndent, SlotTracker);
}
O << Indent << "}\n";
printSuccessors(O, Indent);
}
#endif
bool VPRecipeBase::mayWriteToMemory() const {
switch (getVPDefID()) {
case VPWidenMemoryInstructionSC: {
return cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
}
case VPReplicateSC:
case VPWidenCallSC:
return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
->mayWriteToMemory();
case VPBranchOnMaskSC:
return false;
case VPWidenIntOrFpInductionSC:
case VPWidenCanonicalIVSC:
case VPWidenPHISC:
case VPBlendSC:
case VPWidenSC:
case VPWidenGEPSC:
case VPReductionSC:
case VPWidenSelectSC: {
const Instruction *I =
dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
(void)I;
assert((!I || !I->mayWriteToMemory()) &&
"underlying instruction may write to memory");
return false;
}
default:
return true;
}
}
bool VPRecipeBase::mayReadFromMemory() const {
switch (getVPDefID()) {
case VPWidenMemoryInstructionSC: {
return !cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
}
case VPReplicateSC:
case VPWidenCallSC:
return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
->mayReadFromMemory();
case VPBranchOnMaskSC:
return false;
case VPWidenIntOrFpInductionSC:
case VPWidenCanonicalIVSC:
case VPWidenPHISC:
case VPBlendSC:
case VPWidenSC:
case VPWidenGEPSC:
case VPReductionSC:
case VPWidenSelectSC: {
const Instruction *I =
dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
(void)I;
assert((!I || !I->mayReadFromMemory()) &&
"underlying instruction may read from memory");
return false;
}
default:
return true;
}
}
bool VPRecipeBase::mayHaveSideEffects() const {
switch (getVPDefID()) {
case VPBranchOnMaskSC:
return false;
case VPWidenIntOrFpInductionSC:
case VPWidenCanonicalIVSC:
case VPWidenPHISC:
case VPBlendSC:
case VPWidenSC:
case VPWidenGEPSC:
case VPReductionSC:
case VPWidenSelectSC: {
const Instruction *I =
dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
(void)I;
assert((!I || !I->mayHaveSideEffects()) &&
"underlying instruction has side-effects");
return false;
}
case VPReplicateSC: {
auto *R = cast<VPReplicateRecipe>(this);
return R->getUnderlyingInstr()->mayHaveSideEffects();
}
default:
return true;
}
}
void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
assert(!Parent && "Recipe already in some VPBasicBlock");
assert(InsertPos->getParent() &&
"Insertion position not in any VPBasicBlock");
Parent = InsertPos->getParent();
Parent->getRecipeList().insert(InsertPos->getIterator(), this);
}
void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {
assert(!Parent && "Recipe already in some VPBasicBlock");
assert(InsertPos->getParent() &&
"Insertion position not in any VPBasicBlock");
Parent = InsertPos->getParent();
Parent->getRecipeList().insertAfter(InsertPos->getIterator(), this);
}
void VPRecipeBase::removeFromParent() {
assert(getParent() && "Recipe not in any VPBasicBlock");
getParent()->getRecipeList().remove(getIterator());
Parent = nullptr;
}
iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
assert(getParent() && "Recipe not in any VPBasicBlock");
return getParent()->getRecipeList().erase(getIterator());
}
void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
removeFromParent();
insertAfter(InsertPos);
}
void VPRecipeBase::moveBefore(VPBasicBlock &BB,
iplist<VPRecipeBase>::iterator I) {
assert(I == BB.end() || I->getParent() == &BB);
removeFromParent();
Parent = &BB;
BB.getRecipeList().insert(I, this);
}
void VPInstruction::generateInstruction(VPTransformState &State,
unsigned Part) {
IRBuilder<> &Builder = State.Builder;
if (Instruction::isBinaryOp(getOpcode())) {
Value *A = State.get(getOperand(0), Part);
Value *B = State.get(getOperand(1), Part);
Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
State.set(this, V, Part);
return;
}
switch (getOpcode()) {
case VPInstruction::Not: {
Value *A = State.get(getOperand(0), Part);
Value *V = Builder.CreateNot(A);
State.set(this, V, Part);
break;
}
case VPInstruction::ICmpULE: {
Value *IV = State.get(getOperand(0), Part);
Value *TC = State.get(getOperand(1), Part);
Value *V = Builder.CreateICmpULE(IV, TC);
State.set(this, V, Part);
break;
}
case Instruction::Select: {
Value *Cond = State.get(getOperand(0), Part);
Value *Op1 = State.get(getOperand(1), Part);
Value *Op2 = State.get(getOperand(2), Part);
Value *V = Builder.CreateSelect(Cond, Op1, Op2);
State.set(this, V, Part);
break;
}
case VPInstruction::ActiveLaneMask: {
// Get first lane of vector induction variable.
Value *VIVElem0 = State.get(getOperand(0), VPIteration(Part, 0));
// Get the original loop tripcount.
Value *ScalarTC = State.TripCount;
auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
auto *PredTy = FixedVectorType::get(Int1Ty, State.VF.getKnownMinValue());
Instruction *Call = Builder.CreateIntrinsic(
Intrinsic::get_active_lane_mask, {PredTy, ScalarTC->getType()},
{VIVElem0, ScalarTC}, nullptr, "active.lane.mask");
State.set(this, Call, Part);
break;
}
case VPInstruction::FirstOrderRecurrenceSplice: {
// Generate code to combine the previous and current values in vector v3.
//
// vector.ph:
// v_init = vector(..., ..., ..., a[-1])
// br vector.body
//
// vector.body
// i = phi [0, vector.ph], [i+4, vector.body]
// v1 = phi [v_init, vector.ph], [v2, vector.body]
// v2 = a[i, i+1, i+2, i+3];
// v3 = vector(v1(3), v2(0, 1, 2))
// For the first part, use the recurrence phi (v1), otherwise v2.
auto *V1 = State.get(getOperand(0), 0);
Value *PartMinus1 = Part == 0 ? V1 : State.get(getOperand(1), Part - 1);
if (!PartMinus1->getType()->isVectorTy()) {
State.set(this, PartMinus1, Part);
} else {
Value *V2 = State.get(getOperand(1), Part);
State.set(this, Builder.CreateVectorSplice(PartMinus1, V2, -1), Part);
}
break;
}
default:
llvm_unreachable("Unsupported opcode for instruction");
}
}
void VPInstruction::execute(VPTransformState &State) {
assert(!State.Instance && "VPInstruction executing an Instance");
IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
State.Builder.setFastMathFlags(FMF);
for (unsigned Part = 0; Part < State.UF; ++Part)
generateInstruction(State, Part);
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPInstruction::dump() const {
VPSlotTracker SlotTracker(getParent()->getPlan());
print(dbgs(), "", SlotTracker);
}
void VPInstruction::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "EMIT ";
if (hasResult()) {
printAsOperand(O, SlotTracker);
O << " = ";
}
switch (getOpcode()) {
case VPInstruction::Not:
O << "not";
break;
case VPInstruction::ICmpULE:
O << "icmp ule";
break;
case VPInstruction::SLPLoad:
O << "combined load";
break;
case VPInstruction::SLPStore:
O << "combined store";
break;
case VPInstruction::ActiveLaneMask:
O << "active lane mask";
break;
case VPInstruction::FirstOrderRecurrenceSplice:
O << "first-order splice";
break;
default:
O << Instruction::getOpcodeName(getOpcode());
}
O << FMF;
for (const VPValue *Operand : operands()) {
O << " ";
Operand->printAsOperand(O, SlotTracker);
}
}
#endif
void VPInstruction::setFastMathFlags(FastMathFlags FMFNew) {
// Make sure the VPInstruction is a floating-point operation.
assert((Opcode == Instruction::FAdd || Opcode == Instruction::FMul ||
Opcode == Instruction::FNeg || Opcode == Instruction::FSub ||
Opcode == Instruction::FDiv || Opcode == Instruction::FRem ||
Opcode == Instruction::FCmp) &&
"this op can't take fast-math flags");
FMF = FMFNew;
}
/// Generate the code inside the body of the vectorized loop. Assumes a single
/// LoopVectorBody basic-block was created for this. Introduce additional
/// basic-blocks as needed, and fill them all.
void VPlan::execute(VPTransformState *State) {
// -1. Check if the backedge taken count is needed, and if so build it.
if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
Value *TC = State->TripCount;
IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
"trip.count.minus.1");
auto VF = State->VF;
Value *VTCMO =
VF.isScalar() ? TCMO : Builder.CreateVectorSplat(VF, TCMO, "broadcast");
for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part)
State->set(BackedgeTakenCount, VTCMO, Part);
}
// 0. Set the reverse mapping from VPValues to Values for code generation.
for (auto &Entry : Value2VPValue)
State->VPValue2Value[Entry.second] = Entry.first;
BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
State->CFG.VectorPreHeader = VectorPreHeaderBB;
BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
// 1. Make room to generate basic-blocks inside loop body if needed.
BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
Loop *L = State->LI->getLoopFor(VectorHeaderBB);
L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
// Remove the edge between Header and Latch to allow other connections.
// Temporarily terminate with unreachable until CFG is rewired.
// Note: this asserts the generated code's assumption that
// getFirstInsertionPt() can be dereferenced into an Instruction.
VectorHeaderBB->getTerminator()->eraseFromParent();
State->Builder.SetInsertPoint(VectorHeaderBB);
UnreachableInst *Terminator = State->Builder.CreateUnreachable();
State->Builder.SetInsertPoint(Terminator);
// 2. Generate code in loop body.
State->CFG.PrevVPBB = nullptr;
State->CFG.PrevBB = VectorHeaderBB;
State->CFG.LastBB = VectorLatchBB;
for (VPBlockBase *Block : depth_first(Entry))
Block->execute(State);
// Fix the latch value of reduction and first-order recurrences phis in the
// vector loop.
VPBasicBlock *Header = Entry->getEntryBasicBlock();
for (VPRecipeBase &R : Header->phis()) {
auto *PhiR = dyn_cast<VPWidenPHIRecipe>(&R);
if (!PhiR || !(isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
isa<VPReductionPHIRecipe>(&R)))
continue;
// For first-order recurrences and in-order reduction phis, only a single
// part is generated, which provides the last part from the previous
// iteration. Otherwise all UF parts are generated.
bool SinglePartNeeded = isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
cast<VPReductionPHIRecipe>(&R)->isOrdered();
unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
Value *VecPhi = State->get(PhiR, Part);
Value *Val = State->get(PhiR->getBackedgeValue(),
SinglePartNeeded ? State->UF - 1 : Part);
cast<PHINode>(VecPhi)->addIncoming(Val, VectorLatchBB);
}
}
// Setup branch terminator successors for VPBBs in VPBBsToFix based on
// VPBB's successors.
for (auto VPBB : State->CFG.VPBBsToFix) {
assert(EnableVPlanNativePath &&
"Unexpected VPBBsToFix in non VPlan-native path");
BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
assert(BB && "Unexpected null basic block for VPBB");
unsigned Idx = 0;
auto *BBTerminator = BB->getTerminator();
for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
++Idx;
}
}
// 3. Merge the temporary latch created with the last basic-block filled.
BasicBlock *LastBB = State->CFG.PrevBB;
// Connect LastBB to VectorLatchBB to facilitate their merge.
assert((EnableVPlanNativePath ||
isa<UnreachableInst>(LastBB->getTerminator())) &&
"Expected InnerLoop VPlan CFG to terminate with unreachable");
assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
"Expected VPlan CFG to terminate with branch in NativePath");
LastBB->getTerminator()->eraseFromParent();
BranchInst::Create(VectorLatchBB, LastBB);
// Merge LastBB with Latch.
bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
(void)Merged;
assert(Merged && "Could not merge last basic block with latch.");
VectorLatchBB = LastBB;
// We do not attempt to preserve DT for outer loop vectorization currently.
if (!EnableVPlanNativePath)
updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB,
L->getExitBlock());
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD
void VPlan::print(raw_ostream &O) const {
VPSlotTracker SlotTracker(this);
O << "VPlan '" << Name << "' {";
if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
O << "\nLive-in ";
BackedgeTakenCount->printAsOperand(O, SlotTracker);
O << " = backedge-taken count\n";
}
for (const VPBlockBase *Block : depth_first(getEntry())) {
O << '\n';
Block->print(O, "", SlotTracker);
}
O << "}\n";
}
LLVM_DUMP_METHOD
void VPlan::printDOT(raw_ostream &O) const {
VPlanPrinter Printer(O, *this);
Printer.dump();
}
LLVM_DUMP_METHOD
void VPlan::dump() const { print(dbgs()); }
#endif
void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
BasicBlock *LoopLatchBB,
BasicBlock *LoopExitBB) {
BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
// The vector body may be more than a single basic-block by this point.
// Update the dominator tree information inside the vector body by propagating
// it from header to latch, expecting only triangular control-flow, if any.
BasicBlock *PostDomSucc = nullptr;
for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
// Get the list of successors of this block.
std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
assert(Succs.size() <= 2 &&
"Basic block in vector loop has more than 2 successors.");
PostDomSucc = Succs[0];
if (Succs.size() == 1) {
assert(PostDomSucc->getSinglePredecessor() &&
"PostDom successor has more than one predecessor.");
DT->addNewBlock(PostDomSucc, BB);
continue;
}
BasicBlock *InterimSucc = Succs[1];
if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
PostDomSucc = Succs[1];
InterimSucc = Succs[0];
}
assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
"One successor of a basic block does not lead to the other.");
assert(InterimSucc->getSinglePredecessor() &&
"Interim successor has more than one predecessor.");
assert(PostDomSucc->hasNPredecessors(2) &&
"PostDom successor has more than two predecessors.");
DT->addNewBlock(InterimSucc, BB);
DT->addNewBlock(PostDomSucc, BB);
}
// Latch block is a new dominator for the loop exit.
DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
assert(DT->verify(DominatorTree::VerificationLevel::Fast));
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
Twine(getOrCreateBID(Block));
}
Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
const std::string &Name = Block->getName();
if (!Name.empty())
return Name;
return "VPB" + Twine(getOrCreateBID(Block));
}
void VPlanPrinter::dump() {
Depth = 1;
bumpIndent(0);
OS << "digraph VPlan {\n";
OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
if (!Plan.getName().empty())
OS << "\\n" << DOT::EscapeString(Plan.getName());
if (Plan.BackedgeTakenCount) {
OS << ", where:\\n";
Plan.BackedgeTakenCount->print(OS, SlotTracker);
OS << " := BackedgeTakenCount";
}
OS << "\"]\n";
OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
OS << "edge [fontname=Courier, fontsize=30]\n";
OS << "compound=true\n";
for (const VPBlockBase *Block : depth_first(Plan.getEntry()))
dumpBlock(Block);
OS << "}\n";
}
void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
dumpBasicBlock(BasicBlock);
else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
dumpRegion(Region);
else
llvm_unreachable("Unsupported kind of VPBlock.");
}
void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
bool Hidden, const Twine &Label) {
// Due to "dot" we print an edge between two regions as an edge between the
// exit basic block and the entry basic of the respective regions.
const VPBlockBase *Tail = From->getExitBasicBlock();
const VPBlockBase *Head = To->getEntryBasicBlock();
OS << Indent << getUID(Tail) << " -> " << getUID(Head);
OS << " [ label=\"" << Label << '\"';
if (Tail != From)
OS << " ltail=" << getUID(From);
if (Head != To)
OS << " lhead=" << getUID(To);
if (Hidden)
OS << "; splines=none";
OS << "]\n";
}
void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
auto &Successors = Block->getSuccessors();
if (Successors.size() == 1)
drawEdge(Block, Successors.front(), false, "");
else if (Successors.size() == 2) {
drawEdge(Block, Successors.front(), false, "T");
drawEdge(Block, Successors.back(), false, "F");
} else {
unsigned SuccessorNumber = 0;
for (auto *Successor : Successors)
drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
}
}
void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
// Implement dot-formatted dump by performing plain-text dump into the
// temporary storage followed by some post-processing.
OS << Indent << getUID(BasicBlock) << " [label =\n";
bumpIndent(1);
std::string Str;
raw_string_ostream SS(Str);
// Use no indentation as we need to wrap the lines into quotes ourselves.
BasicBlock->print(SS, "", SlotTracker);
// We need to process each line of the output separately, so split
// single-string plain-text dump.
SmallVector<StringRef, 0> Lines;
StringRef(Str).rtrim('\n').split(Lines, "\n");
auto EmitLine = [&](StringRef Line, StringRef Suffix) {
OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
};
// Don't need the "+" after the last line.
for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
EmitLine(Line, " +\n");
EmitLine(Lines.back(), "\n");
bumpIndent(-1);
OS << Indent << "]\n";
dumpEdges(BasicBlock);
}
void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
OS << Indent << "subgraph " << getUID(Region) << " {\n";
bumpIndent(1);
OS << Indent << "fontname=Courier\n"
<< Indent << "label=\""
<< DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
<< DOT::EscapeString(Region->getName()) << "\"\n";
// Dump the blocks of the region.
assert(Region->getEntry() && "Region contains no inner blocks.");
for (const VPBlockBase *Block : depth_first(Region->getEntry()))
dumpBlock(Block);
bumpIndent(-1);
OS << Indent << "}\n";
dumpEdges(Region);
}
void VPlanIngredient::print(raw_ostream &O) const {
if (auto *Inst = dyn_cast<Instruction>(V)) {
if (!Inst->getType()->isVoidTy()) {
Inst->printAsOperand(O, false);
O << " = ";
}
O << Inst->getOpcodeName() << " ";
unsigned E = Inst->getNumOperands();
if (E > 0) {
Inst->getOperand(0)->printAsOperand(O, false);
for (unsigned I = 1; I < E; ++I)
Inst->getOperand(I)->printAsOperand(O << ", ", false);
}
} else // !Inst
V->printAsOperand(O, false);
}
void VPWidenCallRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "WIDEN-CALL ";
auto *CI = cast<CallInst>(getUnderlyingInstr());
if (CI->getType()->isVoidTy())
O << "void ";
else {
printAsOperand(O, SlotTracker);
O << " = ";
}
O << "call @" << CI->getCalledFunction()->getName() << "(";
printOperands(O, SlotTracker);
O << ")";
}
void VPWidenSelectRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "WIDEN-SELECT ";
printAsOperand(O, SlotTracker);
O << " = select ";
getOperand(0)->printAsOperand(O, SlotTracker);
O << ", ";
getOperand(1)->printAsOperand(O, SlotTracker);
O << ", ";
getOperand(2)->printAsOperand(O, SlotTracker);
O << (InvariantCond ? " (condition is loop invariant)" : "");
}
void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "WIDEN ";
printAsOperand(O, SlotTracker);
O << " = " << getUnderlyingInstr()->getOpcodeName() << " ";
printOperands(O, SlotTracker);
}
void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "WIDEN-INDUCTION";
if (getTruncInst()) {
O << "\\l\"";
O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
O << " +\n" << Indent << "\" ";
getVPValue(0)->printAsOperand(O, SlotTracker);
} else
O << " " << VPlanIngredient(IV);
}
void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "WIDEN-GEP ";
O << (IsPtrLoopInvariant ? "Inv" : "Var");
size_t IndicesNumber = IsIndexLoopInvariant.size();
for (size_t I = 0; I < IndicesNumber; ++I)
O << "[" << (IsIndexLoopInvariant[I] ? "Inv" : "Var") << "]";
O << " ";
printAsOperand(O, SlotTracker);
O << " = getelementptr ";
printOperands(O, SlotTracker);
}
void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "WIDEN-PHI ";
auto *OriginalPhi = cast<PHINode>(getUnderlyingValue());
// Unless all incoming values are modeled in VPlan print the original PHI
// directly.
// TODO: Remove once all VPWidenPHIRecipe instances keep all relevant incoming
// values as VPValues.
if (getNumOperands() != OriginalPhi->getNumOperands()) {
O << VPlanIngredient(OriginalPhi);
return;
}
printAsOperand(O, SlotTracker);
O << " = phi ";
printOperands(O, SlotTracker);
}
void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "BLEND ";
Phi->printAsOperand(O, false);
O << " =";
if (getNumIncomingValues() == 1) {
// Not a User of any mask: not really blending, this is a
// single-predecessor phi.
O << " ";
getIncomingValue(0)->printAsOperand(O, SlotTracker);
} else {
for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
O << " ";
getIncomingValue(I)->printAsOperand(O, SlotTracker);
O << "/";
getMask(I)->printAsOperand(O, SlotTracker);
}
}
}
void VPReductionRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "REDUCE ";
printAsOperand(O, SlotTracker);
O << " = ";
getChainOp()->printAsOperand(O, SlotTracker);
O << " +";
if (isa<FPMathOperator>(getUnderlyingInstr()))
O << getUnderlyingInstr()->getFastMathFlags();
O << " reduce." << Instruction::getOpcodeName(RdxDesc->getOpcode()) << " (";
getVecOp()->printAsOperand(O, SlotTracker);
if (getCondOp()) {
O << ", ";
getCondOp()->printAsOperand(O, SlotTracker);
}
O << ")";
}
void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << (IsUniform ? "CLONE " : "REPLICATE ");
if (!getUnderlyingInstr()->getType()->isVoidTy()) {
printAsOperand(O, SlotTracker);
O << " = ";
}
O << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode()) << " ";
printOperands(O, SlotTracker);
if (AlsoPack)
O << " (S->V)";
}
void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "PHI-PREDICATED-INSTRUCTION ";
printAsOperand(O, SlotTracker);
O << " = ";
printOperands(O, SlotTracker);
}
void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "WIDEN ";
if (!isStore()) {
getVPSingleValue()->printAsOperand(O, SlotTracker);
O << " = ";
}
O << Instruction::getOpcodeName(Ingredient.getOpcode()) << " ";
printOperands(O, SlotTracker);
}
#endif
void VPWidenCanonicalIVRecipe::execute(VPTransformState &State) {
Value *CanonicalIV = State.CanonicalIV;
Type *STy = CanonicalIV->getType();
IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
ElementCount VF = State.VF;
assert(!VF.isScalable() && "the code following assumes non scalables ECs");
Value *VStart = VF.isScalar()
? CanonicalIV
: Builder.CreateVectorSplat(VF.getKnownMinValue(),
CanonicalIV, "broadcast");
for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
SmallVector<Constant *, 8> Indices;
for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
Indices.push_back(
ConstantInt::get(STy, Part * VF.getKnownMinValue() + Lane));
// If VF == 1, there is only one iteration in the loop above, thus the
// element pushed back into Indices is ConstantInt::get(STy, Part)
Constant *VStep =
VF.isScalar() ? Indices.back() : ConstantVector::get(Indices);
// Add the consecutive indices to the vector value.
Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
State.set(this, CanonicalVectorIV, Part);
}
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPWidenCanonicalIVRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "EMIT ";
printAsOperand(O, SlotTracker);
O << " = WIDEN-CANONICAL-INDUCTION";
}
#endif
void VPFirstOrderRecurrencePHIRecipe::execute(VPTransformState &State) {
auto &Builder = State.Builder;
// Create a vector from the initial value.
auto *VectorInit = getStartValue()->getLiveInIRValue();
Type *VecTy = State.VF.isScalar()
? VectorInit->getType()
: VectorType::get(VectorInit->getType(), State.VF);
if (State.VF.isVector()) {
auto *IdxTy = Builder.getInt32Ty();
auto *One = ConstantInt::get(IdxTy, 1);
IRBuilder<>::InsertPointGuard Guard(Builder);
Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
auto *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);
auto *LastIdx = Builder.CreateSub(RuntimeVF, One);
VectorInit = Builder.CreateInsertElement(
PoisonValue::get(VecTy), VectorInit, LastIdx, "vector.recur.init");
}
// Create a phi node for the new recurrence.
PHINode *EntryPart = PHINode::Create(
VecTy, 2, "vector.recur", &*State.CFG.PrevBB->getFirstInsertionPt());
EntryPart->addIncoming(VectorInit, State.CFG.VectorPreHeader);
State.set(this, EntryPart, 0);
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPFirstOrderRecurrencePHIRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
printAsOperand(O, SlotTracker);
O << " = phi ";
printOperands(O, SlotTracker);
}
#endif
void VPReductionPHIRecipe::execute(VPTransformState &State) {
PHINode *PN = cast<PHINode>(getUnderlyingValue());
auto &Builder = State.Builder;
// In order to support recurrences we need to be able to vectorize Phi nodes.
// Phi nodes have cycles, so we need to vectorize them in two stages. This is
// stage #1: We create a new vector PHI node with no incoming edges. We'll use
// this value when we vectorize all of the instructions that use the PHI.
bool ScalarPHI = State.VF.isScalar() || IsInLoop;
Type *VecTy =
ScalarPHI ? PN->getType() : VectorType::get(PN->getType(), State.VF);
BasicBlock *HeaderBB = State.CFG.PrevBB;
assert(State.LI->getLoopFor(HeaderBB)->getHeader() == HeaderBB &&
"recipe must be in the vector loop header");
unsigned LastPartForNewPhi = isOrdered() ? 1 : State.UF;
for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
Value *EntryPart =
PHINode::Create(VecTy, 2, "vec.phi", &*HeaderBB->getFirstInsertionPt());
State.set(this, EntryPart, Part);
}
// Reductions do not have to start at zero. They can start with
// any loop invariant values.
VPValue *StartVPV = getStartValue();
Value *StartV = StartVPV->getLiveInIRValue();
Value *Iden = nullptr;
RecurKind RK = RdxDesc.getRecurrenceKind();
if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK) ||
RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK)) {
// MinMax reduction have the start value as their identify.
if (ScalarPHI) {
Iden = StartV;
} else {
IRBuilderBase::InsertPointGuard IPBuilder(Builder);
Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
StartV = Iden =
Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
}
} else {
Iden = RdxDesc.getRecurrenceIdentity(RK, VecTy->getScalarType(),
RdxDesc.getFastMathFlags());
if (!ScalarPHI) {
Iden = Builder.CreateVectorSplat(State.VF, Iden);
IRBuilderBase::InsertPointGuard IPBuilder(Builder);
Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
Constant *Zero = Builder.getInt32(0);
StartV = Builder.CreateInsertElement(Iden, StartV, Zero);
}
}
for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
Value *EntryPart = State.get(this, Part);
// Make sure to add the reduction start value only to the
// first unroll part.
Value *StartVal = (Part == 0) ? StartV : Iden;
cast<PHINode>(EntryPart)->addIncoming(StartVal, State.CFG.VectorPreHeader);
}
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPReductionPHIRecipe::print(raw_ostream &O, const Twine &Indent,
VPSlotTracker &SlotTracker) const {
O << Indent << "WIDEN-REDUCTION-PHI ";
printAsOperand(O, SlotTracker);
O << " = phi ";
printOperands(O, SlotTracker);
}
#endif
template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
void VPValue::replaceAllUsesWith(VPValue *New) {
for (unsigned J = 0; J < getNumUsers();) {
VPUser *User = Users[J];
unsigned NumUsers = getNumUsers();
for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
if (User->getOperand(I) == this)
User->setOperand(I, New);
// If a user got removed after updating the current user, the next user to
// update will be moved to the current position, so we only need to
// increment the index if the number of users did not change.
if (NumUsers == getNumUsers())
J++;
}
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const {
if (const Value *UV = getUnderlyingValue()) {
OS << "ir<";
UV->printAsOperand(OS, false);
OS << ">";
return;
}
unsigned Slot = Tracker.getSlot(this);
if (Slot == unsigned(-1))
OS << "<badref>";
else
OS << "vp<%" << Tracker.getSlot(this) << ">";
}
void VPUser::printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const {
interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
Op->printAsOperand(O, SlotTracker);
});
}
#endif
void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
Old2NewTy &Old2New,
InterleavedAccessInfo &IAI) {
ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
for (VPBlockBase *Base : RPOT) {
visitBlock(Base, Old2New, IAI);
}
}
void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
InterleavedAccessInfo &IAI) {
if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
for (VPRecipeBase &VPI : *VPBB) {
if (isa<VPWidenPHIRecipe>(&VPI))
continue;
assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
auto *VPInst = cast<VPInstruction>(&VPI);
auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
auto *IG = IAI.getInterleaveGroup(Inst);
if (!IG)
continue;
auto NewIGIter = Old2New.find(IG);
if (NewIGIter == Old2New.end())
Old2New[IG] = new InterleaveGroup<VPInstruction>(
IG->getFactor(), IG->isReverse(), IG->getAlign());
if (Inst == IG->getInsertPos())
Old2New[IG]->setInsertPos(VPInst);
InterleaveGroupMap[VPInst] = Old2New[IG];
InterleaveGroupMap[VPInst]->insertMember(
VPInst, IG->getIndex(Inst),
Align(IG->isReverse() ? (-1) * int(IG->getFactor())
: IG->getFactor()));
}
} else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
visitRegion(Region, Old2New, IAI);
else
llvm_unreachable("Unsupported kind of VPBlock.");
}
VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
InterleavedAccessInfo &IAI) {
Old2NewTy Old2New;
visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
}
void VPSlotTracker::assignSlot(const VPValue *V) {
assert(Slots.find(V) == Slots.end() && "VPValue already has a slot!");
Slots[V] = NextSlot++;
}
void VPSlotTracker::assignSlots(const VPlan &Plan) {
for (const VPValue *V : Plan.VPExternalDefs)
assignSlot(V);
if (Plan.BackedgeTakenCount)
assignSlot(Plan.BackedgeTakenCount);
ReversePostOrderTraversal<
VPBlockRecursiveTraversalWrapper<const VPBlockBase *>>
RPOT(VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(
Plan.getEntry()));
for (const VPBasicBlock *VPBB :
VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
for (const VPRecipeBase &Recipe : *VPBB)
for (VPValue *Def : Recipe.definedValues())
assignSlot(Def);
}