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