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