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->getTruncInst())
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 Instruction *TruncI, 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 VPSingleDefRecipe *BaseIV =
638 Builder.createDerivedIV(Kind, FPBinOp, Start: StartV, Current: CanonicalIV, Step, Flags);
639
640 // Truncate base induction if needed.
641 Type *ResultTy = BaseIV->getScalarType();
642 if (TruncI) {
643 Type *TruncTy = TruncI->getType();
644 assert(ResultTy->getScalarSizeInBits() > TruncTy->getScalarSizeInBits() &&
645 "Not truncating.");
646 assert(ResultTy->isIntegerTy() && "Truncation requires an integer type");
647 BaseIV = Builder.createScalarCast(Opcode: Instruction::Trunc, Op: BaseIV, ResultTy: TruncTy, DL);
648 ResultTy = TruncTy;
649 }
650
651 // Truncate step if needed.
652 Type *StepTy = Step->getScalarType();
653 if (ResultTy != StepTy) {
654 assert(StepTy->getScalarSizeInBits() > ResultTy->getScalarSizeInBits() &&
655 "Not truncating.");
656 assert(StepTy->isIntegerTy() && "Truncation requires an integer type");
657 auto *VecPreheader =
658 cast<VPBasicBlock>(Val: HeaderVPBB->getSingleHierarchicalPredecessor());
659 VPBuilder::InsertPointGuard Guard(Builder);
660 Builder.setInsertPoint(VecPreheader);
661 Step = Builder.createScalarCast(Opcode: Instruction::Trunc, Op: Step, ResultTy, DL);
662 }
663 return Builder.createScalarIVSteps(InductionOpcode, FPBinOp, IV: BaseIV, Step,
664 VF: &Plan.getVF(), DL);
665}
666
667VPValue *
668vputils::scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV,
669 VPlan &Plan, VPBuilder &Builder) {
670 const InductionDescriptor &ID = PtrIV->getInductionDescriptor();
671 VPIRValue *StartV = Plan.getZero(Ty: ID.getStep()->getType());
672 VPValue *StepV = PtrIV->getOperand(N: 1);
673 VPScalarIVStepsRecipe *Steps = createScalarIVSteps(
674 Plan, Kind: InductionDescriptor::IK_IntInduction, InductionOpcode: Instruction::Add, FPBinOp: nullptr,
675 TruncI: nullptr, StartV, Step: StepV, DL: PtrIV->getDebugLoc(), Builder);
676
677 return Builder.createPtrAdd(Ptr: PtrIV->getStartValue(), Offset: Steps,
678 DL: PtrIV->getDebugLoc(), Name: "next.gep");
679}
680
681bool VPBlockUtils::isHeader(const VPBlockBase *VPB,
682 const VPDominatorTree &VPDT) {
683 auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB);
684 if (!VPBB)
685 return false;
686
687 // If VPBB is in a region R, VPBB is a loop header if R is a loop region with
688 // VPBB as its entry, i.e., free of predecessors.
689 if (auto *R = VPBB->getParent())
690 return !R->isReplicator() && !VPBB->hasPredecessors();
691
692 // A header dominates its second predecessor (the latch), with the other
693 // predecessor being the preheader
694 return VPB->getPredecessors().size() == 2 &&
695 VPDT.dominates(A: VPB, B: VPB->getPredecessors()[1]);
696}
697
698bool VPBlockUtils::isLatch(const VPBlockBase *VPB,
699 const VPDominatorTree &VPDT) {
700 // A latch has a header as its last successor, with its other successors
701 // leaving the loop. A preheader OTOH has a header as its first (and only)
702 // successor.
703 return VPB->getNumSuccessors() >= 2 &&
704 VPBlockUtils::isHeader(VPB: VPB->getSuccessors().back(), VPDT);
705}
706
707std::pair<VPBasicBlock *, VPBasicBlock *>
708VPBlockUtils::getPlainCFGHeaderAndLatch(const VPlan &Plan) {
709 VPBasicBlock *Header = cast<VPBasicBlock>(
710 Val: Plan.getEntry()->getNumSuccessors() == 1
711 ? Plan.getEntry()->getSingleSuccessor()
712 : Plan.getEntry()->getSuccessors()[1]->getSingleSuccessor());
713 assert(Header->getNumPredecessors() == 2 &&
714 "Header must have exactly 2 predecessors");
715 auto *Latch = cast<VPBasicBlock>(Val: Header->getPredecessors()[1]);
716 return {Header, Latch};
717}
718
719VPBasicBlock *VPBlockUtils::getPlainCFGMiddleBlock(const VPlan &Plan) {
720 return cast<VPBasicBlock>(Val: Plan.getScalarPreheader()->getPredecessors()[0]);
721}
722
723VPIRFlags vputils::getFlagsForInduction(const InductionDescriptor &ID,
724 const VPPhi *PhiR) {
725 if (ID.getKind() == InductionDescriptor::IK_FpInduction)
726 return ID.getInductionBinOp()->getFastMathFlags();
727
728 // The flags only bound the induction values if the increment directly
729 // updates PhiR.
730 VPValue *Inc = PhiR->getOperand(N: 1);
731 if (match(V: Inc, P: m_c_Add(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue())))
732 return cast<VPInstruction>(Val: Inc)->getNoWrapFlagsOrNone();
733
734 if (match(V: Inc, P: m_Sub(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue()))) {
735 // The step of a sub induction is negated, so NUW cannot be preserved. NSW
736 // can, if the step is not the signed minimum.
737 ConstantInt *Step = ID.getConstIntStepValue();
738 bool NSW = cast<VPInstruction>(Val: Inc)->getNoWrapFlagsOrNone().HasNSW &&
739 Step && !Step->isMinValue(/*IsSigned=*/true);
740 return VPIRFlags::WrapFlagsTy(/*NUW*/ false, NSW);
741 }
742
743 return VPIRFlags::WrapFlagsTy(false, false);
744}
745
746std::optional<MemoryLocation>
747vputils::getMemoryLocation(const VPRecipeBase &R) {
748 auto *M = dyn_cast<VPIRMetadata>(Val: &R);
749 if (!M)
750 return std::nullopt;
751 MemoryLocation Loc;
752 // Populate noalias metadata from VPIRMetadata.
753 if (MDNode *NoAliasMD = M->getMetadata(Kind: LLVMContext::MD_noalias))
754 Loc.AATags.NoAlias = NoAliasMD;
755 if (MDNode *AliasScopeMD = M->getMetadata(Kind: LLVMContext::MD_alias_scope))
756 Loc.AATags.Scope = AliasScopeMD;
757 return Loc;
758}
759
760VPInstruction *vputils::findCanonicalIVIncrement(VPlan &Plan) {
761 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
762 VPRegionValue *CanIV = LoopRegion->getCanonicalIV();
763 assert(CanIV && "Expected loop region to have a canonical IV");
764
765 VPSymbolicValue &VFxUF = Plan.getVFxUF();
766
767 // Check if \p Step matches the expected increment step, accounting for
768 // materialization of VFxUF and UF.
769 auto IsIncrementStep = [&](VPValue *Step) -> bool {
770 if (!VFxUF.isMaterialized())
771 return Step == &VFxUF;
772
773 VPSymbolicValue &UF = Plan.getUF();
774 if (!UF.isMaterialized())
775 return Step == &UF ||
776 match(V: Step, P: m_c_Mul(Op0: m_Specific(VPV: &Plan.getUF()), Op1: m_VScale()));
777
778 // Alias masking: step is number of active lanes of a dependence mask.
779 if (match(V: Step, P: m_ZExtOrTruncOrSelf(
780 Op0: m_VPInstruction<VPInstruction::NumActiveLanes>())))
781 return true;
782
783 unsigned ConcreteUF = Plan.getConcreteUF();
784 // Fixed VF: step is just the concrete UF.
785 if (match(V: Step, P: m_SpecificInt(V: ConcreteUF)))
786 return true;
787
788 // Scalable VF: step involves VScale.
789 if (ConcreteUF == 1)
790 return match(V: Step, P: m_VScale());
791 if (match(V: Step, P: m_c_Mul(Op0: m_SpecificInt(V: ConcreteUF), Op1: m_VScale())))
792 return true;
793 // mul(VScale, ConcreteUF) may have been simplified to
794 // shl(VScale, log2(ConcreteUF)) when ConcreteUF is a power of 2.
795 return isPowerOf2_32(Value: ConcreteUF) &&
796 match(V: Step, P: m_Shl(Op0: m_VScale(), Op1: m_SpecificInt(V: Log2_32(Value: ConcreteUF))));
797 };
798
799 VPInstruction *Increment = nullptr;
800 for (VPUser *U : CanIV->users()) {
801 VPValue *Step;
802 if (isa<VPInstruction>(Val: U) &&
803 match(U, P: m_c_Add(Op0: m_Specific(VPV: CanIV), Op1: m_VPValue(V&: Step))) &&
804 IsIncrementStep(Step)) {
805 assert(!Increment && "There must be a unique increment");
806 Increment = cast<VPInstruction>(Val: U);
807 }
808 }
809
810 assert((!VFxUF.isMaterialized() || Increment) &&
811 "After materializing VFxUF, an increment must exist");
812 assert((!Increment ||
813 LoopRegion->hasCanonicalIVNUW() == Increment->hasNoUnsignedWrap()) &&
814 "NUW flag in region and increment must match");
815 return Increment;
816}
817
818/// Find the ComputeReductionResult recipe for \p PhiR, looking through selects
819/// inserted for predicated reductions or tail folding.
820VPInstruction *vputils::findComputeReductionResult(VPReductionPHIRecipe *PhiR) {
821 VPValue *BackedgeVal = PhiR->getBackedgeValue();
822 if (auto *Res =
823 findUserOf<VPInstruction::ComputeReductionResult>(V: BackedgeVal))
824 return Res;
825
826 // Look through selects inserted for tail folding or predicated reductions.
827 VPRecipeBase *SelR =
828 findUserOf(V: BackedgeVal, P: m_Select(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue()));
829 if (!SelR)
830 return nullptr;
831 return findUserOf<VPInstruction::ComputeReductionResult>(
832 V: cast<VPSingleDefRecipe>(Val: SelR));
833}
834
835bool vputils::isUsedByLoadStoreAddress(const VPValue *V) {
836 SmallPtrSet<const VPValue *, 4> Seen;
837 SmallVector<const VPValue *> WorkList = {V};
838
839 while (!WorkList.empty()) {
840 const VPValue *Cur = WorkList.pop_back_val();
841 if (!Seen.insert(Ptr: Cur).second)
842 continue;
843
844 auto *Blend = dyn_cast<VPBlendRecipe>(Val: Cur);
845 // Skip blends that use V only through a compare by checking if any incoming
846 // value was already visited.
847 if (Blend && none_of(Range: seq<unsigned>(Begin: 0, End: Blend->getNumIncomingValues()),
848 P: [&](unsigned I) {
849 return Seen.contains(Ptr: Blend->getIncomingValue(Idx: I));
850 }))
851 continue;
852
853 for (VPUser *U : Cur->users()) {
854 if (auto *InterleaveR = dyn_cast<VPInterleaveBase>(Val: U))
855 if (InterleaveR->getAddr() == Cur)
856 return true;
857 // Cur is used as the pointer of a (possibly masked) load (operand 0) or
858 // store (operand 1).
859 if (match(U, P: m_CombineOr(Ps: m_Unary<Instruction::Load>(Op0: m_Specific(VPV: Cur)),
860 Ps: m_Binary<Instruction::Store>(Op0: m_VPValue(),
861 Op1: m_Specific(VPV: Cur)))))
862 return true;
863 if (auto *MemR = dyn_cast<VPWidenMemoryRecipe>(Val: cast<VPRecipeBase>(Val: U))) {
864 if (MemR->getAddr() == Cur && MemR->isConsecutive())
865 return true;
866 }
867 }
868
869 // The legacy cost model only supports scalarization loads/stores with phi
870 // addresses, if the phi is directly used as load/store address. Don't
871 // traverse further for Blends.
872 if (Blend)
873 continue;
874
875 // Only traverse further through users that also define a value (and can
876 // thus have their own users walked). Skip when Cur is only used as mask ,
877 // as well as loads: a loaded value does not depend on the load's operand.
878 for (VPUser *U : Cur->users()) {
879 auto *VPI = dyn_cast<VPInstruction>(Val: U);
880 if (VPI && VPI->getMask() == Cur &&
881 none_of(Range: VPI->operandsWithoutMask(), P: equal_to(Arg&: Cur)))
882 continue;
883 if (match(U, P: m_VPInstruction<Instruction::Load>()))
884 continue;
885 if (auto *SDR = dyn_cast<VPSingleDefRecipe>(Val: U))
886 WorkList.push_back(Elt: SDR);
887 }
888 }
889 return false;
890}
891
892/// Try to find a loop-invariant IR value for \p S in the plan's entry block
893/// that can be reused. Returns the corresponding live-in VPValue, or nullptr
894/// if no reusable IR value is found.
895VPValue *VPSCEVExpander::tryToReuseIRValue(const SCEV *S) {
896 if (isa<SCEVConstant, SCEVUnknown>(Val: S))
897 return nullptr;
898 VPlan &Plan = Builder.getPlan();
899 BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock();
900 for (Value *V : SE.getSCEVValues(S)) {
901 // Only reuse instructions in the plan's entry block, or, when a
902 // DominatorTree is available, any instruction that dominates it.
903 // Instructions in sibling branches may not dominate the entry block.
904 auto *I = dyn_cast<Instruction>(Val: V);
905 if (!I)
906 return Plan.getOrAddLiveIn(V);
907 if (!SE.DT.dominates(A: I->getParent(), B: PH))
908 continue;
909 Loop *IL = SE.LI.getLoopFor(BB: I->getParent());
910 if (IL && !IL->contains(BB: PH))
911 continue;
912 SmallVector<Instruction *> DropPoisonGeneratingInsts;
913 if (!SE.canReuseInstruction(S, I, DropPoisonGeneratingInsts))
914 continue;
915 for (Instruction *DropI : DropPoisonGeneratingInsts)
916 SCEVExpander::dropPoisonGeneratingAnnotationsAndReinfer(SE, I: DropI);
917 return Plan.getOrAddLiveIn(V);
918 }
919 return nullptr;
920}
921
922VPValue *VPSCEVExpander::expand(const SCEV *S) {
923 if (VPValue *V = tryToReuseIRValue(S))
924 return V;
925
926 switch (S->getSCEVType()) {
927 case scConstant:
928 return Builder.getPlan().getOrAddLiveIn(V: cast<SCEVConstant>(Val: S)->getValue());
929 case scUnknown:
930 return Builder.getPlan().getOrAddLiveIn(V: cast<SCEVUnknown>(Val: S)->getValue());
931 case scVScale:
932 return Builder.createVScale(ResultTy: S->getType(), DL);
933 case scAddExpr: {
934 auto *AddE = cast<SCEVAddExpr>(Val: S);
935 VPIRFlags::WrapFlagsTy WrapFlags(AddE->hasNoUnsignedWrap(),
936 AddE->hasNoSignedWrap());
937
938 // Expand pointer SCEVAddExpr as a ptradd of the pointer base and the
939 // integer offset, matching SCEVExpander.
940 if (S->getType()->isPointerTy()) {
941 VPValue *Base = expand(S: SE.getPointerBase(V: S));
942 VPValue *Offset = expand(S: SE.removePointerBase(S));
943 GEPNoWrapFlags GEPFlags = WrapFlags.HasNUW
944 ? GEPNoWrapFlags::noUnsignedWrap()
945 : GEPNoWrapFlags::none();
946 return Builder.createNoWrapPtrAdd(Ptr: Base, Offset, GEPFlags, DL);
947 }
948
949 // Non-constant-negative add operands are expanded negated and subtracted
950 // from the running result below, instead of being negated and added.
951 auto UseSubtract = [](const SCEV *Op) {
952 return Op->isNonConstantNegative();
953 };
954 // Iterate in reverse so that constants are emitted last, and move the
955 // subtracted operands last, matching SCEVExpander's LoopCompare, so that
956 // they don't start the running result.
957 SmallVector<const SCEV *, 2> SCEVOps(reverse(C: AddE->operands()));
958 stable_sort(Range&: SCEVOps, C: [&](const SCEV *L, const SCEV *R) {
959 return !UseSubtract(L) && UseSubtract(R);
960 });
961 SmallVector<VPValue *, 2> Ops;
962 for (const SCEV *Op : SCEVOps) {
963 // The first operand starts the result, so it is never subtracted.
964 bool Negate = !Ops.empty() && UseSubtract(Op);
965 Ops.push_back(Elt: expand(S: Negate ? SE.getNegativeSCEV(V: Op) : Op));
966 }
967 VPValue *Result = Ops.front();
968 for (auto [Op, OpV] : drop_begin(RangeOrContainer: zip_equal(t&: SCEVOps, u&: Ops))) {
969 if (UseSubtract(Op)) {
970 // Result + (-Op) == Result - Op, which saves the multiply for the
971 // negation. NSW only transfers if negating Op cannot overflow, see
972 // ScalarEvolution::getMinusSCEV.
973 bool HasNSW =
974 WrapFlags.HasNSW && !SE.getSignedRangeMin(S: Op).isMinSignedValue();
975 Result = Builder.createOverflowingOp(Opcode: Instruction::Sub, Operands: {Result, OpV},
976 WrapFlags: {/*HasNUW=*/false, HasNSW}, DL);
977 continue;
978 }
979 Result = Builder.createOverflowingOp(Opcode: Instruction::Add, Operands: {Result, OpV},
980 WrapFlags, DL);
981 }
982 return Result;
983 }
984 case scMulExpr: {
985 auto *MulE = cast<SCEVMulExpr>(Val: S);
986 VPIRFlags::WrapFlagsTy WrapFlags(MulE->hasNoUnsignedWrap(),
987 MulE->hasNoSignedWrap());
988 SmallVector<VPValue *, 2> Ops;
989 for (const SCEV *Op : reverse(C: MulE->operands()))
990 Ops.push_back(Elt: expand(S: Op));
991 VPValue *Result = Ops.front();
992 for (VPValue *OpV : drop_begin(RangeOrContainer&: Ops)) {
993 Result = Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {Result, OpV},
994 WrapFlags, DL);
995 }
996 return Result;
997 }
998 case scUDivExpr: {
999 auto *UDiv = cast<SCEVUDivExpr>(Val: S);
1000 VPValue *LHS = expand(S: UDiv->getLHS());
1001 const SCEV *RHSExpr = UDiv->getRHS();
1002 VPValue *RHS = expand(S: RHSExpr);
1003 if (SafeUDivMode) {
1004 // Make sure the UDiv's divisor is guaranteed to not be zero/poison, to
1005 // avoid UB.
1006 Type *Ty = UDiv->getType();
1007 bool GuaranteedNotPoison =
1008 ScalarEvolution::isGuaranteedNotToBePoison(Op: RHSExpr);
1009 if (!GuaranteedNotPoison)
1010 RHS = Builder.createFreeze(Op: RHS, DL);
1011 if (!SE.isKnownNonZero(S: RHSExpr) || !GuaranteedNotPoison)
1012 RHS = Builder.createScalarIntrinsic(
1013 IntrinsicID: Intrinsic::umax, Operands: {RHS, Builder.getPlan().getConstantInt(Ty, Val: 1)}, ResultTy: Ty,
1014 DL);
1015 }
1016 return Builder.createNaryOp(Opcode: Instruction::UDiv, Operands: {LHS, RHS},
1017 Flags: VPIRFlags::getDefaultFlags(Opcode: Instruction::UDiv),
1018 DL);
1019 }
1020 case scTruncate:
1021 case scZeroExtend:
1022 case scSignExtend:
1023 case scPtrToAddr: {
1024 auto *Cast = cast<SCEVCastExpr>(Val: S);
1025 VPValue *Op = expand(S: Cast->getOperand());
1026 Instruction::CastOps Opcode;
1027 switch (S->getSCEVType()) {
1028 case scTruncate:
1029 Opcode = Instruction::Trunc;
1030 break;
1031 case scZeroExtend:
1032 Opcode = Instruction::ZExt;
1033 break;
1034 case scSignExtend:
1035 Opcode = Instruction::SExt;
1036 break;
1037 case scPtrToAddr:
1038 Opcode = Instruction::PtrToAddr;
1039 break;
1040 default:
1041 llvm_unreachable("Unhandled cast SCEV");
1042 }
1043
1044 // When expanding ptrtoaddr, first check if there's an existing ptrtoint we
1045 // can reuse.
1046 if (Opcode == Instruction::PtrToAddr) {
1047 VPlan &Plan = Builder.getPlan();
1048 BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock();
1049 if (auto *IRV = dyn_cast<VPIRValue>(Val: Op)) {
1050 if (CastInst *CI = SCEVExpander::findReusableCastForPtrToAddr(
1051 PtrOp: IRV->getValue(), Ty: S->getType(), DL: PH->getDataLayout(),
1052 Dominates: [&](const CastInst *CI) {
1053 return SE.DT.dominates(A: CI->getParent(), B: PH);
1054 }))
1055 return Plan.getOrAddLiveIn(V: CI);
1056 }
1057 }
1058
1059 std::optional<VPIRFlags> Flags;
1060 if (Opcode == Instruction::ZExt)
1061 Flags =
1062 VPIRFlags::NonNegFlagsTy(SE.isKnownNonNegative(S: Cast->getOperand()));
1063
1064 return Builder.createScalarCast(Opcode, Op, ResultTy: S->getType(), DL, Flags);
1065 }
1066 case scUMaxExpr:
1067 case scSMaxExpr:
1068 case scUMinExpr:
1069 case scSMinExpr:
1070 case scSequentialUMinExpr: {
1071 auto *MinMax = cast<SCEVNAryExpr>(Val: S);
1072 Intrinsic::ID IntrinsicID;
1073 switch (S->getSCEVType()) {
1074 case scUMaxExpr:
1075 IntrinsicID = Intrinsic::umax;
1076 break;
1077 case scSMaxExpr:
1078 IntrinsicID = Intrinsic::smax;
1079 break;
1080 case scUMinExpr:
1081 case scSequentialUMinExpr:
1082 IntrinsicID = Intrinsic::umin;
1083 break;
1084 case scSMinExpr:
1085 IntrinsicID = Intrinsic::smin;
1086 break;
1087 default:
1088 llvm_unreachable("Unexpected min/max SCEV type");
1089 }
1090 // Chain operands in reverse order matching SCEVExpander's expansion of
1091 // min/max expressions. In SafeUDivMode freeze expansion results of operands
1092 // other than the first for sequential UMins, to avoid short-circuiting
1093 // divide-by-0/poison.
1094 bool IsSequential = S->getSCEVType() == scSequentialUMinExpr;
1095 Type *ResultTy = MinMax->getType();
1096 bool PrevSafeMode = SafeUDivMode;
1097 SmallVector<VPValue *, 2> Ops;
1098 for (const SCEV *SCEVOp : reverse(C: MinMax->operands())) {
1099 bool MayShortCircuit =
1100 IsSequential && Ops.size() != MinMax->getNumOperands() - 1;
1101 SafeUDivMode = MayShortCircuit || PrevSafeMode;
1102 VPValue *OpV = expand(S: SCEVOp);
1103 SafeUDivMode = PrevSafeMode;
1104 if (MayShortCircuit)
1105 OpV = Builder.createFreeze(Op: OpV, DL);
1106 Ops.push_back(Elt: OpV);
1107 }
1108 VPValue *Result = Ops.front();
1109 for (VPValue *Op : drop_begin(RangeOrContainer&: Ops)) {
1110 if (!ResultTy->isPointerTy()) {
1111 Result = Builder.createScalarIntrinsic(IntrinsicID, Operands: {Result, Op},
1112 ResultTy, DL);
1113 continue;
1114 }
1115 // The min/max intrinsics don't support pointer operands, so expand
1116 // pointer-typed min/max as cmp + select, matching SCEVExpander.
1117 VPValue *Cmp = Builder.createICmp(
1118 Pred: MinMaxIntrinsic::getPredicate(ID: IntrinsicID), A: Result, B: Op, DL);
1119 Result = Builder.createSelect(Cond: Cmp, TrueVal: Result, FalseVal: Op, DL);
1120 Function &F = *Builder.getPlan().getIRFunction();
1121 if (MDNode *MD =
1122 getExplicitlyUnknownBranchWeightsIfProfiled(F, PassName: "scev-expander"))
1123 cast<VPInstruction>(Val: Result)->setMetadata(Kind: LLVMContext::MD_prof, Node: MD);
1124 }
1125 return Result;
1126 }
1127 case scAddRecExpr: {
1128 auto *AR = cast<SCEVAddRecExpr>(Val: S);
1129 VPlan &Plan = Builder.getPlan();
1130 BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock();
1131 assert(SE.DT.dominates(AR->getLoop()->getHeader(), PH) &&
1132 "can only expand AddRecs for loops outside VPlan's scope");
1133
1134 Type *Ty = AR->getType();
1135 if (auto [LCSSAPhi, Diff] = SCEVExpander::findReusableLCSSAPhi(SE, S: AR, InsertBB: PH);
1136 LCSSAPhi) {
1137 VPValue *DiffV = expand(S: Diff);
1138 VPValue *BaseV = Plan.getOrAddLiveIn(V: LCSSAPhi);
1139 if (LCSSAPhi->getType()->isPointerTy()) {
1140 if (Ty->isPointerTy())
1141 return Builder.createPtrAdd(Ptr: BaseV, Offset: DiffV, DL);
1142 BaseV = Builder.createScalarCast(Opcode: Instruction::PtrToAddr, Op: BaseV, ResultTy: Ty, DL);
1143 }
1144 return Builder.createAdd(LHS: BaseV, RHS: DiffV, DL);
1145 }
1146
1147 // Try to expand AR by re-using an existing canonical IV in the Plan's
1148 // entry. A canonical IV must be affine and integer typed.
1149 if (!AR->isAffine() || !AR->getType()->isIntegerTy())
1150 return vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: AR);
1151 auto FoundCanIV =
1152 find_if(Range: Plan.getEntry()->phis(), P: [&](const VPRecipeBase &R) {
1153 if (!SE.isSCEVable(Ty: cast<VPIRPhi>(Val: R).getIRPhi().getType()))
1154 return false;
1155 const SCEV *Candidate = SE.getSCEV(V: &cast<VPIRPhi>(Val: R).getIRPhi());
1156 return match(S: Candidate,
1157 P: m_scev_AffineAddRec(Op0: m_scev_Zero(), Op1: m_scev_One(),
1158 L: m_SpecificLoop(L: AR->getLoop()))) &&
1159 Candidate->getType() == AR->getType();
1160 });
1161 if (FoundCanIV == Plan.getEntry()->phis().end())
1162 return vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: AR);
1163
1164 // {Start, +, Step} --> Start + IV * Step, since the AddRec is affine.
1165 // Compute Offset = IV * Step.
1166 VPValue *Start = expand(S: AR->getStart());
1167 Value *CanonicalIV = &cast<VPIRPhi>(Val&: FoundCanIV)->getIRPhi();
1168 VPValue *Offset = expand(
1169 S: SE.getMulExpr(LHS: SE.getUnknown(V: CanonicalIV), RHS: AR->getStepRecurrence(SE)));
1170
1171 // Compute Start + Offset with nuw from the AddRec.
1172 return Builder.createAdd(LHS: Start, RHS: Offset, DL, Name: "",
1173 WrapFlags: {AR->hasNoUnsignedWrap(), false});
1174 }
1175 case scCouldNotCompute:
1176 llvm_unreachable("Attempt to expand a SCEVCouldNotCompute");
1177 }
1178 llvm_unreachable("Unknown SCEV kind!");
1179}
1180
1181bool vputils::isDeadRecipe(VPRecipeBase &R) {
1182 // Do remove conditional assume instructions as their conditions may be
1183 // flattened.
1184 auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R);
1185 bool IsConditionalAssume = RepR && RepR->isPredicated() &&
1186 match(V: RepR, P: m_Intrinsic<Intrinsic::assume>());
1187 if (IsConditionalAssume)
1188 return true;
1189
1190 if (R.mayHaveSideEffects())
1191 return false;
1192
1193 // Forbid removing trip-count expressions.
1194 if (isa<VPExpandSCEVRecipe>(Val: R) &&
1195 R.getVPSingleValue() == R.getParent()->getPlan()->getTripCount())
1196 return false;
1197
1198 // Recipe is dead if no user keeps the recipe alive.
1199 return all_of(Range: R.definedValues(), P: [](VPValue *V) { return V->user_empty(); });
1200}
1201
1202void vputils::recursivelyDeleteDeadRecipes(VPValue *V) {
1203 SmallVector<VPValue *> WorkList;
1204 SmallPtrSet<VPValue *, 8> Seen;
1205 WorkList.push_back(Elt: V);
1206
1207 while (!WorkList.empty()) {
1208 VPValue *Cur = WorkList.pop_back_val();
1209 if (!Seen.insert(Ptr: Cur).second)
1210 continue;
1211 VPRecipeBase *R = Cur->getDefiningRecipe();
1212 if (!R)
1213 continue;
1214 if (!isDeadRecipe(R&: *R))
1215 continue;
1216 append_range(C&: WorkList, R: R->operands());
1217 R->eraseFromParent();
1218 }
1219}
1220
1221SmallVector<VPUser *> vputils::collectUsersRecursively(VPValue *V) {
1222 SetVector<VPUser *> Users(llvm::from_range, V->users());
1223 for (unsigned I = 0; I != Users.size(); ++I) {
1224 VPRecipeBase *Cur = cast<VPRecipeBase>(Val: Users[I]);
1225 for (VPValue *V : Cur->definedValues())
1226 Users.insert_range(R: V->users());
1227 }
1228 return Users.takeVector();
1229}
1230
1231/// Returns \p Num / \p Denom as a BranchProbability, clamped so a ratio that is
1232/// neither zero nor one does not round to zero or one. BlockFrequencyInfo also
1233/// keeps a zero-weight edge distinguishable from an unreachable one.
1234static BranchProbability getBranchProbabilityKeepingPartial(uint64_t Num,
1235 uint64_t Denom) {
1236 BranchProbability P = BranchProbability::getBranchProbability(Numerator: Num, Denominator: Denom);
1237 if (Num == 0 || Num == Denom)
1238 return P;
1239 return BranchProbability::getRaw(N: std::clamp(
1240 val: P.getNumerator(), lo: 1u, hi: BranchProbability::getDenominator() - 1));
1241}
1242
1243BranchProbability vputils::getExecutionProbability(BlockFrequency Freq) {
1244 return getBranchProbabilityKeepingPartial(
1245 Num: Freq.getFrequency(),
1246 Denom: BlockFrequencyInfoImplBase::BlockMass::getFull().getMass());
1247}
1248
1249/// Returns the probability of each successor edge of \p VPBB, computed via
1250/// BranchProbabilityInfo::getEdgeProbabilitiesFromWeights from the branch
1251/// weights recorded on its terminator, or std::nullopt if not available.
1252static std::optional<SmallVector<BranchProbability>>
1253getSuccessorProbabilities(const VPBasicBlock *VPBB) {
1254 // With a single successor the edge is always taken and needs no weights.
1255 if (VPBB->getSingleSuccessor())
1256 return SmallVector<BranchProbability>{BranchProbability::getOne()};
1257
1258 SmallVector<uint32_t> Weights;
1259 auto *Term = dyn_cast_if_present<VPInstruction>(Val: VPBB->getTerminator());
1260 if (!Term || !extractBranchWeights(ProfileData: Term->getBranchWeights(), Weights) ||
1261 Weights.size() != VPBB->getNumSuccessors())
1262 return std::nullopt;
1263 return BranchProbabilityInfo::getEdgeProbabilitiesFromWeights(Weights);
1264}
1265
1266DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>>
1267vputils::computeExecutionFrequencies(ArrayRef<VPBasicBlock *> Blocks) {
1268 using BFIBase = BlockFrequencyInfoImplBase;
1269 assert(!Blocks.empty() && "expected at least the header block");
1270 // Distribute the header's frequency using BFI. Nodes for blocks are numbered
1271 // in reverse post-order. Edges leaving Blocks, i.e. a plain CFG's edges to
1272 // the middle block or to an exit block, exit to a node outside the loop.
1273 BFIBase BFI;
1274 BFIBase::BlockNode Header(0), Outside(Blocks.size());
1275 BFIBase::LoopData &Loop = BFI.Loops.emplace_back(args: nullptr, args&: Header);
1276 DenseMap<const VPBlockBase *, BFIBase::BlockNode> Nodes;
1277 for (auto [Idx, VPBB] : enumerate(First&: Blocks)) {
1278 Nodes[VPBB] = BFIBase::BlockNode(Idx);
1279 BFI.Working.emplace_back(args: BFIBase::BlockNode(Idx)).Loop = &Loop;
1280 }
1281 BFI.Working.emplace_back(args&: Outside);
1282 BFI.Working[Header.Index].getMass() = BFIBase::BlockMass::getFull();
1283
1284 // Keep track nodes reached via an edge without branch weighs or with
1285 // estimated ones
1286 SmallVector<bool> IsUnknown(Blocks.size()), IsEstimated(Blocks.size());
1287 for (auto [Idx, VPBB] : enumerate(First&: Blocks)) {
1288 BFIBase::BlockNode Node(Idx);
1289 auto Probs = getSuccessorProbabilities(VPBB);
1290 auto *Term = dyn_cast_if_present<VPInstruction>(Val: VPBB->getTerminator());
1291 bool TermIsEstimated = Term && Term->hasEstimatedBranchWeights();
1292 BFIBase::Distribution Dist;
1293 for (auto [SuccIdx, Succ] : enumerate(First&: VPBB->getSuccessors())) {
1294 BFIBase::BlockNode SuccNode = Nodes.lookup_or(Val: Succ, Default&: Outside);
1295 if (SuccNode != Header && SuccNode != Outside) {
1296 IsUnknown[SuccNode.Index] |= IsUnknown[Idx] || !Probs;
1297 IsEstimated[SuccNode.Index] |= IsEstimated[Idx] || TermIsEstimated;
1298 }
1299 if (Probs)
1300 BFI.addToDist(Dist, OuterLoop: &Loop, Pred: Node, Succ: SuccNode,
1301 Weight: getWeightFromBranchProb(Prob: (*Probs)[SuccIdx]));
1302 }
1303 if (Probs)
1304 BFI.distributeMass(Source: Node, OuterLoop: &Loop, Dist);
1305 }
1306
1307 // Round frequencies up to at least 1, so all edges are reached with a
1308 // non-zero frequency, to distinguish rarely executed blocks from unreachable
1309 // ones. blocks distinguishable from unreachable ones.
1310 DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>>
1311 Frequencies;
1312 for (auto [Idx, VPBB] : enumerate(First&: Blocks)) {
1313 std::optional<VPExecutionFrequency> &Freq = Frequencies[VPBB];
1314 if (IsUnknown[Idx])
1315 continue;
1316 uint64_t Mass = BFI.Working[Idx].getMass().getMass();
1317 Freq.emplace(args: BlockFrequency(std::max<uint64_t>(a: Mass, b: 1)), args&: IsEstimated[Idx]);
1318 }
1319 return Frequencies;
1320}
1321
1322VPIRValue *vputils::tryToFoldLiveIns(VPSingleDefRecipe &R,
1323 ArrayRef<VPValue *> Operands,
1324 const DataLayout &DL) {
1325 auto OpcodeOrIID = getOpcodeOrIntrinsicID(V: &R);
1326 if (!OpcodeOrIID)
1327 return nullptr;
1328
1329 SmallVector<Value *, 4> Ops;
1330 for (VPValue *Op : Operands) {
1331 VPValue *Candidate = Op;
1332 match(V: Op, P: m_Broadcast(Op0: m_VPValue(V&: Candidate)));
1333 if (!match(V: Candidate, P: m_LiveIn()))
1334 return nullptr;
1335 Value *V = Candidate->getUnderlyingValue();
1336 if (!V)
1337 return nullptr;
1338 Ops.push_back(Elt: V);
1339 }
1340
1341 VPlan &Plan = *R.getParent()->getPlan();
1342 auto FoldToIRValue = [&]() -> Value * {
1343 InstSimplifyFolder Folder(DL);
1344 if (OpcodeOrIID->first) {
1345 // VPInstructions store the called intrinsic as last operand.
1346 if (isa<VPInstruction>(Val: R))
1347 Ops.pop_back();
1348
1349 auto *RFlags = dyn_cast<VPRecipeWithIRFlags>(Val: &R);
1350 return Folder.FoldIntrinsic(ID: OpcodeOrIID->second, Ops, Ty: R.getScalarType(),
1351 FMF: RFlags ? RFlags->getFastMathFlagsOrNone()
1352 : FastMathFlags());
1353 }
1354 unsigned Opcode = OpcodeOrIID->second;
1355 if (Instruction::isBinaryOp(Opcode))
1356 return Folder.FoldBinOp(Opc: static_cast<Instruction::BinaryOps>(Opcode),
1357 LHS: Ops[0], RHS: Ops[1]);
1358 if (Instruction::isCast(Opcode))
1359 return Folder.FoldCast(Op: static_cast<Instruction::CastOps>(Opcode), V: Ops[0],
1360 DestTy: R.getVPSingleValue()->getScalarType());
1361 switch (Opcode) {
1362 case VPInstruction::Not:
1363 return Folder.FoldBinOp(Opc: Instruction::BinaryOps::Xor, LHS: Ops[0],
1364 RHS: Constant::getAllOnesValue(Ty: Ops[0]->getType()));
1365 case Instruction::Select:
1366 return Folder.FoldSelect(C: Ops[0], True: Ops[1], False: Ops[2]);
1367 case Instruction::ICmp:
1368 case Instruction::FCmp:
1369 return Folder.FoldCmp(P: cast<VPRecipeWithIRFlags>(Val&: R).getPredicate(), LHS: Ops[0],
1370 RHS: Ops[1]);
1371 case Instruction::GetElementPtr: {
1372 auto &RFlags = cast<VPRecipeWithIRFlags>(Val&: R);
1373 auto *GEP = cast<GetElementPtrInst>(Val: RFlags.getUnderlyingInstr());
1374 return Folder.FoldGEP(DL, Ty: GEP->getSourceElementType(), Ptr: Ops[0],
1375 IdxList: drop_begin(RangeOrContainer&: Ops), NW: RFlags.getGEPNoWrapFlags());
1376 }
1377 case VPInstruction::PtrAdd:
1378 case VPInstruction::WidePtrAdd:
1379 return Folder.FoldGEP(DL, Ty: IntegerType::getInt8Ty(C&: Plan.getContext()),
1380 Ptr: Ops[0], IdxList: Ops[1],
1381 NW: cast<VPRecipeWithIRFlags>(Val&: R).getGEPNoWrapFlags());
1382 // An extract of a live-in is an extract of a broadcast, so return the
1383 // broadcasted element.
1384 case Instruction::ExtractElement:
1385 assert(!Ops[0]->getType()->isVectorTy() && "Live-ins should be scalar");
1386 return Ops[0];
1387 case VPInstruction::ActiveLaneMask:
1388 case VPInstruction::WideActiveLaneMask: {
1389 uint64_t Multiplier = 1;
1390 if (Opcode == VPInstruction::WideActiveLaneMask) {
1391 // Optimizing WideALM can only happen after the Plan is unrolled.
1392 if (!Plan.isUnrolled())
1393 return nullptr;
1394 Multiplier = cast<ConstantInt>(Val: Ops[2])->getZExtValue();
1395 Ops.pop_back();
1396 }
1397
1398 // We rely on the fact that different VPlans are created for the
1399 // fixed-vector and scalable-vector cases.
1400 ElementCount MaxVF =
1401 *max_element(Range: Plan.vectorFactors(), C: ElementCount::isKnownLT) *
1402 Multiplier;
1403
1404 Type *I1Ty = IntegerType::getInt1Ty(C&: Plan.getContext());
1405 if (auto *C = dyn_cast_if_present<Constant>(Val: Folder.FoldIntrinsic(
1406 ID: Intrinsic::get_active_lane_mask, Ops,
1407 Ty: VectorType::get(ElementType: I1Ty, EC: MaxVF), FMF: {}, CtxF: Plan.getIRFunction()))) {
1408 // We cannot handle vector constants that are not all-true or all-false,
1409 // because they would not be collapsable to a scalar constant, that
1410 // would be necessary for live-in simplification.
1411 if (C->isOneValue())
1412 return ConstantInt::getTrue(Ty: I1Ty);
1413 if (C->isNullValue())
1414 return ConstantInt::getFalse(Ty: I1Ty);
1415 }
1416 }
1417 }
1418 return nullptr;
1419 };
1420
1421 if (Value *V = FoldToIRValue())
1422 return Plan.getOrAddLiveIn(V);
1423 return nullptr;
1424}
1425
1426void vputils::detail::pullOutPermutationsImpl(
1427 VPlan &Plan, function_ref<VPValue *(VPValue *Op)> MatchPerm,
1428 function_ref<VPSingleDefRecipe *(VPSingleDefRecipe *X)> BuildPerm) {
1429 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
1430 Range: vp_depth_first_deep(G: Plan.getEntry()))) {
1431 for (VPSingleDefRecipe &Def :
1432 make_early_inc_range(Range: make_isa_range<VPSingleDefRecipe>(Range&: *VPBB))) {
1433 if (!isElementwise(V: &Def))
1434 continue;
1435
1436 // At least one of the ops must be a permutation.
1437 if (none_of(Range: Def.operands(), P: MatchPerm))
1438 continue;
1439
1440 // All operands must be a single-use permutation or a live in (splat).
1441 if (!all_of(Range: Def.operands(), P: [&MatchPerm](VPValue *Op) {
1442 return (Op->hasOneUse() && MatchPerm(Op)) || match(V: Op, P: m_LiveIn());
1443 }))
1444 continue;
1445
1446 // Remove the inner permutations.
1447 for (unsigned I = 0, E = Def.getNumOperands(); I != E; ++I)
1448 if (VPValue *X = MatchPerm(Def.getOperand(N: I)))
1449 Def.setOperand(I, New: X);
1450
1451 VPSingleDefRecipe *Res = BuildPerm(&Def);
1452 Res->insertAfter(InsertPos: &Def);
1453 Def.replaceUsesWithIf(New: Res, ShouldReplace: [&Res](VPUser &U) { return &U != Res; });
1454 }
1455 }
1456}
1457
1458// Implements the algorithm described in "Simple and Efficient Construction of
1459// Static Single Assignment Form" by Braun et al.
1460VPValue *vputils::reconstructSSA(VPBasicBlock *VPBB,
1461 DenseMap<VPBasicBlock *, VPValue *> &Defs) {
1462 assert(!Defs.empty() && "Defs shouldn't be empty");
1463 assert(
1464 is_contained(vp_depth_first_shallow(VPBB->getPlan()->getEntry()), VPBB) &&
1465 "VPBB isn't reachable from entry");
1466 if (VPValue *Def = Defs.lookup(Val: VPBB))
1467 return Def;
1468 // If the entry block is reached and there's still no def, then Defs is
1469 // missing a definition that covers this path.
1470 assert(VPBB->getNumPredecessors() && "Not all paths have def");
1471
1472 if (VPBlockBase *Pred = VPBB->getSinglePredecessor())
1473 return reconstructSSA(VPBB: cast<VPBasicBlock>(Val: Pred), Defs);
1474
1475 // Multiple predecessors, create a join.
1476 Type *Ty = Defs.begin()->second->getScalarType();
1477 VPPhi *Phi = VPBuilder(VPBB, VPBB->getFirstNonPhi())
1478 .createScalarPhi(IncomingValues: {}, DL: DebugLoc::getUnknown(), Name: "", Flags: {}, ResultTy: Ty);
1479 Defs[VPBB] = Phi;
1480 for (auto *Pred : VPBB->predecessors())
1481 Phi->addIncoming(IncomingV: reconstructSSA(VPBB: cast<VPBasicBlock>(Val: Pred), Defs));
1482
1483 // Fold away trivial phis.
1484 // TODO: Remove phi users which have become trivial too.
1485 if (all_equal(Range: Phi->incoming_values())) {
1486 VPValue *Common = Phi->getIncomingValue(Idx: 0);
1487 Phi->replaceAllUsesWith(New: Common);
1488 for (auto &[_, V] : Defs)
1489 if (V == Phi)
1490 V = Common;
1491 Defs[VPBB] = Common;
1492 Phi->eraseFromParent();
1493 return Common;
1494 }
1495
1496 return Phi;
1497}
1498