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