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