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