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/InstSimplifyFolder.h"
18#include "llvm/Analysis/MemoryLocation.h"
19#include "llvm/Analysis/ScalarEvolutionExpressions.h"
20#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
21#include "llvm/IR/Dominators.h"
22#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
23
24using namespace llvm;
25using namespace llvm::VPlanPatternMatch;
26using namespace llvm::SCEVPatternMatch;
27
28bool vputils::onlyFirstLaneUsed(const VPValue *Def) {
29 return all_of(Range: Def->users(),
30 P: [Def](const VPUser *U) { return U->usesFirstLaneOnly(Op: Def); });
31}
32
33bool vputils::onlyFirstPartUsed(const VPValue *Def) {
34 return all_of(Range: Def->users(),
35 P: [Def](const VPUser *U) { return U->usesFirstPartOnly(Op: Def); });
36}
37
38bool vputils::onlyScalarValuesUsed(const VPValue *Def) {
39 return all_of(Range: Def->users(),
40 P: [Def](const VPUser *U) { return U->usesScalars(Op: Def); });
41}
42
43VPValue *vputils::getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr) {
44 if (auto *E = dyn_cast<SCEVConstant>(Val: Expr))
45 return Plan.getOrAddLiveIn(V: E->getValue());
46 // Skip SCEV expansion if Expr is a SCEVUnknown wrapping a non-instruction
47 // value. Otherwise the value may be defined in a loop and using it directly
48 // will break LCSSA form. The SCEV expansion takes care of preserving LCSSA
49 // form.
50 auto *U = dyn_cast<SCEVUnknown>(Val: Expr);
51 if (U && !isa<Instruction>(Val: U->getValue()))
52 return Plan.getOrAddLiveIn(V: U->getValue());
53 auto *Expanded = new VPExpandSCEVRecipe(Expr);
54 VPBasicBlock *EntryVPBB = Plan.getEntry();
55 auto Iter = EntryVPBB->getFirstNonPhi();
56 while (Iter != EntryVPBB->end() && isa<VPIRInstruction>(Val: *Iter))
57 ++Iter;
58 EntryVPBB->insert(Recipe: Expanded, InsertPt: Iter);
59 return Expanded;
60}
61
62/// Returns true if \p R propagates poison from any operand to its result.
63static bool propagatesPoisonFromRecipeOp(const VPRecipeBase *R) {
64 return TypeSwitch<const VPRecipeBase *, bool>(R)
65 .Case<VPWidenGEPRecipe, VPWidenCastRecipe>(
66 caseFn: [](const VPRecipeBase *) { return true; })
67 .Case(caseFn: [](const VPReplicateRecipe *Rep) {
68 // GEP and casts propagate poison from all operands.
69 unsigned Opcode = Rep->getOpcode();
70 return Opcode == Instruction::GetElementPtr ||
71 Instruction::isCast(Opcode);
72 })
73 .Default(defaultFn: [](const VPRecipeBase *) { return false; });
74}
75
76/// Returns true if \p V being poison is guaranteed to trigger UB because it
77/// propagates to the address of a memory recipe.
78static bool poisonGuaranteesUB(const VPValue *V) {
79 SmallPtrSet<const VPValue *, 8> Visited;
80 SmallVector<const VPValue *, 16> Worklist;
81
82 Worklist.push_back(Elt: V);
83
84 while (!Worklist.empty()) {
85 const VPValue *Current = Worklist.pop_back_val();
86 if (!Visited.insert(Ptr: Current).second)
87 continue;
88
89 for (VPUser *U : Current->users()) {
90 // Check if Current is used as an address operand for load/store.
91 if (auto *MemR = dyn_cast<VPWidenMemoryRecipe>(Val: cast<VPRecipeBase>(Val: U))) {
92 if (MemR->getAddr() == Current)
93 return true;
94 continue;
95 }
96 if (auto *Rep = dyn_cast<VPReplicateRecipe>(Val: U)) {
97 unsigned Opcode = Rep->getOpcode();
98 if ((Opcode == Instruction::Load && Rep->getOperand(N: 0) == Current) ||
99 (Opcode == Instruction::Store && Rep->getOperand(N: 1) == Current))
100 return true;
101 }
102
103 // Check if poison propagates through this recipe to any of its users.
104 auto *R = cast<VPRecipeBase>(Val: U);
105 for (const VPValue *Op : R->operands()) {
106 if (Op == Current && propagatesPoisonFromRecipeOp(R)) {
107 Worklist.push_back(Elt: R->getVPSingleValue());
108 break;
109 }
110 }
111 }
112 }
113
114 return false;
115}
116
117GEPNoWrapFlags vputils::getGEPFlagsForPtr(VPValue *Ptr) {
118 // Like IR stripPointerCasts, look through GEPs with all-zero indices and
119 // casts to find a root GEP VPInstruction.
120 while (auto *PtrVPI = dyn_cast<VPInstruction>(Val: Ptr)) {
121 unsigned Opcode = PtrVPI->getOpcode();
122 if (Opcode == Instruction::GetElementPtr) {
123 if (!all_of(Range: drop_begin(RangeOrContainer: PtrVPI->operands()), P: match_fn(P: m_ZeroInt())))
124 return PtrVPI->getGEPNoWrapFlags();
125 Ptr = PtrVPI->getOperand(N: 0);
126 continue;
127 }
128 if (Opcode != Instruction::BitCast && Opcode != Instruction::AddrSpaceCast)
129 break;
130 Ptr = PtrVPI->getOperand(N: 0);
131 }
132 return GEPNoWrapFlags::none();
133}
134
135const SCEV *vputils::getSCEVExprForVPValue(const VPValue *V,
136 PredicatedScalarEvolution &PSE,
137 const Loop *L) {
138 ScalarEvolution &SE = *PSE.getSE();
139 if (auto *RV = dyn_cast<VPRegionValue>(Val: V)) {
140 assert(RV == RV->getDefiningRegion()->getCanonicalIV() &&
141 "RegionValue must be canonical IV");
142 if (!L)
143 return SE.getCouldNotCompute();
144 return SE.getAddRecExpr(Start: SE.getZero(Ty: RV->getType()), Step: SE.getOne(Ty: RV->getType()),
145 L, Flags: SCEV::FlagAnyWrap);
146 }
147
148 if (isa<VPIRValue, VPSymbolicValue>(Val: V)) {
149 Value *LiveIn = V->getUnderlyingValue();
150 if (LiveIn && SE.isSCEVable(Ty: LiveIn->getType()))
151 return SE.getSCEV(V: LiveIn);
152 return SE.getCouldNotCompute();
153 }
154
155 // Helper to create SCEVs for binary and unary operations.
156 auto CreateSCEV = [&](ArrayRef<VPValue *> Ops,
157 function_ref<const SCEV *(ArrayRef<SCEVUse>)> CreateFn)
158 -> const SCEV * {
159 SmallVector<SCEVUse, 2> SCEVOps;
160 for (VPValue *Op : Ops) {
161 const SCEV *S = getSCEVExprForVPValue(V: Op, PSE, L);
162 if (isa<SCEVCouldNotCompute>(Val: S))
163 return SE.getCouldNotCompute();
164 SCEVOps.push_back(Elt: S);
165 }
166 return PSE.getPredicatedSCEV(Expr: CreateFn(SCEVOps));
167 };
168
169 VPValue *LHSVal, *RHSVal;
170 if (match(V, P: m_Add(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
171 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
172 return SE.getAddExpr(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagAnyWrap, Depth: 0);
173 });
174 if (match(V, P: m_Sub(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
175 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
176 return SE.getMinusSCEV(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagAnyWrap, Depth: 0);
177 });
178 if (match(V, P: m_Not(Op0: m_VPValue(V&: LHSVal)))) {
179 // not X = xor X, -1 = -1 - X
180 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
181 return SE.getMinusSCEV(LHS: SE.getMinusOne(Ty: Ops[0]->getType()), RHS: Ops[0]);
182 });
183 }
184 if (match(V, P: m_Mul(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
185 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
186 return SE.getMulExpr(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagAnyWrap, Depth: 0);
187 });
188 // Handle shl by constant: x << c is equivalent to x * (1 << c). A shift
189 // amount >= the bit width produces poison; do not rewrite it, as
190 // getPowerOfTwo requires the power to be in range.
191 uint64_t ShiftAmt;
192 if (match(V, P: m_Shl(Op0: m_VPValue(V&: LHSVal), Op1: m_ConstantInt(C&: ShiftAmt))) &&
193 ShiftAmt < LHSVal->getScalarType()->getScalarSizeInBits())
194 return CreateSCEV(LHSVal, [&](ArrayRef<SCEVUse> Ops) {
195 return SE.getMulExpr(LHS: Ops[0],
196 RHS: SE.getPowerOfTwo(Ty: Ops[0]->getType(), Power: ShiftAmt));
197 });
198 if (match(V, P: m_LShr(Op0: m_VPValue(V&: LHSVal), Op1: m_ConstantInt(C&: ShiftAmt)))) {
199 Type *Ty = V->getScalarType();
200 if (ShiftAmt < SE.getTypeSizeInBits(Ty))
201 return CreateSCEV(LHSVal, [&](ArrayRef<SCEVUse> Ops) {
202 return SE.getUDivExpr(LHS: Ops[0], RHS: SE.getPowerOfTwo(Ty, Power: ShiftAmt));
203 });
204 }
205 if (match(V, P: m_UDiv(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
206 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
207 return SE.getUDivExpr(LHS: Ops[0], RHS: Ops[1]);
208 });
209 if (match(V, P: m_URem(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal))))
210 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
211 return SE.getURemExpr(LHS: Ops[0], RHS: Ops[1]);
212 });
213 // A SRem with non-negative operands is equivalent to an URem.
214 if (match(V, P: m_SRem(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) {
215 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
216 if (!SE.isKnownNonNegative(S: Ops[0]) || !SE.isKnownNonNegative(S: Ops[1]))
217 return SE.getCouldNotCompute();
218 return SE.getURemExpr(LHS: Ops[0], RHS: Ops[1]);
219 });
220 }
221 // Handle AND with constant mask: x & (2^n - 1) can be represented as x % 2^n.
222 const APInt *Mask;
223 if (match(V, P: m_c_BinaryAnd(Op0: m_VPValue(V&: LHSVal), Op1: m_APInt(C&: Mask))) &&
224 (*Mask + 1).isPowerOf2())
225 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
226 return SE.getURemExpr(LHS: Ops[0], RHS: SE.getConstant(Val: *Mask + 1));
227 });
228 if (match(V, P: m_Trunc(Op0: m_VPValue(V&: LHSVal)))) {
229 Type *DestTy = V->getScalarType();
230 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
231 return SE.getTruncateExpr(Op: Ops[0], Ty: DestTy);
232 });
233 }
234 if (match(V, P: m_ZExt(Op0: m_VPValue(V&: LHSVal)))) {
235 Type *DestTy = V->getScalarType();
236 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
237 return SE.getZeroExtendExpr(Op: Ops[0], Ty: DestTy);
238 });
239 }
240 if (match(V, P: m_SExt(Op0: m_VPValue(V&: LHSVal)))) {
241 Type *DestTy = V->getScalarType();
242
243 // Mirror SCEV's createSCEV handling for sext(sub nsw): push sign extension
244 // onto the operands before computing the subtraction.
245 VPValue *SubLHS, *SubRHS;
246 auto *SubR = dyn_cast<VPRecipeWithIRFlags>(Val: LHSVal);
247 if (match(V: LHSVal, P: m_Sub(Op0: m_VPValue(V&: SubLHS), Op1: m_VPValue(V&: SubRHS))) && SubR &&
248 SubR->hasNoSignedWrap() && poisonGuaranteesUB(V: LHSVal)) {
249 const SCEV *V1 = getSCEVExprForVPValue(V: SubLHS, PSE, L);
250 const SCEV *V2 = getSCEVExprForVPValue(V: SubRHS, PSE, L);
251 if (!isa<SCEVCouldNotCompute>(Val: V1) && !isa<SCEVCouldNotCompute>(Val: V2))
252 return SE.getMinusSCEV(LHS: SE.getSignExtendExpr(Op: V1, Ty: DestTy),
253 RHS: SE.getSignExtendExpr(Op: V2, Ty: DestTy), Flags: SCEV::FlagNSW);
254 }
255
256 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
257 return SE.getSignExtendExpr(Op: Ops[0], Ty: DestTy);
258 });
259 }
260 if (match(V,
261 P: m_Intrinsic<Intrinsic::umax>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal))))
262 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
263 return SE.getUMaxExpr(LHS: Ops[0], RHS: Ops[1]);
264 });
265 if (match(V,
266 P: m_Intrinsic<Intrinsic::smax>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal))))
267 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
268 return SE.getSMaxExpr(LHS: Ops[0], RHS: Ops[1]);
269 });
270 if (match(V,
271 P: m_Intrinsic<Intrinsic::umin>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal))))
272 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
273 return SE.getUMinExpr(LHS: Ops[0], RHS: Ops[1]);
274 });
275 if (match(V,
276 P: m_Intrinsic<Intrinsic::smin>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal))))
277 return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) {
278 return SE.getSMinExpr(LHS: Ops[0], RHS: Ops[1]);
279 });
280 if (match(V, P: m_Intrinsic<Intrinsic::abs>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue())))
281 return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) {
282 // is_int_min_poison is local to this intrinsic: poison on INT_MIN is
283 // not proof that the input is never INT_MIN, nor that poison reaches
284 // UB. Do not translate it to SCEV's global IsNSW flag.
285 return SE.getAbsExpr(Op: Ops[0], /*IsNSW=*/false);
286 });
287
288 ArrayRef<VPValue *> Ops;
289 Type *SourceElementType;
290 if (match(V, P: m_GetElementPtr(SourceElementType, Operands&: Ops))) {
291 return CreateSCEV(Ops, [&](ArrayRef<SCEVUse> Ops) {
292 return SE.getGEPExpr(BaseExpr: Ops.front(), IndexExprs: Ops.drop_front(), SrcElementTy: SourceElementType);
293 });
294 }
295
296 // TODO: Support constructing SCEVs for more recipes as needed.
297 const VPRecipeBase *DefR = V->getDefiningRecipe();
298 const SCEV *Expr =
299 TypeSwitch<const VPRecipeBase *, const SCEV *>(DefR)
300 .Case(caseFn: [](const VPExpandSCEVRecipe *R) { return R->getSCEV(); })
301 .Case(caseFn: [&SE, &PSE, L](const VPWidenIntOrFpInductionRecipe *R) {
302 const SCEV *Step = getSCEVExprForVPValue(V: R->getStepValue(), PSE, L);
303 if (!L || isa<SCEVCouldNotCompute>(Val: Step))
304 return SE.getCouldNotCompute();
305 const SCEV *Start =
306 getSCEVExprForVPValue(V: R->getStartValue(), PSE, L);
307 const SCEV *AddRec =
308 SE.getAddRecExpr(Start, Step, L, Flags: SCEV::FlagAnyWrap);
309 if (R->getTruncInst())
310 return SE.getTruncateExpr(Op: AddRec, Ty: R->getScalarType());
311 return AddRec;
312 })
313 .Case(caseFn: [&SE, &PSE, L](const VPWidenPointerInductionRecipe *R) {
314 const SCEV *Start =
315 getSCEVExprForVPValue(V: R->getStartValue(), PSE, L);
316 if (!L || isa<SCEVCouldNotCompute>(Val: Start))
317 return SE.getCouldNotCompute();
318 const SCEV *Step = getSCEVExprForVPValue(V: R->getStepValue(), PSE, L);
319 if (isa<SCEVCouldNotCompute>(Val: Step))
320 return SE.getCouldNotCompute();
321 return SE.getAddRecExpr(Start, Step, L, Flags: SCEV::FlagAnyWrap);
322 })
323 .Case(caseFn: [&SE, &PSE, L](const VPDerivedIVRecipe *R) {
324 const SCEV *Start = getSCEVExprForVPValue(V: R->getOperand(N: 0), PSE, L);
325 const SCEV *IV = getSCEVExprForVPValue(V: R->getOperand(N: 1), PSE, L);
326 const SCEV *Scale = getSCEVExprForVPValue(V: R->getOperand(N: 2), PSE, L);
327 if (any_of(Range: ArrayRef({Start, IV, Scale}),
328 P: IsaPred<SCEVCouldNotCompute>))
329 return SE.getCouldNotCompute();
330
331 return SE.getAddExpr(
332 LHS: SE.getTruncateOrSignExtend(V: Start, Ty: IV->getType()),
333 RHS: SE.getMulExpr(
334 LHS: IV, RHS: SE.getTruncateOrSignExtend(V: Scale, Ty: IV->getType())));
335 })
336 .Case(caseFn: [&SE, &PSE, L](const VPScalarIVStepsRecipe *R) {
337 const SCEV *IV = getSCEVExprForVPValue(V: R->getOperand(N: 0), PSE, L);
338 const SCEV *Step = getSCEVExprForVPValue(V: R->getOperand(N: 1), PSE, L);
339 if (isa<SCEVCouldNotCompute>(Val: IV) || !isa<SCEVConstant>(Val: Step))
340 return SE.getCouldNotCompute();
341 return SE.getTruncateOrSignExtend(V: IV, Ty: Step->getType());
342 })
343 .Default(
344 defaultFn: [&SE](const VPRecipeBase *) { return SE.getCouldNotCompute(); });
345
346 return PSE.getPredicatedSCEV(Expr);
347}
348
349bool vputils::isAddressSCEVForCost(const SCEV *Addr, ScalarEvolution &SE,
350 const Loop *L) {
351 // If address is an SCEVAddExpr, we require that all operands must be either
352 // be invariant or a (possibly sign-extend) affine AddRec.
353 if (auto *PtrAdd = dyn_cast<SCEVAddExpr>(Val: Addr)) {
354 return all_of(Range: PtrAdd->operands(), P: [&SE, L](const SCEV *Op) {
355 return SE.isLoopInvariant(S: Op, L) ||
356 match(S: Op, P: m_scev_SExt(Op0: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV()))) ||
357 match(S: Op, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV()));
358 });
359 }
360
361 // Otherwise, check if address is loop invariant or an affine add recurrence.
362 return SE.isLoopInvariant(S: Addr, L) ||
363 match(S: Addr, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV()));
364}
365
366unsigned vputils::getOpcode(const VPValue *V) {
367 return TypeSwitch<const VPValue *, unsigned>(V)
368 .Case<VPInstruction, VPWidenRecipe, VPWidenCastRecipe, VPWidenGEPRecipe,
369 VPReplicateRecipe, VPWidenPHIRecipe>(
370 caseFn: [](auto *I) { return I->getOpcode(); })
371 .Case<VPVectorPointerRecipe, VPPredInstPHIRecipe, VPScalarIVStepsRecipe>(
372 caseFn: [](auto *I) {
373 // For recipes that do not directly map to LLVM IR instructions,
374 // assign opcodes after the last VPInstruction opcode (which is also
375 // after the last IR Instruction opcode), based on the VPRecipeID.
376 return VPInstruction::OpsEnd + 1 + I->getVPRecipeID();
377 })
378 .Default(defaultFn: [](auto *) { return 0; });
379}
380
381std::optional<std::pair<bool, unsigned>>
382vputils::getOpcodeOrIntrinsicID(const VPValue *V) {
383 if (Intrinsic::ID IID = vputils::getIntrinsicID(R: V))
384 return std::make_pair(x: true, y&: IID);
385 if (unsigned Opcode = vputils::getOpcode(V))
386 return std::make_pair(x: false, y&: Opcode);
387 return {};
388}
389
390/// Returns true if \p Opcode preserves uniformity, i.e., if all operands are
391/// uniform, the result will also be uniform.
392static bool preservesUniformity(unsigned Opcode) {
393 if (Instruction::isBinaryOp(Opcode) || Instruction::isCast(Opcode))
394 return true;
395 switch (Opcode) {
396 case Instruction::Freeze:
397 case Instruction::GetElementPtr:
398 case Instruction::ICmp:
399 case Instruction::FCmp:
400 case Instruction::Select:
401 case VPInstruction::Not:
402 case VPInstruction::Broadcast:
403 case VPInstruction::MaskedCond:
404 case VPInstruction::PtrAdd:
405 return true;
406 default:
407 return false;
408 }
409}
410
411bool vputils::isElementwise(const VPValue *V) {
412 // TODO: Handle more opcodes and recipes.
413 if (!isa<VPInstruction, VPWidenRecipe>(Val: V))
414 return false;
415 unsigned Opcode = getOpcode(V);
416 return Instruction::isUnaryOp(Opcode) || Instruction::isBinaryOp(Opcode);
417}
418
419bool vputils::isSingleScalar(const VPValue *VPV) {
420 // Live-in, symbolic and canonical-IV region values are single-scalar.
421 if (auto *RV = dyn_cast<VPRegionValue>(Val: VPV))
422 return RV == RV->getDefiningRegion()->getCanonicalIV();
423 if (isa<VPIRValue, VPSymbolicValue>(Val: VPV))
424 return true;
425
426 if (auto *Rep = dyn_cast<VPReplicateRecipe>(Val: VPV)) {
427 const VPRegionBlock *RegionOfR = Rep->getRegion();
428 // Don't consider recipes in replicate regions as uniform yet; their first
429 // lane cannot be accessed when executing the replicate region for other
430 // lanes.
431 if (RegionOfR && RegionOfR->isReplicator())
432 return false;
433 return Rep->isSingleScalar() || (preservesUniformity(Opcode: Rep->getOpcode()) &&
434 all_of(Range: Rep->operands(), P: isSingleScalar));
435 }
436 if (isa<VPWidenGEPRecipe, VPBlendRecipe>(Val: VPV))
437 return all_of(Range: VPV->getDefiningRecipe()->operands(), P: isSingleScalar);
438 if (auto *WidenR = dyn_cast<VPWidenRecipe>(Val: VPV)) {
439 return preservesUniformity(Opcode: WidenR->getOpcode()) &&
440 all_of(Range: WidenR->operands(), P: isSingleScalar);
441 }
442 if (auto *VPI = dyn_cast<VPInstruction>(Val: VPV))
443 return VPI->isSingleScalar() || VPI->isVectorToScalar() ||
444 (preservesUniformity(Opcode: VPI->getOpcode()) &&
445 all_of(Range: VPI->operands(), P: isSingleScalar));
446 if (auto *RR = dyn_cast<VPReductionRecipe>(Val: VPV))
447 return !RR->isPartialReduction();
448 if (isa<VPVectorPointerRecipe, VPVectorEndPointerRecipe, VPDerivedIVRecipe>(
449 Val: VPV))
450 return true;
451 if (auto *Expr = dyn_cast<VPExpressionRecipe>(Val: VPV))
452 return Expr->isVectorToScalar();
453
454 // VPExpandSCEVRecipes must be placed in the entry and are always uniform.
455 return isa<VPExpandSCEVRecipe>(Val: VPV);
456}
457
458bool vputils::isUniformAcrossVFsAndUFs(const VPValue *V) {
459 // Live-ins, symbolic and canonical-IV region values are uniform.
460 if (auto *RV = dyn_cast<VPRegionValue>(Val: V))
461 return RV == RV->getDefiningRegion()->getCanonicalIV();
462 if (isa<VPIRValue, VPSymbolicValue>(Val: V))
463 return true;
464
465 const VPRecipeBase *R = V->getDefiningRecipe();
466 const VPBasicBlock *VPBB = R ? R->getParent() : nullptr;
467 const VPlan *Plan = VPBB ? VPBB->getPlan() : nullptr;
468 if (VPBB) {
469 if ((VPBB == Plan->getVectorPreheader() || VPBB == Plan->getEntry())) {
470 if (match(V: V->getDefiningRecipe(),
471 P: m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>()))
472 return false;
473 return all_of(Range: R->operands(), P: isUniformAcrossVFsAndUFs);
474 }
475 }
476
477 return TypeSwitch<const VPRecipeBase *, bool>(R)
478 .Case(caseFn: [](const VPDerivedIVRecipe *R) { return true; })
479 .Case(caseFn: [](const VPReplicateRecipe *R) {
480 // Be conservative about side-effects, except for the
481 // known-side-effecting assumes and stores, which we know will be
482 // uniform.
483 return R->isSingleScalar() &&
484 (!R->mayHaveSideEffects() ||
485 isa<AssumeInst, StoreInst>(Val: R->getUnderlyingInstr())) &&
486 all_of(Range: R->operands(), P: isUniformAcrossVFsAndUFs);
487 })
488 .Case(caseFn: [](const VPWidenRecipe *R) {
489 return preservesUniformity(Opcode: R->getOpcode()) &&
490 all_of(Range: R->operands(), P: isUniformAcrossVFsAndUFs);
491 })
492 .Case(caseFn: [](const VPPhi *) {
493 // Bail out on VPPhi, as we can end up in infinite cycles.
494 return false;
495 })
496 .Case(caseFn: [](const VPInstruction *VPI) {
497 return (VPI->isSingleScalar() || VPI->isVectorToScalar() ||
498 preservesUniformity(Opcode: VPI->getOpcode())) &&
499 all_of(Range: VPI->operands(), P: isUniformAcrossVFsAndUFs);
500 })
501 .Case(caseFn: [](const VPWidenCastRecipe *R) {
502 // A cast is uniform according to its operand.
503 return isUniformAcrossVFsAndUFs(V: R->getOperand(N: 0));
504 })
505 .Default(defaultFn: [](const VPRecipeBase *) { // A value is considered non-uniform
506 // unless proven otherwise.
507 return false;
508 });
509}
510
511bool vputils::doesGeneratePerAllLanes(const VPRecipeBase *R) {
512 if (auto *RepR = dyn_cast<VPReplicateRecipe>(Val: R))
513 return RepR->doesGeneratePerAllLanes();
514 if (auto *VPI = dyn_cast<VPInstruction>(Val: R))
515 return VPI->doesGeneratePerAllLanes();
516 if (auto *SIVSteps = dyn_cast<VPScalarIVStepsRecipe>(Val: R))
517 return SIVSteps->doesGeneratePerAllLanes();
518 return false;
519}
520
521VPBasicBlock *vputils::getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT) {
522 auto DepthFirst = vp_depth_first_shallow(G: Plan.getEntry());
523 auto I = find_if(Range&: DepthFirst, P: [&VPDT](VPBlockBase *VPB) {
524 return VPBlockUtils::isHeader(VPB, VPDT);
525 });
526 return I == DepthFirst.end() ? nullptr : cast<VPBasicBlock>(Val: *I);
527}
528
529unsigned vputils::getVFScaleFactor(VPRecipeBase *R) {
530 if (!R)
531 return 1;
532 if (auto *RR = dyn_cast<VPReductionPHIRecipe>(Val: R))
533 return RR->getVFScaleFactor();
534 if (auto *RR = dyn_cast<VPReductionRecipe>(Val: R))
535 return RR->getVFScaleFactor();
536 if (auto *ER = dyn_cast<VPExpressionRecipe>(Val: R))
537 return ER->getVFScaleFactor();
538 assert(
539 (!isa<VPInstruction>(R) || cast<VPInstruction>(R)->getOpcode() !=
540 VPInstruction::ReductionStartVector) &&
541 "getting scaling factor of reduction-start-vector not implemented yet");
542 return 1;
543}
544
545bool vputils::cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking) {
546 // Assumes don't alias anything or throw; as long as they're guaranteed to
547 // execute, they're safe to hoist. They should however not be sunk, as it
548 // would destroy information.
549 if (match(V: &R, P: m_Intrinsic<Intrinsic::assume>()))
550 return Sinking;
551 if (R.mayHaveSideEffects() || R.mayReadFromMemory() || R.isPhi())
552 return true;
553 // Allocas cannot be hoisted.
554 auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R);
555 return RepR && RepR->getOpcode() == Instruction::Alloca;
556}
557
558SmallVector<VPBasicBlock *>
559VPBlockUtils::blocksInSingleSuccessorChainBetween(VPBasicBlock *FirstBB,
560 VPBasicBlock *LastBB) {
561 assert(FirstBB->getParent() == LastBB->getParent() &&
562 "FirstBB and LastBB from different regions");
563#ifndef NDEBUG
564 bool InSingleSuccChain = false;
565 for (VPBlockBase *Succ = FirstBB; Succ; Succ = Succ->getSingleSuccessor())
566 InSingleSuccChain |= (Succ == LastBB);
567 assert(InSingleSuccChain &&
568 "LastBB unreachable from FirstBB in single-successor chain");
569#endif
570 auto Blocks = to_vector(
571 Range: VPBlockUtils::blocksOnly<VPBasicBlock>(Range: vp_depth_first_deep(G: FirstBB)));
572 auto *LastIt = find(Range&: Blocks, Val: LastBB);
573 assert(LastIt != Blocks.end() &&
574 "LastBB unreachable from FirstBB in depth-first traversal");
575 Blocks.erase(CS: std::next(x: LastIt), CE: Blocks.end());
576 return Blocks;
577}
578
579VPValue *vputils::findIncomingAliasMask(const VPlan &Plan) {
580 for (VPRecipeBase &R : *Plan.getVectorPreheader())
581 if (match(V: &R, P: m_VPInstruction<VPInstruction::IncomingAliasMask>()))
582 return cast<VPInstruction>(Val: &R);
583 return nullptr;
584}
585
586bool VPBlockUtils::isHeader(const VPBlockBase *VPB,
587 const VPDominatorTree &VPDT) {
588 auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB);
589 if (!VPBB)
590 return false;
591
592 // If VPBB is in a region R, VPBB is a loop header if R is a loop region with
593 // VPBB as its entry, i.e., free of predecessors.
594 if (auto *R = VPBB->getParent())
595 return !R->isReplicator() && !VPBB->hasPredecessors();
596
597 // A header dominates its second predecessor (the latch), with the other
598 // predecessor being the preheader
599 return VPB->getPredecessors().size() == 2 &&
600 VPDT.dominates(A: VPB, B: VPB->getPredecessors()[1]);
601}
602
603bool VPBlockUtils::isLatch(const VPBlockBase *VPB,
604 const VPDominatorTree &VPDT) {
605 // A latch has a header as its last successor, with its other successors
606 // leaving the loop. A preheader OTOH has a header as its first (and only)
607 // successor.
608 return VPB->getNumSuccessors() >= 2 &&
609 VPBlockUtils::isHeader(VPB: VPB->getSuccessors().back(), VPDT);
610}
611
612std::pair<VPBasicBlock *, VPBasicBlock *>
613VPBlockUtils::getPlainCFGHeaderAndLatch(const VPlan &Plan) {
614 auto *Header = cast<VPBasicBlock>(
615 Val: Plan.getEntry()->getSuccessors()[1]->getSingleSuccessor());
616 auto *Latch = cast<VPBasicBlock>(Val: Header->getPredecessors()[1]);
617 return {Header, Latch};
618}
619
620VPBasicBlock *VPBlockUtils::getPlainCFGMiddleBlock(const VPlan &Plan) {
621 return cast<VPBasicBlock>(Val: Plan.getScalarPreheader()->getPredecessors()[0]);
622}
623
624std::optional<MemoryLocation>
625vputils::getMemoryLocation(const VPRecipeBase &R) {
626 auto *M = dyn_cast<VPIRMetadata>(Val: &R);
627 if (!M)
628 return std::nullopt;
629 MemoryLocation Loc;
630 // Populate noalias metadata from VPIRMetadata.
631 if (MDNode *NoAliasMD = M->getMetadata(Kind: LLVMContext::MD_noalias))
632 Loc.AATags.NoAlias = NoAliasMD;
633 if (MDNode *AliasScopeMD = M->getMetadata(Kind: LLVMContext::MD_alias_scope))
634 Loc.AATags.Scope = AliasScopeMD;
635 return Loc;
636}
637
638VPInstruction *vputils::findCanonicalIVIncrement(VPlan &Plan) {
639 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
640 VPRegionValue *CanIV = LoopRegion->getCanonicalIV();
641 assert(CanIV && "Expected loop region to have a canonical IV");
642
643 VPSymbolicValue &VFxUF = Plan.getVFxUF();
644
645 // Check if \p Step matches the expected increment step, accounting for
646 // materialization of VFxUF and UF.
647 auto IsIncrementStep = [&](VPValue *Step) -> bool {
648 if (!VFxUF.isMaterialized())
649 return Step == &VFxUF;
650
651 VPSymbolicValue &UF = Plan.getUF();
652 if (!UF.isMaterialized())
653 return Step == &UF ||
654 match(V: Step, P: m_c_Mul(Op0: m_Specific(VPV: &Plan.getUF()), Op1: m_VScale()));
655
656 // Alias masking: step is number of active lanes of a dependence mask.
657 if (match(V: Step, P: m_ZExtOrTruncOrSelf(
658 Op0: m_VPInstruction<VPInstruction::NumActiveLanes>())))
659 return true;
660
661 unsigned ConcreteUF = Plan.getConcreteUF();
662 // Fixed VF: step is just the concrete UF.
663 if (match(V: Step, P: m_SpecificInt(V: ConcreteUF)))
664 return true;
665
666 // Scalable VF: step involves VScale.
667 if (ConcreteUF == 1)
668 return match(V: Step, P: m_VScale());
669 if (match(V: Step, P: m_c_Mul(Op0: m_SpecificInt(V: ConcreteUF), Op1: m_VScale())))
670 return true;
671 // mul(VScale, ConcreteUF) may have been simplified to
672 // shl(VScale, log2(ConcreteUF)) when ConcreteUF is a power of 2.
673 return isPowerOf2_32(Value: ConcreteUF) &&
674 match(V: Step, P: m_Shl(Op0: m_VScale(), Op1: m_SpecificInt(V: Log2_32(Value: ConcreteUF))));
675 };
676
677 VPInstruction *Increment = nullptr;
678 for (VPUser *U : CanIV->users()) {
679 VPValue *Step;
680 if (isa<VPInstruction>(Val: U) &&
681 match(U, P: m_c_Add(Op0: m_Specific(VPV: CanIV), Op1: m_VPValue(V&: Step))) &&
682 IsIncrementStep(Step)) {
683 assert(!Increment && "There must be a unique increment");
684 Increment = cast<VPInstruction>(Val: U);
685 }
686 }
687
688 assert((!VFxUF.isMaterialized() || Increment) &&
689 "After materializing VFxUF, an increment must exist");
690 assert((!Increment ||
691 LoopRegion->hasCanonicalIVNUW() == Increment->hasNoUnsignedWrap()) &&
692 "NUW flag in region and increment must match");
693 return Increment;
694}
695
696/// Find the ComputeReductionResult recipe for \p PhiR, looking through selects
697/// inserted for predicated reductions or tail folding.
698VPInstruction *vputils::findComputeReductionResult(VPReductionPHIRecipe *PhiR) {
699 VPValue *BackedgeVal = PhiR->getBackedgeValue();
700 if (auto *Res =
701 findUserOf<VPInstruction::ComputeReductionResult>(V: BackedgeVal))
702 return Res;
703
704 // Look through selects inserted for tail folding or predicated reductions.
705 VPRecipeBase *SelR =
706 findUserOf(V: BackedgeVal, P: m_Select(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue()));
707 if (!SelR)
708 return nullptr;
709 return findUserOf<VPInstruction::ComputeReductionResult>(
710 V: cast<VPSingleDefRecipe>(Val: SelR));
711}
712
713bool vputils::isUsedByLoadStoreAddress(const VPValue *V) {
714 SmallPtrSet<const VPValue *, 4> Seen;
715 SmallVector<const VPValue *> WorkList = {V};
716
717 while (!WorkList.empty()) {
718 const VPValue *Cur = WorkList.pop_back_val();
719 if (!Seen.insert(Ptr: Cur).second)
720 continue;
721
722 auto *Blend = dyn_cast<VPBlendRecipe>(Val: Cur);
723 // Skip blends that use V only through a compare by checking if any incoming
724 // value was already visited.
725 if (Blend && none_of(Range: seq<unsigned>(Begin: 0, End: Blend->getNumIncomingValues()),
726 P: [&](unsigned I) {
727 return Seen.contains(Ptr: Blend->getIncomingValue(Idx: I));
728 }))
729 continue;
730
731 for (VPUser *U : Cur->users()) {
732 if (auto *InterleaveR = dyn_cast<VPInterleaveBase>(Val: U))
733 if (InterleaveR->getAddr() == Cur)
734 return true;
735 // Cur is used as the pointer of a (possibly masked) load (operand 0) or
736 // store (operand 1).
737 if (match(U, P: m_CombineOr(Ps: m_Unary<Instruction::Load>(Op0: m_Specific(VPV: Cur)),
738 Ps: m_Binary<Instruction::Store>(Op0: m_VPValue(),
739 Op1: m_Specific(VPV: Cur)))))
740 return true;
741 if (auto *MemR = dyn_cast<VPWidenMemoryRecipe>(Val: cast<VPRecipeBase>(Val: U))) {
742 if (MemR->getAddr() == Cur && MemR->isConsecutive())
743 return true;
744 }
745 }
746
747 // The legacy cost model only supports scalarization loads/stores with phi
748 // addresses, if the phi is directly used as load/store address. Don't
749 // traverse further for Blends.
750 if (Blend)
751 continue;
752
753 // Only traverse further through users that also define a value (and can
754 // thus have their own users walked). Skip when Cur is only used as mask ,
755 // as well as loads: a loaded value does not depend on the load's operand.
756 for (VPUser *U : Cur->users()) {
757 auto *VPI = dyn_cast<VPInstruction>(Val: U);
758 if (VPI && VPI->getMask() == Cur &&
759 none_of(Range: VPI->operandsWithoutMask(),
760 P: [Cur](VPValue *Op) { return Op == Cur; }))
761 continue;
762 if (match(U, P: m_VPInstruction<Instruction::Load>()))
763 continue;
764 if (auto *SDR = dyn_cast<VPSingleDefRecipe>(Val: U))
765 WorkList.push_back(Elt: SDR);
766 }
767 }
768 return false;
769}
770
771/// Try to find a loop-invariant IR value for \p S in the plan's entry block
772/// that can be reused. Returns the corresponding live-in VPValue, or nullptr
773/// if no reusable IR value is found.
774VPValue *VPSCEVExpander::tryToReuseIRValue(const SCEV *S) {
775 if (isa<SCEVConstant, SCEVUnknown>(Val: S))
776 return nullptr;
777 VPlan &Plan = Builder.getPlan();
778 BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock();
779 for (Value *V : SE.getSCEVValues(S)) {
780 // Only reuse instructions in the plan's entry block, or, when a
781 // DominatorTree is available, any instruction that dominates it.
782 // Instructions in sibling branches may not dominate the entry block.
783 auto *I = dyn_cast<Instruction>(Val: V);
784 if (!I)
785 return Plan.getOrAddLiveIn(V);
786 if (!SE.DT.dominates(A: I->getParent(), B: PH))
787 continue;
788 SmallVector<Instruction *> DropPoisonGeneratingInsts;
789 if (!SE.canReuseInstruction(S, I, DropPoisonGeneratingInsts))
790 continue;
791 for (Instruction *DropI : DropPoisonGeneratingInsts)
792 SCEVExpander::dropPoisonGeneratingAnnotationsAndReinfer(SE, I: DropI);
793 return Plan.getOrAddLiveIn(V);
794 }
795 return nullptr;
796}
797
798VPValue *VPSCEVExpander::tryToExpand(const SCEV *S) {
799 if (VPValue *V = tryToReuseIRValue(S))
800 return V;
801
802 switch (S->getSCEVType()) {
803 case scConstant:
804 return Builder.getPlan().getOrAddLiveIn(V: cast<SCEVConstant>(Val: S)->getValue());
805 case scUnknown:
806 return Builder.getPlan().getOrAddLiveIn(V: cast<SCEVUnknown>(Val: S)->getValue());
807 case scVScale:
808 return Builder.createVScale(ResultTy: S->getType(), DL);
809 case scAddExpr:
810 case scMulExpr: {
811 auto *NAry = cast<SCEVNAryExpr>(Val: S);
812 VPIRFlags::WrapFlagsTy WrapFlags(NAry->hasNoUnsignedWrap(),
813 NAry->hasNoSignedWrap());
814
815 // Expanded poiner SCEVAddExpr as a ptradd of the pointer base and the
816 // integer offset, matching SCEVExpander.
817 if (S->getType()->isPointerTy()) {
818 VPValue *Base = tryToExpand(S: SE.getPointerBase(V: S));
819 if (!Base)
820 return nullptr;
821 VPValue *Offset = tryToExpand(S: SE.removePointerBase(S));
822 if (!Offset)
823 return nullptr;
824 GEPNoWrapFlags GEPFlags = WrapFlags.HasNUW
825 ? GEPNoWrapFlags::noUnsignedWrap()
826 : GEPNoWrapFlags::none();
827 return Builder.createNoWrapPtrAdd(Ptr: Base, Offset, GEPFlags, DL);
828 }
829
830 unsigned Opcode =
831 S->getSCEVType() == scAddExpr ? Instruction::Add : Instruction::Mul;
832 // Iterate in reverse so that constants are emitted last.
833 SmallVector<VPValue *, 2> Ops;
834 for (const SCEVUse &Op : reverse(C: NAry->operands())) {
835 VPValue *OpV = tryToExpand(S: Op);
836 if (!OpV)
837 return nullptr;
838 Ops.push_back(Elt: OpV);
839 }
840 VPValue *Result = Ops.front();
841 for (VPValue *Op : drop_begin(RangeOrContainer&: Ops))
842 Result = Builder.createOverflowingOp(Opcode, Operands: {Result, Op}, WrapFlags, DL);
843 return Result;
844 }
845 case scUDivExpr: {
846 auto *UDiv = cast<SCEVUDivExpr>(Val: S);
847 VPValue *LHS = tryToExpand(S: UDiv->getLHS());
848 if (!LHS)
849 return nullptr;
850 VPValue *RHS = tryToExpand(S: UDiv->getRHS());
851 if (!RHS)
852 return nullptr;
853 return Builder.createNaryOp(Opcode: Instruction::UDiv, Operands: {LHS, RHS},
854 Flags: VPIRFlags::getDefaultFlags(Opcode: Instruction::UDiv),
855 DL);
856 }
857 case scTruncate:
858 case scZeroExtend:
859 case scSignExtend:
860 case scPtrToInt:
861 case scPtrToAddr: {
862 auto *Cast = cast<SCEVCastExpr>(Val: S);
863 VPValue *Op = tryToExpand(S: Cast->getOperand());
864 if (!Op)
865 return nullptr;
866 Instruction::CastOps Opcode;
867 switch (S->getSCEVType()) {
868 case scTruncate:
869 Opcode = Instruction::Trunc;
870 break;
871 case scZeroExtend:
872 Opcode = Instruction::ZExt;
873 break;
874 case scSignExtend:
875 Opcode = Instruction::SExt;
876 break;
877 case scPtrToInt:
878 Opcode = Instruction::PtrToInt;
879 break;
880 case scPtrToAddr:
881 Opcode = Instruction::PtrToAddr;
882 break;
883 default:
884 llvm_unreachable("Unhandled cast SCEV");
885 }
886 return Builder.createScalarCast(Opcode, Op, ResultTy: S->getType(), DL);
887 }
888 case scUMaxExpr:
889 case scSMaxExpr:
890 case scUMinExpr:
891 case scSMinExpr: {
892 auto *MinMax = cast<SCEVMinMaxExpr>(Val: S);
893 Intrinsic::ID IntrinsicID;
894 switch (S->getSCEVType()) {
895 case scUMaxExpr:
896 IntrinsicID = Intrinsic::umax;
897 break;
898 case scSMaxExpr:
899 IntrinsicID = Intrinsic::smax;
900 break;
901 case scUMinExpr:
902 IntrinsicID = Intrinsic::umin;
903 break;
904 case scSMinExpr:
905 IntrinsicID = Intrinsic::smin;
906 break;
907 default:
908 llvm_unreachable("Unexpected min/max SCEV type");
909 }
910 // Chain operands in reverse order matching SCEVExpander's expansion of
911 // min/max expressions.
912 SmallVector<VPValue *, 2> Ops;
913 for (const SCEVUse &Op : reverse(C: MinMax->operands())) {
914 VPValue *OpV = tryToExpand(S: Op);
915 if (!OpV)
916 return nullptr;
917 Ops.push_back(Elt: OpV);
918 }
919 Type *ResultTy = MinMax->getType();
920 VPValue *Result = Ops.front();
921 for (VPValue *Op : drop_begin(RangeOrContainer&: Ops))
922 Result = Builder.createScalarIntrinsic(IntrinsicID, Operands: {Result, Op},
923 ResultTy, DL);
924 return Result;
925 }
926 default:
927 return nullptr;
928 }
929}
930
931bool vputils::isDeadRecipe(VPRecipeBase &R) {
932 // Do remove conditional assume instructions as their conditions may be
933 // flattened.
934 auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R);
935 bool IsConditionalAssume = RepR && RepR->isPredicated() &&
936 match(V: RepR, P: m_Intrinsic<Intrinsic::assume>());
937 if (IsConditionalAssume)
938 return true;
939
940 if (R.mayHaveSideEffects())
941 return false;
942
943 // Recipe is dead if no user keeps the recipe alive.
944 return all_of(Range: R.definedValues(), P: [](VPValue *V) { return V->user_empty(); });
945}
946
947void vputils::recursivelyDeleteDeadRecipes(VPValue *V) {
948 SmallVector<VPValue *> WorkList;
949 SmallPtrSet<VPValue *, 8> Seen;
950 WorkList.push_back(Elt: V);
951
952 while (!WorkList.empty()) {
953 VPValue *Cur = WorkList.pop_back_val();
954 if (!Seen.insert(Ptr: Cur).second)
955 continue;
956 VPRecipeBase *R = Cur->getDefiningRecipe();
957 if (!R)
958 continue;
959 if (!isDeadRecipe(R&: *R))
960 continue;
961 append_range(C&: WorkList, R: R->operands());
962 R->eraseFromParent();
963 }
964}
965
966SmallVector<VPUser *> vputils::collectUsersRecursively(VPValue *V) {
967 SetVector<VPUser *> Users(llvm::from_range, V->users());
968 for (unsigned I = 0; I != Users.size(); ++I) {
969 VPRecipeBase *Cur = cast<VPRecipeBase>(Val: Users[I]);
970 for (VPValue *V : Cur->definedValues())
971 Users.insert_range(R: V->users());
972 }
973 return Users.takeVector();
974}
975
976VPIRValue *vputils::tryToFoldLiveIns(VPSingleDefRecipe &R,
977 ArrayRef<VPValue *> Operands,
978 const DataLayout &DL) {
979 auto OpcodeOrIID = getOpcodeOrIntrinsicID(V: &R);
980 if (!OpcodeOrIID)
981 return nullptr;
982
983 SmallVector<Value *, 4> Ops;
984 for (VPValue *Op : Operands) {
985 VPValue *Candidate = Op;
986 match(V: Op, P: m_Broadcast(Op0: m_VPValue(V&: Candidate)));
987 if (!match(V: Candidate, P: m_LiveIn()))
988 return nullptr;
989 Value *V = Candidate->getUnderlyingValue();
990 if (!V)
991 return nullptr;
992 Ops.push_back(Elt: V);
993 }
994
995 VPlan &Plan = *R.getParent()->getPlan();
996 auto FoldToIRValue = [&]() -> Value * {
997 InstSimplifyFolder Folder(DL);
998 if (OpcodeOrIID->first) {
999 // VPInstructions store the called intrinsic as last operand.
1000 if (isa<VPInstruction>(Val: R))
1001 Ops.pop_back();
1002
1003 auto *RFlags = dyn_cast<VPRecipeWithIRFlags>(Val: &R);
1004 return Folder.FoldIntrinsic(ID: OpcodeOrIID->second, Ops, Ty: R.getScalarType(),
1005 FMF: RFlags ? RFlags->getFastMathFlagsOrNone()
1006 : FastMathFlags());
1007 }
1008 unsigned Opcode = OpcodeOrIID->second;
1009 if (Instruction::isBinaryOp(Opcode))
1010 return Folder.FoldBinOp(Opc: static_cast<Instruction::BinaryOps>(Opcode),
1011 LHS: Ops[0], RHS: Ops[1]);
1012 if (Instruction::isCast(Opcode))
1013 return Folder.FoldCast(Op: static_cast<Instruction::CastOps>(Opcode), V: Ops[0],
1014 DestTy: R.getVPSingleValue()->getScalarType());
1015 switch (Opcode) {
1016 case VPInstruction::Not:
1017 return Folder.FoldBinOp(Opc: Instruction::BinaryOps::Xor, LHS: Ops[0],
1018 RHS: Constant::getAllOnesValue(Ty: Ops[0]->getType()));
1019 case Instruction::Select:
1020 return Folder.FoldSelect(C: Ops[0], True: Ops[1], False: Ops[2]);
1021 case Instruction::ICmp:
1022 case Instruction::FCmp:
1023 return Folder.FoldCmp(P: cast<VPRecipeWithIRFlags>(Val&: R).getPredicate(), LHS: Ops[0],
1024 RHS: Ops[1]);
1025 case Instruction::GetElementPtr: {
1026 auto &RFlags = cast<VPRecipeWithIRFlags>(Val&: R);
1027 auto *GEP = cast<GetElementPtrInst>(Val: RFlags.getUnderlyingInstr());
1028 return Folder.FoldGEP(Ty: GEP->getSourceElementType(), Ptr: Ops[0],
1029 IdxList: drop_begin(RangeOrContainer&: Ops), NW: RFlags.getGEPNoWrapFlags());
1030 }
1031 case VPInstruction::PtrAdd:
1032 case VPInstruction::WidePtrAdd:
1033 return Folder.FoldGEP(Ty: IntegerType::getInt8Ty(C&: Plan.getContext()), Ptr: Ops[0],
1034 IdxList: Ops[1],
1035 NW: cast<VPRecipeWithIRFlags>(Val&: R).getGEPNoWrapFlags());
1036 // An extract of a live-in is an extract of a broadcast, so return the
1037 // broadcasted element.
1038 case Instruction::ExtractElement:
1039 assert(!Ops[0]->getType()->isVectorTy() && "Live-ins should be scalar");
1040 return Ops[0];
1041 }
1042 return nullptr;
1043 };
1044
1045 if (Value *V = FoldToIRValue())
1046 return Plan.getOrAddLiveIn(V);
1047 return nullptr;
1048}
1049
1050void vputils::detail::pullOutPermutationsImpl(
1051 VPlan &Plan, function_ref<VPValue *(VPValue *Op)> MatchPerm,
1052 function_ref<VPSingleDefRecipe *(VPSingleDefRecipe *X)> BuildPerm) {
1053 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
1054 Range: vp_depth_first_deep(G: Plan.getEntry()))) {
1055 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
1056 auto *Def = dyn_cast<VPSingleDefRecipe>(Val: &R);
1057 if (!Def || !isElementwise(V: Def))
1058 continue;
1059
1060 // At least one of the ops must be a permutation.
1061 if (none_of(Range: Def->operands(),
1062 P: [&MatchPerm](VPValue *Op) { return MatchPerm(Op); }))
1063 continue;
1064
1065 // All operands must be a single-use permutation or a live in (splat).
1066 if (!all_of(Range: Def->operands(), P: [&MatchPerm](VPValue *Op) {
1067 return (Op->hasOneUse() && MatchPerm(Op)) || match(V: Op, P: m_LiveIn());
1068 }))
1069 continue;
1070
1071 // Remove the inner permutations.
1072 for (unsigned I = 0, E = Def->getNumOperands(); I != E; ++I)
1073 if (VPValue *X = MatchPerm(Def->getOperand(N: I)))
1074 Def->setOperand(I, New: X);
1075
1076 VPSingleDefRecipe *Res = BuildPerm(Def);
1077 Res->insertAfter(InsertPos: Def);
1078 Def->replaceUsesWithIf(
1079 New: Res, ShouldReplace: [&Res](VPUser &U, unsigned _) { return &U != Res; });
1080 }
1081 }
1082}
1083