xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/IVDescriptors.cpp (revision d409305fa3838fb39b38c26fc085fb729b8766d5)
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/ADT/ScopeExit.h"
15 #include "llvm/Analysis/BasicAliasAnalysis.h"
16 #include "llvm/Analysis/DemandedBits.h"
17 #include "llvm/Analysis/DomTreeUpdater.h"
18 #include "llvm/Analysis/GlobalsModRef.h"
19 #include "llvm/Analysis/InstructionSimplify.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.h"
22 #include "llvm/Analysis/MustExecute.h"
23 #include "llvm/Analysis/ScalarEvolution.h"
24 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
25 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
26 #include "llvm/Analysis/TargetTransformInfo.h"
27 #include "llvm/Analysis/ValueTracking.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/IR/ValueHandle.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/KnownBits.h"
36 
37 using namespace llvm;
38 using namespace llvm::PatternMatch;
39 
40 #define DEBUG_TYPE "iv-descriptors"
41 
42 bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
43                                         SmallPtrSetImpl<Instruction *> &Set) {
44   for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
45     if (!Set.count(dyn_cast<Instruction>(*Use)))
46       return false;
47   return true;
48 }
49 
50 bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) {
51   switch (Kind) {
52   default:
53     break;
54   case RecurKind::Add:
55   case RecurKind::Mul:
56   case RecurKind::Or:
57   case RecurKind::And:
58   case RecurKind::Xor:
59   case RecurKind::SMax:
60   case RecurKind::SMin:
61   case RecurKind::UMax:
62   case RecurKind::UMin:
63     return true;
64   }
65   return false;
66 }
67 
68 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) {
69   return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
70 }
71 
72 bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurKind Kind) {
73   switch (Kind) {
74   default:
75     break;
76   case RecurKind::Add:
77   case RecurKind::Mul:
78   case RecurKind::FAdd:
79   case RecurKind::FMul:
80     return true;
81   }
82   return false;
83 }
84 
85 /// Determines if Phi may have been type-promoted. If Phi has a single user
86 /// that ANDs the Phi with a type mask, return the user. RT is updated to
87 /// account for the narrower bit width represented by the mask, and the AND
88 /// instruction is added to CI.
89 static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
90                                    SmallPtrSetImpl<Instruction *> &Visited,
91                                    SmallPtrSetImpl<Instruction *> &CI) {
92   if (!Phi->hasOneUse())
93     return Phi;
94 
95   const APInt *M = nullptr;
96   Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
97 
98   // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
99   // with a new integer type of the corresponding bit width.
100   if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
101     int32_t Bits = (*M + 1).exactLogBase2();
102     if (Bits > 0) {
103       RT = IntegerType::get(Phi->getContext(), Bits);
104       Visited.insert(Phi);
105       CI.insert(J);
106       return J;
107     }
108   }
109   return Phi;
110 }
111 
112 /// Compute the minimal bit width needed to represent a reduction whose exit
113 /// instruction is given by Exit.
114 static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
115                                                      DemandedBits *DB,
116                                                      AssumptionCache *AC,
117                                                      DominatorTree *DT) {
118   bool IsSigned = false;
119   const DataLayout &DL = Exit->getModule()->getDataLayout();
120   uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
121 
122   if (DB) {
123     // Use the demanded bits analysis to determine the bits that are live out
124     // of the exit instruction, rounding up to the nearest power of two. If the
125     // use of demanded bits results in a smaller bit width, we know the value
126     // must be positive (i.e., IsSigned = false), because if this were not the
127     // case, the sign bit would have been demanded.
128     auto Mask = DB->getDemandedBits(Exit);
129     MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
130   }
131 
132   if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
133     // If demanded bits wasn't able to limit the bit width, we can try to use
134     // value tracking instead. This can be the case, for example, if the value
135     // may be negative.
136     auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
137     auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
138     MaxBitWidth = NumTypeBits - NumSignBits;
139     KnownBits Bits = computeKnownBits(Exit, DL);
140     if (!Bits.isNonNegative()) {
141       // If the value is not known to be non-negative, we set IsSigned to true,
142       // meaning that we will use sext instructions instead of zext
143       // instructions to restore the original type.
144       IsSigned = true;
145       if (!Bits.isNegative())
146         // If the value is not known to be negative, we don't known what the
147         // upper bit is, and therefore, we don't know what kind of extend we
148         // will need. In this case, just increase the bit width by one bit and
149         // use sext.
150         ++MaxBitWidth;
151     }
152   }
153   if (!isPowerOf2_64(MaxBitWidth))
154     MaxBitWidth = NextPowerOf2(MaxBitWidth);
155 
156   return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
157                         IsSigned);
158 }
159 
160 /// Collect cast instructions that can be ignored in the vectorizer's cost
161 /// model, given a reduction exit value and the minimal type in which the
162 /// reduction can be represented.
163 static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
164                                  Type *RecurrenceType,
165                                  SmallPtrSetImpl<Instruction *> &Casts) {
166 
167   SmallVector<Instruction *, 8> Worklist;
168   SmallPtrSet<Instruction *, 8> Visited;
169   Worklist.push_back(Exit);
170 
171   while (!Worklist.empty()) {
172     Instruction *Val = Worklist.pop_back_val();
173     Visited.insert(Val);
174     if (auto *Cast = dyn_cast<CastInst>(Val))
175       if (Cast->getSrcTy() == RecurrenceType) {
176         // If the source type of a cast instruction is equal to the recurrence
177         // type, it will be eliminated, and should be ignored in the vectorizer
178         // cost model.
179         Casts.insert(Cast);
180         continue;
181       }
182 
183     // Add all operands to the work list if they are loop-varying values that
184     // we haven't yet visited.
185     for (Value *O : cast<User>(Val)->operands())
186       if (auto *I = dyn_cast<Instruction>(O))
187         if (TheLoop->contains(I) && !Visited.count(I))
188           Worklist.push_back(I);
189   }
190 }
191 
192 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurKind Kind,
193                                            Loop *TheLoop, bool HasFunNoNaNAttr,
194                                            RecurrenceDescriptor &RedDes,
195                                            DemandedBits *DB,
196                                            AssumptionCache *AC,
197                                            DominatorTree *DT) {
198   if (Phi->getNumIncomingValues() != 2)
199     return false;
200 
201   // Reduction variables are only found in the loop header block.
202   if (Phi->getParent() != TheLoop->getHeader())
203     return false;
204 
205   // Obtain the reduction start value from the value that comes from the loop
206   // preheader.
207   Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
208 
209   // ExitInstruction is the single value which is used outside the loop.
210   // We only allow for a single reduction value to be used outside the loop.
211   // This includes users of the reduction, variables (which form a cycle
212   // which ends in the phi node).
213   Instruction *ExitInstruction = nullptr;
214   // Indicates that we found a reduction operation in our scan.
215   bool FoundReduxOp = false;
216 
217   // We start with the PHI node and scan for all of the users of this
218   // instruction. All users must be instructions that can be used as reduction
219   // variables (such as ADD). We must have a single out-of-block user. The cycle
220   // must include the original PHI.
221   bool FoundStartPHI = false;
222 
223   // To recognize min/max patterns formed by a icmp select sequence, we store
224   // the number of instruction we saw from the recognized min/max pattern,
225   //  to make sure we only see exactly the two instructions.
226   unsigned NumCmpSelectPatternInst = 0;
227   InstDesc ReduxDesc(false, nullptr);
228 
229   // Data used for determining if the recurrence has been type-promoted.
230   Type *RecurrenceType = Phi->getType();
231   SmallPtrSet<Instruction *, 4> CastInsts;
232   Instruction *Start = Phi;
233   bool IsSigned = false;
234 
235   SmallPtrSet<Instruction *, 8> VisitedInsts;
236   SmallVector<Instruction *, 8> Worklist;
237 
238   // Return early if the recurrence kind does not match the type of Phi. If the
239   // recurrence kind is arithmetic, we attempt to look through AND operations
240   // resulting from the type promotion performed by InstCombine.  Vector
241   // operations are not limited to the legal integer widths, so we may be able
242   // to evaluate the reduction in the narrower width.
243   if (RecurrenceType->isFloatingPointTy()) {
244     if (!isFloatingPointRecurrenceKind(Kind))
245       return false;
246   } else if (RecurrenceType->isIntegerTy()) {
247     if (!isIntegerRecurrenceKind(Kind))
248       return false;
249     if (isArithmeticRecurrenceKind(Kind))
250       Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
251   } else {
252     // Pointer min/max may exist, but it is not supported as a reduction op.
253     return false;
254   }
255 
256   Worklist.push_back(Start);
257   VisitedInsts.insert(Start);
258 
259   // Start with all flags set because we will intersect this with the reduction
260   // flags from all the reduction operations.
261   FastMathFlags FMF = FastMathFlags::getFast();
262 
263   // A value in the reduction can be used:
264   //  - By the reduction:
265   //      - Reduction operation:
266   //        - One use of reduction value (safe).
267   //        - Multiple use of reduction value (not safe).
268   //      - PHI:
269   //        - All uses of the PHI must be the reduction (safe).
270   //        - Otherwise, not safe.
271   //  - By instructions outside of the loop (safe).
272   //      * One value may have several outside users, but all outside
273   //        uses must be of the same value.
274   //  - By an instruction that is not part of the reduction (not safe).
275   //    This is either:
276   //      * An instruction type other than PHI or the reduction operation.
277   //      * A PHI in the header other than the initial PHI.
278   while (!Worklist.empty()) {
279     Instruction *Cur = Worklist.pop_back_val();
280 
281     // No Users.
282     // If the instruction has no users then this is a broken chain and can't be
283     // a reduction variable.
284     if (Cur->use_empty())
285       return false;
286 
287     bool IsAPhi = isa<PHINode>(Cur);
288 
289     // A header PHI use other than the original PHI.
290     if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
291       return false;
292 
293     // Reductions of instructions such as Div, and Sub is only possible if the
294     // LHS is the reduction variable.
295     if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
296         !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
297         !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
298       return false;
299 
300     // Any reduction instruction must be of one of the allowed kinds. We ignore
301     // the starting value (the Phi or an AND instruction if the Phi has been
302     // type-promoted).
303     if (Cur != Start) {
304       ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
305       if (!ReduxDesc.isRecurrence())
306         return false;
307       // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
308       if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi)
309         FMF &= ReduxDesc.getPatternInst()->getFastMathFlags();
310       // Update this reduction kind if we matched a new instruction.
311       // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind'
312       //       state accurate while processing the worklist?
313       if (ReduxDesc.getRecKind() != RecurKind::None)
314         Kind = ReduxDesc.getRecKind();
315     }
316 
317     bool IsASelect = isa<SelectInst>(Cur);
318 
319     // A conditional reduction operation must only have 2 or less uses in
320     // VisitedInsts.
321     if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) &&
322         hasMultipleUsesOf(Cur, VisitedInsts, 2))
323       return false;
324 
325     // A reduction operation must only have one use of the reduction value.
326     if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) &&
327         hasMultipleUsesOf(Cur, VisitedInsts, 1))
328       return false;
329 
330     // All inputs to a PHI node must be a reduction value.
331     if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
332       return false;
333 
334     if (isIntMinMaxRecurrenceKind(Kind) &&
335         (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
336       ++NumCmpSelectPatternInst;
337     if (isFPMinMaxRecurrenceKind(Kind) &&
338         (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
339       ++NumCmpSelectPatternInst;
340 
341     // Check  whether we found a reduction operator.
342     FoundReduxOp |= !IsAPhi && Cur != Start;
343 
344     // Process users of current instruction. Push non-PHI nodes after PHI nodes
345     // onto the stack. This way we are going to have seen all inputs to PHI
346     // nodes once we get to them.
347     SmallVector<Instruction *, 8> NonPHIs;
348     SmallVector<Instruction *, 8> PHIs;
349     for (User *U : Cur->users()) {
350       Instruction *UI = cast<Instruction>(U);
351 
352       // Check if we found the exit user.
353       BasicBlock *Parent = UI->getParent();
354       if (!TheLoop->contains(Parent)) {
355         // If we already know this instruction is used externally, move on to
356         // the next user.
357         if (ExitInstruction == Cur)
358           continue;
359 
360         // Exit if you find multiple values used outside or if the header phi
361         // node is being used. In this case the user uses the value of the
362         // previous iteration, in which case we would loose "VF-1" iterations of
363         // the reduction operation if we vectorize.
364         if (ExitInstruction != nullptr || Cur == Phi)
365           return false;
366 
367         // The instruction used by an outside user must be the last instruction
368         // before we feed back to the reduction phi. Otherwise, we loose VF-1
369         // operations on the value.
370         if (!is_contained(Phi->operands(), Cur))
371           return false;
372 
373         ExitInstruction = Cur;
374         continue;
375       }
376 
377       // Process instructions only once (termination). Each reduction cycle
378       // value must only be used once, except by phi nodes and min/max
379       // reductions which are represented as a cmp followed by a select.
380       InstDesc IgnoredVal(false, nullptr);
381       if (VisitedInsts.insert(UI).second) {
382         if (isa<PHINode>(UI))
383           PHIs.push_back(UI);
384         else
385           NonPHIs.push_back(UI);
386       } else if (!isa<PHINode>(UI) &&
387                  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
388                    !isa<SelectInst>(UI)) ||
389                   (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
390                    !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())))
391         return false;
392 
393       // Remember that we completed the cycle.
394       if (UI == Phi)
395         FoundStartPHI = true;
396     }
397     Worklist.append(PHIs.begin(), PHIs.end());
398     Worklist.append(NonPHIs.begin(), NonPHIs.end());
399   }
400 
401   // This means we have seen one but not the other instruction of the
402   // pattern or more than just a select and cmp.
403   if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2)
404     return false;
405 
406   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
407     return false;
408 
409   if (Start != Phi) {
410     // If the starting value is not the same as the phi node, we speculatively
411     // looked through an 'and' instruction when evaluating a potential
412     // arithmetic reduction to determine if it may have been type-promoted.
413     //
414     // We now compute the minimal bit width that is required to represent the
415     // reduction. If this is the same width that was indicated by the 'and', we
416     // can represent the reduction in the smaller type. The 'and' instruction
417     // will be eliminated since it will essentially be a cast instruction that
418     // can be ignore in the cost model. If we compute a different type than we
419     // did when evaluating the 'and', the 'and' will not be eliminated, and we
420     // will end up with different kinds of operations in the recurrence
421     // expression (e.g., IntegerAND, IntegerADD). We give up if this is
422     // the case.
423     //
424     // The vectorizer relies on InstCombine to perform the actual
425     // type-shrinking. It does this by inserting instructions to truncate the
426     // exit value of the reduction to the width indicated by RecurrenceType and
427     // then extend this value back to the original width. If IsSigned is false,
428     // a 'zext' instruction will be generated; otherwise, a 'sext' will be
429     // used.
430     //
431     // TODO: We should not rely on InstCombine to rewrite the reduction in the
432     //       smaller type. We should just generate a correctly typed expression
433     //       to begin with.
434     Type *ComputedType;
435     std::tie(ComputedType, IsSigned) =
436         computeRecurrenceType(ExitInstruction, DB, AC, DT);
437     if (ComputedType != RecurrenceType)
438       return false;
439 
440     // The recurrence expression will be represented in a narrower type. If
441     // there are any cast instructions that will be unnecessary, collect them
442     // in CastInsts. Note that the 'and' instruction was already included in
443     // this list.
444     //
445     // TODO: A better way to represent this may be to tag in some way all the
446     //       instructions that are a part of the reduction. The vectorizer cost
447     //       model could then apply the recurrence type to these instructions,
448     //       without needing a white list of instructions to ignore.
449     //       This may also be useful for the inloop reductions, if it can be
450     //       kept simple enough.
451     collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
452   }
453 
454   // We found a reduction var if we have reached the original phi node and we
455   // only have a single instruction with out-of-loop users.
456 
457   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
458   // is saved as part of the RecurrenceDescriptor.
459 
460   // Save the description of this reduction variable.
461   RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind, FMF,
462                           ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType,
463                           IsSigned, CastInsts);
464   RedDes = RD;
465 
466   return true;
467 }
468 
469 RecurrenceDescriptor::InstDesc
470 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I,
471                                                const InstDesc &Prev) {
472   assert((isa<CmpInst>(I) || isa<SelectInst>(I)) &&
473          "Expected a cmp or select instruction");
474 
475   // We must handle the select(cmp()) as a single instruction. Advance to the
476   // select.
477   CmpInst::Predicate Pred;
478   if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
479     if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
480       return InstDesc(Select, Prev.getRecKind());
481   }
482 
483   // Only match select with single use cmp condition.
484   if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
485                          m_Value())))
486     return InstDesc(false, I);
487 
488   // Look for a min/max pattern.
489   if (match(I, m_UMin(m_Value(), m_Value())))
490     return InstDesc(I, RecurKind::UMin);
491   if (match(I, m_UMax(m_Value(), m_Value())))
492     return InstDesc(I, RecurKind::UMax);
493   if (match(I, m_SMax(m_Value(), m_Value())))
494     return InstDesc(I, RecurKind::SMax);
495   if (match(I, m_SMin(m_Value(), m_Value())))
496     return InstDesc(I, RecurKind::SMin);
497   if (match(I, m_OrdFMin(m_Value(), m_Value())))
498     return InstDesc(I, RecurKind::FMin);
499   if (match(I, m_OrdFMax(m_Value(), m_Value())))
500     return InstDesc(I, RecurKind::FMax);
501   if (match(I, m_UnordFMin(m_Value(), m_Value())))
502     return InstDesc(I, RecurKind::FMin);
503   if (match(I, m_UnordFMax(m_Value(), m_Value())))
504     return InstDesc(I, RecurKind::FMax);
505 
506   return InstDesc(false, I);
507 }
508 
509 /// Returns true if the select instruction has users in the compare-and-add
510 /// reduction pattern below. The select instruction argument is the last one
511 /// in the sequence.
512 ///
513 /// %sum.1 = phi ...
514 /// ...
515 /// %cmp = fcmp pred %0, %CFP
516 /// %add = fadd %0, %sum.1
517 /// %sum.2 = select %cmp, %add, %sum.1
518 RecurrenceDescriptor::InstDesc
519 RecurrenceDescriptor::isConditionalRdxPattern(RecurKind Kind, Instruction *I) {
520   SelectInst *SI = dyn_cast<SelectInst>(I);
521   if (!SI)
522     return InstDesc(false, I);
523 
524   CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
525   // Only handle single use cases for now.
526   if (!CI || !CI->hasOneUse())
527     return InstDesc(false, I);
528 
529   Value *TrueVal = SI->getTrueValue();
530   Value *FalseVal = SI->getFalseValue();
531   // Handle only when either of operands of select instruction is a PHI
532   // node for now.
533   if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
534       (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
535     return InstDesc(false, I);
536 
537   Instruction *I1 =
538       isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
539                              : dyn_cast<Instruction>(TrueVal);
540   if (!I1 || !I1->isBinaryOp())
541     return InstDesc(false, I);
542 
543   Value *Op1, *Op2;
544   if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1)  ||
545        m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
546       I1->isFast())
547     return InstDesc(Kind == RecurKind::FAdd, SI);
548 
549   if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
550     return InstDesc(Kind == RecurKind::FMul, SI);
551 
552   return InstDesc(false, I);
553 }
554 
555 RecurrenceDescriptor::InstDesc
556 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurKind Kind,
557                                         InstDesc &Prev, bool HasFunNoNaNAttr) {
558   Instruction *UAI = Prev.getUnsafeAlgebraInst();
559   if (!UAI && isa<FPMathOperator>(I) && !I->hasAllowReassoc())
560     UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
561 
562   switch (I->getOpcode()) {
563   default:
564     return InstDesc(false, I);
565   case Instruction::PHI:
566     return InstDesc(I, Prev.getRecKind(), Prev.getUnsafeAlgebraInst());
567   case Instruction::Sub:
568   case Instruction::Add:
569     return InstDesc(Kind == RecurKind::Add, I);
570   case Instruction::Mul:
571     return InstDesc(Kind == RecurKind::Mul, I);
572   case Instruction::And:
573     return InstDesc(Kind == RecurKind::And, I);
574   case Instruction::Or:
575     return InstDesc(Kind == RecurKind::Or, I);
576   case Instruction::Xor:
577     return InstDesc(Kind == RecurKind::Xor, I);
578   case Instruction::FDiv:
579   case Instruction::FMul:
580     return InstDesc(Kind == RecurKind::FMul, I, UAI);
581   case Instruction::FSub:
582   case Instruction::FAdd:
583     return InstDesc(Kind == RecurKind::FAdd, I, UAI);
584   case Instruction::Select:
585     if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul)
586       return isConditionalRdxPattern(Kind, I);
587     LLVM_FALLTHROUGH;
588   case Instruction::FCmp:
589   case Instruction::ICmp:
590     if (!isIntMinMaxRecurrenceKind(Kind) &&
591         (!HasFunNoNaNAttr || !isFPMinMaxRecurrenceKind(Kind)))
592       return InstDesc(false, I);
593     return isMinMaxSelectCmpPattern(I, Prev);
594   }
595 }
596 
597 bool RecurrenceDescriptor::hasMultipleUsesOf(
598     Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
599     unsigned MaxNumUses) {
600   unsigned NumUses = 0;
601   for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
602        ++Use) {
603     if (Insts.count(dyn_cast<Instruction>(*Use)))
604       ++NumUses;
605     if (NumUses > MaxNumUses)
606       return true;
607   }
608 
609   return false;
610 }
611 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
612                                           RecurrenceDescriptor &RedDes,
613                                           DemandedBits *DB, AssumptionCache *AC,
614                                           DominatorTree *DT) {
615 
616   BasicBlock *Header = TheLoop->getHeader();
617   Function &F = *Header->getParent();
618   bool HasFunNoNaNAttr =
619       F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
620 
621   if (AddReductionVar(Phi, RecurKind::Add, TheLoop, HasFunNoNaNAttr, RedDes, DB,
622                       AC, DT)) {
623     LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
624     return true;
625   }
626   if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, HasFunNoNaNAttr, RedDes, DB,
627                       AC, DT)) {
628     LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
629     return true;
630   }
631   if (AddReductionVar(Phi, RecurKind::Or, TheLoop, HasFunNoNaNAttr, RedDes, DB,
632                       AC, DT)) {
633     LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
634     return true;
635   }
636   if (AddReductionVar(Phi, RecurKind::And, TheLoop, HasFunNoNaNAttr, RedDes, DB,
637                       AC, DT)) {
638     LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
639     return true;
640   }
641   if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
642                       AC, DT)) {
643     LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
644     return true;
645   }
646   if (AddReductionVar(Phi, RecurKind::SMax, TheLoop, HasFunNoNaNAttr, RedDes,
647                       DB, AC, DT)) {
648     LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n");
649     return true;
650   }
651   if (AddReductionVar(Phi, RecurKind::SMin, TheLoop, HasFunNoNaNAttr, RedDes,
652                       DB, AC, DT)) {
653     LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n");
654     return true;
655   }
656   if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, HasFunNoNaNAttr, RedDes,
657                       DB, AC, DT)) {
658     LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n");
659     return true;
660   }
661   if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, HasFunNoNaNAttr, RedDes,
662                       DB, AC, DT)) {
663     LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n");
664     return true;
665   }
666   if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, HasFunNoNaNAttr, RedDes,
667                       DB, AC, DT)) {
668     LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
669     return true;
670   }
671   if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, HasFunNoNaNAttr, RedDes,
672                       DB, AC, DT)) {
673     LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
674     return true;
675   }
676   if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, HasFunNoNaNAttr, RedDes,
677                       DB, AC, DT)) {
678     LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n");
679     return true;
680   }
681   if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, HasFunNoNaNAttr, RedDes,
682                       DB, AC, DT)) {
683     LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n");
684     return true;
685   }
686   // Not a reduction of known type.
687   return false;
688 }
689 
690 bool RecurrenceDescriptor::isFirstOrderRecurrence(
691     PHINode *Phi, Loop *TheLoop,
692     DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
693 
694   // Ensure the phi node is in the loop header and has two incoming values.
695   if (Phi->getParent() != TheLoop->getHeader() ||
696       Phi->getNumIncomingValues() != 2)
697     return false;
698 
699   // Ensure the loop has a preheader and a single latch block. The loop
700   // vectorizer will need the latch to set up the next iteration of the loop.
701   auto *Preheader = TheLoop->getLoopPreheader();
702   auto *Latch = TheLoop->getLoopLatch();
703   if (!Preheader || !Latch)
704     return false;
705 
706   // Ensure the phi node's incoming blocks are the loop preheader and latch.
707   if (Phi->getBasicBlockIndex(Preheader) < 0 ||
708       Phi->getBasicBlockIndex(Latch) < 0)
709     return false;
710 
711   // Get the previous value. The previous value comes from the latch edge while
712   // the initial value comes form the preheader edge.
713   auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
714   if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
715       SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
716     return false;
717 
718   // Ensure every user of the phi node is dominated by the previous value.
719   // The dominance requirement ensures the loop vectorizer will not need to
720   // vectorize the initial value prior to the first iteration of the loop.
721   // TODO: Consider extending this sinking to handle memory instructions and
722   // phis with multiple users.
723 
724   // Returns true, if all users of I are dominated by DominatedBy.
725   auto allUsesDominatedBy = [DT](Instruction *I, Instruction *DominatedBy) {
726     return all_of(I->uses(), [DT, DominatedBy](Use &U) {
727       return DT->dominates(DominatedBy, U);
728     });
729   };
730 
731   if (Phi->hasOneUse()) {
732     Instruction *I = Phi->user_back();
733 
734     // If the user of the PHI is also the incoming value, we potentially have a
735     // reduction and which cannot be handled by sinking.
736     if (Previous == I)
737       return false;
738 
739     // We cannot sink terminator instructions.
740     if (I->getParent()->getTerminator() == I)
741       return false;
742 
743     // Do not try to sink an instruction multiple times (if multiple operands
744     // are first order recurrences).
745     // TODO: We can support this case, by sinking the instruction after the
746     // 'deepest' previous instruction.
747     if (SinkAfter.find(I) != SinkAfter.end())
748       return false;
749 
750     if (DT->dominates(Previous, I)) // We already are good w/o sinking.
751       return true;
752 
753     // We can sink any instruction without side effects, as long as all users
754     // are dominated by the instruction we are sinking after.
755     if (I->getParent() == Phi->getParent() && !I->mayHaveSideEffects() &&
756         allUsesDominatedBy(I, Previous)) {
757       SinkAfter[I] = Previous;
758       return true;
759     }
760   }
761 
762   return allUsesDominatedBy(Phi, Previous);
763 }
764 
765 /// This function returns the identity element (or neutral element) for
766 /// the operation K.
767 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurKind K, Type *Tp) {
768   switch (K) {
769   case RecurKind::Xor:
770   case RecurKind::Add:
771   case RecurKind::Or:
772     // Adding, Xoring, Oring zero to a number does not change it.
773     return ConstantInt::get(Tp, 0);
774   case RecurKind::Mul:
775     // Multiplying a number by 1 does not change it.
776     return ConstantInt::get(Tp, 1);
777   case RecurKind::And:
778     // AND-ing a number with an all-1 value does not change it.
779     return ConstantInt::get(Tp, -1, true);
780   case RecurKind::FMul:
781     // Multiplying a number by 1 does not change it.
782     return ConstantFP::get(Tp, 1.0L);
783   case RecurKind::FAdd:
784     // Adding zero to a number does not change it.
785     return ConstantFP::get(Tp, 0.0L);
786   case RecurKind::UMin:
787     return ConstantInt::get(Tp, -1);
788   case RecurKind::UMax:
789     return ConstantInt::get(Tp, 0);
790   case RecurKind::SMin:
791     return ConstantInt::get(Tp,
792                             APInt::getSignedMaxValue(Tp->getIntegerBitWidth()));
793   case RecurKind::SMax:
794     return ConstantInt::get(Tp,
795                             APInt::getSignedMinValue(Tp->getIntegerBitWidth()));
796   case RecurKind::FMin:
797     return ConstantFP::getInfinity(Tp, true);
798   case RecurKind::FMax:
799     return ConstantFP::getInfinity(Tp, false);
800   default:
801     llvm_unreachable("Unknown recurrence kind");
802   }
803 }
804 
805 unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
806   switch (Kind) {
807   case RecurKind::Add:
808     return Instruction::Add;
809   case RecurKind::Mul:
810     return Instruction::Mul;
811   case RecurKind::Or:
812     return Instruction::Or;
813   case RecurKind::And:
814     return Instruction::And;
815   case RecurKind::Xor:
816     return Instruction::Xor;
817   case RecurKind::FMul:
818     return Instruction::FMul;
819   case RecurKind::FAdd:
820     return Instruction::FAdd;
821   case RecurKind::SMax:
822   case RecurKind::SMin:
823   case RecurKind::UMax:
824   case RecurKind::UMin:
825     return Instruction::ICmp;
826   case RecurKind::FMax:
827   case RecurKind::FMin:
828     return Instruction::FCmp;
829   default:
830     llvm_unreachable("Unknown recurrence operation");
831   }
832 }
833 
834 SmallVector<Instruction *, 4>
835 RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {
836   SmallVector<Instruction *, 4> ReductionOperations;
837   unsigned RedOp = getOpcode(Kind);
838 
839   // Search down from the Phi to the LoopExitInstr, looking for instructions
840   // with a single user of the correct type for the reduction.
841 
842   // Note that we check that the type of the operand is correct for each item in
843   // the chain, including the last (the loop exit value). This can come up from
844   // sub, which would otherwise be treated as an add reduction. MinMax also need
845   // to check for a pair of icmp/select, for which we use getNextInstruction and
846   // isCorrectOpcode functions to step the right number of instruction, and
847   // check the icmp/select pair.
848   // FIXME: We also do not attempt to look through Phi/Select's yet, which might
849   // be part of the reduction chain, or attempt to looks through And's to find a
850   // smaller bitwidth. Subs are also currently not allowed (which are usually
851   // treated as part of a add reduction) as they are expected to generally be
852   // more expensive than out-of-loop reductions, and need to be costed more
853   // carefully.
854   unsigned ExpectedUses = 1;
855   if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp)
856     ExpectedUses = 2;
857 
858   auto getNextInstruction = [&](Instruction *Cur) {
859     if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
860       // We are expecting a icmp/select pair, which we go to the next select
861       // instruction if we can. We already know that Cur has 2 uses.
862       if (isa<SelectInst>(*Cur->user_begin()))
863         return cast<Instruction>(*Cur->user_begin());
864       else
865         return cast<Instruction>(*std::next(Cur->user_begin()));
866     }
867     return cast<Instruction>(*Cur->user_begin());
868   };
869   auto isCorrectOpcode = [&](Instruction *Cur) {
870     if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
871       Value *LHS, *RHS;
872       return SelectPatternResult::isMinOrMax(
873           matchSelectPattern(Cur, LHS, RHS).Flavor);
874     }
875     return Cur->getOpcode() == RedOp;
876   };
877 
878   // The loop exit instruction we check first (as a quick test) but add last. We
879   // check the opcode is correct (and dont allow them to be Subs) and that they
880   // have expected to have the expected number of uses. They will have one use
881   // from the phi and one from a LCSSA value, no matter the type.
882   if (!isCorrectOpcode(LoopExitInstr) || !LoopExitInstr->hasNUses(2))
883     return {};
884 
885   // Check that the Phi has one (or two for min/max) uses.
886   if (!Phi->hasNUses(ExpectedUses))
887     return {};
888   Instruction *Cur = getNextInstruction(Phi);
889 
890   // Each other instruction in the chain should have the expected number of uses
891   // and be the correct opcode.
892   while (Cur != LoopExitInstr) {
893     if (!isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses))
894       return {};
895 
896     ReductionOperations.push_back(Cur);
897     Cur = getNextInstruction(Cur);
898   }
899 
900   ReductionOperations.push_back(Cur);
901   return ReductionOperations;
902 }
903 
904 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
905                                          const SCEV *Step, BinaryOperator *BOp,
906                                          SmallVectorImpl<Instruction *> *Casts)
907     : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
908   assert(IK != IK_NoInduction && "Not an induction");
909 
910   // Start value type should match the induction kind and the value
911   // itself should not be null.
912   assert(StartValue && "StartValue is null");
913   assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
914          "StartValue is not a pointer for pointer induction");
915   assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
916          "StartValue is not an integer for integer induction");
917 
918   // Check the Step Value. It should be non-zero integer value.
919   assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
920          "Step value is zero");
921 
922   assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
923          "Step value should be constant for pointer induction");
924   assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
925          "StepValue is not an integer");
926 
927   assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
928          "StepValue is not FP for FpInduction");
929   assert((IK != IK_FpInduction ||
930           (InductionBinOp &&
931            (InductionBinOp->getOpcode() == Instruction::FAdd ||
932             InductionBinOp->getOpcode() == Instruction::FSub))) &&
933          "Binary opcode should be specified for FP induction");
934 
935   if (Casts) {
936     for (auto &Inst : *Casts) {
937       RedundantCasts.push_back(Inst);
938     }
939   }
940 }
941 
942 ConstantInt *InductionDescriptor::getConstIntStepValue() const {
943   if (isa<SCEVConstant>(Step))
944     return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
945   return nullptr;
946 }
947 
948 bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
949                                            ScalarEvolution *SE,
950                                            InductionDescriptor &D) {
951 
952   // Here we only handle FP induction variables.
953   assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
954 
955   if (TheLoop->getHeader() != Phi->getParent())
956     return false;
957 
958   // The loop may have multiple entrances or multiple exits; we can analyze
959   // this phi if it has a unique entry value and a unique backedge value.
960   if (Phi->getNumIncomingValues() != 2)
961     return false;
962   Value *BEValue = nullptr, *StartValue = nullptr;
963   if (TheLoop->contains(Phi->getIncomingBlock(0))) {
964     BEValue = Phi->getIncomingValue(0);
965     StartValue = Phi->getIncomingValue(1);
966   } else {
967     assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
968            "Unexpected Phi node in the loop");
969     BEValue = Phi->getIncomingValue(1);
970     StartValue = Phi->getIncomingValue(0);
971   }
972 
973   BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
974   if (!BOp)
975     return false;
976 
977   Value *Addend = nullptr;
978   if (BOp->getOpcode() == Instruction::FAdd) {
979     if (BOp->getOperand(0) == Phi)
980       Addend = BOp->getOperand(1);
981     else if (BOp->getOperand(1) == Phi)
982       Addend = BOp->getOperand(0);
983   } else if (BOp->getOpcode() == Instruction::FSub)
984     if (BOp->getOperand(0) == Phi)
985       Addend = BOp->getOperand(1);
986 
987   if (!Addend)
988     return false;
989 
990   // The addend should be loop invariant
991   if (auto *I = dyn_cast<Instruction>(Addend))
992     if (TheLoop->contains(I))
993       return false;
994 
995   // FP Step has unknown SCEV
996   const SCEV *Step = SE->getUnknown(Addend);
997   D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
998   return true;
999 }
1000 
1001 /// This function is called when we suspect that the update-chain of a phi node
1002 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
1003 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
1004 /// predicate P under which the SCEV expression for the phi can be the
1005 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
1006 /// cast instructions that are involved in the update-chain of this induction.
1007 /// A caller that adds the required runtime predicate can be free to drop these
1008 /// cast instructions, and compute the phi using \p AR (instead of some scev
1009 /// expression with casts).
1010 ///
1011 /// For example, without a predicate the scev expression can take the following
1012 /// form:
1013 ///      (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
1014 ///
1015 /// It corresponds to the following IR sequence:
1016 /// %for.body:
1017 ///   %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
1018 ///   %casted_phi = "ExtTrunc i64 %x"
1019 ///   %add = add i64 %casted_phi, %step
1020 ///
1021 /// where %x is given in \p PN,
1022 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
1023 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
1024 /// several forms, for example, such as:
1025 ///   ExtTrunc1:    %casted_phi = and  %x, 2^n-1
1026 /// or:
1027 ///   ExtTrunc2:    %t = shl %x, m
1028 ///                 %casted_phi = ashr %t, m
1029 ///
1030 /// If we are able to find such sequence, we return the instructions
1031 /// we found, namely %casted_phi and the instructions on its use-def chain up
1032 /// to the phi (not including the phi).
1033 static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
1034                                     const SCEVUnknown *PhiScev,
1035                                     const SCEVAddRecExpr *AR,
1036                                     SmallVectorImpl<Instruction *> &CastInsts) {
1037 
1038   assert(CastInsts.empty() && "CastInsts is expected to be empty.");
1039   auto *PN = cast<PHINode>(PhiScev->getValue());
1040   assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
1041   const Loop *L = AR->getLoop();
1042 
1043   // Find any cast instructions that participate in the def-use chain of
1044   // PhiScev in the loop.
1045   // FORNOW/TODO: We currently expect the def-use chain to include only
1046   // two-operand instructions, where one of the operands is an invariant.
1047   // createAddRecFromPHIWithCasts() currently does not support anything more
1048   // involved than that, so we keep the search simple. This can be
1049   // extended/generalized as needed.
1050 
1051   auto getDef = [&](const Value *Val) -> Value * {
1052     const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
1053     if (!BinOp)
1054       return nullptr;
1055     Value *Op0 = BinOp->getOperand(0);
1056     Value *Op1 = BinOp->getOperand(1);
1057     Value *Def = nullptr;
1058     if (L->isLoopInvariant(Op0))
1059       Def = Op1;
1060     else if (L->isLoopInvariant(Op1))
1061       Def = Op0;
1062     return Def;
1063   };
1064 
1065   // Look for the instruction that defines the induction via the
1066   // loop backedge.
1067   BasicBlock *Latch = L->getLoopLatch();
1068   if (!Latch)
1069     return false;
1070   Value *Val = PN->getIncomingValueForBlock(Latch);
1071   if (!Val)
1072     return false;
1073 
1074   // Follow the def-use chain until the induction phi is reached.
1075   // If on the way we encounter a Value that has the same SCEV Expr as the
1076   // phi node, we can consider the instructions we visit from that point
1077   // as part of the cast-sequence that can be ignored.
1078   bool InCastSequence = false;
1079   auto *Inst = dyn_cast<Instruction>(Val);
1080   while (Val != PN) {
1081     // If we encountered a phi node other than PN, or if we left the loop,
1082     // we bail out.
1083     if (!Inst || !L->contains(Inst)) {
1084       return false;
1085     }
1086     auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
1087     if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
1088       InCastSequence = true;
1089     if (InCastSequence) {
1090       // Only the last instruction in the cast sequence is expected to have
1091       // uses outside the induction def-use chain.
1092       if (!CastInsts.empty())
1093         if (!Inst->hasOneUse())
1094           return false;
1095       CastInsts.push_back(Inst);
1096     }
1097     Val = getDef(Val);
1098     if (!Val)
1099       return false;
1100     Inst = dyn_cast<Instruction>(Val);
1101   }
1102 
1103   return InCastSequence;
1104 }
1105 
1106 bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
1107                                          PredicatedScalarEvolution &PSE,
1108                                          InductionDescriptor &D, bool Assume) {
1109   Type *PhiTy = Phi->getType();
1110 
1111   // Handle integer and pointer inductions variables.
1112   // Now we handle also FP induction but not trying to make a
1113   // recurrent expression from the PHI node in-place.
1114 
1115   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
1116       !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
1117     return false;
1118 
1119   if (PhiTy->isFloatingPointTy())
1120     return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
1121 
1122   const SCEV *PhiScev = PSE.getSCEV(Phi);
1123   const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1124 
1125   // We need this expression to be an AddRecExpr.
1126   if (Assume && !AR)
1127     AR = PSE.getAsAddRec(Phi);
1128 
1129   if (!AR) {
1130     LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1131     return false;
1132   }
1133 
1134   // Record any Cast instructions that participate in the induction update
1135   const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1136   // If we started from an UnknownSCEV, and managed to build an addRecurrence
1137   // only after enabling Assume with PSCEV, this means we may have encountered
1138   // cast instructions that required adding a runtime check in order to
1139   // guarantee the correctness of the AddRecurrence respresentation of the
1140   // induction.
1141   if (PhiScev != AR && SymbolicPhi) {
1142     SmallVector<Instruction *, 2> Casts;
1143     if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1144       return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1145   }
1146 
1147   return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1148 }
1149 
1150 bool InductionDescriptor::isInductionPHI(
1151     PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1152     InductionDescriptor &D, const SCEV *Expr,
1153     SmallVectorImpl<Instruction *> *CastsToIgnore) {
1154   Type *PhiTy = Phi->getType();
1155   // We only handle integer and pointer inductions variables.
1156   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1157     return false;
1158 
1159   // Check that the PHI is consecutive.
1160   const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1161   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1162 
1163   if (!AR) {
1164     LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1165     return false;
1166   }
1167 
1168   if (AR->getLoop() != TheLoop) {
1169     // FIXME: We should treat this as a uniform. Unfortunately, we
1170     // don't currently know how to handled uniform PHIs.
1171     LLVM_DEBUG(
1172         dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1173     return false;
1174   }
1175 
1176   Value *StartValue =
1177       Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
1178 
1179   BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1180   if (!Latch)
1181     return false;
1182   BinaryOperator *BOp =
1183       dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
1184 
1185   const SCEV *Step = AR->getStepRecurrence(*SE);
1186   // Calculate the pointer stride and check if it is consecutive.
1187   // The stride may be a constant or a loop invariant integer value.
1188   const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1189   if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1190     return false;
1191 
1192   if (PhiTy->isIntegerTy()) {
1193     D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1194                             CastsToIgnore);
1195     return true;
1196   }
1197 
1198   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1199   // Pointer induction should be a constant.
1200   if (!ConstStep)
1201     return false;
1202 
1203   ConstantInt *CV = ConstStep->getValue();
1204   Type *PointerElementType = PhiTy->getPointerElementType();
1205   // The pointer stride cannot be determined if the pointer element type is not
1206   // sized.
1207   if (!PointerElementType->isSized())
1208     return false;
1209 
1210   const DataLayout &DL = Phi->getModule()->getDataLayout();
1211   int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1212   if (!Size)
1213     return false;
1214 
1215   int64_t CVSize = CV->getSExtValue();
1216   if (CVSize % Size)
1217     return false;
1218   auto *StepValue =
1219       SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1220   D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);
1221   return true;
1222 }
1223