1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines common loop utility functions.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/IR/Instructions.h"
16 #include "llvm/IR/PatternMatch.h"
17 #include "llvm/IR/ValueHandle.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Analysis/ScalarEvolution.h"
20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/Transforms/Utils/LoopUtils.h"
25 using namespace llvm::PatternMatch;
27 #define DEBUG_TYPE "loop-utils"
29 bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
30 SmallPtrSetImpl<Instruction *> &Set) {
31 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
32 if (!Set.count(dyn_cast<Instruction>(*Use)))
37 bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
46 case RK_IntegerMinMax:
52 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
53 return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
56 bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
70 RecurrenceDescriptor::lookThroughAnd(PHINode *Phi, Type *&RT,
71 SmallPtrSetImpl<Instruction *> &Visited,
72 SmallPtrSetImpl<Instruction *> &CI) {
73 if (!Phi->hasOneUse())
76 const APInt *M = nullptr;
77 Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
79 // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
80 // with a new integer type of the corresponding bit width.
81 if (match(J, m_CombineOr(m_And(m_Instruction(I), m_APInt(M)),
82 m_And(m_APInt(M), m_Instruction(I))))) {
83 int32_t Bits = (*M + 1).exactLogBase2();
85 RT = IntegerType::get(Phi->getContext(), Bits);
94 bool RecurrenceDescriptor::getSourceExtensionKind(
95 Instruction *Start, Instruction *Exit, Type *RT, bool &IsSigned,
96 SmallPtrSetImpl<Instruction *> &Visited,
97 SmallPtrSetImpl<Instruction *> &CI) {
99 SmallVector<Instruction *, 8> Worklist;
100 bool FoundOneOperand = false;
101 unsigned DstSize = RT->getPrimitiveSizeInBits();
102 Worklist.push_back(Exit);
104 // Traverse the instructions in the reduction expression, beginning with the
106 while (!Worklist.empty()) {
107 Instruction *I = Worklist.pop_back_val();
108 for (Use &U : I->operands()) {
110 // Terminate the traversal if the operand is not an instruction, or we
111 // reach the starting value.
112 Instruction *J = dyn_cast<Instruction>(U.get());
113 if (!J || J == Start)
116 // Otherwise, investigate the operation if it is also in the expression.
117 if (Visited.count(J)) {
118 Worklist.push_back(J);
122 // If the operand is not in Visited, it is not a reduction operation, but
123 // it does feed into one. Make sure it is either a single-use sign- or
124 // zero-extend instruction.
125 CastInst *Cast = dyn_cast<CastInst>(J);
126 bool IsSExtInst = isa<SExtInst>(J);
127 if (!Cast || !Cast->hasOneUse() || !(isa<ZExtInst>(J) || IsSExtInst))
130 // Ensure the source type of the extend is no larger than the reduction
131 // type. It is not necessary for the types to be identical.
132 unsigned SrcSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
133 if (SrcSize > DstSize)
136 // Furthermore, ensure that all such extends are of the same kind.
137 if (FoundOneOperand) {
138 if (IsSigned != IsSExtInst)
141 FoundOneOperand = true;
142 IsSigned = IsSExtInst;
145 // Lastly, if the source type of the extend matches the reduction type,
146 // add the extend to CI so that we can avoid accounting for it in the
148 if (SrcSize == DstSize)
155 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
156 Loop *TheLoop, bool HasFunNoNaNAttr,
157 RecurrenceDescriptor &RedDes) {
158 if (Phi->getNumIncomingValues() != 2)
161 // Reduction variables are only found in the loop header block.
162 if (Phi->getParent() != TheLoop->getHeader())
165 // Obtain the reduction start value from the value that comes from the loop
167 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
169 // ExitInstruction is the single value which is used outside the loop.
170 // We only allow for a single reduction value to be used outside the loop.
171 // This includes users of the reduction, variables (which form a cycle
172 // which ends in the phi node).
173 Instruction *ExitInstruction = nullptr;
174 // Indicates that we found a reduction operation in our scan.
175 bool FoundReduxOp = false;
177 // We start with the PHI node and scan for all of the users of this
178 // instruction. All users must be instructions that can be used as reduction
179 // variables (such as ADD). We must have a single out-of-block user. The cycle
180 // must include the original PHI.
181 bool FoundStartPHI = false;
183 // To recognize min/max patterns formed by a icmp select sequence, we store
184 // the number of instruction we saw from the recognized min/max pattern,
185 // to make sure we only see exactly the two instructions.
186 unsigned NumCmpSelectPatternInst = 0;
187 InstDesc ReduxDesc(false, nullptr);
189 // Data used for determining if the recurrence has been type-promoted.
190 Type *RecurrenceType = Phi->getType();
191 SmallPtrSet<Instruction *, 4> CastInsts;
192 Instruction *Start = Phi;
193 bool IsSigned = false;
195 SmallPtrSet<Instruction *, 8> VisitedInsts;
196 SmallVector<Instruction *, 8> Worklist;
198 // Return early if the recurrence kind does not match the type of Phi. If the
199 // recurrence kind is arithmetic, we attempt to look through AND operations
200 // resulting from the type promotion performed by InstCombine. Vector
201 // operations are not limited to the legal integer widths, so we may be able
202 // to evaluate the reduction in the narrower width.
203 if (RecurrenceType->isFloatingPointTy()) {
204 if (!isFloatingPointRecurrenceKind(Kind))
207 if (!isIntegerRecurrenceKind(Kind))
209 if (isArithmeticRecurrenceKind(Kind))
210 Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
213 Worklist.push_back(Start);
214 VisitedInsts.insert(Start);
216 // A value in the reduction can be used:
217 // - By the reduction:
218 // - Reduction operation:
219 // - One use of reduction value (safe).
220 // - Multiple use of reduction value (not safe).
222 // - All uses of the PHI must be the reduction (safe).
223 // - Otherwise, not safe.
224 // - By one instruction outside of the loop (safe).
225 // - By further instructions outside of the loop (not safe).
226 // - By an instruction that is not part of the reduction (not safe).
228 // * An instruction type other than PHI or the reduction operation.
229 // * A PHI in the header other than the initial PHI.
230 while (!Worklist.empty()) {
231 Instruction *Cur = Worklist.back();
235 // If the instruction has no users then this is a broken chain and can't be
236 // a reduction variable.
237 if (Cur->use_empty())
240 bool IsAPhi = isa<PHINode>(Cur);
242 // A header PHI use other than the original PHI.
243 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
246 // Reductions of instructions such as Div, and Sub is only possible if the
247 // LHS is the reduction variable.
248 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
249 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
250 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
253 // Any reduction instruction must be of one of the allowed kinds. We ignore
254 // the starting value (the Phi or an AND instruction if the Phi has been
257 ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
258 if (!ReduxDesc.isRecurrence())
262 // A reduction operation must only have one use of the reduction value.
263 if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
264 hasMultipleUsesOf(Cur, VisitedInsts))
267 // All inputs to a PHI node must be a reduction value.
268 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
271 if (Kind == RK_IntegerMinMax &&
272 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
273 ++NumCmpSelectPatternInst;
274 if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
275 ++NumCmpSelectPatternInst;
277 // Check whether we found a reduction operator.
278 FoundReduxOp |= !IsAPhi && Cur != Start;
280 // Process users of current instruction. Push non-PHI nodes after PHI nodes
281 // onto the stack. This way we are going to have seen all inputs to PHI
282 // nodes once we get to them.
283 SmallVector<Instruction *, 8> NonPHIs;
284 SmallVector<Instruction *, 8> PHIs;
285 for (User *U : Cur->users()) {
286 Instruction *UI = cast<Instruction>(U);
288 // Check if we found the exit user.
289 BasicBlock *Parent = UI->getParent();
290 if (!TheLoop->contains(Parent)) {
291 // Exit if you find multiple outside users or if the header phi node is
292 // being used. In this case the user uses the value of the previous
293 // iteration, in which case we would loose "VF-1" iterations of the
294 // reduction operation if we vectorize.
295 if (ExitInstruction != nullptr || Cur == Phi)
298 // The instruction used by an outside user must be the last instruction
299 // before we feed back to the reduction phi. Otherwise, we loose VF-1
300 // operations on the value.
301 if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end())
304 ExitInstruction = Cur;
308 // Process instructions only once (termination). Each reduction cycle
309 // value must only be used once, except by phi nodes and min/max
310 // reductions which are represented as a cmp followed by a select.
311 InstDesc IgnoredVal(false, nullptr);
312 if (VisitedInsts.insert(UI).second) {
313 if (isa<PHINode>(UI))
316 NonPHIs.push_back(UI);
317 } else if (!isa<PHINode>(UI) &&
318 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
319 !isa<SelectInst>(UI)) ||
320 !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
323 // Remember that we completed the cycle.
325 FoundStartPHI = true;
327 Worklist.append(PHIs.begin(), PHIs.end());
328 Worklist.append(NonPHIs.begin(), NonPHIs.end());
331 // This means we have seen one but not the other instruction of the
332 // pattern or more than just a select and cmp.
333 if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
334 NumCmpSelectPatternInst != 2)
337 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
340 // If we think Phi may have been type-promoted, we also need to ensure that
341 // all source operands of the reduction are either SExtInsts or ZEstInsts. If
342 // so, we will be able to evaluate the reduction in the narrower bit width.
344 if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
345 IsSigned, VisitedInsts, CastInsts))
348 // We found a reduction var if we have reached the original phi node and we
349 // only have a single instruction with out-of-loop users.
351 // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
352 // is saved as part of the RecurrenceDescriptor.
354 // Save the description of this reduction variable.
355 RecurrenceDescriptor RD(
356 RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
357 ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
363 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
364 /// pattern corresponding to a min(X, Y) or max(X, Y).
365 RecurrenceDescriptor::InstDesc
366 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
368 assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
369 "Expect a select instruction");
370 Instruction *Cmp = nullptr;
371 SelectInst *Select = nullptr;
373 // We must handle the select(cmp()) as a single instruction. Advance to the
375 if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
376 if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
377 return InstDesc(false, I);
378 return InstDesc(Select, Prev.getMinMaxKind());
381 // Only handle single use cases for now.
382 if (!(Select = dyn_cast<SelectInst>(I)))
383 return InstDesc(false, I);
384 if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
385 !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
386 return InstDesc(false, I);
387 if (!Cmp->hasOneUse())
388 return InstDesc(false, I);
393 // Look for a min/max pattern.
394 if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
395 return InstDesc(Select, MRK_UIntMin);
396 else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
397 return InstDesc(Select, MRK_UIntMax);
398 else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
399 return InstDesc(Select, MRK_SIntMax);
400 else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
401 return InstDesc(Select, MRK_SIntMin);
402 else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
403 return InstDesc(Select, MRK_FloatMin);
404 else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
405 return InstDesc(Select, MRK_FloatMax);
406 else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
407 return InstDesc(Select, MRK_FloatMin);
408 else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
409 return InstDesc(Select, MRK_FloatMax);
411 return InstDesc(false, I);
414 RecurrenceDescriptor::InstDesc
415 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
416 InstDesc &Prev, bool HasFunNoNaNAttr) {
417 bool FP = I->getType()->isFloatingPointTy();
418 Instruction *UAI = Prev.getUnsafeAlgebraInst();
419 if (!UAI && FP && !I->hasUnsafeAlgebra())
420 UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
422 switch (I->getOpcode()) {
424 return InstDesc(false, I);
425 case Instruction::PHI:
426 return InstDesc(I, Prev.getMinMaxKind());
427 case Instruction::Sub:
428 case Instruction::Add:
429 return InstDesc(Kind == RK_IntegerAdd, I);
430 case Instruction::Mul:
431 return InstDesc(Kind == RK_IntegerMult, I);
432 case Instruction::And:
433 return InstDesc(Kind == RK_IntegerAnd, I);
434 case Instruction::Or:
435 return InstDesc(Kind == RK_IntegerOr, I);
436 case Instruction::Xor:
437 return InstDesc(Kind == RK_IntegerXor, I);
438 case Instruction::FMul:
439 return InstDesc(Kind == RK_FloatMult, I, UAI);
440 case Instruction::FSub:
441 case Instruction::FAdd:
442 return InstDesc(Kind == RK_FloatAdd, I, UAI);
443 case Instruction::FCmp:
444 case Instruction::ICmp:
445 case Instruction::Select:
446 if (Kind != RK_IntegerMinMax &&
447 (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
448 return InstDesc(false, I);
449 return isMinMaxSelectCmpPattern(I, Prev);
453 bool RecurrenceDescriptor::hasMultipleUsesOf(
454 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
455 unsigned NumUses = 0;
456 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
458 if (Insts.count(dyn_cast<Instruction>(*Use)))
466 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
467 RecurrenceDescriptor &RedDes) {
469 bool HasFunNoNaNAttr = false;
470 BasicBlock *Header = TheLoop->getHeader();
471 Function &F = *Header->getParent();
472 if (F.hasFnAttribute("no-nans-fp-math"))
474 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
476 if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
477 DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
480 if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
481 DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
484 if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
485 DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
488 if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
489 DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
492 if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
493 DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
496 if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
498 DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
501 if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
502 DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
505 if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
506 DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
509 if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
510 DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
513 // Not a reduction of known type.
517 /// This function returns the identity element (or neutral element) for
519 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
525 // Adding, Xoring, Oring zero to a number does not change it.
526 return ConstantInt::get(Tp, 0);
528 // Multiplying a number by 1 does not change it.
529 return ConstantInt::get(Tp, 1);
531 // AND-ing a number with an all-1 value does not change it.
532 return ConstantInt::get(Tp, -1, true);
534 // Multiplying a number by 1 does not change it.
535 return ConstantFP::get(Tp, 1.0L);
537 // Adding zero to a number does not change it.
538 return ConstantFP::get(Tp, 0.0L);
540 llvm_unreachable("Unknown recurrence kind");
544 /// This function translates the recurrence kind to an LLVM binary operator.
545 unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
548 return Instruction::Add;
550 return Instruction::Mul;
552 return Instruction::Or;
554 return Instruction::And;
556 return Instruction::Xor;
558 return Instruction::FMul;
560 return Instruction::FAdd;
561 case RK_IntegerMinMax:
562 return Instruction::ICmp;
564 return Instruction::FCmp;
566 llvm_unreachable("Unknown recurrence operation");
570 Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
571 MinMaxRecurrenceKind RK,
572 Value *Left, Value *Right) {
573 CmpInst::Predicate P = CmpInst::ICMP_NE;
576 llvm_unreachable("Unknown min/max recurrence kind");
578 P = CmpInst::ICMP_ULT;
581 P = CmpInst::ICMP_UGT;
584 P = CmpInst::ICMP_SLT;
587 P = CmpInst::ICMP_SGT;
590 P = CmpInst::FCMP_OLT;
593 P = CmpInst::FCMP_OGT;
597 // We only match FP sequences with unsafe algebra, so we can unconditionally
598 // set it on any generated instructions.
599 IRBuilder<>::FastMathFlagGuard FMFG(Builder);
601 FMF.setUnsafeAlgebra();
602 Builder.SetFastMathFlags(FMF);
605 if (RK == MRK_FloatMin || RK == MRK_FloatMax)
606 Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
608 Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
610 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
614 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
616 : StartValue(Start), IK(K), StepValue(Step) {
617 assert(IK != IK_NoInduction && "Not an induction");
618 assert(StartValue && "StartValue is null");
619 assert(StepValue && !StepValue->isZero() && "StepValue is zero");
620 assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
621 "StartValue is not a pointer for pointer induction");
622 assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
623 "StartValue is not an integer for integer induction");
624 assert(StepValue->getType()->isIntegerTy() &&
625 "StepValue is not an integer");
628 int InductionDescriptor::getConsecutiveDirection() const {
629 if (StepValue && (StepValue->isOne() || StepValue->isMinusOne()))
630 return StepValue->getSExtValue();
634 Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index) const {
636 case IK_IntInduction:
637 assert(Index->getType() == StartValue->getType() &&
638 "Index type does not match StartValue type");
639 if (StepValue->isMinusOne())
640 return B.CreateSub(StartValue, Index);
641 if (!StepValue->isOne())
642 Index = B.CreateMul(Index, StepValue);
643 return B.CreateAdd(StartValue, Index);
645 case IK_PtrInduction:
646 assert(Index->getType() == StepValue->getType() &&
647 "Index type does not match StepValue type");
648 if (StepValue->isMinusOne())
649 Index = B.CreateNeg(Index);
650 else if (!StepValue->isOne())
651 Index = B.CreateMul(Index, StepValue);
652 return B.CreateGEP(nullptr, StartValue, Index);
657 llvm_unreachable("invalid enum");
660 bool InductionDescriptor::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
661 InductionDescriptor &D) {
662 Type *PhiTy = Phi->getType();
663 // We only handle integer and pointer inductions variables.
664 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
667 // Check that the PHI is consecutive.
668 const SCEV *PhiScev = SE->getSCEV(Phi);
669 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
671 DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
675 assert(AR->getLoop()->getHeader() == Phi->getParent() &&
676 "PHI is an AddRec for a different loop?!");
678 Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
679 const SCEV *Step = AR->getStepRecurrence(*SE);
680 // Calculate the pointer stride and check if it is consecutive.
681 const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
685 ConstantInt *CV = C->getValue();
686 if (PhiTy->isIntegerTy()) {
687 D = InductionDescriptor(StartValue, IK_IntInduction, CV);
691 assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
692 Type *PointerElementType = PhiTy->getPointerElementType();
693 // The pointer stride cannot be determined if the pointer element type is not
695 if (!PointerElementType->isSized())
698 const DataLayout &DL = Phi->getModule()->getDataLayout();
699 int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
703 int64_t CVSize = CV->getSExtValue();
706 auto *StepValue = ConstantInt::getSigned(CV->getType(), CVSize / Size);
708 D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
712 /// \brief Returns the instructions that use values defined in the loop.
713 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
714 SmallVector<Instruction *, 8> UsedOutside;
716 for (auto *Block : L->getBlocks())
717 // FIXME: I believe that this could use copy_if if the Inst reference could
718 // be adapted into a pointer.
719 for (auto &Inst : *Block) {
720 auto Users = Inst.users();
721 if (std::any_of(Users.begin(), Users.end(), [&](User *U) {
722 auto *Use = cast<Instruction>(U);
723 return !L->contains(Use->getParent());
725 UsedOutside.push_back(&Inst);