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 "LoopVectorizationPlanner.h"
11#include "VPlanAnalysis.h"
12#include "VPlanCFG.h"
13#include "VPlanDominatorTree.h"
14#include "VPlanPatternMatch.h"
15#include "llvm/ADT/MapVector.h"
16#include "llvm/ADT/SetVector.h"
17#include "llvm/ADT/SmallVectorExtras.h"
18#include "llvm/ADT/TypeSwitch.h"
19#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
20#include "llvm/Analysis/BranchProbabilityInfo.h"
21#include "llvm/Analysis/InstSimplifyFolder.h"
22#include "llvm/Analysis/LoopAccessAnalysis.h"
23#include "llvm/Analysis/LoopInfo.h"
24#include "llvm/Analysis/MemoryLocation.h"
25#include "llvm/Analysis/ScalarEvolutionExpressions.h"
26#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/ProfDataUtils.h"
29#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
30
31using namespace llvm;
32using namespace llvm::VPlanPatternMatch;
33using namespace llvm::SCEVPatternMatch;
34
35bool vputils::onlyFirstLaneUsed(const VPValue *Def) {
36 return all_of(Range: Def->users(),
37 P: [Def](const VPUser *U) { return U->usesFirstLaneOnly(Op: Def); });
38}
39
40bool vputils::onlyFirstPartUsed(const VPValue *Def) {
41 return all_of(Range: Def->users(),
42 P: [Def](const VPUser *U) { return U->usesFirstPartOnly(Op: Def); });
43}
44
45bool vputils::onlyScalarValuesUsed(const VPValue *Def) {
46 return all_of(Range: Def->users(),
47 P: [Def](const VPUser *U) { return U->usesScalars(Op: Def); });
48}
49
50VPValue *vputils::getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr) {
51 if (auto *E = dyn_cast<SCEVConstant>(Val: Expr))
52 return Plan.getOrAddLiveIn(V: E->getValue());
53 // Skip SCEV expansion if Expr is a SCEVUnknown wrapping a non-instruction
54 // value. Otherwise the value may be defined in a loop and using it directly
55 // will break LCSSA form. The SCEV expansion takes care of preserving LCSSA
56 // form.
57 auto *U = dyn_cast<SCEVUnknown>(Val: Expr);
58 if (U && !isa<Instruction>(Val: U->getValue()))
59 return Plan.getOrAddLiveIn(V: U->getValue());
60 auto *Expanded = new VPExpandSCEVRecipe(Expr);
61 VPBasicBlock *EntryVPBB = Plan.getEntry();
62 auto Iter = EntryVPBB->getFirstNonPhi();
63 while (Iter != EntryVPBB->end() && isa<VPIRInstruction>(Val: *Iter))
64 ++Iter;
65 EntryVPBB->insert(Recipe: Expanded, InsertPt: Iter);
66 return Expanded;
67}
68
69/// Returns true if \p V being poison is guaranteed to trigger UB because it
70/// propagates to the address of a memory recipe.
71static bool poisonGuaranteesUB(const VPValue *V) {
72 SmallPtrSet<const VPValue *, 8> Visited;
73 SmallVector<const VPValue *, 16> Worklist;
74
75 auto PropagatesPoisonFromRecipeOp = [](const VPRecipeBase *R) {
76 if (!isa<VPSingleDefRecipe>(Val: R))
77 return false;
78 unsigned Opcode = vputils::getOpcode(V: R->getVPSingleValue());
79 return Instruction::isCast(Opcode) || Opcode == Instruction::GetElementPtr;
80 };
81
82 Worklist.push_back(Elt: V);
83
84 while (!Worklist.empty()) {
85 const VPValue *Current = Worklist.pop_back_val();
86 if (!Visited.insert(Ptr: Current).second)
87 continue;
88
89 for (VPUser *U : Current->users()) {
90 // Check if Current is used as an address operand for load/store.
91 auto *R = cast<VPRecipeBase>(Val: U);
92 if (auto *MemR = dyn_cast<VPWidenMemoryRecipe>(Val: R)) {
93 if (MemR->getAddr() == Current)
94 return true;
95 continue;
96 }
97 if (auto *Rep = dyn_cast<VPReplicateRecipe>(Val: U)) {
98 unsigned Opcode = Rep->getOpcode();
99 if ((Opcode == Instruction::Load && Rep->getOperand(N: 0) == Current) ||
100 (Opcode == Instruction::Store && Rep->getOperand(N: 1) == Current))
101 return true;
102 }
103
104 // Check if poison propagates through this recipe to any of its users.
105 for (const VPValue *Op : R->operands()) {
106 if (Op == Current && PropagatesPoisonFromRecipeOp(R)) {
107 Worklist.push_back(Elt: R->getVPSingleValue());
108 break;
109 }
110 }
111 }
112 }
113
114 return false;
115}
116
117GEPNoWrapFlags vputils::getGEPFlagsForPtr(VPValue *Ptr) {
118 // Like IR stripPointerCasts, look through GEPs with all-zero indices and
119 // casts to find a root GEP VPInstruction.
120 while (auto *PtrVPI = dyn_cast<VPInstruction>(Val: Ptr)) {
121 unsigned Opcode = PtrVPI->getOpcode();
122 if (Opcode == Instruction::GetElementPtr) {
123 if (!all_of(Range: drop_begin(RangeOrContainer: PtrVPI->operands()), P: match_fn(P: m_ZeroInt())))
124 return PtrVPI->getGEPNoWrapFlags();
125 Ptr = PtrVPI->getOperand(N: 0);
126 continue;
127 }
128 if (Opcode != Instruction::BitCast && Opcode != Instruction::AddrSpaceCast)
129 break;
130 Ptr = PtrVPI->getOperand(N: 0);
131 }
132 return GEPNoWrapFlags::none();
133}
134
135const SCEV *vputils::getSCEVExprForVPValue(const VPValue *V,
136 PredicatedScalarEvolution &PSE,
137 const Loop *L) {
138 ScalarEvolution &SE = *PSE.getSE();
139 if (auto *RV = dyn_cast<VPRegionValue>(Val: V)) {
140 assert(RV == RV->getDefiningRegion()->getCanonicalIV() &&
141 "RegionValue must be canonical IV");
142 if (!L)
143 return SE.getCouldNotCompute();
144 return SE.getAddRecExpr(Start: SE.getZero(Ty: RV->getType()), Step: SE.getOne(Ty: RV->getType()),
145 L, Flags: SCEV::FlagNone);
146 }
147
148 if (isa<VPIRValue, VPSymbolicValue>(Val: V)) {
149 Value *LiveIn = V->getUnderlyingValue();
150 if (LiveIn && SE.isSCEVable(Ty: LiveIn->getType()))
151 return SE.getSCEV(V: LiveIn);
152 return SE.getCouldNotCompute();
153 }
154
155 // Helper to create SCEVs for binary and unary operations.
156 auto CreateSCEV = [&](ArrayRef<VPValue *> Ops,
157 function_ref<const SCEV *(ArrayRef<SCEVUse>)> CreateFn)
158 -> const SCEV * {
159 SmallVector<SCEVUse, 2> SCEVOps;
160 for (VPValue *Op : Ops) {
161 const SCEV *S = getSCEVExprForVPValue(V: Op, PSE, L);
162 if (isa<SCEVCouldNotCompute>(Val: S))
163 return SE.getCouldNotCompute();
164 SCEVOps.push_back(Elt: S);
165 }
166 return PSE.getPredicatedSCEV(Expr: CreateFn(SCEVOps));
167 };
168
169 VPValue *LHSVal, *RHSVal;
170 if (match(V, P: m_Add(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
171 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
172 return SE.getAddExpr(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagNone, Depth: 0);
173 });
174 if (match(V, P: m_BinaryOr(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
175 if (cast<VPRecipeWithIRFlags>(Val: V->getDefiningRecipe())->isDisjoint())
176 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
177 return SE.getAddExpr(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagNone, Depth: 0);
178 });
179 if (match(V, P: m_Sub(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
180 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
181 return SE.getMinusSCEV(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagNone, Depth: 0);
182 });
183 if (match(V, P: m_Not(Op0: m_VPValue(V&: LHSVal)))) {
184 // not X = xor X, -1 = -1 - X
185 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
186 return SE.getMinusSCEV(LHS: SE.getMinusOne(Ty: Ops[0]->getType()), RHS: Ops[0]);
187 });
188 }
189 if (match(V, P: m_Mul(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
190 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
191 return SE.getMulExpr(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagNone, Depth: 0);
192 });
193 // Handle shl by constant: x << c is equivalent to x * (1 << c). A shift
194 // amount >= the bit width produces poison; do not rewrite it, as
195 // getPowerOfTwo requires the power to be in range.
196 uint64_t ShiftAmt;
197 if (match(V, P: m_Shl(Op0: m_VPValue(V&: LHSVal), Op1: m_ConstantInt(C&: ShiftAmt))) &&
198 ShiftAmt < LHSVal->getScalarType()->getScalarSizeInBits())
199 return CreateSCEV(LHSVal, [&](ArrayRef<SCEVUse> Ops) {
200 return SE.getMulExpr(LHS: Ops[0],
201 RHS: SE.getPowerOfTwo(Ty: Ops[0]->getType(), Power: ShiftAmt));
202 });
203 if (match(V, P: m_LShr(Op0: m_VPValue(V&: LHSVal), Op1: m_ConstantInt(C&: ShiftAmt)))) {
204 Type *Ty = V->getScalarType();
205 if (ShiftAmt < SE.getTypeSizeInBits(Ty))
206 return CreateSCEV(LHSVal, [&](ArrayRef<SCEVUse> Ops) {
207 return SE.getUDivExpr(LHS: Ops[0], RHS: SE.getPowerOfTwo(Ty, Power: ShiftAmt));
208 });
209 }
210 if (match(V, P: m_UDiv(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
211 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
212 return SE.getUDivExpr(LHS: Ops[0], RHS: Ops[1]);
213 });
214 if (match(V, P: m_URem(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
215 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
216 return SE.getURemExpr(LHS: Ops[0], RHS: Ops[1]);
217 });
218 // A SDiv with non-negative operands is equivalent to an UDiv.
219 if (match(V, P: m_SDiv(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) {
220 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
221 if (!SE.isKnownNonNegative(S: Ops[0]) || !SE.isKnownNonNegative(S: Ops[1]))
222 return SE.getCouldNotCompute();
223 return SE.getUDivExpr(LHS: Ops[0], RHS: Ops[1]);
224 });
225 }
226 // A SRem with non-negative operands is equivalent to an URem.
227 if (match(V, P: m_SRem(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) {
228 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
229 if (!SE.isKnownNonNegative(S: Ops[0]) || !SE.isKnownNonNegative(S: Ops[1]))
230 return SE.getCouldNotCompute();
231 return SE.getURemExpr(LHS: Ops[0], RHS: Ops[1]);
232 });
233 }
234 // Handle AND with constant mask: x & (2^n - 1) can be represented as x % 2^n.
235 const APInt *Mask;
236 if (match(V, P: m_c_BinaryAnd(Op0: m_VPValue(V&: LHSVal), Op1: m_APInt(C&: Mask))) &&
237 (*Mask + 1).isPowerOf2())
238 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
239 return SE.getURemExpr(LHS: Ops[0], RHS: SE.getConstant(Val: *Mask + 1));
240 });
241 // SCEV models ptrtoaddr, but not ptrtoint, mirroring createSCEV.
242 if (match(V, P: m_PtrToAddr(Op0: m_VPValue(V&: LHSVal))))
243 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
244 return SE.getPtrToAddrExpr(Op: Ops[0]);
245 });
246 if (match(V, P: m_Trunc(Op0: m_VPValue(V&: LHSVal)))) {
247 Type *DestTy = V->getScalarType();
248 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
249 return SE.getTruncateExpr(Op: Ops[0], Ty: DestTy);
250 });
251 }
252 if (match(V, P: m_ZExt(Op0: m_VPValue(V&: LHSVal)))) {
253 Type *DestTy = V->getScalarType();
254 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
255 return SE.getZeroExtendExpr(Op: Ops[0], Ty: DestTy);
256 });
257 }
258 if (match(V, P: m_SExt(Op0: m_VPValue(V&: LHSVal)))) {
259 Type *DestTy = V->getScalarType();
260
261 // Mirror SCEV's createSCEV handling for sext(sub nsw): push sign extension
262 // onto the operands before computing the subtraction.
263 VPValue *SubLHS, *SubRHS;
264 auto *SubR = dyn_cast<VPRecipeWithIRFlags>(Val: LHSVal);
265 if (match(V: LHSVal, P: m_Sub(Op0: m_VPValue(V&: SubLHS), Op1: m_VPValue(V&: SubRHS))) && SubR &&
266 SubR->hasNoSignedWrap() && poisonGuaranteesUB(V: LHSVal)) {
267 const SCEV *V1 = getSCEVExprForVPValue(V: SubLHS, PSE, L);
268 const SCEV *V2 = getSCEVExprForVPValue(V: SubRHS, PSE, L);
269 if (!isa<SCEVCouldNotCompute>(Val: V1) && !isa<SCEVCouldNotCompute>(Val: V2))
270 return SE.getMinusSCEV(LHS: SE.getSignExtendExpr(Op: V1, Ty: DestTy),
271 RHS: SE.getSignExtendExpr(Op: V2, Ty: DestTy), Flags: SCEV::FlagNSW);
272 }
273
274 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
275 return SE.getSignExtendExpr(Op: Ops[0], Ty: DestTy);
276 });
277 }
278 if (match(V,
279 P: m_Intrinsic<Intrinsic::umax>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal))))
280 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
281 return SE.getUMaxExpr(LHS: Ops[0], RHS: Ops[1]);
282 });
283 if (match(V,
284 P: m_Intrinsic<Intrinsic::smax>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal))))
285 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
286 return SE.getSMaxExpr(LHS: Ops[0], RHS: Ops[1]);
287 });
288 if (match(V,
289 P: m_Intrinsic<Intrinsic::umin>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal))))
290 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
291 return SE.getUMinExpr(LHS: Ops[0], RHS: Ops[1]);
292 });
293 if (match(V,
294 P: m_Intrinsic<Intrinsic::smin>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal))))
295 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
296 return SE.getSMinExpr(LHS: Ops[0], RHS: Ops[1]);
297 });
298 if (match(V, P: m_Intrinsic<Intrinsic::abs>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue())))
299 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
300 // is_int_min_poison is local to this intrinsic: poison on INT_MIN is
301 // not proof that the input is never INT_MIN, nor that poison reaches
302 // UB. Do not translate it to SCEV's global IsNSW flag.
303 return SE.getAbsExpr(Op: Ops[0], /*IsNSW=*/false);
304 });
305
306 ArrayRef<VPValue *> Ops;
307 Type *SourceElementType;
308 if (match(V, P: m_GetElementPtr(SourceElementType, Operands&: Ops))) {
309 return CreateSCEV(Ops, [&](ArrayRef<SCEVUse> Ops) {
310 return SE.getGEPExpr(BaseExpr: Ops.front(), IndexExprs: Ops.drop_front(), SrcElementTy: SourceElementType);
311 });
312 }
313
314 // TODO: Support constructing SCEVs for more recipes as needed.
315 const VPRecipeBase *DefR = V->getDefiningRecipe();
316 const SCEV *Expr =
317 TypeSwitch<const VPRecipeBase *, const SCEV *>(DefR)
318 .Case(caseFn: [](const VPExpandSCEVRecipe *R) { return R->getSCEV(); })
319 .Case(caseFn: [&SE, &PSE, L](const VPWidenIntOrFpInductionRecipe *R) {
320 const SCEV *Step = getSCEVExprForVPValue(V: R->getStepValue(), PSE, L);
321 if (!L || isa<SCEVCouldNotCompute>(Val: Step))
322 return SE.getCouldNotCompute();
323 const SCEV *Start =
324 getSCEVExprForVPValue(V: R->getStartValue(), PSE, L);
325 const SCEV *AddRec =
326 SE.getAddRecExpr(Start, Step, L, Flags: SCEV::FlagNone);
327 if (R->isTruncated())
328 return SE.getTruncateExpr(Op: AddRec, Ty: R->getScalarType());
329 return AddRec;
330 })
331 .Case(caseFn: [&SE, &PSE,
332 L](const VPWidenPointerInductionRecipe *R) -> const SCEV * {
333 const SCEV *Start =
334 getSCEVExprForVPValue(V: R->getStartValue(), PSE, L);
335 if (!L || isa<SCEVCouldNotCompute>(Val: Start))
336 return SE.getCouldNotCompute();
337 const SCEV *Step = getSCEVExprForVPValue(V: R->getStepValue(), PSE, L);
338 if (isa<SCEVCouldNotCompute>(Val: Step))
339 return SE.getCouldNotCompute();
340 return SE.getAddRecExpr(Start, Step, L, Flags: SCEV::FlagNone);
341 })
342 .Case(caseFn: [&SE, &PSE, L](const VPDerivedIVRecipe *R) -> const SCEV * {
343 const SCEV *Start = getSCEVExprForVPValue(V: R->getOperand(N: 0), PSE, L);
344 const SCEV *IV = getSCEVExprForVPValue(V: R->getOperand(N: 1), PSE, L);
345 const SCEV *Scale = getSCEVExprForVPValue(V: R->getOperand(N: 2), PSE, L);
346 if (any_of(Range: ArrayRef({Start, IV, Scale}),
347 P: IsaPred<SCEVCouldNotCompute>))
348 return SE.getCouldNotCompute();
349
350 return SE.getAddExpr(
351 LHS: SE.getTruncateOrSignExtend(V: Start, Ty: IV->getType()),
352 RHS: SE.getMulExpr(
353 LHS: IV, RHS: SE.getTruncateOrSignExtend(V: Scale, Ty: IV->getType())));
354 })
355 .Case(caseFn: [&SE, &PSE, L](const VPScalarIVStepsRecipe *R) {
356 const SCEV *IV = getSCEVExprForVPValue(V: R->getOperand(N: 0), PSE, L);
357 const SCEV *Step = getSCEVExprForVPValue(V: R->getOperand(N: 1), PSE, L);
358 if (isa<SCEVCouldNotCompute>(Val: IV) || !isa<SCEVConstant>(Val: Step))
359 return SE.getCouldNotCompute();
360 return SE.getTruncateOrSignExtend(V: IV, Ty: Step->getType());
361 })
362 .Default(
363 defaultFn: [&SE](const VPRecipeBase *) { return SE.getCouldNotCompute(); });
364
365 return PSE.getPredicatedSCEV(Expr);
366}
367
368std::optional<int64_t>
369vputils::getConstantStride(VPValue *Addr, Type *AccessTy,
370 PredicatedScalarEvolution &PSE, const Loop *L) {
371 assert(!hasIrregularType(AccessTy, L->getHeader()->getDataLayout()) &&
372 "should not try to widen irregular types");
373 const SCEV *AddrSCEV = getSCEVExprForVPValue(V: Addr, PSE, L);
374 auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: AddrSCEV);
375 if (!AddRec)
376 return {};
377
378 return getStrideFromAddRec(AR: AddRec, Lp: L, AccessTy, /*Ptr=*/nullptr, PSE);
379}
380
381bool vputils::isAddressSCEVForCost(const SCEV *Addr, ScalarEvolution &SE,
382 const Loop *L) {
383 // If address is an SCEVAddExpr, we require that all operands must be either
384 // be invariant or a (possibly sign-extend) affine AddRec.
385 if (auto *PtrAdd = dyn_cast<SCEVAddExpr>(Val: Addr)) {
386 return all_of(Range: PtrAdd->operands(), P: [&SE, L](const SCEV *Op) {
387 return SE.isLoopInvariant(S: Op, L) ||
388 match(S: Op, P: m_scev_SExt(Op0: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV()))) ||
389 match(S: Op, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV()));
390 });
391 }
392
393 // Otherwise, check if address is loop invariant or an affine add recurrence.
394 return SE.isLoopInvariant(S: Addr, L) ||
395 match(S: Addr, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV()));
396}
397
398unsigned vputils::getOpcode(const VPValue *V) {
399 return TypeSwitch<const VPValue *, unsigned>(V)
400 .Case<VPInstruction, VPWidenRecipe, VPWidenCastRecipe, VPWidenGEPRecipe,
401 VPReplicateRecipe, VPWidenPHIRecipe, VPWidenLoadRecipe,
402 VPWidenLoadEVLRecipe>(caseFn: [](auto *I) { return I->getOpcode(); })
403 .Case<VPVectorPointerRecipe, VPPredInstPHIRecipe, VPScalarIVStepsRecipe>(
404 caseFn: [](auto *I) {
405 // For recipes that do not directly map to LLVM IR instructions,
406 // assign opcodes after the last VPInstruction opcode (which is also
407 // after the last IR Instruction opcode), based on the VPRecipeID.
408 return VPInstruction::OpsEnd + 1 + I->getVPRecipeID();
409 })
410 .Default(defaultFn: [](auto *) { return 0; });
411}
412
413std::optional<std::pair<bool, unsigned>>
414vputils::getOpcodeOrIntrinsicID(const VPValue *V) {
415 if (Intrinsic::ID IID = vputils::getIntrinsicID(R: V))
416 return std::make_pair(x: true, y&: IID);
417 if (unsigned Opcode = vputils::getOpcode(V))
418 return std::make_pair(x: false, y&: Opcode);
419 return {};
420}
421
422/// Returns true if \p Opcode preserves uniformity, i.e., if all operands are
423/// uniform, the result will also be uniform.
424static bool preservesUniformity(unsigned Opcode) {
425 if (Instruction::isBinaryOp(Opcode) || Instruction::isCast(Opcode))
426 return true;
427 switch (Opcode) {
428 case Instruction::Freeze:
429 case Instruction::GetElementPtr:
430 case Instruction::ICmp:
431 case Instruction::FCmp:
432 case Instruction::Select:
433 case VPInstruction::Not:
434 case VPInstruction::Broadcast:
435 case VPInstruction::MaskedCond:
436 case VPInstruction::PtrAdd:
437 return true;
438 default:
439 return false;
440 }
441}
442
443bool vputils::isElementwise(const VPValue *V) {
444 // TODO: Handle more opcodes and recipes.
445 if (!isa<VPInstruction, VPWidenRecipe>(Val: V))
446 return false;
447 unsigned Opcode = getOpcode(V);
448 return Instruction::isUnaryOp(Opcode) || Instruction::isBinaryOp(Opcode);
449}
450
451bool vputils::isSingleScalar(const VPValue *VPV) {
452 // Live-in, symbolic and canonical-IV region values are single-scalar.
453 if (auto *RV = dyn_cast<VPRegionValue>(Val: VPV))
454 return RV == RV->getDefiningRegion()->getCanonicalIV();
455 if (isa<VPIRValue, VPSymbolicValue>(Val: VPV))
456 return true;
457
458 if (auto *Rep = dyn_cast<VPReplicateRecipe>(Val: VPV)) {
459 const VPRegionBlock *RegionOfR = Rep->getRegion();
460 // Don't consider recipes in replicate regions as uniform yet; their first
461 // lane cannot be accessed when executing the replicate region for other
462 // lanes.
463 if (RegionOfR && RegionOfR->isReplicator())
464 return false;
465 return Rep->isSingleScalar() || (preservesUniformity(Opcode: Rep->getOpcode()) &&
466 all_of(Range: Rep->operands(), P: isSingleScalar));
467 }
468 if (isa<VPWidenGEPRecipe, VPBlendRecipe>(Val: VPV))
469 return all_of(Range: VPV->getDefiningRecipe()->operands(), P: isSingleScalar);
470 if (auto *WidenR = dyn_cast<VPWidenRecipe>(Val: VPV)) {
471 return preservesUniformity(Opcode: WidenR->getOpcode()) &&
472 all_of(Range: WidenR->operands(), P: isSingleScalar);
473 }
474 if (auto *VPI = dyn_cast<VPInstruction>(Val: VPV))
475 return VPI->isSingleScalar() || VPI->isVectorToScalar() ||
476 (preservesUniformity(Opcode: VPI->getOpcode()) &&
477 all_of(Range: VPI->operands(), P: isSingleScalar));
478 if (auto *RR = dyn_cast<VPReductionRecipe>(Val: VPV))
479 return !RR->isPartialReduction();
480 if (isa<VPVectorPointerRecipe, VPVectorEndPointerRecipe, VPDerivedIVRecipe>(
481 Val: VPV))
482 return true;
483 if (auto *Expr = dyn_cast<VPExpressionRecipe>(Val: VPV))
484 return Expr->isVectorToScalar();
485
486 // VPExpandSCEVRecipes must be placed in the entry and are always uniform.
487 return isa<VPExpandSCEVRecipe>(Val: VPV);
488}
489
490bool vputils::isUniformAcrossVFsAndUFs(const VPValue *V) {
491 // Live-ins, symbolic and canonical-IV region values are uniform.
492 if (auto *RV = dyn_cast<VPRegionValue>(Val: V))
493 return RV == RV->getDefiningRegion()->getCanonicalIV();
494 if (isa<VPIRValue, VPSymbolicValue>(Val: V))
495 return true;
496
497 const VPRecipeBase *R = V->getDefiningRecipe();
498 const VPBasicBlock *VPBB = R ? R->getParent() : nullptr;
499 const VPlan *Plan = VPBB ? VPBB->getPlan() : nullptr;
500 if (VPBB &&
501 (VPBB == Plan->getVectorPreheader() || VPBB == Plan->getEntry())) {
502 if (match(V: R,
503 P: m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>()) ||
504 match(V: R, P: m_ExtractVectorForPart(Op0: m_VPValue(), Op1: m_VPValue())))
505 return false;
506 return all_of(Range: R->operands(), P: isUniformAcrossVFsAndUFs);
507 }
508
509 return TypeSwitch<const VPRecipeBase *, bool>(R)
510 .Case(caseFn: [](const VPDerivedIVRecipe *R) { return true; })
511 .Case(caseFn: [](const VPReplicateRecipe *R) {
512 // Be conservative about side-effects, except for the
513 // known-side-effecting assumes and stores, which we know will be
514 // uniform. Each alloca creates a distinct allocation, so allocas are
515 // never uniform.
516 return R->isSingleScalar() && R->getOpcode() != Instruction::Alloca &&
517 (!R->mayHaveSideEffects() ||
518 isa<AssumeInst, StoreInst>(Val: R->getUnderlyingInstr())) &&
519 all_of(Range: R->operands(), P: isUniformAcrossVFsAndUFs);
520 })
521 .Case(caseFn: [](const VPWidenRecipe *R) {
522 return preservesUniformity(Opcode: R->getOpcode()) &&
523 all_of(Range: R->operands(), P: isUniformAcrossVFsAndUFs);
524 })
525 .Case(caseFn: [](const VPPhi *) {
526 // Bail out on VPPhi, as we can end up in infinite cycles.
527 return false;
528 })
529 .Case(caseFn: [](const VPInstruction *VPI) {
530 return (VPI->isSingleScalar() || VPI->isVectorToScalar() ||
531 preservesUniformity(Opcode: VPI->getOpcode())) &&
532 all_of(Range: VPI->operands(), P: isUniformAcrossVFsAndUFs);
533 })
534 .Case(caseFn: [](const VPWidenCastRecipe *R) {
535 // A cast is uniform according to its operand.
536 return isUniformAcrossVFsAndUFs(V: R->getOperand(N: 0));
537 })
538 .Default(defaultFn: [](const VPRecipeBase *) { // A value is considered non-uniform
539 // unless proven otherwise.
540 return false;
541 });
542}
543
544bool vputils::doesGeneratePerAllLanes(const VPRecipeBase *R) {
545 if (auto *RepR = dyn_cast<VPReplicateRecipe>(Val: R))
546 return RepR->doesGeneratePerAllLanes();
547 if (auto *VPI = dyn_cast<VPInstruction>(Val: R))
548 return VPI->doesGeneratePerAllLanes();
549 if (auto *SIVSteps = dyn_cast<VPScalarIVStepsRecipe>(Val: R))
550 return SIVSteps->doesGeneratePerAllLanes();
551 return false;
552}
553
554VPBasicBlock *vputils::getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT) {
555 auto DepthFirst = vp_depth_first_shallow(G: Plan.getEntry());
556 auto I = find_if(Range&: DepthFirst, P: [&VPDT](VPBlockBase *VPB) {
557 return VPBlockUtils::isHeader(VPB, VPDT);
558 });
559 return I == DepthFirst.end() ? nullptr : cast<VPBasicBlock>(Val: *I);
560}
561
562unsigned vputils::getVFScaleFactor(VPRecipeBase *R) {
563 if (!R)
564 return 1;
565 if (auto *RR = dyn_cast<VPReductionPHIRecipe>(Val: R))
566 return RR->getVFScaleFactor();
567 if (auto *RR = dyn_cast<VPReductionRecipe>(Val: R))
568 return RR->getVFScaleFactor();
569 if (auto *ER = dyn_cast<VPExpressionRecipe>(Val: R))
570 return ER->getVFScaleFactor();
571 assert(
572 (!isa<VPInstruction>(R) || cast<VPInstruction>(R)->getOpcode() !=
573 VPInstruction::ReductionStartVector) &&
574 "getting scaling factor of reduction-start-vector not implemented yet");
575 return 1;
576}
577
578bool vputils::cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking) {
579 // Assumes don't alias anything or throw; as long as they're guaranteed to
580 // execute, they're safe to hoist. They should however not be sunk, as it
581 // would destroy information.
582 if (match(V: &R, P: m_Intrinsic<Intrinsic::assume>()))
583 return Sinking;
584 if (R.mayHaveSideEffects() || R.mayReadFromMemory() || R.isPhi())
585 return true;
586 // Allocas cannot be hoisted.
587 auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R);
588 return RepR && RepR->getOpcode() == Instruction::Alloca;
589}
590
591SmallVector<VPBasicBlock *>
592VPBlockUtils::blocksInSingleSuccessorChainBetween(VPBasicBlock *FirstBB,
593 VPBasicBlock *LastBB) {
594 assert(FirstBB->getParent() == LastBB->getParent() &&
595 "FirstBB and LastBB from different regions");
596#ifndef NDEBUG
597 bool InSingleSuccChain = false;
598 for (VPBlockBase *Succ = FirstBB; Succ; Succ = Succ->getSingleSuccessor())
599 InSingleSuccChain |= (Succ == LastBB);
600 assert(InSingleSuccChain &&
601 "LastBB unreachable from FirstBB in single-successor chain");
602#endif
603 auto Blocks = to_vector(
604 Range: VPBlockUtils::blocksOnly<VPBasicBlock>(Range: vp_depth_first_deep(G: FirstBB)));
605 auto *LastIt = find(Range&: Blocks, Val: LastBB);
606 assert(LastIt != Blocks.end() &&
607 "LastBB unreachable from FirstBB in depth-first traversal");
608 Blocks.erase(CS: std::next(x: LastIt), CE: Blocks.end());
609 return Blocks;
610}
611
612VPValue *vputils::findIncomingAliasMask(const VPlan &Plan) {
613 for (VPRecipeBase &R : *Plan.getVectorPreheader())
614 if (match(V: &R, P: m_VPInstruction<VPInstruction::IncomingAliasMask>()))
615 return cast<VPInstruction>(Val: &R);
616 return nullptr;
617}
618
619SmallVector<std::pair<VPBasicBlock *, VPIRBasicBlock *>>
620vputils::getEarlyExits(const VPlan &Plan, const VPBlockBase *MiddleVPBB) {
621 SmallVector<std::pair<VPBasicBlock *, VPIRBasicBlock *>> Exits;
622 for (VPIRBasicBlock *ExitVPBB : Plan.getExitBlocks())
623 for (VPBlockBase *Pred : ExitVPBB->getPredecessors())
624 if (Pred != MiddleVPBB)
625 Exits.emplace_back(Args: cast<VPBasicBlock>(Val: Pred), Args&: ExitVPBB);
626 return Exits;
627}
628
629VPScalarIVStepsRecipe *vputils::createScalarIVSteps(
630 VPlan &Plan, InductionDescriptor::InductionKind Kind,
631 Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp,
632 Type *ResultTy, VPValue *StartV, VPValue *Step, DebugLoc DL,
633 VPBuilder &Builder, const VPIRFlags::WrapFlagsTy &Flags) {
634 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
635 VPBasicBlock *HeaderVPBB = LoopRegion->getEntryBasicBlock();
636 VPValue *CanonicalIV = LoopRegion->getCanonicalIV();
637 VPValue *BaseIV =
638 Builder.createDerivedIV(Kind, FPBinOp, Start: StartV, Current: CanonicalIV, Step, Flags);
639
640 // Truncate BaseIV and Step to ResultTy.
641 if (ResultTy->isIntegerTy()) {
642 [[maybe_unused]] Type *BaseIVTy = BaseIV->getScalarType();
643 assert(BaseIVTy->isIntegerTy() && "Integral BaseIV type expected");
644 assert(BaseIVTy->getPrimitiveSizeInBits() >=
645 ResultTy->getPrimitiveSizeInBits() &&
646 "BaseIV's type must be at least as large as ResultTy");
647 BaseIV = Builder.createScalarZExtOrTrunc(Op: BaseIV, ResultTy, DL);
648 [[maybe_unused]] Type *StepTy = Step->getScalarType();
649 assert(StepTy->isIntegerTy() && "Integral Step type expected");
650 assert(StepTy->getPrimitiveSizeInBits() >=
651 ResultTy->getPrimitiveSizeInBits() &&
652 "Step's type must be at least as large as ResultTy");
653 auto *VecPreheader =
654 cast<VPBasicBlock>(Val: HeaderVPBB->getSingleHierarchicalPredecessor());
655 VPBuilder::InsertPointGuard Guard(Builder);
656 Builder.setInsertPoint(VecPreheader);
657 Step = Builder.createScalarZExtOrTrunc(Op: Step, ResultTy, DL);
658 }
659 return Builder.createScalarIVSteps(InductionOpcode, FPBinOp, IV: BaseIV, Step,
660 VF: &Plan.getVF(), DL);
661}
662
663VPValue *
664vputils::scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV,
665 VPlan &Plan, VPBuilder &Builder) {
666 const InductionDescriptor &ID = PtrIV->getInductionDescriptor();
667 VPIRValue *StartV = Plan.getZero(Ty: ID.getStep()->getType());
668 VPValue *StepV = PtrIV->getOperand(N: 1);
669 VPScalarIVStepsRecipe *Steps = createScalarIVSteps(
670 Plan, Kind: InductionDescriptor::IK_IntInduction, InductionOpcode: Instruction::Add, FPBinOp: nullptr,
671 ResultTy: StartV->getScalarType(), StartV, Step: StepV, DL: PtrIV->getDebugLoc(), Builder);
672
673 return Builder.createPtrAdd(Ptr: PtrIV->getStartValue(), Offset: Steps,
674 DL: PtrIV->getDebugLoc(), Name: "next.gep");
675}
676
677bool VPBlockUtils::isHeader(const VPBlockBase *VPB,
678 const VPDominatorTree &VPDT) {
679 auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB);
680 if (!VPBB)
681 return false;
682
683 // If VPBB is in a region R, VPBB is a loop header if R is a loop region with
684 // VPBB as its entry, i.e., free of predecessors.
685 if (auto *R = VPBB->getParent())
686 return !R->isReplicator() && !VPBB->hasPredecessors();
687
688 // A header dominates its second predecessor (the latch), with the other
689 // predecessor being the preheader
690 return VPB->getPredecessors().size() == 2 &&
691 VPDT.dominates(A: VPB, B: VPB->getPredecessors()[1]);
692}
693
694bool VPBlockUtils::isLatch(const VPBlockBase *VPB,
695 const VPDominatorTree &VPDT) {
696 // A latch has a header as its last successor, with its other successors
697 // leaving the loop. A preheader OTOH has a header as its first (and only)
698 // successor.
699 return VPB->getNumSuccessors() >= 2 &&
700 VPBlockUtils::isHeader(VPB: VPB->getSuccessors().back(), VPDT);
701}
702
703std::pair<VPBasicBlock *, VPBasicBlock *>
704VPBlockUtils::getPlainCFGHeaderAndLatch(const VPlan &Plan) {
705 VPBasicBlock *Header = cast<VPBasicBlock>(
706 Val: Plan.getEntry()->getNumSuccessors() == 1
707 ? Plan.getEntry()->getSingleSuccessor()
708 : Plan.getEntry()->getSuccessors()[1]->getSingleSuccessor());
709 assert(Header->getNumPredecessors() == 2 &&
710 "Header must have exactly 2 predecessors");
711 auto *Latch = cast<VPBasicBlock>(Val: Header->getPredecessors()[1]);
712 return {Header, Latch};
713}
714
715VPBasicBlock *VPBlockUtils::getPlainCFGMiddleBlock(const VPlan &Plan) {
716 return cast<VPBasicBlock>(Val: Plan.getScalarPreheader()->getPredecessors()[0]);
717}
718
719VPIRFlags vputils::getFlagsForInduction(const InductionDescriptor &ID,
720 const VPPhi *PhiR) {
721 if (ID.getKind() == InductionDescriptor::IK_FpInduction)
722 return ID.getInductionBinOp()->getFastMathFlags();
723
724 // The flags only bound the induction values if the increment directly
725 // updates PhiR.
726 VPValue *Inc = PhiR->getOperand(N: 1);
727 if (match(V: Inc, P: m_c_Add(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue())))
728 return cast<VPInstruction>(Val: Inc)->getNoWrapFlagsOrNone();
729
730 if (match(V: Inc, P: m_Sub(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue()))) {
731 // The step of a sub induction is negated, so NUW cannot be preserved. NSW
732 // can, if the step is not the signed minimum.
733 ConstantInt *Step = ID.getConstIntStepValue();
734 bool NSW = cast<VPInstruction>(Val: Inc)->getNoWrapFlagsOrNone().HasNSW &&
735 Step && !Step->isMinValue(/*IsSigned=*/true);
736 return VPIRFlags::WrapFlagsTy(/*NUW*/ false, NSW);
737 }
738
739 return VPIRFlags::WrapFlagsTy(false, false);
740}
741
742std::optional<MemoryLocation>
743vputils::getMemoryLocation(const VPRecipeBase &R) {
744 auto *M = dyn_cast<VPIRMetadata>(Val: &R);
745 if (!M)
746 return std::nullopt;
747 MemoryLocation Loc;
748 // Populate noalias metadata from VPIRMetadata.
749 if (MDNode *NoAliasMD = M->getMetadata(Kind: LLVMContext::MD_noalias))
750 Loc.AATags.NoAlias = NoAliasMD;
751 if (MDNode *AliasScopeMD = M->getMetadata(Kind: LLVMContext::MD_alias_scope))
752 Loc.AATags.Scope = AliasScopeMD;
753 return Loc;
754}
755
756VPInstruction *vputils::findCanonicalIVIncrement(VPlan &Plan) {
757 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
758 VPRegionValue *CanIV = LoopRegion->getCanonicalIV();
759 assert(CanIV && "Expected loop region to have a canonical IV");
760
761 VPSymbolicValue &VFxUF = Plan.getVFxUF();
762
763 // Check if \p Step matches the expected increment step, accounting for
764 // materialization of VFxUF and UF.
765 auto IsIncrementStep = [&](VPValue *Step) -> bool {
766 if (!VFxUF.isMaterialized())
767 return Step == &VFxUF;
768
769 VPSymbolicValue &UF = Plan.getUF();
770 if (!UF.isMaterialized())
771 return Step == &UF ||
772 match(V: Step, P: m_c_Mul(Op0: m_Specific(VPV: &Plan.getUF()), Op1: m_VScale()));
773
774 // Alias masking: step is number of active lanes of a dependence mask.
775 if (match(V: Step, P: m_ZExtOrTruncOrSelf(
776 Op0: m_VPInstruction<VPInstruction::NumActiveLanes>())))
777 return true;
778
779 unsigned ConcreteUF = Plan.getConcreteUF();
780 // Fixed VF: step is just the concrete UF.
781 if (match(V: Step, P: m_SpecificInt(V: ConcreteUF)))
782 return true;
783
784 // Scalable VF: step involves VScale.
785 if (ConcreteUF == 1)
786 return match(V: Step, P: m_VScale());
787 if (match(V: Step, P: m_c_Mul(Op0: m_SpecificInt(V: ConcreteUF), Op1: m_VScale())))
788 return true;
789 // mul(VScale, ConcreteUF) may have been simplified to
790 // shl(VScale, log2(ConcreteUF)) when ConcreteUF is a power of 2.
791 return isPowerOf2_32(Value: ConcreteUF) &&
792 match(V: Step, P: m_Shl(Op0: m_VScale(), Op1: m_SpecificInt(V: Log2_32(Value: ConcreteUF))));
793 };
794
795 VPInstruction *Increment = nullptr;
796 for (VPUser *U : CanIV->users()) {
797 VPValue *Step;
798 if (isa<VPInstruction>(Val: U) &&
799 match(U, P: m_c_Add(Op0: m_Specific(VPV: CanIV), Op1: m_VPValue(V&: Step))) &&
800 IsIncrementStep(Step)) {
801 assert(!Increment && "There must be a unique increment");
802 Increment = cast<VPInstruction>(Val: U);
803 }
804 }
805
806 assert((!VFxUF.isMaterialized() || Increment) &&
807 "After materializing VFxUF, an increment must exist");
808 assert((!Increment ||
809 LoopRegion->hasCanonicalIVNUW() == Increment->hasNoUnsignedWrap()) &&
810 "NUW flag in region and increment must match");
811 return Increment;
812}
813
814/// Find the ComputeReductionResult recipe for \p PhiR, looking through selects
815/// inserted for predicated reductions or tail folding.
816VPInstruction *vputils::findComputeReductionResult(VPReductionPHIRecipe *PhiR) {
817 VPValue *BackedgeVal = PhiR->getBackedgeValue();
818 if (auto *Res =
819 findUserOf<VPInstruction::ComputeReductionResult>(V: BackedgeVal))
820 return Res;
821
822 // Look through selects inserted for tail folding or predicated reductions.
823 VPRecipeBase *SelR =
824 findUserOf(V: BackedgeVal, P: m_Select(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue()));
825 if (!SelR)
826 return nullptr;
827 return findUserOf<VPInstruction::ComputeReductionResult>(
828 V: cast<VPSingleDefRecipe>(Val: SelR));
829}
830
831bool vputils::isUsedByLoadStoreAddress(const VPValue *V) {
832 SmallPtrSet<const VPValue *, 4> Seen;
833 SmallVector<const VPValue *> WorkList = {V};
834
835 while (!WorkList.empty()) {
836 const VPValue *Cur = WorkList.pop_back_val();
837 if (!Seen.insert(Ptr: Cur).second)
838 continue;
839
840 auto *Blend = dyn_cast<VPBlendRecipe>(Val: Cur);
841 // Skip blends that use V only through a compare by checking if any incoming
842 // value was already visited.
843 if (Blend && none_of(Range: seq<unsigned>(Begin: 0, End: Blend->getNumIncomingValues()),
844 P: [&](unsigned I) {
845 return Seen.contains(Ptr: Blend->getIncomingValue(Idx: I));
846 }))
847 continue;
848
849 for (VPUser *U : Cur->users()) {
850 if (auto *InterleaveR = dyn_cast<VPInterleaveBase>(Val: U))
851 if (InterleaveR->getAddr() == Cur)
852 return true;
853 // Cur is used as the pointer of a (possibly masked) load (operand 0) or
854 // store (operand 1).
855 if (match(U, P: m_CombineOr(Ps: m_Unary<Instruction::Load>(Op0: m_Specific(VPV: Cur)),
856 Ps: m_Binary<Instruction::Store>(Op0: m_VPValue(),
857 Op1: m_Specific(VPV: Cur)))))
858 return true;
859 if (auto *MemR = dyn_cast<VPWidenMemoryRecipe>(Val: cast<VPRecipeBase>(Val: U))) {
860 if (MemR->getAddr() == Cur && MemR->isConsecutive())
861 return true;
862 }
863 }
864
865 // The legacy cost model only supports scalarization loads/stores with phi
866 // addresses, if the phi is directly used as load/store address. Don't
867 // traverse further for Blends and first-order recurrence splices.
868 if (Blend ||
869 match(V: Cur,
870 P: m_VPInstruction<VPInstruction::FirstOrderRecurrenceSplice>()))
871 continue;
872
873 // Only traverse further through users that also define a value (and can
874 // thus have their own users walked). Skip when Cur is only used as mask ,
875 // as well as loads: a loaded value does not depend on the load's operand.
876 for (VPUser *U : Cur->users()) {
877 auto *VPI = dyn_cast<VPInstruction>(Val: U);
878 if (VPI && VPI->getMask() == Cur &&
879 none_of(Range: VPI->operandsWithoutMask(), P: equal_to(Arg&: Cur)))
880 continue;
881 if (match(U, P: m_VPInstruction<Instruction::Load>()))
882 continue;
883 if (auto *SDR = dyn_cast<VPSingleDefRecipe>(Val: U))
884 WorkList.push_back(Elt: SDR);
885 }
886 }
887 return false;
888}
889
890/// Try to find a loop-invariant IR value for \p S in the plan's entry block
891/// that can be reused. Returns the corresponding live-in VPValue, or nullptr
892/// if no reusable IR value is found.
893VPValue *VPSCEVExpander::tryToReuseIRValue(const SCEV *S) {
894 if (isa<SCEVConstant, SCEVUnknown>(Val: S))
895 return nullptr;
896 VPlan &Plan = Builder.getPlan();
897 BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock();
898 for (Value *V : SE.getSCEVValues(S)) {
899 // Only reuse instructions in the plan's entry block, or, when a
900 // DominatorTree is available, any instruction that dominates it.
901 // Instructions in sibling branches may not dominate the entry block.
902 auto *I = dyn_cast<Instruction>(Val: V);
903 if (!I)
904 return Plan.getOrAddLiveIn(V);
905 if (!SE.DT.dominates(A: I->getParent(), B: PH))
906 continue;
907 Loop *IL = SE.LI.getLoopFor(BB: I->getParent());
908 if (IL && !IL->contains(BB: PH))
909 continue;
910 SmallVector<Instruction *> DropPoisonGeneratingInsts;
911 if (!SE.canReuseInstruction(S, I, DropPoisonGeneratingInsts))
912 continue;
913 for (Instruction *DropI : DropPoisonGeneratingInsts)
914 SCEVExpander::dropPoisonGeneratingAnnotationsAndReinfer(SE, I: DropI);
915 return Plan.getOrAddLiveIn(V);
916 }
917 return nullptr;
918}
919
920VPValue *VPSCEVExpander::expandAsPtrAdd(const SCEVNAryExpr *S) {
921 VPValue *Base = expand(S: SE.getPointerBase(V: S));
922 VPValue *Offset = expand(S: SE.removePointerBase(S));
923 GEPNoWrapFlags GEPFlags = S->hasNoUnsignedWrap()
924 ? GEPNoWrapFlags::noUnsignedWrap()
925 : GEPNoWrapFlags::none();
926 return Builder.createNoWrapPtrAdd(Ptr: Base, Offset, GEPFlags, DL);
927}
928
929VPValue *VPSCEVExpander::expand(const SCEV *S) {
930 if (VPValue *V = tryToReuseIRValue(S))
931 return V;
932
933 switch (S->getSCEVType()) {
934 case scConstant:
935 return Builder.getPlan().getOrAddLiveIn(V: cast<SCEVConstant>(Val: S)->getValue());
936 case scUnknown:
937 return Builder.getPlan().getOrAddLiveIn(V: cast<SCEVUnknown>(Val: S)->getValue());
938 case scVScale:
939 return Builder.createVScale(ResultTy: S->getType(), DL);
940 case scAddExpr: {
941 auto *AddE = cast<SCEVAddExpr>(Val: S);
942 VPIRFlags::WrapFlagsTy WrapFlags(AddE->hasNoUnsignedWrap(),
943 AddE->hasNoSignedWrap());
944
945 // Expand pointer SCEVAddExpr as a ptradd of the pointer base and the
946 // integer offset, matching SCEVExpander.
947 if (S->getType()->isPointerTy())
948 return expandAsPtrAdd(S: AddE);
949
950 // Non-constant-negative add operands are expanded negated and subtracted
951 // from the running result below, instead of being negated and added.
952 auto UseSubtract = [](const SCEV *Op) {
953 return Op->isNonConstantNegative();
954 };
955 // Iterate in reverse so that constants are emitted last, and move the
956 // subtracted operands last, matching SCEVExpander's LoopCompare, so that
957 // they don't start the running result.
958 SmallVector<const SCEV *, 2> SCEVOps(reverse(C: AddE->operands()));
959 stable_sort(Range&: SCEVOps, C: [&](const SCEV *L, const SCEV *R) {
960 return !UseSubtract(L) && UseSubtract(R);
961 });
962 SmallVector<VPValue *, 2> Ops;
963 for (const SCEV *Op : SCEVOps) {
964 // The first operand starts the result, so it is never subtracted.
965 bool Negate = !Ops.empty() && UseSubtract(Op);
966 Ops.push_back(Elt: expand(S: Negate ? SE.getNegativeSCEV(V: Op) : Op));
967 }
968 VPValue *Result = Ops.front();
969 for (auto [Op, OpV] : drop_begin(RangeOrContainer: zip_equal(t&: SCEVOps, u&: Ops))) {
970 if (UseSubtract(Op)) {
971 // Result + (-Op) == Result - Op, which saves the multiply for the
972 // negation. NSW only transfers if negating Op cannot overflow, see
973 // ScalarEvolution::getMinusSCEV.
974 bool HasNSW =
975 WrapFlags.HasNSW && !SE.getSignedRangeMin(S: Op).isMinSignedValue();
976 Result = Builder.createOverflowingOp(Opcode: Instruction::Sub, Operands: {Result, OpV},
977 WrapFlags: {/*HasNUW=*/false, HasNSW}, DL);
978 continue;
979 }
980 Result = Builder.createOverflowingOp(Opcode: Instruction::Add, Operands: {Result, OpV},
981 WrapFlags, DL);
982 }
983 return Result;
984 }
985 case scMulExpr: {
986 auto *MulE = cast<SCEVMulExpr>(Val: S);
987 VPIRFlags::WrapFlagsTy WrapFlags(MulE->hasNoUnsignedWrap(),
988 MulE->hasNoSignedWrap());
989 SmallVector<VPValue *, 2> Ops;
990 for (const SCEV *Op : reverse(C: MulE->operands()))
991 Ops.push_back(Elt: expand(S: Op));
992 VPValue *Result = Ops.front();
993 for (VPValue *OpV : drop_begin(RangeOrContainer&: Ops)) {
994 Result = Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {Result, OpV},
995 WrapFlags, DL);
996 }
997 return Result;
998 }
999 case scUDivExpr: {
1000 auto *UDiv = cast<SCEVUDivExpr>(Val: S);
1001 VPValue *LHS = expand(S: UDiv->getLHS());
1002 const SCEV *RHSExpr = UDiv->getRHS();
1003 VPValue *RHS = expand(S: RHSExpr);
1004 if (SafeUDivMode) {
1005 // Make sure the UDiv's divisor is guaranteed to not be zero/poison, to
1006 // avoid UB.
1007 Type *Ty = UDiv->getType();
1008 bool GuaranteedNotPoison =
1009 ScalarEvolution::isGuaranteedNotToBePoison(Op: RHSExpr);
1010 if (!GuaranteedNotPoison)
1011 RHS = Builder.createFreeze(Op: RHS, DL);
1012 if (!SE.isKnownNonZero(S: RHSExpr) || !GuaranteedNotPoison)
1013 RHS = Builder.createScalarIntrinsic(
1014 IntrinsicID: Intrinsic::umax, Operands: {RHS, Builder.getPlan().getConstantInt(Ty, Val: 1)}, ResultTy: Ty,
1015 DL);
1016 }
1017 return Builder.createNaryOp(Opcode: Instruction::UDiv, Operands: {LHS, RHS},
1018 Flags: VPIRFlags::getDefaultFlags(Opcode: Instruction::UDiv),
1019 DL);
1020 }
1021 case scTruncate:
1022 case scZeroExtend:
1023 case scSignExtend:
1024 case scPtrToAddr: {
1025 auto *Cast = cast<SCEVCastExpr>(Val: S);
1026 VPValue *Op = expand(S: Cast->getOperand());
1027 Instruction::CastOps Opcode;
1028 switch (S->getSCEVType()) {
1029 case scTruncate:
1030 Opcode = Instruction::Trunc;
1031 break;
1032 case scZeroExtend:
1033 Opcode = Instruction::ZExt;
1034 break;
1035 case scSignExtend:
1036 Opcode = Instruction::SExt;
1037 break;
1038 case scPtrToAddr:
1039 Opcode = Instruction::PtrToAddr;
1040 break;
1041 default:
1042 llvm_unreachable("Unhandled cast SCEV");
1043 }
1044
1045 // For ptrtoaddr of an IR value, reuse an existing cast dominating the
1046 // entry if there is one. Otherwise leave it to SCEVExpander, which places
1047 // the cast right after the IR value's definition, so all users can share
1048 // it.
1049 if (Opcode == Instruction::PtrToAddr) {
1050 VPlan &Plan = Builder.getPlan();
1051 BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock();
1052 if (auto *IRV = dyn_cast<VPIRValue>(Val: Op)) {
1053 if (CastInst *CI = SCEVExpander::findReusableCastForPtrToAddr(
1054 PtrOp: IRV->getValue(), Ty: S->getType(), DL: PH->getDataLayout(),
1055 Dominates: [&](const CastInst *CI) {
1056 return SE.DT.dominates(A: CI->getParent(), B: PH);
1057 }))
1058 return Plan.getOrAddLiveIn(V: CI);
1059 return vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: S);
1060 }
1061 }
1062
1063 std::optional<VPIRFlags> Flags;
1064 if (Opcode == Instruction::ZExt)
1065 Flags =
1066 VPIRFlags::NonNegFlagsTy(SE.isKnownNonNegative(S: Cast->getOperand()));
1067
1068 return Builder.createScalarCast(Opcode, Op, ResultTy: S->getType(), DL, Flags);
1069 }
1070 case scUMaxExpr:
1071 case scSMaxExpr:
1072 case scUMinExpr:
1073 case scSMinExpr:
1074 case scSequentialUMinExpr: {
1075 auto *MinMax = cast<SCEVNAryExpr>(Val: S);
1076 Intrinsic::ID IntrinsicID;
1077 switch (S->getSCEVType()) {
1078 case scUMaxExpr:
1079 IntrinsicID = Intrinsic::umax;
1080 break;
1081 case scSMaxExpr:
1082 IntrinsicID = Intrinsic::smax;
1083 break;
1084 case scUMinExpr:
1085 case scSequentialUMinExpr:
1086 IntrinsicID = Intrinsic::umin;
1087 break;
1088 case scSMinExpr:
1089 IntrinsicID = Intrinsic::smin;
1090 break;
1091 default:
1092 llvm_unreachable("Unexpected min/max SCEV type");
1093 }
1094 // Chain operands in reverse order matching SCEVExpander's expansion of
1095 // min/max expressions. In SafeUDivMode freeze expansion results of operands
1096 // other than the first for sequential UMins, to avoid short-circuiting
1097 // divide-by-0/poison.
1098 bool IsSequential = S->getSCEVType() == scSequentialUMinExpr;
1099 Type *ResultTy = MinMax->getType();
1100 bool PrevSafeMode = SafeUDivMode;
1101 SmallVector<VPValue *, 2> Ops;
1102 for (const SCEV *SCEVOp : reverse(C: MinMax->operands())) {
1103 bool MayShortCircuit =
1104 IsSequential && Ops.size() != MinMax->getNumOperands() - 1;
1105 SafeUDivMode = MayShortCircuit || PrevSafeMode;
1106 VPValue *OpV = expand(S: SCEVOp);
1107 SafeUDivMode = PrevSafeMode;
1108 if (MayShortCircuit)
1109 OpV = Builder.createFreeze(Op: OpV, DL);
1110 Ops.push_back(Elt: OpV);
1111 }
1112 VPValue *Result = Ops.front();
1113 for (VPValue *Op : drop_begin(RangeOrContainer&: Ops)) {
1114 if (!ResultTy->isPointerTy()) {
1115 Result = Builder.createScalarIntrinsic(IntrinsicID, Operands: {Result, Op},
1116 ResultTy, DL);
1117 continue;
1118 }
1119 // The min/max intrinsics don't support pointer operands, so expand
1120 // pointer-typed min/max as cmp + select, matching SCEVExpander.
1121 VPValue *Cmp = Builder.createICmp(
1122 Pred: MinMaxIntrinsic::getPredicate(ID: IntrinsicID), A: Result, B: Op, DL);
1123 Result = Builder.createSelect(Cond: Cmp, TrueVal: Result, FalseVal: Op, DL);
1124 Function &F = *Builder.getPlan().getIRFunction();
1125 if (MDNode *MD =
1126 getExplicitlyUnknownBranchWeightsIfProfiled(F, PassName: "scev-expander"))
1127 cast<VPInstruction>(Val: Result)->setMetadata(Kind: LLVMContext::MD_prof, Node: MD);
1128 }
1129 return Result;
1130 }
1131 case scAddRecExpr: {
1132 auto *AR = cast<SCEVAddRecExpr>(Val: S);
1133 VPlan &Plan = Builder.getPlan();
1134 BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock();
1135 assert(SE.DT.dominates(AR->getLoop()->getHeader(), PH) &&
1136 "can only expand AddRecs for loops outside VPlan's scope");
1137
1138 Type *Ty = AR->getType();
1139 if (auto [LCSSAPhi, Diff] = SCEVExpander::findReusableLCSSAPhi(SE, S: AR, InsertBB: PH);
1140 LCSSAPhi) {
1141 VPValue *DiffV = expand(S: Diff);
1142 VPValue *BaseV = Plan.getOrAddLiveIn(V: LCSSAPhi);
1143 if (LCSSAPhi->getType()->isPointerTy()) {
1144 if (Ty->isPointerTy())
1145 return Builder.createPtrAdd(Ptr: BaseV, Offset: DiffV, DL);
1146 BaseV = Builder.createScalarCast(Opcode: Instruction::PtrToAddr, Op: BaseV, ResultTy: Ty, DL);
1147 }
1148 return Builder.createAdd(LHS: BaseV, RHS: DiffV, DL);
1149 }
1150
1151 // Try to expand AR by re-using an existing canonical IV in the Plan's
1152 // entry. A canonical IV must be affine and integer typed.
1153 if (!AR->isAffine() || !AR->getType()->isIntegerTy())
1154 return vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: AR);
1155 auto FoundCanIV =
1156 find_if(Range: Plan.getEntry()->phis(), P: [&](const VPRecipeBase &R) {
1157 if (!SE.isSCEVable(Ty: cast<VPIRPhi>(Val: R).getIRPhi().getType()))
1158 return false;
1159 const SCEV *Candidate = SE.getSCEV(V: &cast<VPIRPhi>(Val: R).getIRPhi());
1160 return match(S: Candidate,
1161 P: m_scev_AffineAddRec(Op0: m_scev_Zero(), Op1: m_scev_One(),
1162 L: m_SpecificLoop(L: AR->getLoop()))) &&
1163 Candidate->getType() == AR->getType();
1164 });
1165 if (FoundCanIV == Plan.getEntry()->phis().end())
1166 return vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: AR);
1167
1168 // {Start, +, Step} --> Start + IV * Step, since the AddRec is affine.
1169 // Compute Offset = IV * Step.
1170 VPValue *Start = expand(S: AR->getStart());
1171 Value *CanonicalIV = &cast<VPIRPhi>(Val&: FoundCanIV)->getIRPhi();
1172 VPValue *Offset = expand(
1173 S: SE.getMulExpr(LHS: SE.getUnknown(V: CanonicalIV), RHS: AR->getStepRecurrence(SE)));
1174
1175 // Compute Start + Offset with nuw from the AddRec.
1176 return Builder.createAdd(LHS: Start, RHS: Offset, DL, Name: "",
1177 WrapFlags: {AR->hasNoUnsignedWrap(), false});
1178 }
1179 case scCouldNotCompute:
1180 llvm_unreachable("Attempt to expand a SCEVCouldNotCompute");
1181 }
1182 llvm_unreachable("Unknown SCEV kind!");
1183}
1184
1185bool vputils::isDeadRecipe(VPRecipeBase &R) {
1186 // Do remove conditional assume instructions as their conditions may be
1187 // flattened.
1188 auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R);
1189 bool IsConditionalAssume = RepR && RepR->isPredicated() &&
1190 match(V: RepR, P: m_Intrinsic<Intrinsic::assume>());
1191 if (IsConditionalAssume)
1192 return true;
1193
1194 if (R.mayHaveSideEffects())
1195 return false;
1196
1197 // Forbid removing trip-count expressions.
1198 if (isa<VPExpandSCEVRecipe>(Val: R) &&
1199 R.getVPSingleValue() == R.getParent()->getPlan()->getTripCount())
1200 return false;
1201
1202 // Recipe is dead if no user keeps the recipe alive.
1203 return all_of(Range: R.definedValues(), P: [](VPValue *V) { return V->user_empty(); });
1204}
1205
1206void vputils::recursivelyDeleteDeadRecipes(VPValue *V) {
1207 SmallVector<VPValue *> WorkList;
1208 SmallPtrSet<VPValue *, 8> Seen;
1209 WorkList.push_back(Elt: V);
1210
1211 while (!WorkList.empty()) {
1212 VPValue *Cur = WorkList.pop_back_val();
1213 if (!Seen.insert(Ptr: Cur).second)
1214 continue;
1215 VPRecipeBase *R = Cur->getDefiningRecipe();
1216 if (!R)
1217 continue;
1218 if (!isDeadRecipe(R&: *R))
1219 continue;
1220 append_range(C&: WorkList, R: R->operands());
1221 R->eraseFromParent();
1222 }
1223}
1224
1225SmallVector<VPUser *> vputils::collectUsersRecursively(VPValue *V) {
1226 SetVector<VPUser *> Users(llvm::from_range, V->users());
1227 for (unsigned I = 0; I != Users.size(); ++I) {
1228 VPRecipeBase *Cur = cast<VPRecipeBase>(Val: Users[I]);
1229 for (VPValue *V : Cur->definedValues())
1230 Users.insert_range(R: V->users());
1231 }
1232 return Users.takeVector();
1233}
1234
1235/// Returns \p Num / \p Denom as a BranchProbability, clamped so a ratio that is
1236/// neither zero nor one does not round to zero or one. BlockFrequencyInfo also
1237/// keeps a zero-weight edge distinguishable from an unreachable one.
1238static BranchProbability getBranchProbabilityKeepingPartial(uint64_t Num,
1239 uint64_t Denom) {
1240 BranchProbability P = BranchProbability::getBranchProbability(Numerator: Num, Denominator: Denom);
1241 if (Num == 0 || Num == Denom)
1242 return P;
1243 return BranchProbability::getRaw(N: std::clamp(
1244 val: P.getNumerator(), lo: 1u, hi: BranchProbability::getDenominator() - 1));
1245}
1246
1247BranchProbability vputils::getExecutionProbability(BlockFrequency Freq) {
1248 return getBranchProbabilityKeepingPartial(
1249 Num: Freq.getFrequency(),
1250 Denom: BlockFrequencyInfoImplBase::BlockMass::getFull().getMass());
1251}
1252
1253/// Returns the probability of each successor edge of \p VPBB, computed via
1254/// BranchProbabilityInfo::getEdgeProbabilitiesFromWeights from the branch
1255/// weights recorded on its terminator, or std::nullopt if not available.
1256static std::optional<SmallVector<BranchProbability>>
1257getSuccessorProbabilities(const VPBasicBlock *VPBB) {
1258 // With a single successor the edge is always taken and needs no weights.
1259 if (VPBB->getSingleSuccessor())
1260 return SmallVector<BranchProbability>{BranchProbability::getOne()};
1261
1262 SmallVector<uint32_t> Weights;
1263 auto *Term = dyn_cast_if_present<VPInstruction>(Val: VPBB->getTerminator());
1264 if (!Term || !extractBranchWeights(ProfileData: Term->getBranchWeights(), Weights) ||
1265 Weights.size() != VPBB->getNumSuccessors())
1266 return std::nullopt;
1267 return BranchProbabilityInfo::getEdgeProbabilitiesFromWeights(Weights);
1268}
1269
1270DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>>
1271vputils::computeExecutionFrequencies(ArrayRef<VPBasicBlock *> Blocks) {
1272 using BFIBase = BlockFrequencyInfoImplBase;
1273 assert(!Blocks.empty() && "expected at least the header block");
1274 // Distribute the header's frequency using BFI. Nodes for blocks are numbered
1275 // in reverse post-order. Edges leaving Blocks, i.e. a plain CFG's edges to
1276 // the middle block or to an exit block, exit to a node outside the loop.
1277 BFIBase BFI;
1278 BFIBase::BlockNode Header(0), Outside(Blocks.size());
1279 BFIBase::LoopData &Loop = BFI.Loops.emplace_back(args: nullptr, args&: Header);
1280 DenseMap<const VPBlockBase *, BFIBase::BlockNode> Nodes;
1281 for (auto [Idx, VPBB] : enumerate(First&: Blocks)) {
1282 Nodes[VPBB] = BFIBase::BlockNode(Idx);
1283 BFI.Working.emplace_back(args: BFIBase::BlockNode(Idx)).Loop = &Loop;
1284 }
1285 BFI.Working.emplace_back(args&: Outside);
1286 BFI.Working[Header.Index].getMass() = BFIBase::BlockMass::getFull();
1287
1288 // Keep track nodes reached via an edge without branch weighs or with
1289 // estimated ones
1290 SmallVector<bool> IsUnknown(Blocks.size()), IsEstimated(Blocks.size());
1291 for (auto [Idx, VPBB] : enumerate(First&: Blocks)) {
1292 BFIBase::BlockNode Node(Idx);
1293 auto Probs = getSuccessorProbabilities(VPBB);
1294 auto *Term = dyn_cast_if_present<VPInstruction>(Val: VPBB->getTerminator());
1295 bool TermIsEstimated = Term && Term->hasEstimatedBranchWeights();
1296 BFIBase::Distribution Dist;
1297 for (auto [SuccIdx, Succ] : enumerate(First&: VPBB->getSuccessors())) {
1298 BFIBase::BlockNode SuccNode = Nodes.lookup_or(Val: Succ, Default&: Outside);
1299 if (SuccNode != Header && SuccNode != Outside) {
1300 IsUnknown[SuccNode.Index] |= IsUnknown[Idx] || !Probs;
1301 IsEstimated[SuccNode.Index] |= IsEstimated[Idx] || TermIsEstimated;
1302 }
1303 if (Probs)
1304 BFI.addToDist(Dist, OuterLoop: &Loop, Pred: Node, Succ: SuccNode,
1305 Weight: getWeightFromBranchProb(Prob: (*Probs)[SuccIdx]));
1306 }
1307 if (Probs)
1308 BFI.distributeMass(Source: Node, OuterLoop: &Loop, Dist);
1309 }
1310
1311 // Round frequencies up to at least 1, so all edges are reached with a
1312 // non-zero frequency, to distinguish rarely executed blocks from unreachable
1313 // ones. blocks distinguishable from unreachable ones.
1314 DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>>
1315 Frequencies;
1316 for (auto [Idx, VPBB] : enumerate(First&: Blocks)) {
1317 std::optional<VPExecutionFrequency> &Freq = Frequencies[VPBB];
1318 if (IsUnknown[Idx])
1319 continue;
1320 uint64_t Mass = BFI.Working[Idx].getMass().getMass();
1321 Freq.emplace(args: BlockFrequency(std::max<uint64_t>(a: Mass, b: 1)), args&: IsEstimated[Idx]);
1322 }
1323 return Frequencies;
1324}
1325
1326VPIRValue *vputils::tryToFoldLiveIns(VPSingleDefRecipe &R,
1327 ArrayRef<VPValue *> Operands,
1328 const DataLayout &DL) {
1329 auto OpcodeOrIID = getOpcodeOrIntrinsicID(V: &R);
1330 if (!OpcodeOrIID)
1331 return nullptr;
1332
1333 SmallVector<Value *, 4> Ops;
1334 for (VPValue *Op : Operands) {
1335 VPValue *Candidate = Op;
1336 match(V: Op, P: m_Broadcast(Op0: m_VPValue(V&: Candidate)));
1337 if (!match(V: Candidate, P: m_LiveIn()))
1338 return nullptr;
1339 Value *V = Candidate->getUnderlyingValue();
1340 if (!V)
1341 return nullptr;
1342 Ops.push_back(Elt: V);
1343 }
1344
1345 VPlan &Plan = *R.getParent()->getPlan();
1346 auto FoldToIRValue = [&]() -> Value * {
1347 InstSimplifyFolder Folder(DL);
1348 if (OpcodeOrIID->first) {
1349 // VPInstructions store the called intrinsic as last operand.
1350 if (isa<VPInstruction>(Val: R))
1351 Ops.pop_back();
1352
1353 auto *RFlags = dyn_cast<VPRecipeWithIRFlags>(Val: &R);
1354 return Folder.FoldIntrinsic(ID: OpcodeOrIID->second, Ops, Ty: R.getScalarType(),
1355 FMF: RFlags ? RFlags->getFastMathFlagsOrNone()
1356 : FastMathFlags());
1357 }
1358 unsigned Opcode = OpcodeOrIID->second;
1359 if (Instruction::isBinaryOp(Opcode))
1360 return Folder.FoldBinOp(Opc: static_cast<Instruction::BinaryOps>(Opcode),
1361 LHS: Ops[0], RHS: Ops[1]);
1362 if (Instruction::isCast(Opcode))
1363 return Folder.FoldCast(Op: static_cast<Instruction::CastOps>(Opcode), V: Ops[0],
1364 DestTy: R.getVPSingleValue()->getScalarType());
1365 switch (Opcode) {
1366 case VPInstruction::Not:
1367 return Folder.FoldBinOp(Opc: Instruction::BinaryOps::Xor, LHS: Ops[0],
1368 RHS: Constant::getAllOnesValue(Ty: Ops[0]->getType()));
1369 case Instruction::Select:
1370 return Folder.FoldSelect(C: Ops[0], True: Ops[1], False: Ops[2]);
1371 case Instruction::ICmp:
1372 case Instruction::FCmp:
1373 return Folder.FoldCmp(P: cast<VPRecipeWithIRFlags>(Val&: R).getPredicate(), LHS: Ops[0],
1374 RHS: Ops[1]);
1375 case Instruction::GetElementPtr: {
1376 auto &RFlags = cast<VPRecipeWithIRFlags>(Val&: R);
1377 auto *GEP = cast<GetElementPtrInst>(Val: RFlags.getUnderlyingInstr());
1378 return Folder.FoldGEP(DL, Ty: GEP->getSourceElementType(), Ptr: Ops[0],
1379 IdxList: drop_begin(RangeOrContainer&: Ops), NW: RFlags.getGEPNoWrapFlags());
1380 }
1381 case VPInstruction::PtrAdd:
1382 case VPInstruction::WidePtrAdd:
1383 return Folder.FoldGEP(DL, Ty: IntegerType::getInt8Ty(C&: Plan.getContext()),
1384 Ptr: Ops[0], IdxList: Ops[1],
1385 NW: cast<VPRecipeWithIRFlags>(Val&: R).getGEPNoWrapFlags());
1386 // An extract of a live-in is an extract of a broadcast, so return the
1387 // broadcasted element.
1388 case Instruction::ExtractElement:
1389 assert(!Ops[0]->getType()->isVectorTy() && "Live-ins should be scalar");
1390 return Ops[0];
1391 case VPInstruction::ActiveLaneMask:
1392 case VPInstruction::WideActiveLaneMask: {
1393 uint64_t Multiplier = 1;
1394 if (Opcode == VPInstruction::WideActiveLaneMask) {
1395 // Optimizing WideALM can only happen after the Plan is unrolled.
1396 if (!Plan.isUnrolled())
1397 return nullptr;
1398 Multiplier = cast<ConstantInt>(Val: Ops[2])->getZExtValue();
1399 Ops.pop_back();
1400 }
1401
1402 // We rely on the fact that different VPlans are created for the
1403 // fixed-vector and scalable-vector cases.
1404 ElementCount MaxVF =
1405 *max_element(Range: Plan.vectorFactors(), C: ElementCount::isKnownLT) *
1406 Multiplier;
1407
1408 Type *I1Ty = IntegerType::getInt1Ty(C&: Plan.getContext());
1409 if (auto *C = dyn_cast_if_present<Constant>(Val: Folder.FoldIntrinsic(
1410 ID: Intrinsic::get_active_lane_mask, Ops,
1411 Ty: VectorType::get(ElementType: I1Ty, EC: MaxVF), FMF: {}, CtxF: Plan.getIRFunction()))) {
1412 // We cannot handle vector constants that are not all-true or all-false,
1413 // because they would not be collapsable to a scalar constant, that
1414 // would be necessary for live-in simplification.
1415 if (C->isOneValue())
1416 return ConstantInt::getTrue(Ty: I1Ty);
1417 if (C->isNullValue())
1418 return ConstantInt::getFalse(Ty: I1Ty);
1419 }
1420 }
1421 }
1422 return nullptr;
1423 };
1424
1425 if (Value *V = FoldToIRValue())
1426 return Plan.getOrAddLiveIn(V);
1427 return nullptr;
1428}
1429
1430void vputils::detail::pullOutPermutationsImpl(
1431 VPlan &Plan, function_ref<VPValue *(VPValue *Op)> MatchPerm,
1432 function_ref<VPSingleDefRecipe *(VPSingleDefRecipe *X)> BuildPerm) {
1433 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
1434 Range: vp_depth_first_deep(G: Plan.getEntry()))) {
1435 for (VPSingleDefRecipe &Def :
1436 make_early_inc_range(Range: make_isa_range<VPSingleDefRecipe>(Range&: *VPBB))) {
1437 if (!isElementwise(V: &Def))
1438 continue;
1439
1440 // At least one of the ops must be a permutation.
1441 if (none_of(Range: Def.operands(), P: MatchPerm))
1442 continue;
1443
1444 // All operands must be a single-use permutation or a live in (splat).
1445 if (!all_of(Range: Def.operands(), P: [&MatchPerm](VPValue *Op) {
1446 return (Op->hasOneUse() && MatchPerm(Op)) || match(V: Op, P: m_LiveIn());
1447 }))
1448 continue;
1449
1450 // Remove the inner permutations.
1451 for (unsigned I = 0, E = Def.getNumOperands(); I != E; ++I)
1452 if (VPValue *X = MatchPerm(Def.getOperand(N: I)))
1453 Def.setOperand(I, New: X);
1454
1455 VPSingleDefRecipe *Res = BuildPerm(&Def);
1456 Res->insertAfter(InsertPos: &Def);
1457 Def.replaceUsesWithIf(New: Res, ShouldReplace: not_equal_to(Arg&: Res));
1458 }
1459 }
1460}
1461
1462// Implements the algorithm described in "Simple and Efficient Construction of
1463// Static Single Assignment Form" by Braun et al.
1464VPValue *vputils::reconstructSSA(VPBasicBlock *VPBB,
1465 DenseMap<VPBasicBlock *, VPValue *> &Defs) {
1466 assert(!Defs.empty() && "Defs shouldn't be empty");
1467 assert(
1468 is_contained(vp_depth_first_shallow(VPBB->getPlan()->getEntry()), VPBB) &&
1469 "VPBB isn't reachable from entry");
1470 if (VPValue *Def = Defs.lookup(Val: VPBB))
1471 return Def;
1472 // If the entry block is reached and there's still no def, then Defs is
1473 // missing a definition that covers this path.
1474 assert(VPBB->getNumPredecessors() && "Not all paths have def");
1475
1476 if (VPBlockBase *Pred = VPBB->getSinglePredecessor())
1477 return reconstructSSA(VPBB: cast<VPBasicBlock>(Val: Pred), Defs);
1478
1479 // Multiple predecessors, create a join.
1480 Type *Ty = Defs.begin()->second->getScalarType();
1481 VPPhi *Phi = VPBuilder(VPBB, VPBB->getFirstNonPhi())
1482 .createScalarPhi(IncomingValues: {}, DL: DebugLoc::getUnknown(), Name: "", Flags: {}, ResultTy: Ty);
1483 Defs[VPBB] = Phi;
1484 for (auto *Pred : VPBB->predecessors())
1485 Phi->addIncoming(IncomingV: reconstructSSA(VPBB: cast<VPBasicBlock>(Val: Pred), Defs));
1486
1487 // Fold away trivial phis.
1488 // TODO: Remove phi users which have become trivial too.
1489 if (all_equal(Range: Phi->incoming_values())) {
1490 VPValue *Common = Phi->getIncomingValue(Idx: 0);
1491 Phi->replaceAllUsesWith(New: Common);
1492 for (auto &[_, V] : Defs)
1493 if (V == Phi)
1494 V = Common;
1495 Defs[VPBB] = Common;
1496 Phi->eraseFromParent();
1497 return Common;
1498 }
1499
1500 return Phi;
1501}
1502