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