lib/Transforms/Utils/LoopUtils.cpp

   1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines common loop utility functions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  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"
  23
  24 using namespace llvm;
  25 using namespace llvm::PatternMatch;
  26
  27 #define DEBUG_TYPE "loop-utils"
  28
  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)))
  33       return false;
  34   return true;
  35 }
  36
  37 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
  38                                            Loop *TheLoop, bool HasFunNoNaNAttr,
  39                                            RecurrenceDescriptor &RedDes) {
  40   if (Phi->getNumIncomingValues() != 2)
  41     return false;
  42
  43   // Reduction variables are only found in the loop header block.
  44   if (Phi->getParent() != TheLoop->getHeader())
  45     return false;
  46
  47   // Obtain the reduction start value from the value that comes from the loop
  48   // preheader.
  49   Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
  50
  51   // ExitInstruction is the single value which is used outside the loop.
  52   // We only allow for a single reduction value to be used outside the loop.
  53   // This includes users of the reduction, variables (which form a cycle
  54   // which ends in the phi node).
  55   Instruction *ExitInstruction = nullptr;
  56   // Indicates that we found a reduction operation in our scan.
  57   bool FoundReduxOp = false;
  58
  59   // We start with the PHI node and scan for all of the users of this
  60   // instruction. All users must be instructions that can be used as reduction
  61   // variables (such as ADD). We must have a single out-of-block user. The cycle
  62   // must include the original PHI.
  63   bool FoundStartPHI = false;
  64
  65   // To recognize min/max patterns formed by a icmp select sequence, we store
  66   // the number of instruction we saw from the recognized min/max pattern,
  67   //  to make sure we only see exactly the two instructions.
  68   unsigned NumCmpSelectPatternInst = 0;
  69   InstDesc ReduxDesc(false, nullptr);
  70
  71   SmallPtrSet<Instruction *, 8> VisitedInsts;
  72   SmallVector<Instruction *, 8> Worklist;
  73   Worklist.push_back(Phi);
  74   VisitedInsts.insert(Phi);
  75
  76   // A value in the reduction can be used:
  77   //  - By the reduction:
  78   //      - Reduction operation:
  79   //        - One use of reduction value (safe).
  80   //        - Multiple use of reduction value (not safe).
  81   //      - PHI:
  82   //        - All uses of the PHI must be the reduction (safe).
  83   //        - Otherwise, not safe.
  84   //  - By one instruction outside of the loop (safe).
  85   //  - By further instructions outside of the loop (not safe).
  86   //  - By an instruction that is not part of the reduction (not safe).
  87   //    This is either:
  88   //      * An instruction type other than PHI or the reduction operation.
  89   //      * A PHI in the header other than the initial PHI.
  90   while (!Worklist.empty()) {
  91     Instruction *Cur = Worklist.back();
  92     Worklist.pop_back();
  93
  94     // No Users.
  95     // If the instruction has no users then this is a broken chain and can't be
  96     // a reduction variable.
  97     if (Cur->use_empty())
  98       return false;
  99
 100     bool IsAPhi = isa<PHINode>(Cur);
 101
 102     // A header PHI use other than the original PHI.
 103     if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
 104       return false;
 105
 106     // Reductions of instructions such as Div, and Sub is only possible if the
 107     // LHS is the reduction variable.
 108     if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
 109         !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
 110         !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
 111       return false;
 112
 113     // Any reduction instruction must be of one of the allowed kinds.
 114     ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
 115     if (!ReduxDesc.isRecurrence())
 116       return false;
 117
 118     // A reduction operation must only have one use of the reduction value.
 119     if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
 120         hasMultipleUsesOf(Cur, VisitedInsts))
 121       return false;
 122
 123     // All inputs to a PHI node must be a reduction value.
 124     if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
 125       return false;
 126
 127     if (Kind == RK_IntegerMinMax &&
 128         (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
 129       ++NumCmpSelectPatternInst;
 130     if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
 131       ++NumCmpSelectPatternInst;
 132
 133     // Check  whether we found a reduction operator.
 134     FoundReduxOp |= !IsAPhi;
 135
 136     // Process users of current instruction. Push non-PHI nodes after PHI nodes
 137     // onto the stack. This way we are going to have seen all inputs to PHI
 138     // nodes once we get to them.
 139     SmallVector<Instruction *, 8> NonPHIs;
 140     SmallVector<Instruction *, 8> PHIs;
 141     for (User *U : Cur->users()) {
 142       Instruction *UI = cast<Instruction>(U);
 143
 144       // Check if we found the exit user.
 145       BasicBlock *Parent = UI->getParent();
 146       if (!TheLoop->contains(Parent)) {
 147         // Exit if you find multiple outside users or if the header phi node is
 148         // being used. In this case the user uses the value of the previous
 149         // iteration, in which case we would loose "VF-1" iterations of the
 150         // reduction operation if we vectorize.
 151         if (ExitInstruction != nullptr || Cur == Phi)
 152           return false;
 153
 154         // The instruction used by an outside user must be the last instruction
 155         // before we feed back to the reduction phi. Otherwise, we loose VF-1
 156         // operations on the value.
 157         if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end())
 158           return false;
 159
 160         ExitInstruction = Cur;
 161         continue;
 162       }
 163
 164       // Process instructions only once (termination). Each reduction cycle
 165       // value must only be used once, except by phi nodes and min/max
 166       // reductions which are represented as a cmp followed by a select.
 167       InstDesc IgnoredVal(false, nullptr);
 168       if (VisitedInsts.insert(UI).second) {
 169         if (isa<PHINode>(UI))
 170           PHIs.push_back(UI);
 171         else
 172           NonPHIs.push_back(UI);
 173       } else if (!isa<PHINode>(UI) &&
 174                  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
 175                    !isa<SelectInst>(UI)) ||
 176                   !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
 177         return false;
 178
 179       // Remember that we completed the cycle.
 180       if (UI == Phi)
 181         FoundStartPHI = true;
 182     }
 183     Worklist.append(PHIs.begin(), PHIs.end());
 184     Worklist.append(NonPHIs.begin(), NonPHIs.end());
 185   }
 186
 187   // This means we have seen one but not the other instruction of the
 188   // pattern or more than just a select and cmp.
 189   if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
 190       NumCmpSelectPatternInst != 2)
 191     return false;
 192
 193   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
 194     return false;
 195
 196   // We found a reduction var if we have reached the original phi node and we
 197   // only have a single instruction with out-of-loop users.
 198
 199   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
 200   // is saved as part of the RecurrenceDescriptor.
 201
 202   // Save the description of this reduction variable.
 203   RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind,
 204                           ReduxDesc.getMinMaxKind(),
 205                           ReduxDesc.getUnsafeAlgebraInst());
 206
 207   RedDes = RD;
 208
 209   return true;
 210 }
 211
 212 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
 213 /// pattern corresponding to a min(X, Y) or max(X, Y).
 214 RecurrenceDescriptor::InstDesc
 215 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
 216
 217   assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
 218          "Expect a select instruction");
 219   Instruction *Cmp = nullptr;
 220   SelectInst *Select = nullptr;
 221
 222   // We must handle the select(cmp()) as a single instruction. Advance to the
 223   // select.
 224   if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
 225     if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
 226       return InstDesc(false, I);
 227     return InstDesc(Select, Prev.getMinMaxKind());
 228   }
 229
 230   // Only handle single use cases for now.
 231   if (!(Select = dyn_cast<SelectInst>(I)))
 232     return InstDesc(false, I);
 233   if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
 234       !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
 235     return InstDesc(false, I);
 236   if (!Cmp->hasOneUse())
 237     return InstDesc(false, I);
 238
 239   Value *CmpLeft;
 240   Value *CmpRight;
 241
 242   // Look for a min/max pattern.
 243   if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 244     return InstDesc(Select, MRK_UIntMin);
 245   else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 246     return InstDesc(Select, MRK_UIntMax);
 247   else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 248     return InstDesc(Select, MRK_SIntMax);
 249   else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 250     return InstDesc(Select, MRK_SIntMin);
 251   else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 252     return InstDesc(Select, MRK_FloatMin);
 253   else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 254     return InstDesc(Select, MRK_FloatMax);
 255   else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 256     return InstDesc(Select, MRK_FloatMin);
 257   else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 258     return InstDesc(Select, MRK_FloatMax);
 259
 260   return InstDesc(false, I);
 261 }
 262
 263 RecurrenceDescriptor::InstDesc
 264 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
 265                                         InstDesc &Prev, bool HasFunNoNaNAttr) {
 266   bool FP = I->getType()->isFloatingPointTy();
 267   Instruction *UAI = Prev.getUnsafeAlgebraInst();
 268   if (!UAI && FP && !I->hasUnsafeAlgebra())
 269     UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
 270
 271   switch (I->getOpcode()) {
 272   default:
 273     return InstDesc(false, I);
 274   case Instruction::PHI:
 275     if (FP &&
 276         (Kind != RK_FloatMult && Kind != RK_FloatAdd && Kind != RK_FloatMinMax))
 277       return InstDesc(false, I);
 278     return InstDesc(I, Prev.getMinMaxKind());
 279   case Instruction::Sub:
 280   case Instruction::Add:
 281     return InstDesc(Kind == RK_IntegerAdd, I);
 282   case Instruction::Mul:
 283     return InstDesc(Kind == RK_IntegerMult, I);
 284   case Instruction::And:
 285     return InstDesc(Kind == RK_IntegerAnd, I);
 286   case Instruction::Or:
 287     return InstDesc(Kind == RK_IntegerOr, I);
 288   case Instruction::Xor:
 289     return InstDesc(Kind == RK_IntegerXor, I);
 290   case Instruction::FMul:
 291     return InstDesc(Kind == RK_FloatMult, I, UAI);
 292   case Instruction::FSub:
 293   case Instruction::FAdd:
 294     return InstDesc(Kind == RK_FloatAdd, I, UAI);
 295   case Instruction::FCmp:
 296   case Instruction::ICmp:
 297   case Instruction::Select:
 298     if (Kind != RK_IntegerMinMax &&
 299         (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
 300       return InstDesc(false, I);
 301     return isMinMaxSelectCmpPattern(I, Prev);
 302   }
 303 }
 304
 305 bool RecurrenceDescriptor::hasMultipleUsesOf(
 306     Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
 307   unsigned NumUses = 0;
 308   for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
 309        ++Use) {
 310     if (Insts.count(dyn_cast<Instruction>(*Use)))
 311       ++NumUses;
 312     if (NumUses > 1)
 313       return true;
 314   }
 315
 316   return false;
 317 }
 318 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
 319                                           RecurrenceDescriptor &RedDes) {
 320
 321   bool HasFunNoNaNAttr = false;
 322   BasicBlock *Header = TheLoop->getHeader();
 323   Function &F = *Header->getParent();
 324   if (F.hasFnAttribute("no-nans-fp-math"))
 325     HasFunNoNaNAttr =
 326         F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 327
 328   if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 329     DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
 330     return true;
 331   }
 332   if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
 333     DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
 334     return true;
 335   }
 336   if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
 337     DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
 338     return true;
 339   }
 340   if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 341     DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
 342     return true;
 343   }
 344   if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
 345     DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
 346     return true;
 347   }
 348   if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
 349                       RedDes)) {
 350     DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
 351     return true;
 352   }
 353   if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
 354     DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
 355     return true;
 356   }
 357   if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 358     DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
 359     return true;
 360   }
 361   if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
 362     DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
 363     return true;
 364   }
 365   // Not a reduction of known type.
 366   return false;
 367 }
 368
 369 /// This function returns the identity element (or neutral element) for
 370 /// the operation K.
 371 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
 372                                                       Type *Tp) {
 373   switch (K) {
 374   case RK_IntegerXor:
 375   case RK_IntegerAdd:
 376   case RK_IntegerOr:
 377     // Adding, Xoring, Oring zero to a number does not change it.
 378     return ConstantInt::get(Tp, 0);
 379   case RK_IntegerMult:
 380     // Multiplying a number by 1 does not change it.
 381     return ConstantInt::get(Tp, 1);
 382   case RK_IntegerAnd:
 383     // AND-ing a number with an all-1 value does not change it.
 384     return ConstantInt::get(Tp, -1, true);
 385   case RK_FloatMult:
 386     // Multiplying a number by 1 does not change it.
 387     return ConstantFP::get(Tp, 1.0L);
 388   case RK_FloatAdd:
 389     // Adding zero to a number does not change it.
 390     return ConstantFP::get(Tp, 0.0L);
 391   default:
 392     llvm_unreachable("Unknown recurrence kind");
 393   }
 394 }
 395
 396 /// This function translates the recurrence kind to an LLVM binary operator.
 397 unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
 398   switch (Kind) {
 399   case RK_IntegerAdd:
 400     return Instruction::Add;
 401   case RK_IntegerMult:
 402     return Instruction::Mul;
 403   case RK_IntegerOr:
 404     return Instruction::Or;
 405   case RK_IntegerAnd:
 406     return Instruction::And;
 407   case RK_IntegerXor:
 408     return Instruction::Xor;
 409   case RK_FloatMult:
 410     return Instruction::FMul;
 411   case RK_FloatAdd:
 412     return Instruction::FAdd;
 413   case RK_IntegerMinMax:
 414     return Instruction::ICmp;
 415   case RK_FloatMinMax:
 416     return Instruction::FCmp;
 417   default:
 418     llvm_unreachable("Unknown recurrence operation");
 419   }
 420 }
 421
 422 Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
 423                                             MinMaxRecurrenceKind RK,
 424                                             Value *Left, Value *Right) {
 425   CmpInst::Predicate P = CmpInst::ICMP_NE;
 426   switch (RK) {
 427   default:
 428     llvm_unreachable("Unknown min/max recurrence kind");
 429   case MRK_UIntMin:
 430     P = CmpInst::ICMP_ULT;
 431     break;
 432   case MRK_UIntMax:
 433     P = CmpInst::ICMP_UGT;
 434     break;
 435   case MRK_SIntMin:
 436     P = CmpInst::ICMP_SLT;
 437     break;
 438   case MRK_SIntMax:
 439     P = CmpInst::ICMP_SGT;
 440     break;
 441   case MRK_FloatMin:
 442     P = CmpInst::FCMP_OLT;
 443     break;
 444   case MRK_FloatMax:
 445     P = CmpInst::FCMP_OGT;
 446     break;
 447   }
 448
 449   Value *Cmp;
 450   if (RK == MRK_FloatMin || RK == MRK_FloatMax)
 451     Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
 452   else
 453     Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
 454
 455   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
 456   return Select;
 457 }
 458
 459 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
 460                                          ConstantInt *Step)
 461   : StartValue(Start), IK(K), StepValue(Step) {
 462   assert(IK != IK_NoInduction && "Not an induction");
 463   assert(StartValue && "StartValue is null");
 464   assert(StepValue && !StepValue->isZero() && "StepValue is zero");
 465   assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
 466          "StartValue is not a pointer for pointer induction");
 467   assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
 468          "StartValue is not an integer for integer induction");
 469   assert(StepValue->getType()->isIntegerTy() &&
 470          "StepValue is not an integer");
 471 }
 472
 473 int InductionDescriptor::getConsecutiveDirection() const {
 474   if (StepValue && (StepValue->isOne() || StepValue->isMinusOne()))
 475     return StepValue->getSExtValue();
 476   return 0;
 477 }
 478
 479 Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index) const {
 480   switch (IK) {
 481   case IK_IntInduction:
 482     assert(Index->getType() == StartValue->getType() &&
 483            "Index type does not match StartValue type");
 484     if (StepValue->isMinusOne())
 485       return B.CreateSub(StartValue, Index);
 486     if (!StepValue->isOne())
 487       Index = B.CreateMul(Index, StepValue);
 488     return B.CreateAdd(StartValue, Index);
 489
 490   case IK_PtrInduction:
 491     assert(Index->getType() == StepValue->getType() &&
 492            "Index type does not match StepValue type");
 493     if (StepValue->isMinusOne())
 494       Index = B.CreateNeg(Index);
 495     else if (!StepValue->isOne())
 496       Index = B.CreateMul(Index, StepValue);
 497     return B.CreateGEP(nullptr, StartValue, Index);
 498
 499   case IK_NoInduction:
 500     return nullptr;
 501   }
 502   llvm_unreachable("invalid enum");
 503 }
 504
 505 bool InductionDescriptor::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
 506                                          InductionDescriptor &D) {
 507   Type *PhiTy = Phi->getType();
 508   // We only handle integer and pointer inductions variables.
 509   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
 510     return false;
 511
 512   // Check that the PHI is consecutive.
 513   const SCEV *PhiScev = SE->getSCEV(Phi);
 514   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
 515   if (!AR) {
 516     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
 517     return false;
 518   }
 519
 520   assert(AR->getLoop()->getHeader() == Phi->getParent() &&
 521          "PHI is an AddRec for a different loop?!");
 522   Value *StartValue =
 523     Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
 524   const SCEV *Step = AR->getStepRecurrence(*SE);
 525   // Calculate the pointer stride and check if it is consecutive.
 526   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
 527   if (!C)
 528     return false;
 529
 530   ConstantInt *CV = C->getValue();
 531   if (PhiTy->isIntegerTy()) {
 532     D = InductionDescriptor(StartValue, IK_IntInduction, CV);
 533     return true;
 534   }
 535
 536   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
 537   Type *PointerElementType = PhiTy->getPointerElementType();
 538   // The pointer stride cannot be determined if the pointer element type is not
 539   // sized.
 540   if (!PointerElementType->isSized())
 541     return false;
 542
 543   const DataLayout &DL = Phi->getModule()->getDataLayout();
 544   int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
 545   if (!Size)
 546     return false;
 547
 548   int64_t CVSize = CV->getSExtValue();
 549   if (CVSize % Size)
 550     return false;
 551   auto *StepValue = ConstantInt::getSigned(CV->getType(), CVSize / Size);
 552
 553   D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
 554   return true;
 555 }
 556
 557 /// \brief Returns the instructions that use values defined in the loop.
 558 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
 559   SmallVector<Instruction *, 8> UsedOutside;
 560
 561   for (auto *Block : L->getBlocks())
 562     // FIXME: I believe that this could use copy_if if the Inst reference could
 563     // be adapted into a pointer.
 564     for (auto &Inst : *Block) {
 565       auto Users = Inst.users();
 566       if (std::any_of(Users.begin(), Users.end(), [&](User *U) {
 567             auto *Use = cast<Instruction>(U);
 568             return !L->contains(Use->getParent());
 569           }))
 570         UsedOutside.push_back(&Inst);
 571     }
 572
 573   return UsedOutside;
 574 }