1//===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===//
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// This file "describes" induction and recurrence variables.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/IVDescriptors.h"
14#include "llvm/Analysis/DemandedBits.h"
15#include "llvm/Analysis/LoopInfo.h"
16#include "llvm/Analysis/ScalarEvolution.h"
17#include "llvm/Analysis/ScalarEvolutionExpressions.h"
18#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
19#include "llvm/Analysis/ValueTracking.h"
20#include "llvm/IR/Dominators.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/PatternMatch.h"
23#include "llvm/IR/ValueHandle.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/KnownBits.h"
26
27using namespace llvm;
28using namespace llvm::PatternMatch;
29using namespace llvm::SCEVPatternMatch;
30
31#define DEBUG_TYPE "iv-descriptors"
32
33bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
34 SmallPtrSetImpl<Instruction *> &Set) {
35 for (const Use &Use : I->operands())
36 if (!Set.count(Ptr: dyn_cast<Instruction>(Val: Use)))
37 return false;
38 return true;
39}
40
41bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) {
42 switch (Kind) {
43 default:
44 break;
45 case RecurKind::AddChainWithSubs:
46 case RecurKind::Sub:
47 case RecurKind::Add:
48 case RecurKind::Mul:
49 case RecurKind::Or:
50 case RecurKind::And:
51 case RecurKind::Xor:
52 case RecurKind::SMax:
53 case RecurKind::SMin:
54 case RecurKind::UMax:
55 case RecurKind::UMin:
56 case RecurKind::AnyOf:
57 case RecurKind::FindIV:
58 case RecurKind::FindLast:
59 return true;
60 }
61 return false;
62}
63
64bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) {
65 return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
66}
67
68/// Determines if Phi may have been type-promoted. If Phi has a single user
69/// that ANDs the Phi with a type mask, return the user. RT is updated to
70/// account for the narrower bit width represented by the mask, and the AND
71/// instruction is added to CI.
72static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
73 SmallPtrSetImpl<Instruction *> &Visited,
74 SmallPtrSetImpl<Instruction *> &CI) {
75 if (!Phi->hasOneUse())
76 return Phi;
77
78 const APInt *M = nullptr;
79 Instruction *I, *J = cast<Instruction>(Val: Phi->use_begin()->getUser());
80
81 // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
82 // with a new integer type of the corresponding bit width.
83 if (match(V: J, P: m_And(L: m_Instruction(I), R: m_APInt(Res&: M)))) {
84 int32_t Bits = (*M + 1).exactLogBase2();
85 if (Bits > 0) {
86 RT = IntegerType::get(C&: Phi->getContext(), NumBits: Bits);
87 Visited.insert(Ptr: Phi);
88 CI.insert(Ptr: J);
89 return J;
90 }
91 }
92 return Phi;
93}
94
95bool RecurrenceDescriptor::isSubRecurrenceKind(RecurKind Kind) {
96 return Kind == RecurKind::Sub || Kind == RecurKind::FSub;
97}
98
99/// Compute the minimal bit width needed to represent a reduction whose exit
100/// instruction is given by Exit.
101static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
102 DemandedBits *DB,
103 AssumptionCache *AC,
104 DominatorTree *DT) {
105 bool IsSigned = false;
106 const DataLayout &DL = Exit->getDataLayout();
107 uint64_t MaxBitWidth = DL.getTypeSizeInBits(Ty: Exit->getType());
108
109 if (DB) {
110 // Use the demanded bits analysis to determine the bits that are live out
111 // of the exit instruction, rounding up to the nearest power of two. If the
112 // use of demanded bits results in a smaller bit width, we know the value
113 // must be positive (i.e., IsSigned = false), because if this were not the
114 // case, the sign bit would have been demanded.
115 auto Mask = DB->getDemandedBits(I: Exit);
116 MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero();
117 }
118
119 if (MaxBitWidth == DL.getTypeSizeInBits(Ty: Exit->getType()) && AC && DT) {
120 // If demanded bits wasn't able to limit the bit width, we can try to use
121 // value tracking instead. This can be the case, for example, if the value
122 // may be negative.
123 auto NumSignBits = ComputeNumSignBits(Op: Exit, DL, AC, CtxI: nullptr, DT);
124 auto NumTypeBits = DL.getTypeSizeInBits(Ty: Exit->getType());
125 MaxBitWidth = NumTypeBits - NumSignBits;
126 KnownBits Bits = computeKnownBits(V: Exit, DL);
127 if (!Bits.isNonNegative()) {
128 // If the value is not known to be non-negative, we set IsSigned to true,
129 // meaning that we will use sext instructions instead of zext
130 // instructions to restore the original type.
131 IsSigned = true;
132 // Make sure at least one sign bit is included in the result, so it
133 // will get properly sign-extended.
134 ++MaxBitWidth;
135 }
136 }
137 MaxBitWidth = llvm::bit_ceil(Value: MaxBitWidth);
138
139 return std::make_pair(x: Type::getIntNTy(C&: Exit->getContext(), N: MaxBitWidth),
140 y&: IsSigned);
141}
142
143/// Collect cast instructions that can be ignored in the vectorizer's cost
144/// model, given a reduction exit value and the minimal type in which the
145// reduction can be represented. Also search casts to the recurrence type
146// to find the minimum width used by the recurrence.
147static void collectCastInstrs(Loop *TheLoop, Instruction *Exit,
148 Type *RecurrenceType,
149 SmallPtrSetImpl<Instruction *> &Casts,
150 Type *&MinWidthCastToRecurTy) {
151
152 SmallVector<Instruction *, 8> Worklist;
153 SmallPtrSet<Instruction *, 8> Visited;
154 Worklist.push_back(Elt: Exit);
155 MinWidthCastToRecurTy = nullptr;
156
157 while (!Worklist.empty()) {
158 Instruction *Val = Worklist.pop_back_val();
159 Visited.insert(Ptr: Val);
160 if (auto *Cast = dyn_cast<CastInst>(Val)) {
161 if (Cast->getSrcTy() == RecurrenceType) {
162 // If the source type of a cast instruction is equal to the recurrence
163 // type, it will be eliminated, and should be ignored in the vectorizer
164 // cost model.
165 Casts.insert(Ptr: Cast);
166 continue;
167 }
168 if (Cast->getDestTy() == RecurrenceType) {
169 // The minimum width used by the recurrence is found by checking for
170 // casts on its operands. The minimum width is used by the vectorizer
171 // when finding the widest type for in-loop reductions without any
172 // loads/stores.
173 Type *SrcTy = Cast->getSrcTy()->getScalarType();
174 if (!MinWidthCastToRecurTy ||
175 SrcTy->getScalarSizeInBits() <
176 MinWidthCastToRecurTy->getScalarSizeInBits())
177 MinWidthCastToRecurTy = SrcTy;
178 continue;
179 }
180 }
181 // Add all operands to the work list if they are loop-varying values that
182 // we haven't yet visited.
183 for (Value *O : cast<User>(Val)->operands())
184 if (auto *I = dyn_cast<Instruction>(Val: O))
185 if (TheLoop->contains(Inst: I) && !Visited.count(Ptr: I))
186 Worklist.push_back(Elt: I);
187 }
188}
189
190// Check if a given Phi node can be recognized as an ordered reduction for
191// vectorizing floating point operations without unsafe math.
192static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst,
193 Instruction *Exit, PHINode *Phi) {
194 // Currently only FAdd and FMulAdd are supported.
195 if (Kind != RecurKind::FAdd && Kind != RecurKind::FMulAdd)
196 return false;
197
198 if (Kind == RecurKind::FAdd && Exit->getOpcode() != Instruction::FAdd)
199 return false;
200
201 if (Kind == RecurKind::FMulAdd &&
202 !RecurrenceDescriptor::isFMulAddIntrinsic(I: Exit))
203 return false;
204
205 // Ensure the exit instruction has only one user other than the reduction PHI
206 if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(N: 3))
207 return false;
208
209 // The only pattern accepted is the one in which the reduction PHI
210 // is used as one of the operands of the exit instruction
211 auto *Op0 = Exit->getOperand(i: 0);
212 auto *Op1 = Exit->getOperand(i: 1);
213 if (Kind == RecurKind::FAdd && Op0 != Phi && Op1 != Phi)
214 return false;
215 if (Kind == RecurKind::FMulAdd && Exit->getOperand(i: 2) != Phi)
216 return false;
217
218 LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phi
219 << ", ExitInst: " << *Exit << "\n");
220
221 return true;
222}
223
224// Collect FMF from a value and its associated fcmp in select patterns
225static FastMathFlags collectMinMaxFMF(Value *V) {
226 FastMathFlags FMF = cast<FPMathOperator>(Val: V)->getFastMathFlags();
227 if (auto *Sel = dyn_cast<SelectInst>(Val: V)) {
228 // Accept FMF from either fcmp or select in a min/max idiom.
229 // TODO: Remove this when FMF propagation is fixed or we standardize on
230 // intrinsics.
231 if (auto *FCmp = dyn_cast<FCmpInst>(Val: Sel->getCondition()))
232 FMF |= FCmp->getFastMathFlags();
233 }
234 return FMF;
235}
236
237static std::optional<FastMathFlags>
238hasRequiredFastMathFlags(FPMathOperator *FPOp, RecurKind &RK) {
239 bool HasRequiredFMF = FPOp && FPOp->hasNoNaNs() && FPOp->hasNoSignedZeros();
240 if (HasRequiredFMF)
241 return collectMinMaxFMF(V: FPOp);
242
243 switch (RK) {
244 case RecurKind::FMinimum:
245 case RecurKind::FMaximum:
246 case RecurKind::FMinimumNum:
247 case RecurKind::FMaximumNum:
248 break;
249
250 case RecurKind::FMax:
251 if (!match(V: FPOp, P: m_Intrinsic<Intrinsic::maxnum>(Ops: m_Value(), Ops: m_Value())))
252 return std::nullopt;
253 RK = RecurKind::FMaxNum;
254 break;
255 case RecurKind::FMin:
256 if (!match(V: FPOp, P: m_Intrinsic<Intrinsic::minnum>(Ops: m_Value(), Ops: m_Value())))
257 return std::nullopt;
258 RK = RecurKind::FMinNum;
259 break;
260 default:
261 return std::nullopt;
262 }
263 return collectMinMaxFMF(V: FPOp);
264}
265
266static RecurrenceDescriptor getMinMaxRecurrence(PHINode *Phi, Loop *TheLoop,
267 ScalarEvolution *SE) {
268 Type *Ty = Phi->getType()->getScalarType();
269 BasicBlock *Latch = TheLoop->getLoopLatch();
270 if (Phi->getNumIncomingValues() != 2 ||
271 Phi->getParent() != TheLoop->getHeader() ||
272 (!Ty->isIntegerTy() && !Ty->isFloatingPointTy()) || !Latch)
273 return {};
274
275 auto GetMinMaxRK = [](Value *V, Value *&A, Value *&B) -> RecurKind {
276 if (match(V, P: m_UMin(Op0: m_Value(V&: A), Op1: m_Value(V&: B))))
277 return RecurKind::UMin;
278 if (match(V, P: m_UMax(Op0: m_Value(V&: A), Op1: m_Value(V&: B))))
279 return RecurKind::UMax;
280 if (match(V, P: m_SMax(Op0: m_Value(V&: A), Op1: m_Value(V&: B))))
281 return RecurKind::SMax;
282 if (match(V, P: m_SMin(Op0: m_Value(V&: A), Op1: m_Value(V&: B))))
283 return RecurKind::SMin;
284 if (match(V, P: m_OrdOrUnordFMin(L: m_Value(V&: A), R: m_Value(V&: B))) ||
285 match(V, P: m_Intrinsic<Intrinsic::minnum>(Ops: m_Value(V&: A), Ops: m_Value(V&: B))))
286 return RecurKind::FMin;
287 if (match(V, P: m_OrdOrUnordFMax(L: m_Value(V&: A), R: m_Value(V&: B))) ||
288 match(V, P: m_Intrinsic<Intrinsic::maxnum>(Ops: m_Value(V&: A), Ops: m_Value(V&: B))))
289 return RecurKind::FMax;
290 if (match(V, P: m_FMinimum(Op0: m_Value(V&: A), Op1: m_Value(V&: B))))
291 return RecurKind::FMinimum;
292 if (match(V, P: m_FMaximum(Op0: m_Value(V&: A), Op1: m_Value(V&: B))))
293 return RecurKind::FMaximum;
294 if (match(V, P: m_Intrinsic<Intrinsic::minimumnum>(Ops: m_Value(V&: A), Ops: m_Value(V&: B))))
295 return RecurKind::FMinimumNum;
296 if (match(V, P: m_Intrinsic<Intrinsic::maximumnum>(Ops: m_Value(V&: A), Ops: m_Value(V&: B))))
297 return RecurKind::FMaximumNum;
298 return RecurKind::None;
299 };
300
301 FastMathFlags FMF = FastMathFlags::getFast();
302 Value *BackedgeValue = Phi->getIncomingValueForBlock(BB: Latch);
303 RecurKind RK = RecurKind::None;
304 // Walk def-use chains upwards from BackedgeValue to identify min/max
305 // recurrences.
306 SmallVector<Value *> WorkList({BackedgeValue});
307 SmallPtrSet<Value *, 8> Chain({Phi});
308 while (!WorkList.empty()) {
309 Value *Cur = WorkList.pop_back_val();
310 if (!Chain.insert(Ptr: Cur).second)
311 continue;
312 auto *I = dyn_cast<Instruction>(Val: Cur);
313 if (!I || !TheLoop->contains(Inst: I))
314 return {};
315 if (auto *PN = dyn_cast<PHINode>(Val: I)) {
316 append_range(C&: WorkList, R: PN->operands());
317 continue;
318 }
319 Value *A, *B;
320 RecurKind CurRK = GetMinMaxRK(Cur, A, B);
321 if (CurRK == RecurKind::None || (RK != RecurKind::None && CurRK != RK))
322 return {};
323
324 RK = CurRK;
325 // Check required fast-math flags for FP recurrences.
326 if (RecurrenceDescriptor::isFPMinMaxRecurrenceKind(Kind: CurRK)) {
327 auto CurFMF = hasRequiredFastMathFlags(FPOp: cast<FPMathOperator>(Val: Cur), RK);
328 if (!CurFMF)
329 return {};
330 FMF &= *CurFMF;
331 }
332
333 if (auto *SI = dyn_cast<SelectInst>(Val: I))
334 Chain.insert(Ptr: SI->getCondition());
335
336 if (A == Phi || B == Phi)
337 continue;
338
339 // Add operand to worklist if it matches the pattern (exactly one must
340 // match)
341 Value *X, *Y;
342 auto *IA = dyn_cast<Instruction>(Val: A);
343 auto *IB = dyn_cast<Instruction>(Val: B);
344 bool AMatches = IA && TheLoop->contains(Inst: IA) && GetMinMaxRK(A, X, Y) == RK;
345 bool BMatches = IB && TheLoop->contains(Inst: IB) && GetMinMaxRK(B, X, Y) == RK;
346 if (AMatches == BMatches) // Both or neither match
347 return {};
348 WorkList.push_back(Elt: AMatches ? A : B);
349 }
350
351 // Handle argmin/argmax pattern: PHI has uses outside the reduction chain
352 // that are not intermediate min/max operations (which are handled below).
353 // Requires integer min/max, and the PHI must be the only in-loop user of
354 // BackedgeValue (so vectorizer can handle both PHIs together).
355 bool PhiHasInvalidUses = any_of(Range: Phi->users(), P: [&](Instruction *U) {
356 Value *A, *B;
357 return !Chain.contains(Ptr: U) && TheLoop->contains(Inst: U) &&
358 GetMinMaxRK(U, A, B) == RecurKind::None;
359 });
360 if (PhiHasInvalidUses) {
361 if (!RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind: RK) ||
362 any_of(Range: BackedgeValue->users(), P: [&](User *U) {
363 auto *UI = cast<Instruction>(Val: U);
364 return UI != Phi && TheLoop->contains(Inst: UI);
365 }))
366 return {};
367 return RecurrenceDescriptor(
368 Phi->getIncomingValueForBlock(BB: TheLoop->getLoopPreheader()),
369 /*Exit=*/nullptr, /*Store=*/nullptr, RK, FastMathFlags(),
370 /*ExactFP=*/nullptr, Phi->getType(), /*IsMultiUse=*/true);
371 }
372
373 // Validate chain entries and collect stores from chain entries and
374 // intermediate ops.
375 SmallVector<StoreInst *> Stores;
376 for (Value *V : Chain) {
377 for (User *U : V->users()) {
378 if (Chain.contains(Ptr: U))
379 continue;
380 auto *I = dyn_cast<Instruction>(Val: U);
381 if (!I || (!TheLoop->contains(Inst: I) && V != BackedgeValue))
382 return {};
383 if (!TheLoop->contains(Inst: I))
384 continue;
385 if (auto *SI = dyn_cast<StoreInst>(Val: I)) {
386 Stores.push_back(Elt: SI);
387 continue;
388 }
389 // Must be intermediate min/max of the same kind.
390 Value *A, *B;
391 if (GetMinMaxRK(I, A, B) != RK)
392 return {};
393 for (User *IU : I->users()) {
394 if (auto *SI = dyn_cast<StoreInst>(Val: IU))
395 Stores.push_back(Elt: SI);
396 else if (!Chain.contains(Ptr: IU))
397 return {};
398 }
399 }
400 }
401
402 // Validate all stores go to same invariant address and are in the same block.
403 StoreInst *IntermediateStore = nullptr;
404 const SCEV *StorePtrSCEV = nullptr;
405 for (StoreInst *SI : Stores) {
406 if (!SE)
407 return {};
408 const SCEV *Ptr = SE->getSCEV(V: SI->getPointerOperand());
409 if (!SE->isLoopInvariant(S: Ptr, L: TheLoop) ||
410 (StorePtrSCEV && StorePtrSCEV != Ptr))
411 return {};
412 StorePtrSCEV = Ptr;
413 if (!IntermediateStore)
414 IntermediateStore = SI;
415 else if (IntermediateStore->getParent() != SI->getParent())
416 return {};
417 else if (IntermediateStore->comesBefore(Other: SI))
418 IntermediateStore = SI;
419 }
420
421 // The vectorizer replaces the per-iteration store to the invariant address
422 // with a single store of the final reduced value in the middle block. That is
423 // only correct if the store stores the reduction value itself. If it stores a
424 // value derived from it (e.g. `%other = smax(%phi, 42); store %other`), that
425 // value observes the per-iteration running min/max, so replacing it with the
426 // final reduction value would miscompile. Mirrors the check in
427 // AddReductionVar.
428 if (IntermediateStore &&
429 IntermediateStore->getValueOperand() != BackedgeValue)
430 return {};
431
432 return RecurrenceDescriptor(
433 Phi->getIncomingValueForBlock(BB: TheLoop->getLoopPreheader()),
434 cast<Instruction>(Val: BackedgeValue), IntermediateStore, RK, FMF, nullptr,
435 Phi->getType());
436}
437
438// This matches a phi that selects between the original value (HeaderPhi) and an
439// arbitrary non-reduction value.
440static bool isFindLastLikePhi(PHINode *Phi, PHINode *HeaderPhi,
441 SmallPtrSetImpl<Instruction *> &ReductionInstrs) {
442 unsigned NumNonReduxInputs = 0;
443 for (const Value *Op : Phi->operands()) {
444 if (!ReductionInstrs.contains(Ptr: dyn_cast<Instruction>(Val: Op))) {
445 if (++NumNonReduxInputs > 1)
446 return false;
447 } else if (Op != HeaderPhi) {
448 // TODO: Remove this restriction once chained phis are supported.
449 return false;
450 }
451 }
452 return NumNonReduxInputs == 1;
453}
454
455bool RecurrenceDescriptor::AddReductionVar(
456 PHINode *Phi, RecurKind Kind, Loop *TheLoop, RecurrenceDescriptor &RedDes,
457 DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT,
458 ScalarEvolution *SE) {
459 if (Phi->getNumIncomingValues() != 2)
460 return false;
461
462 // Reduction variables are only found in the loop header block.
463 if (Phi->getParent() != TheLoop->getHeader())
464 return false;
465
466 // Obtain the reduction start value from the value that comes from the loop
467 // preheader.
468 if (!TheLoop->getLoopPreheader())
469 return false;
470
471 Value *RdxStart = Phi->getIncomingValueForBlock(BB: TheLoop->getLoopPreheader());
472 // ExitInstruction is the single value which is used outside the loop.
473 // We only allow for a single reduction value to be used outside the loop.
474 // This includes users of the reduction, variables (which form a cycle
475 // which ends in the phi node).
476 Instruction *ExitInstruction = nullptr;
477
478 // Variable to keep last visited store instruction. By the end of the
479 // algorithm this variable will be either empty or having intermediate
480 // reduction value stored in invariant address.
481 StoreInst *IntermediateStore = nullptr;
482
483 // Indicates that we found a reduction operation in our scan.
484 bool FoundReduxOp = false;
485
486 // We start with the PHI node and scan for all of the users of this
487 // instruction. All users must be instructions that can be used as reduction
488 // variables (such as ADD). We must have a single out-of-block user. The cycle
489 // must include the original PHI.
490 bool FoundStartPHI = false;
491
492 // To recognize AnyOf patterns formed by a icmp select sequence, we store
493 // the number of instruction we saw to make sure we only see one.
494 unsigned NumCmpSelectPatternInst = 0;
495 InstDesc ReduxDesc(false, nullptr);
496
497 // To recognize find-lasts of conditional operations (such as loads or
498 // divides), that need masking, we track non-phi users and if we've found a
499 // "find-last-like" phi (see isFindLastLikePhi). We currently only support
500 // find-last reduction chains with a single "find-last-like" phi and do not
501 // allow any other operations.
502 [[maybe_unused]] unsigned NumNonPHIUsers = 0;
503 bool FoundFindLastLikePhi = false;
504
505 // Data used for determining if the recurrence has been type-promoted.
506 Type *RecurrenceType = Phi->getType();
507 SmallPtrSet<Instruction *, 4> CastInsts;
508 Type *MinWidthCastToRecurrenceType = nullptr;
509 Instruction *Start = Phi;
510 bool IsSigned = false;
511
512 SmallPtrSet<Instruction *, 8> VisitedInsts;
513 SmallVector<Instruction *, 8> Worklist;
514
515 // Return early if the recurrence kind does not match the type of Phi. If the
516 // recurrence kind is arithmetic, we attempt to look through AND operations
517 // resulting from the type promotion performed by InstCombine. Vector
518 // operations are not limited to the legal integer widths, so we may be able
519 // to evaluate the reduction in the narrower width.
520 // Check the scalar type to handle both scalar and vector types.
521 Type *ScalarTy = RecurrenceType->getScalarType();
522 if (Kind == RecurKind::FindLast) {
523 // FindLast supports all primitive scalar types.
524 if (!ScalarTy->isFloatingPointTy() && !ScalarTy->isIntegerTy() &&
525 !ScalarTy->isPointerTy())
526 return false;
527 } else if (ScalarTy->isFloatingPointTy()) {
528 if (!isFloatingPointRecurrenceKind(Kind))
529 return false;
530 } else if (ScalarTy->isIntegerTy()) {
531 if (!isIntegerRecurrenceKind(Kind))
532 return false;
533 Start = lookThroughAnd(Phi, RT&: RecurrenceType, Visited&: VisitedInsts, CI&: CastInsts);
534 } else {
535 // Pointer min/max may exist, but it is not supported as a reduction op.
536 return false;
537 }
538
539 Worklist.push_back(Elt: Start);
540 VisitedInsts.insert(Ptr: Start);
541
542 // Start with all flags set because we will intersect this with the reduction
543 // flags from all the reduction operations.
544 FastMathFlags FMF = FastMathFlags::getFast();
545
546 // The first instruction in the use-def chain of the Phi node that requires
547 // exact floating point operations.
548 Instruction *ExactFPMathInst = nullptr;
549
550 // A value in the reduction can be used:
551 // - By the reduction:
552 // - Reduction operation:
553 // - One use of reduction value (safe).
554 // - Multiple use of reduction value (not safe).
555 // - PHI:
556 // - All uses of the PHI must be the reduction (safe).
557 // - Otherwise, not safe.
558 // - By instructions outside of the loop (safe).
559 // * One value may have several outside users, but all outside
560 // uses must be of the same value.
561 // - By store instructions with a loop invariant address (safe with
562 // the following restrictions):
563 // * If there are several stores, all must have the same address.
564 // * Final value should be stored in that loop invariant address.
565 // - By an instruction that is not part of the reduction (not safe).
566 // This is either:
567 // * An instruction type other than PHI or the reduction operation.
568 // * A PHI in the header other than the initial PHI.
569 while (!Worklist.empty()) {
570 Instruction *Cur = Worklist.pop_back_val();
571
572 // Store instructions are allowed iff it is the store of the reduction
573 // value to the same loop invariant memory location.
574 if (auto *SI = dyn_cast<StoreInst>(Val: Cur)) {
575 if (!SE) {
576 LLVM_DEBUG(dbgs() << "Store instructions are not processed without "
577 << "Scalar Evolution Analysis\n");
578 return false;
579 }
580
581 const SCEV *PtrScev = SE->getSCEV(V: SI->getPointerOperand());
582 // Check it is the same address as previous stores
583 if (IntermediateStore) {
584 const SCEV *OtherScev =
585 SE->getSCEV(V: IntermediateStore->getPointerOperand());
586
587 if (OtherScev != PtrScev) {
588 LLVM_DEBUG(dbgs() << "Storing reduction value to different addresses "
589 << "inside the loop: " << *SI->getPointerOperand()
590 << " and "
591 << *IntermediateStore->getPointerOperand() << '\n');
592 return false;
593 }
594 }
595
596 // Check the pointer is loop invariant
597 if (!SE->isLoopInvariant(S: PtrScev, L: TheLoop)) {
598 LLVM_DEBUG(dbgs() << "Storing reduction value to non-uniform address "
599 << "inside the loop: " << *SI->getPointerOperand()
600 << '\n');
601 return false;
602 }
603
604 // IntermediateStore is always the last store in the loop.
605 IntermediateStore = SI;
606 continue;
607 }
608
609 // No Users.
610 // If the instruction has no users then this is a broken chain and can't be
611 // a reduction variable.
612 if (Cur->use_empty())
613 return false;
614
615 bool IsAPhi = isa<PHINode>(Val: Cur);
616 if (!IsAPhi)
617 ++NumNonPHIUsers;
618
619 // A header PHI use other than the original PHI.
620 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
621 return false;
622
623 // Reductions of instructions such as Div, and Sub is only possible if the
624 // LHS is the reduction variable.
625 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Val: Cur) &&
626 !isa<ICmpInst>(Val: Cur) && !isa<FCmpInst>(Val: Cur) &&
627 !VisitedInsts.count(Ptr: dyn_cast<Instruction>(Val: Cur->getOperand(i: 0))))
628 return false;
629
630 // Any reduction instruction must be of one of the allowed kinds. We ignore
631 // the starting value (the Phi or an AND instruction if the Phi has been
632 // type-promoted).
633 if (Cur != Start) {
634 ReduxDesc = isRecurrenceInstr(L: TheLoop, Phi, I: Cur, Kind, Prev&: ReduxDesc, SE);
635 ExactFPMathInst = ExactFPMathInst == nullptr
636 ? ReduxDesc.getExactFPMathInst()
637 : ExactFPMathInst;
638 if (!ReduxDesc.isRecurrence())
639 return false;
640 // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
641 if (isa<FPMathOperator>(Val: ReduxDesc.getPatternInst()) && !IsAPhi)
642 FMF &= collectMinMaxFMF(V: ReduxDesc.getPatternInst());
643 // Update this reduction kind if we matched a new instruction.
644 // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind'
645 // state accurate while processing the worklist?
646 if (ReduxDesc.getRecKind() != RecurKind::None)
647 Kind = ReduxDesc.getRecKind();
648 }
649
650 bool IsASelect = isa<SelectInst>(Val: Cur);
651
652 // A conditional reduction operation must only have 2 or less uses in
653 // VisitedInsts.
654 if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) &&
655 hasMultipleUsesOf(I: Cur, Insts&: VisitedInsts, MaxNumUses: 2))
656 return false;
657
658 // A reduction operation must only have one use of the reduction value.
659 if (!IsAPhi && !IsASelect && !isAnyOfRecurrenceKind(Kind) &&
660 hasMultipleUsesOf(I: Cur, Insts&: VisitedInsts, MaxNumUses: 1))
661 return false;
662
663 // All inputs to a PHI node must be a reduction value, unless the phi is a
664 // "FindLast-like" phi (described below).
665 if (IsAPhi && Cur != Phi) {
666 if (!areAllUsesIn(I: Cur, Set&: VisitedInsts)) {
667 // A "FindLast-like" phi acts like a conditional select between the
668 // previous reduction value, and an arbitrary value. Note: Multiple
669 // "FindLast-like" phis are not supported see:
670 // IVDescriptorsTest.UnsupportedFindLastPhi.
671 FoundFindLastLikePhi =
672 Kind == RecurKind::FindLast && !FoundFindLastLikePhi &&
673 isFindLastLikePhi(Phi: cast<PHINode>(Val: Cur), HeaderPhi: Phi, ReductionInstrs&: VisitedInsts);
674 if (!FoundFindLastLikePhi)
675 return false;
676 }
677 }
678
679 if (isAnyOfRecurrenceKind(Kind) && IsASelect)
680 ++NumCmpSelectPatternInst;
681
682 // Check whether we found a reduction operator.
683 FoundReduxOp |= (!IsAPhi || FoundFindLastLikePhi) && Cur != Start;
684
685 // Process users of current instruction. Push non-PHI nodes after PHI nodes
686 // onto the stack. This way we are going to have seen all inputs to PHI
687 // nodes once we get to them.
688 SmallVector<Instruction *, 8> NonPHIs;
689 SmallVector<Instruction *, 8> PHIs;
690 for (User *U : Cur->users()) {
691 Instruction *UI = cast<Instruction>(Val: U);
692
693 // If the user is a call to llvm.fmuladd then the instruction can only be
694 // the final operand.
695 if (isFMulAddIntrinsic(I: UI))
696 if (Cur == UI->getOperand(i: 0) || Cur == UI->getOperand(i: 1))
697 return false;
698
699 // Check if we found the exit user.
700 BasicBlock *Parent = UI->getParent();
701 if (!TheLoop->contains(BB: Parent)) {
702 // If we already know this instruction is used externally, move on to
703 // the next user.
704 if (ExitInstruction == Cur)
705 continue;
706
707 // Exit if you find multiple values used outside or if the header phi
708 // node is being used. In this case the user uses the value of the
709 // previous iteration, in which case we would loose "VF-1" iterations of
710 // the reduction operation if we vectorize.
711 if (ExitInstruction != nullptr || Cur == Phi)
712 return false;
713
714 // The instruction used by an outside user must be the last instruction
715 // before we feed back to the reduction phi. Otherwise, we loose VF-1
716 // operations on the value.
717 if (!is_contained(Range: Phi->operands(), Element: Cur))
718 return false;
719
720 ExitInstruction = Cur;
721 continue;
722 }
723
724 // Process instructions only once (termination). Each reduction cycle
725 // value must only be used once, except by phi nodes and conditional
726 // reductions which are represented as a cmp followed by a select.
727 InstDesc IgnoredVal(false, nullptr);
728 if (VisitedInsts.insert(Ptr: UI).second) {
729 if (isa<PHINode>(Val: UI)) {
730 PHIs.push_back(Elt: UI);
731 } else {
732 StoreInst *SI = dyn_cast<StoreInst>(Val: UI);
733 if (SI && SI->getPointerOperand() == Cur) {
734 // Reduction variable chain can only be stored somewhere but it
735 // can't be used as an address.
736 return false;
737 }
738 NonPHIs.push_back(Elt: UI);
739 }
740 } else if (!isa<PHINode>(Val: UI) &&
741 ((!isConditionalRdxPattern(I: UI).isRecurrence() &&
742 !isAnyOfPattern(Loop: TheLoop, OrigPhi: Phi, I: UI, Prev&: IgnoredVal)
743 .isRecurrence())))
744 return false;
745
746 // Remember that we completed the cycle.
747 if (UI == Phi)
748 FoundStartPHI = true;
749 }
750 Worklist.append(in_start: PHIs.begin(), in_end: PHIs.end());
751 Worklist.append(in_start: NonPHIs.begin(), in_end: NonPHIs.end());
752 }
753
754 // We only expect to match a single "find-last-like" phi per find-last
755 // reduction, with no non-phi operations in the reduction use chain.
756 assert((!FoundFindLastLikePhi ||
757 (Kind == RecurKind::FindLast && NumNonPHIUsers == 0)) &&
758 "Unexpectedly matched a 'find-last-like' phi");
759
760 if (isAnyOfRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1)
761 return false;
762
763 if (IntermediateStore) {
764 // Check that stored value goes to the phi node again. This way we make sure
765 // that the value stored in IntermediateStore is indeed the final reduction
766 // value.
767 if (!is_contained(Range: Phi->operands(), Element: IntermediateStore->getValueOperand())) {
768 LLVM_DEBUG(dbgs() << "Not a final reduction value stored: "
769 << *IntermediateStore << '\n');
770 return false;
771 }
772
773 // If there is an exit instruction it's value should be stored in
774 // IntermediateStore
775 if (ExitInstruction &&
776 IntermediateStore->getValueOperand() != ExitInstruction) {
777 LLVM_DEBUG(dbgs() << "Last store Instruction of reduction value does not "
778 "store last calculated value of the reduction: "
779 << *IntermediateStore << '\n');
780 return false;
781 }
782
783 // If all uses are inside the loop (intermediate stores), then the
784 // reduction value after the loop will be the one used in the last store.
785 if (!ExitInstruction)
786 ExitInstruction = cast<Instruction>(Val: IntermediateStore->getValueOperand());
787 }
788
789 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
790 return false;
791
792 const bool IsOrdered =
793 checkOrderedReduction(Kind, ExactFPMathInst, Exit: ExitInstruction, Phi);
794
795 if (Start != Phi) {
796 // If the starting value is not the same as the phi node, we speculatively
797 // looked through an 'and' instruction when evaluating a potential
798 // arithmetic reduction to determine if it may have been type-promoted.
799 //
800 // We now compute the minimal bit width that is required to represent the
801 // reduction. If this is the same width that was indicated by the 'and', we
802 // can represent the reduction in the smaller type. The 'and' instruction
803 // will be eliminated since it will essentially be a cast instruction that
804 // can be ignore in the cost model. If we compute a different type than we
805 // did when evaluating the 'and', the 'and' will not be eliminated, and we
806 // will end up with different kinds of operations in the recurrence
807 // expression (e.g., IntegerAND, IntegerADD). We give up if this is
808 // the case.
809 //
810 // The vectorizer relies on InstCombine to perform the actual
811 // type-shrinking. It does this by inserting instructions to truncate the
812 // exit value of the reduction to the width indicated by RecurrenceType and
813 // then extend this value back to the original width. If IsSigned is false,
814 // a 'zext' instruction will be generated; otherwise, a 'sext' will be
815 // used.
816 //
817 // TODO: We should not rely on InstCombine to rewrite the reduction in the
818 // smaller type. We should just generate a correctly typed expression
819 // to begin with.
820 Type *ComputedType;
821 std::tie(args&: ComputedType, args&: IsSigned) =
822 computeRecurrenceType(Exit: ExitInstruction, DB, AC, DT);
823 if (ComputedType != RecurrenceType)
824 return false;
825 }
826
827 // Collect cast instructions and the minimum width used by the recurrence.
828 // If the starting value is not the same as the phi node and the computed
829 // recurrence type is equal to the recurrence type, the recurrence expression
830 // will be represented in a narrower or wider type. If there are any cast
831 // instructions that will be unnecessary, collect them in CastsFromRecurTy.
832 // Note that the 'and' instruction was already included in this list.
833 //
834 // TODO: A better way to represent this may be to tag in some way all the
835 // instructions that are a part of the reduction. The vectorizer cost
836 // model could then apply the recurrence type to these instructions,
837 // without needing a white list of instructions to ignore.
838 // This may also be useful for the inloop reductions, if it can be
839 // kept simple enough.
840 collectCastInstrs(TheLoop, Exit: ExitInstruction, RecurrenceType, Casts&: CastInsts,
841 MinWidthCastToRecurTy&: MinWidthCastToRecurrenceType);
842
843 // We found a reduction var if we have reached the original phi node and we
844 // only have a single instruction with out-of-loop users.
845
846 // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
847 // is saved as part of the RecurrenceDescriptor.
848
849 // Save the description of this reduction variable.
850 RedDes =
851 RecurrenceDescriptor(RdxStart, ExitInstruction, IntermediateStore, Kind,
852 FMF, ExactFPMathInst, RecurrenceType, IsSigned,
853 IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
854 return true;
855}
856
857// We are looking for loops that do something like this:
858// int r = 0;
859// for (int i = 0; i < n; i++) {
860// if (src[i] > 3)
861// r = 3;
862// }
863// where the reduction value (r) only has two states, in this example 0 or 3.
864// The generated LLVM IR for this type of loop will be like this:
865// for.body:
866// %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
867// ...
868// %cmp = icmp sgt i32 %5, 3
869// %spec.select = select i1 %cmp, i32 3, i32 %r
870// ...
871// In general we can support vectorization of loops where 'r' flips between
872// any two non-constants, provided they are loop invariant. The only thing
873// we actually care about at the end of the loop is whether or not any lane
874// in the selected vector is different from the start value. The final
875// across-vector reduction after the loop simply involves choosing the start
876// value if nothing changed (0 in the example above) or the other selected
877// value (3 in the example above).
878RecurrenceDescriptor::InstDesc
879RecurrenceDescriptor::isAnyOfPattern(Loop *Loop, PHINode *OrigPhi,
880 Instruction *I, InstDesc &Prev) {
881 // We must handle the select(cmp(),x,y) as a single instruction. Advance to
882 // the select.
883 if (match(V: I, P: m_OneUse(SubPattern: m_Cmp()))) {
884 if (auto *Select = dyn_cast<SelectInst>(Val: *I->user_begin()))
885 return InstDesc(Select, Prev.getRecKind());
886 }
887
888 if (!match(V: I, P: m_Select(C: m_Cmp(), L: m_Value(), R: m_Value())))
889 return InstDesc(false, I);
890
891 SelectInst *SI = cast<SelectInst>(Val: I);
892 Value *NonPhi = nullptr;
893
894 if (OrigPhi == dyn_cast<PHINode>(Val: SI->getTrueValue()))
895 NonPhi = SI->getFalseValue();
896 else if (OrigPhi == dyn_cast<PHINode>(Val: SI->getFalseValue()))
897 NonPhi = SI->getTrueValue();
898 else
899 return InstDesc(false, I);
900
901 // We are looking for selects of the form:
902 // select(cmp(), phi, loop_invariant) or
903 // select(cmp(), loop_invariant, phi)
904 if (!Loop->isLoopInvariant(V: NonPhi))
905 return InstDesc(false, I);
906
907 return InstDesc(I, RecurKind::AnyOf);
908}
909
910// We are looking for loops that do something like this:
911// int r = 0;
912// for (int i = 0; i < n; i++) {
913// if (src[i] > 3)
914// r = i;
915// }
916// or like this:
917// int r = 0;
918// for (int i = 0; i < n; i++) {
919// if (src[i] > 3)
920// r = <loop-varying value>;
921// }
922// The reduction value (r) is derived from either the values of an induction
923// variable (i) sequence, an arbitrary loop-varying value, or from the start
924// value (0). The LLVM IR generated for such loops would be as follows:
925// for.body:
926// %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
927// %i = phi i32 [ %inc, %for.body ], [ 0, %entry ]
928// ...
929// %cmp = icmp sgt i32 %5, 3
930// %spec.select = select i1 %cmp, i32 %i, i32 %r
931// %inc = add nsw i32 %i, 1
932// ...
933//
934// When searching for an arbitrary loop-varying value, the reduction value will
935// either be the initial value (0) if the condition was never met, or the value
936// of the loop-varying value in the most recent loop iteration where the
937// condition was met.
938RecurrenceDescriptor::InstDesc
939RecurrenceDescriptor::isFindPattern(Loop *TheLoop, PHINode *OrigPhi,
940 Instruction *I, ScalarEvolution &SE) {
941 // TODO: Support the vectorization of FindLastIV when the reduction phi is
942 // used by more than one select instruction. This vectorization is only
943 // performed when the SCEV of each increasing induction variable used by the
944 // select instructions is identical.
945 if (!OrigPhi->hasOneUse())
946 return InstDesc(false, I);
947
948 // We are looking for selects of the form:
949 // select(cmp(), phi, value) or
950 // select(cmp(), value, phi)
951 if (!match(V: I, P: m_CombineOr(Ps: m_Select(C: m_Cmp(), L: m_Value(), R: m_Specific(V: OrigPhi)),
952 Ps: m_Select(C: m_Cmp(), L: m_Specific(V: OrigPhi), R: m_Value()))))
953 return InstDesc(false, I);
954
955 return InstDesc(I, RecurKind::FindLast);
956}
957
958/// Returns true if the select instruction has users in the compare-and-add
959/// reduction pattern below. The select instruction argument is the last one
960/// in the sequence.
961///
962/// %sum.1 = phi ...
963/// ...
964/// %cmp = fcmp pred %0, %CFP
965/// %add = fadd %0, %sum.1
966/// %sum.2 = select %cmp, %add, %sum.1
967RecurrenceDescriptor::InstDesc
968RecurrenceDescriptor::isConditionalRdxPattern(Instruction *I) {
969 Value *TrueVal, *FalseVal;
970 // Only handle single use cases for now.
971 if (!match(V: I,
972 P: m_Select(C: m_OneUse(SubPattern: m_Cmp()), L: m_Value(V&: TrueVal), R: m_Value(V&: FalseVal))))
973 return InstDesc(false, I);
974
975 // Handle only when either of operands of select instruction is a PHI
976 // node for now.
977 if ((isa<PHINode>(Val: TrueVal) && isa<PHINode>(Val: FalseVal)) ||
978 (!isa<PHINode>(Val: TrueVal) && !isa<PHINode>(Val: FalseVal)))
979 return InstDesc(false, I);
980
981 Instruction *I1 = isa<PHINode>(Val: TrueVal) ? dyn_cast<Instruction>(Val: FalseVal)
982 : dyn_cast<Instruction>(Val: TrueVal);
983 if (!I1 || !I1->isBinaryOp())
984 return InstDesc(false, I);
985
986 Value *Op1, *Op2;
987 if (!(((m_FAdd(L: m_Value(V&: Op1), R: m_Value(V&: Op2)).match(V: I1) ||
988 m_FSub(L: m_Value(V&: Op1), R: m_Value(V&: Op2)).match(V: I1)) &&
989 I1->isFast()) ||
990 (m_FMul(L: m_Value(V&: Op1), R: m_Value(V&: Op2)).match(V: I1) && (I1->isFast())) ||
991 ((m_Add(L: m_Value(V&: Op1), R: m_Value(V&: Op2)).match(V: I1) ||
992 m_Sub(L: m_Value(V&: Op1), R: m_Value(V&: Op2)).match(V: I1))) ||
993 (m_Mul(L: m_Value(V&: Op1), R: m_Value(V&: Op2)).match(V: I1))))
994 return InstDesc(false, I);
995
996 Instruction *IPhi = isa<PHINode>(Val: Op1) ? dyn_cast<Instruction>(Val: Op1)
997 : dyn_cast<Instruction>(Val: Op2);
998 if (!IPhi || IPhi != FalseVal)
999 return InstDesc(false, I);
1000
1001 return InstDesc(true, I);
1002}
1003
1004RecurrenceDescriptor::InstDesc
1005RecurrenceDescriptor::isRecurrenceInstr(Loop *L, PHINode *OrigPhi,
1006 Instruction *I, RecurKind Kind,
1007 InstDesc &Prev, ScalarEvolution *SE) {
1008 assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind);
1009 switch (I->getOpcode()) {
1010 default:
1011 return InstDesc(false, I);
1012 case Instruction::PHI:
1013 return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
1014 case Instruction::Sub:
1015 return InstDesc(
1016 Kind == RecurKind::Sub || Kind == RecurKind::AddChainWithSubs, I);
1017 case Instruction::Add:
1018 return InstDesc(
1019 Kind == RecurKind::Add || Kind == RecurKind::AddChainWithSubs, I);
1020 case Instruction::Mul:
1021 return InstDesc(Kind == RecurKind::Mul, I);
1022 case Instruction::And:
1023 return InstDesc(Kind == RecurKind::And, I);
1024 case Instruction::Or:
1025 return InstDesc(Kind == RecurKind::Or, I);
1026 case Instruction::Xor:
1027 return InstDesc(Kind == RecurKind::Xor, I);
1028 case Instruction::FDiv:
1029 case Instruction::FMul:
1030 return InstDesc(Kind == RecurKind::FMul, I,
1031 I->hasAllowReassoc() ? nullptr : I);
1032 case Instruction::FSub:
1033 return InstDesc(Kind == RecurKind::FSub ||
1034 Kind == RecurKind::FAddChainWithSubs,
1035 I, I->hasAllowReassoc() ? nullptr : I);
1036 case Instruction::FAdd:
1037 return InstDesc(Kind == RecurKind::FAdd ||
1038 Kind == RecurKind::FAddChainWithSubs,
1039 I, I->hasAllowReassoc() ? nullptr : I);
1040 case Instruction::Select:
1041 if (isSubRecurrenceKind(Kind) || Kind == RecurKind::FAdd ||
1042 Kind == RecurKind::FMul || Kind == RecurKind::Add ||
1043 Kind == RecurKind::Mul || Kind == RecurKind::AddChainWithSubs ||
1044 Kind == RecurKind::FAddChainWithSubs)
1045 return isConditionalRdxPattern(I);
1046 if (isFindRecurrenceKind(Kind) && SE)
1047 return isFindPattern(TheLoop: L, OrigPhi, I, SE&: *SE);
1048 [[fallthrough]];
1049 case Instruction::FCmp:
1050 case Instruction::ICmp:
1051 case Instruction::Call:
1052 if (isAnyOfRecurrenceKind(Kind))
1053 return isAnyOfPattern(Loop: L, OrigPhi, I, Prev);
1054 if (isFMulAddIntrinsic(I))
1055 return InstDesc(Kind == RecurKind::FMulAdd, I,
1056 I->hasAllowReassoc() ? nullptr : I);
1057 return InstDesc(false, I);
1058 }
1059}
1060
1061bool RecurrenceDescriptor::hasMultipleUsesOf(
1062 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
1063 unsigned MaxNumUses) {
1064 unsigned NumUses = 0;
1065 for (const Use &U : I->operands()) {
1066 if (Insts.count(Ptr: dyn_cast<Instruction>(Val: U)))
1067 ++NumUses;
1068 if (NumUses > MaxNumUses)
1069 return true;
1070 }
1071
1072 return false;
1073}
1074
1075bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
1076 RecurrenceDescriptor &RedDes,
1077 DemandedBits *DB, AssumptionCache *AC,
1078 DominatorTree *DT,
1079 ScalarEvolution *SE) {
1080 if (AddReductionVar(Phi, Kind: RecurKind::Add, TheLoop, RedDes, DB, AC, DT, SE)) {
1081 LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
1082 return true;
1083 }
1084 if (AddReductionVar(Phi, Kind: RecurKind::Sub, TheLoop, RedDes, DB, AC, DT, SE)) {
1085 LLVM_DEBUG(dbgs() << "Found a SUB reduction PHI." << *Phi << "\n");
1086 return true;
1087 }
1088 if (AddReductionVar(Phi, Kind: RecurKind::AddChainWithSubs, TheLoop, RedDes, DB, AC,
1089 DT, SE)) {
1090 LLVM_DEBUG(dbgs() << "Found a chained ADD-SUB reduction PHI." << *Phi
1091 << "\n");
1092 return true;
1093 }
1094 if (AddReductionVar(Phi, Kind: RecurKind::Mul, TheLoop, RedDes, DB, AC, DT, SE)) {
1095 LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
1096 return true;
1097 }
1098 if (AddReductionVar(Phi, Kind: RecurKind::Or, TheLoop, RedDes, DB, AC, DT, SE)) {
1099 LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
1100 return true;
1101 }
1102 if (AddReductionVar(Phi, Kind: RecurKind::And, TheLoop, RedDes, DB, AC, DT, SE)) {
1103 LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
1104 return true;
1105 }
1106 if (AddReductionVar(Phi, Kind: RecurKind::Xor, TheLoop, RedDes, DB, AC, DT, SE)) {
1107 LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
1108 return true;
1109 }
1110 auto RD = getMinMaxRecurrence(Phi, TheLoop, SE);
1111 if (RD.getRecurrenceKind() != RecurKind::None) {
1112 assert(
1113 RecurrenceDescriptor::isMinMaxRecurrenceKind(RD.getRecurrenceKind()) &&
1114 "Expected a min/max recurrence kind");
1115 LLVM_DEBUG(dbgs() << "Found a min/max reduction PHI." << *Phi << "\n");
1116 RedDes = std::move(RD);
1117 return true;
1118 }
1119 if (AddReductionVar(Phi, Kind: RecurKind::AnyOf, TheLoop, RedDes, DB, AC, DT, SE)) {
1120 LLVM_DEBUG(dbgs() << "Found a conditional select reduction PHI." << *Phi
1121 << "\n");
1122 return true;
1123 }
1124 if (AddReductionVar(Phi, Kind: RecurKind::FindLast, TheLoop, RedDes, DB, AC, DT,
1125 SE)) {
1126 LLVM_DEBUG(dbgs() << "Found a Find reduction PHI." << *Phi << "\n");
1127 return true;
1128 }
1129 if (AddReductionVar(Phi, Kind: RecurKind::FMul, TheLoop, RedDes, DB, AC, DT, SE)) {
1130 LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
1131 return true;
1132 }
1133 if (AddReductionVar(Phi, Kind: RecurKind::FSub, TheLoop, RedDes, DB, AC, DT, SE)) {
1134 LLVM_DEBUG(dbgs() << "Found an FSub reduction PHI." << *Phi << "\n");
1135 return true;
1136 }
1137 if (AddReductionVar(Phi, Kind: RecurKind::FAdd, TheLoop, RedDes, DB, AC, DT, SE)) {
1138 LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
1139 return true;
1140 }
1141 if (AddReductionVar(Phi, Kind: RecurKind::FAddChainWithSubs, TheLoop, RedDes, DB,
1142 AC, DT, SE)) {
1143 LLVM_DEBUG(dbgs() << "Found a chained FADD-FSUB chained reduction PHI."
1144 << *Phi << "\n");
1145 return true;
1146 }
1147 if (AddReductionVar(Phi, Kind: RecurKind::FMulAdd, TheLoop, RedDes, DB, AC, DT,
1148 SE)) {
1149 LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n");
1150 return true;
1151 }
1152
1153 // Not a reduction of known type.
1154 return false;
1155}
1156
1157bool RecurrenceDescriptor::isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop,
1158 DominatorTree *DT) {
1159
1160 // Ensure the phi node is in the loop header and has two incoming values.
1161 if (Phi->getParent() != TheLoop->getHeader() ||
1162 Phi->getNumIncomingValues() != 2)
1163 return false;
1164
1165 // Ensure the loop has a preheader and a single latch block. The loop
1166 // vectorizer will need the latch to set up the next iteration of the loop.
1167 auto *Preheader = TheLoop->getLoopPreheader();
1168 auto *Latch = TheLoop->getLoopLatch();
1169 if (!Preheader || !Latch)
1170 return false;
1171
1172 // Ensure the phi node's incoming blocks are the loop preheader and latch.
1173 if (Phi->getBasicBlockIndex(BB: Preheader) < 0 ||
1174 Phi->getBasicBlockIndex(BB: Latch) < 0)
1175 return false;
1176
1177 // Get the previous value. The previous value comes from the latch edge while
1178 // the initial value comes from the preheader edge.
1179 auto *Previous = dyn_cast<Instruction>(Val: Phi->getIncomingValueForBlock(BB: Latch));
1180
1181 // If Previous is a phi in the header, go through incoming values from the
1182 // latch until we find a non-phi value. Use this as the new Previous, all uses
1183 // in the header will be dominated by the original phi, but need to be moved
1184 // after the non-phi previous value.
1185 SmallPtrSet<PHINode *, 4> SeenPhis;
1186 while (auto *PrevPhi = dyn_cast_or_null<PHINode>(Val: Previous)) {
1187 if (PrevPhi->getParent() != Phi->getParent())
1188 return false;
1189 if (!SeenPhis.insert(Ptr: PrevPhi).second)
1190 return false;
1191 Previous = dyn_cast<Instruction>(Val: PrevPhi->getIncomingValueForBlock(BB: Latch));
1192 }
1193
1194 if (!Previous || isa<PHINode>(Val: Previous))
1195 return false;
1196
1197 // Handle recurrences with a loop-invariant latch value.
1198 if (!TheLoop->contains(Inst: Previous)) {
1199 assert(DT->dominates(Previous, Phi) &&
1200 "loop-invariant latch value must dominate the header phi");
1201 return true;
1202 }
1203
1204 // Ensure every user of the phi node (recursively) is dominated by the
1205 // previous value. The dominance requirement ensures the loop vectorizer will
1206 // not need to vectorize the initial value prior to the first iteration of the
1207 // loop.
1208 // TODO: Consider extending this sinking to handle memory instructions.
1209
1210 SmallPtrSet<Value *, 8> Seen;
1211 BasicBlock *PhiBB = Phi->getParent();
1212 SmallVector<Instruction *, 8> WorkList;
1213 auto TryToPushSinkCandidate = [&](Instruction *SinkCandidate) {
1214 // Cyclic dependence.
1215 if (Previous == SinkCandidate)
1216 return false;
1217
1218 if (!Seen.insert(Ptr: SinkCandidate).second)
1219 return true;
1220 if (DT->dominates(Def: Previous,
1221 User: SinkCandidate)) // We already are good w/o sinking.
1222 return true;
1223
1224 if (SinkCandidate->getParent() != PhiBB ||
1225 SinkCandidate->mayHaveSideEffects() ||
1226 SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
1227 return false;
1228
1229 // If we reach a PHI node that is not dominated by Previous, we reached a
1230 // header PHI. No need for sinking.
1231 if (isa<PHINode>(Val: SinkCandidate))
1232 return true;
1233
1234 // Sink User tentatively and check its users
1235 WorkList.push_back(Elt: SinkCandidate);
1236 return true;
1237 };
1238
1239 WorkList.push_back(Elt: Phi);
1240 // Try to recursively sink instructions and their users after Previous.
1241 while (!WorkList.empty()) {
1242 Instruction *Current = WorkList.pop_back_val();
1243 for (User *User : Current->users()) {
1244 if (!TryToPushSinkCandidate(cast<Instruction>(Val: User)))
1245 return false;
1246 }
1247 }
1248
1249 return true;
1250}
1251
1252unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
1253 switch (Kind) {
1254 case RecurKind::Sub:
1255 return Instruction::Sub;
1256 case RecurKind::AddChainWithSubs:
1257 case RecurKind::Add:
1258 return Instruction::Add;
1259 case RecurKind::Mul:
1260 return Instruction::Mul;
1261 case RecurKind::Or:
1262 return Instruction::Or;
1263 case RecurKind::And:
1264 return Instruction::And;
1265 case RecurKind::Xor:
1266 return Instruction::Xor;
1267 case RecurKind::FMul:
1268 return Instruction::FMul;
1269 case RecurKind::FMulAdd:
1270 case RecurKind::FAddChainWithSubs:
1271 case RecurKind::FAdd:
1272 return Instruction::FAdd;
1273 case RecurKind::FSub:
1274 return Instruction::FSub;
1275 case RecurKind::SMax:
1276 case RecurKind::SMin:
1277 case RecurKind::UMax:
1278 case RecurKind::UMin:
1279 return Instruction::ICmp;
1280 case RecurKind::FMax:
1281 case RecurKind::FMin:
1282 case RecurKind::FMaximum:
1283 case RecurKind::FMinimum:
1284 case RecurKind::FMaximumNum:
1285 case RecurKind::FMinimumNum:
1286 return Instruction::FCmp;
1287 case RecurKind::FindLast:
1288 case RecurKind::AnyOf:
1289 case RecurKind::FindIV:
1290 // TODO: Set AnyOf and FindIV to Instruction::Select once in-loop reductions
1291 // are supported.
1292 default:
1293 llvm_unreachable("Unknown recurrence operation");
1294 }
1295}
1296
1297SmallVector<Instruction *, 4>
1298RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {
1299 SmallVector<Instruction *, 4> ReductionOperations;
1300 const bool IsMinMax = isMinMaxRecurrenceKind(Kind);
1301
1302 // Search down from the Phi to the LoopExitInstr, looking for instructions
1303 // with a single user of the correct type for the reduction.
1304
1305 // Note that we check that the type of the operand is correct for each item in
1306 // the chain, including the last (the loop exit value). This can come up from
1307 // sub, which would otherwise be treated as an add reduction. MinMax also need
1308 // to check for a pair of icmp/select, for which we use getNextInstruction and
1309 // isCorrectOpcode functions to step the right number of instruction, and
1310 // check the icmp/select pair.
1311 // FIXME: We also do not attempt to look through Select's yet, which might
1312 // be part of the reduction chain, or attempt to looks through And's to find a
1313 // smaller bitwidth. Subs are also currently not allowed (which are usually
1314 // treated as part of a add reduction) as they are expected to generally be
1315 // more expensive than out-of-loop reductions, and need to be costed more
1316 // carefully.
1317 unsigned ExpectedUses = 1;
1318 if (IsMinMax)
1319 ExpectedUses = 2;
1320
1321 auto getNextInstruction = [&](Instruction *Cur) -> Instruction * {
1322 for (auto *User : Cur->users()) {
1323 Instruction *UI = cast<Instruction>(Val: User);
1324 if (isa<PHINode>(Val: UI))
1325 continue;
1326 if (IsMinMax) {
1327 // We are expecting a icmp/select pair, which we go to the next select
1328 // instruction if we can. We already know that Cur has 2 uses.
1329 if (isa<SelectInst>(Val: UI))
1330 return UI;
1331 continue;
1332 }
1333 return UI;
1334 }
1335 return nullptr;
1336 };
1337 auto isCorrectOpcode = [&](Instruction *Cur) {
1338 if (IsMinMax) {
1339 Value *LHS, *RHS;
1340 return SelectPatternResult::isMinOrMax(
1341 SPF: matchSelectPattern(V: Cur, LHS, RHS).Flavor);
1342 }
1343 // Recognize a call to the llvm.fmuladd intrinsic.
1344 if (isFMulAddIntrinsic(I: Cur))
1345 return true;
1346
1347 if (Cur->getOpcode() == Instruction::Sub &&
1348 Kind == RecurKind::AddChainWithSubs)
1349 return true;
1350
1351 if (Cur->getOpcode() == Instruction::FSub &&
1352 Kind == RecurKind::FAddChainWithSubs)
1353 return true;
1354
1355 return Cur->getOpcode() == getOpcode();
1356 };
1357
1358 // Attempt to look through Phis which are part of the reduction chain
1359 unsigned ExtraPhiUses = 0;
1360 Instruction *RdxInstr = LoopExitInstr;
1361 if (auto ExitPhi = dyn_cast<PHINode>(Val: LoopExitInstr)) {
1362 if (ExitPhi->getNumIncomingValues() != 2)
1363 return {};
1364
1365 Instruction *Inc0 = dyn_cast<Instruction>(Val: ExitPhi->getIncomingValue(i: 0));
1366 Instruction *Inc1 = dyn_cast<Instruction>(Val: ExitPhi->getIncomingValue(i: 1));
1367
1368 Instruction *Chain = nullptr;
1369 if (Inc0 == Phi)
1370 Chain = Inc1;
1371 else if (Inc1 == Phi)
1372 Chain = Inc0;
1373 else
1374 return {};
1375
1376 RdxInstr = Chain;
1377 ExtraPhiUses = 1;
1378 }
1379
1380 // The loop exit instruction we check first (as a quick test) but add last. We
1381 // check the opcode is correct (and dont allow them to be Subs) and that they
1382 // have expected to have the expected number of uses. They will have one use
1383 // from the phi and one from a LCSSA value, no matter the type.
1384 if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->hasNUses(N: 2))
1385 return {};
1386
1387 // Check that the Phi has one (or two for min/max) uses, plus an extra use
1388 // for conditional reductions.
1389 if (!Phi->hasNUses(N: ExpectedUses + ExtraPhiUses))
1390 return {};
1391
1392 Instruction *Cur = getNextInstruction(Phi);
1393
1394 // Each other instruction in the chain should have the expected number of uses
1395 // and be the correct opcode.
1396 while (Cur != RdxInstr) {
1397 if (!Cur || !isCorrectOpcode(Cur) || !Cur->hasNUses(N: ExpectedUses))
1398 return {};
1399
1400 ReductionOperations.push_back(Elt: Cur);
1401 Cur = getNextInstruction(Cur);
1402 }
1403
1404 ReductionOperations.push_back(Elt: Cur);
1405 return ReductionOperations;
1406}
1407
1408InductionDescriptor::InductionDescriptor(
1409 Value *Start, InductionKind K, const SCEV *Step, BinaryOperator *BOp,
1410 SmallVectorImpl<Instruction *> *Casts,
1411 ArrayRef<const SCEVPredicate *> NoWrapPreds)
1412 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
1413 assert(IK != IK_NoInduction && "Not an induction");
1414
1415 // Start value type should match the induction kind and the value
1416 // itself should not be null.
1417 assert(StartValue && "StartValue is null");
1418 assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
1419 "StartValue is not a pointer for pointer induction");
1420 assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
1421 "StartValue is not an integer for integer induction");
1422
1423 // Check the Step Value. It should be non-zero integer value.
1424 assert((!getConstStepValue() || !getConstStepValue()->isZero()) &&
1425 "Step value is zero");
1426
1427 assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
1428 "StepValue is not an integer");
1429
1430 assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
1431 "StepValue is not FP for FpInduction");
1432 assert((IK != IK_FpInduction ||
1433 (InductionBinOp &&
1434 (InductionBinOp->getOpcode() == Instruction::FAdd ||
1435 InductionBinOp->getOpcode() == Instruction::FSub))) &&
1436 "Binary opcode should be specified for FP induction");
1437
1438 if (Casts)
1439 llvm::append_range(C&: RedundantCasts, R&: *Casts);
1440 llvm::append_range(C&: NoWrapPredicates, R&: NoWrapPreds);
1441}
1442
1443InductionDescriptor
1444InductionDescriptor::getCanonicalIntInduction(Type *Ty, ScalarEvolution &SE) {
1445 return InductionDescriptor(Constant::getNullValue(Ty), IK_IntInduction,
1446 SE.getOne(Ty));
1447}
1448
1449std::optional<APInt> InductionDescriptor::getConstStepValue() const {
1450 if (auto *ConstStep = dyn_cast<SCEVConstant>(Val: Step))
1451 return ConstStep->getValue()->getValue();
1452 return {};
1453}
1454
1455bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
1456 ScalarEvolution *SE,
1457 InductionDescriptor &D) {
1458
1459 // Here we only handle FP induction variables.
1460 assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
1461
1462 if (TheLoop->getHeader() != Phi->getParent())
1463 return false;
1464
1465 // The loop may have multiple entrances or multiple exits; we can analyze
1466 // this phi if it has a unique entry value and a unique backedge value.
1467 if (Phi->getNumIncomingValues() != 2)
1468 return false;
1469 Value *BEValue = nullptr, *StartValue = nullptr;
1470 if (TheLoop->contains(BB: Phi->getIncomingBlock(i: 0))) {
1471 BEValue = Phi->getIncomingValue(i: 0);
1472 StartValue = Phi->getIncomingValue(i: 1);
1473 } else {
1474 assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
1475 "Unexpected Phi node in the loop");
1476 BEValue = Phi->getIncomingValue(i: 1);
1477 StartValue = Phi->getIncomingValue(i: 0);
1478 }
1479
1480 BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val: BEValue);
1481 if (!BOp)
1482 return false;
1483
1484 Value *Addend = nullptr;
1485 if (BOp->getOpcode() == Instruction::FAdd) {
1486 if (BOp->getOperand(i_nocapture: 0) == Phi)
1487 Addend = BOp->getOperand(i_nocapture: 1);
1488 else if (BOp->getOperand(i_nocapture: 1) == Phi)
1489 Addend = BOp->getOperand(i_nocapture: 0);
1490 } else if (BOp->getOpcode() == Instruction::FSub)
1491 if (BOp->getOperand(i_nocapture: 0) == Phi)
1492 Addend = BOp->getOperand(i_nocapture: 1);
1493
1494 if (!Addend)
1495 return false;
1496
1497 // The addend should be loop invariant
1498 if (auto *I = dyn_cast<Instruction>(Val: Addend))
1499 if (TheLoop->contains(Inst: I))
1500 return false;
1501
1502 // FP Step has unknown SCEV
1503 const SCEV *Step = SE->getUnknown(V: Addend);
1504 D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
1505 return true;
1506}
1507
1508/// This function is called when we suspect that the update-chain of a phi node
1509/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
1510/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
1511/// predicate P under which the SCEV expression for the phi can be the
1512/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
1513/// cast instructions that are involved in the update-chain of this induction.
1514/// A caller that adds the required runtime predicate can be free to drop these
1515/// cast instructions, and compute the phi using \p AR (instead of some scev
1516/// expression with casts).
1517///
1518/// For example, without a predicate the scev expression can take the following
1519/// form:
1520/// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
1521///
1522/// It corresponds to the following IR sequence:
1523/// %for.body:
1524/// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
1525/// %casted_phi = "ExtTrunc i64 %x"
1526/// %add = add i64 %casted_phi, %step
1527///
1528/// where %x is given in \p PN,
1529/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
1530/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
1531/// several forms, for example, such as:
1532/// ExtTrunc1: %casted_phi = and %x, 2^n-1
1533/// or:
1534/// ExtTrunc2: %t = shl %x, m
1535/// %casted_phi = ashr %t, m
1536///
1537/// If we are able to find such sequence, we return the instructions
1538/// we found, namely %casted_phi and the instructions on its use-def chain up
1539/// to the phi (not including the phi).
1540static bool
1541getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
1542 const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR,
1543 SmallVectorImpl<Instruction *> &CastInsts,
1544 ArrayRef<const SCEVPredicate *> NoWrapPreds) {
1545
1546 assert(CastInsts.empty() && "CastInsts is expected to be empty.");
1547 auto *PN = cast<PHINode>(Val: PhiScev->getValue());
1548
1549 // Build a predicate to rewrite SCEVs of values in the cast chain using the
1550 // predicates needed for this induction.
1551 ScalarEvolution &SE = *PSE.getSE();
1552 SCEVUnionPredicate NoWrapUnionPred(NoWrapPreds, SE);
1553 const Loop *L = AR->getLoop();
1554 assert(SE.rewriteUsingPredicate(SE.getSCEV(PN), L, NoWrapUnionPred) == AR &&
1555 "Unexpected phi node SCEV expression");
1556
1557 // Find any cast instructions that participate in the def-use chain of
1558 // PhiScev in the loop.
1559 // FORNOW/TODO: We currently expect the def-use chain to include only
1560 // two-operand instructions, where one of the operands is an invariant.
1561 // createAddRecFromPHIWithCasts() currently does not support anything more
1562 // involved than that, so we keep the search simple. This can be
1563 // extended/generalized as needed.
1564
1565 auto getDef = [&](const Value *Val) -> Value * {
1566 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
1567 if (!BinOp)
1568 return nullptr;
1569 Value *Op0 = BinOp->getOperand(i_nocapture: 0);
1570 Value *Op1 = BinOp->getOperand(i_nocapture: 1);
1571 Value *Def = nullptr;
1572 if (L->isLoopInvariant(V: Op0))
1573 Def = Op1;
1574 else if (L->isLoopInvariant(V: Op1))
1575 Def = Op0;
1576 return Def;
1577 };
1578
1579 // Look for the instruction that defines the induction via the
1580 // loop backedge.
1581 BasicBlock *Latch = L->getLoopLatch();
1582 if (!Latch)
1583 return false;
1584 Value *Val = PN->getIncomingValueForBlock(BB: Latch);
1585 if (!Val)
1586 return false;
1587
1588 // Follow the def-use chain until the induction phi is reached.
1589 // If on the way we encounter a Value that has the same SCEV Expr as the
1590 // phi node, we can consider the instructions we visit from that point
1591 // as part of the cast-sequence that can be ignored.
1592 bool InCastSequence = false;
1593 auto *Inst = dyn_cast<Instruction>(Val);
1594 while (Val != PN) {
1595 // If we encountered a phi node other than PN, or if we left the loop,
1596 // we bail out.
1597 if (!Inst || !L->contains(Inst)) {
1598 return false;
1599 }
1600 // Create AddRec with NoWrapPredicates applied.
1601 auto *AddRec = dyn_cast<SCEVAddRecExpr>(
1602 Val: SE.rewriteUsingPredicate(S: SE.getSCEV(V: Val), L, A: NoWrapUnionPred));
1603 if (AddRec && PSE.areAddRecsEqualWithPreds(AR1: AddRec, AR2: AR, ExtraPreds: NoWrapPreds))
1604 InCastSequence = true;
1605 if (InCastSequence) {
1606 // Only the last instruction in the cast sequence is expected to have
1607 // uses outside the induction def-use chain.
1608 if (!CastInsts.empty())
1609 if (!Inst->hasOneUse())
1610 return false;
1611 CastInsts.push_back(Elt: Inst);
1612 }
1613 Val = getDef(Val);
1614 if (!Val)
1615 return false;
1616 Inst = dyn_cast<Instruction>(Val);
1617 }
1618
1619 return InCastSequence;
1620}
1621
1622bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
1623 PredicatedScalarEvolution &PSE,
1624 InductionDescriptor &D, bool Assume) {
1625 Type *PhiTy = Phi->getType();
1626
1627 // Handle integer and pointer inductions variables.
1628 // Now we handle also FP induction but not trying to make a
1629 // recurrent expression from the PHI node in-place.
1630
1631 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
1632 !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
1633 return false;
1634
1635 if (PhiTy->isFloatingPointTy())
1636 return isFPInductionPHI(Phi, TheLoop, SE: PSE.getSE(), D);
1637
1638 const SCEV *PhiScev = PSE.getSCEV(V: Phi);
1639 const auto *AR = dyn_cast<SCEVAddRecExpr>(Val: PhiScev);
1640
1641 // Collect predicates needed to force the SCEV into an AddRecExpr.
1642 SmallVector<const SCEVPredicate *, 2> Preds;
1643
1644 // We need this expression to be an AddRecExpr.
1645 if (Assume && !AR)
1646 AR = PSE.getAsAddRec(V: Phi, WrapPredsAdded: &Preds);
1647
1648 if (!AR) {
1649 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1650 return false;
1651 }
1652
1653 // Record any Cast instructions that participate in the induction update
1654 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(Val: PhiScev);
1655 // If we started from an UnknownSCEV, and managed to build an addRecurrence
1656 // only after enabling Assume with PSCEV, this means we may have encountered
1657 // cast instructions that required adding a runtime check in order to
1658 // guarantee the correctness of the AddRecurrence respresentation of the
1659 // induction.
1660 if (PhiScev != AR && SymbolicPhi) {
1661 SmallVector<Instruction *, 2> Casts;
1662 if (getCastsForInductionPHI(PSE, PhiScev: SymbolicPhi, AR, CastInsts&: Casts, NoWrapPreds: Preds))
1663 return isInductionPHI(Phi, L: TheLoop, SE: PSE.getSE(), D, NoWrapPreds: Preds, Expr: AR, CastsToIgnore: &Casts);
1664 }
1665
1666 return isInductionPHI(Phi, L: TheLoop, SE: PSE.getSE(), D, NoWrapPreds: Preds, Expr: AR);
1667}
1668
1669bool InductionDescriptor::isInductionPHI(
1670 PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1671 InductionDescriptor &D, ArrayRef<const SCEVPredicate *> Preds,
1672 const SCEV *Expr, SmallVectorImpl<Instruction *> *CastsToIgnore) {
1673 Type *PhiTy = Phi->getType();
1674 // isSCEVable returns true for integer and pointer types.
1675 if (!SE->isSCEVable(Ty: PhiTy))
1676 return false;
1677
1678 // Check that the PHI is consecutive.
1679 const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(V: Phi);
1680 const SCEV *Step;
1681
1682 // FIXME: We are currently matching the specific loop TheLoop; if it doesn't
1683 // match, we should treat it as a uniform. Unfortunately, we don't currently
1684 // know how to handled uniform PHIs.
1685 if (!match(S: PhiScev, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV(V&: Step),
1686 L: m_SpecificLoop(L: TheLoop)))) {
1687 LLVM_DEBUG(
1688 dbgs() << "LV: PHI is not a poly recurrence for requested loop.\n");
1689 return false;
1690 }
1691
1692 // This function assumes that InductionPhi is called only on Phi nodes
1693 // present inside loop headers. Check for the same, and throw an assert if
1694 // the current Phi is not present inside the loop header.
1695 assert(Phi->getParent() == TheLoop->getHeader() &&
1696 "Invalid Phi node, not present in loop header");
1697
1698 if (!TheLoop->getLoopPreheader())
1699 return false;
1700
1701 Value *StartValue =
1702 Phi->getIncomingValueForBlock(BB: TheLoop->getLoopPreheader());
1703
1704 BasicBlock *Latch = TheLoop->getLoopLatch();
1705 if (!Latch)
1706 return false;
1707
1708 if (PhiTy->isIntegerTy()) {
1709 BinaryOperator *BOp =
1710 dyn_cast<BinaryOperator>(Val: Phi->getIncomingValueForBlock(BB: Latch));
1711 D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1712 CastsToIgnore, Preds);
1713 return true;
1714 }
1715
1716 assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1717
1718 // This allows induction variables w/non-constant steps.
1719 D = InductionDescriptor(StartValue, IK_PtrInduction, Step,
1720 /*InductionBinOp=*/nullptr, /*Casts=*/nullptr, Preds);
1721 return true;
1722}
1723
1724// Recognize a conditional induction PHI by matching the following pattern:
1725// loop_header:
1726// %conditional_iv = phi [ %start, %preheader ], [ %latch_phi, %latch ]
1727// br i1 %do_step, label %step_bb, label %latch
1728//
1729// step_bb:
1730// %step = add/gep %conditional_iv, %step_val
1731// br label %latch
1732//
1733// latch:
1734// %latch_phi = phi [ %conditional_iv, %loop_header ], [ %step, %step_bb ]
1735// br label %loop_header
1736bool ConditionalInductionDescriptor::isConditionalInductionPHI(
1737 PHINode *PN, const Loop *L, ConditionalInductionDescriptor &Desc,
1738 ScalarEvolution &SE) {
1739 BasicBlock *Preheader = L->getLoopPreheader();
1740 if (!Preheader)
1741 return false;
1742
1743 BasicBlock *Latch = L->getLoopLatch();
1744 if (!Latch || !PN->getType()->isIntOrPtrTy() ||
1745 PN->getParent() != L->getHeader())
1746 return false;
1747
1748 auto *BackedgePHI = dyn_cast<PHINode>(Val: PN->getIncomingValueForBlock(BB: Latch));
1749 if (!BackedgePHI)
1750 return false;
1751
1752 // Ensure the only users of the backedge PHI are outside the loop or the
1753 // header PHI (PN).
1754 for (User *U : BackedgePHI->users()) {
1755 auto *UI = cast<Instruction>(Val: U);
1756 if (UI != PN && L->contains(Inst: UI))
1757 return false;
1758 }
1759
1760 // Find the step operation used to increment the conditional induction PHI.
1761 // TODO: Support chains of PHIs.
1762 Value *StepOp =
1763 find_singleton<Value>(Range: BackedgePHI->incoming_values(),
1764 P: [&](Use &Incoming, bool /*AllowRepeats*/) {
1765 return Incoming != PN ? Incoming.get() : nullptr;
1766 });
1767 if (!StepOp || !StepOp->hasOneUse())
1768 return false;
1769
1770 auto *StepInst = dyn_cast<Instruction>(Val: StepOp);
1771 if (!StepInst)
1772 return false;
1773
1774 const DataLayout &DL = SE.getDataLayout();
1775 Value *Step = nullptr;
1776 bool StepMatch =
1777 PN->getType()->isPointerTy()
1778 ? match(V: StepInst, P: m_PtrAdd(DL, PointerOp: m_Specific(V: PN), OffsetOp: m_Value(V&: Step)))
1779 : match(V: StepInst, P: m_c_Add(L: m_Specific(V: PN), R: m_Value(V&: Step)));
1780 if (!StepMatch || !L->isLoopInvariant(V: Step))
1781 return false;
1782
1783 const SCEV *StepSCEV = SE.getSCEV(V: Step);
1784 if (StepSCEV->isZero())
1785 return false;
1786
1787 Value *Start = PN->getIncomingValueForBlock(BB: Preheader);
1788 const SCEV *StartSCEV = SE.getSCEV(V: Start);
1789
1790 SCEVFlags NoWrapFlags = SCEV::FlagNone;
1791 if (auto *GEP = dyn_cast<GEPOperator>(Val: StepInst)) {
1792 // With NUSW, we can add NUW if the step is non-negative. We can't add NSW
1793 // as the base address is unsigned.
1794 if (GEP->hasNoUnsignedWrap() ||
1795 (GEP->hasNoUnsignedSignedWrap() && SE.isKnownNonNegative(S: StepSCEV)))
1796 NoWrapFlags = ScalarEvolution::setFlags(Flags: NoWrapFlags, OnFlags: SCEV::FlagNUW);
1797 } else if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Val: StepInst)) {
1798 if (OBO->hasNoUnsignedWrap())
1799 NoWrapFlags = ScalarEvolution::setFlags(Flags: NoWrapFlags, OnFlags: SCEV::FlagNUW);
1800 if (OBO->hasNoSignedWrap())
1801 NoWrapFlags = ScalarEvolution::setFlags(Flags: NoWrapFlags, OnFlags: SCEV::FlagNSW);
1802 }
1803
1804 LLVM_DEBUG(dbgs() << "LV: Found a conditional induction phi: HeaderPHI: "
1805 << *PN << ", StepInst: " << *StepInst << "\n");
1806
1807 Desc = ConditionalInductionDescriptor(PN, BackedgePHI, StepInst, StartSCEV,
1808 StepSCEV, NoWrapFlags);
1809 return true;
1810}
1811
1812const SCEV *
1813ConditionalInductionDescriptor::getUnconditionalAddRec(ScalarEvolution &SE,
1814 const Loop &L) const {
1815 assert(L.contains(HeaderPHI) &&
1816 "The provided loop does not contain this conditional induction");
1817 return SE.getAddRecExpr(Start: getStartSCEV(), Step: getStepSCEV(), L: &L, Flags: SCEV::FlagNone);
1818}
1819