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