1773 lines · cpp
1//===- VPlan.cpp - Vectorizer Plan ----------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This is the LLVM vectorization plan. It represents a candidate for11/// vectorization, allowing to plan and optimize how to vectorize a given loop12/// before generating LLVM-IR.13/// The vectorizer uses vectorization plans to estimate the costs of potential14/// candidates and if profitable to execute the desired plan, generating vector15/// LLVM-IR code.16///17//===----------------------------------------------------------------------===//18 19#include "VPlan.h"20#include "LoopVectorizationPlanner.h"21#include "VPlanCFG.h"22#include "VPlanDominatorTree.h"23#include "VPlanHelpers.h"24#include "VPlanPatternMatch.h"25#include "VPlanTransforms.h"26#include "VPlanUtils.h"27#include "llvm/ADT/PostOrderIterator.h"28#include "llvm/ADT/STLExtras.h"29#include "llvm/ADT/SmallVector.h"30#include "llvm/ADT/StringExtras.h"31#include "llvm/ADT/Twine.h"32#include "llvm/Analysis/DomTreeUpdater.h"33#include "llvm/Analysis/LoopInfo.h"34#include "llvm/IR/BasicBlock.h"35#include "llvm/IR/CFG.h"36#include "llvm/IR/IRBuilder.h"37#include "llvm/IR/Instruction.h"38#include "llvm/IR/Instructions.h"39#include "llvm/IR/Type.h"40#include "llvm/IR/Value.h"41#include "llvm/Support/Casting.h"42#include "llvm/Support/CommandLine.h"43#include "llvm/Support/Debug.h"44#include "llvm/Support/GraphWriter.h"45#include "llvm/Support/raw_ostream.h"46#include "llvm/Transforms/Utils/BasicBlockUtils.h"47#include "llvm/Transforms/Utils/LoopVersioning.h"48#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"49#include <cassert>50#include <string>51 52using namespace llvm;53using namespace llvm::VPlanPatternMatch;54 55/// @{56/// Metadata attribute names57const char LLVMLoopVectorizeFollowupAll[] = "llvm.loop.vectorize.followup_all";58const char LLVMLoopVectorizeFollowupVectorized[] =59 "llvm.loop.vectorize.followup_vectorized";60const char LLVMLoopVectorizeFollowupEpilogue[] =61 "llvm.loop.vectorize.followup_epilogue";62/// @}63 64extern cl::opt<unsigned> ForceTargetInstructionCost;65 66static cl::opt<bool> PrintVPlansInDotFormat(67 "vplan-print-in-dot-format", cl::Hidden,68 cl::desc("Use dot format instead of plain text when dumping VPlans"));69 70#define DEBUG_TYPE "loop-vectorize"71 72#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)73raw_ostream &llvm::operator<<(raw_ostream &OS, const VPRecipeBase &R) {74 const VPBasicBlock *Parent = R.getParent();75 VPSlotTracker SlotTracker(Parent ? Parent->getPlan() : nullptr);76 R.print(OS, "", SlotTracker);77 return OS;78}79#endif80 81Value *VPLane::getAsRuntimeExpr(IRBuilderBase &Builder,82 const ElementCount &VF) const {83 switch (LaneKind) {84 case VPLane::Kind::ScalableLast:85 // Lane = RuntimeVF - VF.getKnownMinValue() + Lane86 return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),87 Builder.getInt32(VF.getKnownMinValue() - Lane));88 case VPLane::Kind::First:89 return Builder.getInt32(Lane);90 }91 llvm_unreachable("Unknown lane kind");92}93 94VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)95 : SubclassID(SC), UnderlyingVal(UV), Def(Def) {96 if (Def)97 Def->addDefinedValue(this);98}99 100VPValue::~VPValue() {101 assert(Users.empty() && "trying to delete a VPValue with remaining users");102 if (VPDef *Def = getDefiningRecipe())103 Def->removeDefinedValue(this);104}105 106#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)107void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const {108 if (const VPRecipeBase *R = getDefiningRecipe())109 R->print(OS, "", SlotTracker);110 else111 printAsOperand(OS, SlotTracker);112}113 114void VPValue::dump() const {115 const VPRecipeBase *Instr = getDefiningRecipe();116 VPSlotTracker SlotTracker(117 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);118 print(dbgs(), SlotTracker);119 dbgs() << "\n";120}121 122void VPDef::dump() const {123 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);124 VPSlotTracker SlotTracker(125 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);126 print(dbgs(), "", SlotTracker);127 dbgs() << "\n";128}129#endif130 131VPRecipeBase *VPValue::getDefiningRecipe() {132 return cast_or_null<VPRecipeBase>(Def);133}134 135const VPRecipeBase *VPValue::getDefiningRecipe() const {136 return cast_or_null<VPRecipeBase>(Def);137}138 139// Get the top-most entry block of \p Start. This is the entry block of the140// containing VPlan. This function is templated to support both const and non-const blocks141template <typename T> static T *getPlanEntry(T *Start) {142 T *Next = Start;143 T *Current = Start;144 while ((Next = Next->getParent()))145 Current = Next;146 147 SmallSetVector<T *, 8> WorkList;148 WorkList.insert(Current);149 150 for (unsigned i = 0; i < WorkList.size(); i++) {151 T *Current = WorkList[i];152 if (!Current->hasPredecessors())153 return Current;154 auto &Predecessors = Current->getPredecessors();155 WorkList.insert_range(Predecessors);156 }157 158 llvm_unreachable("VPlan without any entry node without predecessors");159}160 161VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }162 163const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }164 165/// \return the VPBasicBlock that is the entry of Block, possibly indirectly.166const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {167 const VPBlockBase *Block = this;168 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))169 Block = Region->getEntry();170 return cast<VPBasicBlock>(Block);171}172 173VPBasicBlock *VPBlockBase::getEntryBasicBlock() {174 VPBlockBase *Block = this;175 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))176 Block = Region->getEntry();177 return cast<VPBasicBlock>(Block);178}179 180void VPBlockBase::setPlan(VPlan *ParentPlan) {181 assert(ParentPlan->getEntry() == this && "Can only set plan on its entry.");182 Plan = ParentPlan;183}184 185/// \return the VPBasicBlock that is the exit of Block, possibly indirectly.186const VPBasicBlock *VPBlockBase::getExitingBasicBlock() const {187 const VPBlockBase *Block = this;188 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))189 Block = Region->getExiting();190 return cast<VPBasicBlock>(Block);191}192 193VPBasicBlock *VPBlockBase::getExitingBasicBlock() {194 VPBlockBase *Block = this;195 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))196 Block = Region->getExiting();197 return cast<VPBasicBlock>(Block);198}199 200VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {201 if (!Successors.empty() || !Parent)202 return this;203 assert(Parent->getExiting() == this &&204 "Block w/o successors not the exiting block of its parent.");205 return Parent->getEnclosingBlockWithSuccessors();206}207 208VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {209 if (!Predecessors.empty() || !Parent)210 return this;211 assert(Parent->getEntry() == this &&212 "Block w/o predecessors not the entry of its parent.");213 return Parent->getEnclosingBlockWithPredecessors();214}215 216VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {217 iterator It = begin();218 while (It != end() && It->isPhi())219 It++;220 return It;221}222 223VPTransformState::VPTransformState(const TargetTransformInfo *TTI,224 ElementCount VF, LoopInfo *LI,225 DominatorTree *DT, AssumptionCache *AC,226 IRBuilderBase &Builder, VPlan *Plan,227 Loop *CurrentParentLoop, Type *CanonicalIVTy)228 : TTI(TTI), VF(VF), CFG(DT), LI(LI), AC(AC), Builder(Builder), Plan(Plan),229 CurrentParentLoop(CurrentParentLoop), TypeAnalysis(*Plan), VPDT(*Plan) {}230 231Value *VPTransformState::get(const VPValue *Def, const VPLane &Lane) {232 if (Def->isLiveIn())233 return Def->getLiveInIRValue();234 235 if (hasScalarValue(Def, Lane))236 return Data.VPV2Scalars[Def][Lane.mapToCacheIndex(VF)];237 238 if (!Lane.isFirstLane() && vputils::isSingleScalar(Def) &&239 hasScalarValue(Def, VPLane::getFirstLane())) {240 return Data.VPV2Scalars[Def][0];241 }242 243 // Look through BuildVector to avoid redundant extracts.244 // TODO: Remove once replicate regions are unrolled explicitly.245 if (Lane.getKind() == VPLane::Kind::First && match(Def, m_BuildVector())) {246 auto *BuildVector = cast<VPInstruction>(Def);247 return get(BuildVector->getOperand(Lane.getKnownLane()), true);248 }249 250 assert(hasVectorValue(Def));251 auto *VecPart = Data.VPV2Vector[Def];252 if (!VecPart->getType()->isVectorTy()) {253 assert(Lane.isFirstLane() && "cannot get lane > 0 for scalar");254 return VecPart;255 }256 // TODO: Cache created scalar values.257 Value *LaneV = Lane.getAsRuntimeExpr(Builder, VF);258 auto *Extract = Builder.CreateExtractElement(VecPart, LaneV);259 // set(Def, Extract, Instance);260 return Extract;261}262 263Value *VPTransformState::get(const VPValue *Def, bool NeedsScalar) {264 if (NeedsScalar) {265 assert((VF.isScalar() || Def->isLiveIn() || hasVectorValue(Def) ||266 !vputils::onlyFirstLaneUsed(Def) ||267 (hasScalarValue(Def, VPLane(0)) &&268 Data.VPV2Scalars[Def].size() == 1)) &&269 "Trying to access a single scalar per part but has multiple scalars "270 "per part.");271 return get(Def, VPLane(0));272 }273 274 // If Values have been set for this Def return the one relevant for \p Part.275 if (hasVectorValue(Def))276 return Data.VPV2Vector[Def];277 278 auto GetBroadcastInstrs = [this](Value *V) {279 if (VF.isScalar())280 return V;281 // Broadcast the scalar into all locations in the vector.282 Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");283 return Shuf;284 };285 286 if (!hasScalarValue(Def, {0})) {287 assert(Def->isLiveIn() && "expected a live-in");288 Value *IRV = Def->getLiveInIRValue();289 Value *B = GetBroadcastInstrs(IRV);290 set(Def, B);291 return B;292 }293 294 Value *ScalarValue = get(Def, VPLane(0));295 // If we aren't vectorizing, we can just copy the scalar map values over296 // to the vector map.297 if (VF.isScalar()) {298 set(Def, ScalarValue);299 return ScalarValue;300 }301 302 bool IsSingleScalar = vputils::isSingleScalar(Def);303 VPLane LastLane(IsSingleScalar ? 0 : VF.getFixedValue() - 1);304 305 // We need to construct the vector value for a single-scalar value by306 // broadcasting the scalar to all lanes.307 // TODO: Replace by introducing Broadcast VPInstructions.308 assert(IsSingleScalar && "must be a single-scalar at this point");309 // Set the insert point after the last scalarized instruction or after the310 // last PHI, if LastInst is a PHI. This ensures the insertelement sequence311 // will directly follow the scalar definitions.312 auto OldIP = Builder.saveIP();313 auto *LastInst = cast<Instruction>(get(Def, LastLane));314 auto NewIP = isa<PHINode>(LastInst)315 ? LastInst->getParent()->getFirstNonPHIIt()316 : std::next(BasicBlock::iterator(LastInst));317 Builder.SetInsertPoint(&*NewIP);318 Value *VectorValue = GetBroadcastInstrs(ScalarValue);319 set(Def, VectorValue);320 Builder.restoreIP(OldIP);321 return VectorValue;322}323 324void VPTransformState::setDebugLocFrom(DebugLoc DL) {325 const DILocation *DIL = DL;326 // When a FSDiscriminator is enabled, we don't need to add the multiply327 // factors to the discriminators.328 if (DIL &&329 Builder.GetInsertBlock()330 ->getParent()331 ->shouldEmitDebugInfoForProfiling() &&332 !EnableFSDiscriminator) {333 // FIXME: For scalable vectors, assume vscale=1.334 unsigned UF = Plan->getUF();335 auto NewDIL =336 DIL->cloneByMultiplyingDuplicationFactor(UF * VF.getKnownMinValue());337 if (NewDIL)338 Builder.SetCurrentDebugLocation(*NewDIL);339 else340 LLVM_DEBUG(dbgs() << "Failed to create new discriminator: "341 << DIL->getFilename() << " Line: " << DIL->getLine());342 } else343 Builder.SetCurrentDebugLocation(DL);344}345 346Value *VPTransformState::packScalarIntoVectorizedValue(const VPValue *Def,347 Value *WideValue,348 const VPLane &Lane) {349 Value *ScalarInst = get(Def, Lane);350 Value *LaneExpr = Lane.getAsRuntimeExpr(Builder, VF);351 if (auto *StructTy = dyn_cast<StructType>(WideValue->getType())) {352 // We must handle each element of a vectorized struct type.353 for (unsigned I = 0, E = StructTy->getNumElements(); I != E; I++) {354 Value *ScalarValue = Builder.CreateExtractValue(ScalarInst, I);355 Value *VectorValue = Builder.CreateExtractValue(WideValue, I);356 VectorValue =357 Builder.CreateInsertElement(VectorValue, ScalarValue, LaneExpr);358 WideValue = Builder.CreateInsertValue(WideValue, VectorValue, I);359 }360 } else {361 WideValue = Builder.CreateInsertElement(WideValue, ScalarInst, LaneExpr);362 }363 return WideValue;364}365 366BasicBlock *VPBasicBlock::createEmptyBasicBlock(VPTransformState &State) {367 auto &CFG = State.CFG;368 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.369 // Pred stands for Predessor. Prev stands for Previous - last visited/created.370 BasicBlock *PrevBB = CFG.PrevBB;371 BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),372 PrevBB->getParent(), CFG.ExitBB);373 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');374 375 return NewBB;376}377 378void VPBasicBlock::connectToPredecessors(VPTransformState &State) {379 auto &CFG = State.CFG;380 BasicBlock *NewBB = CFG.VPBB2IRBB[this];381 382 // Register NewBB in its loop. In innermost loops its the same for all383 // BB's.384 Loop *ParentLoop = State.CurrentParentLoop;385 // If this block has a sole successor that is an exit block or is an exit386 // block itself then it needs adding to the same parent loop as the exit387 // block.388 VPBlockBase *SuccOrExitVPB = getSingleSuccessor();389 SuccOrExitVPB = SuccOrExitVPB ? SuccOrExitVPB : this;390 if (State.Plan->isExitBlock(SuccOrExitVPB)) {391 ParentLoop = State.LI->getLoopFor(392 cast<VPIRBasicBlock>(SuccOrExitVPB)->getIRBasicBlock());393 }394 395 if (ParentLoop && !State.LI->getLoopFor(NewBB))396 ParentLoop->addBasicBlockToLoop(NewBB, *State.LI);397 398 SmallVector<VPBlockBase *> Preds;399 if (VPBlockUtils::isHeader(this, State.VPDT)) {400 // There's no block for the latch yet, connect to the preheader only.401 Preds = {getPredecessors()[0]};402 } else {403 Preds = to_vector(getPredecessors());404 }405 406 // Hook up the new basic block to its predecessors.407 for (VPBlockBase *PredVPBlock : Preds) {408 VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();409 auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors();410 assert(CFG.VPBB2IRBB.contains(PredVPBB) &&411 "Predecessor basic-block not found building successor.");412 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];413 auto *PredBBTerminator = PredBB->getTerminator();414 LLVM_DEBUG(dbgs() << "LV: draw edge from " << PredBB->getName() << '\n');415 416 auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);417 if (isa<UnreachableInst>(PredBBTerminator)) {418 assert(PredVPSuccessors.size() == 1 &&419 "Predecessor ending w/o branch must have single successor.");420 DebugLoc DL = PredBBTerminator->getDebugLoc();421 PredBBTerminator->eraseFromParent();422 auto *Br = BranchInst::Create(NewBB, PredBB);423 Br->setDebugLoc(DL);424 } else if (TermBr && !TermBr->isConditional()) {425 TermBr->setSuccessor(0, NewBB);426 } else {427 // Set each forward successor here when it is created, excluding428 // backedges. A backward successor is set when the branch is created.429 // Branches to VPIRBasicBlocks must have the same successors in VPlan as430 // in the original IR, except when the predecessor is the entry block.431 // This enables including SCEV and memory runtime check blocks in VPlan.432 // TODO: Remove exception by modeling the terminator of entry block using433 // BranchOnCond.434 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;435 assert((TermBr && (!TermBr->getSuccessor(idx) ||436 (isa<VPIRBasicBlock>(this) &&437 (TermBr->getSuccessor(idx) == NewBB ||438 PredVPBlock == getPlan()->getEntry())))) &&439 "Trying to reset an existing successor block.");440 TermBr->setSuccessor(idx, NewBB);441 }442 CFG.DTU.applyUpdates({{DominatorTree::Insert, PredBB, NewBB}});443 }444}445 446void VPIRBasicBlock::execute(VPTransformState *State) {447 assert(getHierarchicalSuccessors().size() <= 2 &&448 "VPIRBasicBlock can have at most two successors at the moment!");449 // Move completely disconnected blocks to their final position.450 if (IRBB->hasNPredecessors(0) && succ_begin(IRBB) == succ_end(IRBB))451 IRBB->moveAfter(State->CFG.PrevBB);452 State->Builder.SetInsertPoint(IRBB->getTerminator());453 State->CFG.PrevBB = IRBB;454 State->CFG.VPBB2IRBB[this] = IRBB;455 executeRecipes(State, IRBB);456 // Create a branch instruction to terminate IRBB if one was not created yet457 // and is needed.458 if (getSingleSuccessor() && isa<UnreachableInst>(IRBB->getTerminator())) {459 auto *Br = State->Builder.CreateBr(IRBB);460 Br->setOperand(0, nullptr);461 IRBB->getTerminator()->eraseFromParent();462 } else {463 assert(464 (getNumSuccessors() == 0 || isa<BranchInst>(IRBB->getTerminator())) &&465 "other blocks must be terminated by a branch");466 }467 468 connectToPredecessors(*State);469}470 471VPIRBasicBlock *VPIRBasicBlock::clone() {472 auto *NewBlock = getPlan()->createEmptyVPIRBasicBlock(IRBB);473 for (VPRecipeBase &R : Recipes)474 NewBlock->appendRecipe(R.clone());475 return NewBlock;476}477 478void VPBasicBlock::execute(VPTransformState *State) {479 bool Replica = bool(State->Lane);480 BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.481 482 if (VPBlockUtils::isHeader(this, State->VPDT)) {483 // Create and register the new vector loop.484 Loop *PrevParentLoop = State->CurrentParentLoop;485 State->CurrentParentLoop = State->LI->AllocateLoop();486 487 // Insert the new loop into the loop nest and register the new basic blocks488 // before calling any utilities such as SCEV that require valid LoopInfo.489 if (PrevParentLoop)490 PrevParentLoop->addChildLoop(State->CurrentParentLoop);491 else492 State->LI->addTopLevelLoop(State->CurrentParentLoop);493 }494 495 auto IsReplicateRegion = [](VPBlockBase *BB) {496 auto *R = dyn_cast_or_null<VPRegionBlock>(BB);497 assert((!R || R->isReplicator()) &&498 "only replicate region blocks should remain");499 return R;500 };501 // 1. Create an IR basic block.502 if ((Replica && this == getParent()->getEntry()) ||503 IsReplicateRegion(getSingleHierarchicalPredecessor())) {504 // Reuse the previous basic block if the current VPBB is either505 // * the entry to a replicate region, or506 // * the exit of a replicate region.507 State->CFG.VPBB2IRBB[this] = NewBB;508 } else {509 NewBB = createEmptyBasicBlock(*State);510 511 State->Builder.SetInsertPoint(NewBB);512 // Temporarily terminate with unreachable until CFG is rewired.513 UnreachableInst *Terminator = State->Builder.CreateUnreachable();514 State->Builder.SetInsertPoint(Terminator);515 516 State->CFG.PrevBB = NewBB;517 State->CFG.VPBB2IRBB[this] = NewBB;518 connectToPredecessors(*State);519 }520 521 // 2. Fill the IR basic block with IR instructions.522 executeRecipes(State, NewBB);523 524 // If this block is a latch, update CurrentParentLoop.525 if (VPBlockUtils::isLatch(this, State->VPDT))526 State->CurrentParentLoop = State->CurrentParentLoop->getParentLoop();527}528 529VPBasicBlock *VPBasicBlock::clone() {530 auto *NewBlock = getPlan()->createVPBasicBlock(getName());531 for (VPRecipeBase &R : *this)532 NewBlock->appendRecipe(R.clone());533 return NewBlock;534}535 536void VPBasicBlock::executeRecipes(VPTransformState *State, BasicBlock *BB) {537 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB: " << getName()538 << " in BB: " << BB->getName() << '\n');539 540 State->CFG.PrevVPBB = this;541 542 for (VPRecipeBase &Recipe : Recipes) {543 State->setDebugLocFrom(Recipe.getDebugLoc());544 Recipe.execute(*State);545 }546 547 LLVM_DEBUG(dbgs() << "LV: filled BB: " << *BB);548}549 550VPBasicBlock *VPBasicBlock::splitAt(iterator SplitAt) {551 assert((SplitAt == end() || SplitAt->getParent() == this) &&552 "can only split at a position in the same block");553 554 // Create new empty block after the block to split.555 auto *SplitBlock = getPlan()->createVPBasicBlock(getName() + ".split");556 VPBlockUtils::insertBlockAfter(SplitBlock, this);557 558 // Finally, move the recipes starting at SplitAt to new block.559 for (VPRecipeBase &ToMove :560 make_early_inc_range(make_range(SplitAt, this->end())))561 ToMove.moveBefore(*SplitBlock, SplitBlock->end());562 563 return SplitBlock;564}565 566/// Return the enclosing loop region for region \p P. The templated version is567/// used to support both const and non-const block arguments.568template <typename T> static T *getEnclosingLoopRegionForRegion(T *P) {569 if (P && P->isReplicator()) {570 P = P->getParent();571 // Multiple loop regions can be nested, but replicate regions can only be572 // nested inside a loop region or must be outside any other region.573 assert((!P || !P->isReplicator()) && "unexpected nested replicate regions");574 }575 return P;576}577 578VPRegionBlock *VPBasicBlock::getEnclosingLoopRegion() {579 return getEnclosingLoopRegionForRegion(getParent());580}581 582const VPRegionBlock *VPBasicBlock::getEnclosingLoopRegion() const {583 return getEnclosingLoopRegionForRegion(getParent());584}585 586static bool hasConditionalTerminator(const VPBasicBlock *VPBB) {587 if (VPBB->empty()) {588 assert(589 VPBB->getNumSuccessors() < 2 &&590 "block with multiple successors doesn't have a recipe as terminator");591 return false;592 }593 594 const VPRecipeBase *R = &VPBB->back();595 bool IsSwitch = isa<VPInstruction>(R) &&596 cast<VPInstruction>(R)->getOpcode() == Instruction::Switch;597 bool IsCondBranch =598 isa<VPBranchOnMaskRecipe>(R) ||599 match(R, m_CombineOr(m_BranchOnCond(), m_BranchOnCount()));600 (void)IsCondBranch;601 (void)IsSwitch;602 if (VPBB->getNumSuccessors() == 2 ||603 (VPBB->isExiting() && !VPBB->getParent()->isReplicator())) {604 assert((IsCondBranch || IsSwitch) &&605 "block with multiple successors not terminated by "606 "conditional branch nor switch recipe");607 608 return true;609 }610 611 if (VPBB->getNumSuccessors() > 2) {612 assert(IsSwitch && "block with more than 2 successors not terminated by "613 "a switch recipe");614 return true;615 }616 617 assert(618 !IsCondBranch &&619 "block with 0 or 1 successors terminated by conditional branch recipe");620 return false;621}622 623VPRecipeBase *VPBasicBlock::getTerminator() {624 if (hasConditionalTerminator(this))625 return &back();626 return nullptr;627}628 629const VPRecipeBase *VPBasicBlock::getTerminator() const {630 if (hasConditionalTerminator(this))631 return &back();632 return nullptr;633}634 635bool VPBasicBlock::isExiting() const {636 return getParent() && getParent()->getExitingBasicBlock() == this;637}638 639#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)640void VPBlockBase::print(raw_ostream &O) const {641 VPSlotTracker SlotTracker(getPlan());642 print(O, "", SlotTracker);643}644 645void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {646 if (getSuccessors().empty()) {647 O << Indent << "No successors\n";648 } else {649 O << Indent << "Successor(s): ";650 ListSeparator LS;651 for (auto *Succ : getSuccessors())652 O << LS << Succ->getName();653 O << '\n';654 }655}656 657void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,658 VPSlotTracker &SlotTracker) const {659 O << Indent << getName() << ":\n";660 661 auto RecipeIndent = Indent + " ";662 for (const VPRecipeBase &Recipe : *this) {663 Recipe.print(O, RecipeIndent, SlotTracker);664 O << '\n';665 }666 667 printSuccessors(O, Indent);668}669#endif670 671static std::pair<VPBlockBase *, VPBlockBase *> cloneFrom(VPBlockBase *Entry);672 673// Clone the CFG for all nodes reachable from \p Entry, this includes cloning674// the blocks and their recipes. Operands of cloned recipes will NOT be updated.675// Remapping of operands must be done separately. Returns a pair with the new676// entry and exiting blocks of the cloned region. If \p Entry isn't part of a677// region, return nullptr for the exiting block.678static std::pair<VPBlockBase *, VPBlockBase *> cloneFrom(VPBlockBase *Entry) {679 DenseMap<VPBlockBase *, VPBlockBase *> Old2NewVPBlocks;680 VPBlockBase *Exiting = nullptr;681 bool InRegion = Entry->getParent();682 // First, clone blocks reachable from Entry.683 for (VPBlockBase *BB : vp_depth_first_shallow(Entry)) {684 VPBlockBase *NewBB = BB->clone();685 Old2NewVPBlocks[BB] = NewBB;686 if (InRegion && BB->getNumSuccessors() == 0) {687 assert(!Exiting && "Multiple exiting blocks?");688 Exiting = BB;689 }690 }691 assert((!InRegion || Exiting) && "regions must have a single exiting block");692 693 // Second, update the predecessors & successors of the cloned blocks.694 for (VPBlockBase *BB : vp_depth_first_shallow(Entry)) {695 VPBlockBase *NewBB = Old2NewVPBlocks[BB];696 SmallVector<VPBlockBase *> NewPreds;697 for (VPBlockBase *Pred : BB->getPredecessors()) {698 NewPreds.push_back(Old2NewVPBlocks[Pred]);699 }700 NewBB->setPredecessors(NewPreds);701 SmallVector<VPBlockBase *> NewSuccs;702 for (VPBlockBase *Succ : BB->successors()) {703 NewSuccs.push_back(Old2NewVPBlocks[Succ]);704 }705 NewBB->setSuccessors(NewSuccs);706 }707 708#if !defined(NDEBUG)709 // Verify that the order of predecessors and successors matches in the cloned710 // version.711 for (const auto &[OldBB, NewBB] :712 zip(vp_depth_first_shallow(Entry),713 vp_depth_first_shallow(Old2NewVPBlocks[Entry]))) {714 for (const auto &[OldPred, NewPred] :715 zip(OldBB->getPredecessors(), NewBB->getPredecessors()))716 assert(NewPred == Old2NewVPBlocks[OldPred] && "Different predecessors");717 718 for (const auto &[OldSucc, NewSucc] :719 zip(OldBB->successors(), NewBB->successors()))720 assert(NewSucc == Old2NewVPBlocks[OldSucc] && "Different successors");721 }722#endif723 724 return std::make_pair(Old2NewVPBlocks[Entry],725 Exiting ? Old2NewVPBlocks[Exiting] : nullptr);726}727 728VPRegionBlock *VPRegionBlock::clone() {729 const auto &[NewEntry, NewExiting] = cloneFrom(getEntry());730 VPlan &Plan = *getPlan();731 VPRegionBlock *NewRegion =732 isReplicator()733 ? Plan.createReplicateRegion(NewEntry, NewExiting, getName())734 : Plan.createLoopRegion(getName(), NewEntry, NewExiting);735 736 for (VPBlockBase *Block : vp_depth_first_shallow(NewEntry))737 Block->setParent(NewRegion);738 return NewRegion;739}740 741void VPRegionBlock::execute(VPTransformState *State) {742 assert(isReplicator() &&743 "Loop regions should have been lowered to plain CFG");744 assert(!State->Lane && "Replicating a Region with non-null instance.");745 assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");746 747 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT(748 Entry);749 State->Lane = VPLane(0);750 for (unsigned Lane = 0, VF = State->VF.getFixedValue(); Lane < VF; ++Lane) {751 State->Lane = VPLane(Lane, VPLane::Kind::First);752 // Visit the VPBlocks connected to \p this, starting from it.753 for (VPBlockBase *Block : RPOT) {754 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');755 Block->execute(State);756 }757 }758 759 // Exit replicating mode.760 State->Lane.reset();761}762 763InstructionCost VPBasicBlock::cost(ElementCount VF, VPCostContext &Ctx) {764 InstructionCost Cost = 0;765 for (VPRecipeBase &R : Recipes)766 Cost += R.cost(VF, Ctx);767 return Cost;768}769 770const VPBasicBlock *VPBasicBlock::getCFGPredecessor(unsigned Idx) const {771 const VPBlockBase *Pred = nullptr;772 if (hasPredecessors()) {773 Pred = getPredecessors()[Idx];774 } else {775 auto *Region = getParent();776 assert(Region && !Region->isReplicator() && Region->getEntry() == this &&777 "must be in the entry block of a non-replicate region");778 assert(Idx < 2 && Region->getNumPredecessors() == 1 &&779 "loop region has a single predecessor (preheader), its entry block "780 "has 2 incoming blocks");781 782 // Idx == 0 selects the predecessor of the region, Idx == 1 selects the783 // region itself whose exiting block feeds the phi across the backedge.784 Pred = Idx == 0 ? Region->getSinglePredecessor() : Region;785 }786 return Pred->getExitingBasicBlock();787}788 789InstructionCost VPRegionBlock::cost(ElementCount VF, VPCostContext &Ctx) {790 if (!isReplicator()) {791 InstructionCost Cost = 0;792 for (VPBlockBase *Block : vp_depth_first_shallow(getEntry()))793 Cost += Block->cost(VF, Ctx);794 InstructionCost BackedgeCost =795 ForceTargetInstructionCost.getNumOccurrences()796 ? InstructionCost(ForceTargetInstructionCost.getNumOccurrences())797 : Ctx.TTI.getCFInstrCost(Instruction::Br, Ctx.CostKind);798 LLVM_DEBUG(dbgs() << "Cost of " << BackedgeCost << " for VF " << VF799 << ": vector loop backedge\n");800 Cost += BackedgeCost;801 return Cost;802 }803 804 // Compute the cost of a replicate region. Replicating isn't supported for805 // scalable vectors, return an invalid cost for them.806 // TODO: Discard scalable VPlans with replicate recipes earlier after807 // construction.808 if (VF.isScalable())809 return InstructionCost::getInvalid();810 811 // Compute and return the cost of the conditionally executed recipes.812 assert(VF.isVector() && "Can only compute vector cost at the moment.");813 VPBasicBlock *Then = cast<VPBasicBlock>(getEntry()->getSuccessors()[0]);814 return Then->cost(VF, Ctx);815}816 817#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)818void VPRegionBlock::print(raw_ostream &O, const Twine &Indent,819 VPSlotTracker &SlotTracker) const {820 O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";821 auto NewIndent = Indent + " ";822 for (auto *BlockBase : vp_depth_first_shallow(Entry)) {823 O << '\n';824 BlockBase->print(O, NewIndent, SlotTracker);825 }826 O << Indent << "}\n";827 828 printSuccessors(O, Indent);829}830#endif831 832void VPRegionBlock::dissolveToCFGLoop() {833 auto *Header = cast<VPBasicBlock>(getEntry());834 if (auto *CanIV = dyn_cast<VPCanonicalIVPHIRecipe>(&Header->front())) {835 assert(this == getPlan()->getVectorLoopRegion() &&836 "Canonical IV must be in the entry of the top-level loop region");837 auto *ScalarR = VPBuilder(CanIV).createScalarPhi(838 {CanIV->getStartValue(), CanIV->getBackedgeValue()},839 CanIV->getDebugLoc(), "index");840 CanIV->replaceAllUsesWith(ScalarR);841 CanIV->eraseFromParent();842 }843 844 VPBlockBase *Preheader = getSinglePredecessor();845 auto *ExitingLatch = cast<VPBasicBlock>(getExiting());846 VPBlockBase *Middle = getSingleSuccessor();847 VPBlockUtils::disconnectBlocks(Preheader, this);848 VPBlockUtils::disconnectBlocks(this, Middle);849 850 for (VPBlockBase *VPB : vp_depth_first_shallow(Entry))851 VPB->setParent(getParent());852 853 VPBlockUtils::connectBlocks(Preheader, Header);854 VPBlockUtils::connectBlocks(ExitingLatch, Middle);855 VPBlockUtils::connectBlocks(ExitingLatch, Header);856}857 858VPlan::VPlan(Loop *L) {859 setEntry(createVPIRBasicBlock(L->getLoopPreheader()));860 ScalarHeader = createVPIRBasicBlock(L->getHeader());861 862 SmallVector<BasicBlock *> IRExitBlocks;863 L->getUniqueExitBlocks(IRExitBlocks);864 for (BasicBlock *EB : IRExitBlocks)865 ExitBlocks.push_back(createVPIRBasicBlock(EB));866}867 868VPlan::~VPlan() {869 VPValue DummyValue;870 871 for (auto *VPB : CreatedBlocks) {872 if (auto *VPBB = dyn_cast<VPBasicBlock>(VPB)) {873 // Replace all operands of recipes and all VPValues defined in VPBB with874 // DummyValue so the block can be deleted.875 for (VPRecipeBase &R : *VPBB) {876 for (auto *Def : R.definedValues())877 Def->replaceAllUsesWith(&DummyValue);878 879 for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)880 R.setOperand(I, &DummyValue);881 }882 }883 delete VPB;884 }885 for (VPValue *VPV : getLiveIns())886 delete VPV;887 delete BackedgeTakenCount;888}889 890VPIRBasicBlock *VPlan::getExitBlock(BasicBlock *IRBB) const {891 auto Iter = find_if(getExitBlocks(), [IRBB](const VPIRBasicBlock *VPIRBB) {892 return VPIRBB->getIRBasicBlock() == IRBB;893 });894 assert(Iter != getExitBlocks().end() && "no exit block found");895 return *Iter;896}897 898bool VPlan::isExitBlock(VPBlockBase *VPBB) {899 return is_contained(ExitBlocks, VPBB);900}901 902/// Generate the code inside the preheader and body of the vectorized loop.903/// Assumes a single pre-header basic-block was created for this. Introduce904/// additional basic-blocks as needed, and fill them all.905void VPlan::execute(VPTransformState *State) {906 // Initialize CFG state.907 State->CFG.PrevVPBB = nullptr;908 State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();909 910 // Update VPDominatorTree since VPBasicBlock may be removed after State was911 // constructed.912 State->VPDT.recalculate(*this);913 914 // Disconnect VectorPreHeader from ExitBB in both the CFG and DT.915 BasicBlock *VectorPreHeader = State->CFG.PrevBB;916 cast<BranchInst>(VectorPreHeader->getTerminator())->setSuccessor(0, nullptr);917 State->CFG.DTU.applyUpdates(918 {{DominatorTree::Delete, VectorPreHeader, State->CFG.ExitBB}});919 920 LLVM_DEBUG(dbgs() << "Executing best plan with VF=" << State->VF921 << ", UF=" << getUF() << '\n');922 setName("Final VPlan");923 LLVM_DEBUG(dump());924 925 BasicBlock *ScalarPh = State->CFG.ExitBB;926 VPBasicBlock *ScalarPhVPBB = getScalarPreheader();927 if (ScalarPhVPBB->hasPredecessors()) {928 // Disconnect scalar preheader and scalar header, as the dominator tree edge929 // will be updated as part of VPlan execution. This allows keeping the DTU930 // logic generic during VPlan execution.931 State->CFG.DTU.applyUpdates(932 {{DominatorTree::Delete, ScalarPh, ScalarPh->getSingleSuccessor()}});933 }934 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT(935 Entry);936 // Generate code for the VPlan, in parts of the vector skeleton, loop body and937 // successor blocks including the middle, exit and scalar preheader blocks.938 for (VPBlockBase *Block : RPOT)939 Block->execute(State);940 941 // If the original loop is unreachable, delete it and all its blocks.942 if (!ScalarPhVPBB->hasPredecessors()) {943 // DeleteDeadBlocks will remove single-entry phis. Remove them from the exit944 // VPIRBBs in VPlan as well, otherwise we would retain references to deleted945 // IR instructions.946 for (VPIRBasicBlock *EB : getExitBlocks()) {947 for (VPRecipeBase &R : make_early_inc_range(EB->phis())) {948 if (R.getNumOperands() == 1)949 R.eraseFromParent();950 }951 }952 953 Loop *OrigLoop =954 State->LI->getLoopFor(getScalarHeader()->getIRBasicBlock());955 auto Blocks = OrigLoop->getBlocksVector();956 Blocks.push_back(cast<VPIRBasicBlock>(ScalarPhVPBB)->getIRBasicBlock());957 for (auto *BB : Blocks)958 State->LI->removeBlock(BB);959 DeleteDeadBlocks(Blocks, &State->CFG.DTU);960 State->LI->erase(OrigLoop);961 }962 963 State->CFG.DTU.flush();964 965 VPBasicBlock *Header = vputils::getFirstLoopHeader(*this, State->VPDT);966 if (!Header)967 return;968 969 auto *LatchVPBB = cast<VPBasicBlock>(Header->getPredecessors()[1]);970 BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB];971 972 // Fix the latch value of canonical, reduction and first-order recurrences973 // phis in the vector loop.974 for (VPRecipeBase &R : Header->phis()) {975 // Skip phi-like recipes that generate their backedege values themselves.976 if (isa<VPWidenPHIRecipe>(&R))977 continue;978 979 auto *PhiR = cast<VPSingleDefRecipe>(&R);980 // VPInstructions currently model scalar Phis only.981 bool NeedsScalar = isa<VPInstruction>(PhiR) ||982 (isa<VPReductionPHIRecipe>(PhiR) &&983 cast<VPReductionPHIRecipe>(PhiR)->isInLoop());984 985 Value *Phi = State->get(PhiR, NeedsScalar);986 // VPHeaderPHIRecipe supports getBackedgeValue() but VPInstruction does987 // not.988 Value *Val = State->get(PhiR->getOperand(1), NeedsScalar);989 cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);990 }991}992 993InstructionCost VPlan::cost(ElementCount VF, VPCostContext &Ctx) {994 // For now only return the cost of the vector loop region, ignoring any other995 // blocks, like the preheader or middle blocks, expect for checking them for996 // recipes with invalid costs.997 InstructionCost Cost = getVectorLoopRegion()->cost(VF, Ctx);998 999 // If the cost of the loop region is invalid or any recipe in the skeleton1000 // outside loop regions are invalid return an invalid cost.1001 if (!Cost.isValid() || any_of(VPBlockUtils::blocksOnly<VPBasicBlock>(1002 vp_depth_first_shallow(getEntry())),1003 [&VF, &Ctx](VPBasicBlock *VPBB) {1004 return !VPBB->cost(VF, Ctx).isValid();1005 }))1006 return InstructionCost::getInvalid();1007 1008 return Cost;1009}1010 1011VPRegionBlock *VPlan::getVectorLoopRegion() {1012 // TODO: Cache if possible.1013 for (VPBlockBase *B : vp_depth_first_shallow(getEntry()))1014 if (auto *R = dyn_cast<VPRegionBlock>(B))1015 return R->isReplicator() ? nullptr : R;1016 return nullptr;1017}1018 1019const VPRegionBlock *VPlan::getVectorLoopRegion() const {1020 for (const VPBlockBase *B : vp_depth_first_shallow(getEntry()))1021 if (auto *R = dyn_cast<VPRegionBlock>(B))1022 return R->isReplicator() ? nullptr : R;1023 return nullptr;1024}1025 1026#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1027void VPlan::printLiveIns(raw_ostream &O) const {1028 VPSlotTracker SlotTracker(this);1029 1030 if (VF.getNumUsers() > 0) {1031 O << "\nLive-in ";1032 VF.printAsOperand(O, SlotTracker);1033 O << " = VF";1034 }1035 1036 if (VFxUF.getNumUsers() > 0) {1037 O << "\nLive-in ";1038 VFxUF.printAsOperand(O, SlotTracker);1039 O << " = VF * UF";1040 }1041 1042 if (VectorTripCount.getNumUsers() > 0) {1043 O << "\nLive-in ";1044 VectorTripCount.printAsOperand(O, SlotTracker);1045 O << " = vector-trip-count";1046 }1047 1048 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {1049 O << "\nLive-in ";1050 BackedgeTakenCount->printAsOperand(O, SlotTracker);1051 O << " = backedge-taken count";1052 }1053 1054 O << "\n";1055 if (TripCount) {1056 if (TripCount->isLiveIn())1057 O << "Live-in ";1058 TripCount->printAsOperand(O, SlotTracker);1059 O << " = original trip-count";1060 O << "\n";1061 }1062}1063 1064LLVM_DUMP_METHOD1065void VPlan::print(raw_ostream &O) const {1066 VPSlotTracker SlotTracker(this);1067 1068 O << "VPlan '" << getName() << "' {";1069 1070 printLiveIns(O);1071 1072 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<const VPBlockBase *>>1073 RPOT(getEntry());1074 for (const VPBlockBase *Block : RPOT) {1075 O << '\n';1076 Block->print(O, "", SlotTracker);1077 }1078 1079 O << "}\n";1080}1081 1082std::string VPlan::getName() const {1083 std::string Out;1084 raw_string_ostream RSO(Out);1085 RSO << Name << " for ";1086 if (!VFs.empty()) {1087 RSO << "VF={" << VFs[0];1088 for (ElementCount VF : drop_begin(VFs))1089 RSO << "," << VF;1090 RSO << "},";1091 }1092 1093 if (UFs.empty()) {1094 RSO << "UF>=1";1095 } else {1096 RSO << "UF={" << UFs[0];1097 for (unsigned UF : drop_begin(UFs))1098 RSO << "," << UF;1099 RSO << "}";1100 }1101 1102 return Out;1103}1104 1105LLVM_DUMP_METHOD1106void VPlan::printDOT(raw_ostream &O) const {1107 VPlanPrinter Printer(O, *this);1108 Printer.dump();1109}1110 1111LLVM_DUMP_METHOD1112void VPlan::dump() const { print(dbgs()); }1113#endif1114 1115static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry,1116 DenseMap<VPValue *, VPValue *> &Old2NewVPValues) {1117 // Update the operands of all cloned recipes starting at NewEntry. This1118 // traverses all reachable blocks. This is done in two steps, to handle cycles1119 // in PHI recipes.1120 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>>1121 OldDeepRPOT(Entry);1122 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>>1123 NewDeepRPOT(NewEntry);1124 // First, collect all mappings from old to new VPValues defined by cloned1125 // recipes.1126 for (const auto &[OldBB, NewBB] :1127 zip(VPBlockUtils::blocksOnly<VPBasicBlock>(OldDeepRPOT),1128 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT))) {1129 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().size() &&1130 "blocks must have the same number of recipes");1131 for (const auto &[OldR, NewR] : zip(*OldBB, *NewBB)) {1132 assert(OldR.getNumOperands() == NewR.getNumOperands() &&1133 "recipes must have the same number of operands");1134 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&1135 "recipes must define the same number of operands");1136 for (const auto &[OldV, NewV] :1137 zip(OldR.definedValues(), NewR.definedValues()))1138 Old2NewVPValues[OldV] = NewV;1139 }1140 }1141 1142 // Update all operands to use cloned VPValues.1143 for (VPBasicBlock *NewBB :1144 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) {1145 for (VPRecipeBase &NewR : *NewBB)1146 for (unsigned I = 0, E = NewR.getNumOperands(); I != E; ++I) {1147 VPValue *NewOp = Old2NewVPValues.lookup(NewR.getOperand(I));1148 NewR.setOperand(I, NewOp);1149 }1150 }1151}1152 1153VPlan *VPlan::duplicate() {1154 unsigned NumBlocksBeforeCloning = CreatedBlocks.size();1155 // Clone blocks.1156 const auto &[NewEntry, __] = cloneFrom(Entry);1157 1158 BasicBlock *ScalarHeaderIRBB = getScalarHeader()->getIRBasicBlock();1159 VPIRBasicBlock *NewScalarHeader = nullptr;1160 if (getScalarHeader()->hasPredecessors()) {1161 NewScalarHeader = cast<VPIRBasicBlock>(*find_if(1162 vp_depth_first_shallow(NewEntry), [ScalarHeaderIRBB](VPBlockBase *VPB) {1163 auto *VPIRBB = dyn_cast<VPIRBasicBlock>(VPB);1164 return VPIRBB && VPIRBB->getIRBasicBlock() == ScalarHeaderIRBB;1165 }));1166 } else {1167 NewScalarHeader = createVPIRBasicBlock(ScalarHeaderIRBB);1168 }1169 // Create VPlan, clone live-ins and remap operands in the cloned blocks.1170 auto *NewPlan = new VPlan(cast<VPBasicBlock>(NewEntry), NewScalarHeader);1171 DenseMap<VPValue *, VPValue *> Old2NewVPValues;1172 for (VPValue *OldLiveIn : getLiveIns()) {1173 Old2NewVPValues[OldLiveIn] =1174 NewPlan->getOrAddLiveIn(OldLiveIn->getLiveInIRValue());1175 }1176 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;1177 Old2NewVPValues[&VF] = &NewPlan->VF;1178 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;1179 if (BackedgeTakenCount) {1180 NewPlan->BackedgeTakenCount = new VPValue();1181 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;1182 }1183 if (TripCount && TripCount->isLiveIn())1184 Old2NewVPValues[TripCount] =1185 NewPlan->getOrAddLiveIn(TripCount->getLiveInIRValue());1186 // else NewTripCount will be created and inserted into Old2NewVPValues when1187 // TripCount is cloned. In any case NewPlan->TripCount is updated below.1188 1189 remapOperands(Entry, NewEntry, Old2NewVPValues);1190 1191 // Initialize remaining fields of cloned VPlan.1192 NewPlan->VFs = VFs;1193 NewPlan->UFs = UFs;1194 // TODO: Adjust names.1195 NewPlan->Name = Name;1196 if (TripCount) {1197 assert(Old2NewVPValues.contains(TripCount) &&1198 "TripCount must have been added to Old2NewVPValues");1199 NewPlan->TripCount = Old2NewVPValues[TripCount];1200 }1201 1202 // Transfer all cloned blocks (the second half of all current blocks) from1203 // current to new VPlan.1204 unsigned NumBlocksAfterCloning = CreatedBlocks.size();1205 for (unsigned I :1206 seq<unsigned>(NumBlocksBeforeCloning, NumBlocksAfterCloning))1207 NewPlan->CreatedBlocks.push_back(this->CreatedBlocks[I]);1208 CreatedBlocks.truncate(NumBlocksBeforeCloning);1209 1210 // Update ExitBlocks of the new plan.1211 for (VPBlockBase *VPB : NewPlan->CreatedBlocks) {1212 if (VPB->getNumSuccessors() == 0 && isa<VPIRBasicBlock>(VPB) &&1213 VPB != NewScalarHeader)1214 NewPlan->ExitBlocks.push_back(cast<VPIRBasicBlock>(VPB));1215 }1216 1217 return NewPlan;1218}1219 1220VPIRBasicBlock *VPlan::createEmptyVPIRBasicBlock(BasicBlock *IRBB) {1221 auto *VPIRBB = new VPIRBasicBlock(IRBB);1222 CreatedBlocks.push_back(VPIRBB);1223 return VPIRBB;1224}1225 1226VPIRBasicBlock *VPlan::createVPIRBasicBlock(BasicBlock *IRBB) {1227 auto *VPIRBB = createEmptyVPIRBasicBlock(IRBB);1228 for (Instruction &I :1229 make_range(IRBB->begin(), IRBB->getTerminator()->getIterator()))1230 VPIRBB->appendRecipe(VPIRInstruction::create(I));1231 return VPIRBB;1232}1233 1234#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1235 1236Twine VPlanPrinter::getUID(const VPBlockBase *Block) {1237 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +1238 Twine(getOrCreateBID(Block));1239}1240 1241Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {1242 const std::string &Name = Block->getName();1243 if (!Name.empty())1244 return Name;1245 return "VPB" + Twine(getOrCreateBID(Block));1246}1247 1248void VPlanPrinter::dump() {1249 Depth = 1;1250 bumpIndent(0);1251 OS << "digraph VPlan {\n";1252 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";1253 if (!Plan.getName().empty())1254 OS << "\\n" << DOT::EscapeString(Plan.getName());1255 1256 {1257 // Print live-ins.1258 std::string Str;1259 raw_string_ostream SS(Str);1260 Plan.printLiveIns(SS);1261 SmallVector<StringRef, 0> Lines;1262 StringRef(Str).rtrim('\n').split(Lines, "\n");1263 for (auto Line : Lines)1264 OS << DOT::EscapeString(Line.str()) << "\\n";1265 }1266 1267 OS << "\"]\n";1268 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";1269 OS << "edge [fontname=Courier, fontsize=30]\n";1270 OS << "compound=true\n";1271 1272 for (const VPBlockBase *Block : vp_depth_first_shallow(Plan.getEntry()))1273 dumpBlock(Block);1274 1275 OS << "}\n";1276}1277 1278void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {1279 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))1280 dumpBasicBlock(BasicBlock);1281 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))1282 dumpRegion(Region);1283 else1284 llvm_unreachable("Unsupported kind of VPBlock.");1285}1286 1287void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,1288 bool Hidden, const Twine &Label) {1289 // Due to "dot" we print an edge between two regions as an edge between the1290 // exiting basic block and the entry basic of the respective regions.1291 const VPBlockBase *Tail = From->getExitingBasicBlock();1292 const VPBlockBase *Head = To->getEntryBasicBlock();1293 OS << Indent << getUID(Tail) << " -> " << getUID(Head);1294 OS << " [ label=\"" << Label << '\"';1295 if (Tail != From)1296 OS << " ltail=" << getUID(From);1297 if (Head != To)1298 OS << " lhead=" << getUID(To);1299 if (Hidden)1300 OS << "; splines=none";1301 OS << "]\n";1302}1303 1304void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {1305 auto &Successors = Block->getSuccessors();1306 if (Successors.size() == 1)1307 drawEdge(Block, Successors.front(), false, "");1308 else if (Successors.size() == 2) {1309 drawEdge(Block, Successors.front(), false, "T");1310 drawEdge(Block, Successors.back(), false, "F");1311 } else {1312 unsigned SuccessorNumber = 0;1313 for (auto *Successor : Successors)1314 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));1315 }1316}1317 1318void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {1319 // Implement dot-formatted dump by performing plain-text dump into the1320 // temporary storage followed by some post-processing.1321 OS << Indent << getUID(BasicBlock) << " [label =\n";1322 bumpIndent(1);1323 std::string Str;1324 raw_string_ostream SS(Str);1325 // Use no indentation as we need to wrap the lines into quotes ourselves.1326 BasicBlock->print(SS, "", SlotTracker);1327 1328 // We need to process each line of the output separately, so split1329 // single-string plain-text dump.1330 SmallVector<StringRef, 0> Lines;1331 StringRef(Str).rtrim('\n').split(Lines, "\n");1332 1333 auto EmitLine = [&](StringRef Line, StringRef Suffix) {1334 OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;1335 };1336 1337 // Don't need the "+" after the last line.1338 for (auto Line : make_range(Lines.begin(), Lines.end() - 1))1339 EmitLine(Line, " +\n");1340 EmitLine(Lines.back(), "\n");1341 1342 bumpIndent(-1);1343 OS << Indent << "]\n";1344 1345 dumpEdges(BasicBlock);1346}1347 1348void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {1349 OS << Indent << "subgraph " << getUID(Region) << " {\n";1350 bumpIndent(1);1351 OS << Indent << "fontname=Courier\n"1352 << Indent << "label=\""1353 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")1354 << DOT::EscapeString(Region->getName()) << "\"\n";1355 // Dump the blocks of the region.1356 assert(Region->getEntry() && "Region contains no inner blocks.");1357 for (const VPBlockBase *Block : vp_depth_first_shallow(Region->getEntry()))1358 dumpBlock(Block);1359 bumpIndent(-1);1360 OS << Indent << "}\n";1361 dumpEdges(Region);1362}1363 1364#endif1365 1366/// Returns true if there is a vector loop region and \p VPV is defined in a1367/// loop region.1368static bool isDefinedInsideLoopRegions(const VPValue *VPV) {1369 const VPRecipeBase *DefR = VPV->getDefiningRecipe();1370 return DefR && (!DefR->getParent()->getPlan()->getVectorLoopRegion() ||1371 DefR->getParent()->getEnclosingLoopRegion());1372}1373 1374bool VPValue::isDefinedOutsideLoopRegions() const {1375 return !isDefinedInsideLoopRegions(this);1376}1377void VPValue::replaceAllUsesWith(VPValue *New) {1378 replaceUsesWithIf(New, [](VPUser &, unsigned) { return true; });1379}1380 1381void VPValue::replaceUsesWithIf(1382 VPValue *New,1383 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace) {1384 // Note that this early exit is required for correctness; the implementation1385 // below relies on the number of users for this VPValue to decrease, which1386 // isn't the case if this == New.1387 if (this == New)1388 return;1389 1390 for (unsigned J = 0; J < getNumUsers();) {1391 VPUser *User = Users[J];1392 bool RemovedUser = false;1393 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {1394 if (User->getOperand(I) != this || !ShouldReplace(*User, I))1395 continue;1396 1397 RemovedUser = true;1398 User->setOperand(I, New);1399 }1400 // If a user got removed after updating the current user, the next user to1401 // update will be moved to the current position, so we only need to1402 // increment the index if the number of users did not change.1403 if (!RemovedUser)1404 J++;1405 }1406}1407 1408void VPUser::replaceUsesOfWith(VPValue *From, VPValue *To) {1409 for (unsigned Idx = 0; Idx != getNumOperands(); ++Idx) {1410 if (getOperand(Idx) == From)1411 setOperand(Idx, To);1412 }1413}1414 1415#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1416void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const {1417 OS << Tracker.getOrCreateName(this);1418}1419 1420void VPUser::printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const {1421 interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {1422 Op->printAsOperand(O, SlotTracker);1423 });1424}1425#endif1426 1427void VPSlotTracker::assignName(const VPValue *V) {1428 assert(!VPValue2Name.contains(V) && "VPValue already has a name!");1429 auto *UV = V->getUnderlyingValue();1430 auto *VPI = dyn_cast_or_null<VPInstruction>(V);1431 if (!UV && !(VPI && !VPI->getName().empty())) {1432 VPValue2Name[V] = (Twine("vp<%") + Twine(NextSlot) + ">").str();1433 NextSlot++;1434 return;1435 }1436 1437 // Use the name of the underlying Value, wrapped in "ir<>", and versioned by1438 // appending ".Number" to the name if there are multiple uses.1439 std::string Name;1440 if (UV)1441 Name = getName(UV);1442 else1443 Name = VPI->getName();1444 1445 assert(!Name.empty() && "Name cannot be empty.");1446 StringRef Prefix = UV ? "ir<" : "vp<%";1447 std::string BaseName = (Twine(Prefix) + Name + Twine(">")).str();1448 1449 // First assign the base name for V.1450 const auto &[A, _] = VPValue2Name.try_emplace(V, BaseName);1451 // Integer or FP constants with different types will result in he same string1452 // due to stripping types.1453 if (V->isLiveIn() && isa<ConstantInt, ConstantFP>(UV))1454 return;1455 1456 // If it is already used by C > 0 other VPValues, increase the version counter1457 // C and use it for V.1458 const auto &[C, UseInserted] = BaseName2Version.try_emplace(BaseName, 0);1459 if (!UseInserted) {1460 C->second++;1461 A->second = (BaseName + Twine(".") + Twine(C->second)).str();1462 }1463}1464 1465void VPSlotTracker::assignNames(const VPlan &Plan) {1466 if (Plan.VF.getNumUsers() > 0)1467 assignName(&Plan.VF);1468 if (Plan.VFxUF.getNumUsers() > 0)1469 assignName(&Plan.VFxUF);1470 assignName(&Plan.VectorTripCount);1471 if (Plan.BackedgeTakenCount)1472 assignName(Plan.BackedgeTakenCount);1473 for (VPValue *LI : Plan.getLiveIns())1474 assignName(LI);1475 1476 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<const VPBlockBase *>>1477 RPOT(VPBlockDeepTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));1478 for (const VPBasicBlock *VPBB :1479 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))1480 assignNames(VPBB);1481}1482 1483void VPSlotTracker::assignNames(const VPBasicBlock *VPBB) {1484 for (const VPRecipeBase &Recipe : *VPBB)1485 for (VPValue *Def : Recipe.definedValues())1486 assignName(Def);1487}1488 1489std::string VPSlotTracker::getName(const Value *V) {1490 std::string Name;1491 raw_string_ostream S(Name);1492 if (V->hasName() || !isa<Instruction>(V)) {1493 V->printAsOperand(S, false);1494 return Name;1495 }1496 1497 if (!MST) {1498 // Lazily create the ModuleSlotTracker when we first hit an unnamed1499 // instruction.1500 auto *I = cast<Instruction>(V);1501 // This check is required to support unit tests with incomplete IR.1502 if (I->getParent()) {1503 MST = std::make_unique<ModuleSlotTracker>(I->getModule());1504 MST->incorporateFunction(*I->getFunction());1505 } else {1506 MST = std::make_unique<ModuleSlotTracker>(nullptr);1507 }1508 }1509 V->printAsOperand(S, false, *MST);1510 return Name;1511}1512 1513std::string VPSlotTracker::getOrCreateName(const VPValue *V) const {1514 std::string Name = VPValue2Name.lookup(V);1515 if (!Name.empty())1516 return Name;1517 1518 // If no name was assigned, no VPlan was provided when creating the slot1519 // tracker or it is not reachable from the provided VPlan. This can happen,1520 // e.g. when trying to print a recipe that has not been inserted into a VPlan1521 // in a debugger.1522 // TODO: Update VPSlotTracker constructor to assign names to recipes &1523 // VPValues not associated with a VPlan, instead of constructing names ad-hoc1524 // here.1525 const VPRecipeBase *DefR = V->getDefiningRecipe();1526 (void)DefR;1527 assert((!DefR || !DefR->getParent() || !DefR->getParent()->getPlan()) &&1528 "VPValue defined by a recipe in a VPlan?");1529 1530 // Use the underlying value's name, if there is one.1531 if (auto *UV = V->getUnderlyingValue()) {1532 std::string Name;1533 raw_string_ostream S(Name);1534 UV->printAsOperand(S, false);1535 return (Twine("ir<") + Name + ">").str();1536 }1537 1538 return "<badref>";1539}1540 1541bool LoopVectorizationPlanner::getDecisionAndClampRange(1542 const std::function<bool(ElementCount)> &Predicate, VFRange &Range) {1543 assert(!Range.isEmpty() && "Trying to test an empty VF range.");1544 bool PredicateAtRangeStart = Predicate(Range.Start);1545 1546 for (ElementCount TmpVF : VFRange(Range.Start * 2, Range.End))1547 if (Predicate(TmpVF) != PredicateAtRangeStart) {1548 Range.End = TmpVF;1549 break;1550 }1551 1552 return PredicateAtRangeStart;1553}1554 1555/// Build VPlans for the full range of feasible VF's = {\p MinVF, 2 * \p MinVF,1556/// 4 * \p MinVF, ..., \p MaxVF} by repeatedly building a VPlan for a sub-range1557/// of VF's starting at a given VF and extending it as much as possible. Each1558/// vectorization decision can potentially shorten this sub-range during1559/// buildVPlan().1560void LoopVectorizationPlanner::buildVPlans(ElementCount MinVF,1561 ElementCount MaxVF) {1562 auto MaxVFTimes2 = MaxVF * 2;1563 for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFTimes2);) {1564 VFRange SubRange = {VF, MaxVFTimes2};1565 if (auto Plan = tryToBuildVPlan(SubRange)) {1566 VPlanTransforms::optimize(*Plan);1567 // Update the name of the latch of the top-level vector loop region region1568 // after optimizations which includes block folding.1569 Plan->getVectorLoopRegion()->getExiting()->setName("vector.latch");1570 VPlans.push_back(std::move(Plan));1571 }1572 VF = SubRange.End;1573 }1574}1575 1576VPlan &LoopVectorizationPlanner::getPlanFor(ElementCount VF) const {1577 assert(count_if(VPlans,1578 [VF](const VPlanPtr &Plan) { return Plan->hasVF(VF); }) ==1579 1 &&1580 "Multiple VPlans for VF.");1581 1582 for (const VPlanPtr &Plan : VPlans) {1583 if (Plan->hasVF(VF))1584 return *Plan.get();1585 }1586 llvm_unreachable("No plan found!");1587}1588 1589static void addRuntimeUnrollDisableMetaData(Loop *L) {1590 SmallVector<Metadata *, 4> MDs;1591 // Reserve first location for self reference to the LoopID metadata node.1592 MDs.push_back(nullptr);1593 bool IsUnrollMetadata = false;1594 MDNode *LoopID = L->getLoopID();1595 if (LoopID) {1596 // First find existing loop unrolling disable metadata.1597 for (unsigned I = 1, IE = LoopID->getNumOperands(); I < IE; ++I) {1598 auto *MD = dyn_cast<MDNode>(LoopID->getOperand(I));1599 if (MD) {1600 const auto *S = dyn_cast<MDString>(MD->getOperand(0));1601 if (!S)1602 continue;1603 if (S->getString().starts_with("llvm.loop.unroll.runtime.disable"))1604 continue;1605 IsUnrollMetadata =1606 S->getString().starts_with("llvm.loop.unroll.disable");1607 }1608 MDs.push_back(LoopID->getOperand(I));1609 }1610 }1611 1612 if (!IsUnrollMetadata) {1613 // Add runtime unroll disable metadata.1614 LLVMContext &Context = L->getHeader()->getContext();1615 SmallVector<Metadata *, 1> DisableOperands;1616 DisableOperands.push_back(1617 MDString::get(Context, "llvm.loop.unroll.runtime.disable"));1618 MDNode *DisableNode = MDNode::get(Context, DisableOperands);1619 MDs.push_back(DisableNode);1620 MDNode *NewLoopID = MDNode::get(Context, MDs);1621 // Set operand 0 to refer to the loop id itself.1622 NewLoopID->replaceOperandWith(0, NewLoopID);1623 L->setLoopID(NewLoopID);1624 }1625}1626 1627void LoopVectorizationPlanner::updateLoopMetadataAndProfileInfo(1628 Loop *VectorLoop, VPBasicBlock *HeaderVPBB, const VPlan &Plan,1629 bool VectorizingEpilogue, MDNode *OrigLoopID,1630 std::optional<unsigned> OrigAverageTripCount,1631 unsigned OrigLoopInvocationWeight, unsigned EstimatedVFxUF,1632 bool DisableRuntimeUnroll) {1633 // Update the metadata of the scalar loop. Skip the update when vectorizing1634 // the epilogue loop to ensure it is updated only once. Also skip the update1635 // when the scalar loop became unreachable.1636 if (Plan.getScalarPreheader()->hasPredecessors() && !VectorizingEpilogue) {1637 std::optional<MDNode *> RemainderLoopID =1638 makeFollowupLoopID(OrigLoopID, {LLVMLoopVectorizeFollowupAll,1639 LLVMLoopVectorizeFollowupEpilogue});1640 if (RemainderLoopID) {1641 OrigLoop->setLoopID(*RemainderLoopID);1642 } else {1643 if (DisableRuntimeUnroll)1644 addRuntimeUnrollDisableMetaData(OrigLoop);1645 1646 LoopVectorizeHints Hints(OrigLoop, true, *ORE);1647 Hints.setAlreadyVectorized();1648 }1649 }1650 1651 if (!VectorLoop)1652 return;1653 1654 if (std::optional<MDNode *> VectorizedLoopID = makeFollowupLoopID(1655 OrigLoopID, {LLVMLoopVectorizeFollowupAll,1656 LLVMLoopVectorizeFollowupVectorized})) {1657 VectorLoop->setLoopID(*VectorizedLoopID);1658 } else {1659 // Keep all loop hints from the original loop on the vector loop (we'll1660 // replace the vectorizer-specific hints below).1661 if (OrigLoopID)1662 VectorLoop->setLoopID(OrigLoopID);1663 1664 if (!VectorizingEpilogue) {1665 LoopVectorizeHints Hints(VectorLoop, true, *ORE);1666 Hints.setAlreadyVectorized();1667 }1668 }1669 TargetTransformInfo::UnrollingPreferences UP;1670 TTI.getUnrollingPreferences(VectorLoop, *PSE.getSE(), UP, ORE);1671 if (!UP.UnrollVectorizedLoop || VectorizingEpilogue)1672 addRuntimeUnrollDisableMetaData(VectorLoop);1673 1674 // Set/update profile weights for the vector and remainder loops as original1675 // loop iterations are now distributed among them. Note that original loop1676 // becomes the scalar remainder loop after vectorization.1677 //1678 // For cases like foldTailByMasking() and requiresScalarEpiloque() we may1679 // end up getting slightly roughened result but that should be OK since1680 // profile is not inherently precise anyway. Note also possible bypass of1681 // vector code caused by legality checks is ignored, assigning all the weight1682 // to the vector loop, optimistically.1683 //1684 // For scalable vectorization we can't know at compile time how many1685 // iterations of the loop are handled in one vector iteration, so instead1686 // use the value of vscale used for tuning.1687 if (!OrigAverageTripCount)1688 return;1689 // Calculate number of iterations in unrolled loop.1690 unsigned AverageVectorTripCount = *OrigAverageTripCount / EstimatedVFxUF;1691 // Calculate number of iterations for remainder loop.1692 unsigned RemainderAverageTripCount = *OrigAverageTripCount % EstimatedVFxUF;1693 1694 if (HeaderVPBB) {1695 setLoopEstimatedTripCount(VectorLoop, AverageVectorTripCount,1696 OrigLoopInvocationWeight);1697 }1698 if (Plan.getScalarPreheader()->hasPredecessors()) {1699 setLoopEstimatedTripCount(OrigLoop, RemainderAverageTripCount,1700 OrigLoopInvocationWeight);1701 }1702}1703 1704#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1705void LoopVectorizationPlanner::printPlans(raw_ostream &O) {1706 if (VPlans.empty()) {1707 O << "LV: No VPlans built.\n";1708 return;1709 }1710 for (const auto &Plan : VPlans)1711 if (PrintVPlansInDotFormat)1712 Plan->printDOT(O);1713 else1714 Plan->print(O);1715}1716#endif1717 1718bool llvm::canConstantBeExtended(const APInt *C, Type *NarrowType,1719 TTI::PartialReductionExtendKind ExtKind) {1720 APInt TruncatedVal = C->trunc(NarrowType->getScalarSizeInBits());1721 unsigned WideSize = C->getBitWidth();1722 APInt ExtendedVal = ExtKind == TTI::PR_SignExtend1723 ? TruncatedVal.sext(WideSize)1724 : TruncatedVal.zext(WideSize);1725 return ExtendedVal == *C;1726}1727 1728TargetTransformInfo::OperandValueInfo1729VPCostContext::getOperandInfo(VPValue *V) const {1730 if (!V->isLiveIn())1731 return {};1732 1733 return TTI::getOperandInfo(V->getLiveInIRValue());1734}1735 1736InstructionCost VPCostContext::getScalarizationOverhead(1737 Type *ResultTy, ArrayRef<const VPValue *> Operands, ElementCount VF,1738 bool AlwaysIncludeReplicatingR) {1739 if (VF.isScalar())1740 return 0;1741 1742 assert(!VF.isScalable() &&1743 "Scalarization overhead not supported for scalable vectors");1744 1745 InstructionCost ScalarizationCost = 0;1746 // Compute the cost of scalarizing the result if needed.1747 if (!ResultTy->isVoidTy()) {1748 for (Type *VectorTy :1749 to_vector(getContainedTypes(toVectorizedTy(ResultTy, VF)))) {1750 ScalarizationCost += TTI.getScalarizationOverhead(1751 cast<VectorType>(VectorTy), APInt::getAllOnes(VF.getFixedValue()),1752 /*Insert=*/true,1753 /*Extract=*/false, CostKind);1754 }1755 }1756 // Compute the cost of scalarizing the operands, skipping ones that do not1757 // require extraction/scalarization and do not incur any overhead.1758 SmallPtrSet<const VPValue *, 4> UniqueOperands;1759 SmallVector<Type *> Tys;1760 for (auto *Op : Operands) {1761 if (Op->isLiveIn() ||1762 (!AlwaysIncludeReplicatingR &&1763 isa<VPReplicateRecipe, VPPredInstPHIRecipe>(Op)) ||1764 (isa<VPReplicateRecipe>(Op) &&1765 cast<VPReplicateRecipe>(Op)->getOpcode() == Instruction::Load) ||1766 !UniqueOperands.insert(Op).second)1767 continue;1768 Tys.push_back(toVectorizedTy(Types.inferScalarType(Op), VF));1769 }1770 return ScalarizationCost +1771 TTI.getOperandsScalarizationOverhead(Tys, CostKind);1772}1773