LLVM 22.0.0git
VPlanUtils.cpp
Go to the documentation of this file.
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"
14
15using namespace llvm;
16
18 return all_of(Def->users(),
19 [Def](const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
20}
21
23 return all_of(Def->users(),
24 [Def](const VPUser *U) { return U->onlyFirstPartUsed(Def); });
25}
26
28 return all_of(Def->users(),
29 [Def](const VPUser *U) { return U->usesScalars(Def); });
30}
31
33 if (auto *Expanded = Plan.getSCEVExpansion(Expr))
34 return Expanded;
35 VPValue *Expanded = nullptr;
36 if (auto *E = dyn_cast<SCEVConstant>(Expr))
37 Expanded = Plan.getOrAddLiveIn(E->getValue());
38 else {
39 auto *U = dyn_cast<SCEVUnknown>(Expr);
40 // Skip SCEV expansion if Expr is a SCEVUnknown wrapping a non-instruction
41 // value. Otherwise the value may be defined in a loop and using it directly
42 // will break LCSSA form. The SCEV expansion takes care of preserving LCSSA
43 // form.
44 if (U && !isa<Instruction>(U->getValue())) {
45 Expanded = Plan.getOrAddLiveIn(U->getValue());
46 } else {
47 Expanded = new VPExpandSCEVRecipe(Expr);
48 Plan.getEntry()->appendRecipe(Expanded->getDefiningRecipe());
49 }
50 }
51 Plan.addSCEVExpansion(Expr, Expanded);
52 return Expanded;
53}
54
55bool vputils::isHeaderMask(const VPValue *V, VPlan &Plan) {
57 return true;
58
59 auto IsWideCanonicalIV = [](VPValue *A) {
63 };
64
65 VPValue *A, *B;
66 using namespace VPlanPatternMatch;
67
68 if (match(V, m_ActiveLaneMask(m_VPValue(A), m_VPValue(B), m_One())))
69 return B == Plan.getTripCount() &&
70 (match(A, m_ScalarIVSteps(m_Specific(Plan.getCanonicalIV()), m_One(),
71 m_Specific(&Plan.getVF()))) ||
72 IsWideCanonicalIV(A));
73
74 return match(V, m_Binary<Instruction::ICmp>(m_VPValue(A), m_VPValue(B))) &&
75 IsWideCanonicalIV(A) && B == Plan.getOrCreateBackedgeTakenCount();
76}
77
79 if (V->isLiveIn()) {
80 if (Value *LiveIn = V->getLiveInIRValue())
81 return SE.getSCEV(LiveIn);
82 return SE.getCouldNotCompute();
83 }
84
85 // TODO: Support constructing SCEVs for more recipes as needed.
86 return TypeSwitch<const VPRecipeBase *, const SCEV *>(V->getDefiningRecipe())
88 [](const VPExpandSCEVRecipe *R) { return R->getSCEV(); })
89 .Default([&SE](const VPRecipeBase *) { return SE.getCouldNotCompute(); });
90}
91
93 using namespace VPlanPatternMatch;
94 // Live-ins are uniform.
95 if (V->isLiveIn())
96 return true;
97
98 VPRecipeBase *R = V->getDefiningRecipe();
99 if (R && V->isDefinedOutsideLoopRegions()) {
100 if (match(V->getDefiningRecipe(),
101 m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>()))
102 return false;
103 return all_of(R->operands(), isUniformAcrossVFsAndUFs);
104 }
105
106 auto *CanonicalIV = R->getParent()->getPlan()->getCanonicalIV();
107 // Canonical IV chain is uniform.
108 if (V == CanonicalIV || V == CanonicalIV->getBackedgeValue())
109 return true;
110
112 .Case<VPDerivedIVRecipe>([](const auto *R) { return true; })
113 .Case<VPReplicateRecipe>([](const auto *R) {
114 // Loads and stores that are uniform across VF lanes are handled by
115 // VPReplicateRecipe.IsUniform. They are also uniform across UF parts if
116 // all their operands are invariant.
117 // TODO: Further relax the restrictions.
118 return R->isSingleScalar() &&
119 (isa<LoadInst, StoreInst>(R->getUnderlyingValue())) &&
120 all_of(R->operands(), isUniformAcrossVFsAndUFs);
121 })
122 .Case<VPInstruction>([](const auto *VPI) {
123 return VPI->isScalarCast() &&
124 isUniformAcrossVFsAndUFs(VPI->getOperand(0));
125 })
126 .Case<VPWidenCastRecipe>([](const auto *R) {
127 // A cast is uniform according to its operand.
128 return isUniformAcrossVFsAndUFs(R->getOperand(0));
129 })
130 .Default([](const VPRecipeBase *) { // A value is considered non-uniform
131 // unless proven otherwise.
132 return false;
133 });
134}
135
137 auto DepthFirst = vp_depth_first_shallow(Plan.getEntry());
138 auto I = find_if(DepthFirst, [&VPDT](VPBlockBase *VPB) {
139 return VPBlockUtils::isHeader(VPB, VPDT);
140 });
141 return I == DepthFirst.end() ? nullptr : cast<VPBasicBlock>(*I);
142}
143
144std::optional<VPValue *>
148 using namespace llvm::VPlanPatternMatch;
149 // Given a VPlan like the following (just including the recipes contributing
150 // to loop control exiting here, not the actual work), we're looking to match
151 // the recipes contributing to the uncountable exit condition comparison
152 // (here, vp<%4>) back to either live-ins or the address nodes for the load
153 // used as part of the uncountable exit comparison so that we can copy them
154 // to a preheader and rotate the address in the loop to the next vector
155 // iteration.
156 //
157 // Currently, the address of the load is restricted to a GEP with 2 operands
158 // and a live-in base address. This constraint may be relaxed later.
159 //
160 // VPlan ' for UF>=1' {
161 // Live-in vp<%0> = VF
162 // Live-in ir<64> = original trip-count
163 //
164 // entry:
165 // Successor(s): preheader, vector.ph
166 //
167 // vector.ph:
168 // Successor(s): vector loop
169 //
170 // <x1> vector loop: {
171 // vector.body:
172 // EMIT vp<%2> = CANONICAL-INDUCTION ir<0>
173 // vp<%3> = SCALAR-STEPS vp<%2>, ir<1>, vp<%0>
174 // CLONE ir<%ee.addr> = getelementptr ir<0>, vp<%3>
175 // WIDEN ir<%ee.load> = load ir<%ee.addr>
176 // WIDEN vp<%4> = icmp eq ir<%ee.load>, ir<0>
177 // EMIT vp<%5> = any-of vp<%4>
178 // EMIT vp<%6> = add vp<%2>, vp<%0>
179 // EMIT vp<%7> = icmp eq vp<%6>, ir<64>
180 // EMIT vp<%8> = or vp<%5>, vp<%7>
181 // EMIT branch-on-cond vp<%8>
182 // No successors
183 // }
184 // Successor(s): middle.block
185 //
186 // middle.block:
187 // Successor(s): preheader
188 //
189 // preheader:
190 // No successors
191 // }
192
193 // Find the uncountable loop exit condition.
194 auto *Region = Plan.getVectorLoopRegion();
195 VPValue *UncountableCondition = nullptr;
196 if (!match(Region->getExitingBasicBlock()->getTerminator(),
198 m_AnyOf(m_VPValue(UncountableCondition)), m_VPValue())))))
199 return std::nullopt;
200
202 Worklist.push_back(UncountableCondition);
203 while (!Worklist.empty()) {
204 VPValue *V = Worklist.pop_back_val();
205
206 // Any value defined outside the loop does not need to be copied.
207 if (V->isDefinedOutsideLoopRegions())
208 continue;
209
210 // FIXME: Remove the single user restriction; it's here because we're
211 // starting with the simplest set of loops we can, and multiple
212 // users means needing to add PHI nodes in the transform.
213 if (V->getNumUsers() > 1)
214 return std::nullopt;
215
216 VPValue *Op1, *Op2;
217 // Walk back through recipes until we find at least one load from memory.
218 if (match(V, m_ICmp(m_VPValue(Op1), m_VPValue(Op2)))) {
219 Worklist.push_back(Op1);
220 Worklist.push_back(Op2);
221 Recipes.push_back(V->getDefiningRecipe());
222 } else if (auto *Load = dyn_cast<VPWidenLoadRecipe>(V)) {
223 // Reject masked loads for the time being; they make the exit condition
224 // more complex.
225 if (Load->isMasked())
226 return std::nullopt;
227
228 VPValue *GEP = Load->getAddr();
230 return std::nullopt;
231
232 Recipes.push_back(Load);
233 Recipes.push_back(GEP->getDefiningRecipe());
234 GEPs.push_back(GEP->getDefiningRecipe());
235 } else
236 return std::nullopt;
237 }
238
239 return UncountableCondition;
240}
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Hexagon Common GEP
#define I(x, y, z)
Definition MD5.cpp:58
This file implements the TypeSwitch template, which mimics a switch() statement whose cases are type ...
This class represents an analyzed expression in the program.
The main scalar evolution driver.
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getCouldNotCompute()
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This class implements a switch-like dispatch statement for a value of 'T' using dyn_cast functionalit...
Definition TypeSwitch.h:87
TypeSwitch< T, ResultT > & Case(CallableT &&caseFn)
Add a case on the given type.
Definition TypeSwitch.h:96
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition VPlan.h:3755
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition VPlan.h:3830
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition VPlan.h:81
static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT)
Returns true if VPB is a loop header, based on regions or VPDT in their absence.
Definition VPlan.cpp:220
A recipe for converting the input value IV value to the corresponding value of an IV with different s...
Definition VPlan.h:3576
Template specialization of the standard LLVM dominator tree utility for VPBlockBases.
Recipe to expand a SCEV expression.
Definition VPlan.h:3374
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition VPlan.h:394
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition VPlanValue.h:199
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition VPlan.cpp:135
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition VPlan.h:4046
VPBasicBlock * getEntry()
Definition VPlan.h:4145
VPValue & getVF()
Returns the VF of the vector loop region.
Definition VPlan.h:4238
VPValue * getTripCount() const
The trip count of the original loop.
Definition VPlan.h:4207
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition VPlan.h:4228
void addSCEVExpansion(const SCEV *S, VPValue *V)
Definition VPlan.h:4364
LLVM_ABI_FOR_TEST VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition VPlan.cpp:1046
VPValue * getOrAddLiveIn(Value *V)
Gets the live-in VPValue for V or adds a new live-in (if none exists yet) for V.
Definition VPlan.h:4297
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
Definition VPlan.h:4351
VPValue * getSCEVExpansion(const SCEV *S) const
Definition VPlan.h:4360
LLVM Value Representation.
Definition Value.h:75
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
AllRecipe_commutative_match< Instruction::Or, Op0_t, Op1_t > m_c_BinaryOr(const Op0_t &Op0, const Op1_t &Op1)
VPInstruction_match< VPInstruction::AnyOf, Op0_t > m_AnyOf(const Op0_t &Op0)
GEPLikeRecipe_match< Op0_t, Op1_t > m_GetElementPtr(const Op0_t &Op0, const Op1_t &Op1)
class_match< VPValue > m_VPValue()
Match an arbitrary VPValue and ignore it.
VPInstruction_match< VPInstruction::BranchOnCond, Op0_t > m_BranchOnCond(const Op0_t &Op0)
bool isUniformAcrossVFsAndUFs(VPValue *V)
Checks if V is uniform across all VF lanes and UF parts.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr)
Get or create a VPValue that corresponds to the expansion of Expr.
VPBasicBlock * getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT)
Returns the header block of the first, top-level loop, or null if none exist.
bool onlyFirstPartUsed(const VPValue *Def)
Returns true if only the first part of Def is used.
const SCEV * getSCEVExprForVPValue(VPValue *V, ScalarEvolution &SE)
Return the SCEV expression for V.
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used.
bool isHeaderMask(const VPValue *V, VPlan &Plan)
Return true if V is a header mask in Plan.
bool onlyScalarValuesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users.
std::optional< VPValue * > getRecipesForUncountableExit(VPlan &Plan, SmallVectorImpl< VPRecipeBase * > &Recipes, SmallVectorImpl< VPRecipeBase * > &GEPs)
Returns the VPValue representing the uncountable exit comparison used by AnyOf if the recipes it depe...
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1705
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:649
iterator_range< df_iterator< VPBlockShallowTraversalWrapper< VPBlockBase * > > > vp_depth_first_shallow(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order.
Definition VPlanCFG.h:216
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:548
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:565
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1738
@ Default
The result values are uniform if and only if all operands are uniform.
Definition Uniformity.h:20