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::isIntegerRecurrenceKind(RecurrenceKind Kind) {
  38   switch (Kind) {
  39   default:
  40     break;
  41   case RK_IntegerAdd:
  42   case RK_IntegerMult:
  43   case RK_IntegerOr:
  44   case RK_IntegerAnd:
  45   case RK_IntegerXor:
  46   case RK_IntegerMinMax:
  47     return true;
  48   }
  49   return false;
  50 }
  51
  52 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
  53   return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
  54 }
  55
  56 bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
  57   switch (Kind) {
  58   default:
  59     break;
  60   case RK_IntegerAdd:
  61   case RK_IntegerMult:
  62   case RK_FloatAdd:
  63   case RK_FloatMult:
  64     return true;
  65   }
  66   return false;
  67 }
  68
  69 Instruction *
  70 RecurrenceDescriptor::lookThroughAnd(PHINode *Phi, Type *&RT,
  71                                      SmallPtrSetImpl<Instruction *> &Visited,
  72                                      SmallPtrSetImpl<Instruction *> &CI) {
  73   if (!Phi->hasOneUse())
  74     return Phi;
  75
  76   const APInt *M = nullptr;
  77   Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
  78
  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();
  84     if (Bits > 0) {
  85       RT = IntegerType::get(Phi->getContext(), Bits);
  86       Visited.insert(Phi);
  87       CI.insert(J);
  88       return J;
  89     }
  90   }
  91   return Phi;
  92 }
  93
  94 bool RecurrenceDescriptor::getSourceExtensionKind(
  95     Instruction *Start, Instruction *Exit, Type *RT, bool &IsSigned,
  96     SmallPtrSetImpl<Instruction *> &Visited,
  97     SmallPtrSetImpl<Instruction *> &CI) {
  98
  99   SmallVector<Instruction *, 8> Worklist;
 100   bool FoundOneOperand = false;
 101   unsigned DstSize = RT->getPrimitiveSizeInBits();
 102   Worklist.push_back(Exit);
 103
 104   // Traverse the instructions in the reduction expression, beginning with the
 105   // exit value.
 106   while (!Worklist.empty()) {
 107     Instruction *I = Worklist.pop_back_val();
 108     for (Use &U : I->operands()) {
 109
 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)
 114         continue;
 115
 116       // Otherwise, investigate the operation if it is also in the expression.
 117       if (Visited.count(J)) {
 118         Worklist.push_back(J);
 119         continue;
 120       }
 121
 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))
 128         return false;
 129
 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)
 134         return false;
 135
 136       // Furthermore, ensure that all such extends are of the same kind.
 137       if (FoundOneOperand) {
 138         if (IsSigned != IsSExtInst)
 139           return false;
 140       } else {
 141         FoundOneOperand = true;
 142         IsSigned = IsSExtInst;
 143       }
 144
 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
 147       // cost model.
 148       if (SrcSize == DstSize)
 149         CI.insert(Cast);
 150     }
 151   }
 152   return true;
 153 }
 154
 155 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
 156                                            Loop *TheLoop, bool HasFunNoNaNAttr,
 157                                            RecurrenceDescriptor &RedDes) {
 158   if (Phi->getNumIncomingValues() != 2)
 159     return false;
 160
 161   // Reduction variables are only found in the loop header block.
 162   if (Phi->getParent() != TheLoop->getHeader())
 163     return false;
 164
 165   // Obtain the reduction start value from the value that comes from the loop
 166   // preheader.
 167   Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
 168
 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;
 176
 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;
 182
 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);
 188
 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;
 194
 195   SmallPtrSet<Instruction *, 8> VisitedInsts;
 196   SmallVector<Instruction *, 8> Worklist;
 197
 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))
 205       return false;
 206   } else {
 207     if (!isIntegerRecurrenceKind(Kind))
 208       return false;
 209     if (isArithmeticRecurrenceKind(Kind))
 210       Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
 211   }
 212
 213   Worklist.push_back(Start);
 214   VisitedInsts.insert(Start);
 215
 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).
 221   //      - PHI:
 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).
 227   //    This is either:
 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();
 232     Worklist.pop_back();
 233
 234     // No Users.
 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())
 238       return false;
 239
 240     bool IsAPhi = isa<PHINode>(Cur);
 241
 242     // A header PHI use other than the original PHI.
 243     if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
 244       return false;
 245
 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))))
 251       return false;
 252
 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
 255     // type-promoted).
 256     if (Cur != Start) {
 257       ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
 258       if (!ReduxDesc.isRecurrence())
 259         return false;
 260     }
 261
 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))
 265       return false;
 266
 267     // All inputs to a PHI node must be a reduction value.
 268     if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
 269       return false;
 270
 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;
 276
 277     // Check  whether we found a reduction operator.
 278     FoundReduxOp |= !IsAPhi && Cur != Start;
 279
 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);
 287
 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)
 296           return false;
 297
 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())
 302           return false;
 303
 304         ExitInstruction = Cur;
 305         continue;
 306       }
 307
 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))
 314           PHIs.push_back(UI);
 315         else
 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()))
 321         return false;
 322
 323       // Remember that we completed the cycle.
 324       if (UI == Phi)
 325         FoundStartPHI = true;
 326     }
 327     Worklist.append(PHIs.begin(), PHIs.end());
 328     Worklist.append(NonPHIs.begin(), NonPHIs.end());
 329   }
 330
 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)
 335     return false;
 336
 337   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
 338     return false;
 339
 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.
 343   if (Start != Phi)
 344     if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
 345                                 IsSigned, VisitedInsts, CastInsts))
 346       return false;
 347
 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.
 350
 351   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
 352   // is saved as part of the RecurrenceDescriptor.
 353
 354   // Save the description of this reduction variable.
 355   RecurrenceDescriptor RD(
 356       RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
 357       ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
 358   RedDes = RD;
 359
 360   return true;
 361 }
 362
 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) {
 367
 368   assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
 369          "Expect a select instruction");
 370   Instruction *Cmp = nullptr;
 371   SelectInst *Select = nullptr;
 372
 373   // We must handle the select(cmp()) as a single instruction. Advance to the
 374   // select.
 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());
 379   }
 380
 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);
 389
 390   Value *CmpLeft;
 391   Value *CmpRight;
 392
 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);
 410
 411   return InstDesc(false, I);
 412 }
 413
 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.
 421
 422   switch (I->getOpcode()) {
 423   default:
 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);
 450   }
 451 }
 452
 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;
 457        ++Use) {
 458     if (Insts.count(dyn_cast<Instruction>(*Use)))
 459       ++NumUses;
 460     if (NumUses > 1)
 461       return true;
 462   }
 463
 464   return false;
 465 }
 466 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
 467                                           RecurrenceDescriptor &RedDes) {
 468
 469   bool HasFunNoNaNAttr = false;
 470   BasicBlock *Header = TheLoop->getHeader();
 471   Function &F = *Header->getParent();
 472   if (F.hasFnAttribute("no-nans-fp-math"))
 473     HasFunNoNaNAttr =
 474         F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 475
 476   if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 477     DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
 478     return true;
 479   }
 480   if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
 481     DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
 482     return true;
 483   }
 484   if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
 485     DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
 486     return true;
 487   }
 488   if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 489     DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
 490     return true;
 491   }
 492   if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
 493     DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
 494     return true;
 495   }
 496   if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
 497                       RedDes)) {
 498     DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
 499     return true;
 500   }
 501   if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
 502     DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
 503     return true;
 504   }
 505   if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 506     DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
 507     return true;
 508   }
 509   if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
 510     DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
 511     return true;
 512   }
 513   // Not a reduction of known type.
 514   return false;
 515 }
 516
 517 /// This function returns the identity element (or neutral element) for
 518 /// the operation K.
 519 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
 520                                                       Type *Tp) {
 521   switch (K) {
 522   case RK_IntegerXor:
 523   case RK_IntegerAdd:
 524   case RK_IntegerOr:
 525     // Adding, Xoring, Oring zero to a number does not change it.
 526     return ConstantInt::get(Tp, 0);
 527   case RK_IntegerMult:
 528     // Multiplying a number by 1 does not change it.
 529     return ConstantInt::get(Tp, 1);
 530   case RK_IntegerAnd:
 531     // AND-ing a number with an all-1 value does not change it.
 532     return ConstantInt::get(Tp, -1, true);
 533   case RK_FloatMult:
 534     // Multiplying a number by 1 does not change it.
 535     return ConstantFP::get(Tp, 1.0L);
 536   case RK_FloatAdd:
 537     // Adding zero to a number does not change it.
 538     return ConstantFP::get(Tp, 0.0L);
 539   default:
 540     llvm_unreachable("Unknown recurrence kind");
 541   }
 542 }
 543
 544 /// This function translates the recurrence kind to an LLVM binary operator.
 545 unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
 546   switch (Kind) {
 547   case RK_IntegerAdd:
 548     return Instruction::Add;
 549   case RK_IntegerMult:
 550     return Instruction::Mul;
 551   case RK_IntegerOr:
 552     return Instruction::Or;
 553   case RK_IntegerAnd:
 554     return Instruction::And;
 555   case RK_IntegerXor:
 556     return Instruction::Xor;
 557   case RK_FloatMult:
 558     return Instruction::FMul;
 559   case RK_FloatAdd:
 560     return Instruction::FAdd;
 561   case RK_IntegerMinMax:
 562     return Instruction::ICmp;
 563   case RK_FloatMinMax:
 564     return Instruction::FCmp;
 565   default:
 566     llvm_unreachable("Unknown recurrence operation");
 567   }
 568 }
 569
 570 Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
 571                                             MinMaxRecurrenceKind RK,
 572                                             Value *Left, Value *Right) {
 573   CmpInst::Predicate P = CmpInst::ICMP_NE;
 574   switch (RK) {
 575   default:
 576     llvm_unreachable("Unknown min/max recurrence kind");
 577   case MRK_UIntMin:
 578     P = CmpInst::ICMP_ULT;
 579     break;
 580   case MRK_UIntMax:
 581     P = CmpInst::ICMP_UGT;
 582     break;
 583   case MRK_SIntMin:
 584     P = CmpInst::ICMP_SLT;
 585     break;
 586   case MRK_SIntMax:
 587     P = CmpInst::ICMP_SGT;
 588     break;
 589   case MRK_FloatMin:
 590     P = CmpInst::FCMP_OLT;
 591     break;
 592   case MRK_FloatMax:
 593     P = CmpInst::FCMP_OGT;
 594     break;
 595   }
 596
 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);
 600   FastMathFlags FMF;
 601   FMF.setUnsafeAlgebra();
 602   Builder.SetFastMathFlags(FMF);
 603
 604   Value *Cmp;
 605   if (RK == MRK_FloatMin || RK == MRK_FloatMax)
 606     Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
 607   else
 608     Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
 609
 610   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
 611   return Select;
 612 }
 613
 614 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
 615                                          ConstantInt *Step)
 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");
 626 }
 627
 628 int InductionDescriptor::getConsecutiveDirection() const {
 629   if (StepValue && (StepValue->isOne() || StepValue->isMinusOne()))
 630     return StepValue->getSExtValue();
 631   return 0;
 632 }
 633
 634 Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index) const {
 635   switch (IK) {
 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);
 644
 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);
 653
 654   case IK_NoInduction:
 655     return nullptr;
 656   }
 657   llvm_unreachable("invalid enum");
 658 }
 659
 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())
 665     return false;
 666
 667   // Check that the PHI is consecutive.
 668   const SCEV *PhiScev = SE->getSCEV(Phi);
 669   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
 670   if (!AR) {
 671     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
 672     return false;
 673   }
 674
 675   assert(AR->getLoop()->getHeader() == Phi->getParent() &&
 676          "PHI is an AddRec for a different loop?!");
 677   Value *StartValue =
 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);
 682   if (!C)
 683     return false;
 684
 685   ConstantInt *CV = C->getValue();
 686   if (PhiTy->isIntegerTy()) {
 687     D = InductionDescriptor(StartValue, IK_IntInduction, CV);
 688     return true;
 689   }
 690
 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
 694   // sized.
 695   if (!PointerElementType->isSized())
 696     return false;
 697
 698   const DataLayout &DL = Phi->getModule()->getDataLayout();
 699   int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
 700   if (!Size)
 701     return false;
 702
 703   int64_t CVSize = CV->getSExtValue();
 704   if (CVSize % Size)
 705     return false;
 706   auto *StepValue = ConstantInt::getSigned(CV->getType(), CVSize / Size);
 707
 708   D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
 709   return true;
 710 }
 711
 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;
 715
 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());
 724           }))
 725         UsedOutside.push_back(&Inst);
 726     }
 727
 728   return UsedOutside;
 729 }