420 lines · cpp
1//===- VPlanUtils.cpp - VPlan-related utilities ---------------------------===//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 "VPlanUtils.h"10#include "VPlanCFG.h"11#include "VPlanDominatorTree.h"12#include "VPlanPatternMatch.h"13#include "llvm/ADT/TypeSwitch.h"14#include "llvm/Analysis/MemoryLocation.h"15#include "llvm/Analysis/ScalarEvolutionExpressions.h"16 17using namespace llvm;18using namespace llvm::VPlanPatternMatch;19 20bool vputils::onlyFirstLaneUsed(const VPValue *Def) {21 return all_of(Def->users(),22 [Def](const VPUser *U) { return U->usesFirstLaneOnly(Def); });23}24 25bool vputils::onlyFirstPartUsed(const VPValue *Def) {26 return all_of(Def->users(),27 [Def](const VPUser *U) { return U->usesFirstPartOnly(Def); });28}29 30bool vputils::onlyScalarValuesUsed(const VPValue *Def) {31 return all_of(Def->users(),32 [Def](const VPUser *U) { return U->usesScalars(Def); });33}34 35VPValue *vputils::getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr) {36 if (auto *E = dyn_cast<SCEVConstant>(Expr))37 return Plan.getOrAddLiveIn(E->getValue());38 // Skip SCEV expansion if Expr is a SCEVUnknown wrapping a non-instruction39 // value. Otherwise the value may be defined in a loop and using it directly40 // will break LCSSA form. The SCEV expansion takes care of preserving LCSSA41 // form.42 auto *U = dyn_cast<SCEVUnknown>(Expr);43 if (U && !isa<Instruction>(U->getValue()))44 return Plan.getOrAddLiveIn(U->getValue());45 auto *Expanded = new VPExpandSCEVRecipe(Expr);46 Plan.getEntry()->appendRecipe(Expanded);47 return Expanded;48}49 50bool vputils::isHeaderMask(const VPValue *V, const VPlan &Plan) {51 if (isa<VPActiveLaneMaskPHIRecipe>(V))52 return true;53 54 auto IsWideCanonicalIV = [](VPValue *A) {55 return isa<VPWidenCanonicalIVRecipe>(A) ||56 (isa<VPWidenIntOrFpInductionRecipe>(A) &&57 cast<VPWidenIntOrFpInductionRecipe>(A)->isCanonical());58 };59 60 VPValue *A, *B;61 62 auto m_CanonicalScalarIVSteps =63 m_ScalarIVSteps(m_Specific(Plan.getVectorLoopRegion()->getCanonicalIV()),64 m_One(), m_Specific(&Plan.getVF()));65 66 if (match(V, m_ActiveLaneMask(m_VPValue(A), m_VPValue(B), m_One())))67 return B == Plan.getTripCount() &&68 (match(A, m_CanonicalScalarIVSteps) || IsWideCanonicalIV(A));69 70 // For scalar plans, the header mask uses the scalar steps.71 if (match(V, m_ICmp(m_CanonicalScalarIVSteps,72 m_Specific(Plan.getBackedgeTakenCount())))) {73 assert(Plan.hasScalarVFOnly() &&74 "Non-scalar VF using scalar IV steps for header mask?");75 return true;76 }77 78 return match(V, m_ICmp(m_VPValue(A), m_VPValue(B))) && IsWideCanonicalIV(A) &&79 B == Plan.getBackedgeTakenCount();80}81 82const SCEV *vputils::getSCEVExprForVPValue(const VPValue *V,83 ScalarEvolution &SE, const Loop *L) {84 if (V->isLiveIn()) {85 if (Value *LiveIn = V->getLiveInIRValue())86 return SE.getSCEV(LiveIn);87 return SE.getCouldNotCompute();88 }89 90 // TODO: Support constructing SCEVs for more recipes as needed.91 return TypeSwitch<const VPRecipeBase *, const SCEV *>(V->getDefiningRecipe())92 .Case<VPExpandSCEVRecipe>(93 [](const VPExpandSCEVRecipe *R) { return R->getSCEV(); })94 .Case<VPCanonicalIVPHIRecipe>([&SE, L](const VPCanonicalIVPHIRecipe *R) {95 if (!L)96 return SE.getCouldNotCompute();97 const SCEV *Start = getSCEVExprForVPValue(R->getOperand(0), SE, L);98 return SE.getAddRecExpr(Start, SE.getOne(Start->getType()), L,99 SCEV::FlagAnyWrap);100 })101 .Case<VPWidenIntOrFpInductionRecipe>(102 [&SE, L](const VPWidenIntOrFpInductionRecipe *R) {103 const SCEV *Step = getSCEVExprForVPValue(R->getStepValue(), SE, L);104 if (!L || isa<SCEVCouldNotCompute>(Step))105 return SE.getCouldNotCompute();106 const SCEV *Start =107 getSCEVExprForVPValue(R->getStartValue(), SE, L);108 return SE.getAddRecExpr(Start, Step, L, SCEV::FlagAnyWrap);109 })110 .Case<VPDerivedIVRecipe>([&SE, L](const VPDerivedIVRecipe *R) {111 const SCEV *Start = getSCEVExprForVPValue(R->getOperand(0), SE, L);112 const SCEV *IV = getSCEVExprForVPValue(R->getOperand(1), SE, L);113 const SCEV *Scale = getSCEVExprForVPValue(R->getOperand(2), SE, L);114 if (any_of(ArrayRef({Start, IV, Scale}), IsaPred<SCEVCouldNotCompute>))115 return SE.getCouldNotCompute();116 117 return SE.getAddExpr(SE.getTruncateOrSignExtend(Start, IV->getType()),118 SE.getMulExpr(IV, SE.getTruncateOrSignExtend(119 Scale, IV->getType())));120 })121 .Case<VPScalarIVStepsRecipe>([&SE, L](const VPScalarIVStepsRecipe *R) {122 const SCEV *IV = getSCEVExprForVPValue(R->getOperand(0), SE, L);123 const SCEV *Step = getSCEVExprForVPValue(R->getOperand(1), SE, L);124 if (isa<SCEVCouldNotCompute>(IV) || isa<SCEVCouldNotCompute>(Step) ||125 !Step->isOne())126 return SE.getCouldNotCompute();127 return SE.getMulExpr(SE.getTruncateOrSignExtend(IV, Step->getType()),128 Step);129 })130 .Case<VPReplicateRecipe>([&SE, L](const VPReplicateRecipe *R) {131 if (R->getOpcode() != Instruction::GetElementPtr)132 return SE.getCouldNotCompute();133 134 const SCEV *Base = getSCEVExprForVPValue(R->getOperand(0), SE, L);135 if (isa<SCEVCouldNotCompute>(Base))136 return SE.getCouldNotCompute();137 138 SmallVector<const SCEV *> IndexExprs;139 for (VPValue *Index : drop_begin(R->operands())) {140 const SCEV *IndexExpr = getSCEVExprForVPValue(Index, SE, L);141 if (isa<SCEVCouldNotCompute>(IndexExpr))142 return SE.getCouldNotCompute();143 IndexExprs.push_back(IndexExpr);144 }145 146 Type *SrcElementTy = cast<GetElementPtrInst>(R->getUnderlyingInstr())147 ->getSourceElementType();148 return SE.getGEPExpr(Base, IndexExprs, SrcElementTy);149 })150 .Default([&SE](const VPRecipeBase *) { return SE.getCouldNotCompute(); });151}152 153/// Returns true if \p Opcode preserves uniformity, i.e., if all operands are154/// uniform, the result will also be uniform.155static bool preservesUniformity(unsigned Opcode) {156 if (Instruction::isBinaryOp(Opcode) || Instruction::isCast(Opcode))157 return true;158 switch (Opcode) {159 case Instruction::GetElementPtr:160 case Instruction::ICmp:161 case Instruction::FCmp:162 case Instruction::Select:163 case VPInstruction::Not:164 case VPInstruction::Broadcast:165 case VPInstruction::PtrAdd:166 return true;167 default:168 return false;169 }170}171 172bool vputils::isSingleScalar(const VPValue *VPV) {173 // A live-in must be uniform across the scope of VPlan.174 if (VPV->isLiveIn())175 return true;176 177 if (auto *Rep = dyn_cast<VPReplicateRecipe>(VPV)) {178 const VPRegionBlock *RegionOfR = Rep->getRegion();179 // Don't consider recipes in replicate regions as uniform yet; their first180 // lane cannot be accessed when executing the replicate region for other181 // lanes.182 if (RegionOfR && RegionOfR->isReplicator())183 return false;184 return Rep->isSingleScalar() || (preservesUniformity(Rep->getOpcode()) &&185 all_of(Rep->operands(), isSingleScalar));186 }187 if (isa<VPWidenGEPRecipe, VPDerivedIVRecipe, VPBlendRecipe,188 VPWidenSelectRecipe>(VPV))189 return all_of(VPV->getDefiningRecipe()->operands(), isSingleScalar);190 if (auto *WidenR = dyn_cast<VPWidenRecipe>(VPV)) {191 return preservesUniformity(WidenR->getOpcode()) &&192 all_of(WidenR->operands(), isSingleScalar);193 }194 if (auto *VPI = dyn_cast<VPInstruction>(VPV))195 return VPI->isSingleScalar() || VPI->isVectorToScalar() ||196 (preservesUniformity(VPI->getOpcode()) &&197 all_of(VPI->operands(), isSingleScalar));198 if (auto *RR = dyn_cast<VPReductionRecipe>(VPV))199 return !RR->isPartialReduction();200 if (isa<VPCanonicalIVPHIRecipe, VPVectorPointerRecipe,201 VPVectorEndPointerRecipe>(VPV))202 return true;203 if (auto *Expr = dyn_cast<VPExpressionRecipe>(VPV))204 return Expr->isSingleScalar();205 206 // VPExpandSCEVRecipes must be placed in the entry and are always uniform.207 return isa<VPExpandSCEVRecipe>(VPV);208}209 210bool vputils::isUniformAcrossVFsAndUFs(VPValue *V) {211 // Live-ins are uniform.212 if (V->isLiveIn())213 return true;214 215 VPRecipeBase *R = V->getDefiningRecipe();216 if (R && V->isDefinedOutsideLoopRegions()) {217 if (match(V->getDefiningRecipe(),218 m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>()))219 return false;220 return all_of(R->operands(), isUniformAcrossVFsAndUFs);221 }222 223 auto *CanonicalIV =224 R->getParent()->getEnclosingLoopRegion()->getCanonicalIV();225 // Canonical IV chain is uniform.226 if (V == CanonicalIV || V == CanonicalIV->getBackedgeValue())227 return true;228 229 return TypeSwitch<const VPRecipeBase *, bool>(R)230 .Case<VPDerivedIVRecipe>([](const auto *R) { return true; })231 .Case<VPReplicateRecipe>([](const auto *R) {232 // Be conservative about side-effects, except for the233 // known-side-effecting assumes and stores, which we know will be234 // uniform.235 return R->isSingleScalar() &&236 (!R->mayHaveSideEffects() ||237 isa<AssumeInst, StoreInst>(R->getUnderlyingInstr())) &&238 all_of(R->operands(), isUniformAcrossVFsAndUFs);239 })240 .Case<VPWidenRecipe>([](const auto *R) {241 return preservesUniformity(R->getOpcode()) &&242 all_of(R->operands(), isUniformAcrossVFsAndUFs);243 })244 .Case<VPInstruction>([](const auto *VPI) {245 return (VPI->isScalarCast() &&246 isUniformAcrossVFsAndUFs(VPI->getOperand(0))) ||247 (preservesUniformity(VPI->getOpcode()) &&248 all_of(VPI->operands(), isUniformAcrossVFsAndUFs));249 })250 .Case<VPWidenCastRecipe>([](const auto *R) {251 // A cast is uniform according to its operand.252 return isUniformAcrossVFsAndUFs(R->getOperand(0));253 })254 .Default([](const VPRecipeBase *) { // A value is considered non-uniform255 // unless proven otherwise.256 return false;257 });258}259 260VPBasicBlock *vputils::getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT) {261 auto DepthFirst = vp_depth_first_shallow(Plan.getEntry());262 auto I = find_if(DepthFirst, [&VPDT](VPBlockBase *VPB) {263 return VPBlockUtils::isHeader(VPB, VPDT);264 });265 return I == DepthFirst.end() ? nullptr : cast<VPBasicBlock>(*I);266}267 268unsigned vputils::getVFScaleFactor(VPRecipeBase *R) {269 if (!R)270 return 1;271 if (auto *RR = dyn_cast<VPReductionPHIRecipe>(R))272 return RR->getVFScaleFactor();273 if (auto *RR = dyn_cast<VPReductionRecipe>(R))274 return RR->getVFScaleFactor();275 if (auto *ER = dyn_cast<VPExpressionRecipe>(R))276 return ER->getVFScaleFactor();277 assert(278 (!isa<VPInstruction>(R) || cast<VPInstruction>(R)->getOpcode() !=279 VPInstruction::ReductionStartVector) &&280 "getting scaling factor of reduction-start-vector not implemented yet");281 return 1;282}283 284std::optional<VPValue *>285vputils::getRecipesForUncountableExit(VPlan &Plan,286 SmallVectorImpl<VPRecipeBase *> &Recipes,287 SmallVectorImpl<VPRecipeBase *> &GEPs) {288 // Given a VPlan like the following (just including the recipes contributing289 // to loop control exiting here, not the actual work), we're looking to match290 // the recipes contributing to the uncountable exit condition comparison291 // (here, vp<%4>) back to either live-ins or the address nodes for the load292 // used as part of the uncountable exit comparison so that we can copy them293 // to a preheader and rotate the address in the loop to the next vector294 // iteration.295 //296 // Currently, the address of the load is restricted to a GEP with 2 operands297 // and a live-in base address. This constraint may be relaxed later.298 //299 // VPlan ' for UF>=1' {300 // Live-in vp<%0> = VF301 // Live-in ir<64> = original trip-count302 //303 // entry:304 // Successor(s): preheader, vector.ph305 //306 // vector.ph:307 // Successor(s): vector loop308 //309 // <x1> vector loop: {310 // vector.body:311 // EMIT vp<%2> = CANONICAL-INDUCTION ir<0>312 // vp<%3> = SCALAR-STEPS vp<%2>, ir<1>, vp<%0>313 // CLONE ir<%ee.addr> = getelementptr ir<0>, vp<%3>314 // WIDEN ir<%ee.load> = load ir<%ee.addr>315 // WIDEN vp<%4> = icmp eq ir<%ee.load>, ir<0>316 // EMIT vp<%5> = any-of vp<%4>317 // EMIT vp<%6> = add vp<%2>, vp<%0>318 // EMIT vp<%7> = icmp eq vp<%6>, ir<64>319 // EMIT vp<%8> = or vp<%5>, vp<%7>320 // EMIT branch-on-cond vp<%8>321 // No successors322 // }323 // Successor(s): middle.block324 //325 // middle.block:326 // Successor(s): preheader327 //328 // preheader:329 // No successors330 // }331 332 // Find the uncountable loop exit condition.333 auto *Region = Plan.getVectorLoopRegion();334 VPValue *UncountableCondition = nullptr;335 if (!match(Region->getExitingBasicBlock()->getTerminator(),336 m_BranchOnCond(m_OneUse(m_c_BinaryOr(337 m_AnyOf(m_VPValue(UncountableCondition)), m_VPValue())))))338 return std::nullopt;339 340 SmallVector<VPValue *, 4> Worklist;341 Worklist.push_back(UncountableCondition);342 while (!Worklist.empty()) {343 VPValue *V = Worklist.pop_back_val();344 345 // Any value defined outside the loop does not need to be copied.346 if (V->isDefinedOutsideLoopRegions())347 continue;348 349 // FIXME: Remove the single user restriction; it's here because we're350 // starting with the simplest set of loops we can, and multiple351 // users means needing to add PHI nodes in the transform.352 if (V->getNumUsers() > 1)353 return std::nullopt;354 355 VPValue *Op1, *Op2;356 // Walk back through recipes until we find at least one load from memory.357 if (match(V, m_ICmp(m_VPValue(Op1), m_VPValue(Op2)))) {358 Worklist.push_back(Op1);359 Worklist.push_back(Op2);360 Recipes.push_back(V->getDefiningRecipe());361 } else if (auto *Load = dyn_cast<VPWidenLoadRecipe>(V)) {362 // Reject masked loads for the time being; they make the exit condition363 // more complex.364 if (Load->isMasked())365 return std::nullopt;366 367 VPValue *GEP = Load->getAddr();368 if (!match(GEP, m_GetElementPtr(m_LiveIn(), m_VPValue())))369 return std::nullopt;370 371 Recipes.push_back(Load);372 Recipes.push_back(GEP->getDefiningRecipe());373 GEPs.push_back(GEP->getDefiningRecipe());374 } else375 return std::nullopt;376 }377 378 return UncountableCondition;379}380 381bool VPBlockUtils::isHeader(const VPBlockBase *VPB,382 const VPDominatorTree &VPDT) {383 auto *VPBB = dyn_cast<VPBasicBlock>(VPB);384 if (!VPBB)385 return false;386 387 // If VPBB is in a region R, VPBB is a loop header if R is a loop region with388 // VPBB as its entry, i.e., free of predecessors.389 if (auto *R = VPBB->getParent())390 return !R->isReplicator() && !VPBB->hasPredecessors();391 392 // A header dominates its second predecessor (the latch), with the other393 // predecessor being the preheader394 return VPB->getPredecessors().size() == 2 &&395 VPDT.dominates(VPB, VPB->getPredecessors()[1]);396}397 398bool VPBlockUtils::isLatch(const VPBlockBase *VPB,399 const VPDominatorTree &VPDT) {400 // A latch has a header as its second successor, with its other successor401 // leaving the loop. A preheader OTOH has a header as its first (and only)402 // successor.403 return VPB->getNumSuccessors() == 2 &&404 VPBlockUtils::isHeader(VPB->getSuccessors()[1], VPDT);405}406 407std::optional<MemoryLocation>408vputils::getMemoryLocation(const VPRecipeBase &R) {409 auto *M = dyn_cast<VPIRMetadata>(&R);410 if (!M)411 return std::nullopt;412 MemoryLocation Loc;413 // Populate noalias metadata from VPIRMetadata.414 if (MDNode *NoAliasMD = M->getMetadata(LLVMContext::MD_noalias))415 Loc.AATags.NoAlias = NoAliasMD;416 if (MDNode *AliasScopeMD = M->getMetadata(LLVMContext::MD_alias_scope))417 Loc.AATags.Scope = AliasScopeMD;418 return Loc;419}420