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-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "VPlanUtils.h"
10 #include "VPlanCFG.h"
11 #include "VPlanPatternMatch.h"
12 #include "llvm/ADT/TypeSwitch.h"
13 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
14
15 using namespace llvm;
16
onlyFirstLaneUsed(const VPValue * Def)17 bool vputils::onlyFirstLaneUsed(const VPValue *Def) {
18 return all_of(Def->users(),
19 [Def](const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
20 }
21
onlyFirstPartUsed(const VPValue * Def)22 bool vputils::onlyFirstPartUsed(const VPValue *Def) {
23 return all_of(Def->users(),
24 [Def](const VPUser *U) { return U->onlyFirstPartUsed(Def); });
25 }
26
getOrCreateVPValueForSCEVExpr(VPlan & Plan,const SCEV * Expr,ScalarEvolution & SE)27 VPValue *vputils::getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr,
28 ScalarEvolution &SE) {
29 if (auto *Expanded = Plan.getSCEVExpansion(Expr))
30 return Expanded;
31 VPValue *Expanded = nullptr;
32 if (auto *E = dyn_cast<SCEVConstant>(Expr))
33 Expanded = Plan.getOrAddLiveIn(E->getValue());
34 else {
35 auto *U = dyn_cast<SCEVUnknown>(Expr);
36 // Skip SCEV expansion if Expr is a SCEVUnknown wrapping a non-instruction
37 // value. Otherwise the value may be defined in a loop and using it directly
38 // will break LCSSA form. The SCEV expansion takes care of preserving LCSSA
39 // form.
40 if (U && !isa<Instruction>(U->getValue())) {
41 Expanded = Plan.getOrAddLiveIn(U->getValue());
42 } else {
43 Expanded = new VPExpandSCEVRecipe(Expr, SE);
44 Plan.getEntry()->appendRecipe(Expanded->getDefiningRecipe());
45 }
46 }
47 Plan.addSCEVExpansion(Expr, Expanded);
48 return Expanded;
49 }
50
isHeaderMask(const VPValue * V,VPlan & Plan)51 bool vputils::isHeaderMask(const VPValue *V, VPlan &Plan) {
52 if (isa<VPActiveLaneMaskPHIRecipe>(V))
53 return true;
54
55 auto IsWideCanonicalIV = [](VPValue *A) {
56 return isa<VPWidenCanonicalIVRecipe>(A) ||
57 (isa<VPWidenIntOrFpInductionRecipe>(A) &&
58 cast<VPWidenIntOrFpInductionRecipe>(A)->isCanonical());
59 };
60
61 VPValue *A, *B;
62 using namespace VPlanPatternMatch;
63
64 if (match(V, m_ActiveLaneMask(m_VPValue(A), m_VPValue(B))))
65 return B == Plan.getTripCount() &&
66 (match(A, m_ScalarIVSteps(m_Specific(Plan.getCanonicalIV()),
67 m_SpecificInt(1),
68 m_Specific(&Plan.getVF()))) ||
69 IsWideCanonicalIV(A));
70
71 return match(V, m_Binary<Instruction::ICmp>(m_VPValue(A), m_VPValue(B))) &&
72 IsWideCanonicalIV(A) && B == Plan.getOrCreateBackedgeTakenCount();
73 }
74
getSCEVExprForVPValue(VPValue * V,ScalarEvolution & SE)75 const SCEV *vputils::getSCEVExprForVPValue(VPValue *V, ScalarEvolution &SE) {
76 if (V->isLiveIn())
77 return SE.getSCEV(V->getLiveInIRValue());
78
79 // TODO: Support constructing SCEVs for more recipes as needed.
80 return TypeSwitch<const VPRecipeBase *, const SCEV *>(V->getDefiningRecipe())
81 .Case<VPExpandSCEVRecipe>(
82 [](const VPExpandSCEVRecipe *R) { return R->getSCEV(); })
83 .Default([&SE](const VPRecipeBase *) { return SE.getCouldNotCompute(); });
84 }
85
isUniformAcrossVFsAndUFs(VPValue * V)86 bool vputils::isUniformAcrossVFsAndUFs(VPValue *V) {
87 using namespace VPlanPatternMatch;
88 // Live-ins are uniform.
89 if (V->isLiveIn())
90 return true;
91
92 VPRecipeBase *R = V->getDefiningRecipe();
93 if (R && V->isDefinedOutsideLoopRegions()) {
94 if (match(V->getDefiningRecipe(),
95 m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>(
96 m_VPValue())))
97 return false;
98 return all_of(R->operands(), isUniformAcrossVFsAndUFs);
99 }
100
101 auto *CanonicalIV = R->getParent()->getPlan()->getCanonicalIV();
102 // Canonical IV chain is uniform.
103 if (V == CanonicalIV || V == CanonicalIV->getBackedgeValue())
104 return true;
105
106 return TypeSwitch<const VPRecipeBase *, bool>(R)
107 .Case<VPDerivedIVRecipe>([](const auto *R) { return true; })
108 .Case<VPReplicateRecipe>([](const auto *R) {
109 // Loads and stores that are uniform across VF lanes are handled by
110 // VPReplicateRecipe.IsUniform. They are also uniform across UF parts if
111 // all their operands are invariant.
112 // TODO: Further relax the restrictions.
113 return R->isSingleScalar() &&
114 (isa<LoadInst, StoreInst>(R->getUnderlyingValue())) &&
115 all_of(R->operands(), isUniformAcrossVFsAndUFs);
116 })
117 .Case<VPInstruction>([](const auto *VPI) {
118 return VPI->isScalarCast() &&
119 isUniformAcrossVFsAndUFs(VPI->getOperand(0));
120 })
121 .Case<VPWidenCastRecipe>([](const auto *R) {
122 // A cast is uniform according to its operand.
123 return isUniformAcrossVFsAndUFs(R->getOperand(0));
124 })
125 .Default([](const VPRecipeBase *) { // A value is considered non-uniform
126 // unless proven otherwise.
127 return false;
128 });
129 }
130
getFirstLoopHeader(VPlan & Plan,VPDominatorTree & VPDT)131 VPBasicBlock *vputils::getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT) {
132 auto DepthFirst = vp_depth_first_shallow(Plan.getEntry());
133 auto I = find_if(DepthFirst, [&VPDT](VPBlockBase *VPB) {
134 return VPBlockUtils::isHeader(VPB, VPDT);
135 });
136 return I == DepthFirst.end() ? nullptr : cast<VPBasicBlock>(*I);
137 }
138