4995 lines · cpp
1//===-- VPlanTransforms.cpp - Utility VPlan to VPlan transforms -----------===//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 file implements a set of utility VPlan to VPlan transformations.11///12//===----------------------------------------------------------------------===//13 14#include "VPlanTransforms.h"15#include "VPRecipeBuilder.h"16#include "VPlan.h"17#include "VPlanAnalysis.h"18#include "VPlanCFG.h"19#include "VPlanDominatorTree.h"20#include "VPlanHelpers.h"21#include "VPlanPatternMatch.h"22#include "VPlanUtils.h"23#include "VPlanVerifier.h"24#include "llvm/ADT/APInt.h"25#include "llvm/ADT/PostOrderIterator.h"26#include "llvm/ADT/STLExtras.h"27#include "llvm/ADT/SetOperations.h"28#include "llvm/ADT/SetVector.h"29#include "llvm/ADT/SmallPtrSet.h"30#include "llvm/ADT/TypeSwitch.h"31#include "llvm/Analysis/IVDescriptors.h"32#include "llvm/Analysis/InstSimplifyFolder.h"33#include "llvm/Analysis/LoopInfo.h"34#include "llvm/Analysis/MemoryLocation.h"35#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"36#include "llvm/Analysis/ScopedNoAliasAA.h"37#include "llvm/Analysis/VectorUtils.h"38#include "llvm/IR/Intrinsics.h"39#include "llvm/IR/MDBuilder.h"40#include "llvm/IR/Metadata.h"41#include "llvm/Support/Casting.h"42#include "llvm/Support/TypeSize.h"43#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"44 45using namespace llvm;46using namespace VPlanPatternMatch;47 48bool VPlanTransforms::tryToConvertVPInstructionsToVPRecipes(49 VPlan &Plan,50 function_ref<const InductionDescriptor *(PHINode *)>51 GetIntOrFpInductionDescriptor,52 const TargetLibraryInfo &TLI) {53 54 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> RPOT(55 Plan.getVectorLoopRegion());56 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {57 // Skip blocks outside region58 if (!VPBB->getParent())59 break;60 VPRecipeBase *Term = VPBB->getTerminator();61 auto EndIter = Term ? Term->getIterator() : VPBB->end();62 // Introduce each ingredient into VPlan.63 for (VPRecipeBase &Ingredient :64 make_early_inc_range(make_range(VPBB->begin(), EndIter))) {65 66 VPValue *VPV = Ingredient.getVPSingleValue();67 if (!VPV->getUnderlyingValue())68 continue;69 70 Instruction *Inst = cast<Instruction>(VPV->getUnderlyingValue());71 72 VPRecipeBase *NewRecipe = nullptr;73 if (auto *PhiR = dyn_cast<VPPhi>(&Ingredient)) {74 auto *Phi = cast<PHINode>(PhiR->getUnderlyingValue());75 const auto *II = GetIntOrFpInductionDescriptor(Phi);76 if (!II) {77 NewRecipe = new VPWidenPHIRecipe(Phi, nullptr, PhiR->getDebugLoc());78 for (VPValue *Op : PhiR->operands())79 NewRecipe->addOperand(Op);80 } else {81 VPValue *Start = Plan.getOrAddLiveIn(II->getStartValue());82 VPValue *Step =83 vputils::getOrCreateVPValueForSCEVExpr(Plan, II->getStep());84 // It is always safe to copy over the NoWrap and FastMath flags. In85 // particular, when folding tail by masking, the masked-off lanes are86 // never used, so it is safe.87 VPIRFlags Flags = vputils::getFlagsFromIndDesc(*II);88 NewRecipe = new VPWidenIntOrFpInductionRecipe(89 Phi, Start, Step, &Plan.getVF(), *II, Flags,90 Ingredient.getDebugLoc());91 }92 } else {93 auto *VPI = cast<VPInstruction>(&Ingredient);94 assert(!isa<PHINode>(Inst) && "phis should be handled above");95 // Create VPWidenMemoryRecipe for loads and stores.96 if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {97 NewRecipe = new VPWidenLoadRecipe(98 *Load, Ingredient.getOperand(0), nullptr /*Mask*/,99 false /*Consecutive*/, false /*Reverse*/, *VPI,100 Ingredient.getDebugLoc());101 } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {102 NewRecipe = new VPWidenStoreRecipe(103 *Store, Ingredient.getOperand(1), Ingredient.getOperand(0),104 nullptr /*Mask*/, false /*Consecutive*/, false /*Reverse*/, *VPI,105 Ingredient.getDebugLoc());106 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {107 NewRecipe = new VPWidenGEPRecipe(GEP, Ingredient.operands(), *VPI,108 Ingredient.getDebugLoc());109 } else if (CallInst *CI = dyn_cast<CallInst>(Inst)) {110 Intrinsic::ID VectorID = getVectorIntrinsicIDForCall(CI, &TLI);111 if (VectorID == Intrinsic::not_intrinsic)112 return false;113 NewRecipe = new VPWidenIntrinsicRecipe(114 *CI, getVectorIntrinsicIDForCall(CI, &TLI),115 drop_end(Ingredient.operands()), CI->getType(), VPIRFlags(*CI),116 *VPI, CI->getDebugLoc());117 } else if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {118 NewRecipe = new VPWidenSelectRecipe(SI, Ingredient.operands(), *VPI,119 *VPI, Ingredient.getDebugLoc());120 } else if (auto *CI = dyn_cast<CastInst>(Inst)) {121 NewRecipe = new VPWidenCastRecipe(122 CI->getOpcode(), Ingredient.getOperand(0), CI->getType(), CI,123 VPIRFlags(*CI), VPIRMetadata(*CI));124 } else {125 NewRecipe = new VPWidenRecipe(*Inst, Ingredient.operands(), *VPI,126 *VPI, Ingredient.getDebugLoc());127 }128 }129 130 NewRecipe->insertBefore(&Ingredient);131 if (NewRecipe->getNumDefinedValues() == 1)132 VPV->replaceAllUsesWith(NewRecipe->getVPSingleValue());133 else134 assert(NewRecipe->getNumDefinedValues() == 0 &&135 "Only recpies with zero or one defined values expected");136 Ingredient.eraseFromParent();137 }138 }139 return true;140}141 142// Check if a load can be hoisted by verifying it doesn't alias with any stores143// in blocks between FirstBB and LastBB using scoped noalias metadata.144static bool canHoistLoadWithNoAliasCheck(VPReplicateRecipe *Load,145 VPBasicBlock *FirstBB,146 VPBasicBlock *LastBB) {147 // Get the load's memory location and check if it aliases with any stores148 // using scoped noalias metadata.149 auto LoadLoc = vputils::getMemoryLocation(*Load);150 if (!LoadLoc || !LoadLoc->AATags.Scope)151 return false;152 153 const AAMDNodes &LoadAA = LoadLoc->AATags;154 for (VPBlockBase *Block = FirstBB; Block;155 Block = Block->getSingleSuccessor()) {156 // This function assumes a simple linear chain of blocks. If there are157 // multiple successors, we would need more complex analysis.158 assert(Block->getNumSuccessors() <= 1 &&159 "Expected at most one successor in block chain");160 auto *VPBB = cast<VPBasicBlock>(Block);161 for (VPRecipeBase &R : *VPBB) {162 if (R.mayWriteToMemory()) {163 auto Loc = vputils::getMemoryLocation(R);164 // Bail out if we can't get the location or if the scoped noalias165 // metadata indicates potential aliasing.166 if (!Loc || ScopedNoAliasAAResult::mayAliasInScopes(167 LoadAA.Scope, Loc->AATags.NoAlias))168 return false;169 }170 }171 if (Block == LastBB)172 break;173 }174 return true;175}176 177/// Return true if we do not know how to (mechanically) hoist or sink \p R out178/// of a loop region.179static bool cannotHoistOrSinkRecipe(const VPRecipeBase &R) {180 // Assumes don't alias anything or throw; as long as they're guaranteed to181 // execute, they're safe to hoist.182 if (match(&R, m_Intrinsic<Intrinsic::assume>()))183 return false;184 185 // TODO: Relax checks in the future, e.g. we could also hoist reads, if their186 // memory location is not modified in the vector loop.187 if (R.mayHaveSideEffects() || R.mayReadFromMemory() || R.isPhi())188 return true;189 190 // Allocas cannot be hoisted.191 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);192 return RepR && RepR->getOpcode() == Instruction::Alloca;193}194 195static bool sinkScalarOperands(VPlan &Plan) {196 auto Iter = vp_depth_first_deep(Plan.getEntry());197 bool ScalarVFOnly = Plan.hasScalarVFOnly();198 bool Changed = false;199 200 SetVector<std::pair<VPBasicBlock *, VPSingleDefRecipe *>> WorkList;201 auto InsertIfValidSinkCandidate = [ScalarVFOnly, &WorkList](202 VPBasicBlock *SinkTo, VPValue *Op) {203 auto *Candidate =204 dyn_cast_or_null<VPSingleDefRecipe>(Op->getDefiningRecipe());205 if (!Candidate)206 return;207 208 // We only know how to sink VPReplicateRecipes and VPScalarIVStepsRecipes209 // for now.210 if (!isa<VPReplicateRecipe, VPScalarIVStepsRecipe>(Candidate))211 return;212 213 if (Candidate->getParent() == SinkTo || cannotHoistOrSinkRecipe(*Candidate))214 return;215 216 if (auto *RepR = dyn_cast<VPReplicateRecipe>(Candidate))217 if (!ScalarVFOnly && RepR->isSingleScalar())218 return;219 220 WorkList.insert({SinkTo, Candidate});221 };222 223 // First, collect the operands of all recipes in replicate blocks as seeds for224 // sinking.225 for (VPRegionBlock *VPR : VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)) {226 VPBasicBlock *EntryVPBB = VPR->getEntryBasicBlock();227 if (!VPR->isReplicator() || EntryVPBB->getSuccessors().size() != 2)228 continue;229 VPBasicBlock *VPBB = cast<VPBasicBlock>(EntryVPBB->getSuccessors().front());230 if (VPBB->getSingleSuccessor() != VPR->getExitingBasicBlock())231 continue;232 for (auto &Recipe : *VPBB)233 for (VPValue *Op : Recipe.operands())234 InsertIfValidSinkCandidate(VPBB, Op);235 }236 237 // Try to sink each replicate or scalar IV steps recipe in the worklist.238 for (unsigned I = 0; I != WorkList.size(); ++I) {239 VPBasicBlock *SinkTo;240 VPSingleDefRecipe *SinkCandidate;241 std::tie(SinkTo, SinkCandidate) = WorkList[I];242 243 // All recipe users of SinkCandidate must be in the same block SinkTo or all244 // users outside of SinkTo must only use the first lane of SinkCandidate. In245 // the latter case, we need to duplicate SinkCandidate.246 auto UsersOutsideSinkTo =247 make_filter_range(SinkCandidate->users(), [SinkTo](VPUser *U) {248 return cast<VPRecipeBase>(U)->getParent() != SinkTo;249 });250 if (any_of(UsersOutsideSinkTo, [SinkCandidate](VPUser *U) {251 return !U->usesFirstLaneOnly(SinkCandidate);252 }))253 continue;254 bool NeedsDuplicating = !UsersOutsideSinkTo.empty();255 256 if (NeedsDuplicating) {257 if (ScalarVFOnly)258 continue;259 VPSingleDefRecipe *Clone;260 if (auto *SinkCandidateRepR =261 dyn_cast<VPReplicateRecipe>(SinkCandidate)) {262 // TODO: Handle converting to uniform recipes as separate transform,263 // then cloning should be sufficient here.264 Instruction *I = SinkCandidate->getUnderlyingInstr();265 Clone = new VPReplicateRecipe(I, SinkCandidate->operands(), true,266 nullptr /*Mask*/, *SinkCandidateRepR,267 *SinkCandidateRepR);268 // TODO: add ".cloned" suffix to name of Clone's VPValue.269 } else {270 Clone = SinkCandidate->clone();271 }272 273 Clone->insertBefore(SinkCandidate);274 SinkCandidate->replaceUsesWithIf(Clone, [SinkTo](VPUser &U, unsigned) {275 return cast<VPRecipeBase>(&U)->getParent() != SinkTo;276 });277 }278 SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi());279 for (VPValue *Op : SinkCandidate->operands())280 InsertIfValidSinkCandidate(SinkTo, Op);281 Changed = true;282 }283 return Changed;284}285 286/// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return287/// the mask.288static VPValue *getPredicatedMask(VPRegionBlock *R) {289 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());290 if (!EntryBB || EntryBB->size() != 1 ||291 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))292 return nullptr;293 294 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);295}296 297/// If \p R is a triangle region, return the 'then' block of the triangle.298static VPBasicBlock *getPredicatedThenBlock(VPRegionBlock *R) {299 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());300 if (EntryBB->getNumSuccessors() != 2)301 return nullptr;302 303 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);304 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);305 if (!Succ0 || !Succ1)306 return nullptr;307 308 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)309 return nullptr;310 if (Succ0->getSingleSuccessor() == Succ1)311 return Succ0;312 if (Succ1->getSingleSuccessor() == Succ0)313 return Succ1;314 return nullptr;315}316 317// Merge replicate regions in their successor region, if a replicate region318// is connected to a successor replicate region with the same predicate by a319// single, empty VPBasicBlock.320static bool mergeReplicateRegionsIntoSuccessors(VPlan &Plan) {321 SmallPtrSet<VPRegionBlock *, 4> TransformedRegions;322 323 // Collect replicate regions followed by an empty block, followed by another324 // replicate region with matching masks to process front. This is to avoid325 // iterator invalidation issues while merging regions.326 SmallVector<VPRegionBlock *, 8> WorkList;327 for (VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(328 vp_depth_first_deep(Plan.getEntry()))) {329 if (!Region1->isReplicator())330 continue;331 auto *MiddleBasicBlock =332 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());333 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())334 continue;335 336 auto *Region2 =337 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());338 if (!Region2 || !Region2->isReplicator())339 continue;340 341 VPValue *Mask1 = getPredicatedMask(Region1);342 VPValue *Mask2 = getPredicatedMask(Region2);343 if (!Mask1 || Mask1 != Mask2)344 continue;345 346 assert(Mask1 && Mask2 && "both region must have conditions");347 WorkList.push_back(Region1);348 }349 350 // Move recipes from Region1 to its successor region, if both are triangles.351 for (VPRegionBlock *Region1 : WorkList) {352 if (TransformedRegions.contains(Region1))353 continue;354 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());355 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());356 357 VPBasicBlock *Then1 = getPredicatedThenBlock(Region1);358 VPBasicBlock *Then2 = getPredicatedThenBlock(Region2);359 if (!Then1 || !Then2)360 continue;361 362 // Note: No fusion-preventing memory dependencies are expected in either363 // region. Such dependencies should be rejected during earlier dependence364 // checks, which guarantee accesses can be re-ordered for vectorization.365 //366 // Move recipes to the successor region.367 for (VPRecipeBase &ToMove : make_early_inc_range(reverse(*Then1)))368 ToMove.moveBefore(*Then2, Then2->getFirstNonPhi());369 370 auto *Merge1 = cast<VPBasicBlock>(Then1->getSingleSuccessor());371 auto *Merge2 = cast<VPBasicBlock>(Then2->getSingleSuccessor());372 373 // Move VPPredInstPHIRecipes from the merge block to the successor region's374 // merge block. Update all users inside the successor region to use the375 // original values.376 for (VPRecipeBase &Phi1ToMove : make_early_inc_range(reverse(*Merge1))) {377 VPValue *PredInst1 =378 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);379 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();380 Phi1ToMoveV->replaceUsesWithIf(PredInst1, [Then2](VPUser &U, unsigned) {381 return cast<VPRecipeBase>(&U)->getParent() == Then2;382 });383 384 // Remove phi recipes that are unused after merging the regions.385 if (Phi1ToMove.getVPSingleValue()->getNumUsers() == 0) {386 Phi1ToMove.eraseFromParent();387 continue;388 }389 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());390 }391 392 // Remove the dead recipes in Region1's entry block.393 for (VPRecipeBase &R :394 make_early_inc_range(reverse(*Region1->getEntryBasicBlock())))395 R.eraseFromParent();396 397 // Finally, remove the first region.398 for (VPBlockBase *Pred : make_early_inc_range(Region1->getPredecessors())) {399 VPBlockUtils::disconnectBlocks(Pred, Region1);400 VPBlockUtils::connectBlocks(Pred, MiddleBasicBlock);401 }402 VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock);403 TransformedRegions.insert(Region1);404 }405 406 return !TransformedRegions.empty();407}408 409static VPRegionBlock *createReplicateRegion(VPReplicateRecipe *PredRecipe,410 VPlan &Plan) {411 Instruction *Instr = PredRecipe->getUnderlyingInstr();412 // Build the triangular if-then region.413 std::string RegionName = (Twine("pred.") + Instr->getOpcodeName()).str();414 assert(Instr->getParent() && "Predicated instruction not in any basic block");415 auto *BlockInMask = PredRecipe->getMask();416 auto *MaskDef = BlockInMask->getDefiningRecipe();417 auto *BOMRecipe = new VPBranchOnMaskRecipe(418 BlockInMask, MaskDef ? MaskDef->getDebugLoc() : DebugLoc::getUnknown());419 auto *Entry =420 Plan.createVPBasicBlock(Twine(RegionName) + ".entry", BOMRecipe);421 422 // Replace predicated replicate recipe with a replicate recipe without a423 // mask but in the replicate region.424 auto *RecipeWithoutMask = new VPReplicateRecipe(425 PredRecipe->getUnderlyingInstr(), drop_end(PredRecipe->operands()),426 PredRecipe->isSingleScalar(), nullptr /*Mask*/, *PredRecipe, *PredRecipe,427 PredRecipe->getDebugLoc());428 auto *Pred =429 Plan.createVPBasicBlock(Twine(RegionName) + ".if", RecipeWithoutMask);430 431 VPPredInstPHIRecipe *PHIRecipe = nullptr;432 if (PredRecipe->getNumUsers() != 0) {433 PHIRecipe = new VPPredInstPHIRecipe(RecipeWithoutMask,434 RecipeWithoutMask->getDebugLoc());435 PredRecipe->replaceAllUsesWith(PHIRecipe);436 PHIRecipe->setOperand(0, RecipeWithoutMask);437 }438 PredRecipe->eraseFromParent();439 auto *Exiting =440 Plan.createVPBasicBlock(Twine(RegionName) + ".continue", PHIRecipe);441 VPRegionBlock *Region =442 Plan.createReplicateRegion(Entry, Exiting, RegionName);443 444 // Note: first set Entry as region entry and then connect successors starting445 // from it in order, to propagate the "parent" of each VPBasicBlock.446 VPBlockUtils::insertTwoBlocksAfter(Pred, Exiting, Entry);447 VPBlockUtils::connectBlocks(Pred, Exiting);448 449 return Region;450}451 452static void addReplicateRegions(VPlan &Plan) {453 SmallVector<VPReplicateRecipe *> WorkList;454 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(455 vp_depth_first_deep(Plan.getEntry()))) {456 for (VPRecipeBase &R : *VPBB)457 if (auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {458 if (RepR->isPredicated())459 WorkList.push_back(RepR);460 }461 }462 463 unsigned BBNum = 0;464 for (VPReplicateRecipe *RepR : WorkList) {465 VPBasicBlock *CurrentBlock = RepR->getParent();466 VPBasicBlock *SplitBlock = CurrentBlock->splitAt(RepR->getIterator());467 468 BasicBlock *OrigBB = RepR->getUnderlyingInstr()->getParent();469 SplitBlock->setName(470 OrigBB->hasName() ? OrigBB->getName() + "." + Twine(BBNum++) : "");471 // Record predicated instructions for above packing optimizations.472 VPRegionBlock *Region = createReplicateRegion(RepR, Plan);473 Region->setParent(CurrentBlock->getParent());474 VPBlockUtils::insertOnEdge(CurrentBlock, SplitBlock, Region);475 476 VPRegionBlock *ParentRegion = Region->getParent();477 if (ParentRegion && ParentRegion->getExiting() == CurrentBlock)478 ParentRegion->setExiting(SplitBlock);479 }480}481 482/// Remove redundant VPBasicBlocks by merging them into their predecessor if483/// the predecessor has a single successor.484static bool mergeBlocksIntoPredecessors(VPlan &Plan) {485 SmallVector<VPBasicBlock *> WorkList;486 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(487 vp_depth_first_deep(Plan.getEntry()))) {488 // Don't fold the blocks in the skeleton of the Plan into their single489 // predecessors for now.490 // TODO: Remove restriction once more of the skeleton is modeled in VPlan.491 if (!VPBB->getParent())492 continue;493 auto *PredVPBB =494 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());495 if (!PredVPBB || PredVPBB->getNumSuccessors() != 1 ||496 isa<VPIRBasicBlock>(PredVPBB))497 continue;498 WorkList.push_back(VPBB);499 }500 501 for (VPBasicBlock *VPBB : WorkList) {502 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());503 for (VPRecipeBase &R : make_early_inc_range(*VPBB))504 R.moveBefore(*PredVPBB, PredVPBB->end());505 VPBlockUtils::disconnectBlocks(PredVPBB, VPBB);506 auto *ParentRegion = VPBB->getParent();507 if (ParentRegion && ParentRegion->getExiting() == VPBB)508 ParentRegion->setExiting(PredVPBB);509 for (auto *Succ : to_vector(VPBB->successors())) {510 VPBlockUtils::disconnectBlocks(VPBB, Succ);511 VPBlockUtils::connectBlocks(PredVPBB, Succ);512 }513 // VPBB is now dead and will be cleaned up when the plan gets destroyed.514 }515 return !WorkList.empty();516}517 518void VPlanTransforms::createAndOptimizeReplicateRegions(VPlan &Plan) {519 // Convert masked VPReplicateRecipes to if-then region blocks.520 addReplicateRegions(Plan);521 522 bool ShouldSimplify = true;523 while (ShouldSimplify) {524 ShouldSimplify = sinkScalarOperands(Plan);525 ShouldSimplify |= mergeReplicateRegionsIntoSuccessors(Plan);526 ShouldSimplify |= mergeBlocksIntoPredecessors(Plan);527 }528}529 530/// Remove redundant casts of inductions.531///532/// Such redundant casts are casts of induction variables that can be ignored,533/// because we already proved that the casted phi is equal to the uncasted phi534/// in the vectorized loop. There is no need to vectorize the cast - the same535/// value can be used for both the phi and casts in the vector loop.536static void removeRedundantInductionCasts(VPlan &Plan) {537 for (auto &Phi : Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {538 auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);539 if (!IV || IV->getTruncInst())540 continue;541 542 // A sequence of IR Casts has potentially been recorded for IV, which543 // *must be bypassed* when the IV is vectorized, because the vectorized IV544 // will produce the desired casted value. This sequence forms a def-use545 // chain and is provided in reverse order, ending with the cast that uses546 // the IV phi. Search for the recipe of the last cast in the chain and547 // replace it with the original IV. Note that only the final cast is548 // expected to have users outside the cast-chain and the dead casts left549 // over will be cleaned up later.550 ArrayRef<Instruction *> Casts = IV->getInductionDescriptor().getCastInsts();551 VPValue *FindMyCast = IV;552 for (Instruction *IRCast : reverse(Casts)) {553 VPSingleDefRecipe *FoundUserCast = nullptr;554 for (auto *U : FindMyCast->users()) {555 auto *UserCast = dyn_cast<VPSingleDefRecipe>(U);556 if (UserCast && UserCast->getUnderlyingValue() == IRCast) {557 FoundUserCast = UserCast;558 break;559 }560 }561 FindMyCast = FoundUserCast;562 }563 FindMyCast->replaceAllUsesWith(IV);564 }565}566 567/// Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV568/// recipe, if it exists.569static void removeRedundantCanonicalIVs(VPlan &Plan) {570 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();571 VPCanonicalIVPHIRecipe *CanonicalIV = LoopRegion->getCanonicalIV();572 VPWidenCanonicalIVRecipe *WidenNewIV = nullptr;573 for (VPUser *U : CanonicalIV->users()) {574 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);575 if (WidenNewIV)576 break;577 }578 579 if (!WidenNewIV)580 return;581 582 VPBasicBlock *HeaderVPBB = LoopRegion->getEntryBasicBlock();583 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {584 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);585 586 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical())587 continue;588 589 // Replace WidenNewIV with WidenOriginalIV if WidenOriginalIV provides590 // everything WidenNewIV's users need. That is, WidenOriginalIV will591 // generate a vector phi or all users of WidenNewIV demand the first lane592 // only.593 if (!vputils::onlyScalarValuesUsed(WidenOriginalIV) ||594 vputils::onlyFirstLaneUsed(WidenNewIV)) {595 // We are replacing a wide canonical iv with a suitable wide induction.596 // This is used to compute header mask, hence all lanes will be used and597 // we need to drop wrap flags only applying to lanes guranteed to execute598 // in the original scalar loop.599 WidenOriginalIV->dropPoisonGeneratingFlags();600 WidenNewIV->replaceAllUsesWith(WidenOriginalIV);601 WidenNewIV->eraseFromParent();602 return;603 }604 }605}606 607/// Returns true if \p R is dead and can be removed.608static bool isDeadRecipe(VPRecipeBase &R) {609 // Do remove conditional assume instructions as their conditions may be610 // flattened.611 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);612 bool IsConditionalAssume = RepR && RepR->isPredicated() &&613 match(RepR, m_Intrinsic<Intrinsic::assume>());614 if (IsConditionalAssume)615 return true;616 617 if (R.mayHaveSideEffects())618 return false;619 620 // Recipe is dead if no user keeps the recipe alive.621 return all_of(R.definedValues(),622 [](VPValue *V) { return V->getNumUsers() == 0; });623}624 625void VPlanTransforms::removeDeadRecipes(VPlan &Plan) {626 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(627 vp_post_order_deep(Plan.getEntry()))) {628 // The recipes in the block are processed in reverse order, to catch chains629 // of dead recipes.630 for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) {631 if (isDeadRecipe(R)) {632 R.eraseFromParent();633 continue;634 }635 636 // Check if R is a dead VPPhi <-> update cycle and remove it.637 auto *PhiR = dyn_cast<VPPhi>(&R);638 if (!PhiR || PhiR->getNumOperands() != 2)639 continue;640 VPUser *PhiUser = PhiR->getSingleUser();641 if (!PhiUser)642 continue;643 VPValue *Incoming = PhiR->getOperand(1);644 if (PhiUser != Incoming->getDefiningRecipe() ||645 Incoming->getNumUsers() != 1)646 continue;647 PhiR->replaceAllUsesWith(PhiR->getOperand(0));648 PhiR->eraseFromParent();649 Incoming->getDefiningRecipe()->eraseFromParent();650 }651 }652}653 654static VPScalarIVStepsRecipe *655createScalarIVSteps(VPlan &Plan, InductionDescriptor::InductionKind Kind,656 Instruction::BinaryOps InductionOpcode,657 FPMathOperator *FPBinOp, Instruction *TruncI,658 VPValue *StartV, VPValue *Step, DebugLoc DL,659 VPBuilder &Builder) {660 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();661 VPBasicBlock *HeaderVPBB = LoopRegion->getEntryBasicBlock();662 VPCanonicalIVPHIRecipe *CanonicalIV = LoopRegion->getCanonicalIV();663 VPSingleDefRecipe *BaseIV = Builder.createDerivedIV(664 Kind, FPBinOp, StartV, CanonicalIV, Step, "offset.idx");665 666 // Truncate base induction if needed.667 VPTypeAnalysis TypeInfo(Plan);668 Type *ResultTy = TypeInfo.inferScalarType(BaseIV);669 if (TruncI) {670 Type *TruncTy = TruncI->getType();671 assert(ResultTy->getScalarSizeInBits() > TruncTy->getScalarSizeInBits() &&672 "Not truncating.");673 assert(ResultTy->isIntegerTy() && "Truncation requires an integer type");674 BaseIV = Builder.createScalarCast(Instruction::Trunc, BaseIV, TruncTy, DL);675 ResultTy = TruncTy;676 }677 678 // Truncate step if needed.679 Type *StepTy = TypeInfo.inferScalarType(Step);680 if (ResultTy != StepTy) {681 assert(StepTy->getScalarSizeInBits() > ResultTy->getScalarSizeInBits() &&682 "Not truncating.");683 assert(StepTy->isIntegerTy() && "Truncation requires an integer type");684 auto *VecPreheader =685 cast<VPBasicBlock>(HeaderVPBB->getSingleHierarchicalPredecessor());686 VPBuilder::InsertPointGuard Guard(Builder);687 Builder.setInsertPoint(VecPreheader);688 Step = Builder.createScalarCast(Instruction::Trunc, Step, ResultTy, DL);689 }690 return Builder.createScalarIVSteps(InductionOpcode, FPBinOp, BaseIV, Step,691 &Plan.getVF(), DL);692}693 694static SmallVector<VPUser *> collectUsersRecursively(VPValue *V) {695 SetVector<VPUser *> Users(llvm::from_range, V->users());696 for (unsigned I = 0; I != Users.size(); ++I) {697 VPRecipeBase *Cur = cast<VPRecipeBase>(Users[I]);698 if (isa<VPHeaderPHIRecipe>(Cur))699 continue;700 for (VPValue *V : Cur->definedValues())701 Users.insert_range(V->users());702 }703 return Users.takeVector();704}705 706/// Scalarize a VPWidenPointerInductionRecipe by replacing it with a PtrAdd707/// (IndStart, ScalarIVSteps (0, Step)). This is used when the recipe only708/// generates scalar values.709static VPValue *710scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV,711 VPlan &Plan, VPBuilder &Builder) {712 const InductionDescriptor &ID = PtrIV->getInductionDescriptor();713 VPValue *StartV = Plan.getConstantInt(ID.getStep()->getType(), 0);714 VPValue *StepV = PtrIV->getOperand(1);715 VPScalarIVStepsRecipe *Steps = createScalarIVSteps(716 Plan, InductionDescriptor::IK_IntInduction, Instruction::Add, nullptr,717 nullptr, StartV, StepV, PtrIV->getDebugLoc(), Builder);718 719 return Builder.createPtrAdd(PtrIV->getStartValue(), Steps,720 PtrIV->getDebugLoc(), "next.gep");721}722 723/// Legalize VPWidenPointerInductionRecipe, by replacing it with a PtrAdd724/// (IndStart, ScalarIVSteps (0, Step)) if only its scalar values are used, as725/// VPWidenPointerInductionRecipe will generate vectors only. If some users726/// require vectors while other require scalars, the scalar uses need to extract727/// the scalars from the generated vectors (Note that this is different to how728/// int/fp inductions are handled). Legalize extract-from-ends using uniform729/// VPReplicateRecipe of wide inductions to use regular VPReplicateRecipe, so730/// the correct end value is available. Also optimize731/// VPWidenIntOrFpInductionRecipe, if any of its users needs scalar values, by732/// providing them scalar steps built on the canonical scalar IV and update the733/// original IV's users. This is an optional optimization to reduce the needs of734/// vector extracts.735static void legalizeAndOptimizeInductions(VPlan &Plan) {736 VPBasicBlock *HeaderVPBB = Plan.getVectorLoopRegion()->getEntryBasicBlock();737 bool HasOnlyVectorVFs = !Plan.hasScalarVFOnly();738 VPBuilder Builder(HeaderVPBB, HeaderVPBB->getFirstNonPhi());739 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {740 auto *PhiR = dyn_cast<VPWidenInductionRecipe>(&Phi);741 if (!PhiR)742 continue;743 744 // Try to narrow wide and replicating recipes to uniform recipes, based on745 // VPlan analysis.746 // TODO: Apply to all recipes in the future, to replace legacy uniformity747 // analysis.748 auto Users = collectUsersRecursively(PhiR);749 for (VPUser *U : reverse(Users)) {750 auto *Def = dyn_cast<VPRecipeWithIRFlags>(U);751 auto *RepR = dyn_cast<VPReplicateRecipe>(U);752 // Skip recipes that shouldn't be narrowed.753 if (!Def || !isa<VPReplicateRecipe, VPWidenRecipe>(Def) ||754 Def->getNumUsers() == 0 || !Def->getUnderlyingValue() ||755 (RepR && (RepR->isSingleScalar() || RepR->isPredicated())))756 continue;757 758 // Skip recipes that may have other lanes than their first used.759 if (!vputils::isSingleScalar(Def) && !vputils::onlyFirstLaneUsed(Def))760 continue;761 762 auto *Clone = new VPReplicateRecipe(Def->getUnderlyingInstr(),763 Def->operands(), /*IsUniform*/ true,764 /*Mask*/ nullptr, /*Flags*/ *Def);765 Clone->insertAfter(Def);766 Def->replaceAllUsesWith(Clone);767 }768 769 // Replace wide pointer inductions which have only their scalars used by770 // PtrAdd(IndStart, ScalarIVSteps (0, Step)).771 if (auto *PtrIV = dyn_cast<VPWidenPointerInductionRecipe>(&Phi)) {772 if (!Plan.hasScalarVFOnly() &&773 !PtrIV->onlyScalarsGenerated(Plan.hasScalableVF()))774 continue;775 776 VPValue *PtrAdd = scalarizeVPWidenPointerInduction(PtrIV, Plan, Builder);777 PtrIV->replaceAllUsesWith(PtrAdd);778 continue;779 }780 781 // Replace widened induction with scalar steps for users that only use782 // scalars.783 auto *WideIV = cast<VPWidenIntOrFpInductionRecipe>(&Phi);784 if (HasOnlyVectorVFs && none_of(WideIV->users(), [WideIV](VPUser *U) {785 return U->usesScalars(WideIV);786 }))787 continue;788 789 const InductionDescriptor &ID = WideIV->getInductionDescriptor();790 VPScalarIVStepsRecipe *Steps = createScalarIVSteps(791 Plan, ID.getKind(), ID.getInductionOpcode(),792 dyn_cast_or_null<FPMathOperator>(ID.getInductionBinOp()),793 WideIV->getTruncInst(), WideIV->getStartValue(), WideIV->getStepValue(),794 WideIV->getDebugLoc(), Builder);795 796 // Update scalar users of IV to use Step instead.797 if (!HasOnlyVectorVFs) {798 assert(!Plan.hasScalableVF() &&799 "plans containing a scalar VF cannot also include scalable VFs");800 WideIV->replaceAllUsesWith(Steps);801 } else {802 bool HasScalableVF = Plan.hasScalableVF();803 WideIV->replaceUsesWithIf(Steps,804 [WideIV, HasScalableVF](VPUser &U, unsigned) {805 if (HasScalableVF)806 return U.usesFirstLaneOnly(WideIV);807 return U.usesScalars(WideIV);808 });809 }810 }811}812 813/// Check if \p VPV is an untruncated wide induction, either before or after the814/// increment. If so return the header IV (before the increment), otherwise815/// return null.816static VPWidenInductionRecipe *getOptimizableIVOf(VPValue *VPV,817 ScalarEvolution &SE) {818 auto *WideIV = dyn_cast<VPWidenInductionRecipe>(VPV);819 if (WideIV) {820 // VPV itself is a wide induction, separately compute the end value for exit821 // users if it is not a truncated IV.822 auto *IntOrFpIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(WideIV);823 return (IntOrFpIV && IntOrFpIV->getTruncInst()) ? nullptr : WideIV;824 }825 826 // Check if VPV is an optimizable induction increment.827 VPRecipeBase *Def = VPV->getDefiningRecipe();828 if (!Def || Def->getNumOperands() != 2)829 return nullptr;830 WideIV = dyn_cast<VPWidenInductionRecipe>(Def->getOperand(0));831 if (!WideIV)832 WideIV = dyn_cast<VPWidenInductionRecipe>(Def->getOperand(1));833 if (!WideIV)834 return nullptr;835 836 auto IsWideIVInc = [&]() {837 auto &ID = WideIV->getInductionDescriptor();838 839 // Check if VPV increments the induction by the induction step.840 VPValue *IVStep = WideIV->getStepValue();841 switch (ID.getInductionOpcode()) {842 case Instruction::Add:843 return match(VPV, m_c_Add(m_Specific(WideIV), m_Specific(IVStep)));844 case Instruction::FAdd:845 return match(VPV, m_c_Binary<Instruction::FAdd>(m_Specific(WideIV),846 m_Specific(IVStep)));847 case Instruction::FSub:848 return match(VPV, m_Binary<Instruction::FSub>(m_Specific(WideIV),849 m_Specific(IVStep)));850 case Instruction::Sub: {851 // IVStep will be the negated step of the subtraction. Check if Step == -1852 // * IVStep.853 VPValue *Step;854 if (!match(VPV, m_Sub(m_VPValue(), m_VPValue(Step))))855 return false;856 const SCEV *IVStepSCEV = vputils::getSCEVExprForVPValue(IVStep, SE);857 const SCEV *StepSCEV = vputils::getSCEVExprForVPValue(Step, SE);858 return !isa<SCEVCouldNotCompute>(IVStepSCEV) &&859 !isa<SCEVCouldNotCompute>(StepSCEV) &&860 IVStepSCEV == SE.getNegativeSCEV(StepSCEV);861 }862 default:863 return ID.getKind() == InductionDescriptor::IK_PtrInduction &&864 match(VPV, m_GetElementPtr(m_Specific(WideIV),865 m_Specific(WideIV->getStepValue())));866 }867 llvm_unreachable("should have been covered by switch above");868 };869 return IsWideIVInc() ? WideIV : nullptr;870}871 872/// Attempts to optimize the induction variable exit values for users in the873/// early exit block.874static VPValue *optimizeEarlyExitInductionUser(VPlan &Plan,875 VPTypeAnalysis &TypeInfo,876 VPBlockBase *PredVPBB,877 VPValue *Op,878 ScalarEvolution &SE) {879 VPValue *Incoming, *Mask;880 if (!match(Op, m_ExtractLane(m_FirstActiveLane(m_VPValue(Mask)),881 m_VPValue(Incoming))))882 return nullptr;883 884 auto *WideIV = getOptimizableIVOf(Incoming, SE);885 if (!WideIV)886 return nullptr;887 888 auto *WideIntOrFp = dyn_cast<VPWidenIntOrFpInductionRecipe>(WideIV);889 if (WideIntOrFp && WideIntOrFp->getTruncInst())890 return nullptr;891 892 // Calculate the final index.893 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();894 auto *CanonicalIV = LoopRegion->getCanonicalIV();895 Type *CanonicalIVType = LoopRegion->getCanonicalIVType();896 VPBuilder B(cast<VPBasicBlock>(PredVPBB));897 898 DebugLoc DL = cast<VPInstruction>(Op)->getDebugLoc();899 VPValue *FirstActiveLane =900 B.createNaryOp(VPInstruction::FirstActiveLane, Mask, DL);901 Type *FirstActiveLaneType = TypeInfo.inferScalarType(FirstActiveLane);902 FirstActiveLane = B.createScalarZExtOrTrunc(FirstActiveLane, CanonicalIVType,903 FirstActiveLaneType, DL);904 VPValue *EndValue =905 B.createNaryOp(Instruction::Add, {CanonicalIV, FirstActiveLane}, DL);906 907 // `getOptimizableIVOf()` always returns the pre-incremented IV, so if it908 // changed it means the exit is using the incremented value, so we need to909 // add the step.910 if (Incoming != WideIV) {911 VPValue *One = Plan.getConstantInt(CanonicalIVType, 1);912 EndValue = B.createNaryOp(Instruction::Add, {EndValue, One}, DL);913 }914 915 if (!WideIntOrFp || !WideIntOrFp->isCanonical()) {916 const InductionDescriptor &ID = WideIV->getInductionDescriptor();917 VPValue *Start = WideIV->getStartValue();918 VPValue *Step = WideIV->getStepValue();919 EndValue = B.createDerivedIV(920 ID.getKind(), dyn_cast_or_null<FPMathOperator>(ID.getInductionBinOp()),921 Start, EndValue, Step);922 }923 924 return EndValue;925}926 927/// Attempts to optimize the induction variable exit values for users in the928/// exit block coming from the latch in the original scalar loop.929static VPValue *optimizeLatchExitInductionUser(930 VPlan &Plan, VPTypeAnalysis &TypeInfo, VPBlockBase *PredVPBB, VPValue *Op,931 DenseMap<VPValue *, VPValue *> &EndValues, ScalarEvolution &SE) {932 VPValue *Incoming;933 if (!match(Op, m_ExtractLastElement(m_VPValue(Incoming))))934 return nullptr;935 936 auto *WideIV = getOptimizableIVOf(Incoming, SE);937 if (!WideIV)938 return nullptr;939 940 VPValue *EndValue = EndValues.lookup(WideIV);941 assert(EndValue && "end value must have been pre-computed");942 943 // `getOptimizableIVOf()` always returns the pre-incremented IV, so if it944 // changed it means the exit is using the incremented value, so we don't945 // need to subtract the step.946 if (Incoming != WideIV)947 return EndValue;948 949 // Otherwise, subtract the step from the EndValue.950 VPBuilder B(cast<VPBasicBlock>(PredVPBB)->getTerminator());951 VPValue *Step = WideIV->getStepValue();952 Type *ScalarTy = TypeInfo.inferScalarType(WideIV);953 if (ScalarTy->isIntegerTy())954 return B.createNaryOp(Instruction::Sub, {EndValue, Step}, {}, "ind.escape");955 if (ScalarTy->isPointerTy()) {956 Type *StepTy = TypeInfo.inferScalarType(Step);957 auto *Zero = Plan.getConstantInt(StepTy, 0);958 return B.createPtrAdd(EndValue,959 B.createNaryOp(Instruction::Sub, {Zero, Step}),960 DebugLoc::getUnknown(), "ind.escape");961 }962 if (ScalarTy->isFloatingPointTy()) {963 const auto &ID = WideIV->getInductionDescriptor();964 return B.createNaryOp(965 ID.getInductionBinOp()->getOpcode() == Instruction::FAdd966 ? Instruction::FSub967 : Instruction::FAdd,968 {EndValue, Step}, {ID.getInductionBinOp()->getFastMathFlags()});969 }970 llvm_unreachable("all possible induction types must be handled");971 return nullptr;972}973 974void VPlanTransforms::optimizeInductionExitUsers(975 VPlan &Plan, DenseMap<VPValue *, VPValue *> &EndValues,976 ScalarEvolution &SE) {977 VPBlockBase *MiddleVPBB = Plan.getMiddleBlock();978 VPTypeAnalysis TypeInfo(Plan);979 for (VPIRBasicBlock *ExitVPBB : Plan.getExitBlocks()) {980 for (VPRecipeBase &R : ExitVPBB->phis()) {981 auto *ExitIRI = cast<VPIRPhi>(&R);982 983 for (auto [Idx, PredVPBB] : enumerate(ExitVPBB->getPredecessors())) {984 VPValue *Escape = nullptr;985 if (PredVPBB == MiddleVPBB)986 Escape = optimizeLatchExitInductionUser(Plan, TypeInfo, PredVPBB,987 ExitIRI->getOperand(Idx),988 EndValues, SE);989 else990 Escape = optimizeEarlyExitInductionUser(Plan, TypeInfo, PredVPBB,991 ExitIRI->getOperand(Idx), SE);992 if (Escape)993 ExitIRI->setOperand(Idx, Escape);994 }995 }996 }997}998 999/// Remove redundant EpxandSCEVRecipes in \p Plan's entry block by replacing1000/// them with already existing recipes expanding the same SCEV expression.1001static void removeRedundantExpandSCEVRecipes(VPlan &Plan) {1002 DenseMap<const SCEV *, VPValue *> SCEV2VPV;1003 1004 for (VPRecipeBase &R :1005 make_early_inc_range(*Plan.getEntry()->getEntryBasicBlock())) {1006 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);1007 if (!ExpR)1008 continue;1009 1010 const auto &[V, Inserted] = SCEV2VPV.try_emplace(ExpR->getSCEV(), ExpR);1011 if (Inserted)1012 continue;1013 ExpR->replaceAllUsesWith(V->second);1014 ExpR->eraseFromParent();1015 }1016}1017 1018static void recursivelyDeleteDeadRecipes(VPValue *V) {1019 SmallVector<VPValue *> WorkList;1020 SmallPtrSet<VPValue *, 8> Seen;1021 WorkList.push_back(V);1022 1023 while (!WorkList.empty()) {1024 VPValue *Cur = WorkList.pop_back_val();1025 if (!Seen.insert(Cur).second)1026 continue;1027 VPRecipeBase *R = Cur->getDefiningRecipe();1028 if (!R)1029 continue;1030 if (!isDeadRecipe(*R))1031 continue;1032 append_range(WorkList, R->operands());1033 R->eraseFromParent();1034 }1035}1036 1037/// Get any instruction opcode or intrinsic ID data embedded in recipe \p R.1038/// Returns an optional pair, where the first element indicates whether it is1039/// an intrinsic ID.1040static std::optional<std::pair<bool, unsigned>>1041getOpcodeOrIntrinsicID(const VPSingleDefRecipe *R) {1042 return TypeSwitch<const VPSingleDefRecipe *,1043 std::optional<std::pair<bool, unsigned>>>(R)1044 .Case<VPInstruction, VPWidenRecipe, VPWidenCastRecipe,1045 VPWidenSelectRecipe, VPWidenGEPRecipe, VPReplicateRecipe>(1046 [](auto *I) { return std::make_pair(false, I->getOpcode()); })1047 .Case<VPWidenIntrinsicRecipe>([](auto *I) {1048 return std::make_pair(true, I->getVectorIntrinsicID());1049 })1050 .Case<VPVectorPointerRecipe, VPPredInstPHIRecipe>([](auto *I) {1051 // For recipes that do not directly map to LLVM IR instructions,1052 // assign opcodes after the last VPInstruction opcode (which is also1053 // after the last IR Instruction opcode), based on the VPDefID.1054 return std::make_pair(false,1055 VPInstruction::OpsEnd + 1 + I->getVPDefID());1056 })1057 .Default([](auto *) { return std::nullopt; });1058}1059 1060/// Try to fold \p R using InstSimplifyFolder. Will succeed and return a1061/// non-nullptr VPValue for a handled opcode or intrinsic ID if corresponding \p1062/// Operands are foldable live-ins.1063static VPValue *tryToFoldLiveIns(VPSingleDefRecipe &R,1064 ArrayRef<VPValue *> Operands,1065 const DataLayout &DL,1066 VPTypeAnalysis &TypeInfo) {1067 auto OpcodeOrIID = getOpcodeOrIntrinsicID(&R);1068 if (!OpcodeOrIID)1069 return nullptr;1070 1071 SmallVector<Value *, 4> Ops;1072 for (VPValue *Op : Operands) {1073 if (!Op->isLiveIn() || !Op->getLiveInIRValue())1074 return nullptr;1075 Ops.push_back(Op->getLiveInIRValue());1076 }1077 1078 auto FoldToIRValue = [&]() -> Value * {1079 InstSimplifyFolder Folder(DL);1080 if (OpcodeOrIID->first) {1081 if (R.getNumOperands() != 2)1082 return nullptr;1083 unsigned ID = OpcodeOrIID->second;1084 return Folder.FoldBinaryIntrinsic(ID, Ops[0], Ops[1],1085 TypeInfo.inferScalarType(&R));1086 }1087 unsigned Opcode = OpcodeOrIID->second;1088 if (Instruction::isBinaryOp(Opcode))1089 return Folder.FoldBinOp(static_cast<Instruction::BinaryOps>(Opcode),1090 Ops[0], Ops[1]);1091 if (Instruction::isCast(Opcode))1092 return Folder.FoldCast(static_cast<Instruction::CastOps>(Opcode), Ops[0],1093 TypeInfo.inferScalarType(R.getVPSingleValue()));1094 switch (Opcode) {1095 case VPInstruction::LogicalAnd:1096 return Folder.FoldSelect(Ops[0], Ops[1],1097 ConstantInt::getNullValue(Ops[1]->getType()));1098 case VPInstruction::Not:1099 return Folder.FoldBinOp(Instruction::BinaryOps::Xor, Ops[0],1100 Constant::getAllOnesValue(Ops[0]->getType()));1101 case Instruction::Select:1102 return Folder.FoldSelect(Ops[0], Ops[1], Ops[2]);1103 case Instruction::ICmp:1104 case Instruction::FCmp:1105 return Folder.FoldCmp(cast<VPRecipeWithIRFlags>(R).getPredicate(), Ops[0],1106 Ops[1]);1107 case Instruction::GetElementPtr: {1108 auto &RFlags = cast<VPRecipeWithIRFlags>(R);1109 auto *GEP = cast<GetElementPtrInst>(RFlags.getUnderlyingInstr());1110 return Folder.FoldGEP(GEP->getSourceElementType(), Ops[0],1111 drop_begin(Ops), RFlags.getGEPNoWrapFlags());1112 }1113 case VPInstruction::PtrAdd:1114 case VPInstruction::WidePtrAdd:1115 return Folder.FoldGEP(IntegerType::getInt8Ty(TypeInfo.getContext()),1116 Ops[0], Ops[1],1117 cast<VPRecipeWithIRFlags>(R).getGEPNoWrapFlags());1118 // An extract of a live-in is an extract of a broadcast, so return the1119 // broadcasted element.1120 case Instruction::ExtractElement:1121 assert(!Ops[0]->getType()->isVectorTy() && "Live-ins should be scalar");1122 return Ops[0];1123 }1124 return nullptr;1125 };1126 1127 if (Value *V = FoldToIRValue())1128 return R.getParent()->getPlan()->getOrAddLiveIn(V);1129 return nullptr;1130}1131 1132/// Try to simplify VPSingleDefRecipe \p Def.1133static void simplifyRecipe(VPSingleDefRecipe *Def, VPTypeAnalysis &TypeInfo) {1134 VPlan *Plan = Def->getParent()->getPlan();1135 1136 // Simplification of live-in IR values for SingleDef recipes using1137 // InstSimplifyFolder.1138 const DataLayout &DL =1139 Plan->getScalarHeader()->getIRBasicBlock()->getDataLayout();1140 if (VPValue *V = tryToFoldLiveIns(*Def, Def->operands(), DL, TypeInfo))1141 return Def->replaceAllUsesWith(V);1142 1143 // Fold PredPHI LiveIn -> LiveIn.1144 if (auto *PredPHI = dyn_cast<VPPredInstPHIRecipe>(Def)) {1145 VPValue *Op = PredPHI->getOperand(0);1146 if (Op->isLiveIn())1147 PredPHI->replaceAllUsesWith(Op);1148 }1149 1150 VPBuilder Builder(Def);1151 VPValue *A;1152 if (match(Def, m_Trunc(m_ZExtOrSExt(m_VPValue(A))))) {1153 Type *TruncTy = TypeInfo.inferScalarType(Def);1154 Type *ATy = TypeInfo.inferScalarType(A);1155 if (TruncTy == ATy) {1156 Def->replaceAllUsesWith(A);1157 } else {1158 // Don't replace a scalarizing recipe with a widened cast.1159 if (isa<VPReplicateRecipe>(Def))1160 return;1161 if (ATy->getScalarSizeInBits() < TruncTy->getScalarSizeInBits()) {1162 1163 unsigned ExtOpcode = match(Def->getOperand(0), m_SExt(m_VPValue()))1164 ? Instruction::SExt1165 : Instruction::ZExt;1166 auto *Ext = Builder.createWidenCast(Instruction::CastOps(ExtOpcode), A,1167 TruncTy);1168 if (auto *UnderlyingExt = Def->getOperand(0)->getUnderlyingValue()) {1169 // UnderlyingExt has distinct return type, used to retain legacy cost.1170 Ext->setUnderlyingValue(UnderlyingExt);1171 }1172 Def->replaceAllUsesWith(Ext);1173 } else if (ATy->getScalarSizeInBits() > TruncTy->getScalarSizeInBits()) {1174 auto *Trunc = Builder.createWidenCast(Instruction::Trunc, A, TruncTy);1175 Def->replaceAllUsesWith(Trunc);1176 }1177 }1178#ifndef NDEBUG1179 // Verify that the cached type info is for both A and its users is still1180 // accurate by comparing it to freshly computed types.1181 VPTypeAnalysis TypeInfo2(*Plan);1182 assert(TypeInfo.inferScalarType(A) == TypeInfo2.inferScalarType(A));1183 for (VPUser *U : A->users()) {1184 auto *R = cast<VPRecipeBase>(U);1185 for (VPValue *VPV : R->definedValues())1186 assert(TypeInfo.inferScalarType(VPV) == TypeInfo2.inferScalarType(VPV));1187 }1188#endif1189 }1190 1191 // Simplify (X && Y) || (X && !Y) -> X.1192 // TODO: Split up into simpler, modular combines: (X && Y) || (X && Z) into X1193 // && (Y || Z) and (X || !X) into true. This requires queuing newly created1194 // recipes to be visited during simplification.1195 VPValue *X, *Y, *Z;1196 if (match(Def,1197 m_c_BinaryOr(m_LogicalAnd(m_VPValue(X), m_VPValue(Y)),1198 m_LogicalAnd(m_Deferred(X), m_Not(m_Deferred(Y)))))) {1199 Def->replaceAllUsesWith(X);1200 Def->eraseFromParent();1201 return;1202 }1203 1204 // x | 1 -> 11205 if (match(Def, m_c_BinaryOr(m_VPValue(X), m_AllOnes())))1206 return Def->replaceAllUsesWith(Def->getOperand(Def->getOperand(0) == X));1207 1208 // x | 0 -> x1209 if (match(Def, m_c_BinaryOr(m_VPValue(X), m_ZeroInt())))1210 return Def->replaceAllUsesWith(X);1211 1212 // x & 0 -> 01213 if (match(Def, m_c_BinaryAnd(m_VPValue(X), m_ZeroInt())))1214 return Def->replaceAllUsesWith(Def->getOperand(Def->getOperand(0) == X));1215 1216 // x && false -> false1217 if (match(Def, m_LogicalAnd(m_VPValue(X), m_False())))1218 return Def->replaceAllUsesWith(Def->getOperand(1));1219 1220 // (x && y) || (x && z) -> x && (y || z)1221 if (match(Def, m_c_BinaryOr(m_LogicalAnd(m_VPValue(X), m_VPValue(Y)),1222 m_LogicalAnd(m_Deferred(X), m_VPValue(Z)))) &&1223 // Simplify only if one of the operands has one use to avoid creating an1224 // extra recipe.1225 (!Def->getOperand(0)->hasMoreThanOneUniqueUser() ||1226 !Def->getOperand(1)->hasMoreThanOneUniqueUser()))1227 return Def->replaceAllUsesWith(1228 Builder.createLogicalAnd(X, Builder.createOr(Y, Z)));1229 1230 // x && !x -> 01231 if (match(Def, m_LogicalAnd(m_VPValue(X), m_Not(m_Deferred(X)))))1232 return Def->replaceAllUsesWith(Plan->getFalse());1233 1234 if (match(Def, m_Select(m_VPValue(), m_VPValue(X), m_Deferred(X))))1235 return Def->replaceAllUsesWith(X);1236 1237 // select !c, x, y -> select c, y, x1238 VPValue *C;1239 if (match(Def, m_Select(m_Not(m_VPValue(C)), m_VPValue(X), m_VPValue(Y)))) {1240 Def->setOperand(0, C);1241 Def->setOperand(1, Y);1242 Def->setOperand(2, X);1243 return;1244 }1245 1246 // Reassociate (x && y) && z -> x && (y && z) if x has multiple users. With1247 // tail folding it is likely that x is a header mask and can be simplified1248 // further.1249 if (match(Def, m_LogicalAnd(m_LogicalAnd(m_VPValue(X), m_VPValue(Y)),1250 m_VPValue(Z))) &&1251 X->hasMoreThanOneUniqueUser())1252 return Def->replaceAllUsesWith(1253 Builder.createLogicalAnd(X, Builder.createLogicalAnd(Y, Z)));1254 1255 if (match(Def, m_c_Add(m_VPValue(A), m_ZeroInt())))1256 return Def->replaceAllUsesWith(A);1257 1258 if (match(Def, m_c_Mul(m_VPValue(A), m_One())))1259 return Def->replaceAllUsesWith(A);1260 1261 if (match(Def, m_c_Mul(m_VPValue(A), m_ZeroInt())))1262 return Def->replaceAllUsesWith(1263 Def->getOperand(0) == A ? Def->getOperand(1) : Def->getOperand(0));1264 1265 if (match(Def, m_Not(m_VPValue(A)))) {1266 if (match(A, m_Not(m_VPValue(A))))1267 return Def->replaceAllUsesWith(A);1268 1269 // Try to fold Not into compares by adjusting the predicate in-place.1270 CmpPredicate Pred;1271 if (match(A, m_Cmp(Pred, m_VPValue(), m_VPValue()))) {1272 auto *Cmp = cast<VPRecipeWithIRFlags>(A);1273 if (all_of(Cmp->users(),1274 match_fn(m_CombineOr(1275 m_Not(m_Specific(Cmp)),1276 m_Select(m_Specific(Cmp), m_VPValue(), m_VPValue()))))) {1277 Cmp->setPredicate(CmpInst::getInversePredicate(Pred));1278 for (VPUser *U : to_vector(Cmp->users())) {1279 auto *R = cast<VPSingleDefRecipe>(U);1280 if (match(R, m_Select(m_Specific(Cmp), m_VPValue(X), m_VPValue(Y)))) {1281 // select (cmp pred), x, y -> select (cmp inv_pred), y, x1282 R->setOperand(1, Y);1283 R->setOperand(2, X);1284 } else {1285 // not (cmp pred) -> cmp inv_pred1286 assert(match(R, m_Not(m_Specific(Cmp))) && "Unexpected user");1287 R->replaceAllUsesWith(Cmp);1288 }1289 }1290 // If Cmp doesn't have a debug location, use the one from the negation,1291 // to preserve the location.1292 if (!Cmp->getDebugLoc() && Def->getDebugLoc())1293 Cmp->setDebugLoc(Def->getDebugLoc());1294 }1295 }1296 }1297 1298 // Fold any-of (fcmp uno %A, %A), (fcmp uno %B, %B), ... ->1299 // any-of (fcmp uno %A, %B), ...1300 if (match(Def, m_AnyOf())) {1301 SmallVector<VPValue *, 4> NewOps;1302 VPRecipeBase *UnpairedCmp = nullptr;1303 for (VPValue *Op : Def->operands()) {1304 VPValue *X;1305 if (Op->getNumUsers() > 1 ||1306 !match(Op, m_SpecificCmp(CmpInst::FCMP_UNO, m_VPValue(X),1307 m_Deferred(X)))) {1308 NewOps.push_back(Op);1309 } else if (!UnpairedCmp) {1310 UnpairedCmp = Op->getDefiningRecipe();1311 } else {1312 NewOps.push_back(Builder.createFCmp(CmpInst::FCMP_UNO,1313 UnpairedCmp->getOperand(0), X));1314 UnpairedCmp = nullptr;1315 }1316 }1317 1318 if (UnpairedCmp)1319 NewOps.push_back(UnpairedCmp->getVPSingleValue());1320 1321 if (NewOps.size() < Def->getNumOperands()) {1322 VPValue *NewAnyOf = Builder.createNaryOp(VPInstruction::AnyOf, NewOps);1323 return Def->replaceAllUsesWith(NewAnyOf);1324 }1325 }1326 1327 // Fold (fcmp uno %X, %X) or (fcmp uno %Y, %Y) -> fcmp uno %X, %Y1328 // This is useful for fmax/fmin without fast-math flags, where we need to1329 // check if any operand is NaN.1330 if (match(Def, m_BinaryOr(m_SpecificCmp(CmpInst::FCMP_UNO, m_VPValue(X),1331 m_Deferred(X)),1332 m_SpecificCmp(CmpInst::FCMP_UNO, m_VPValue(Y),1333 m_Deferred(Y))))) {1334 VPValue *NewCmp = Builder.createFCmp(CmpInst::FCMP_UNO, X, Y);1335 return Def->replaceAllUsesWith(NewCmp);1336 }1337 1338 // Remove redundant DerviedIVs, that is 0 + A * 1 -> A and 0 + 0 * x -> 0.1339 if ((match(Def, m_DerivedIV(m_ZeroInt(), m_VPValue(A), m_One())) ||1340 match(Def, m_DerivedIV(m_ZeroInt(), m_ZeroInt(), m_VPValue()))) &&1341 TypeInfo.inferScalarType(Def->getOperand(1)) ==1342 TypeInfo.inferScalarType(Def))1343 return Def->replaceAllUsesWith(Def->getOperand(1));1344 1345 if (match(Def, m_VPInstruction<VPInstruction::WideIVStep>(m_VPValue(X),1346 m_One()))) {1347 Type *WideStepTy = TypeInfo.inferScalarType(Def);1348 if (TypeInfo.inferScalarType(X) != WideStepTy)1349 X = Builder.createWidenCast(Instruction::Trunc, X, WideStepTy);1350 Def->replaceAllUsesWith(X);1351 return;1352 }1353 1354 // For i1 vp.merges produced by AnyOf reductions:1355 // vp.merge true, (or x, y), x, evl -> vp.merge y, true, x, evl1356 if (match(Def, m_Intrinsic<Intrinsic::vp_merge>(m_True(), m_VPValue(A),1357 m_VPValue(X), m_VPValue())) &&1358 match(A, m_c_BinaryOr(m_Specific(X), m_VPValue(Y))) &&1359 TypeInfo.inferScalarType(Def)->isIntegerTy(1)) {1360 Def->setOperand(1, Def->getOperand(0));1361 Def->setOperand(0, Y);1362 return;1363 }1364 1365 if (auto *Phi = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(Def)) {1366 if (Phi->getOperand(0) == Phi->getOperand(1))1367 Phi->replaceAllUsesWith(Phi->getOperand(0));1368 return;1369 }1370 1371 // Look through ExtractLastElement (BuildVector ....).1372 if (match(Def, m_CombineOr(m_ExtractLastElement(m_BuildVector()),1373 m_ExtractLastLanePerPart(m_BuildVector())))) {1374 auto *BuildVector = cast<VPInstruction>(Def->getOperand(0));1375 Def->replaceAllUsesWith(1376 BuildVector->getOperand(BuildVector->getNumOperands() - 1));1377 return;1378 }1379 1380 // Look through ExtractPenultimateElement (BuildVector ....).1381 if (match(Def, m_ExtractPenultimateElement(m_BuildVector()))) {1382 auto *BuildVector = cast<VPInstruction>(Def->getOperand(0));1383 Def->replaceAllUsesWith(1384 BuildVector->getOperand(BuildVector->getNumOperands() - 2));1385 return;1386 }1387 1388 uint64_t Idx;1389 if (match(Def, m_ExtractElement(m_BuildVector(), m_ConstantInt(Idx)))) {1390 auto *BuildVector = cast<VPInstruction>(Def->getOperand(0));1391 Def->replaceAllUsesWith(BuildVector->getOperand(Idx));1392 return;1393 }1394 1395 if (match(Def, m_BuildVector()) && all_equal(Def->operands())) {1396 Def->replaceAllUsesWith(1397 Builder.createNaryOp(VPInstruction::Broadcast, Def->getOperand(0)));1398 return;1399 }1400 1401 // Look through broadcast of single-scalar when used as select conditions; in1402 // that case the scalar condition can be used directly.1403 if (match(Def,1404 m_Select(m_Broadcast(m_VPValue(C)), m_VPValue(), m_VPValue()))) {1405 assert(vputils::isSingleScalar(C) &&1406 "broadcast operand must be single-scalar");1407 Def->setOperand(0, C);1408 return;1409 }1410 1411 if (auto *Phi = dyn_cast<VPPhi>(Def)) {1412 if (Phi->getNumOperands() == 1)1413 Phi->replaceAllUsesWith(Phi->getOperand(0));1414 return;1415 }1416 1417 // Some simplifications can only be applied after unrolling. Perform them1418 // below.1419 if (!Plan->isUnrolled())1420 return;1421 1422 // Hoist an invariant increment Y of a phi X, by having X start at Y.1423 if (match(Def, m_c_Add(m_VPValue(X), m_VPValue(Y))) && Y->isLiveIn() &&1424 isa<VPPhi>(X)) {1425 auto *Phi = cast<VPPhi>(X);1426 if (Phi->getOperand(1) != Def && match(Phi->getOperand(0), m_ZeroInt()) &&1427 Phi->getSingleUser() == Def) {1428 Phi->setOperand(0, Y);1429 Def->replaceAllUsesWith(Phi);1430 return;1431 }1432 }1433 1434 // VPVectorPointer for part 0 can be replaced by their start pointer.1435 if (auto *VecPtr = dyn_cast<VPVectorPointerRecipe>(Def)) {1436 if (VecPtr->isFirstPart()) {1437 VecPtr->replaceAllUsesWith(VecPtr->getOperand(0));1438 return;1439 }1440 }1441 1442 // VPScalarIVSteps for part 0 can be replaced by their start value, if only1443 // the first lane is demanded.1444 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(Def)) {1445 if (Steps->isPart0() && vputils::onlyFirstLaneUsed(Steps)) {1446 Steps->replaceAllUsesWith(Steps->getOperand(0));1447 return;1448 }1449 }1450 // Simplify redundant ReductionStartVector recipes after unrolling.1451 VPValue *StartV;1452 if (match(Def, m_VPInstruction<VPInstruction::ReductionStartVector>(1453 m_VPValue(StartV), m_VPValue(), m_VPValue()))) {1454 Def->replaceUsesWithIf(StartV, [](const VPUser &U, unsigned Idx) {1455 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(&U);1456 return PhiR && PhiR->isInLoop();1457 });1458 return;1459 }1460 1461 if (match(Def,1462 m_CombineOr(m_ExtractLastElement(m_Broadcast(m_VPValue(A))),1463 m_ExtractLastLanePerPart(m_Broadcast(m_VPValue(A)))))) {1464 Def->replaceAllUsesWith(A);1465 return;1466 }1467 1468 if (match(Def, m_CombineOr(m_ExtractLastElement(m_VPValue(A)),1469 m_ExtractLastLanePerPart(m_VPValue(A)))) &&1470 ((isa<VPInstruction>(A) && vputils::isSingleScalar(A)) ||1471 (isa<VPReplicateRecipe>(A) &&1472 cast<VPReplicateRecipe>(A)->isSingleScalar())) &&1473 all_of(A->users(),1474 [Def, A](VPUser *U) { return U->usesScalars(A) || Def == U; })) {1475 return Def->replaceAllUsesWith(A);1476 }1477 1478 if (Plan->getUF() == 1 &&1479 match(Def, m_ExtractLastLanePerPart(m_VPValue(A)))) {1480 return Def->replaceAllUsesWith(1481 Builder.createNaryOp(VPInstruction::ExtractLastElement, {A}));1482 }1483}1484 1485void VPlanTransforms::simplifyRecipes(VPlan &Plan) {1486 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> RPOT(1487 Plan.getEntry());1488 VPTypeAnalysis TypeInfo(Plan);1489 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {1490 for (VPRecipeBase &R : make_early_inc_range(*VPBB))1491 if (auto *Def = dyn_cast<VPSingleDefRecipe>(&R))1492 simplifyRecipe(Def, TypeInfo);1493 }1494}1495 1496static void narrowToSingleScalarRecipes(VPlan &Plan) {1497 if (Plan.hasScalarVFOnly())1498 return;1499 1500 // Try to narrow wide and replicating recipes to single scalar recipes,1501 // based on VPlan analysis. Only process blocks in the loop region for now,1502 // without traversing into nested regions, as recipes in replicate regions1503 // cannot be converted yet.1504 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(1505 vp_depth_first_shallow(Plan.getVectorLoopRegion()->getEntry()))) {1506 for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) {1507 if (!isa<VPWidenRecipe, VPWidenSelectRecipe, VPWidenGEPRecipe,1508 VPReplicateRecipe>(&R))1509 continue;1510 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);1511 if (RepR && (RepR->isSingleScalar() || RepR->isPredicated()))1512 continue;1513 1514 auto *RepOrWidenR = cast<VPRecipeWithIRFlags>(&R);1515 if (RepR && isa<StoreInst>(RepR->getUnderlyingInstr()) &&1516 vputils::isSingleScalar(RepR->getOperand(1))) {1517 auto *Clone = new VPReplicateRecipe(1518 RepOrWidenR->getUnderlyingInstr(), RepOrWidenR->operands(),1519 true /*IsSingleScalar*/, nullptr /*Mask*/, *RepR /*Flags*/,1520 *RepR /*Metadata*/, RepR->getDebugLoc());1521 Clone->insertBefore(RepOrWidenR);1522 unsigned ExtractOpc =1523 vputils::isUniformAcrossVFsAndUFs(RepR->getOperand(1))1524 ? VPInstruction::ExtractLastElement1525 : VPInstruction::ExtractLastLanePerPart;1526 auto *Ext = new VPInstruction(ExtractOpc, {Clone->getOperand(0)});1527 Ext->insertBefore(Clone);1528 Clone->setOperand(0, Ext);1529 RepR->eraseFromParent();1530 continue;1531 }1532 1533 // Skip recipes that aren't single scalars.1534 if (!vputils::isSingleScalar(RepOrWidenR))1535 continue;1536 1537 // Skip recipes for which conversion to single-scalar does introduce1538 // additional broadcasts. No extra broadcasts are needed, if either only1539 // the scalars of the recipe are used, or at least one of the operands1540 // would require a broadcast. In the latter case, the single-scalar may1541 // need to be broadcasted, but another broadcast is removed.1542 if (!all_of(RepOrWidenR->users(),1543 [RepOrWidenR](const VPUser *U) {1544 if (auto *VPI = dyn_cast<VPInstruction>(U)) {1545 unsigned Opcode = VPI->getOpcode();1546 if (Opcode == VPInstruction::ExtractLastElement ||1547 Opcode == VPInstruction::ExtractLastLanePerPart ||1548 Opcode == VPInstruction::ExtractPenultimateElement)1549 return true;1550 }1551 1552 return U->usesScalars(RepOrWidenR);1553 }) &&1554 none_of(RepOrWidenR->operands(), [RepOrWidenR](VPValue *Op) {1555 if (Op->getSingleUser() != RepOrWidenR)1556 return false;1557 // Non-constant live-ins require broadcasts, while constants do not1558 // need explicit broadcasts.1559 bool LiveInNeedsBroadcast =1560 Op->isLiveIn() && !isa<Constant>(Op->getLiveInIRValue());1561 auto *OpR = dyn_cast<VPReplicateRecipe>(Op);1562 return LiveInNeedsBroadcast || (OpR && OpR->isSingleScalar());1563 }))1564 continue;1565 1566 auto *Clone = new VPReplicateRecipe(1567 RepOrWidenR->getUnderlyingInstr(), RepOrWidenR->operands(),1568 true /*IsSingleScalar*/, nullptr, *RepOrWidenR);1569 Clone->insertBefore(RepOrWidenR);1570 RepOrWidenR->replaceAllUsesWith(Clone);1571 if (isDeadRecipe(*RepOrWidenR))1572 RepOrWidenR->eraseFromParent();1573 }1574 }1575}1576 1577/// Try to see if all of \p Blend's masks share a common value logically and'ed1578/// and remove it from the masks.1579static void removeCommonBlendMask(VPBlendRecipe *Blend) {1580 if (Blend->isNormalized())1581 return;1582 VPValue *CommonEdgeMask;1583 if (!match(Blend->getMask(0),1584 m_LogicalAnd(m_VPValue(CommonEdgeMask), m_VPValue())))1585 return;1586 for (unsigned I = 0; I < Blend->getNumIncomingValues(); I++)1587 if (!match(Blend->getMask(I),1588 m_LogicalAnd(m_Specific(CommonEdgeMask), m_VPValue())))1589 return;1590 for (unsigned I = 0; I < Blend->getNumIncomingValues(); I++)1591 Blend->setMask(I, Blend->getMask(I)->getDefiningRecipe()->getOperand(1));1592}1593 1594/// Normalize and simplify VPBlendRecipes. Should be run after simplifyRecipes1595/// to make sure the masks are simplified.1596static void simplifyBlends(VPlan &Plan) {1597 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(1598 vp_depth_first_shallow(Plan.getVectorLoopRegion()->getEntry()))) {1599 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {1600 auto *Blend = dyn_cast<VPBlendRecipe>(&R);1601 if (!Blend)1602 continue;1603 1604 removeCommonBlendMask(Blend);1605 1606 // Try to remove redundant blend recipes.1607 SmallPtrSet<VPValue *, 4> UniqueValues;1608 if (Blend->isNormalized() || !match(Blend->getMask(0), m_False()))1609 UniqueValues.insert(Blend->getIncomingValue(0));1610 for (unsigned I = 1; I != Blend->getNumIncomingValues(); ++I)1611 if (!match(Blend->getMask(I), m_False()))1612 UniqueValues.insert(Blend->getIncomingValue(I));1613 1614 if (UniqueValues.size() == 1) {1615 Blend->replaceAllUsesWith(*UniqueValues.begin());1616 Blend->eraseFromParent();1617 continue;1618 }1619 1620 if (Blend->isNormalized())1621 continue;1622 1623 // Normalize the blend so its first incoming value is used as the initial1624 // value with the others blended into it.1625 1626 unsigned StartIndex = 0;1627 for (unsigned I = 0; I != Blend->getNumIncomingValues(); ++I) {1628 // If a value's mask is used only by the blend then is can be deadcoded.1629 // TODO: Find the most expensive mask that can be deadcoded, or a mask1630 // that's used by multiple blends where it can be removed from them all.1631 VPValue *Mask = Blend->getMask(I);1632 if (Mask->getNumUsers() == 1 && !match(Mask, m_False())) {1633 StartIndex = I;1634 break;1635 }1636 }1637 1638 SmallVector<VPValue *, 4> OperandsWithMask;1639 OperandsWithMask.push_back(Blend->getIncomingValue(StartIndex));1640 1641 for (unsigned I = 0; I != Blend->getNumIncomingValues(); ++I) {1642 if (I == StartIndex)1643 continue;1644 OperandsWithMask.push_back(Blend->getIncomingValue(I));1645 OperandsWithMask.push_back(Blend->getMask(I));1646 }1647 1648 auto *NewBlend =1649 new VPBlendRecipe(cast_or_null<PHINode>(Blend->getUnderlyingValue()),1650 OperandsWithMask, Blend->getDebugLoc());1651 NewBlend->insertBefore(&R);1652 1653 VPValue *DeadMask = Blend->getMask(StartIndex);1654 Blend->replaceAllUsesWith(NewBlend);1655 Blend->eraseFromParent();1656 recursivelyDeleteDeadRecipes(DeadMask);1657 1658 /// Simplify BLEND %a, %b, Not(%mask) -> BLEND %b, %a, %mask.1659 VPValue *NewMask;1660 if (NewBlend->getNumOperands() == 3 &&1661 match(NewBlend->getMask(1), m_Not(m_VPValue(NewMask)))) {1662 VPValue *Inc0 = NewBlend->getOperand(0);1663 VPValue *Inc1 = NewBlend->getOperand(1);1664 VPValue *OldMask = NewBlend->getOperand(2);1665 NewBlend->setOperand(0, Inc1);1666 NewBlend->setOperand(1, Inc0);1667 NewBlend->setOperand(2, NewMask);1668 if (OldMask->getNumUsers() == 0)1669 cast<VPInstruction>(OldMask)->eraseFromParent();1670 }1671 }1672 }1673}1674 1675/// Optimize the width of vector induction variables in \p Plan based on a known1676/// constant Trip Count, \p BestVF and \p BestUF.1677static bool optimizeVectorInductionWidthForTCAndVFUF(VPlan &Plan,1678 ElementCount BestVF,1679 unsigned BestUF) {1680 // Only proceed if we have not completely removed the vector region.1681 if (!Plan.getVectorLoopRegion())1682 return false;1683 1684 const APInt *TC;1685 if (!BestVF.isFixed() || !match(Plan.getTripCount(), m_APInt(TC)))1686 return false;1687 1688 // Calculate the minimum power-of-2 bit width that can fit the known TC, VF1689 // and UF. Returns at least 8.1690 auto ComputeBitWidth = [](APInt TC, uint64_t Align) {1691 APInt AlignedTC =1692 Align * APIntOps::RoundingUDiv(TC, APInt(TC.getBitWidth(), Align),1693 APInt::Rounding::UP);1694 APInt MaxVal = AlignedTC - 1;1695 return std::max<unsigned>(PowerOf2Ceil(MaxVal.getActiveBits()), 8);1696 };1697 unsigned NewBitWidth =1698 ComputeBitWidth(*TC, BestVF.getKnownMinValue() * BestUF);1699 1700 LLVMContext &Ctx = Plan.getContext();1701 auto *NewIVTy = IntegerType::get(Ctx, NewBitWidth);1702 1703 bool MadeChange = false;1704 1705 VPBasicBlock *HeaderVPBB = Plan.getVectorLoopRegion()->getEntryBasicBlock();1706 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {1707 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);1708 1709 // Currently only handle canonical IVs as it is trivial to replace the start1710 // and stop values, and we currently only perform the optimization when the1711 // IV has a single use.1712 if (!WideIV || !WideIV->isCanonical() ||1713 WideIV->hasMoreThanOneUniqueUser() ||1714 NewIVTy == WideIV->getScalarType())1715 continue;1716 1717 // Currently only handle cases where the single user is a header-mask1718 // comparison with the backedge-taken-count.1719 VPUser *SingleUser = WideIV->getSingleUser();1720 if (!SingleUser ||1721 !match(SingleUser, m_ICmp(m_Specific(WideIV),1722 m_Broadcast(m_Specific(1723 Plan.getOrCreateBackedgeTakenCount())))))1724 continue;1725 1726 // Update IV operands and comparison bound to use new narrower type.1727 auto *NewStart = Plan.getConstantInt(NewIVTy, 0);1728 WideIV->setStartValue(NewStart);1729 auto *NewStep = Plan.getConstantInt(NewIVTy, 1);1730 WideIV->setStepValue(NewStep);1731 1732 auto *NewBTC = new VPWidenCastRecipe(1733 Instruction::Trunc, Plan.getOrCreateBackedgeTakenCount(), NewIVTy);1734 Plan.getVectorPreheader()->appendRecipe(NewBTC);1735 auto *Cmp = cast<VPInstruction>(WideIV->getSingleUser());1736 Cmp->setOperand(1, NewBTC);1737 1738 MadeChange = true;1739 }1740 1741 return MadeChange;1742}1743 1744/// Return true if \p Cond is known to be true for given \p BestVF and \p1745/// BestUF.1746static bool isConditionTrueViaVFAndUF(VPValue *Cond, VPlan &Plan,1747 ElementCount BestVF, unsigned BestUF,1748 ScalarEvolution &SE) {1749 if (match(Cond, m_BinaryOr(m_VPValue(), m_VPValue())))1750 return any_of(Cond->getDefiningRecipe()->operands(), [&Plan, BestVF, BestUF,1751 &SE](VPValue *C) {1752 return isConditionTrueViaVFAndUF(C, Plan, BestVF, BestUF, SE);1753 });1754 1755 auto *CanIV = Plan.getVectorLoopRegion()->getCanonicalIV();1756 if (!match(Cond, m_SpecificICmp(CmpInst::ICMP_EQ,1757 m_Specific(CanIV->getBackedgeValue()),1758 m_Specific(&Plan.getVectorTripCount()))))1759 return false;1760 1761 // The compare checks CanIV + VFxUF == vector trip count. The vector trip1762 // count is not conveniently available as SCEV so far, so we compare directly1763 // against the original trip count. This is stricter than necessary, as we1764 // will only return true if the trip count == vector trip count.1765 const SCEV *VectorTripCount =1766 vputils::getSCEVExprForVPValue(&Plan.getVectorTripCount(), SE);1767 if (isa<SCEVCouldNotCompute>(VectorTripCount))1768 VectorTripCount = vputils::getSCEVExprForVPValue(Plan.getTripCount(), SE);1769 assert(!isa<SCEVCouldNotCompute>(VectorTripCount) &&1770 "Trip count SCEV must be computable");1771 ElementCount NumElements = BestVF.multiplyCoefficientBy(BestUF);1772 const SCEV *C = SE.getElementCount(VectorTripCount->getType(), NumElements);1773 return SE.isKnownPredicate(CmpInst::ICMP_EQ, VectorTripCount, C);1774}1775 1776/// Try to replace multiple active lane masks used for control flow with1777/// a single, wide active lane mask instruction followed by multiple1778/// extract subvector intrinsics. This applies to the active lane mask1779/// instructions both in the loop and in the preheader.1780/// Incoming values of all ActiveLaneMaskPHIs are updated to use the1781/// new extracts from the first active lane mask, which has it's last1782/// operand (multiplier) set to UF.1783static bool tryToReplaceALMWithWideALM(VPlan &Plan, ElementCount VF,1784 unsigned UF) {1785 if (!EnableWideActiveLaneMask || !VF.isVector() || UF == 1)1786 return false;1787 1788 VPRegionBlock *VectorRegion = Plan.getVectorLoopRegion();1789 VPBasicBlock *ExitingVPBB = VectorRegion->getExitingBasicBlock();1790 auto *Term = &ExitingVPBB->back();1791 1792 using namespace llvm::VPlanPatternMatch;1793 if (!match(Term, m_BranchOnCond(m_Not(m_ActiveLaneMask(1794 m_VPValue(), m_VPValue(), m_VPValue())))))1795 return false;1796 1797 auto *Header = cast<VPBasicBlock>(VectorRegion->getEntry());1798 LLVMContext &Ctx = Plan.getContext();1799 1800 auto ExtractFromALM = [&](VPInstruction *ALM,1801 SmallVectorImpl<VPValue *> &Extracts) {1802 DebugLoc DL = ALM->getDebugLoc();1803 for (unsigned Part = 0; Part < UF; ++Part) {1804 SmallVector<VPValue *> Ops;1805 Ops.append({ALM, Plan.getOrAddLiveIn(1806 ConstantInt::get(IntegerType::getInt64Ty(Ctx),1807 VF.getKnownMinValue() * Part))});1808 auto *Ext =1809 new VPWidenIntrinsicRecipe(Intrinsic::vector_extract, Ops,1810 IntegerType::getInt1Ty(Ctx), {}, {}, DL);1811 Extracts[Part] = Ext;1812 Ext->insertAfter(ALM);1813 }1814 };1815 1816 // Create a list of each active lane mask phi, ordered by unroll part.1817 SmallVector<VPActiveLaneMaskPHIRecipe *> Phis(UF, nullptr);1818 for (VPRecipeBase &R : Header->phis()) {1819 auto *Phi = dyn_cast<VPActiveLaneMaskPHIRecipe>(&R);1820 if (!Phi)1821 continue;1822 VPValue *Index = nullptr;1823 match(Phi->getBackedgeValue(),1824 m_ActiveLaneMask(m_VPValue(Index), m_VPValue(), m_VPValue()));1825 assert(Index && "Expected index from ActiveLaneMask instruction");1826 1827 uint64_t Part;1828 if (match(Index,1829 m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>(1830 m_VPValue(), m_ConstantInt(Part))))1831 Phis[Part] = Phi;1832 else1833 // Anything other than a CanonicalIVIncrementForPart is part 01834 Phis[0] = Phi;1835 }1836 1837 assert(all_of(Phis, [](VPActiveLaneMaskPHIRecipe *Phi) { return Phi; }) &&1838 "Expected one VPActiveLaneMaskPHIRecipe for each unroll part");1839 1840 auto *EntryALM = cast<VPInstruction>(Phis[0]->getStartValue());1841 auto *LoopALM = cast<VPInstruction>(Phis[0]->getBackedgeValue());1842 1843 assert((EntryALM->getOpcode() == VPInstruction::ActiveLaneMask &&1844 LoopALM->getOpcode() == VPInstruction::ActiveLaneMask) &&1845 "Expected incoming values of Phi to be ActiveLaneMasks");1846 1847 // When using wide lane masks, the return type of the get.active.lane.mask1848 // intrinsic is VF x UF (last operand).1849 VPValue *ALMMultiplier = Plan.getConstantInt(64, UF);1850 EntryALM->setOperand(2, ALMMultiplier);1851 LoopALM->setOperand(2, ALMMultiplier);1852 1853 // Create UF x extract vectors and insert into preheader.1854 SmallVector<VPValue *> EntryExtracts(UF);1855 ExtractFromALM(EntryALM, EntryExtracts);1856 1857 // Create UF x extract vectors and insert before the loop compare & branch,1858 // updating the compare to use the first extract.1859 SmallVector<VPValue *> LoopExtracts(UF);1860 ExtractFromALM(LoopALM, LoopExtracts);1861 VPInstruction *Not = cast<VPInstruction>(Term->getOperand(0));1862 Not->setOperand(0, LoopExtracts[0]);1863 1864 // Update the incoming values of active lane mask phis.1865 for (unsigned Part = 0; Part < UF; ++Part) {1866 Phis[Part]->setStartValue(EntryExtracts[Part]);1867 Phis[Part]->setBackedgeValue(LoopExtracts[Part]);1868 }1869 1870 return true;1871}1872 1873/// Try to simplify the branch condition of \p Plan. This may restrict the1874/// resulting plan to \p BestVF and \p BestUF.1875static bool simplifyBranchConditionForVFAndUF(VPlan &Plan, ElementCount BestVF,1876 unsigned BestUF,1877 PredicatedScalarEvolution &PSE) {1878 VPRegionBlock *VectorRegion = Plan.getVectorLoopRegion();1879 VPBasicBlock *ExitingVPBB = VectorRegion->getExitingBasicBlock();1880 auto *Term = &ExitingVPBB->back();1881 VPValue *Cond;1882 ScalarEvolution &SE = *PSE.getSE();1883 if (match(Term, m_BranchOnCount()) ||1884 match(Term, m_BranchOnCond(m_Not(m_ActiveLaneMask(1885 m_VPValue(), m_VPValue(), m_VPValue()))))) {1886 // Try to simplify the branch condition if VectorTC <= VF * UF when the1887 // latch terminator is BranchOnCount or BranchOnCond(Not(ActiveLaneMask)).1888 const SCEV *VectorTripCount =1889 vputils::getSCEVExprForVPValue(&Plan.getVectorTripCount(), SE);1890 if (isa<SCEVCouldNotCompute>(VectorTripCount))1891 VectorTripCount = vputils::getSCEVExprForVPValue(Plan.getTripCount(), SE);1892 assert(!isa<SCEVCouldNotCompute>(VectorTripCount) &&1893 "Trip count SCEV must be computable");1894 ElementCount NumElements = BestVF.multiplyCoefficientBy(BestUF);1895 const SCEV *C = SE.getElementCount(VectorTripCount->getType(), NumElements);1896 if (!SE.isKnownPredicate(CmpInst::ICMP_ULE, VectorTripCount, C))1897 return false;1898 } else if (match(Term, m_BranchOnCond(m_VPValue(Cond)))) {1899 // For BranchOnCond, check if we can prove the condition to be true using VF1900 // and UF.1901 if (!isConditionTrueViaVFAndUF(Cond, Plan, BestVF, BestUF, SE))1902 return false;1903 } else {1904 return false;1905 }1906 1907 // The vector loop region only executes once. If possible, completely remove1908 // the region, otherwise replace the terminator controlling the latch with1909 // (BranchOnCond true).1910 // TODO: VPWidenIntOrFpInductionRecipe is only partially supported; add1911 // support for other non-canonical widen induction recipes (e.g.,1912 // VPWidenPointerInductionRecipe).1913 auto *Header = cast<VPBasicBlock>(VectorRegion->getEntry());1914 if (all_of(Header->phis(), [](VPRecipeBase &Phi) {1915 if (auto *R = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi))1916 return R->isCanonical();1917 return isa<VPCanonicalIVPHIRecipe, VPEVLBasedIVPHIRecipe,1918 VPFirstOrderRecurrencePHIRecipe, VPPhi>(&Phi);1919 })) {1920 for (VPRecipeBase &HeaderR : make_early_inc_range(Header->phis())) {1921 if (auto *R = dyn_cast<VPWidenIntOrFpInductionRecipe>(&HeaderR)) {1922 VPBuilder Builder(Plan.getVectorPreheader());1923 VPValue *StepV = Builder.createNaryOp(VPInstruction::StepVector, {},1924 R->getScalarType());1925 HeaderR.getVPSingleValue()->replaceAllUsesWith(StepV);1926 HeaderR.eraseFromParent();1927 continue;1928 }1929 auto *Phi = cast<VPPhiAccessors>(&HeaderR);1930 HeaderR.getVPSingleValue()->replaceAllUsesWith(Phi->getIncomingValue(0));1931 HeaderR.eraseFromParent();1932 }1933 1934 VPBlockBase *Preheader = VectorRegion->getSinglePredecessor();1935 VPBlockBase *Exit = VectorRegion->getSingleSuccessor();1936 VPBlockUtils::disconnectBlocks(Preheader, VectorRegion);1937 VPBlockUtils::disconnectBlocks(VectorRegion, Exit);1938 1939 for (VPBlockBase *B : vp_depth_first_shallow(VectorRegion->getEntry()))1940 B->setParent(nullptr);1941 1942 VPBlockUtils::connectBlocks(Preheader, Header);1943 VPBlockUtils::connectBlocks(ExitingVPBB, Exit);1944 VPlanTransforms::simplifyRecipes(Plan);1945 } else {1946 // The vector region contains header phis for which we cannot remove the1947 // loop region yet.1948 auto *BOC = new VPInstruction(VPInstruction::BranchOnCond, {Plan.getTrue()},1949 {}, {}, Term->getDebugLoc());1950 ExitingVPBB->appendRecipe(BOC);1951 }1952 1953 Term->eraseFromParent();1954 1955 return true;1956}1957 1958/// From the definition of llvm.experimental.get.vector.length,1959/// VPInstruction::ExplicitVectorLength(%AVL) = %AVL when %AVL <= VF.1960static bool simplifyKnownEVL(VPlan &Plan, ElementCount VF,1961 PredicatedScalarEvolution &PSE) {1962 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(1963 vp_depth_first_deep(Plan.getEntry()))) {1964 for (VPRecipeBase &R : *VPBB) {1965 VPValue *AVL;1966 if (!match(&R, m_EVL(m_VPValue(AVL))))1967 continue;1968 1969 ScalarEvolution &SE = *PSE.getSE();1970 const SCEV *AVLSCEV = vputils::getSCEVExprForVPValue(AVL, SE);1971 if (isa<SCEVCouldNotCompute>(AVLSCEV))1972 continue;1973 const SCEV *VFSCEV = SE.getElementCount(AVLSCEV->getType(), VF);1974 if (!SE.isKnownPredicate(CmpInst::ICMP_ULE, AVLSCEV, VFSCEV))1975 continue;1976 1977 VPValue *Trunc = VPBuilder(&R).createScalarZExtOrTrunc(1978 AVL, Type::getInt32Ty(Plan.getContext()), AVLSCEV->getType(),1979 R.getDebugLoc());1980 R.getVPSingleValue()->replaceAllUsesWith(Trunc);1981 return true;1982 }1983 }1984 return false;1985}1986 1987void VPlanTransforms::optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,1988 unsigned BestUF,1989 PredicatedScalarEvolution &PSE) {1990 assert(Plan.hasVF(BestVF) && "BestVF is not available in Plan");1991 assert(Plan.hasUF(BestUF) && "BestUF is not available in Plan");1992 1993 bool MadeChange = tryToReplaceALMWithWideALM(Plan, BestVF, BestUF);1994 MadeChange |= simplifyBranchConditionForVFAndUF(Plan, BestVF, BestUF, PSE);1995 MadeChange |= optimizeVectorInductionWidthForTCAndVFUF(Plan, BestVF, BestUF);1996 MadeChange |= simplifyKnownEVL(Plan, BestVF, PSE);1997 1998 if (MadeChange) {1999 Plan.setVF(BestVF);2000 assert(Plan.getUF() == BestUF && "BestUF must match the Plan's UF");2001 }2002}2003 2004/// Sink users of \p FOR after the recipe defining the previous value \p2005/// Previous of the recurrence. \returns true if all users of \p FOR could be2006/// re-arranged as needed or false if it is not possible.2007static bool2008sinkRecurrenceUsersAfterPrevious(VPFirstOrderRecurrencePHIRecipe *FOR,2009 VPRecipeBase *Previous,2010 VPDominatorTree &VPDT) {2011 // Collect recipes that need sinking.2012 SmallVector<VPRecipeBase *> WorkList;2013 SmallPtrSet<VPRecipeBase *, 8> Seen;2014 Seen.insert(Previous);2015 auto TryToPushSinkCandidate = [&](VPRecipeBase *SinkCandidate) {2016 // The previous value must not depend on the users of the recurrence phi. In2017 // that case, FOR is not a fixed order recurrence.2018 if (SinkCandidate == Previous)2019 return false;2020 2021 if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||2022 !Seen.insert(SinkCandidate).second ||2023 VPDT.properlyDominates(Previous, SinkCandidate))2024 return true;2025 2026 if (cannotHoistOrSinkRecipe(*SinkCandidate))2027 return false;2028 2029 WorkList.push_back(SinkCandidate);2030 return true;2031 };2032 2033 // Recursively sink users of FOR after Previous.2034 WorkList.push_back(FOR);2035 for (unsigned I = 0; I != WorkList.size(); ++I) {2036 VPRecipeBase *Current = WorkList[I];2037 assert(Current->getNumDefinedValues() == 1 &&2038 "only recipes with a single defined value expected");2039 2040 for (VPUser *User : Current->getVPSingleValue()->users()) {2041 if (!TryToPushSinkCandidate(cast<VPRecipeBase>(User)))2042 return false;2043 }2044 }2045 2046 // Keep recipes to sink ordered by dominance so earlier instructions are2047 // processed first.2048 sort(WorkList, [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {2049 return VPDT.properlyDominates(A, B);2050 });2051 2052 for (VPRecipeBase *SinkCandidate : WorkList) {2053 if (SinkCandidate == FOR)2054 continue;2055 2056 SinkCandidate->moveAfter(Previous);2057 Previous = SinkCandidate;2058 }2059 return true;2060}2061 2062/// Try to hoist \p Previous and its operands before all users of \p FOR.2063static bool hoistPreviousBeforeFORUsers(VPFirstOrderRecurrencePHIRecipe *FOR,2064 VPRecipeBase *Previous,2065 VPDominatorTree &VPDT) {2066 if (cannotHoistOrSinkRecipe(*Previous))2067 return false;2068 2069 // Collect recipes that need hoisting.2070 SmallVector<VPRecipeBase *> HoistCandidates;2071 SmallPtrSet<VPRecipeBase *, 8> Visited;2072 VPRecipeBase *HoistPoint = nullptr;2073 // Find the closest hoist point by looking at all users of FOR and selecting2074 // the recipe dominating all other users.2075 for (VPUser *U : FOR->users()) {2076 auto *R = cast<VPRecipeBase>(U);2077 if (!HoistPoint || VPDT.properlyDominates(R, HoistPoint))2078 HoistPoint = R;2079 }2080 assert(all_of(FOR->users(),2081 [&VPDT, HoistPoint](VPUser *U) {2082 auto *R = cast<VPRecipeBase>(U);2083 return HoistPoint == R ||2084 VPDT.properlyDominates(HoistPoint, R);2085 }) &&2086 "HoistPoint must dominate all users of FOR");2087 2088 auto NeedsHoisting = [HoistPoint, &VPDT,2089 &Visited](VPValue *HoistCandidateV) -> VPRecipeBase * {2090 VPRecipeBase *HoistCandidate = HoistCandidateV->getDefiningRecipe();2091 if (!HoistCandidate)2092 return nullptr;2093 VPRegionBlock *EnclosingLoopRegion =2094 HoistCandidate->getParent()->getEnclosingLoopRegion();2095 assert((!HoistCandidate->getRegion() ||2096 HoistCandidate->getRegion() == EnclosingLoopRegion) &&2097 "CFG in VPlan should still be flat, without replicate regions");2098 // Hoist candidate was already visited, no need to hoist.2099 if (!Visited.insert(HoistCandidate).second)2100 return nullptr;2101 2102 // Candidate is outside loop region or a header phi, dominates FOR users w/o2103 // hoisting.2104 if (!EnclosingLoopRegion || isa<VPHeaderPHIRecipe>(HoistCandidate))2105 return nullptr;2106 2107 // If we reached a recipe that dominates HoistPoint, we don't need to2108 // hoist the recipe.2109 if (VPDT.properlyDominates(HoistCandidate, HoistPoint))2110 return nullptr;2111 return HoistCandidate;2112 };2113 2114 if (!NeedsHoisting(Previous->getVPSingleValue()))2115 return true;2116 2117 // Recursively try to hoist Previous and its operands before all users of FOR.2118 HoistCandidates.push_back(Previous);2119 2120 for (unsigned I = 0; I != HoistCandidates.size(); ++I) {2121 VPRecipeBase *Current = HoistCandidates[I];2122 assert(Current->getNumDefinedValues() == 1 &&2123 "only recipes with a single defined value expected");2124 if (cannotHoistOrSinkRecipe(*Current))2125 return false;2126 2127 for (VPValue *Op : Current->operands()) {2128 // If we reach FOR, it means the original Previous depends on some other2129 // recurrence that in turn depends on FOR. If that is the case, we would2130 // also need to hoist recipes involving the other FOR, which may break2131 // dependencies.2132 if (Op == FOR)2133 return false;2134 2135 if (auto *R = NeedsHoisting(Op))2136 HoistCandidates.push_back(R);2137 }2138 }2139 2140 // Order recipes to hoist by dominance so earlier instructions are processed2141 // first.2142 sort(HoistCandidates, [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {2143 return VPDT.properlyDominates(A, B);2144 });2145 2146 for (VPRecipeBase *HoistCandidate : HoistCandidates) {2147 HoistCandidate->moveBefore(*HoistPoint->getParent(),2148 HoistPoint->getIterator());2149 }2150 2151 return true;2152}2153 2154bool VPlanTransforms::adjustFixedOrderRecurrences(VPlan &Plan,2155 VPBuilder &LoopBuilder) {2156 VPDominatorTree VPDT(Plan);2157 2158 SmallVector<VPFirstOrderRecurrencePHIRecipe *> RecurrencePhis;2159 for (VPRecipeBase &R :2160 Plan.getVectorLoopRegion()->getEntry()->getEntryBasicBlock()->phis())2161 if (auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R))2162 RecurrencePhis.push_back(FOR);2163 2164 for (VPFirstOrderRecurrencePHIRecipe *FOR : RecurrencePhis) {2165 SmallPtrSet<VPFirstOrderRecurrencePHIRecipe *, 4> SeenPhis;2166 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();2167 // Fixed-order recurrences do not contain cycles, so this loop is guaranteed2168 // to terminate.2169 while (auto *PrevPhi =2170 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {2171 assert(PrevPhi->getParent() == FOR->getParent());2172 assert(SeenPhis.insert(PrevPhi).second);2173 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();2174 }2175 2176 if (!sinkRecurrenceUsersAfterPrevious(FOR, Previous, VPDT) &&2177 !hoistPreviousBeforeFORUsers(FOR, Previous, VPDT))2178 return false;2179 2180 // Introduce a recipe to combine the incoming and previous values of a2181 // fixed-order recurrence.2182 VPBasicBlock *InsertBlock = Previous->getParent();2183 if (isa<VPHeaderPHIRecipe>(Previous))2184 LoopBuilder.setInsertPoint(InsertBlock, InsertBlock->getFirstNonPhi());2185 else2186 LoopBuilder.setInsertPoint(InsertBlock,2187 std::next(Previous->getIterator()));2188 2189 auto *RecurSplice =2190 LoopBuilder.createNaryOp(VPInstruction::FirstOrderRecurrenceSplice,2191 {FOR, FOR->getBackedgeValue()});2192 2193 FOR->replaceAllUsesWith(RecurSplice);2194 // Set the first operand of RecurSplice to FOR again, after replacing2195 // all users.2196 RecurSplice->setOperand(0, FOR);2197 2198 // Check for users extracting at the penultimate active lane of the FOR.2199 // If only a single lane is active in the current iteration, we need to2200 // select the last element from the previous iteration (from the FOR phi2201 // directly).2202 for (VPUser *U : RecurSplice->users()) {2203 if (!match(U, m_ExtractLane(m_LastActiveLane(m_VPValue()),2204 m_Specific(RecurSplice))))2205 continue;2206 2207 VPBuilder B(cast<VPInstruction>(U));2208 VPValue *LastActiveLane = cast<VPInstruction>(U)->getOperand(0);2209 Type *I64Ty = Type::getInt64Ty(Plan.getContext());2210 VPValue *Zero = Plan.getOrAddLiveIn(ConstantInt::get(I64Ty, 0));2211 VPValue *One = Plan.getOrAddLiveIn(ConstantInt::get(I64Ty, 1));2212 VPValue *PenultimateIndex =2213 B.createNaryOp(Instruction::Sub, {LastActiveLane, One});2214 VPValue *PenultimateLastIter =2215 B.createNaryOp(VPInstruction::ExtractLane,2216 {PenultimateIndex, FOR->getBackedgeValue()});2217 VPValue *LastPrevIter =2218 B.createNaryOp(VPInstruction::ExtractLastElement, FOR);2219 VPValue *Cmp = B.createICmp(CmpInst::ICMP_EQ, LastActiveLane, Zero);2220 VPValue *Sel = B.createSelect(Cmp, LastPrevIter, PenultimateLastIter);2221 cast<VPInstruction>(U)->replaceAllUsesWith(Sel);2222 }2223 }2224 return true;2225}2226 2227void VPlanTransforms::clearReductionWrapFlags(VPlan &Plan) {2228 for (VPRecipeBase &R :2229 Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {2230 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(&R);2231 if (!PhiR)2232 continue;2233 RecurKind RK = PhiR->getRecurrenceKind();2234 if (RK != RecurKind::Add && RK != RecurKind::Mul && RK != RecurKind::Sub &&2235 RK != RecurKind::AddChainWithSubs)2236 continue;2237 2238 for (VPUser *U : collectUsersRecursively(PhiR))2239 if (auto *RecWithFlags = dyn_cast<VPRecipeWithIRFlags>(U)) {2240 RecWithFlags->dropPoisonGeneratingFlags();2241 }2242 }2243}2244 2245namespace {2246struct VPCSEDenseMapInfo : public DenseMapInfo<VPSingleDefRecipe *> {2247 static bool isSentinel(const VPSingleDefRecipe *Def) {2248 return Def == getEmptyKey() || Def == getTombstoneKey();2249 }2250 2251 /// If recipe \p R will lower to a GEP with a non-i8 source element type,2252 /// return that source element type.2253 static Type *getGEPSourceElementType(const VPSingleDefRecipe *R) {2254 // All VPInstructions that lower to GEPs must have the i8 source element2255 // type (as they are PtrAdds), so we omit it.2256 return TypeSwitch<const VPSingleDefRecipe *, Type *>(R)2257 .Case<VPReplicateRecipe>([](auto *I) -> Type * {2258 if (auto *GEP = dyn_cast<GetElementPtrInst>(I->getUnderlyingValue()))2259 return GEP->getSourceElementType();2260 return nullptr;2261 })2262 .Case<VPVectorPointerRecipe, VPWidenGEPRecipe>(2263 [](auto *I) { return I->getSourceElementType(); })2264 .Default([](auto *) { return nullptr; });2265 }2266 2267 /// Returns true if recipe \p Def can be safely handed for CSE.2268 static bool canHandle(const VPSingleDefRecipe *Def) {2269 // We can extend the list of handled recipes in the future,2270 // provided we account for the data embedded in them while checking for2271 // equality or hashing.2272 auto C = getOpcodeOrIntrinsicID(Def);2273 2274 // The issue with (Insert|Extract)Value is that the index of the2275 // insert/extract is not a proper operand in LLVM IR, and hence also not in2276 // VPlan.2277 if (!C || (!C->first && (C->second == Instruction::InsertValue ||2278 C->second == Instruction::ExtractValue)))2279 return false;2280 2281 // During CSE, we can only handle recipes that don't read from memory: if2282 // they read from memory, there could be an intervening write to memory2283 // before the next instance is CSE'd, leading to an incorrect result.2284 return !Def->mayReadFromMemory();2285 }2286 2287 /// Hash the underlying data of \p Def.2288 static unsigned getHashValue(const VPSingleDefRecipe *Def) {2289 const VPlan *Plan = Def->getParent()->getPlan();2290 VPTypeAnalysis TypeInfo(*Plan);2291 hash_code Result = hash_combine(2292 Def->getVPDefID(), getOpcodeOrIntrinsicID(Def),2293 getGEPSourceElementType(Def), TypeInfo.inferScalarType(Def),2294 vputils::isSingleScalar(Def), hash_combine_range(Def->operands()));2295 if (auto *RFlags = dyn_cast<VPRecipeWithIRFlags>(Def))2296 if (RFlags->hasPredicate())2297 return hash_combine(Result, RFlags->getPredicate());2298 return Result;2299 }2300 2301 /// Check equality of underlying data of \p L and \p R.2302 static bool isEqual(const VPSingleDefRecipe *L, const VPSingleDefRecipe *R) {2303 if (isSentinel(L) || isSentinel(R))2304 return L == R;2305 if (L->getVPDefID() != R->getVPDefID() ||2306 getOpcodeOrIntrinsicID(L) != getOpcodeOrIntrinsicID(R) ||2307 getGEPSourceElementType(L) != getGEPSourceElementType(R) ||2308 vputils::isSingleScalar(L) != vputils::isSingleScalar(R) ||2309 !equal(L->operands(), R->operands()))2310 return false;2311 assert(getOpcodeOrIntrinsicID(L) && getOpcodeOrIntrinsicID(R) &&2312 "must have valid opcode info for both recipes");2313 if (auto *LFlags = dyn_cast<VPRecipeWithIRFlags>(L))2314 if (LFlags->hasPredicate() &&2315 LFlags->getPredicate() !=2316 cast<VPRecipeWithIRFlags>(R)->getPredicate())2317 return false;2318 // Recipes in replicate regions implicitly depend on predicate. If either2319 // recipe is in a replicate region, only consider them equal if both have2320 // the same parent.2321 const VPRegionBlock *RegionL = L->getRegion();2322 const VPRegionBlock *RegionR = R->getRegion();2323 if (((RegionL && RegionL->isReplicator()) ||2324 (RegionR && RegionR->isReplicator())) &&2325 L->getParent() != R->getParent())2326 return false;2327 const VPlan *Plan = L->getParent()->getPlan();2328 VPTypeAnalysis TypeInfo(*Plan);2329 return TypeInfo.inferScalarType(L) == TypeInfo.inferScalarType(R);2330 }2331};2332} // end anonymous namespace2333 2334/// Perform a common-subexpression-elimination of VPSingleDefRecipes on the \p2335/// Plan.2336void VPlanTransforms::cse(VPlan &Plan) {2337 VPDominatorTree VPDT(Plan);2338 DenseMap<VPSingleDefRecipe *, VPSingleDefRecipe *, VPCSEDenseMapInfo> CSEMap;2339 2340 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(2341 vp_depth_first_deep(Plan.getEntry()))) {2342 for (VPRecipeBase &R : *VPBB) {2343 auto *Def = dyn_cast<VPSingleDefRecipe>(&R);2344 if (!Def || !VPCSEDenseMapInfo::canHandle(Def))2345 continue;2346 if (VPSingleDefRecipe *V = CSEMap.lookup(Def)) {2347 // V must dominate Def for a valid replacement.2348 if (!VPDT.dominates(V->getParent(), VPBB))2349 continue;2350 // Only keep flags present on both V and Def.2351 if (auto *RFlags = dyn_cast<VPRecipeWithIRFlags>(V))2352 RFlags->intersectFlags(*cast<VPRecipeWithIRFlags>(Def));2353 Def->replaceAllUsesWith(V);2354 continue;2355 }2356 CSEMap[Def] = Def;2357 }2358 }2359}2360 2361/// Move loop-invariant recipes out of the vector loop region in \p Plan.2362static void licm(VPlan &Plan) {2363 VPBasicBlock *Preheader = Plan.getVectorPreheader();2364 2365 // Hoist any loop invariant recipes from the vector loop region to the2366 // preheader. Preform a shallow traversal of the vector loop region, to2367 // exclude recipes in replicate regions. Since the top-level blocks in the2368 // vector loop region are guaranteed to execute if the vector pre-header is,2369 // we don't need to check speculation safety.2370 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();2371 assert(Preheader->getSingleSuccessor() == LoopRegion &&2372 "Expected vector prehader's successor to be the vector loop region");2373 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(2374 vp_depth_first_shallow(LoopRegion->getEntry()))) {2375 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {2376 if (cannotHoistOrSinkRecipe(R))2377 continue;2378 if (any_of(R.operands(), [](VPValue *Op) {2379 return !Op->isDefinedOutsideLoopRegions();2380 }))2381 continue;2382 R.moveBefore(*Preheader, Preheader->end());2383 }2384 }2385}2386 2387void VPlanTransforms::truncateToMinimalBitwidths(2388 VPlan &Plan, const MapVector<Instruction *, uint64_t> &MinBWs) {2389 if (Plan.hasScalarVFOnly())2390 return;2391 // Keep track of created truncates, so they can be re-used. Note that we2392 // cannot use RAUW after creating a new truncate, as this would could make2393 // other uses have different types for their operands, making them invalidly2394 // typed.2395 DenseMap<VPValue *, VPWidenCastRecipe *> ProcessedTruncs;2396 VPTypeAnalysis TypeInfo(Plan);2397 VPBasicBlock *PH = Plan.getVectorPreheader();2398 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(2399 vp_depth_first_deep(Plan.getVectorLoopRegion()))) {2400 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {2401 if (!isa<VPWidenRecipe, VPWidenCastRecipe, VPReplicateRecipe,2402 VPWidenSelectRecipe, VPWidenLoadRecipe, VPWidenIntrinsicRecipe>(2403 &R))2404 continue;2405 2406 VPValue *ResultVPV = R.getVPSingleValue();2407 auto *UI = cast_or_null<Instruction>(ResultVPV->getUnderlyingValue());2408 unsigned NewResSizeInBits = MinBWs.lookup(UI);2409 if (!NewResSizeInBits)2410 continue;2411 2412 // If the value wasn't vectorized, we must maintain the original scalar2413 // type. Skip those here, after incrementing NumProcessedRecipes. Also2414 // skip casts which do not need to be handled explicitly here, as2415 // redundant casts will be removed during recipe simplification.2416 if (isa<VPReplicateRecipe, VPWidenCastRecipe>(&R))2417 continue;2418 2419 Type *OldResTy = TypeInfo.inferScalarType(ResultVPV);2420 unsigned OldResSizeInBits = OldResTy->getScalarSizeInBits();2421 assert(OldResTy->isIntegerTy() && "only integer types supported");2422 (void)OldResSizeInBits;2423 2424 auto *NewResTy = IntegerType::get(Plan.getContext(), NewResSizeInBits);2425 2426 // Any wrapping introduced by shrinking this operation shouldn't be2427 // considered undefined behavior. So, we can't unconditionally copy2428 // arithmetic wrapping flags to VPW.2429 if (auto *VPW = dyn_cast<VPRecipeWithIRFlags>(&R))2430 VPW->dropPoisonGeneratingFlags();2431 2432 if (OldResSizeInBits != NewResSizeInBits &&2433 !match(&R, m_ICmp(m_VPValue(), m_VPValue()))) {2434 // Extend result to original width.2435 auto *Ext =2436 new VPWidenCastRecipe(Instruction::ZExt, ResultVPV, OldResTy);2437 Ext->insertAfter(&R);2438 ResultVPV->replaceAllUsesWith(Ext);2439 Ext->setOperand(0, ResultVPV);2440 assert(OldResSizeInBits > NewResSizeInBits && "Nothing to shrink?");2441 } else {2442 assert(match(&R, m_ICmp(m_VPValue(), m_VPValue())) &&2443 "Only ICmps should not need extending the result.");2444 }2445 2446 assert(!isa<VPWidenStoreRecipe>(&R) && "stores cannot be narrowed");2447 if (isa<VPWidenLoadRecipe, VPWidenIntrinsicRecipe>(&R))2448 continue;2449 2450 // Shrink operands by introducing truncates as needed.2451 unsigned StartIdx = isa<VPWidenSelectRecipe>(&R) ? 1 : 0;2452 for (unsigned Idx = StartIdx; Idx != R.getNumOperands(); ++Idx) {2453 auto *Op = R.getOperand(Idx);2454 unsigned OpSizeInBits =2455 TypeInfo.inferScalarType(Op)->getScalarSizeInBits();2456 if (OpSizeInBits == NewResSizeInBits)2457 continue;2458 assert(OpSizeInBits > NewResSizeInBits && "nothing to truncate");2459 auto [ProcessedIter, IterIsEmpty] = ProcessedTruncs.try_emplace(Op);2460 if (!IterIsEmpty) {2461 R.setOperand(Idx, ProcessedIter->second);2462 continue;2463 }2464 2465 VPBuilder Builder;2466 if (Op->isLiveIn())2467 Builder.setInsertPoint(PH);2468 else2469 Builder.setInsertPoint(&R);2470 VPWidenCastRecipe *NewOp =2471 Builder.createWidenCast(Instruction::Trunc, Op, NewResTy);2472 ProcessedIter->second = NewOp;2473 R.setOperand(Idx, NewOp);2474 }2475 2476 }2477 }2478}2479 2480void VPlanTransforms::removeBranchOnConst(VPlan &Plan) {2481 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(2482 vp_depth_first_shallow(Plan.getEntry()))) {2483 VPValue *Cond;2484 // Skip blocks that are not terminated by BranchOnCond.2485 if (VPBB->empty() || !match(&VPBB->back(), m_BranchOnCond(m_VPValue(Cond))))2486 continue;2487 2488 assert(VPBB->getNumSuccessors() == 2 &&2489 "Two successors expected for BranchOnCond");2490 unsigned RemovedIdx;2491 if (match(Cond, m_True()))2492 RemovedIdx = 1;2493 else if (match(Cond, m_False()))2494 RemovedIdx = 0;2495 else2496 continue;2497 2498 VPBasicBlock *RemovedSucc =2499 cast<VPBasicBlock>(VPBB->getSuccessors()[RemovedIdx]);2500 assert(count(RemovedSucc->getPredecessors(), VPBB) == 1 &&2501 "There must be a single edge between VPBB and its successor");2502 // Values coming from VPBB into phi recipes of RemoveSucc are removed from2503 // these recipes.2504 for (VPRecipeBase &R : RemovedSucc->phis())2505 cast<VPPhiAccessors>(&R)->removeIncomingValueFor(VPBB);2506 2507 // Disconnect blocks and remove the terminator. RemovedSucc will be deleted2508 // automatically on VPlan destruction if it becomes unreachable.2509 VPBlockUtils::disconnectBlocks(VPBB, RemovedSucc);2510 VPBB->back().eraseFromParent();2511 }2512}2513 2514void VPlanTransforms::optimize(VPlan &Plan) {2515 runPass(removeRedundantCanonicalIVs, Plan);2516 runPass(removeRedundantInductionCasts, Plan);2517 2518 runPass(simplifyRecipes, Plan);2519 runPass(removeDeadRecipes, Plan);2520 runPass(simplifyBlends, Plan);2521 runPass(legalizeAndOptimizeInductions, Plan);2522 runPass(narrowToSingleScalarRecipes, Plan);2523 runPass(removeRedundantExpandSCEVRecipes, Plan);2524 runPass(simplifyRecipes, Plan);2525 runPass(removeBranchOnConst, Plan);2526 runPass(removeDeadRecipes, Plan);2527 2528 runPass(createAndOptimizeReplicateRegions, Plan);2529 runPass(hoistInvariantLoads, Plan);2530 runPass(mergeBlocksIntoPredecessors, Plan);2531 runPass(licm, Plan);2532}2533 2534// Add a VPActiveLaneMaskPHIRecipe and related recipes to \p Plan and replace2535// the loop terminator with a branch-on-cond recipe with the negated2536// active-lane-mask as operand. Note that this turns the loop into an2537// uncountable one. Only the existing terminator is replaced, all other existing2538// recipes/users remain unchanged, except for poison-generating flags being2539// dropped from the canonical IV increment. Return the created2540// VPActiveLaneMaskPHIRecipe.2541//2542// The function uses the following definitions:2543//2544// %TripCount = DataWithControlFlowWithoutRuntimeCheck ?2545// calculate-trip-count-minus-VF (original TC) : original TC2546// %IncrementValue = DataWithControlFlowWithoutRuntimeCheck ?2547// CanonicalIVPhi : CanonicalIVIncrement2548// %StartV is the canonical induction start value.2549//2550// The function adds the following recipes:2551//2552// vector.ph:2553// %TripCount = calculate-trip-count-minus-VF (original TC)2554// [if DataWithControlFlowWithoutRuntimeCheck]2555// %EntryInc = canonical-iv-increment-for-part %StartV2556// %EntryALM = active-lane-mask %EntryInc, %TripCount2557//2558// vector.body:2559// ...2560// %P = active-lane-mask-phi [ %EntryALM, %vector.ph ], [ %ALM, %vector.body ]2561// ...2562// %InLoopInc = canonical-iv-increment-for-part %IncrementValue2563// %ALM = active-lane-mask %InLoopInc, TripCount2564// %Negated = Not %ALM2565// branch-on-cond %Negated2566//2567static VPActiveLaneMaskPHIRecipe *addVPLaneMaskPhiAndUpdateExitBranch(2568 VPlan &Plan, bool DataAndControlFlowWithoutRuntimeCheck) {2569 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();2570 VPBasicBlock *EB = TopRegion->getExitingBasicBlock();2571 auto *CanonicalIVPHI = TopRegion->getCanonicalIV();2572 VPValue *StartV = CanonicalIVPHI->getStartValue();2573 2574 auto *CanonicalIVIncrement =2575 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());2576 // TODO: Check if dropping the flags is needed if2577 // !DataAndControlFlowWithoutRuntimeCheck.2578 CanonicalIVIncrement->dropPoisonGeneratingFlags();2579 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();2580 // We can't use StartV directly in the ActiveLaneMask VPInstruction, since2581 // we have to take unrolling into account. Each part needs to start at2582 // Part * VF2583 auto *VecPreheader = Plan.getVectorPreheader();2584 VPBuilder Builder(VecPreheader);2585 2586 // Create the ActiveLaneMask instruction using the correct start values.2587 VPValue *TC = Plan.getTripCount();2588 2589 VPValue *TripCount, *IncrementValue;2590 if (!DataAndControlFlowWithoutRuntimeCheck) {2591 // When the loop is guarded by a runtime overflow check for the loop2592 // induction variable increment by VF, we can increment the value before2593 // the get.active.lane mask and use the unmodified tripcount.2594 IncrementValue = CanonicalIVIncrement;2595 TripCount = TC;2596 } else {2597 // When avoiding a runtime check, the active.lane.mask inside the loop2598 // uses a modified trip count and the induction variable increment is2599 // done after the active.lane.mask intrinsic is called.2600 IncrementValue = CanonicalIVPHI;2601 TripCount = Builder.createNaryOp(VPInstruction::CalculateTripCountMinusVF,2602 {TC}, DL);2603 }2604 auto *EntryIncrement = Builder.createOverflowingOp(2605 VPInstruction::CanonicalIVIncrementForPart, {StartV}, {false, false}, DL,2606 "index.part.next");2607 2608 // Create the active lane mask instruction in the VPlan preheader.2609 VPValue *ALMMultiplier =2610 Plan.getConstantInt(TopRegion->getCanonicalIVType(), 1);2611 auto *EntryALM = Builder.createNaryOp(VPInstruction::ActiveLaneMask,2612 {EntryIncrement, TC, ALMMultiplier}, DL,2613 "active.lane.mask.entry");2614 2615 // Now create the ActiveLaneMaskPhi recipe in the main loop using the2616 // preheader ActiveLaneMask instruction.2617 auto *LaneMaskPhi =2618 new VPActiveLaneMaskPHIRecipe(EntryALM, DebugLoc::getUnknown());2619 LaneMaskPhi->insertAfter(CanonicalIVPHI);2620 2621 // Create the active lane mask for the next iteration of the loop before the2622 // original terminator.2623 VPRecipeBase *OriginalTerminator = EB->getTerminator();2624 Builder.setInsertPoint(OriginalTerminator);2625 auto *InLoopIncrement =2626 Builder.createOverflowingOp(VPInstruction::CanonicalIVIncrementForPart,2627 {IncrementValue}, {false, false}, DL);2628 auto *ALM = Builder.createNaryOp(VPInstruction::ActiveLaneMask,2629 {InLoopIncrement, TripCount, ALMMultiplier},2630 DL, "active.lane.mask.next");2631 LaneMaskPhi->addOperand(ALM);2632 2633 // Replace the original terminator with BranchOnCond. We have to invert the2634 // mask here because a true condition means jumping to the exit block.2635 auto *NotMask = Builder.createNot(ALM, DL);2636 Builder.createNaryOp(VPInstruction::BranchOnCond, {NotMask}, DL);2637 OriginalTerminator->eraseFromParent();2638 return LaneMaskPhi;2639}2640 2641/// Collect the header mask with the pattern:2642/// (ICMP_ULE, WideCanonicalIV, backedge-taken-count)2643/// TODO: Introduce explicit recipe for header-mask instead of searching2644/// for the header-mask pattern manually.2645static VPSingleDefRecipe *findHeaderMask(VPlan &Plan) {2646 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();2647 SmallVector<VPValue *> WideCanonicalIVs;2648 auto *FoundWidenCanonicalIVUser = find_if(2649 LoopRegion->getCanonicalIV()->users(), IsaPred<VPWidenCanonicalIVRecipe>);2650 assert(count_if(LoopRegion->getCanonicalIV()->users(),2651 IsaPred<VPWidenCanonicalIVRecipe>) <= 1 &&2652 "Must have at most one VPWideCanonicalIVRecipe");2653 if (FoundWidenCanonicalIVUser !=2654 LoopRegion->getCanonicalIV()->users().end()) {2655 auto *WideCanonicalIV =2656 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);2657 WideCanonicalIVs.push_back(WideCanonicalIV);2658 }2659 2660 // Also include VPWidenIntOrFpInductionRecipes that represent a widened2661 // version of the canonical induction.2662 VPBasicBlock *HeaderVPBB = LoopRegion->getEntryBasicBlock();2663 for (VPRecipeBase &Phi : HeaderVPBB->phis()) {2664 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);2665 if (WidenOriginalIV && WidenOriginalIV->isCanonical())2666 WideCanonicalIVs.push_back(WidenOriginalIV);2667 }2668 2669 // Walk users of wide canonical IVs and find the single compare of the form2670 // (ICMP_ULE, WideCanonicalIV, backedge-taken-count).2671 VPSingleDefRecipe *HeaderMask = nullptr;2672 for (auto *Wide : WideCanonicalIVs) {2673 for (VPUser *U : SmallVector<VPUser *>(Wide->users())) {2674 auto *VPI = dyn_cast<VPInstruction>(U);2675 if (!VPI || !vputils::isHeaderMask(VPI, Plan))2676 continue;2677 2678 assert(VPI->getOperand(0) == Wide &&2679 "WidenCanonicalIV must be the first operand of the compare");2680 assert(!HeaderMask && "Multiple header masks found?");2681 HeaderMask = VPI;2682 }2683 }2684 return HeaderMask;2685}2686 2687void VPlanTransforms::addActiveLaneMask(2688 VPlan &Plan, bool UseActiveLaneMaskForControlFlow,2689 bool DataAndControlFlowWithoutRuntimeCheck) {2690 assert((!DataAndControlFlowWithoutRuntimeCheck ||2691 UseActiveLaneMaskForControlFlow) &&2692 "DataAndControlFlowWithoutRuntimeCheck implies "2693 "UseActiveLaneMaskForControlFlow");2694 2695 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();2696 auto *FoundWidenCanonicalIVUser = find_if(2697 LoopRegion->getCanonicalIV()->users(), IsaPred<VPWidenCanonicalIVRecipe>);2698 assert(FoundWidenCanonicalIVUser &&2699 "Must have widened canonical IV when tail folding!");2700 VPSingleDefRecipe *HeaderMask = findHeaderMask(Plan);2701 auto *WideCanonicalIV =2702 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);2703 VPSingleDefRecipe *LaneMask;2704 if (UseActiveLaneMaskForControlFlow) {2705 LaneMask = addVPLaneMaskPhiAndUpdateExitBranch(2706 Plan, DataAndControlFlowWithoutRuntimeCheck);2707 } else {2708 VPBuilder B = VPBuilder::getToInsertAfter(WideCanonicalIV);2709 VPValue *ALMMultiplier = Plan.getOrAddLiveIn(2710 ConstantInt::get(LoopRegion->getCanonicalIVType(), 1));2711 LaneMask =2712 B.createNaryOp(VPInstruction::ActiveLaneMask,2713 {WideCanonicalIV, Plan.getTripCount(), ALMMultiplier},2714 nullptr, "active.lane.mask");2715 }2716 2717 // Walk users of WideCanonicalIV and replace the header mask of the form2718 // (ICMP_ULE, WideCanonicalIV, backedge-taken-count) with an active-lane-mask,2719 // removing the old one to ensure there is always only a single header mask.2720 HeaderMask->replaceAllUsesWith(LaneMask);2721 HeaderMask->eraseFromParent();2722}2723 2724template <typename Op0_t, typename Op1_t> struct RemoveMask_match {2725 Op0_t In;2726 Op1_t &Out;2727 2728 RemoveMask_match(const Op0_t &In, Op1_t &Out) : In(In), Out(Out) {}2729 2730 template <typename OpTy> bool match(OpTy *V) const {2731 if (m_Specific(In).match(V)) {2732 Out = nullptr;2733 return true;2734 }2735 return m_LogicalAnd(m_Specific(In), m_VPValue(Out)).match(V);2736 }2737};2738 2739/// Match a specific mask \p In, or a combination of it (logical-and In, Out).2740/// Returns the remaining part \p Out if so, or nullptr otherwise.2741template <typename Op0_t, typename Op1_t>2742static inline RemoveMask_match<Op0_t, Op1_t> m_RemoveMask(const Op0_t &In,2743 Op1_t &Out) {2744 return RemoveMask_match<Op0_t, Op1_t>(In, Out);2745}2746 2747/// Try to optimize a \p CurRecipe masked by \p HeaderMask to a corresponding2748/// EVL-based recipe without the header mask. Returns nullptr if no EVL-based2749/// recipe could be created.2750/// \p HeaderMask Header Mask.2751/// \p CurRecipe Recipe to be transform.2752/// \p TypeInfo VPlan-based type analysis.2753/// \p EVL The explicit vector length parameter of vector-predication2754/// intrinsics.2755static VPRecipeBase *optimizeMaskToEVL(VPValue *HeaderMask,2756 VPRecipeBase &CurRecipe,2757 VPTypeAnalysis &TypeInfo, VPValue &EVL) {2758 VPlan *Plan = CurRecipe.getParent()->getPlan();2759 DebugLoc DL = CurRecipe.getDebugLoc();2760 VPValue *Addr, *Mask, *EndPtr;2761 2762 /// Adjust any end pointers so that they point to the end of EVL lanes not VF.2763 auto AdjustEndPtr = [&CurRecipe, &EVL](VPValue *EndPtr) {2764 auto *EVLEndPtr = cast<VPVectorEndPointerRecipe>(EndPtr)->clone();2765 EVLEndPtr->insertBefore(&CurRecipe);2766 EVLEndPtr->setOperand(1, &EVL);2767 return EVLEndPtr;2768 };2769 2770 if (match(&CurRecipe,2771 m_MaskedLoad(m_VPValue(Addr), m_RemoveMask(HeaderMask, Mask))) &&2772 !cast<VPWidenLoadRecipe>(CurRecipe).isReverse())2773 return new VPWidenLoadEVLRecipe(cast<VPWidenLoadRecipe>(CurRecipe), Addr,2774 EVL, Mask);2775 2776 if (match(&CurRecipe,2777 m_MaskedLoad(m_VPValue(EndPtr), m_RemoveMask(HeaderMask, Mask))) &&2778 match(EndPtr, m_VecEndPtr(m_VPValue(Addr), m_Specific(&Plan->getVF()))) &&2779 cast<VPWidenLoadRecipe>(CurRecipe).isReverse())2780 return new VPWidenLoadEVLRecipe(cast<VPWidenLoadRecipe>(CurRecipe),2781 AdjustEndPtr(EndPtr), EVL, Mask);2782 2783 if (match(&CurRecipe, m_MaskedStore(m_VPValue(Addr), m_VPValue(),2784 m_RemoveMask(HeaderMask, Mask))) &&2785 !cast<VPWidenStoreRecipe>(CurRecipe).isReverse())2786 return new VPWidenStoreEVLRecipe(cast<VPWidenStoreRecipe>(CurRecipe), Addr,2787 EVL, Mask);2788 2789 if (match(&CurRecipe, m_MaskedStore(m_VPValue(EndPtr), m_VPValue(),2790 m_RemoveMask(HeaderMask, Mask))) &&2791 match(EndPtr, m_VecEndPtr(m_VPValue(Addr), m_Specific(&Plan->getVF()))) &&2792 cast<VPWidenStoreRecipe>(CurRecipe).isReverse())2793 return new VPWidenStoreEVLRecipe(cast<VPWidenStoreRecipe>(CurRecipe),2794 AdjustEndPtr(EndPtr), EVL, Mask);2795 2796 if (auto *Rdx = dyn_cast<VPReductionRecipe>(&CurRecipe))2797 if (Rdx->isConditional() &&2798 match(Rdx->getCondOp(), m_RemoveMask(HeaderMask, Mask)))2799 return new VPReductionEVLRecipe(*Rdx, EVL, Mask);2800 2801 if (auto *Interleave = dyn_cast<VPInterleaveRecipe>(&CurRecipe))2802 if (Interleave->getMask() &&2803 match(Interleave->getMask(), m_RemoveMask(HeaderMask, Mask)))2804 return new VPInterleaveEVLRecipe(*Interleave, EVL, Mask);2805 2806 VPValue *LHS, *RHS;2807 if (match(&CurRecipe,2808 m_Select(m_Specific(HeaderMask), m_VPValue(LHS), m_VPValue(RHS))))2809 return new VPWidenIntrinsicRecipe(2810 Intrinsic::vp_merge, {Plan->getTrue(), LHS, RHS, &EVL},2811 TypeInfo.inferScalarType(LHS), {}, {}, DL);2812 2813 if (match(&CurRecipe, m_Select(m_RemoveMask(HeaderMask, Mask), m_VPValue(LHS),2814 m_VPValue(RHS))))2815 return new VPWidenIntrinsicRecipe(2816 Intrinsic::vp_merge, {Mask, LHS, RHS, &EVL},2817 TypeInfo.inferScalarType(LHS), {}, {}, DL);2818 2819 if (match(&CurRecipe, m_LastActiveLane(m_Specific(HeaderMask)))) {2820 Type *Ty = TypeInfo.inferScalarType(CurRecipe.getVPSingleValue());2821 VPValue *ZExt =2822 VPBuilder(&CurRecipe).createScalarCast(Instruction::ZExt, &EVL, Ty, DL);2823 return new VPInstruction(Instruction::Sub,2824 {ZExt, Plan->getConstantInt(Ty, 1)}, {}, {}, DL);2825 }2826 2827 return nullptr;2828}2829 2830/// Replace recipes with their EVL variants.2831static void transformRecipestoEVLRecipes(VPlan &Plan, VPValue &EVL) {2832 VPTypeAnalysis TypeInfo(Plan);2833 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();2834 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();2835 2836 assert(all_of(Plan.getVF().users(),2837 IsaPred<VPVectorEndPointerRecipe, VPScalarIVStepsRecipe,2838 VPWidenIntOrFpInductionRecipe>) &&2839 "User of VF that we can't transform to EVL.");2840 Plan.getVF().replaceUsesWithIf(&EVL, [](VPUser &U, unsigned Idx) {2841 return isa<VPWidenIntOrFpInductionRecipe, VPScalarIVStepsRecipe>(U);2842 });2843 2844 assert(all_of(Plan.getVFxUF().users(),2845 [&LoopRegion, &Plan](VPUser *U) {2846 return match(U,2847 m_c_Add(m_Specific(LoopRegion->getCanonicalIV()),2848 m_Specific(&Plan.getVFxUF()))) ||2849 isa<VPWidenPointerInductionRecipe>(U);2850 }) &&2851 "Only users of VFxUF should be VPWidenPointerInductionRecipe and the "2852 "increment of the canonical induction.");2853 Plan.getVFxUF().replaceUsesWithIf(&EVL, [](VPUser &U, unsigned Idx) {2854 // Only replace uses in VPWidenPointerInductionRecipe; The increment of the2855 // canonical induction must not be updated.2856 return isa<VPWidenPointerInductionRecipe>(U);2857 });2858 2859 // Defer erasing recipes till the end so that we don't invalidate the2860 // VPTypeAnalysis cache.2861 SmallVector<VPRecipeBase *> ToErase;2862 2863 // Create a scalar phi to track the previous EVL if fixed-order recurrence is2864 // contained.2865 bool ContainsFORs =2866 any_of(Header->phis(), IsaPred<VPFirstOrderRecurrencePHIRecipe>);2867 if (ContainsFORs) {2868 // TODO: Use VPInstruction::ExplicitVectorLength to get maximum EVL.2869 VPValue *MaxEVL = &Plan.getVF();2870 // Emit VPScalarCastRecipe in preheader if VF is not a 32 bits integer.2871 VPBuilder Builder(LoopRegion->getPreheaderVPBB());2872 MaxEVL = Builder.createScalarZExtOrTrunc(2873 MaxEVL, Type::getInt32Ty(Plan.getContext()),2874 TypeInfo.inferScalarType(MaxEVL), DebugLoc::getUnknown());2875 2876 Builder.setInsertPoint(Header, Header->getFirstNonPhi());2877 VPValue *PrevEVL = Builder.createScalarPhi(2878 {MaxEVL, &EVL}, DebugLoc::getUnknown(), "prev.evl");2879 2880 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(2881 vp_depth_first_deep(Plan.getVectorLoopRegion()->getEntry()))) {2882 for (VPRecipeBase &R : *VPBB) {2883 VPValue *V1, *V2;2884 if (!match(&R,2885 m_VPInstruction<VPInstruction::FirstOrderRecurrenceSplice>(2886 m_VPValue(V1), m_VPValue(V2))))2887 continue;2888 VPValue *Imm = Plan.getOrAddLiveIn(2889 ConstantInt::getSigned(Type::getInt32Ty(Plan.getContext()), -1));2890 VPWidenIntrinsicRecipe *VPSplice = new VPWidenIntrinsicRecipe(2891 Intrinsic::experimental_vp_splice,2892 {V1, V2, Imm, Plan.getTrue(), PrevEVL, &EVL},2893 TypeInfo.inferScalarType(R.getVPSingleValue()), {}, {},2894 R.getDebugLoc());2895 VPSplice->insertBefore(&R);2896 R.getVPSingleValue()->replaceAllUsesWith(VPSplice);2897 ToErase.push_back(&R);2898 }2899 }2900 }2901 2902 VPValue *HeaderMask = findHeaderMask(Plan);2903 if (!HeaderMask)2904 return;2905 2906 // Replace header masks with a mask equivalent to predicating by EVL:2907 //2908 // icmp ule widen-canonical-iv backedge-taken-count2909 // ->2910 // icmp ult step-vector, EVL2911 VPRecipeBase *EVLR = EVL.getDefiningRecipe();2912 VPBuilder Builder(EVLR->getParent(), std::next(EVLR->getIterator()));2913 Type *EVLType = TypeInfo.inferScalarType(&EVL);2914 VPValue *EVLMask = Builder.createICmp(2915 CmpInst::ICMP_ULT,2916 Builder.createNaryOp(VPInstruction::StepVector, {}, EVLType), &EVL);2917 HeaderMask->replaceAllUsesWith(EVLMask);2918 ToErase.push_back(HeaderMask->getDefiningRecipe());2919 2920 // Try to optimize header mask recipes away to their EVL variants.2921 // TODO: Split optimizeMaskToEVL out and move into2922 // VPlanTransforms::optimize. transformRecipestoEVLRecipes should be run in2923 // tryToBuildVPlanWithVPRecipes beforehand.2924 for (VPUser *U : collectUsersRecursively(EVLMask)) {2925 auto *CurRecipe = cast<VPRecipeBase>(U);2926 VPRecipeBase *EVLRecipe =2927 optimizeMaskToEVL(EVLMask, *CurRecipe, TypeInfo, EVL);2928 if (!EVLRecipe)2929 continue;2930 2931 unsigned NumDefVal = EVLRecipe->getNumDefinedValues();2932 assert(NumDefVal == CurRecipe->getNumDefinedValues() &&2933 "New recipe must define the same number of values as the "2934 "original.");2935 EVLRecipe->insertBefore(CurRecipe);2936 if (isa<VPSingleDefRecipe, VPWidenLoadEVLRecipe, VPInterleaveEVLRecipe>(2937 EVLRecipe)) {2938 for (unsigned I = 0; I < NumDefVal; ++I) {2939 VPValue *CurVPV = CurRecipe->getVPValue(I);2940 CurVPV->replaceAllUsesWith(EVLRecipe->getVPValue(I));2941 }2942 }2943 ToErase.push_back(CurRecipe);2944 }2945 // Remove dead EVL mask.2946 if (EVLMask->getNumUsers() == 0)2947 ToErase.push_back(EVLMask->getDefiningRecipe());2948 2949 for (VPRecipeBase *R : reverse(ToErase)) {2950 SmallVector<VPValue *> PossiblyDead(R->operands());2951 R->eraseFromParent();2952 for (VPValue *Op : PossiblyDead)2953 recursivelyDeleteDeadRecipes(Op);2954 }2955}2956 2957/// Add a VPEVLBasedIVPHIRecipe and related recipes to \p Plan and2958/// replaces all uses except the canonical IV increment of2959/// VPCanonicalIVPHIRecipe with a VPEVLBasedIVPHIRecipe. VPCanonicalIVPHIRecipe2960/// is used only for loop iterations counting after this transformation.2961///2962/// The function uses the following definitions:2963/// %StartV is the canonical induction start value.2964///2965/// The function adds the following recipes:2966///2967/// vector.ph:2968/// ...2969///2970/// vector.body:2971/// ...2972/// %EVLPhi = EXPLICIT-VECTOR-LENGTH-BASED-IV-PHI [ %StartV, %vector.ph ],2973/// [ %NextEVLIV, %vector.body ]2974/// %AVL = phi [ trip-count, %vector.ph ], [ %NextAVL, %vector.body ]2975/// %VPEVL = EXPLICIT-VECTOR-LENGTH %AVL2976/// ...2977/// %OpEVL = cast i32 %VPEVL to IVSize2978/// %NextEVLIV = add IVSize %OpEVL, %EVLPhi2979/// %NextAVL = sub IVSize nuw %AVL, %OpEVL2980/// ...2981///2982/// If MaxSafeElements is provided, the function adds the following recipes:2983/// vector.ph:2984/// ...2985///2986/// vector.body:2987/// ...2988/// %EVLPhi = EXPLICIT-VECTOR-LENGTH-BASED-IV-PHI [ %StartV, %vector.ph ],2989/// [ %NextEVLIV, %vector.body ]2990/// %AVL = phi [ trip-count, %vector.ph ], [ %NextAVL, %vector.body ]2991/// %cmp = cmp ult %AVL, MaxSafeElements2992/// %SAFE_AVL = select %cmp, %AVL, MaxSafeElements2993/// %VPEVL = EXPLICIT-VECTOR-LENGTH %SAFE_AVL2994/// ...2995/// %OpEVL = cast i32 %VPEVL to IVSize2996/// %NextEVLIV = add IVSize %OpEVL, %EVLPhi2997/// %NextAVL = sub IVSize nuw %AVL, %OpEVL2998/// ...2999///3000void VPlanTransforms::addExplicitVectorLength(3001 VPlan &Plan, const std::optional<unsigned> &MaxSafeElements) {3002 if (Plan.hasScalarVFOnly())3003 return;3004 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();3005 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();3006 3007 auto *CanonicalIVPHI = LoopRegion->getCanonicalIV();3008 auto *CanIVTy = LoopRegion->getCanonicalIVType();3009 VPValue *StartV = CanonicalIVPHI->getStartValue();3010 3011 // Create the ExplicitVectorLengthPhi recipe in the main loop.3012 auto *EVLPhi = new VPEVLBasedIVPHIRecipe(StartV, DebugLoc::getUnknown());3013 EVLPhi->insertAfter(CanonicalIVPHI);3014 VPBuilder Builder(Header, Header->getFirstNonPhi());3015 // Create the AVL (application vector length), starting from TC -> 0 in steps3016 // of EVL.3017 VPPhi *AVLPhi = Builder.createScalarPhi(3018 {Plan.getTripCount()}, DebugLoc::getCompilerGenerated(), "avl");3019 VPValue *AVL = AVLPhi;3020 3021 if (MaxSafeElements) {3022 // Support for MaxSafeDist for correct loop emission.3023 VPValue *AVLSafe = Plan.getConstantInt(CanIVTy, *MaxSafeElements);3024 VPValue *Cmp = Builder.createICmp(ICmpInst::ICMP_ULT, AVL, AVLSafe);3025 AVL = Builder.createSelect(Cmp, AVL, AVLSafe, DebugLoc::getUnknown(),3026 "safe_avl");3027 }3028 auto *VPEVL = Builder.createNaryOp(VPInstruction::ExplicitVectorLength, AVL,3029 DebugLoc::getUnknown());3030 3031 auto *CanonicalIVIncrement =3032 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());3033 Builder.setInsertPoint(CanonicalIVIncrement);3034 VPValue *OpVPEVL = VPEVL;3035 3036 auto *I32Ty = Type::getInt32Ty(Plan.getContext());3037 OpVPEVL = Builder.createScalarZExtOrTrunc(3038 OpVPEVL, CanIVTy, I32Ty, CanonicalIVIncrement->getDebugLoc());3039 3040 auto *NextEVLIV = Builder.createOverflowingOp(3041 Instruction::Add, {OpVPEVL, EVLPhi},3042 {CanonicalIVIncrement->hasNoUnsignedWrap(),3043 CanonicalIVIncrement->hasNoSignedWrap()},3044 CanonicalIVIncrement->getDebugLoc(), "index.evl.next");3045 EVLPhi->addOperand(NextEVLIV);3046 3047 VPValue *NextAVL = Builder.createOverflowingOp(3048 Instruction::Sub, {AVLPhi, OpVPEVL}, {/*hasNUW=*/true, /*hasNSW=*/false},3049 DebugLoc::getCompilerGenerated(), "avl.next");3050 AVLPhi->addOperand(NextAVL);3051 3052 transformRecipestoEVLRecipes(Plan, *VPEVL);3053 3054 // Replace all uses of VPCanonicalIVPHIRecipe by3055 // VPEVLBasedIVPHIRecipe except for the canonical IV increment.3056 CanonicalIVPHI->replaceAllUsesWith(EVLPhi);3057 CanonicalIVIncrement->setOperand(0, CanonicalIVPHI);3058 // TODO: support unroll factor > 1.3059 Plan.setUF(1);3060}3061 3062void VPlanTransforms::canonicalizeEVLLoops(VPlan &Plan) {3063 // Find EVL loop entries by locating VPEVLBasedIVPHIRecipe.3064 // There should be only one EVL PHI in the entire plan.3065 VPEVLBasedIVPHIRecipe *EVLPhi = nullptr;3066 3067 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(3068 vp_depth_first_shallow(Plan.getEntry())))3069 for (VPRecipeBase &R : VPBB->phis())3070 if (auto *PhiR = dyn_cast<VPEVLBasedIVPHIRecipe>(&R)) {3071 assert(!EVLPhi && "Found multiple EVL PHIs. Only one expected");3072 EVLPhi = PhiR;3073 }3074 3075 // Early return if no EVL PHI is found.3076 if (!EVLPhi)3077 return;3078 3079 VPBasicBlock *HeaderVPBB = EVLPhi->getParent();3080 VPValue *EVLIncrement = EVLPhi->getBackedgeValue();3081 VPValue *AVL;3082 [[maybe_unused]] bool FoundAVL =3083 match(EVLIncrement,3084 m_c_Add(m_ZExtOrSelf(m_EVL(m_VPValue(AVL))), m_Specific(EVLPhi)));3085 assert(FoundAVL && "Didn't find AVL?");3086 3087 // The AVL may be capped to a safe distance.3088 VPValue *SafeAVL;3089 if (match(AVL, m_Select(m_VPValue(), m_VPValue(SafeAVL), m_VPValue())))3090 AVL = SafeAVL;3091 3092 VPValue *AVLNext;3093 [[maybe_unused]] bool FoundAVLNext =3094 match(AVL, m_VPInstruction<Instruction::PHI>(3095 m_Specific(Plan.getTripCount()), m_VPValue(AVLNext)));3096 assert(FoundAVLNext && "Didn't find AVL backedge?");3097 3098 // Convert EVLPhi to concrete recipe.3099 auto *ScalarR =3100 VPBuilder(EVLPhi).createScalarPhi({EVLPhi->getStartValue(), EVLIncrement},3101 EVLPhi->getDebugLoc(), "evl.based.iv");3102 EVLPhi->replaceAllUsesWith(ScalarR);3103 EVLPhi->eraseFromParent();3104 3105 // Replace CanonicalIVInc with EVL-PHI increment.3106 auto *CanonicalIV = cast<VPPhi>(&*HeaderVPBB->begin());3107 VPValue *Backedge = CanonicalIV->getIncomingValue(1);3108 assert(match(Backedge, m_c_Add(m_Specific(CanonicalIV),3109 m_Specific(&Plan.getVFxUF()))) &&3110 "Unexpected canonical iv");3111 Backedge->replaceAllUsesWith(EVLIncrement);3112 3113 // Remove unused phi and increment.3114 VPRecipeBase *CanonicalIVIncrement = Backedge->getDefiningRecipe();3115 CanonicalIVIncrement->eraseFromParent();3116 CanonicalIV->eraseFromParent();3117 3118 // Replace the use of VectorTripCount in the latch-exiting block.3119 // Before: (branch-on-count EVLIVInc, VectorTripCount)3120 // After: (branch-on-cond eq AVLNext, 0)3121 3122 VPBasicBlock *LatchExiting =3123 HeaderVPBB->getPredecessors()[1]->getEntryBasicBlock();3124 auto *LatchExitingBr = cast<VPInstruction>(LatchExiting->getTerminator());3125 // Skip single-iteration loop region3126 if (match(LatchExitingBr, m_BranchOnCond(m_True())))3127 return;3128 assert(LatchExitingBr &&3129 match(LatchExitingBr,3130 m_BranchOnCount(m_VPValue(EVLIncrement),3131 m_Specific(&Plan.getVectorTripCount()))) &&3132 "Unexpected terminator in EVL loop");3133 3134 Type *AVLTy = VPTypeAnalysis(Plan).inferScalarType(AVLNext);3135 VPBuilder Builder(LatchExitingBr);3136 VPValue *Cmp = Builder.createICmp(CmpInst::ICMP_EQ, AVLNext,3137 Plan.getConstantInt(AVLTy, 0));3138 Builder.createNaryOp(VPInstruction::BranchOnCond, Cmp);3139 LatchExitingBr->eraseFromParent();3140}3141 3142void VPlanTransforms::replaceSymbolicStrides(3143 VPlan &Plan, PredicatedScalarEvolution &PSE,3144 const DenseMap<Value *, const SCEV *> &StridesMap) {3145 // Replace VPValues for known constant strides guaranteed by predicate scalar3146 // evolution.3147 auto CanUseVersionedStride = [&Plan](VPUser &U, unsigned) {3148 auto *R = cast<VPRecipeBase>(&U);3149 return R->getRegion() ||3150 R->getParent() == Plan.getVectorLoopRegion()->getSinglePredecessor();3151 };3152 ValueToSCEVMapTy RewriteMap;3153 for (const SCEV *Stride : StridesMap.values()) {3154 using namespace SCEVPatternMatch;3155 auto *StrideV = cast<SCEVUnknown>(Stride)->getValue();3156 const APInt *StrideConst;3157 if (!match(PSE.getSCEV(StrideV), m_scev_APInt(StrideConst)))3158 // Only handle constant strides for now.3159 continue;3160 3161 auto *CI = Plan.getConstantInt(*StrideConst);3162 if (VPValue *StrideVPV = Plan.getLiveIn(StrideV))3163 StrideVPV->replaceUsesWithIf(CI, CanUseVersionedStride);3164 3165 // The versioned value may not be used in the loop directly but through a3166 // sext/zext. Add new live-ins in those cases.3167 for (Value *U : StrideV->users()) {3168 if (!isa<SExtInst, ZExtInst>(U))3169 continue;3170 VPValue *StrideVPV = Plan.getLiveIn(U);3171 if (!StrideVPV)3172 continue;3173 unsigned BW = U->getType()->getScalarSizeInBits();3174 APInt C =3175 isa<SExtInst>(U) ? StrideConst->sext(BW) : StrideConst->zext(BW);3176 VPValue *CI = Plan.getConstantInt(C);3177 StrideVPV->replaceUsesWithIf(CI, CanUseVersionedStride);3178 }3179 RewriteMap[StrideV] = PSE.getSCEV(StrideV);3180 }3181 3182 for (VPRecipeBase &R : *Plan.getEntry()) {3183 auto *ExpSCEV = dyn_cast<VPExpandSCEVRecipe>(&R);3184 if (!ExpSCEV)3185 continue;3186 const SCEV *ScevExpr = ExpSCEV->getSCEV();3187 auto *NewSCEV =3188 SCEVParameterRewriter::rewrite(ScevExpr, *PSE.getSE(), RewriteMap);3189 if (NewSCEV != ScevExpr) {3190 VPValue *NewExp = vputils::getOrCreateVPValueForSCEVExpr(Plan, NewSCEV);3191 ExpSCEV->replaceAllUsesWith(NewExp);3192 if (Plan.getTripCount() == ExpSCEV)3193 Plan.resetTripCount(NewExp);3194 }3195 }3196}3197 3198void VPlanTransforms::dropPoisonGeneratingRecipes(3199 VPlan &Plan,3200 const std::function<bool(BasicBlock *)> &BlockNeedsPredication) {3201 // Collect recipes in the backward slice of `Root` that may generate a poison3202 // value that is used after vectorization.3203 SmallPtrSet<VPRecipeBase *, 16> Visited;3204 auto CollectPoisonGeneratingInstrsInBackwardSlice([&](VPRecipeBase *Root) {3205 SmallVector<VPRecipeBase *, 16> Worklist;3206 Worklist.push_back(Root);3207 3208 // Traverse the backward slice of Root through its use-def chain.3209 while (!Worklist.empty()) {3210 VPRecipeBase *CurRec = Worklist.pop_back_val();3211 3212 if (!Visited.insert(CurRec).second)3213 continue;3214 3215 // Prune search if we find another recipe generating a widen memory3216 // instruction. Widen memory instructions involved in address computation3217 // will lead to gather/scatter instructions, which don't need to be3218 // handled.3219 if (isa<VPWidenMemoryRecipe, VPInterleaveRecipe, VPScalarIVStepsRecipe,3220 VPHeaderPHIRecipe>(CurRec))3221 continue;3222 3223 // This recipe contributes to the address computation of a widen3224 // load/store. If the underlying instruction has poison-generating flags,3225 // drop them directly.3226 if (auto *RecWithFlags = dyn_cast<VPRecipeWithIRFlags>(CurRec)) {3227 VPValue *A, *B;3228 // Dropping disjoint from an OR may yield incorrect results, as some3229 // analysis may have converted it to an Add implicitly (e.g. SCEV used3230 // for dependence analysis). Instead, replace it with an equivalent Add.3231 // This is possible as all users of the disjoint OR only access lanes3232 // where the operands are disjoint or poison otherwise.3233 if (match(RecWithFlags, m_BinaryOr(m_VPValue(A), m_VPValue(B))) &&3234 RecWithFlags->isDisjoint()) {3235 VPBuilder Builder(RecWithFlags);3236 VPInstruction *New = Builder.createOverflowingOp(3237 Instruction::Add, {A, B}, {false, false},3238 RecWithFlags->getDebugLoc());3239 New->setUnderlyingValue(RecWithFlags->getUnderlyingValue());3240 RecWithFlags->replaceAllUsesWith(New);3241 RecWithFlags->eraseFromParent();3242 CurRec = New;3243 } else3244 RecWithFlags->dropPoisonGeneratingFlags();3245 } else {3246 Instruction *Instr = dyn_cast_or_null<Instruction>(3247 CurRec->getVPSingleValue()->getUnderlyingValue());3248 (void)Instr;3249 assert((!Instr || !Instr->hasPoisonGeneratingFlags()) &&3250 "found instruction with poison generating flags not covered by "3251 "VPRecipeWithIRFlags");3252 }3253 3254 // Add new definitions to the worklist.3255 for (VPValue *Operand : CurRec->operands())3256 if (VPRecipeBase *OpDef = Operand->getDefiningRecipe())3257 Worklist.push_back(OpDef);3258 }3259 });3260 3261 // Traverse all the recipes in the VPlan and collect the poison-generating3262 // recipes in the backward slice starting at the address of a VPWidenRecipe or3263 // VPInterleaveRecipe.3264 auto Iter = vp_depth_first_deep(Plan.getEntry());3265 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {3266 for (VPRecipeBase &Recipe : *VPBB) {3267 if (auto *WidenRec = dyn_cast<VPWidenMemoryRecipe>(&Recipe)) {3268 Instruction &UnderlyingInstr = WidenRec->getIngredient();3269 VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();3270 if (AddrDef && WidenRec->isConsecutive() &&3271 BlockNeedsPredication(UnderlyingInstr.getParent()))3272 CollectPoisonGeneratingInstrsInBackwardSlice(AddrDef);3273 } else if (auto *InterleaveRec = dyn_cast<VPInterleaveRecipe>(&Recipe)) {3274 VPRecipeBase *AddrDef = InterleaveRec->getAddr()->getDefiningRecipe();3275 if (AddrDef) {3276 // Check if any member of the interleave group needs predication.3277 const InterleaveGroup<Instruction> *InterGroup =3278 InterleaveRec->getInterleaveGroup();3279 bool NeedPredication = false;3280 for (int I = 0, NumMembers = InterGroup->getNumMembers();3281 I < NumMembers; ++I) {3282 Instruction *Member = InterGroup->getMember(I);3283 if (Member)3284 NeedPredication |= BlockNeedsPredication(Member->getParent());3285 }3286 3287 if (NeedPredication)3288 CollectPoisonGeneratingInstrsInBackwardSlice(AddrDef);3289 }3290 }3291 }3292 }3293}3294 3295void VPlanTransforms::createInterleaveGroups(3296 VPlan &Plan,3297 const SmallPtrSetImpl<const InterleaveGroup<Instruction> *>3298 &InterleaveGroups,3299 VPRecipeBuilder &RecipeBuilder, const bool &ScalarEpilogueAllowed) {3300 if (InterleaveGroups.empty())3301 return;3302 3303 // Interleave memory: for each Interleave Group we marked earlier as relevant3304 // for this VPlan, replace the Recipes widening its memory instructions with a3305 // single VPInterleaveRecipe at its insertion point.3306 VPDominatorTree VPDT(Plan);3307 for (const auto *IG : InterleaveGroups) {3308 auto *Start =3309 cast<VPWidenMemoryRecipe>(RecipeBuilder.getRecipe(IG->getMember(0)));3310 VPIRMetadata InterleaveMD(*Start);3311 SmallVector<VPValue *, 4> StoredValues;3312 if (auto *StoreR = dyn_cast<VPWidenStoreRecipe>(Start))3313 StoredValues.push_back(StoreR->getStoredValue());3314 for (unsigned I = 1; I < IG->getFactor(); ++I) {3315 Instruction *MemberI = IG->getMember(I);3316 if (!MemberI)3317 continue;3318 VPWidenMemoryRecipe *MemoryR =3319 cast<VPWidenMemoryRecipe>(RecipeBuilder.getRecipe(MemberI));3320 if (auto *StoreR = dyn_cast<VPWidenStoreRecipe>(MemoryR))3321 StoredValues.push_back(StoreR->getStoredValue());3322 InterleaveMD.intersect(*MemoryR);3323 }3324 3325 bool NeedsMaskForGaps =3326 (IG->requiresScalarEpilogue() && !ScalarEpilogueAllowed) ||3327 (!StoredValues.empty() && !IG->isFull());3328 3329 Instruction *IRInsertPos = IG->getInsertPos();3330 auto *InsertPos =3331 cast<VPWidenMemoryRecipe>(RecipeBuilder.getRecipe(IRInsertPos));3332 3333 GEPNoWrapFlags NW = GEPNoWrapFlags::none();3334 if (auto *Gep = dyn_cast<GetElementPtrInst>(3335 getLoadStorePointerOperand(IRInsertPos)->stripPointerCasts()))3336 NW = Gep->getNoWrapFlags().withoutNoUnsignedWrap();3337 3338 // Get or create the start address for the interleave group.3339 VPValue *Addr = Start->getAddr();3340 VPRecipeBase *AddrDef = Addr->getDefiningRecipe();3341 if (AddrDef && !VPDT.properlyDominates(AddrDef, InsertPos)) {3342 // We cannot re-use the address of member zero because it does not3343 // dominate the insert position. Instead, use the address of the insert3344 // position and create a PtrAdd adjusting it to the address of member3345 // zero.3346 // TODO: Hoist Addr's defining recipe (and any operands as needed) to3347 // InsertPos or sink loads above zero members to join it.3348 assert(IG->getIndex(IRInsertPos) != 0 &&3349 "index of insert position shouldn't be zero");3350 auto &DL = IRInsertPos->getDataLayout();3351 APInt Offset(32,3352 DL.getTypeAllocSize(getLoadStoreType(IRInsertPos)) *3353 IG->getIndex(IRInsertPos),3354 /*IsSigned=*/true);3355 VPValue *OffsetVPV = Plan.getConstantInt(-Offset);3356 VPBuilder B(InsertPos);3357 Addr = B.createNoWrapPtrAdd(InsertPos->getAddr(), OffsetVPV, NW);3358 }3359 // If the group is reverse, adjust the index to refer to the last vector3360 // lane instead of the first. We adjust the index from the first vector3361 // lane, rather than directly getting the pointer for lane VF - 1, because3362 // the pointer operand of the interleaved access is supposed to be uniform.3363 if (IG->isReverse()) {3364 auto *ReversePtr = new VPVectorEndPointerRecipe(3365 Addr, &Plan.getVF(), getLoadStoreType(IRInsertPos),3366 -(int64_t)IG->getFactor(), NW, InsertPos->getDebugLoc());3367 ReversePtr->insertBefore(InsertPos);3368 Addr = ReversePtr;3369 }3370 auto *VPIG = new VPInterleaveRecipe(IG, Addr, StoredValues,3371 InsertPos->getMask(), NeedsMaskForGaps,3372 InterleaveMD, InsertPos->getDebugLoc());3373 VPIG->insertBefore(InsertPos);3374 3375 unsigned J = 0;3376 for (unsigned i = 0; i < IG->getFactor(); ++i)3377 if (Instruction *Member = IG->getMember(i)) {3378 VPRecipeBase *MemberR = RecipeBuilder.getRecipe(Member);3379 if (!Member->getType()->isVoidTy()) {3380 VPValue *OriginalV = MemberR->getVPSingleValue();3381 OriginalV->replaceAllUsesWith(VPIG->getVPValue(J));3382 J++;3383 }3384 MemberR->eraseFromParent();3385 }3386 }3387}3388 3389/// Expand a VPWidenIntOrFpInduction into executable recipes, for the initial3390/// value, phi and backedge value. In the following example:3391///3392/// vector.ph:3393/// Successor(s): vector loop3394///3395/// <x1> vector loop: {3396/// vector.body:3397/// WIDEN-INDUCTION %i = phi %start, %step, %vf3398/// ...3399/// EMIT branch-on-count ...3400/// No successors3401/// }3402///3403/// WIDEN-INDUCTION will get expanded to:3404///3405/// vector.ph:3406/// ...3407/// vp<%induction.start> = ...3408/// vp<%induction.increment> = ...3409///3410/// Successor(s): vector loop3411///3412/// <x1> vector loop: {3413/// vector.body:3414/// ir<%i> = WIDEN-PHI vp<%induction.start>, vp<%vec.ind.next>3415/// ...3416/// vp<%vec.ind.next> = add ir<%i>, vp<%induction.increment>3417/// EMIT branch-on-count ...3418/// No successors3419/// }3420static void3421expandVPWidenIntOrFpInduction(VPWidenIntOrFpInductionRecipe *WidenIVR,3422 VPTypeAnalysis &TypeInfo) {3423 VPlan *Plan = WidenIVR->getParent()->getPlan();3424 VPValue *Start = WidenIVR->getStartValue();3425 VPValue *Step = WidenIVR->getStepValue();3426 VPValue *VF = WidenIVR->getVFValue();3427 DebugLoc DL = WidenIVR->getDebugLoc();3428 3429 // The value from the original loop to which we are mapping the new induction3430 // variable.3431 Type *Ty = TypeInfo.inferScalarType(WidenIVR);3432 3433 const InductionDescriptor &ID = WidenIVR->getInductionDescriptor();3434 Instruction::BinaryOps AddOp;3435 Instruction::BinaryOps MulOp;3436 VPIRFlags Flags = *WidenIVR;3437 if (ID.getKind() == InductionDescriptor::IK_IntInduction) {3438 AddOp = Instruction::Add;3439 MulOp = Instruction::Mul;3440 } else {3441 AddOp = ID.getInductionOpcode();3442 MulOp = Instruction::FMul;3443 }3444 3445 // If the phi is truncated, truncate the start and step values.3446 VPBuilder Builder(Plan->getVectorPreheader());3447 Type *StepTy = TypeInfo.inferScalarType(Step);3448 if (Ty->getScalarSizeInBits() < StepTy->getScalarSizeInBits()) {3449 assert(StepTy->isIntegerTy() && "Truncation requires an integer type");3450 Step = Builder.createScalarCast(Instruction::Trunc, Step, Ty, DL);3451 Start = Builder.createScalarCast(Instruction::Trunc, Start, Ty, DL);3452 // Truncation doesn't preserve WrapFlags.3453 Flags.dropPoisonGeneratingFlags();3454 StepTy = Ty;3455 }3456 3457 // Construct the initial value of the vector IV in the vector loop preheader.3458 Type *IVIntTy =3459 IntegerType::get(Plan->getContext(), StepTy->getScalarSizeInBits());3460 VPValue *Init = Builder.createNaryOp(VPInstruction::StepVector, {}, IVIntTy);3461 if (StepTy->isFloatingPointTy())3462 Init = Builder.createWidenCast(Instruction::UIToFP, Init, StepTy);3463 3464 VPValue *SplatStart = Builder.createNaryOp(VPInstruction::Broadcast, Start);3465 VPValue *SplatStep = Builder.createNaryOp(VPInstruction::Broadcast, Step);3466 3467 Init = Builder.createNaryOp(MulOp, {Init, SplatStep}, Flags);3468 Init = Builder.createNaryOp(AddOp, {SplatStart, Init}, Flags,3469 DebugLoc::getUnknown(), "induction");3470 3471 // Create the widened phi of the vector IV.3472 auto *WidePHI = new VPWidenPHIRecipe(WidenIVR->getPHINode(), Init,3473 WidenIVR->getDebugLoc(), "vec.ind");3474 WidePHI->insertBefore(WidenIVR);3475 3476 // Create the backedge value for the vector IV.3477 VPValue *Inc;3478 VPValue *Prev;3479 // If unrolled, use the increment and prev value from the operands.3480 if (auto *SplatVF = WidenIVR->getSplatVFValue()) {3481 Inc = SplatVF;3482 Prev = WidenIVR->getLastUnrolledPartOperand();3483 } else {3484 if (VPRecipeBase *R = VF->getDefiningRecipe())3485 Builder.setInsertPoint(R->getParent(), std::next(R->getIterator()));3486 // Multiply the vectorization factor by the step using integer or3487 // floating-point arithmetic as appropriate.3488 if (StepTy->isFloatingPointTy())3489 VF = Builder.createScalarCast(Instruction::CastOps::UIToFP, VF, StepTy,3490 DL);3491 else3492 VF = Builder.createScalarZExtOrTrunc(VF, StepTy,3493 TypeInfo.inferScalarType(VF), DL);3494 3495 Inc = Builder.createNaryOp(MulOp, {Step, VF}, Flags);3496 Inc = Builder.createNaryOp(VPInstruction::Broadcast, Inc);3497 Prev = WidePHI;3498 }3499 3500 VPBasicBlock *ExitingBB = Plan->getVectorLoopRegion()->getExitingBasicBlock();3501 Builder.setInsertPoint(ExitingBB, ExitingBB->getTerminator()->getIterator());3502 auto *Next = Builder.createNaryOp(AddOp, {Prev, Inc}, Flags,3503 WidenIVR->getDebugLoc(), "vec.ind.next");3504 3505 WidePHI->addOperand(Next);3506 3507 WidenIVR->replaceAllUsesWith(WidePHI);3508}3509 3510/// Expand a VPWidenPointerInductionRecipe into executable recipes, for the3511/// initial value, phi and backedge value. In the following example:3512///3513/// <x1> vector loop: {3514/// vector.body:3515/// EMIT ir<%ptr.iv> = WIDEN-POINTER-INDUCTION %start, %step, %vf3516/// ...3517/// EMIT branch-on-count ...3518/// }3519///3520/// WIDEN-POINTER-INDUCTION will get expanded to:3521///3522/// <x1> vector loop: {3523/// vector.body:3524/// EMIT-SCALAR %pointer.phi = phi %start, %ptr.ind3525/// EMIT %mul = mul %stepvector, %step3526/// EMIT %vector.gep = wide-ptradd %pointer.phi, %mul3527/// ...3528/// EMIT %ptr.ind = ptradd %pointer.phi, %vf3529/// EMIT branch-on-count ...3530/// }3531static void expandVPWidenPointerInduction(VPWidenPointerInductionRecipe *R,3532 VPTypeAnalysis &TypeInfo) {3533 VPlan *Plan = R->getParent()->getPlan();3534 VPValue *Start = R->getStartValue();3535 VPValue *Step = R->getStepValue();3536 VPValue *VF = R->getVFValue();3537 3538 assert(R->getInductionDescriptor().getKind() ==3539 InductionDescriptor::IK_PtrInduction &&3540 "Not a pointer induction according to InductionDescriptor!");3541 assert(TypeInfo.inferScalarType(R)->isPointerTy() && "Unexpected type.");3542 assert(!R->onlyScalarsGenerated(Plan->hasScalableVF()) &&3543 "Recipe should have been replaced");3544 3545 VPBuilder Builder(R);3546 DebugLoc DL = R->getDebugLoc();3547 3548 // Build a scalar pointer phi.3549 VPPhi *ScalarPtrPhi = Builder.createScalarPhi(Start, DL, "pointer.phi");3550 3551 // Create actual address geps that use the pointer phi as base and a3552 // vectorized version of the step value (<step*0, ..., step*N>) as offset.3553 Builder.setInsertPoint(R->getParent(), R->getParent()->getFirstNonPhi());3554 Type *StepTy = TypeInfo.inferScalarType(Step);3555 VPValue *Offset = Builder.createNaryOp(VPInstruction::StepVector, {}, StepTy);3556 Offset = Builder.createOverflowingOp(Instruction::Mul, {Offset, Step});3557 VPValue *PtrAdd = Builder.createNaryOp(3558 VPInstruction::WidePtrAdd, {ScalarPtrPhi, Offset}, DL, "vector.gep");3559 R->replaceAllUsesWith(PtrAdd);3560 3561 // Create the backedge value for the scalar pointer phi.3562 VPBasicBlock *ExitingBB = Plan->getVectorLoopRegion()->getExitingBasicBlock();3563 Builder.setInsertPoint(ExitingBB, ExitingBB->getTerminator()->getIterator());3564 VF = Builder.createScalarZExtOrTrunc(VF, StepTy, TypeInfo.inferScalarType(VF),3565 DL);3566 VPValue *Inc = Builder.createOverflowingOp(Instruction::Mul, {Step, VF});3567 3568 VPValue *InductionGEP =3569 Builder.createPtrAdd(ScalarPtrPhi, Inc, DL, "ptr.ind");3570 ScalarPtrPhi->addOperand(InductionGEP);3571}3572 3573void VPlanTransforms::dissolveLoopRegions(VPlan &Plan) {3574 // Replace loop regions with explicity CFG.3575 SmallVector<VPRegionBlock *> LoopRegions;3576 for (VPRegionBlock *R : VPBlockUtils::blocksOnly<VPRegionBlock>(3577 vp_depth_first_deep(Plan.getEntry()))) {3578 if (!R->isReplicator())3579 LoopRegions.push_back(R);3580 }3581 for (VPRegionBlock *R : LoopRegions)3582 R->dissolveToCFGLoop();3583}3584 3585void VPlanTransforms::convertToConcreteRecipes(VPlan &Plan) {3586 VPTypeAnalysis TypeInfo(Plan);3587 SmallVector<VPRecipeBase *> ToRemove;3588 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(3589 vp_depth_first_deep(Plan.getEntry()))) {3590 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {3591 if (auto *WidenIVR = dyn_cast<VPWidenIntOrFpInductionRecipe>(&R)) {3592 expandVPWidenIntOrFpInduction(WidenIVR, TypeInfo);3593 ToRemove.push_back(WidenIVR);3594 continue;3595 }3596 3597 if (auto *WidenIVR = dyn_cast<VPWidenPointerInductionRecipe>(&R)) {3598 // If the recipe only generates scalars, scalarize it instead of3599 // expanding it.3600 if (WidenIVR->onlyScalarsGenerated(Plan.hasScalableVF())) {3601 VPBuilder Builder(WidenIVR);3602 VPValue *PtrAdd =3603 scalarizeVPWidenPointerInduction(WidenIVR, Plan, Builder);3604 WidenIVR->replaceAllUsesWith(PtrAdd);3605 ToRemove.push_back(WidenIVR);3606 continue;3607 }3608 expandVPWidenPointerInduction(WidenIVR, TypeInfo);3609 ToRemove.push_back(WidenIVR);3610 continue;3611 }3612 3613 // Expand VPBlendRecipe into VPInstruction::Select.3614 VPBuilder Builder(&R);3615 if (auto *Blend = dyn_cast<VPBlendRecipe>(&R)) {3616 VPValue *Select = Blend->getIncomingValue(0);3617 for (unsigned I = 1; I != Blend->getNumIncomingValues(); ++I)3618 Select = Builder.createSelect(Blend->getMask(I),3619 Blend->getIncomingValue(I), Select,3620 R.getDebugLoc(), "predphi");3621 Blend->replaceAllUsesWith(Select);3622 ToRemove.push_back(Blend);3623 }3624 3625 if (auto *Expr = dyn_cast<VPExpressionRecipe>(&R)) {3626 Expr->decompose();3627 ToRemove.push_back(Expr);3628 }3629 3630 // Expand LastActiveLane into Not + FirstActiveLane + Sub.3631 auto *LastActiveL = dyn_cast<VPInstruction>(&R);3632 if (LastActiveL &&3633 LastActiveL->getOpcode() == VPInstruction::LastActiveLane) {3634 // Create Not(Mask) for all operands.3635 SmallVector<VPValue *, 2> NotMasks;3636 for (VPValue *Op : LastActiveL->operands()) {3637 VPValue *NotMask = Builder.createNot(Op, LastActiveL->getDebugLoc());3638 NotMasks.push_back(NotMask);3639 }3640 3641 // Create FirstActiveLane on the inverted masks.3642 VPValue *FirstInactiveLane = Builder.createNaryOp(3643 VPInstruction::FirstActiveLane, NotMasks,3644 LastActiveL->getDebugLoc(), "first.inactive.lane");3645 3646 // Subtract 1 to get the last active lane.3647 VPValue *One = Plan.getOrAddLiveIn(3648 ConstantInt::get(Type::getInt64Ty(Plan.getContext()), 1));3649 VPValue *LastLane = Builder.createNaryOp(3650 Instruction::Sub, {FirstInactiveLane, One},3651 LastActiveL->getDebugLoc(), "last.active.lane");3652 3653 LastActiveL->replaceAllUsesWith(LastLane);3654 ToRemove.push_back(LastActiveL);3655 continue;3656 }3657 3658 VPValue *VectorStep;3659 VPValue *ScalarStep;3660 if (!match(&R, m_VPInstruction<VPInstruction::WideIVStep>(3661 m_VPValue(VectorStep), m_VPValue(ScalarStep))))3662 continue;3663 3664 // Expand WideIVStep.3665 auto *VPI = cast<VPInstruction>(&R);3666 Type *IVTy = TypeInfo.inferScalarType(VPI);3667 if (TypeInfo.inferScalarType(VectorStep) != IVTy) {3668 Instruction::CastOps CastOp = IVTy->isFloatingPointTy()3669 ? Instruction::UIToFP3670 : Instruction::Trunc;3671 VectorStep = Builder.createWidenCast(CastOp, VectorStep, IVTy);3672 }3673 3674 assert(!match(ScalarStep, m_One()) && "Expected non-unit scalar-step");3675 if (TypeInfo.inferScalarType(ScalarStep) != IVTy) {3676 ScalarStep =3677 Builder.createWidenCast(Instruction::Trunc, ScalarStep, IVTy);3678 }3679 3680 VPIRFlags Flags;3681 if (IVTy->isFloatingPointTy())3682 Flags = {VPI->getFastMathFlags()};3683 3684 unsigned MulOpc =3685 IVTy->isFloatingPointTy() ? Instruction::FMul : Instruction::Mul;3686 VPInstruction *Mul = Builder.createNaryOp(3687 MulOpc, {VectorStep, ScalarStep}, Flags, R.getDebugLoc());3688 VectorStep = Mul;3689 VPI->replaceAllUsesWith(VectorStep);3690 ToRemove.push_back(VPI);3691 }3692 }3693 3694 for (VPRecipeBase *R : ToRemove)3695 R->eraseFromParent();3696}3697 3698void VPlanTransforms::handleUncountableEarlyExit(VPBasicBlock *EarlyExitingVPBB,3699 VPBasicBlock *EarlyExitVPBB,3700 VPlan &Plan,3701 VPBasicBlock *HeaderVPBB,3702 VPBasicBlock *LatchVPBB) {3703 VPBlockBase *MiddleVPBB = LatchVPBB->getSuccessors()[0];3704 if (!EarlyExitVPBB->getSinglePredecessor() &&3705 EarlyExitVPBB->getPredecessors()[1] == MiddleVPBB) {3706 assert(EarlyExitVPBB->getNumPredecessors() == 2 &&3707 EarlyExitVPBB->getPredecessors()[0] == EarlyExitingVPBB &&3708 "unsupported early exit VPBB");3709 // Early exit operand should always be last phi operand. If EarlyExitVPBB3710 // has two predecessors and EarlyExitingVPBB is the first, swap the operands3711 // of the phis.3712 for (VPRecipeBase &R : EarlyExitVPBB->phis())3713 cast<VPIRPhi>(&R)->swapOperands();3714 }3715 3716 VPBuilder Builder(LatchVPBB->getTerminator());3717 VPBlockBase *TrueSucc = EarlyExitingVPBB->getSuccessors()[0];3718 assert(match(EarlyExitingVPBB->getTerminator(), m_BranchOnCond()) &&3719 "Terminator must be be BranchOnCond");3720 VPValue *CondOfEarlyExitingVPBB =3721 EarlyExitingVPBB->getTerminator()->getOperand(0);3722 auto *CondToEarlyExit = TrueSucc == EarlyExitVPBB3723 ? CondOfEarlyExitingVPBB3724 : Builder.createNot(CondOfEarlyExitingVPBB);3725 3726 // Split the middle block and have it conditionally branch to the early exit3727 // block if CondToEarlyExit.3728 VPValue *IsEarlyExitTaken =3729 Builder.createNaryOp(VPInstruction::AnyOf, {CondToEarlyExit});3730 VPBasicBlock *NewMiddle = Plan.createVPBasicBlock("middle.split");3731 VPBasicBlock *VectorEarlyExitVPBB =3732 Plan.createVPBasicBlock("vector.early.exit");3733 VPBlockUtils::insertOnEdge(LatchVPBB, MiddleVPBB, NewMiddle);3734 VPBlockUtils::connectBlocks(NewMiddle, VectorEarlyExitVPBB);3735 NewMiddle->swapSuccessors();3736 3737 VPBlockUtils::connectBlocks(VectorEarlyExitVPBB, EarlyExitVPBB);3738 3739 // Update the exit phis in the early exit block.3740 VPBuilder MiddleBuilder(NewMiddle);3741 VPBuilder EarlyExitB(VectorEarlyExitVPBB);3742 for (VPRecipeBase &R : EarlyExitVPBB->phis()) {3743 auto *ExitIRI = cast<VPIRPhi>(&R);3744 // Early exit operand should always be last, i.e., 0 if EarlyExitVPBB has3745 // a single predecessor and 1 if it has two.3746 unsigned EarlyExitIdx = ExitIRI->getNumOperands() - 1;3747 if (ExitIRI->getNumOperands() != 1) {3748 // The first of two operands corresponds to the latch exit, via MiddleVPBB3749 // predecessor. Extract its last lane.3750 ExitIRI->extractLastLaneOfFirstOperand(MiddleBuilder);3751 }3752 3753 VPValue *IncomingFromEarlyExit = ExitIRI->getOperand(EarlyExitIdx);3754 if (!IncomingFromEarlyExit->isLiveIn()) {3755 // Update the incoming value from the early exit.3756 VPValue *FirstActiveLane = EarlyExitB.createNaryOp(3757 VPInstruction::FirstActiveLane, {CondToEarlyExit}, nullptr,3758 "first.active.lane");3759 IncomingFromEarlyExit = EarlyExitB.createNaryOp(3760 VPInstruction::ExtractLane, {FirstActiveLane, IncomingFromEarlyExit},3761 nullptr, "early.exit.value");3762 ExitIRI->setOperand(EarlyExitIdx, IncomingFromEarlyExit);3763 }3764 }3765 MiddleBuilder.createNaryOp(VPInstruction::BranchOnCond, {IsEarlyExitTaken});3766 3767 // Replace the condition controlling the non-early exit from the vector loop3768 // with one exiting if either the original condition of the vector latch is3769 // true or the early exit has been taken.3770 auto *LatchExitingBranch = cast<VPInstruction>(LatchVPBB->getTerminator());3771 assert(LatchExitingBranch->getOpcode() == VPInstruction::BranchOnCount &&3772 "Unexpected terminator");3773 auto *IsLatchExitTaken =3774 Builder.createICmp(CmpInst::ICMP_EQ, LatchExitingBranch->getOperand(0),3775 LatchExitingBranch->getOperand(1));3776 auto *AnyExitTaken = Builder.createNaryOp(3777 Instruction::Or, {IsEarlyExitTaken, IsLatchExitTaken});3778 Builder.createNaryOp(VPInstruction::BranchOnCond, AnyExitTaken);3779 LatchExitingBranch->eraseFromParent();3780}3781 3782/// This function tries convert extended in-loop reductions to3783/// VPExpressionRecipe and clamp the \p Range if it is beneficial and3784/// valid. The created recipe must be decomposed to its constituent3785/// recipes before execution.3786static VPExpressionRecipe *3787tryToMatchAndCreateExtendedReduction(VPReductionRecipe *Red, VPCostContext &Ctx,3788 VFRange &Range) {3789 Type *RedTy = Ctx.Types.inferScalarType(Red);3790 VPValue *VecOp = Red->getVecOp();3791 3792 // Clamp the range if using extended-reduction is profitable.3793 auto IsExtendedRedValidAndClampRange =3794 [&](unsigned Opcode, Instruction::CastOps ExtOpc, Type *SrcTy) -> bool {3795 return LoopVectorizationPlanner::getDecisionAndClampRange(3796 [&](ElementCount VF) {3797 auto *SrcVecTy = cast<VectorType>(toVectorTy(SrcTy, VF));3798 TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;3799 3800 InstructionCost ExtRedCost;3801 InstructionCost ExtCost =3802 cast<VPWidenCastRecipe>(VecOp)->computeCost(VF, Ctx);3803 InstructionCost RedCost = Red->computeCost(VF, Ctx);3804 3805 if (Red->isPartialReduction()) {3806 TargetTransformInfo::PartialReductionExtendKind ExtKind =3807 TargetTransformInfo::getPartialReductionExtendKind(ExtOpc);3808 // FIXME: Move partial reduction creation, costing and clamping3809 // here from LoopVectorize.cpp.3810 ExtRedCost = Ctx.TTI.getPartialReductionCost(3811 Opcode, SrcTy, nullptr, RedTy, VF, ExtKind,3812 llvm::TargetTransformInfo::PR_None, std::nullopt, Ctx.CostKind);3813 } else {3814 ExtRedCost = Ctx.TTI.getExtendedReductionCost(3815 Opcode, ExtOpc == Instruction::CastOps::ZExt, RedTy, SrcVecTy,3816 Red->getFastMathFlags(), CostKind);3817 }3818 return ExtRedCost.isValid() && ExtRedCost < ExtCost + RedCost;3819 },3820 Range);3821 };3822 3823 VPValue *A;3824 // Match reduce(ext)).3825 if (match(VecOp, m_ZExtOrSExt(m_VPValue(A))) &&3826 IsExtendedRedValidAndClampRange(3827 RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()),3828 cast<VPWidenCastRecipe>(VecOp)->getOpcode(),3829 Ctx.Types.inferScalarType(A)))3830 return new VPExpressionRecipe(cast<VPWidenCastRecipe>(VecOp), Red);3831 3832 return nullptr;3833}3834 3835/// This function tries convert extended in-loop reductions to3836/// VPExpressionRecipe and clamp the \p Range if it is beneficial3837/// and valid. The created VPExpressionRecipe must be decomposed to its3838/// constituent recipes before execution. Patterns of the3839/// VPExpressionRecipe:3840/// reduce.add(mul(...)),3841/// reduce.add(mul(ext(A), ext(B))),3842/// reduce.add(ext(mul(ext(A), ext(B)))).3843static VPExpressionRecipe *3844tryToMatchAndCreateMulAccumulateReduction(VPReductionRecipe *Red,3845 VPCostContext &Ctx, VFRange &Range) {3846 unsigned Opcode = RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind());3847 if (Opcode != Instruction::Add && Opcode != Instruction::Sub)3848 return nullptr;3849 3850 Type *RedTy = Ctx.Types.inferScalarType(Red);3851 3852 // Clamp the range if using multiply-accumulate-reduction is profitable.3853 auto IsMulAccValidAndClampRange =3854 [&](VPWidenRecipe *Mul, VPWidenCastRecipe *Ext0, VPWidenCastRecipe *Ext1,3855 VPWidenCastRecipe *OuterExt) -> bool {3856 return LoopVectorizationPlanner::getDecisionAndClampRange(3857 [&](ElementCount VF) {3858 TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;3859 Type *SrcTy =3860 Ext0 ? Ctx.Types.inferScalarType(Ext0->getOperand(0)) : RedTy;3861 InstructionCost MulAccCost;3862 3863 if (Red->isPartialReduction()) {3864 Type *SrcTy2 =3865 Ext1 ? Ctx.Types.inferScalarType(Ext1->getOperand(0)) : nullptr;3866 // FIXME: Move partial reduction creation, costing and clamping3867 // here from LoopVectorize.cpp.3868 MulAccCost = Ctx.TTI.getPartialReductionCost(3869 Opcode, SrcTy, SrcTy2, RedTy, VF,3870 Ext0 ? TargetTransformInfo::getPartialReductionExtendKind(3871 Ext0->getOpcode())3872 : TargetTransformInfo::PR_None,3873 Ext1 ? TargetTransformInfo::getPartialReductionExtendKind(3874 Ext1->getOpcode())3875 : TargetTransformInfo::PR_None,3876 Mul->getOpcode(), CostKind);3877 } else {3878 // Only partial reductions support mixed extends at the moment.3879 if (Ext0 && Ext1 && Ext0->getOpcode() != Ext1->getOpcode())3880 return false;3881 3882 bool IsZExt =3883 !Ext0 || Ext0->getOpcode() == Instruction::CastOps::ZExt;3884 auto *SrcVecTy = cast<VectorType>(toVectorTy(SrcTy, VF));3885 MulAccCost = Ctx.TTI.getMulAccReductionCost(IsZExt, Opcode, RedTy,3886 SrcVecTy, CostKind);3887 }3888 3889 InstructionCost MulCost = Mul->computeCost(VF, Ctx);3890 InstructionCost RedCost = Red->computeCost(VF, Ctx);3891 InstructionCost ExtCost = 0;3892 if (Ext0)3893 ExtCost += Ext0->computeCost(VF, Ctx);3894 if (Ext1)3895 ExtCost += Ext1->computeCost(VF, Ctx);3896 if (OuterExt)3897 ExtCost += OuterExt->computeCost(VF, Ctx);3898 3899 return MulAccCost.isValid() &&3900 MulAccCost < ExtCost + MulCost + RedCost;3901 },3902 Range);3903 };3904 3905 VPValue *VecOp = Red->getVecOp();3906 VPRecipeBase *Sub = nullptr;3907 VPValue *A, *B;3908 VPValue *Tmp = nullptr;3909 // Sub reductions could have a sub between the add reduction and vec op.3910 if (match(VecOp, m_Sub(m_ZeroInt(), m_VPValue(Tmp)))) {3911 Sub = VecOp->getDefiningRecipe();3912 VecOp = Tmp;3913 }3914 3915 // If ValB is a constant and can be safely extended, truncate it to the same3916 // type as ExtA's operand, then extend it to the same type as ExtA. This3917 // creates two uniform extends that can more easily be matched by the rest of3918 // the bundling code. The ExtB reference, ValB and operand 1 of Mul are all3919 // replaced with the new extend of the constant.3920 auto ExtendAndReplaceConstantOp = [&Ctx](VPWidenCastRecipe *ExtA,3921 VPWidenCastRecipe *&ExtB,3922 VPValue *&ValB, VPWidenRecipe *Mul) {3923 if (!ExtA || ExtB || !ValB->isLiveIn())3924 return;3925 Type *NarrowTy = Ctx.Types.inferScalarType(ExtA->getOperand(0));3926 Instruction::CastOps ExtOpc = ExtA->getOpcode();3927 const APInt *Const;3928 if (!match(ValB, m_APInt(Const)) ||3929 !llvm::canConstantBeExtended(3930 Const, NarrowTy, TTI::getPartialReductionExtendKind(ExtOpc)))3931 return;3932 // The truncate ensures that the type of each extended operand is the3933 // same, and it's been proven that the constant can be extended from3934 // NarrowTy safely. Necessary since ExtA's extended operand would be3935 // e.g. an i8, while the const will likely be an i32. This will be3936 // elided by later optimisations.3937 VPBuilder Builder(Mul);3938 auto *Trunc =3939 Builder.createWidenCast(Instruction::CastOps::Trunc, ValB, NarrowTy);3940 Type *WideTy = Ctx.Types.inferScalarType(ExtA);3941 ValB = ExtB = Builder.createWidenCast(ExtOpc, Trunc, WideTy);3942 Mul->setOperand(1, ExtB);3943 };3944 3945 // Try to match reduce.add(mul(...)).3946 if (match(VecOp, m_Mul(m_VPValue(A), m_VPValue(B)))) {3947 auto *RecipeA = dyn_cast_if_present<VPWidenCastRecipe>(A);3948 auto *RecipeB = dyn_cast_if_present<VPWidenCastRecipe>(B);3949 auto *Mul = cast<VPWidenRecipe>(VecOp);3950 3951 // Convert reduce.add(mul(ext, const)) to reduce.add(mul(ext, ext(const)))3952 ExtendAndReplaceConstantOp(RecipeA, RecipeB, B, Mul);3953 3954 // Match reduce.add/sub(mul(ext, ext)).3955 if (RecipeA && RecipeB && match(RecipeA, m_ZExtOrSExt(m_VPValue())) &&3956 match(RecipeB, m_ZExtOrSExt(m_VPValue())) &&3957 IsMulAccValidAndClampRange(Mul, RecipeA, RecipeB, nullptr)) {3958 if (Sub)3959 return new VPExpressionRecipe(RecipeA, RecipeB, Mul,3960 cast<VPWidenRecipe>(Sub), Red);3961 return new VPExpressionRecipe(RecipeA, RecipeB, Mul, Red);3962 }3963 // TODO: Add an expression type for this variant with a negated mul3964 if (!Sub && IsMulAccValidAndClampRange(Mul, nullptr, nullptr, nullptr))3965 return new VPExpressionRecipe(Mul, Red);3966 }3967 // TODO: Add an expression type for negated versions of other expression3968 // variants.3969 if (Sub)3970 return nullptr;3971 3972 // Match reduce.add(ext(mul(A, B))).3973 if (match(VecOp, m_ZExtOrSExt(m_Mul(m_VPValue(A), m_VPValue(B))))) {3974 auto *Ext = cast<VPWidenCastRecipe>(VecOp);3975 auto *Mul = cast<VPWidenRecipe>(Ext->getOperand(0));3976 auto *Ext0 = dyn_cast_if_present<VPWidenCastRecipe>(A);3977 auto *Ext1 = dyn_cast_if_present<VPWidenCastRecipe>(B);3978 3979 // reduce.add(ext(mul(ext, const)))3980 // -> reduce.add(ext(mul(ext, ext(const))))3981 ExtendAndReplaceConstantOp(Ext0, Ext1, B, Mul);3982 3983 // reduce.add(ext(mul(ext(A), ext(B))))3984 // -> reduce.add(mul(wider_ext(A), wider_ext(B)))3985 // The inner extends must either have the same opcode as the outer extend or3986 // be the same, in which case the multiply can never result in a negative3987 // value and the outer extend can be folded away by doing wider3988 // extends for the operands of the mul.3989 if (Ext0 && Ext1 &&3990 (Ext->getOpcode() == Ext0->getOpcode() || Ext0 == Ext1) &&3991 Ext0->getOpcode() == Ext1->getOpcode() &&3992 IsMulAccValidAndClampRange(Mul, Ext0, Ext1, Ext) && Mul->hasOneUse()) {3993 auto *NewExt0 = new VPWidenCastRecipe(3994 Ext0->getOpcode(), Ext0->getOperand(0), Ext->getResultType(), nullptr,3995 *Ext0, *Ext0, Ext0->getDebugLoc());3996 NewExt0->insertBefore(Ext0);3997 3998 VPWidenCastRecipe *NewExt1 = NewExt0;3999 if (Ext0 != Ext1) {4000 NewExt1 = new VPWidenCastRecipe(Ext1->getOpcode(), Ext1->getOperand(0),4001 Ext->getResultType(), nullptr, *Ext1,4002 *Ext1, Ext1->getDebugLoc());4003 NewExt1->insertBefore(Ext1);4004 }4005 Mul->setOperand(0, NewExt0);4006 Mul->setOperand(1, NewExt1);4007 Red->setOperand(1, Mul);4008 return new VPExpressionRecipe(NewExt0, NewExt1, Mul, Red);4009 }4010 }4011 return nullptr;4012}4013 4014/// This function tries to create abstract recipes from the reduction recipe for4015/// following optimizations and cost estimation.4016static void tryToCreateAbstractReductionRecipe(VPReductionRecipe *Red,4017 VPCostContext &Ctx,4018 VFRange &Range) {4019 VPExpressionRecipe *AbstractR = nullptr;4020 auto IP = std::next(Red->getIterator());4021 auto *VPBB = Red->getParent();4022 if (auto *MulAcc = tryToMatchAndCreateMulAccumulateReduction(Red, Ctx, Range))4023 AbstractR = MulAcc;4024 else if (auto *ExtRed = tryToMatchAndCreateExtendedReduction(Red, Ctx, Range))4025 AbstractR = ExtRed;4026 // Cannot create abstract inloop reduction recipes.4027 if (!AbstractR)4028 return;4029 4030 AbstractR->insertBefore(*VPBB, IP);4031 Red->replaceAllUsesWith(AbstractR);4032}4033 4034void VPlanTransforms::convertToAbstractRecipes(VPlan &Plan, VPCostContext &Ctx,4035 VFRange &Range) {4036 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(4037 vp_depth_first_deep(Plan.getVectorLoopRegion()))) {4038 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {4039 if (auto *Red = dyn_cast<VPReductionRecipe>(&R))4040 tryToCreateAbstractReductionRecipe(Red, Ctx, Range);4041 }4042 }4043}4044 4045void VPlanTransforms::materializeBroadcasts(VPlan &Plan) {4046 if (Plan.hasScalarVFOnly())4047 return;4048 4049#ifndef NDEBUG4050 VPDominatorTree VPDT(Plan);4051#endif4052 4053 SmallVector<VPValue *> VPValues;4054 if (Plan.getOrCreateBackedgeTakenCount()->getNumUsers() > 0)4055 VPValues.push_back(Plan.getOrCreateBackedgeTakenCount());4056 append_range(VPValues, Plan.getLiveIns());4057 for (VPRecipeBase &R : *Plan.getEntry())4058 append_range(VPValues, R.definedValues());4059 4060 auto *VectorPreheader = Plan.getVectorPreheader();4061 for (VPValue *VPV : VPValues) {4062 if (vputils::onlyScalarValuesUsed(VPV) ||4063 (VPV->isLiveIn() && VPV->getLiveInIRValue() &&4064 isa<Constant>(VPV->getLiveInIRValue())))4065 continue;4066 4067 // Add explicit broadcast at the insert point that dominates all users.4068 VPBasicBlock *HoistBlock = VectorPreheader;4069 VPBasicBlock::iterator HoistPoint = VectorPreheader->end();4070 for (VPUser *User : VPV->users()) {4071 if (User->usesScalars(VPV))4072 continue;4073 if (cast<VPRecipeBase>(User)->getParent() == VectorPreheader)4074 HoistPoint = HoistBlock->begin();4075 else4076 assert(VPDT.dominates(VectorPreheader,4077 cast<VPRecipeBase>(User)->getParent()) &&4078 "All users must be in the vector preheader or dominated by it");4079 }4080 4081 VPBuilder Builder(cast<VPBasicBlock>(HoistBlock), HoistPoint);4082 auto *Broadcast = Builder.createNaryOp(VPInstruction::Broadcast, {VPV});4083 VPV->replaceUsesWithIf(Broadcast,4084 [VPV, Broadcast](VPUser &U, unsigned Idx) {4085 return Broadcast != &U && !U.usesScalars(VPV);4086 });4087 }4088}4089 4090void VPlanTransforms::hoistInvariantLoads(VPlan &Plan) {4091 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();4092 4093 // Collect candidate loads with invariant addresses and noalias scopes4094 // metadata and memory-writing recipes with noalias metadata.4095 SmallVector<std::pair<VPRecipeBase *, MemoryLocation>> CandidateLoads;4096 SmallVector<MemoryLocation> Stores;4097 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(4098 vp_depth_first_shallow(LoopRegion->getEntry()))) {4099 for (VPRecipeBase &R : *VPBB) {4100 // Only handle single-scalar replicated loads with invariant addresses.4101 if (auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {4102 if (RepR->isPredicated() || !RepR->isSingleScalar() ||4103 RepR->getOpcode() != Instruction::Load)4104 continue;4105 4106 VPValue *Addr = RepR->getOperand(0);4107 if (Addr->isDefinedOutsideLoopRegions()) {4108 MemoryLocation Loc = *vputils::getMemoryLocation(*RepR);4109 if (!Loc.AATags.Scope)4110 continue;4111 CandidateLoads.push_back({RepR, Loc});4112 }4113 }4114 if (R.mayWriteToMemory()) {4115 auto Loc = vputils::getMemoryLocation(R);4116 if (!Loc || !Loc->AATags.Scope || !Loc->AATags.NoAlias)4117 return;4118 Stores.push_back(*Loc);4119 }4120 }4121 }4122 4123 VPBasicBlock *Preheader = Plan.getVectorPreheader();4124 for (auto &[LoadRecipe, LoadLoc] : CandidateLoads) {4125 // Hoist the load to the preheader if it doesn't alias with any stores4126 // according to the noalias metadata. Other loads should have been hoisted4127 // by other passes4128 const AAMDNodes &LoadAA = LoadLoc.AATags;4129 if (all_of(Stores, [&](const MemoryLocation &StoreLoc) {4130 return !ScopedNoAliasAAResult::mayAliasInScopes(4131 LoadAA.Scope, StoreLoc.AATags.NoAlias);4132 })) {4133 LoadRecipe->moveBefore(*Preheader, Preheader->getFirstNonPhi());4134 }4135 }4136}4137 4138// Returns the intersection of metadata from a group of loads.4139static VPIRMetadata getCommonLoadMetadata(ArrayRef<VPReplicateRecipe *> Loads) {4140 VPIRMetadata CommonMetadata = *Loads.front();4141 for (VPReplicateRecipe *Load : drop_begin(Loads))4142 CommonMetadata.intersect(*Load);4143 return CommonMetadata;4144}4145 4146void VPlanTransforms::hoistPredicatedLoads(VPlan &Plan, ScalarEvolution &SE,4147 const Loop *L) {4148 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();4149 VPTypeAnalysis TypeInfo(Plan);4150 VPDominatorTree VPDT(Plan);4151 4152 // Group predicated loads by their address SCEV.4153 DenseMap<const SCEV *, SmallVector<VPReplicateRecipe *>> LoadsByAddress;4154 for (VPBlockBase *Block : vp_depth_first_shallow(LoopRegion->getEntry())) {4155 auto *VPBB = cast<VPBasicBlock>(Block);4156 for (VPRecipeBase &R : *VPBB) {4157 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);4158 if (!RepR || RepR->getOpcode() != Instruction::Load ||4159 !RepR->isPredicated())4160 continue;4161 4162 VPValue *Addr = RepR->getOperand(0);4163 const SCEV *AddrSCEV = vputils::getSCEVExprForVPValue(Addr, SE, L);4164 if (!isa<SCEVCouldNotCompute>(AddrSCEV))4165 LoadsByAddress[AddrSCEV].push_back(RepR);4166 }4167 }4168 4169 // For each address, collect loads with complementary masks, sort by4170 // dominance, and use the earliest load.4171 for (auto &[Addr, Loads] : LoadsByAddress) {4172 if (Loads.size() < 2)4173 continue;4174 4175 // Collect groups of loads with complementary masks.4176 SmallVector<SmallVector<VPReplicateRecipe *, 4>> LoadGroups;4177 for (VPReplicateRecipe *&LoadI : Loads) {4178 if (!LoadI)4179 continue;4180 4181 VPValue *MaskI = LoadI->getMask();4182 Type *TypeI = TypeInfo.inferScalarType(LoadI);4183 SmallVector<VPReplicateRecipe *, 4> Group;4184 Group.push_back(LoadI);4185 LoadI = nullptr;4186 4187 // Find all loads with the same type.4188 for (VPReplicateRecipe *&LoadJ : Loads) {4189 if (!LoadJ)4190 continue;4191 4192 Type *TypeJ = TypeInfo.inferScalarType(LoadJ);4193 if (TypeI == TypeJ) {4194 Group.push_back(LoadJ);4195 LoadJ = nullptr;4196 }4197 }4198 4199 // Check if any load in the group has a complementary mask with another,4200 // that is M1 == NOT(M2) or M2 == NOT(M1).4201 bool HasComplementaryMask =4202 any_of(drop_begin(Group), [MaskI](VPReplicateRecipe *Load) {4203 VPValue *MaskJ = Load->getMask();4204 return match(MaskI, m_Not(m_Specific(MaskJ))) ||4205 match(MaskJ, m_Not(m_Specific(MaskI)));4206 });4207 4208 if (HasComplementaryMask)4209 LoadGroups.push_back(std::move(Group));4210 }4211 4212 // For each group, check memory dependencies and hoist the earliest load.4213 for (auto &Group : LoadGroups) {4214 // Sort loads by dominance order, with earliest (most dominating) first.4215 sort(Group, [&VPDT](VPReplicateRecipe *A, VPReplicateRecipe *B) {4216 return VPDT.properlyDominates(A, B);4217 });4218 4219 VPReplicateRecipe *EarliestLoad = Group.front();4220 VPBasicBlock *FirstBB = EarliestLoad->getParent();4221 VPBasicBlock *LastBB = Group.back()->getParent();4222 4223 // Check that the load doesn't alias with stores between first and last.4224 if (!canHoistLoadWithNoAliasCheck(EarliestLoad, FirstBB, LastBB))4225 continue;4226 4227 // Find the load with minimum alignment to use.4228 auto *LoadWithMinAlign =4229 *min_element(Group, [](VPReplicateRecipe *A, VPReplicateRecipe *B) {4230 return cast<LoadInst>(A->getUnderlyingInstr())->getAlign() <4231 cast<LoadInst>(B->getUnderlyingInstr())->getAlign();4232 });4233 4234 // Collect common metadata from all loads in the group.4235 VPIRMetadata CommonMetadata = getCommonLoadMetadata(Group);4236 4237 // Create an unpredicated load with minimum alignment using the earliest4238 // dominating address and common metadata.4239 auto *UnpredicatedLoad = new VPReplicateRecipe(4240 LoadWithMinAlign->getUnderlyingInstr(), EarliestLoad->getOperand(0),4241 /*IsSingleScalar=*/false, /*Mask=*/nullptr, /*Flags=*/{},4242 CommonMetadata);4243 UnpredicatedLoad->insertBefore(EarliestLoad);4244 4245 // Replace all loads in the group with the unpredicated load.4246 for (VPReplicateRecipe *Load : Group) {4247 Load->replaceAllUsesWith(UnpredicatedLoad);4248 Load->eraseFromParent();4249 }4250 }4251 }4252}4253 4254void VPlanTransforms::materializeConstantVectorTripCount(4255 VPlan &Plan, ElementCount BestVF, unsigned BestUF,4256 PredicatedScalarEvolution &PSE) {4257 assert(Plan.hasVF(BestVF) && "BestVF is not available in Plan");4258 assert(Plan.hasUF(BestUF) && "BestUF is not available in Plan");4259 4260 VPValue *TC = Plan.getTripCount();4261 // Skip cases for which the trip count may be non-trivial to materialize.4262 // I.e., when a scalar tail is absent - due to tail folding, or when a scalar4263 // tail is required.4264 if (!Plan.hasScalarTail() ||4265 Plan.getMiddleBlock()->getSingleSuccessor() ==4266 Plan.getScalarPreheader() ||4267 !TC->isLiveIn())4268 return;4269 4270 // Materialize vector trip counts for constants early if it can simply4271 // be computed as (Original TC / VF * UF) * VF * UF.4272 // TODO: Compute vector trip counts for loops requiring a scalar epilogue and4273 // tail-folded loops.4274 ScalarEvolution &SE = *PSE.getSE();4275 auto *TCScev = SE.getSCEV(TC->getLiveInIRValue());4276 if (!isa<SCEVConstant>(TCScev))4277 return;4278 const SCEV *VFxUF = SE.getElementCount(TCScev->getType(), BestVF * BestUF);4279 auto VecTCScev = SE.getMulExpr(SE.getUDivExpr(TCScev, VFxUF), VFxUF);4280 if (auto *ConstVecTC = dyn_cast<SCEVConstant>(VecTCScev))4281 Plan.getVectorTripCount().setUnderlyingValue(ConstVecTC->getValue());4282}4283 4284void VPlanTransforms::materializeBackedgeTakenCount(VPlan &Plan,4285 VPBasicBlock *VectorPH) {4286 VPValue *BTC = Plan.getOrCreateBackedgeTakenCount();4287 if (BTC->getNumUsers() == 0)4288 return;4289 4290 VPBuilder Builder(VectorPH, VectorPH->begin());4291 auto *TCTy = VPTypeAnalysis(Plan).inferScalarType(Plan.getTripCount());4292 auto *TCMO = Builder.createNaryOp(4293 Instruction::Sub, {Plan.getTripCount(), Plan.getConstantInt(TCTy, 1)},4294 DebugLoc::getCompilerGenerated(), "trip.count.minus.1");4295 BTC->replaceAllUsesWith(TCMO);4296}4297 4298void VPlanTransforms::materializePacksAndUnpacks(VPlan &Plan) {4299 if (Plan.hasScalarVFOnly())4300 return;4301 4302 VPTypeAnalysis TypeInfo(Plan);4303 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();4304 auto VPBBsOutsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(4305 vp_depth_first_shallow(Plan.getEntry()));4306 auto VPBBsInsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(4307 vp_depth_first_shallow(LoopRegion->getEntry()));4308 // Materialize Build(Struct)Vector for all replicating VPReplicateRecipes and4309 // VPInstructions, excluding ones in replicate regions. Those are not4310 // materialized explicitly yet. Those vector users are still handled in4311 // VPReplicateRegion::execute(), via shouldPack().4312 // TODO: materialize build vectors for replicating recipes in replicating4313 // regions.4314 for (VPBasicBlock *VPBB :4315 concat<VPBasicBlock *>(VPBBsOutsideLoopRegion, VPBBsInsideLoopRegion)) {4316 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {4317 if (!isa<VPReplicateRecipe, VPInstruction>(&R))4318 continue;4319 auto *DefR = cast<VPRecipeWithIRFlags>(&R);4320 auto UsesVectorOrInsideReplicateRegion = [DefR, LoopRegion](VPUser *U) {4321 VPRegionBlock *ParentRegion = cast<VPRecipeBase>(U)->getRegion();4322 return !U->usesScalars(DefR) || ParentRegion != LoopRegion;4323 };4324 if ((isa<VPReplicateRecipe>(DefR) &&4325 cast<VPReplicateRecipe>(DefR)->isSingleScalar()) ||4326 (isa<VPInstruction>(DefR) &&4327 (vputils::onlyFirstLaneUsed(DefR) ||4328 !cast<VPInstruction>(DefR)->doesGeneratePerAllLanes())) ||4329 none_of(DefR->users(), UsesVectorOrInsideReplicateRegion))4330 continue;4331 4332 Type *ScalarTy = TypeInfo.inferScalarType(DefR);4333 unsigned Opcode = ScalarTy->isStructTy()4334 ? VPInstruction::BuildStructVector4335 : VPInstruction::BuildVector;4336 auto *BuildVector = new VPInstruction(Opcode, {DefR});4337 BuildVector->insertAfter(DefR);4338 4339 DefR->replaceUsesWithIf(4340 BuildVector, [BuildVector, &UsesVectorOrInsideReplicateRegion](4341 VPUser &U, unsigned) {4342 return &U != BuildVector && UsesVectorOrInsideReplicateRegion(&U);4343 });4344 }4345 }4346 4347 // Create explicit VPInstructions to convert vectors to scalars. The current4348 // implementation is conservative - it may miss some cases that may or may not4349 // be vector values. TODO: introduce Unpacks speculatively - remove them later4350 // if they are known to operate on scalar values.4351 for (VPBasicBlock *VPBB : VPBBsInsideLoopRegion) {4352 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {4353 if (isa<VPReplicateRecipe, VPInstruction, VPScalarIVStepsRecipe,4354 VPDerivedIVRecipe, VPCanonicalIVPHIRecipe>(&R))4355 continue;4356 for (VPValue *Def : R.definedValues()) {4357 // Skip recipes that are single-scalar or only have their first lane4358 // used.4359 // TODO: The Defs skipped here may or may not be vector values.4360 // Introduce Unpacks, and remove them later, if they are guaranteed to4361 // produce scalar values.4362 if (vputils::isSingleScalar(Def) || vputils::onlyFirstLaneUsed(Def))4363 continue;4364 4365 // At the moment, we create unpacks only for scalar users outside4366 // replicate regions. Recipes inside replicate regions still extract the4367 // required lanes implicitly.4368 // TODO: Remove once replicate regions are unrolled completely.4369 auto IsCandidateUnpackUser = [Def](VPUser *U) {4370 VPRegionBlock *ParentRegion = cast<VPRecipeBase>(U)->getRegion();4371 return U->usesScalars(Def) &&4372 (!ParentRegion || !ParentRegion->isReplicator());4373 };4374 if (none_of(Def->users(), IsCandidateUnpackUser))4375 continue;4376 4377 auto *Unpack = new VPInstruction(VPInstruction::Unpack, {Def});4378 if (R.isPhi())4379 Unpack->insertBefore(*VPBB, VPBB->getFirstNonPhi());4380 else4381 Unpack->insertAfter(&R);4382 Def->replaceUsesWithIf(Unpack,4383 [&IsCandidateUnpackUser](VPUser &U, unsigned) {4384 return IsCandidateUnpackUser(&U);4385 });4386 }4387 }4388 }4389}4390 4391void VPlanTransforms::materializeVectorTripCount(VPlan &Plan,4392 VPBasicBlock *VectorPHVPBB,4393 bool TailByMasking,4394 bool RequiresScalarEpilogue) {4395 VPValue &VectorTC = Plan.getVectorTripCount();4396 assert(VectorTC.isLiveIn() && "vector-trip-count must be a live-in");4397 // There's nothing to do if there are no users of the vector trip count or its4398 // IR value has already been set.4399 if (VectorTC.getNumUsers() == 0 || VectorTC.getLiveInIRValue())4400 return;4401 4402 VPValue *TC = Plan.getTripCount();4403 Type *TCTy = VPTypeAnalysis(Plan).inferScalarType(TC);4404 VPBuilder Builder(VectorPHVPBB, VectorPHVPBB->begin());4405 VPValue *Step = &Plan.getVFxUF();4406 4407 // If the tail is to be folded by masking, round the number of iterations N4408 // up to a multiple of Step instead of rounding down. This is done by first4409 // adding Step-1 and then rounding down. Note that it's ok if this addition4410 // overflows: the vector induction variable will eventually wrap to zero given4411 // that it starts at zero and its Step is a power of two; the loop will then4412 // exit, with the last early-exit vector comparison also producing all-true.4413 // For scalable vectors the VF is not guaranteed to be a power of 2, but this4414 // is accounted for in emitIterationCountCheck that adds an overflow check.4415 if (TailByMasking) {4416 TC = Builder.createNaryOp(4417 Instruction::Add,4418 {TC, Builder.createNaryOp(Instruction::Sub,4419 {Step, Plan.getConstantInt(TCTy, 1)})},4420 DebugLoc::getCompilerGenerated(), "n.rnd.up");4421 }4422 4423 // Now we need to generate the expression for the part of the loop that the4424 // vectorized body will execute. This is equal to N - (N % Step) if scalar4425 // iterations are not required for correctness, or N - Step, otherwise. Step4426 // is equal to the vectorization factor (number of SIMD elements) times the4427 // unroll factor (number of SIMD instructions).4428 VPValue *R =4429 Builder.createNaryOp(Instruction::URem, {TC, Step},4430 DebugLoc::getCompilerGenerated(), "n.mod.vf");4431 4432 // There are cases where we *must* run at least one iteration in the remainder4433 // loop. See the cost model for when this can happen. If the step evenly4434 // divides the trip count, we set the remainder to be equal to the step. If4435 // the step does not evenly divide the trip count, no adjustment is necessary4436 // since there will already be scalar iterations. Note that the minimum4437 // iterations check ensures that N >= Step.4438 if (RequiresScalarEpilogue) {4439 assert(!TailByMasking &&4440 "requiring scalar epilogue is not supported with fail folding");4441 VPValue *IsZero =4442 Builder.createICmp(CmpInst::ICMP_EQ, R, Plan.getConstantInt(TCTy, 0));4443 R = Builder.createSelect(IsZero, Step, R);4444 }4445 4446 VPValue *Res = Builder.createNaryOp(4447 Instruction::Sub, {TC, R}, DebugLoc::getCompilerGenerated(), "n.vec");4448 VectorTC.replaceAllUsesWith(Res);4449}4450 4451void VPlanTransforms::materializeVFAndVFxUF(VPlan &Plan, VPBasicBlock *VectorPH,4452 ElementCount VFEC) {4453 VPBuilder Builder(VectorPH, VectorPH->begin());4454 Type *TCTy = VPTypeAnalysis(Plan).inferScalarType(Plan.getTripCount());4455 VPValue &VF = Plan.getVF();4456 VPValue &VFxUF = Plan.getVFxUF();4457 // Note that after the transform, Plan.getVF and Plan.getVFxUF should not be4458 // used.4459 // TODO: Assert that they aren't used.4460 4461 // If there are no users of the runtime VF, compute VFxUF by constant folding4462 // the multiplication of VF and UF.4463 if (VF.getNumUsers() == 0) {4464 VPValue *RuntimeVFxUF =4465 Builder.createElementCount(TCTy, VFEC * Plan.getUF());4466 VFxUF.replaceAllUsesWith(RuntimeVFxUF);4467 return;4468 }4469 4470 // For users of the runtime VF, compute it as VF * vscale, and VFxUF as (VF *4471 // vscale) * UF.4472 VPValue *RuntimeVF = Builder.createElementCount(TCTy, VFEC);4473 if (!vputils::onlyScalarValuesUsed(&VF)) {4474 VPValue *BC = Builder.createNaryOp(VPInstruction::Broadcast, RuntimeVF);4475 VF.replaceUsesWithIf(4476 BC, [&VF](VPUser &U, unsigned) { return !U.usesScalars(&VF); });4477 }4478 VF.replaceAllUsesWith(RuntimeVF);4479 4480 VPValue *UF = Plan.getConstantInt(TCTy, Plan.getUF());4481 VPValue *MulByUF = Builder.createNaryOp(Instruction::Mul, {RuntimeVF, UF});4482 VFxUF.replaceAllUsesWith(MulByUF);4483}4484 4485DenseMap<const SCEV *, Value *>4486VPlanTransforms::expandSCEVs(VPlan &Plan, ScalarEvolution &SE) {4487 const DataLayout &DL = SE.getDataLayout();4488 SCEVExpander Expander(SE, DL, "induction", /*PreserveLCSSA=*/false);4489 4490 auto *Entry = cast<VPIRBasicBlock>(Plan.getEntry());4491 BasicBlock *EntryBB = Entry->getIRBasicBlock();4492 DenseMap<const SCEV *, Value *> ExpandedSCEVs;4493 for (VPRecipeBase &R : make_early_inc_range(*Entry)) {4494 if (isa<VPIRInstruction, VPIRPhi>(&R))4495 continue;4496 auto *ExpSCEV = dyn_cast<VPExpandSCEVRecipe>(&R);4497 if (!ExpSCEV)4498 break;4499 const SCEV *Expr = ExpSCEV->getSCEV();4500 Value *Res =4501 Expander.expandCodeFor(Expr, Expr->getType(), EntryBB->getTerminator());4502 ExpandedSCEVs[ExpSCEV->getSCEV()] = Res;4503 VPValue *Exp = Plan.getOrAddLiveIn(Res);4504 ExpSCEV->replaceAllUsesWith(Exp);4505 if (Plan.getTripCount() == ExpSCEV)4506 Plan.resetTripCount(Exp);4507 ExpSCEV->eraseFromParent();4508 }4509 assert(none_of(*Entry, IsaPred<VPExpandSCEVRecipe>) &&4510 "VPExpandSCEVRecipes must be at the beginning of the entry block, "4511 "after any VPIRInstructions");4512 // Add IR instructions in the entry basic block but not in the VPIRBasicBlock4513 // to the VPIRBasicBlock.4514 auto EI = Entry->begin();4515 for (Instruction &I : drop_end(*EntryBB)) {4516 if (EI != Entry->end() && isa<VPIRInstruction>(*EI) &&4517 &cast<VPIRInstruction>(&*EI)->getInstruction() == &I) {4518 EI++;4519 continue;4520 }4521 VPIRInstruction::create(I)->insertBefore(*Entry, EI);4522 }4523 4524 return ExpandedSCEVs;4525}4526 4527/// Returns true if \p V is VPWidenLoadRecipe or VPInterleaveRecipe that can be4528/// converted to a narrower recipe. \p V is used by a wide recipe that feeds a4529/// store interleave group at index \p Idx, \p WideMember0 is the recipe feeding4530/// the same interleave group at index 0. A VPWidenLoadRecipe can be narrowed to4531/// an index-independent load if it feeds all wide ops at all indices (\p OpV4532/// must be the operand at index \p OpIdx for both the recipe at lane 0, \p4533/// WideMember0). A VPInterleaveRecipe can be narrowed to a wide load, if \p V4534/// is defined at \p Idx of a load interleave group.4535static bool canNarrowLoad(VPWidenRecipe *WideMember0, unsigned OpIdx,4536 VPValue *OpV, unsigned Idx) {4537 VPValue *Member0Op = WideMember0->getOperand(OpIdx);4538 VPRecipeBase *Member0OpR = Member0Op->getDefiningRecipe();4539 if (!Member0OpR)4540 return Member0Op == OpV;4541 if (auto *W = dyn_cast<VPWidenLoadRecipe>(Member0OpR))4542 return !W->getMask() && Member0Op == OpV;4543 if (auto *IR = dyn_cast<VPInterleaveRecipe>(Member0OpR))4544 return IR->getInterleaveGroup()->isFull() && IR->getVPValue(Idx) == OpV;4545 return false;4546}4547 4548/// Returns true if \p IR is a full interleave group with factor and number of4549/// members both equal to \p VF. The interleave group must also access the full4550/// vector width \p VectorRegWidth.4551static bool isConsecutiveInterleaveGroup(VPInterleaveRecipe *InterleaveR,4552 ElementCount VF,4553 VPTypeAnalysis &TypeInfo,4554 TypeSize VectorRegWidth) {4555 if (!InterleaveR || InterleaveR->getMask())4556 return false;4557 4558 Type *GroupElementTy = nullptr;4559 if (InterleaveR->getStoredValues().empty()) {4560 GroupElementTy = TypeInfo.inferScalarType(InterleaveR->getVPValue(0));4561 if (!all_of(InterleaveR->definedValues(),4562 [&TypeInfo, GroupElementTy](VPValue *Op) {4563 return TypeInfo.inferScalarType(Op) == GroupElementTy;4564 }))4565 return false;4566 } else {4567 GroupElementTy =4568 TypeInfo.inferScalarType(InterleaveR->getStoredValues()[0]);4569 if (!all_of(InterleaveR->getStoredValues(),4570 [&TypeInfo, GroupElementTy](VPValue *Op) {4571 return TypeInfo.inferScalarType(Op) == GroupElementTy;4572 }))4573 return false;4574 }4575 4576 unsigned VFMin = VF.getKnownMinValue();4577 TypeSize GroupSize = TypeSize::get(4578 GroupElementTy->getScalarSizeInBits() * VFMin, VF.isScalable());4579 const auto *IG = InterleaveR->getInterleaveGroup();4580 return IG->getFactor() == VFMin && IG->getNumMembers() == VFMin &&4581 GroupSize == VectorRegWidth;4582}4583 4584/// Returns true if \p VPValue is a narrow VPValue.4585static bool isAlreadyNarrow(VPValue *VPV) {4586 if (VPV->isLiveIn())4587 return true;4588 auto *RepR = dyn_cast<VPReplicateRecipe>(VPV);4589 return RepR && RepR->isSingleScalar();4590}4591 4592// Convert a wide recipe defining a VPValue \p V feeding an interleave group to4593// a narrow variant.4594static VPValue *4595narrowInterleaveGroupOp(VPValue *V, SmallPtrSetImpl<VPValue *> &NarrowedOps) {4596 auto *R = V->getDefiningRecipe();4597 if (!R || NarrowedOps.contains(V))4598 return V;4599 4600 if (isAlreadyNarrow(V))4601 return V;4602 4603 if (auto *WideMember0 = dyn_cast<VPWidenRecipe>(R)) {4604 for (unsigned Idx = 0, E = WideMember0->getNumOperands(); Idx != E; ++Idx)4605 WideMember0->setOperand(4606 Idx,4607 narrowInterleaveGroupOp(WideMember0->getOperand(Idx), NarrowedOps));4608 return V;4609 }4610 4611 if (auto *LoadGroup = dyn_cast<VPInterleaveRecipe>(R)) {4612 // Narrow interleave group to wide load, as transformed VPlan will only4613 // process one original iteration.4614 auto *LI = cast<LoadInst>(LoadGroup->getInterleaveGroup()->getInsertPos());4615 auto *L = new VPWidenLoadRecipe(4616 *LI, LoadGroup->getAddr(), LoadGroup->getMask(), /*Consecutive=*/true,4617 /*Reverse=*/false, {}, LoadGroup->getDebugLoc());4618 L->insertBefore(LoadGroup);4619 NarrowedOps.insert(L);4620 return L;4621 }4622 4623 if (auto *RepR = dyn_cast<VPReplicateRecipe>(R)) {4624 assert(RepR->isSingleScalar() &&4625 isa<LoadInst>(RepR->getUnderlyingInstr()) &&4626 "must be a single scalar load");4627 NarrowedOps.insert(RepR);4628 return RepR;4629 }4630 4631 auto *WideLoad = cast<VPWidenLoadRecipe>(R);4632 VPValue *PtrOp = WideLoad->getAddr();4633 if (auto *VecPtr = dyn_cast<VPVectorPointerRecipe>(PtrOp))4634 PtrOp = VecPtr->getOperand(0);4635 // Narrow wide load to uniform scalar load, as transformed VPlan will only4636 // process one original iteration.4637 auto *N = new VPReplicateRecipe(&WideLoad->getIngredient(), {PtrOp},4638 /*IsUniform*/ true,4639 /*Mask*/ nullptr, {}, *WideLoad);4640 N->insertBefore(WideLoad);4641 NarrowedOps.insert(N);4642 return N;4643}4644 4645void VPlanTransforms::narrowInterleaveGroups(VPlan &Plan, ElementCount VF,4646 TypeSize VectorRegWidth) {4647 VPRegionBlock *VectorLoop = Plan.getVectorLoopRegion();4648 if (!VectorLoop || VectorLoop->getEntry()->getNumSuccessors() != 0)4649 return;4650 4651 VPTypeAnalysis TypeInfo(Plan);4652 4653 SmallVector<VPInterleaveRecipe *> StoreGroups;4654 for (auto &R : *VectorLoop->getEntryBasicBlock()) {4655 if (isa<VPCanonicalIVPHIRecipe>(&R))4656 continue;4657 4658 if (isa<VPDerivedIVRecipe, VPScalarIVStepsRecipe>(&R) &&4659 vputils::onlyFirstLaneUsed(cast<VPSingleDefRecipe>(&R)))4660 continue;4661 4662 // Bail out on recipes not supported at the moment:4663 // * phi recipes other than the canonical induction4664 // * recipes writing to memory except interleave groups4665 // Only support plans with a canonical induction phi.4666 if (R.isPhi())4667 return;4668 4669 auto *InterleaveR = dyn_cast<VPInterleaveRecipe>(&R);4670 if (R.mayWriteToMemory() && !InterleaveR)4671 return;4672 4673 // Do not narrow interleave groups if there are VectorPointer recipes and4674 // the plan was unrolled. The recipe implicitly uses VF from4675 // VPTransformState.4676 // TODO: Remove restriction once the VF for the VectorPointer offset is4677 // modeled explicitly as operand.4678 if (isa<VPVectorPointerRecipe>(&R) && Plan.getUF() > 1)4679 return;4680 4681 // All other ops are allowed, but we reject uses that cannot be converted4682 // when checking all allowed consumers (store interleave groups) below.4683 if (!InterleaveR)4684 continue;4685 4686 // Bail out on non-consecutive interleave groups.4687 if (!isConsecutiveInterleaveGroup(InterleaveR, VF, TypeInfo,4688 VectorRegWidth))4689 return;4690 4691 // Skip read interleave groups.4692 if (InterleaveR->getStoredValues().empty())4693 continue;4694 4695 // Narrow interleave groups, if all operands are already matching narrow4696 // ops.4697 auto *Member0 = InterleaveR->getStoredValues()[0];4698 if (isAlreadyNarrow(Member0) &&4699 all_of(InterleaveR->getStoredValues(),4700 [Member0](VPValue *VPV) { return Member0 == VPV; })) {4701 StoreGroups.push_back(InterleaveR);4702 continue;4703 }4704 4705 // For now, we only support full interleave groups storing load interleave4706 // groups.4707 if (all_of(enumerate(InterleaveR->getStoredValues()), [](auto Op) {4708 VPRecipeBase *DefR = Op.value()->getDefiningRecipe();4709 if (!DefR)4710 return false;4711 auto *IR = dyn_cast<VPInterleaveRecipe>(DefR);4712 return IR && IR->getInterleaveGroup()->isFull() &&4713 IR->getVPValue(Op.index()) == Op.value();4714 })) {4715 StoreGroups.push_back(InterleaveR);4716 continue;4717 }4718 4719 // Check if all values feeding InterleaveR are matching wide recipes, which4720 // operands that can be narrowed.4721 auto *WideMember0 =4722 dyn_cast_or_null<VPWidenRecipe>(InterleaveR->getStoredValues()[0]);4723 if (!WideMember0)4724 return;4725 for (const auto &[I, V] : enumerate(InterleaveR->getStoredValues())) {4726 auto *R = dyn_cast_or_null<VPWidenRecipe>(V);4727 if (!R || R->getOpcode() != WideMember0->getOpcode() ||4728 R->getNumOperands() > 2)4729 return;4730 if (any_of(enumerate(R->operands()),4731 [WideMember0, Idx = I](const auto &P) {4732 const auto &[OpIdx, OpV] = P;4733 return !canNarrowLoad(WideMember0, OpIdx, OpV, Idx);4734 }))4735 return;4736 }4737 StoreGroups.push_back(InterleaveR);4738 }4739 4740 if (StoreGroups.empty())4741 return;4742 4743 // Convert InterleaveGroup \p R to a single VPWidenLoadRecipe.4744 SmallPtrSet<VPValue *, 4> NarrowedOps;4745 // Narrow operation tree rooted at store groups.4746 for (auto *StoreGroup : StoreGroups) {4747 VPValue *Res =4748 narrowInterleaveGroupOp(StoreGroup->getStoredValues()[0], NarrowedOps);4749 auto *SI =4750 cast<StoreInst>(StoreGroup->getInterleaveGroup()->getInsertPos());4751 auto *S = new VPWidenStoreRecipe(4752 *SI, StoreGroup->getAddr(), Res, nullptr, /*Consecutive=*/true,4753 /*Reverse=*/false, {}, StoreGroup->getDebugLoc());4754 S->insertBefore(StoreGroup);4755 StoreGroup->eraseFromParent();4756 }4757 4758 // Adjust induction to reflect that the transformed plan only processes one4759 // original iteration.4760 auto *CanIV = VectorLoop->getCanonicalIV();4761 auto *Inc = cast<VPInstruction>(CanIV->getBackedgeValue());4762 VPBuilder PHBuilder(Plan.getVectorPreheader());4763 4764 VPValue *UF = Plan.getOrAddLiveIn(4765 ConstantInt::get(VectorLoop->getCanonicalIVType(), 1 * Plan.getUF()));4766 if (VF.isScalable()) {4767 VPValue *VScale = PHBuilder.createElementCount(4768 VectorLoop->getCanonicalIVType(), ElementCount::getScalable(1));4769 VPValue *VScaleUF = PHBuilder.createNaryOp(Instruction::Mul, {VScale, UF});4770 Inc->setOperand(1, VScaleUF);4771 Plan.getVF().replaceAllUsesWith(VScale);4772 } else {4773 Inc->setOperand(1, UF);4774 Plan.getVF().replaceAllUsesWith(4775 Plan.getConstantInt(CanIV->getScalarType(), 1));4776 }4777 removeDeadRecipes(Plan);4778}4779 4780/// Add branch weight metadata, if the \p Plan's middle block is terminated by a4781/// BranchOnCond recipe.4782void VPlanTransforms::addBranchWeightToMiddleTerminator(4783 VPlan &Plan, ElementCount VF, std::optional<unsigned> VScaleForTuning) {4784 VPBasicBlock *MiddleVPBB = Plan.getMiddleBlock();4785 auto *MiddleTerm =4786 dyn_cast_or_null<VPInstruction>(MiddleVPBB->getTerminator());4787 // Only add branch metadata if there is a (conditional) terminator.4788 if (!MiddleTerm)4789 return;4790 4791 assert(MiddleTerm->getOpcode() == VPInstruction::BranchOnCond &&4792 "must have a BranchOnCond");4793 // Assume that `TripCount % VectorStep ` is equally distributed.4794 unsigned VectorStep = Plan.getUF() * VF.getKnownMinValue();4795 if (VF.isScalable() && VScaleForTuning.has_value())4796 VectorStep *= *VScaleForTuning;4797 assert(VectorStep > 0 && "trip count should not be zero");4798 MDBuilder MDB(Plan.getContext());4799 MDNode *BranchWeights =4800 MDB.createBranchWeights({1, VectorStep - 1}, /*IsExpected=*/false);4801 MiddleTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);4802}4803 4804/// Compute and return the end value for \p WideIV, unless it is truncated. If4805/// the induction recipe is not canonical, creates a VPDerivedIVRecipe to4806/// compute the end value of the induction.4807static VPValue *tryToComputeEndValueForInduction(VPWidenInductionRecipe *WideIV,4808 VPBuilder &VectorPHBuilder,4809 VPTypeAnalysis &TypeInfo,4810 VPValue *VectorTC) {4811 auto *WideIntOrFp = dyn_cast<VPWidenIntOrFpInductionRecipe>(WideIV);4812 // Truncated wide inductions resume from the last lane of their vector value4813 // in the last vector iteration which is handled elsewhere.4814 if (WideIntOrFp && WideIntOrFp->getTruncInst())4815 return nullptr;4816 4817 VPValue *Start = WideIV->getStartValue();4818 VPValue *Step = WideIV->getStepValue();4819 const InductionDescriptor &ID = WideIV->getInductionDescriptor();4820 VPValue *EndValue = VectorTC;4821 if (!WideIntOrFp || !WideIntOrFp->isCanonical()) {4822 EndValue = VectorPHBuilder.createDerivedIV(4823 ID.getKind(), dyn_cast_or_null<FPMathOperator>(ID.getInductionBinOp()),4824 Start, VectorTC, Step);4825 }4826 4827 // EndValue is derived from the vector trip count (which has the same type as4828 // the widest induction) and thus may be wider than the induction here.4829 Type *ScalarTypeOfWideIV = TypeInfo.inferScalarType(WideIV);4830 if (ScalarTypeOfWideIV != TypeInfo.inferScalarType(EndValue)) {4831 EndValue = VectorPHBuilder.createScalarCast(Instruction::Trunc, EndValue,4832 ScalarTypeOfWideIV,4833 WideIV->getDebugLoc());4834 }4835 4836 return EndValue;4837}4838 4839void VPlanTransforms::updateScalarResumePhis(4840 VPlan &Plan, DenseMap<VPValue *, VPValue *> &IVEndValues) {4841 VPTypeAnalysis TypeInfo(Plan);4842 auto *ScalarPH = Plan.getScalarPreheader();4843 auto *MiddleVPBB = cast<VPBasicBlock>(ScalarPH->getPredecessors()[0]);4844 VPRegionBlock *VectorRegion = Plan.getVectorLoopRegion();4845 VPBuilder VectorPHBuilder(4846 cast<VPBasicBlock>(VectorRegion->getSinglePredecessor()));4847 VPBuilder MiddleBuilder(MiddleVPBB, MiddleVPBB->getFirstNonPhi());4848 for (VPRecipeBase &PhiR : Plan.getScalarPreheader()->phis()) {4849 auto *ResumePhiR = cast<VPPhi>(&PhiR);4850 4851 // TODO: Extract final value from induction recipe initially, optimize to4852 // pre-computed end value together in optimizeInductionExitUsers.4853 auto *VectorPhiR = cast<VPHeaderPHIRecipe>(ResumePhiR->getOperand(0));4854 if (auto *WideIVR = dyn_cast<VPWidenInductionRecipe>(VectorPhiR)) {4855 if (VPValue *EndValue = tryToComputeEndValueForInduction(4856 WideIVR, VectorPHBuilder, TypeInfo, &Plan.getVectorTripCount())) {4857 IVEndValues[WideIVR] = EndValue;4858 ResumePhiR->setOperand(0, EndValue);4859 ResumePhiR->setName("bc.resume.val");4860 continue;4861 }4862 // TODO: Also handle truncated inductions here. Computing end-values4863 // separately should be done as VPlan-to-VPlan optimization, after4864 // legalizing all resume values to use the last lane from the loop.4865 assert(cast<VPWidenIntOrFpInductionRecipe>(VectorPhiR)->getTruncInst() &&4866 "should only skip truncated wide inductions");4867 continue;4868 }4869 4870 // The backedge value provides the value to resume coming out of a loop,4871 // which for FORs is a vector whose last element needs to be extracted. The4872 // start value provides the value if the loop is bypassed.4873 bool IsFOR = isa<VPFirstOrderRecurrencePHIRecipe>(VectorPhiR);4874 auto *ResumeFromVectorLoop = VectorPhiR->getBackedgeValue();4875 assert(VectorRegion->getSingleSuccessor() == Plan.getMiddleBlock() &&4876 "Cannot handle loops with uncountable early exits");4877 if (IsFOR)4878 ResumeFromVectorLoop = MiddleBuilder.createNaryOp(4879 VPInstruction::ExtractLastElement, {ResumeFromVectorLoop}, {},4880 "vector.recur.extract");4881 ResumePhiR->setName(IsFOR ? "scalar.recur.init" : "bc.merge.rdx");4882 ResumePhiR->setOperand(0, ResumeFromVectorLoop);4883 }4884}4885 4886void VPlanTransforms::addExitUsersForFirstOrderRecurrences(VPlan &Plan,4887 VFRange &Range) {4888 VPRegionBlock *VectorRegion = Plan.getVectorLoopRegion();4889 auto *ScalarPHVPBB = Plan.getScalarPreheader();4890 auto *MiddleVPBB = Plan.getMiddleBlock();4891 VPBuilder ScalarPHBuilder(ScalarPHVPBB);4892 VPBuilder MiddleBuilder(MiddleVPBB, MiddleVPBB->getFirstNonPhi());4893 4894 auto IsScalableOne = [](ElementCount VF) -> bool {4895 return VF == ElementCount::getScalable(1);4896 };4897 4898 for (auto &HeaderPhi : VectorRegion->getEntryBasicBlock()->phis()) {4899 auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&HeaderPhi);4900 if (!FOR)4901 continue;4902 4903 assert(VectorRegion->getSingleSuccessor() == Plan.getMiddleBlock() &&4904 "Cannot handle loops with uncountable early exits");4905 4906 // This is the second phase of vectorizing first-order recurrences, creating4907 // extract for users outside the loop. An overview of the transformation is4908 // described below. Suppose we have the following loop with some use after4909 // the loop of the last a[i-1],4910 //4911 // for (int i = 0; i < n; ++i) {4912 // t = a[i - 1];4913 // b[i] = a[i] - t;4914 // }4915 // use t;4916 //4917 // There is a first-order recurrence on "a". For this loop, the shorthand4918 // scalar IR looks like:4919 //4920 // scalar.ph:4921 // s.init = a[-1]4922 // br scalar.body4923 //4924 // scalar.body:4925 // i = phi [0, scalar.ph], [i+1, scalar.body]4926 // s1 = phi [s.init, scalar.ph], [s2, scalar.body]4927 // s2 = a[i]4928 // b[i] = s2 - s14929 // br cond, scalar.body, exit.block4930 //4931 // exit.block:4932 // use = lcssa.phi [s1, scalar.body]4933 //4934 // In this example, s1 is a recurrence because it's value depends on the4935 // previous iteration. In the first phase of vectorization, we created a4936 // VPFirstOrderRecurrencePHIRecipe v1 for s1. Now we create the extracts4937 // for users in the scalar preheader and exit block.4938 //4939 // vector.ph:4940 // v_init = vector(..., ..., ..., a[-1])4941 // br vector.body4942 //4943 // vector.body4944 // i = phi [0, vector.ph], [i+4, vector.body]4945 // v1 = phi [v_init, vector.ph], [v2, vector.body]4946 // v2 = a[i, i+1, i+2, i+3]4947 // b[i] = v2 - v14948 // // Next, third phase will introduce v1' = splice(v1(3), v2(0, 1, 2))4949 // b[i, i+1, i+2, i+3] = v2 - v14950 // br cond, vector.body, middle.block4951 //4952 // middle.block:4953 // vector.recur.extract.for.phi = v2(2)4954 // vector.recur.extract = v2(3)4955 // br cond, scalar.ph, exit.block4956 //4957 // scalar.ph:4958 // scalar.recur.init = phi [vector.recur.extract, middle.block],4959 // [s.init, otherwise]4960 // br scalar.body4961 //4962 // scalar.body:4963 // i = phi [0, scalar.ph], [i+1, scalar.body]4964 // s1 = phi [scalar.recur.init, scalar.ph], [s2, scalar.body]4965 // s2 = a[i]4966 // b[i] = s2 - s14967 // br cond, scalar.body, exit.block4968 //4969 // exit.block:4970 // lo = lcssa.phi [s1, scalar.body],4971 // [vector.recur.extract.for.phi, middle.block]4972 //4973 // Now update VPIRInstructions modeling LCSSA phis in the exit block.4974 // Extract the penultimate value of the recurrence and use it as operand for4975 // the VPIRInstruction modeling the phi.4976 for (VPUser *U : FOR->users()) {4977 using namespace llvm::VPlanPatternMatch;4978 if (!match(U, m_ExtractLastElement(m_Specific(FOR))))4979 continue;4980 // For VF vscale x 1, if vscale = 1, we are unable to extract the4981 // penultimate value of the recurrence. Instead we rely on the existing4982 // extract of the last element from the result of4983 // VPInstruction::FirstOrderRecurrenceSplice.4984 // TODO: Consider vscale_range info and UF.4985 if (LoopVectorizationPlanner::getDecisionAndClampRange(IsScalableOne,4986 Range))4987 return;4988 VPValue *PenultimateElement = MiddleBuilder.createNaryOp(4989 VPInstruction::ExtractPenultimateElement, {FOR->getBackedgeValue()},4990 {}, "vector.recur.extract.for.phi");4991 cast<VPInstruction>(U)->replaceAllUsesWith(PenultimateElement);4992 }4993 }4994}4995