contrib/llvm/lib/Analysis/IVDescriptors.cpp

   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/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/ScalarEvolutionExpander.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
  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
  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
  66 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
  67   return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
  68 }
  69
  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.
  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.
 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.
 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
 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       if (isa<FPMathOperator>(ReduxDesc.getPatternInst()))
 304         FMF &= ReduxDesc.getPatternInst()->getFastMathFlags();
 305     }
 306
 307     bool IsASelect = isa<SelectInst>(Cur);
 308
 309     // A conditional reduction operation must only have 2 or less uses in
 310     // VisitedInsts.
 311     if (IsASelect && (Kind == RK_FloatAdd || Kind == RK_FloatMult) &&
 312         hasMultipleUsesOf(Cur, VisitedInsts, 2))
 313       return false;
 314
 315     // A reduction operation must only have one use of the reduction value.
 316     if (!IsAPhi && !IsASelect && Kind != RK_IntegerMinMax &&
 317         Kind != RK_FloatMinMax && hasMultipleUsesOf(Cur, VisitedInsts, 1))
 318       return false;
 319
 320     // All inputs to a PHI node must be a reduction value.
 321     if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
 322       return false;
 323
 324     if (Kind == RK_IntegerMinMax &&
 325         (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
 326       ++NumCmpSelectPatternInst;
 327     if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
 328       ++NumCmpSelectPatternInst;
 329
 330     // Check  whether we found a reduction operator.
 331     FoundReduxOp |= !IsAPhi && Cur != Start;
 332
 333     // Process users of current instruction. Push non-PHI nodes after PHI nodes
 334     // onto the stack. This way we are going to have seen all inputs to PHI
 335     // nodes once we get to them.
 336     SmallVector<Instruction *, 8> NonPHIs;
 337     SmallVector<Instruction *, 8> PHIs;
 338     for (User *U : Cur->users()) {
 339       Instruction *UI = cast<Instruction>(U);
 340
 341       // Check if we found the exit user.
 342       BasicBlock *Parent = UI->getParent();
 343       if (!TheLoop->contains(Parent)) {
 344         // If we already know this instruction is used externally, move on to
 345         // the next user.
 346         if (ExitInstruction == Cur)
 347           continue;
 348
 349         // Exit if you find multiple values used outside or if the header phi
 350         // node is being used. In this case the user uses the value of the
 351         // previous iteration, in which case we would loose "VF-1" iterations of
 352         // the reduction operation if we vectorize.
 353         if (ExitInstruction != nullptr || Cur == Phi)
 354           return false;
 355
 356         // The instruction used by an outside user must be the last instruction
 357         // before we feed back to the reduction phi. Otherwise, we loose VF-1
 358         // operations on the value.
 359         if (!is_contained(Phi->operands(), Cur))
 360           return false;
 361
 362         ExitInstruction = Cur;
 363         continue;
 364       }
 365
 366       // Process instructions only once (termination). Each reduction cycle
 367       // value must only be used once, except by phi nodes and min/max
 368       // reductions which are represented as a cmp followed by a select.
 369       InstDesc IgnoredVal(false, nullptr);
 370       if (VisitedInsts.insert(UI).second) {
 371         if (isa<PHINode>(UI))
 372           PHIs.push_back(UI);
 373         else
 374           NonPHIs.push_back(UI);
 375       } else if (!isa<PHINode>(UI) &&
 376                  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
 377                    !isa<SelectInst>(UI)) ||
 378                   (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
 379                    !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())))
 380         return false;
 381
 382       // Remember that we completed the cycle.
 383       if (UI == Phi)
 384         FoundStartPHI = true;
 385     }
 386     Worklist.append(PHIs.begin(), PHIs.end());
 387     Worklist.append(NonPHIs.begin(), NonPHIs.end());
 388   }
 389
 390   // This means we have seen one but not the other instruction of the
 391   // pattern or more than just a select and cmp.
 392   if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
 393       NumCmpSelectPatternInst != 2)
 394     return false;
 395
 396   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
 397     return false;
 398
 399   if (Start != Phi) {
 400     // If the starting value is not the same as the phi node, we speculatively
 401     // looked through an 'and' instruction when evaluating a potential
 402     // arithmetic reduction to determine if it may have been type-promoted.
 403     //
 404     // We now compute the minimal bit width that is required to represent the
 405     // reduction. If this is the same width that was indicated by the 'and', we
 406     // can represent the reduction in the smaller type. The 'and' instruction
 407     // will be eliminated since it will essentially be a cast instruction that
 408     // can be ignore in the cost model. If we compute a different type than we
 409     // did when evaluating the 'and', the 'and' will not be eliminated, and we
 410     // will end up with different kinds of operations in the recurrence
 411     // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is
 412     // the case.
 413     //
 414     // The vectorizer relies on InstCombine to perform the actual
 415     // type-shrinking. It does this by inserting instructions to truncate the
 416     // exit value of the reduction to the width indicated by RecurrenceType and
 417     // then extend this value back to the original width. If IsSigned is false,
 418     // a 'zext' instruction will be generated; otherwise, a 'sext' will be
 419     // used.
 420     //
 421     // TODO: We should not rely on InstCombine to rewrite the reduction in the
 422     //       smaller type. We should just generate a correctly typed expression
 423     //       to begin with.
 424     Type *ComputedType;
 425     std::tie(ComputedType, IsSigned) =
 426         computeRecurrenceType(ExitInstruction, DB, AC, DT);
 427     if (ComputedType != RecurrenceType)
 428       return false;
 429
 430     // The recurrence expression will be represented in a narrower type. If
 431     // there are any cast instructions that will be unnecessary, collect them
 432     // in CastInsts. Note that the 'and' instruction was already included in
 433     // this list.
 434     //
 435     // TODO: A better way to represent this may be to tag in some way all the
 436     //       instructions that are a part of the reduction. The vectorizer cost
 437     //       model could then apply the recurrence type to these instructions,
 438     //       without needing a white list of instructions to ignore.
 439     collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
 440   }
 441
 442   // We found a reduction var if we have reached the original phi node and we
 443   // only have a single instruction with out-of-loop users.
 444
 445   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
 446   // is saved as part of the RecurrenceDescriptor.
 447
 448   // Save the description of this reduction variable.
 449   RecurrenceDescriptor RD(
 450       RdxStart, ExitInstruction, Kind, FMF, ReduxDesc.getMinMaxKind(),
 451       ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
 452   RedDes = RD;
 453
 454   return true;
 455 }
 456
 457 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
 458 /// pattern corresponding to a min(X, Y) or max(X, Y).
 459 RecurrenceDescriptor::InstDesc
 460 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
 461
 462   assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
 463          "Expect a select instruction");
 464   Instruction *Cmp = nullptr;
 465   SelectInst *Select = nullptr;
 466
 467   // We must handle the select(cmp()) as a single instruction. Advance to the
 468   // select.
 469   if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
 470     if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
 471       return InstDesc(false, I);
 472     return InstDesc(Select, Prev.getMinMaxKind());
 473   }
 474
 475   // Only handle single use cases for now.
 476   if (!(Select = dyn_cast<SelectInst>(I)))
 477     return InstDesc(false, I);
 478   if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
 479       !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
 480     return InstDesc(false, I);
 481   if (!Cmp->hasOneUse())
 482     return InstDesc(false, I);
 483
 484   Value *CmpLeft;
 485   Value *CmpRight;
 486
 487   // Look for a min/max pattern.
 488   if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 489     return InstDesc(Select, MRK_UIntMin);
 490   else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 491     return InstDesc(Select, MRK_UIntMax);
 492   else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 493     return InstDesc(Select, MRK_SIntMax);
 494   else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 495     return InstDesc(Select, MRK_SIntMin);
 496   else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 497     return InstDesc(Select, MRK_FloatMin);
 498   else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 499     return InstDesc(Select, MRK_FloatMax);
 500   else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 501     return InstDesc(Select, MRK_FloatMin);
 502   else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 503     return InstDesc(Select, MRK_FloatMax);
 504
 505   return InstDesc(false, I);
 506 }
 507
 508 /// Returns true if the select instruction has users in the compare-and-add
 509 /// reduction pattern below. The select instruction argument is the last one
 510 /// in the sequence.
 511 ///
 512 /// %sum.1 = phi ...
 513 /// ...
 514 /// %cmp = fcmp pred %0, %CFP
 515 /// %add = fadd %0, %sum.1
 516 /// %sum.2 = select %cmp, %add, %sum.1
 517 RecurrenceDescriptor::InstDesc
 518 RecurrenceDescriptor::isConditionalRdxPattern(
 519     RecurrenceKind 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 == RK_FloatAdd, SI);
 548
 549   if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
 550     return InstDesc(Kind == RK_FloatMult, SI);
 551
 552   return InstDesc(false, I);
 553 }
 554
 555 RecurrenceDescriptor::InstDesc
 556 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind 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.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
 567   case Instruction::Sub:
 568   case Instruction::Add:
 569     return InstDesc(Kind == RK_IntegerAdd, I);
 570   case Instruction::Mul:
 571     return InstDesc(Kind == RK_IntegerMult, I);
 572   case Instruction::And:
 573     return InstDesc(Kind == RK_IntegerAnd, I);
 574   case Instruction::Or:
 575     return InstDesc(Kind == RK_IntegerOr, I);
 576   case Instruction::Xor:
 577     return InstDesc(Kind == RK_IntegerXor, I);
 578   case Instruction::FMul:
 579     return InstDesc(Kind == RK_FloatMult, I, UAI);
 580   case Instruction::FSub:
 581   case Instruction::FAdd:
 582     return InstDesc(Kind == RK_FloatAdd, I, UAI);
 583   case Instruction::Select:
 584     if (Kind == RK_FloatAdd || Kind == RK_FloatMult)
 585       return isConditionalRdxPattern(Kind, I);
 586     LLVM_FALLTHROUGH;
 587   case Instruction::FCmp:
 588   case Instruction::ICmp:
 589     if (Kind != RK_IntegerMinMax &&
 590         (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
 591       return InstDesc(false, I);
 592     return isMinMaxSelectCmpPattern(I, Prev);
 593   }
 594 }
 595
 596 bool RecurrenceDescriptor::hasMultipleUsesOf(
 597     Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
 598     unsigned MaxNumUses) {
 599   unsigned NumUses = 0;
 600   for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
 601        ++Use) {
 602     if (Insts.count(dyn_cast<Instruction>(*Use)))
 603       ++NumUses;
 604     if (NumUses > MaxNumUses)
 605       return true;
 606   }
 607
 608   return false;
 609 }
 610 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
 611                                           RecurrenceDescriptor &RedDes,
 612                                           DemandedBits *DB, AssumptionCache *AC,
 613                                           DominatorTree *DT) {
 614
 615   BasicBlock *Header = TheLoop->getHeader();
 616   Function &F = *Header->getParent();
 617   bool HasFunNoNaNAttr =
 618       F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 619
 620   if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
 621                       AC, DT)) {
 622     LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
 623     return true;
 624   }
 625   if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
 626                       AC, DT)) {
 627     LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
 628     return true;
 629   }
 630   if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
 631                       AC, DT)) {
 632     LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
 633     return true;
 634   }
 635   if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
 636                       AC, DT)) {
 637     LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
 638     return true;
 639   }
 640   if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
 641                       AC, DT)) {
 642     LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
 643     return true;
 644   }
 645   if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
 646                       DB, AC, DT)) {
 647     LLVM_DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
 648     return true;
 649   }
 650   if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
 651                       AC, DT)) {
 652     LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
 653     return true;
 654   }
 655   if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
 656                       AC, DT)) {
 657     LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
 658     return true;
 659   }
 660   if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
 661                       AC, DT)) {
 662     LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
 663                       << "\n");
 664     return true;
 665   }
 666   // Not a reduction of known type.
 667   return false;
 668 }
 669
 670 bool RecurrenceDescriptor::isFirstOrderRecurrence(
 671     PHINode *Phi, Loop *TheLoop,
 672     DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
 673
 674   // Ensure the phi node is in the loop header and has two incoming values.
 675   if (Phi->getParent() != TheLoop->getHeader() ||
 676       Phi->getNumIncomingValues() != 2)
 677     return false;
 678
 679   // Ensure the loop has a preheader and a single latch block. The loop
 680   // vectorizer will need the latch to set up the next iteration of the loop.
 681   auto *Preheader = TheLoop->getLoopPreheader();
 682   auto *Latch = TheLoop->getLoopLatch();
 683   if (!Preheader || !Latch)
 684     return false;
 685
 686   // Ensure the phi node's incoming blocks are the loop preheader and latch.
 687   if (Phi->getBasicBlockIndex(Preheader) < 0 ||
 688       Phi->getBasicBlockIndex(Latch) < 0)
 689     return false;
 690
 691   // Get the previous value. The previous value comes from the latch edge while
 692   // the initial value comes form the preheader edge.
 693   auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
 694   if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
 695       SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
 696     return false;
 697
 698   // Ensure every user of the phi node is dominated by the previous value.
 699   // The dominance requirement ensures the loop vectorizer will not need to
 700   // vectorize the initial value prior to the first iteration of the loop.
 701   // TODO: Consider extending this sinking to handle other kinds of instructions
 702   // and expressions, beyond sinking a single cast past Previous.
 703   if (Phi->hasOneUse()) {
 704     auto *I = Phi->user_back();
 705     if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() &&
 706         DT->dominates(Previous, I->user_back())) {
 707       if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
 708         SinkAfter[I] = Previous;
 709       return true;
 710     }
 711   }
 712
 713   for (User *U : Phi->users())
 714     if (auto *I = dyn_cast<Instruction>(U)) {
 715       if (!DT->dominates(Previous, I))
 716         return false;
 717     }
 718
 719   return true;
 720 }
 721
 722 /// This function returns the identity element (or neutral element) for
 723 /// the operation K.
 724 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
 725                                                       Type *Tp) {
 726   switch (K) {
 727   case RK_IntegerXor:
 728   case RK_IntegerAdd:
 729   case RK_IntegerOr:
 730     // Adding, Xoring, Oring zero to a number does not change it.
 731     return ConstantInt::get(Tp, 0);
 732   case RK_IntegerMult:
 733     // Multiplying a number by 1 does not change it.
 734     return ConstantInt::get(Tp, 1);
 735   case RK_IntegerAnd:
 736     // AND-ing a number with an all-1 value does not change it.
 737     return ConstantInt::get(Tp, -1, true);
 738   case RK_FloatMult:
 739     // Multiplying a number by 1 does not change it.
 740     return ConstantFP::get(Tp, 1.0L);
 741   case RK_FloatAdd:
 742     // Adding zero to a number does not change it.
 743     return ConstantFP::get(Tp, 0.0L);
 744   default:
 745     llvm_unreachable("Unknown recurrence kind");
 746   }
 747 }
 748
 749 /// This function translates the recurrence kind to an LLVM binary operator.
 750 unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
 751   switch (Kind) {
 752   case RK_IntegerAdd:
 753     return Instruction::Add;
 754   case RK_IntegerMult:
 755     return Instruction::Mul;
 756   case RK_IntegerOr:
 757     return Instruction::Or;
 758   case RK_IntegerAnd:
 759     return Instruction::And;
 760   case RK_IntegerXor:
 761     return Instruction::Xor;
 762   case RK_FloatMult:
 763     return Instruction::FMul;
 764   case RK_FloatAdd:
 765     return Instruction::FAdd;
 766   case RK_IntegerMinMax:
 767     return Instruction::ICmp;
 768   case RK_FloatMinMax:
 769     return Instruction::FCmp;
 770   default:
 771     llvm_unreachable("Unknown recurrence operation");
 772   }
 773 }
 774
 775 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
 776                                          const SCEV *Step, BinaryOperator *BOp,
 777                                          SmallVectorImpl<Instruction *> *Casts)
 778     : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
 779   assert(IK != IK_NoInduction && "Not an induction");
 780
 781   // Start value type should match the induction kind and the value
 782   // itself should not be null.
 783   assert(StartValue && "StartValue is null");
 784   assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
 785          "StartValue is not a pointer for pointer induction");
 786   assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
 787          "StartValue is not an integer for integer induction");
 788
 789   // Check the Step Value. It should be non-zero integer value.
 790   assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
 791          "Step value is zero");
 792
 793   assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
 794          "Step value should be constant for pointer induction");
 795   assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
 796          "StepValue is not an integer");
 797
 798   assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
 799          "StepValue is not FP for FpInduction");
 800   assert((IK != IK_FpInduction ||
 801           (InductionBinOp &&
 802            (InductionBinOp->getOpcode() == Instruction::FAdd ||
 803             InductionBinOp->getOpcode() == Instruction::FSub))) &&
 804          "Binary opcode should be specified for FP induction");
 805
 806   if (Casts) {
 807     for (auto &Inst : *Casts) {
 808       RedundantCasts.push_back(Inst);
 809     }
 810   }
 811 }
 812
 813 int InductionDescriptor::getConsecutiveDirection() const {
 814   ConstantInt *ConstStep = getConstIntStepValue();
 815   if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
 816     return ConstStep->getSExtValue();
 817   return 0;
 818 }
 819
 820 ConstantInt *InductionDescriptor::getConstIntStepValue() const {
 821   if (isa<SCEVConstant>(Step))
 822     return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
 823   return nullptr;
 824 }
 825
 826 bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
 827                                            ScalarEvolution *SE,
 828                                            InductionDescriptor &D) {
 829
 830   // Here we only handle FP induction variables.
 831   assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
 832
 833   if (TheLoop->getHeader() != Phi->getParent())
 834     return false;
 835
 836   // The loop may have multiple entrances or multiple exits; we can analyze
 837   // this phi if it has a unique entry value and a unique backedge value.
 838   if (Phi->getNumIncomingValues() != 2)
 839     return false;
 840   Value *BEValue = nullptr, *StartValue = nullptr;
 841   if (TheLoop->contains(Phi->getIncomingBlock(0))) {
 842     BEValue = Phi->getIncomingValue(0);
 843     StartValue = Phi->getIncomingValue(1);
 844   } else {
 845     assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
 846            "Unexpected Phi node in the loop");
 847     BEValue = Phi->getIncomingValue(1);
 848     StartValue = Phi->getIncomingValue(0);
 849   }
 850
 851   BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
 852   if (!BOp)
 853     return false;
 854
 855   Value *Addend = nullptr;
 856   if (BOp->getOpcode() == Instruction::FAdd) {
 857     if (BOp->getOperand(0) == Phi)
 858       Addend = BOp->getOperand(1);
 859     else if (BOp->getOperand(1) == Phi)
 860       Addend = BOp->getOperand(0);
 861   } else if (BOp->getOpcode() == Instruction::FSub)
 862     if (BOp->getOperand(0) == Phi)
 863       Addend = BOp->getOperand(1);
 864
 865   if (!Addend)
 866     return false;
 867
 868   // The addend should be loop invariant
 869   if (auto *I = dyn_cast<Instruction>(Addend))
 870     if (TheLoop->contains(I))
 871       return false;
 872
 873   // FP Step has unknown SCEV
 874   const SCEV *Step = SE->getUnknown(Addend);
 875   D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
 876   return true;
 877 }
 878
 879 /// This function is called when we suspect that the update-chain of a phi node
 880 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
 881 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
 882 /// predicate P under which the SCEV expression for the phi can be the
 883 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
 884 /// cast instructions that are involved in the update-chain of this induction.
 885 /// A caller that adds the required runtime predicate can be free to drop these
 886 /// cast instructions, and compute the phi using \p AR (instead of some scev
 887 /// expression with casts).
 888 ///
 889 /// For example, without a predicate the scev expression can take the following
 890 /// form:
 891 ///      (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
 892 ///
 893 /// It corresponds to the following IR sequence:
 894 /// %for.body:
 895 ///   %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
 896 ///   %casted_phi = "ExtTrunc i64 %x"
 897 ///   %add = add i64 %casted_phi, %step
 898 ///
 899 /// where %x is given in \p PN,
 900 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
 901 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
 902 /// several forms, for example, such as:
 903 ///   ExtTrunc1:    %casted_phi = and  %x, 2^n-1
 904 /// or:
 905 ///   ExtTrunc2:    %t = shl %x, m
 906 ///                 %casted_phi = ashr %t, m
 907 ///
 908 /// If we are able to find such sequence, we return the instructions
 909 /// we found, namely %casted_phi and the instructions on its use-def chain up
 910 /// to the phi (not including the phi).
 911 static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
 912                                     const SCEVUnknown *PhiScev,
 913                                     const SCEVAddRecExpr *AR,
 914                                     SmallVectorImpl<Instruction *> &CastInsts) {
 915
 916   assert(CastInsts.empty() && "CastInsts is expected to be empty.");
 917   auto *PN = cast<PHINode>(PhiScev->getValue());
 918   assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
 919   const Loop *L = AR->getLoop();
 920
 921   // Find any cast instructions that participate in the def-use chain of
 922   // PhiScev in the loop.
 923   // FORNOW/TODO: We currently expect the def-use chain to include only
 924   // two-operand instructions, where one of the operands is an invariant.
 925   // createAddRecFromPHIWithCasts() currently does not support anything more
 926   // involved than that, so we keep the search simple. This can be
 927   // extended/generalized as needed.
 928
 929   auto getDef = [&](const Value *Val) -> Value * {
 930     const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
 931     if (!BinOp)
 932       return nullptr;
 933     Value *Op0 = BinOp->getOperand(0);
 934     Value *Op1 = BinOp->getOperand(1);
 935     Value *Def = nullptr;
 936     if (L->isLoopInvariant(Op0))
 937       Def = Op1;
 938     else if (L->isLoopInvariant(Op1))
 939       Def = Op0;
 940     return Def;
 941   };
 942
 943   // Look for the instruction that defines the induction via the
 944   // loop backedge.
 945   BasicBlock *Latch = L->getLoopLatch();
 946   if (!Latch)
 947     return false;
 948   Value *Val = PN->getIncomingValueForBlock(Latch);
 949   if (!Val)
 950     return false;
 951
 952   // Follow the def-use chain until the induction phi is reached.
 953   // If on the way we encounter a Value that has the same SCEV Expr as the
 954   // phi node, we can consider the instructions we visit from that point
 955   // as part of the cast-sequence that can be ignored.
 956   bool InCastSequence = false;
 957   auto *Inst = dyn_cast<Instruction>(Val);
 958   while (Val != PN) {
 959     // If we encountered a phi node other than PN, or if we left the loop,
 960     // we bail out.
 961     if (!Inst || !L->contains(Inst)) {
 962       return false;
 963     }
 964     auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
 965     if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
 966       InCastSequence = true;
 967     if (InCastSequence) {
 968       // Only the last instruction in the cast sequence is expected to have
 969       // uses outside the induction def-use chain.
 970       if (!CastInsts.empty())
 971         if (!Inst->hasOneUse())
 972           return false;
 973       CastInsts.push_back(Inst);
 974     }
 975     Val = getDef(Val);
 976     if (!Val)
 977       return false;
 978     Inst = dyn_cast<Instruction>(Val);
 979   }
 980
 981   return InCastSequence;
 982 }
 983
 984 bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
 985                                          PredicatedScalarEvolution &PSE,
 986                                          InductionDescriptor &D, bool Assume) {
 987   Type *PhiTy = Phi->getType();
 988
 989   // Handle integer and pointer inductions variables.
 990   // Now we handle also FP induction but not trying to make a
 991   // recurrent expression from the PHI node in-place.
 992
 993   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
 994       !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
 995     return false;
 996
 997   if (PhiTy->isFloatingPointTy())
 998     return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
 999
1000   const SCEV *PhiScev = PSE.getSCEV(Phi);
1001   const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1002
1003   // We need this expression to be an AddRecExpr.
1004   if (Assume && !AR)
1005     AR = PSE.getAsAddRec(Phi);
1006
1007   if (!AR) {
1008     LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1009     return false;
1010   }
1011
1012   // Record any Cast instructions that participate in the induction update
1013   const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1014   // If we started from an UnknownSCEV, and managed to build an addRecurrence
1015   // only after enabling Assume with PSCEV, this means we may have encountered
1016   // cast instructions that required adding a runtime check in order to
1017   // guarantee the correctness of the AddRecurrence respresentation of the
1018   // induction.
1019   if (PhiScev != AR && SymbolicPhi) {
1020     SmallVector<Instruction *, 2> Casts;
1021     if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1022       return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1023   }
1024
1025   return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1026 }
1027
1028 bool InductionDescriptor::isInductionPHI(
1029     PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1030     InductionDescriptor &D, const SCEV *Expr,
1031     SmallVectorImpl<Instruction *> *CastsToIgnore) {
1032   Type *PhiTy = Phi->getType();
1033   // We only handle integer and pointer inductions variables.
1034   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1035     return false;
1036
1037   // Check that the PHI is consecutive.
1038   const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1039   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1040
1041   if (!AR) {
1042     LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1043     return false;
1044   }
1045
1046   if (AR->getLoop() != TheLoop) {
1047     // FIXME: We should treat this as a uniform. Unfortunately, we
1048     // don't currently know how to handled uniform PHIs.
1049     LLVM_DEBUG(
1050         dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1051     return false;
1052   }
1053
1054   Value *StartValue =
1055       Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
1056
1057   BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1058   if (!Latch)
1059     return false;
1060   BinaryOperator *BOp =
1061       dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
1062
1063   const SCEV *Step = AR->getStepRecurrence(*SE);
1064   // Calculate the pointer stride and check if it is consecutive.
1065   // The stride may be a constant or a loop invariant integer value.
1066   const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1067   if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1068     return false;
1069
1070   if (PhiTy->isIntegerTy()) {
1071     D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1072                             CastsToIgnore);
1073     return true;
1074   }
1075
1076   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1077   // Pointer induction should be a constant.
1078   if (!ConstStep)
1079     return false;
1080
1081   ConstantInt *CV = ConstStep->getValue();
1082   Type *PointerElementType = PhiTy->getPointerElementType();
1083   // The pointer stride cannot be determined if the pointer element type is not
1084   // sized.
1085   if (!PointerElementType->isSized())
1086     return false;
1087
1088   const DataLayout &DL = Phi->getModule()->getDataLayout();
1089   int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1090   if (!Size)
1091     return false;
1092
1093   int64_t CVSize = CV->getSExtValue();
1094   if (CVSize % Size)
1095     return false;
1096   auto *StepValue =
1097       SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1098   D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);
1099   return true;
1100 }