642 lines · cpp
1//===- VPlanAnalysis.cpp - Various Analyses working on VPlan ----*- C++ -*-===//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#include "VPlanAnalysis.h"10#include "VPlan.h"11#include "VPlanCFG.h"12#include "VPlanDominatorTree.h"13#include "VPlanHelpers.h"14#include "VPlanPatternMatch.h"15#include "llvm/ADT/PostOrderIterator.h"16#include "llvm/ADT/TypeSwitch.h"17#include "llvm/Analysis/ScalarEvolution.h"18#include "llvm/Analysis/TargetTransformInfo.h"19#include "llvm/IR/Instruction.h"20#include "llvm/IR/PatternMatch.h"21 22using namespace llvm;23using namespace VPlanPatternMatch;24 25#define DEBUG_TYPE "vplan"26 27VPTypeAnalysis::VPTypeAnalysis(const VPlan &Plan) : Ctx(Plan.getContext()) {28 if (auto LoopRegion = Plan.getVectorLoopRegion()) {29 if (const auto *CanIV = dyn_cast<VPCanonicalIVPHIRecipe>(30 &LoopRegion->getEntryBasicBlock()->front())) {31 CanonicalIVTy = CanIV->getScalarType();32 return;33 }34 }35 36 // If there's no canonical IV, retrieve the type from the trip count37 // expression.38 auto *TC = Plan.getTripCount();39 if (TC->isLiveIn()) {40 CanonicalIVTy = TC->getLiveInIRValue()->getType();41 return;42 }43 CanonicalIVTy = cast<VPExpandSCEVRecipe>(TC)->getSCEV()->getType();44}45 46Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPBlendRecipe *R) {47 Type *ResTy = inferScalarType(R->getIncomingValue(0));48 for (unsigned I = 1, E = R->getNumIncomingValues(); I != E; ++I) {49 VPValue *Inc = R->getIncomingValue(I);50 assert(inferScalarType(Inc) == ResTy &&51 "different types inferred for different incoming values");52 CachedTypes[Inc] = ResTy;53 }54 return ResTy;55}56 57Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPInstruction *R) {58 // Set the result type from the first operand, check if the types for all59 // other operands match and cache them.60 auto SetResultTyFromOp = [this, R]() {61 Type *ResTy = inferScalarType(R->getOperand(0));62 for (unsigned Op = 1; Op != R->getNumOperands(); ++Op) {63 VPValue *OtherV = R->getOperand(Op);64 assert(inferScalarType(OtherV) == ResTy &&65 "different types inferred for different operands");66 CachedTypes[OtherV] = ResTy;67 }68 return ResTy;69 };70 71 unsigned Opcode = R->getOpcode();72 if (Instruction::isBinaryOp(Opcode) || Instruction::isUnaryOp(Opcode))73 return SetResultTyFromOp();74 75 switch (Opcode) {76 case Instruction::ExtractElement:77 case Instruction::Freeze:78 case VPInstruction::ReductionStartVector:79 case VPInstruction::ResumeForEpilogue:80 return inferScalarType(R->getOperand(0));81 case Instruction::Select: {82 Type *ResTy = inferScalarType(R->getOperand(1));83 VPValue *OtherV = R->getOperand(2);84 assert(inferScalarType(OtherV) == ResTy &&85 "different types inferred for different operands");86 CachedTypes[OtherV] = ResTy;87 return ResTy;88 }89 case Instruction::ICmp:90 case Instruction::FCmp:91 case VPInstruction::ActiveLaneMask:92 assert(inferScalarType(R->getOperand(0)) ==93 inferScalarType(R->getOperand(1)) &&94 "different types inferred for different operands");95 return IntegerType::get(Ctx, 1);96 case VPInstruction::ComputeAnyOfResult:97 return inferScalarType(R->getOperand(1));98 case VPInstruction::ComputeFindIVResult:99 case VPInstruction::ComputeReductionResult: {100 return inferScalarType(R->getOperand(0));101 }102 case VPInstruction::ExplicitVectorLength:103 return Type::getIntNTy(Ctx, 32);104 case Instruction::PHI:105 // Infer the type of first operand only, as other operands of header phi's106 // may lead to infinite recursion.107 return inferScalarType(R->getOperand(0));108 case VPInstruction::FirstOrderRecurrenceSplice:109 case VPInstruction::Not:110 case VPInstruction::CalculateTripCountMinusVF:111 case VPInstruction::CanonicalIVIncrementForPart:112 case VPInstruction::AnyOf:113 case VPInstruction::BuildStructVector:114 case VPInstruction::BuildVector:115 case VPInstruction::Unpack:116 return SetResultTyFromOp();117 case VPInstruction::ExtractLane:118 return inferScalarType(R->getOperand(1));119 case VPInstruction::FirstActiveLane:120 case VPInstruction::LastActiveLane:121 return Type::getIntNTy(Ctx, 64);122 case VPInstruction::ExtractLastElement:123 case VPInstruction::ExtractLastLanePerPart:124 case VPInstruction::ExtractPenultimateElement: {125 Type *BaseTy = inferScalarType(R->getOperand(0));126 if (auto *VecTy = dyn_cast<VectorType>(BaseTy))127 return VecTy->getElementType();128 return BaseTy;129 }130 case VPInstruction::LogicalAnd:131 assert(inferScalarType(R->getOperand(0))->isIntegerTy(1) &&132 inferScalarType(R->getOperand(1))->isIntegerTy(1) &&133 "LogicalAnd operands should be bool");134 return IntegerType::get(Ctx, 1);135 case VPInstruction::Broadcast:136 case VPInstruction::PtrAdd:137 case VPInstruction::WidePtrAdd:138 // Return the type based on first operand.139 return inferScalarType(R->getOperand(0));140 case VPInstruction::BranchOnCond:141 case VPInstruction::BranchOnCount:142 return Type::getVoidTy(Ctx);143 default:144 break;145 }146 // Type inference not implemented for opcode.147 LLVM_DEBUG({148 dbgs() << "LV: Found unhandled opcode for: ";149 R->getVPSingleValue()->dump();150 });151 llvm_unreachable("Unhandled opcode!");152}153 154Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenRecipe *R) {155 unsigned Opcode = R->getOpcode();156 if (Instruction::isBinaryOp(Opcode) || Instruction::isShift(Opcode) ||157 Instruction::isBitwiseLogicOp(Opcode)) {158 Type *ResTy = inferScalarType(R->getOperand(0));159 assert(ResTy == inferScalarType(R->getOperand(1)) &&160 "types for both operands must match for binary op");161 CachedTypes[R->getOperand(1)] = ResTy;162 return ResTy;163 }164 165 switch (Opcode) {166 case Instruction::ICmp:167 case Instruction::FCmp:168 return IntegerType::get(Ctx, 1);169 case Instruction::FNeg:170 case Instruction::Freeze:171 return inferScalarType(R->getOperand(0));172 case Instruction::ExtractValue: {173 assert(R->getNumOperands() == 2 && "expected single level extractvalue");174 auto *StructTy = cast<StructType>(inferScalarType(R->getOperand(0)));175 auto *CI = cast<ConstantInt>(R->getOperand(1)->getLiveInIRValue());176 return StructTy->getTypeAtIndex(CI->getZExtValue());177 }178 default:179 break;180 }181 182 // Type inference not implemented for opcode.183 LLVM_DEBUG({184 dbgs() << "LV: Found unhandled opcode for: ";185 R->getVPSingleValue()->dump();186 });187 llvm_unreachable("Unhandled opcode!");188}189 190Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenCallRecipe *R) {191 auto &CI = *cast<CallInst>(R->getUnderlyingInstr());192 return CI.getType();193}194 195Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenMemoryRecipe *R) {196 assert((isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(R)) &&197 "Store recipes should not define any values");198 return cast<LoadInst>(&R->getIngredient())->getType();199}200 201Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPWidenSelectRecipe *R) {202 Type *ResTy = inferScalarType(R->getOperand(1));203 VPValue *OtherV = R->getOperand(2);204 assert(inferScalarType(OtherV) == ResTy &&205 "different types inferred for different operands");206 CachedTypes[OtherV] = ResTy;207 return ResTy;208}209 210Type *VPTypeAnalysis::inferScalarTypeForRecipe(const VPReplicateRecipe *R) {211 unsigned Opcode = R->getUnderlyingInstr()->getOpcode();212 213 if (Instruction::isBinaryOp(Opcode) || Instruction::isShift(Opcode) ||214 Instruction::isBitwiseLogicOp(Opcode)) {215 Type *ResTy = inferScalarType(R->getOperand(0));216 assert(ResTy == inferScalarType(R->getOperand(1)) &&217 "inferred types for operands of binary op don't match");218 CachedTypes[R->getOperand(1)] = ResTy;219 return ResTy;220 }221 222 if (Instruction::isCast(Opcode))223 return R->getUnderlyingInstr()->getType();224 225 switch (Opcode) {226 case Instruction::Call: {227 unsigned CallIdx = R->getNumOperands() - (R->isPredicated() ? 2 : 1);228 return cast<Function>(R->getOperand(CallIdx)->getLiveInIRValue())229 ->getReturnType();230 }231 case Instruction::Select: {232 Type *ResTy = inferScalarType(R->getOperand(1));233 assert(ResTy == inferScalarType(R->getOperand(2)) &&234 "inferred types for operands of select op don't match");235 CachedTypes[R->getOperand(2)] = ResTy;236 return ResTy;237 }238 case Instruction::ICmp:239 case Instruction::FCmp:240 return IntegerType::get(Ctx, 1);241 case Instruction::Alloca:242 case Instruction::ExtractValue:243 return R->getUnderlyingInstr()->getType();244 case Instruction::Freeze:245 case Instruction::FNeg:246 case Instruction::GetElementPtr:247 return inferScalarType(R->getOperand(0));248 case Instruction::Load:249 return cast<LoadInst>(R->getUnderlyingInstr())->getType();250 case Instruction::Store:251 // FIXME: VPReplicateRecipes with store opcodes still define a result252 // VPValue, so we need to handle them here. Remove the code here once this253 // is modeled accurately in VPlan.254 return Type::getVoidTy(Ctx);255 default:256 break;257 }258 // Type inference not implemented for opcode.259 LLVM_DEBUG({260 dbgs() << "LV: Found unhandled opcode for: ";261 R->getVPSingleValue()->dump();262 });263 llvm_unreachable("Unhandled opcode");264}265 266Type *VPTypeAnalysis::inferScalarType(const VPValue *V) {267 if (Type *CachedTy = CachedTypes.lookup(V))268 return CachedTy;269 270 if (V->isLiveIn()) {271 if (auto *IRValue = V->getLiveInIRValue())272 return IRValue->getType();273 // All VPValues without any underlying IR value (like the vector trip count274 // or the backedge-taken count) have the same type as the canonical IV.275 return CanonicalIVTy;276 }277 278 Type *ResultTy =279 TypeSwitch<const VPRecipeBase *, Type *>(V->getDefiningRecipe())280 .Case<VPActiveLaneMaskPHIRecipe, VPCanonicalIVPHIRecipe,281 VPFirstOrderRecurrencePHIRecipe, VPReductionPHIRecipe,282 VPWidenPointerInductionRecipe, VPEVLBasedIVPHIRecipe>(283 [this](const auto *R) {284 // Handle header phi recipes, except VPWidenIntOrFpInduction285 // which needs special handling due it being possibly truncated.286 // TODO: consider inferring/caching type of siblings, e.g.,287 // backedge value, here and in cases below.288 return inferScalarType(R->getStartValue());289 })290 .Case<VPWidenIntOrFpInductionRecipe, VPDerivedIVRecipe>(291 [](const auto *R) { return R->getScalarType(); })292 .Case<VPReductionRecipe, VPPredInstPHIRecipe, VPWidenPHIRecipe,293 VPScalarIVStepsRecipe, VPWidenGEPRecipe, VPVectorPointerRecipe,294 VPVectorEndPointerRecipe, VPWidenCanonicalIVRecipe>(295 [this](const VPRecipeBase *R) {296 return inferScalarType(R->getOperand(0));297 })298 // VPInstructionWithType must be handled before VPInstruction.299 .Case<VPInstructionWithType, VPWidenIntrinsicRecipe,300 VPWidenCastRecipe>(301 [](const auto *R) { return R->getResultType(); })302 .Case<VPBlendRecipe, VPInstruction, VPWidenRecipe, VPReplicateRecipe,303 VPWidenCallRecipe, VPWidenMemoryRecipe, VPWidenSelectRecipe>(304 [this](const auto *R) { return inferScalarTypeForRecipe(R); })305 .Case<VPInterleaveBase>([V](const auto *R) {306 // TODO: Use info from interleave group.307 return V->getUnderlyingValue()->getType();308 })309 .Case<VPExpandSCEVRecipe>([](const VPExpandSCEVRecipe *R) {310 return R->getSCEV()->getType();311 })312 .Case<VPReductionRecipe>([this](const auto *R) {313 return inferScalarType(R->getChainOp());314 })315 .Case<VPExpressionRecipe>([this](const auto *R) {316 return inferScalarType(R->getOperandOfResultType());317 });318 319 assert(ResultTy && "could not infer type for the given VPValue");320 CachedTypes[V] = ResultTy;321 return ResultTy;322}323 324void llvm::collectEphemeralRecipesForVPlan(325 VPlan &Plan, DenseSet<VPRecipeBase *> &EphRecipes) {326 // First, collect seed recipes which are operands of assumes.327 SmallVector<VPRecipeBase *> Worklist;328 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(329 vp_depth_first_deep(Plan.getVectorLoopRegion()->getEntry()))) {330 for (VPRecipeBase &R : *VPBB) {331 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);332 if (!RepR || !match(RepR, m_Intrinsic<Intrinsic::assume>()))333 continue;334 Worklist.push_back(RepR);335 EphRecipes.insert(RepR);336 }337 }338 339 // Process operands of candidates in worklist and add them to the set of340 // ephemeral recipes, if they don't have side-effects and are only used by341 // other ephemeral recipes.342 while (!Worklist.empty()) {343 VPRecipeBase *Cur = Worklist.pop_back_val();344 for (VPValue *Op : Cur->operands()) {345 auto *OpR = Op->getDefiningRecipe();346 if (!OpR || OpR->mayHaveSideEffects() || EphRecipes.contains(OpR))347 continue;348 if (any_of(Op->users(), [EphRecipes](VPUser *U) {349 auto *UR = dyn_cast<VPRecipeBase>(U);350 return !UR || !EphRecipes.contains(UR);351 }))352 continue;353 EphRecipes.insert(OpR);354 Worklist.push_back(OpR);355 }356 }357}358 359template void DomTreeBuilder::Calculate<DominatorTreeBase<VPBlockBase, false>>(360 DominatorTreeBase<VPBlockBase, false> &DT);361 362bool VPDominatorTree::properlyDominates(const VPRecipeBase *A,363 const VPRecipeBase *B) {364 if (A == B)365 return false;366 367 auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {368 for (auto &R : *A->getParent()) {369 if (&R == A)370 return true;371 if (&R == B)372 return false;373 }374 llvm_unreachable("recipe not found");375 };376 const VPBlockBase *ParentA = A->getParent();377 const VPBlockBase *ParentB = B->getParent();378 if (ParentA == ParentB)379 return LocalComesBefore(A, B);380 381#ifndef NDEBUG382 auto GetReplicateRegion = [](VPRecipeBase *R) -> VPRegionBlock * {383 VPRegionBlock *Region = R->getRegion();384 if (Region && Region->isReplicator()) {385 assert(Region->getNumSuccessors() == 1 &&386 Region->getNumPredecessors() == 1 && "Expected SESE region!");387 assert(R->getParent()->size() == 1 &&388 "A recipe in an original replicator region must be the only "389 "recipe in its block");390 return Region;391 }392 return nullptr;393 };394 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(A)) &&395 "No replicate regions expected at this point");396 assert(!GetReplicateRegion(const_cast<VPRecipeBase *>(B)) &&397 "No replicate regions expected at this point");398#endif399 return Base::properlyDominates(ParentA, ParentB);400}401 402bool VPRegisterUsage::exceedsMaxNumRegs(const TargetTransformInfo &TTI,403 unsigned OverrideMaxNumRegs) const {404 return any_of(MaxLocalUsers, [&TTI, &OverrideMaxNumRegs](auto &LU) {405 return LU.second > (OverrideMaxNumRegs > 0406 ? OverrideMaxNumRegs407 : TTI.getNumberOfRegisters(LU.first));408 });409}410 411SmallVector<VPRegisterUsage, 8> llvm::calculateRegisterUsageForPlan(412 VPlan &Plan, ArrayRef<ElementCount> VFs, const TargetTransformInfo &TTI,413 const SmallPtrSetImpl<const Value *> &ValuesToIgnore) {414 // Each 'key' in the map opens a new interval. The values415 // of the map are the index of the 'last seen' usage of the416 // VPValue that is the key.417 using IntervalMap = SmallDenseMap<VPValue *, unsigned, 16>;418 419 // Maps indices to recipes.420 SmallVector<VPRecipeBase *, 64> Idx2Recipe;421 // Marks the end of each interval.422 IntervalMap EndPoint;423 // Saves the list of VPValues that are used in the loop.424 SmallPtrSet<VPValue *, 8> Ends;425 // Saves the list of values that are used in the loop but are defined outside426 // the loop (not including non-recipe values such as arguments and427 // constants).428 SmallSetVector<VPValue *, 8> LoopInvariants;429 LoopInvariants.insert(&Plan.getVectorTripCount());430 431 // We scan the loop in a topological order in order and assign a number to432 // each recipe. We use RPO to ensure that defs are met before their users. We433 // assume that each recipe that has in-loop users starts an interval. We434 // record every time that an in-loop value is used, so we have a list of the435 // first occurences of each recipe and last occurrence of each VPValue.436 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();437 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> RPOT(438 LoopRegion);439 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {440 if (!VPBB->getParent())441 break;442 for (VPRecipeBase &R : *VPBB) {443 Idx2Recipe.push_back(&R);444 445 // Save the end location of each USE.446 for (VPValue *U : R.operands()) {447 auto *DefR = U->getDefiningRecipe();448 449 // Ignore non-recipe values such as arguments, constants, etc.450 // FIXME: Might need some motivation why these values are ignored. If451 // for example an argument is used inside the loop it will increase the452 // register pressure (so shouldn't we add it to LoopInvariants).453 if (!DefR && (!U->getLiveInIRValue() ||454 !isa<Instruction>(U->getLiveInIRValue())))455 continue;456 457 // If this recipe is outside the loop then record it and continue.458 if (!DefR) {459 LoopInvariants.insert(U);460 continue;461 }462 463 // Overwrite previous end points.464 EndPoint[U] = Idx2Recipe.size();465 Ends.insert(U);466 }467 }468 if (VPBB == LoopRegion->getExiting()) {469 // VPWidenIntOrFpInductionRecipes are used implicitly at the end of the470 // exiting block, where their increment will get materialized eventually.471 for (auto &R : LoopRegion->getEntryBasicBlock()->phis()) {472 if (auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&R)) {473 EndPoint[WideIV] = Idx2Recipe.size();474 Ends.insert(WideIV);475 }476 }477 }478 }479 480 // Saves the list of intervals that end with the index in 'key'.481 using VPValueList = SmallVector<VPValue *, 2>;482 SmallDenseMap<unsigned, VPValueList, 16> TransposeEnds;483 484 // Next, we transpose the EndPoints into a multi map that holds the list of485 // intervals that *end* at a specific location.486 for (auto &Interval : EndPoint)487 TransposeEnds[Interval.second].push_back(Interval.first);488 489 SmallPtrSet<VPValue *, 8> OpenIntervals;490 SmallVector<VPRegisterUsage, 8> RUs(VFs.size());491 SmallVector<SmallMapVector<unsigned, unsigned, 4>, 8> MaxUsages(VFs.size());492 493 LLVM_DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n");494 495 VPTypeAnalysis TypeInfo(Plan);496 497 const auto &TTICapture = TTI;498 auto GetRegUsage = [&TTICapture](Type *Ty, ElementCount VF) -> unsigned {499 if (Ty->isTokenTy() || !VectorType::isValidElementType(Ty) ||500 (VF.isScalable() &&501 !TTICapture.isElementTypeLegalForScalableVector(Ty)))502 return 0;503 return TTICapture.getRegUsageForType(VectorType::get(Ty, VF));504 };505 506 // We scan the instructions linearly and record each time that a new interval507 // starts, by placing it in a set. If we find this value in TransposEnds then508 // we remove it from the set. The max register usage is the maximum register509 // usage of the recipes of the set.510 for (unsigned int Idx = 0, Sz = Idx2Recipe.size(); Idx < Sz; ++Idx) {511 VPRecipeBase *R = Idx2Recipe[Idx];512 513 // Remove all of the VPValues that end at this location.514 VPValueList &List = TransposeEnds[Idx];515 for (VPValue *ToRemove : List)516 OpenIntervals.erase(ToRemove);517 518 // Ignore recipes that are never used within the loop and do not have side519 // effects.520 if (none_of(R->definedValues(),521 [&Ends](VPValue *Def) { return Ends.count(Def); }) &&522 !R->mayHaveSideEffects())523 continue;524 525 // Skip recipes for ignored values.526 // TODO: Should mark recipes for ephemeral values that cannot be removed527 // explictly in VPlan.528 if (isa<VPSingleDefRecipe>(R) &&529 ValuesToIgnore.contains(530 cast<VPSingleDefRecipe>(R)->getUnderlyingValue()))531 continue;532 533 // For each VF find the maximum usage of registers.534 for (unsigned J = 0, E = VFs.size(); J < E; ++J) {535 // Count the number of registers used, per register class, given all open536 // intervals.537 // Note that elements in this SmallMapVector will be default constructed538 // as 0. So we can use "RegUsage[ClassID] += n" in the code below even if539 // there is no previous entry for ClassID.540 SmallMapVector<unsigned, unsigned, 4> RegUsage;541 542 for (auto *VPV : OpenIntervals) {543 // Skip values that weren't present in the original loop.544 // TODO: Remove after removing the legacy545 // LoopVectorizationCostModel::calculateRegisterUsage546 if (isa<VPVectorPointerRecipe, VPVectorEndPointerRecipe,547 VPBranchOnMaskRecipe>(VPV))548 continue;549 550 if (VFs[J].isScalar() ||551 isa<VPCanonicalIVPHIRecipe, VPReplicateRecipe, VPDerivedIVRecipe,552 VPEVLBasedIVPHIRecipe, VPScalarIVStepsRecipe>(VPV) ||553 (isa<VPInstruction>(VPV) && vputils::onlyScalarValuesUsed(VPV)) ||554 (isa<VPReductionPHIRecipe>(VPV) &&555 (cast<VPReductionPHIRecipe>(VPV))->isInLoop())) {556 unsigned ClassID =557 TTI.getRegisterClassForType(false, TypeInfo.inferScalarType(VPV));558 // FIXME: The target might use more than one register for the type559 // even in the scalar case.560 RegUsage[ClassID] += 1;561 } else {562 // The output from scaled phis and scaled reductions actually has563 // fewer lanes than the VF.564 unsigned ScaleFactor =565 vputils::getVFScaleFactor(VPV->getDefiningRecipe());566 ElementCount VF = VFs[J];567 if (ScaleFactor > 1) {568 VF = VFs[J].divideCoefficientBy(ScaleFactor);569 LLVM_DEBUG(dbgs() << "LV(REG): Scaled down VF from " << VFs[J]570 << " to " << VF << " for " << *R << "\n";);571 }572 573 Type *ScalarTy = TypeInfo.inferScalarType(VPV);574 unsigned ClassID = TTI.getRegisterClassForType(true, ScalarTy);575 RegUsage[ClassID] += GetRegUsage(ScalarTy, VF);576 }577 }578 579 for (const auto &Pair : RegUsage) {580 auto &Entry = MaxUsages[J][Pair.first];581 Entry = std::max(Entry, Pair.second);582 }583 }584 585 LLVM_DEBUG(dbgs() << "LV(REG): At #" << Idx << " Interval # "586 << OpenIntervals.size() << '\n');587 588 // Add used VPValues defined by the current recipe to the list of open589 // intervals.590 for (VPValue *DefV : R->definedValues())591 if (Ends.contains(DefV))592 OpenIntervals.insert(DefV);593 }594 595 // We also search for instructions that are defined outside the loop, but are596 // used inside the loop. We need this number separately from the max-interval597 // usage number because when we unroll, loop-invariant values do not take598 // more register.599 VPRegisterUsage RU;600 for (unsigned Idx = 0, End = VFs.size(); Idx < End; ++Idx) {601 // Note that elements in this SmallMapVector will be default constructed602 // as 0. So we can use "Invariant[ClassID] += n" in the code below even if603 // there is no previous entry for ClassID.604 SmallMapVector<unsigned, unsigned, 4> Invariant;605 606 for (auto *In : LoopInvariants) {607 // FIXME: The target might use more than one register for the type608 // even in the scalar case.609 bool IsScalar = vputils::onlyScalarValuesUsed(In);610 611 ElementCount VF = IsScalar ? ElementCount::getFixed(1) : VFs[Idx];612 unsigned ClassID = TTI.getRegisterClassForType(613 VF.isVector(), TypeInfo.inferScalarType(In));614 Invariant[ClassID] += GetRegUsage(TypeInfo.inferScalarType(In), VF);615 }616 617 LLVM_DEBUG({618 dbgs() << "LV(REG): VF = " << VFs[Idx] << '\n';619 dbgs() << "LV(REG): Found max usage: " << MaxUsages[Idx].size()620 << " item\n";621 for (const auto &pair : MaxUsages[Idx]) {622 dbgs() << "LV(REG): RegisterClass: "623 << TTI.getRegisterClassName(pair.first) << ", " << pair.second624 << " registers\n";625 }626 dbgs() << "LV(REG): Found invariant usage: " << Invariant.size()627 << " item\n";628 for (const auto &pair : Invariant) {629 dbgs() << "LV(REG): RegisterClass: "630 << TTI.getRegisterClassName(pair.first) << ", " << pair.second631 << " registers\n";632 }633 });634 635 RU.LoopInvariantRegs = Invariant;636 RU.MaxLocalUsers = MaxUsages[Idx];637 RUs[Idx] = RU;638 }639 640 return RUs;641}642