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