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/Transforms/Utils/LoopUtils.h"
  15 #include "llvm/Analysis/AliasAnalysis.h"
  16 #include "llvm/Analysis/BasicAliasAnalysis.h"
  17 #include "llvm/Analysis/GlobalsModRef.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Analysis/LoopPass.h"
  20 #include "llvm/Analysis/ScalarEvolution.h"
  21 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  22 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  23 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  24 #include "llvm/Analysis/TargetTransformInfo.h"
  25 #include "llvm/IR/Dominators.h"
  26 #include "llvm/IR/Instructions.h"
  27 #include "llvm/IR/Module.h"
  28 #include "llvm/IR/PatternMatch.h"
  29 #include "llvm/IR/ValueHandle.h"
  30 #include "llvm/Pass.h"
  31 #include "llvm/Support/Debug.h"
  32
  33 using namespace llvm;
  34 using namespace llvm::PatternMatch;
  35
  36 #define DEBUG_TYPE "loop-utils"
  37
  38 bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
  39                                         SmallPtrSetImpl<Instruction *> &Set) {
  40   for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
  41     if (!Set.count(dyn_cast<Instruction>(*Use)))
  42       return false;
  43   return true;
  44 }
  45
  46 bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
  47   switch (Kind) {
  48   default:
  49     break;
  50   case RK_IntegerAdd:
  51   case RK_IntegerMult:
  52   case RK_IntegerOr:
  53   case RK_IntegerAnd:
  54   case RK_IntegerXor:
  55   case RK_IntegerMinMax:
  56     return true;
  57   }
  58   return false;
  59 }
  60
  61 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
  62   return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
  63 }
  64
  65 bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
  66   switch (Kind) {
  67   default:
  68     break;
  69   case RK_IntegerAdd:
  70   case RK_IntegerMult:
  71   case RK_FloatAdd:
  72   case RK_FloatMult:
  73     return true;
  74   }
  75   return false;
  76 }
  77
  78 Instruction *
  79 RecurrenceDescriptor::lookThroughAnd(PHINode *Phi, Type *&RT,
  80                                      SmallPtrSetImpl<Instruction *> &Visited,
  81                                      SmallPtrSetImpl<Instruction *> &CI) {
  82   if (!Phi->hasOneUse())
  83     return Phi;
  84
  85   const APInt *M = nullptr;
  86   Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
  87
  88   // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
  89   // with a new integer type of the corresponding bit width.
  90   if (match(J, m_CombineOr(m_And(m_Instruction(I), m_APInt(M)),
  91                            m_And(m_APInt(M), m_Instruction(I))))) {
  92     int32_t Bits = (*M + 1).exactLogBase2();
  93     if (Bits > 0) {
  94       RT = IntegerType::get(Phi->getContext(), Bits);
  95       Visited.insert(Phi);
  96       CI.insert(J);
  97       return J;
  98     }
  99   }
 100   return Phi;
 101 }
 102
 103 bool RecurrenceDescriptor::getSourceExtensionKind(
 104     Instruction *Start, Instruction *Exit, Type *RT, bool &IsSigned,
 105     SmallPtrSetImpl<Instruction *> &Visited,
 106     SmallPtrSetImpl<Instruction *> &CI) {
 107
 108   SmallVector<Instruction *, 8> Worklist;
 109   bool FoundOneOperand = false;
 110   unsigned DstSize = RT->getPrimitiveSizeInBits();
 111   Worklist.push_back(Exit);
 112
 113   // Traverse the instructions in the reduction expression, beginning with the
 114   // exit value.
 115   while (!Worklist.empty()) {
 116     Instruction *I = Worklist.pop_back_val();
 117     for (Use &U : I->operands()) {
 118
 119       // Terminate the traversal if the operand is not an instruction, or we
 120       // reach the starting value.
 121       Instruction *J = dyn_cast<Instruction>(U.get());
 122       if (!J || J == Start)
 123         continue;
 124
 125       // Otherwise, investigate the operation if it is also in the expression.
 126       if (Visited.count(J)) {
 127         Worklist.push_back(J);
 128         continue;
 129       }
 130
 131       // If the operand is not in Visited, it is not a reduction operation, but
 132       // it does feed into one. Make sure it is either a single-use sign- or
 133       // zero-extend instruction.
 134       CastInst *Cast = dyn_cast<CastInst>(J);
 135       bool IsSExtInst = isa<SExtInst>(J);
 136       if (!Cast || !Cast->hasOneUse() || !(isa<ZExtInst>(J) || IsSExtInst))
 137         return false;
 138
 139       // Ensure the source type of the extend is no larger than the reduction
 140       // type. It is not necessary for the types to be identical.
 141       unsigned SrcSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
 142       if (SrcSize > DstSize)
 143         return false;
 144
 145       // Furthermore, ensure that all such extends are of the same kind.
 146       if (FoundOneOperand) {
 147         if (IsSigned != IsSExtInst)
 148           return false;
 149       } else {
 150         FoundOneOperand = true;
 151         IsSigned = IsSExtInst;
 152       }
 153
 154       // Lastly, if the source type of the extend matches the reduction type,
 155       // add the extend to CI so that we can avoid accounting for it in the
 156       // cost model.
 157       if (SrcSize == DstSize)
 158         CI.insert(Cast);
 159     }
 160   }
 161   return true;
 162 }
 163
 164 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
 165                                            Loop *TheLoop, bool HasFunNoNaNAttr,
 166                                            RecurrenceDescriptor &RedDes) {
 167   if (Phi->getNumIncomingValues() != 2)
 168     return false;
 169
 170   // Reduction variables are only found in the loop header block.
 171   if (Phi->getParent() != TheLoop->getHeader())
 172     return false;
 173
 174   // Obtain the reduction start value from the value that comes from the loop
 175   // preheader.
 176   Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
 177
 178   // ExitInstruction is the single value which is used outside the loop.
 179   // We only allow for a single reduction value to be used outside the loop.
 180   // This includes users of the reduction, variables (which form a cycle
 181   // which ends in the phi node).
 182   Instruction *ExitInstruction = nullptr;
 183   // Indicates that we found a reduction operation in our scan.
 184   bool FoundReduxOp = false;
 185
 186   // We start with the PHI node and scan for all of the users of this
 187   // instruction. All users must be instructions that can be used as reduction
 188   // variables (such as ADD). We must have a single out-of-block user. The cycle
 189   // must include the original PHI.
 190   bool FoundStartPHI = false;
 191
 192   // To recognize min/max patterns formed by a icmp select sequence, we store
 193   // the number of instruction we saw from the recognized min/max pattern,
 194   //  to make sure we only see exactly the two instructions.
 195   unsigned NumCmpSelectPatternInst = 0;
 196   InstDesc ReduxDesc(false, nullptr);
 197
 198   // Data used for determining if the recurrence has been type-promoted.
 199   Type *RecurrenceType = Phi->getType();
 200   SmallPtrSet<Instruction *, 4> CastInsts;
 201   Instruction *Start = Phi;
 202   bool IsSigned = false;
 203
 204   SmallPtrSet<Instruction *, 8> VisitedInsts;
 205   SmallVector<Instruction *, 8> Worklist;
 206
 207   // Return early if the recurrence kind does not match the type of Phi. If the
 208   // recurrence kind is arithmetic, we attempt to look through AND operations
 209   // resulting from the type promotion performed by InstCombine.  Vector
 210   // operations are not limited to the legal integer widths, so we may be able
 211   // to evaluate the reduction in the narrower width.
 212   if (RecurrenceType->isFloatingPointTy()) {
 213     if (!isFloatingPointRecurrenceKind(Kind))
 214       return false;
 215   } else {
 216     if (!isIntegerRecurrenceKind(Kind))
 217       return false;
 218     if (isArithmeticRecurrenceKind(Kind))
 219       Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
 220   }
 221
 222   Worklist.push_back(Start);
 223   VisitedInsts.insert(Start);
 224
 225   // A value in the reduction can be used:
 226   //  - By the reduction:
 227   //      - Reduction operation:
 228   //        - One use of reduction value (safe).
 229   //        - Multiple use of reduction value (not safe).
 230   //      - PHI:
 231   //        - All uses of the PHI must be the reduction (safe).
 232   //        - Otherwise, not safe.
 233   //  - By instructions outside of the loop (safe).
 234   //      * One value may have several outside users, but all outside
 235   //        uses must be of the same value.
 236   //  - By an instruction that is not part of the reduction (not safe).
 237   //    This is either:
 238   //      * An instruction type other than PHI or the reduction operation.
 239   //      * A PHI in the header other than the initial PHI.
 240   while (!Worklist.empty()) {
 241     Instruction *Cur = Worklist.back();
 242     Worklist.pop_back();
 243
 244     // No Users.
 245     // If the instruction has no users then this is a broken chain and can't be
 246     // a reduction variable.
 247     if (Cur->use_empty())
 248       return false;
 249
 250     bool IsAPhi = isa<PHINode>(Cur);
 251
 252     // A header PHI use other than the original PHI.
 253     if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
 254       return false;
 255
 256     // Reductions of instructions such as Div, and Sub is only possible if the
 257     // LHS is the reduction variable.
 258     if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
 259         !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
 260         !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
 261       return false;
 262
 263     // Any reduction instruction must be of one of the allowed kinds. We ignore
 264     // the starting value (the Phi or an AND instruction if the Phi has been
 265     // type-promoted).
 266     if (Cur != Start) {
 267       ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
 268       if (!ReduxDesc.isRecurrence())
 269         return false;
 270     }
 271
 272     // A reduction operation must only have one use of the reduction value.
 273     if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
 274         hasMultipleUsesOf(Cur, VisitedInsts))
 275       return false;
 276
 277     // All inputs to a PHI node must be a reduction value.
 278     if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
 279       return false;
 280
 281     if (Kind == RK_IntegerMinMax &&
 282         (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
 283       ++NumCmpSelectPatternInst;
 284     if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
 285       ++NumCmpSelectPatternInst;
 286
 287     // Check  whether we found a reduction operator.
 288     FoundReduxOp |= !IsAPhi && Cur != Start;
 289
 290     // Process users of current instruction. Push non-PHI nodes after PHI nodes
 291     // onto the stack. This way we are going to have seen all inputs to PHI
 292     // nodes once we get to them.
 293     SmallVector<Instruction *, 8> NonPHIs;
 294     SmallVector<Instruction *, 8> PHIs;
 295     for (User *U : Cur->users()) {
 296       Instruction *UI = cast<Instruction>(U);
 297
 298       // Check if we found the exit user.
 299       BasicBlock *Parent = UI->getParent();
 300       if (!TheLoop->contains(Parent)) {
 301         // If we already know this instruction is used externally, move on to
 302         // the next user.
 303         if (ExitInstruction == Cur)
 304           continue;
 305
 306         // Exit if you find multiple values used outside or if the header phi
 307         // node is being used. In this case the user uses the value of the
 308         // previous iteration, in which case we would loose "VF-1" iterations of
 309         // the reduction operation if we vectorize.
 310         if (ExitInstruction != nullptr || Cur == Phi)
 311           return false;
 312
 313         // The instruction used by an outside user must be the last instruction
 314         // before we feed back to the reduction phi. Otherwise, we loose VF-1
 315         // operations on the value.
 316         if (!is_contained(Phi->operands(), Cur))
 317           return false;
 318
 319         ExitInstruction = Cur;
 320         continue;
 321       }
 322
 323       // Process instructions only once (termination). Each reduction cycle
 324       // value must only be used once, except by phi nodes and min/max
 325       // reductions which are represented as a cmp followed by a select.
 326       InstDesc IgnoredVal(false, nullptr);
 327       if (VisitedInsts.insert(UI).second) {
 328         if (isa<PHINode>(UI))
 329           PHIs.push_back(UI);
 330         else
 331           NonPHIs.push_back(UI);
 332       } else if (!isa<PHINode>(UI) &&
 333                  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
 334                    !isa<SelectInst>(UI)) ||
 335                   !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
 336         return false;
 337
 338       // Remember that we completed the cycle.
 339       if (UI == Phi)
 340         FoundStartPHI = true;
 341     }
 342     Worklist.append(PHIs.begin(), PHIs.end());
 343     Worklist.append(NonPHIs.begin(), NonPHIs.end());
 344   }
 345
 346   // This means we have seen one but not the other instruction of the
 347   // pattern or more than just a select and cmp.
 348   if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
 349       NumCmpSelectPatternInst != 2)
 350     return false;
 351
 352   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
 353     return false;
 354
 355   // If we think Phi may have been type-promoted, we also need to ensure that
 356   // all source operands of the reduction are either SExtInsts or ZEstInsts. If
 357   // so, we will be able to evaluate the reduction in the narrower bit width.
 358   if (Start != Phi)
 359     if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
 360                                 IsSigned, VisitedInsts, CastInsts))
 361       return false;
 362
 363   // We found a reduction var if we have reached the original phi node and we
 364   // only have a single instruction with out-of-loop users.
 365
 366   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
 367   // is saved as part of the RecurrenceDescriptor.
 368
 369   // Save the description of this reduction variable.
 370   RecurrenceDescriptor RD(
 371       RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
 372       ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
 373   RedDes = RD;
 374
 375   return true;
 376 }
 377
 378 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
 379 /// pattern corresponding to a min(X, Y) or max(X, Y).
 380 RecurrenceDescriptor::InstDesc
 381 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
 382
 383   assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
 384          "Expect a select instruction");
 385   Instruction *Cmp = nullptr;
 386   SelectInst *Select = nullptr;
 387
 388   // We must handle the select(cmp()) as a single instruction. Advance to the
 389   // select.
 390   if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
 391     if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
 392       return InstDesc(false, I);
 393     return InstDesc(Select, Prev.getMinMaxKind());
 394   }
 395
 396   // Only handle single use cases for now.
 397   if (!(Select = dyn_cast<SelectInst>(I)))
 398     return InstDesc(false, I);
 399   if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
 400       !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
 401     return InstDesc(false, I);
 402   if (!Cmp->hasOneUse())
 403     return InstDesc(false, I);
 404
 405   Value *CmpLeft;
 406   Value *CmpRight;
 407
 408   // Look for a min/max pattern.
 409   if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 410     return InstDesc(Select, MRK_UIntMin);
 411   else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 412     return InstDesc(Select, MRK_UIntMax);
 413   else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 414     return InstDesc(Select, MRK_SIntMax);
 415   else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 416     return InstDesc(Select, MRK_SIntMin);
 417   else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 418     return InstDesc(Select, MRK_FloatMin);
 419   else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 420     return InstDesc(Select, MRK_FloatMax);
 421   else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 422     return InstDesc(Select, MRK_FloatMin);
 423   else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
 424     return InstDesc(Select, MRK_FloatMax);
 425
 426   return InstDesc(false, I);
 427 }
 428
 429 RecurrenceDescriptor::InstDesc
 430 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
 431                                         InstDesc &Prev, bool HasFunNoNaNAttr) {
 432   bool FP = I->getType()->isFloatingPointTy();
 433   Instruction *UAI = Prev.getUnsafeAlgebraInst();
 434   if (!UAI && FP && !I->hasUnsafeAlgebra())
 435     UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
 436
 437   switch (I->getOpcode()) {
 438   default:
 439     return InstDesc(false, I);
 440   case Instruction::PHI:
 441     return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
 442   case Instruction::Sub:
 443   case Instruction::Add:
 444     return InstDesc(Kind == RK_IntegerAdd, I);
 445   case Instruction::Mul:
 446     return InstDesc(Kind == RK_IntegerMult, I);
 447   case Instruction::And:
 448     return InstDesc(Kind == RK_IntegerAnd, I);
 449   case Instruction::Or:
 450     return InstDesc(Kind == RK_IntegerOr, I);
 451   case Instruction::Xor:
 452     return InstDesc(Kind == RK_IntegerXor, I);
 453   case Instruction::FMul:
 454     return InstDesc(Kind == RK_FloatMult, I, UAI);
 455   case Instruction::FSub:
 456   case Instruction::FAdd:
 457     return InstDesc(Kind == RK_FloatAdd, I, UAI);
 458   case Instruction::FCmp:
 459   case Instruction::ICmp:
 460   case Instruction::Select:
 461     if (Kind != RK_IntegerMinMax &&
 462         (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
 463       return InstDesc(false, I);
 464     return isMinMaxSelectCmpPattern(I, Prev);
 465   }
 466 }
 467
 468 bool RecurrenceDescriptor::hasMultipleUsesOf(
 469     Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
 470   unsigned NumUses = 0;
 471   for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
 472        ++Use) {
 473     if (Insts.count(dyn_cast<Instruction>(*Use)))
 474       ++NumUses;
 475     if (NumUses > 1)
 476       return true;
 477   }
 478
 479   return false;
 480 }
 481 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
 482                                           RecurrenceDescriptor &RedDes) {
 483
 484   BasicBlock *Header = TheLoop->getHeader();
 485   Function &F = *Header->getParent();
 486   bool HasFunNoNaNAttr =
 487       F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 488
 489   if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 490     DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
 491     return true;
 492   }
 493   if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
 494     DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
 495     return true;
 496   }
 497   if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
 498     DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
 499     return true;
 500   }
 501   if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 502     DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
 503     return true;
 504   }
 505   if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
 506     DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
 507     return true;
 508   }
 509   if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
 510                       RedDes)) {
 511     DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
 512     return true;
 513   }
 514   if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
 515     DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
 516     return true;
 517   }
 518   if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
 519     DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
 520     return true;
 521   }
 522   if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
 523     DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
 524     return true;
 525   }
 526   // Not a reduction of known type.
 527   return false;
 528 }
 529
 530 bool RecurrenceDescriptor::isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
 531                                                   DominatorTree *DT) {
 532
 533   // Ensure the phi node is in the loop header and has two incoming values.
 534   if (Phi->getParent() != TheLoop->getHeader() ||
 535       Phi->getNumIncomingValues() != 2)
 536     return false;
 537
 538   // Ensure the loop has a preheader and a single latch block. The loop
 539   // vectorizer will need the latch to set up the next iteration of the loop.
 540   auto *Preheader = TheLoop->getLoopPreheader();
 541   auto *Latch = TheLoop->getLoopLatch();
 542   if (!Preheader || !Latch)
 543     return false;
 544
 545   // Ensure the phi node's incoming blocks are the loop preheader and latch.
 546   if (Phi->getBasicBlockIndex(Preheader) < 0 ||
 547       Phi->getBasicBlockIndex(Latch) < 0)
 548     return false;
 549
 550   // Get the previous value. The previous value comes from the latch edge while
 551   // the initial value comes form the preheader edge.
 552   auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
 553   if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous))
 554     return false;
 555
 556   // Ensure every user of the phi node is dominated by the previous value.
 557   // The dominance requirement ensures the loop vectorizer will not need to
 558   // vectorize the initial value prior to the first iteration of the loop.
 559   for (User *U : Phi->users())
 560     if (auto *I = dyn_cast<Instruction>(U)) {
 561       if (!DT->dominates(Previous, I))
 562         return false;
 563     }
 564
 565   return true;
 566 }
 567
 568 /// This function returns the identity element (or neutral element) for
 569 /// the operation K.
 570 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
 571                                                       Type *Tp) {
 572   switch (K) {
 573   case RK_IntegerXor:
 574   case RK_IntegerAdd:
 575   case RK_IntegerOr:
 576     // Adding, Xoring, Oring zero to a number does not change it.
 577     return ConstantInt::get(Tp, 0);
 578   case RK_IntegerMult:
 579     // Multiplying a number by 1 does not change it.
 580     return ConstantInt::get(Tp, 1);
 581   case RK_IntegerAnd:
 582     // AND-ing a number with an all-1 value does not change it.
 583     return ConstantInt::get(Tp, -1, true);
 584   case RK_FloatMult:
 585     // Multiplying a number by 1 does not change it.
 586     return ConstantFP::get(Tp, 1.0L);
 587   case RK_FloatAdd:
 588     // Adding zero to a number does not change it.
 589     return ConstantFP::get(Tp, 0.0L);
 590   default:
 591     llvm_unreachable("Unknown recurrence kind");
 592   }
 593 }
 594
 595 /// This function translates the recurrence kind to an LLVM binary operator.
 596 unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
 597   switch (Kind) {
 598   case RK_IntegerAdd:
 599     return Instruction::Add;
 600   case RK_IntegerMult:
 601     return Instruction::Mul;
 602   case RK_IntegerOr:
 603     return Instruction::Or;
 604   case RK_IntegerAnd:
 605     return Instruction::And;
 606   case RK_IntegerXor:
 607     return Instruction::Xor;
 608   case RK_FloatMult:
 609     return Instruction::FMul;
 610   case RK_FloatAdd:
 611     return Instruction::FAdd;
 612   case RK_IntegerMinMax:
 613     return Instruction::ICmp;
 614   case RK_FloatMinMax:
 615     return Instruction::FCmp;
 616   default:
 617     llvm_unreachable("Unknown recurrence operation");
 618   }
 619 }
 620
 621 Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
 622                                             MinMaxRecurrenceKind RK,
 623                                             Value *Left, Value *Right) {
 624   CmpInst::Predicate P = CmpInst::ICMP_NE;
 625   switch (RK) {
 626   default:
 627     llvm_unreachable("Unknown min/max recurrence kind");
 628   case MRK_UIntMin:
 629     P = CmpInst::ICMP_ULT;
 630     break;
 631   case MRK_UIntMax:
 632     P = CmpInst::ICMP_UGT;
 633     break;
 634   case MRK_SIntMin:
 635     P = CmpInst::ICMP_SLT;
 636     break;
 637   case MRK_SIntMax:
 638     P = CmpInst::ICMP_SGT;
 639     break;
 640   case MRK_FloatMin:
 641     P = CmpInst::FCMP_OLT;
 642     break;
 643   case MRK_FloatMax:
 644     P = CmpInst::FCMP_OGT;
 645     break;
 646   }
 647
 648   // We only match FP sequences with unsafe algebra, so we can unconditionally
 649   // set it on any generated instructions.
 650   IRBuilder<>::FastMathFlagGuard FMFG(Builder);
 651   FastMathFlags FMF;
 652   FMF.setUnsafeAlgebra();
 653   Builder.setFastMathFlags(FMF);
 654
 655   Value *Cmp;
 656   if (RK == MRK_FloatMin || RK == MRK_FloatMax)
 657     Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
 658   else
 659     Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
 660
 661   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
 662   return Select;
 663 }
 664
 665 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
 666                                          const SCEV *Step, BinaryOperator *BOp)
 667   : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
 668   assert(IK != IK_NoInduction && "Not an induction");
 669
 670   // Start value type should match the induction kind and the value
 671   // itself should not be null.
 672   assert(StartValue && "StartValue is null");
 673   assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
 674          "StartValue is not a pointer for pointer induction");
 675   assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
 676          "StartValue is not an integer for integer induction");
 677
 678   // Check the Step Value. It should be non-zero integer value.
 679   assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
 680          "Step value is zero");
 681
 682   assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
 683          "Step value should be constant for pointer induction");
 684   assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
 685          "StepValue is not an integer");
 686
 687   assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
 688          "StepValue is not FP for FpInduction");
 689   assert((IK != IK_FpInduction || (InductionBinOp &&
 690           (InductionBinOp->getOpcode() == Instruction::FAdd ||
 691            InductionBinOp->getOpcode() == Instruction::FSub))) &&
 692          "Binary opcode should be specified for FP induction");
 693 }
 694
 695 int InductionDescriptor::getConsecutiveDirection() const {
 696   ConstantInt *ConstStep = getConstIntStepValue();
 697   if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
 698     return ConstStep->getSExtValue();
 699   return 0;
 700 }
 701
 702 ConstantInt *InductionDescriptor::getConstIntStepValue() const {
 703   if (isa<SCEVConstant>(Step))
 704     return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
 705   return nullptr;
 706 }
 707
 708 Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index,
 709                                       ScalarEvolution *SE,
 710                                       const DataLayout& DL) const {
 711
 712   SCEVExpander Exp(*SE, DL, "induction");
 713   assert(Index->getType() == Step->getType() &&
 714          "Index type does not match StepValue type");
 715   switch (IK) {
 716   case IK_IntInduction: {
 717     assert(Index->getType() == StartValue->getType() &&
 718            "Index type does not match StartValue type");
 719
 720     // FIXME: Theoretically, we can call getAddExpr() of ScalarEvolution
 721     // and calculate (Start + Index * Step) for all cases, without
 722     // special handling for "isOne" and "isMinusOne".
 723     // But in the real life the result code getting worse. We mix SCEV
 724     // expressions and ADD/SUB operations and receive redundant
 725     // intermediate values being calculated in different ways and
 726     // Instcombine is unable to reduce them all.
 727
 728     if (getConstIntStepValue() &&
 729         getConstIntStepValue()->isMinusOne())
 730       return B.CreateSub(StartValue, Index);
 731     if (getConstIntStepValue() &&
 732         getConstIntStepValue()->isOne())
 733       return B.CreateAdd(StartValue, Index);
 734     const SCEV *S = SE->getAddExpr(SE->getSCEV(StartValue),
 735                                    SE->getMulExpr(Step, SE->getSCEV(Index)));
 736     return Exp.expandCodeFor(S, StartValue->getType(), &*B.GetInsertPoint());
 737   }
 738   case IK_PtrInduction: {
 739     assert(isa<SCEVConstant>(Step) &&
 740            "Expected constant step for pointer induction");
 741     const SCEV *S = SE->getMulExpr(SE->getSCEV(Index), Step);
 742     Index = Exp.expandCodeFor(S, Index->getType(), &*B.GetInsertPoint());
 743     return B.CreateGEP(nullptr, StartValue, Index);
 744   }
 745   case IK_FpInduction: {
 746     assert(Step->getType()->isFloatingPointTy() && "Expected FP Step value");
 747     assert(InductionBinOp &&
 748            (InductionBinOp->getOpcode() == Instruction::FAdd ||
 749             InductionBinOp->getOpcode() == Instruction::FSub) &&
 750            "Original bin op should be defined for FP induction");
 751
 752     Value *StepValue = cast<SCEVUnknown>(Step)->getValue();
 753
 754     // Floating point operations had to be 'fast' to enable the induction.
 755     FastMathFlags Flags;
 756     Flags.setUnsafeAlgebra();
 757
 758     Value *MulExp = B.CreateFMul(StepValue, Index);
 759     if (isa<Instruction>(MulExp))
 760       // We have to check, the MulExp may be a constant.
 761       cast<Instruction>(MulExp)->setFastMathFlags(Flags);
 762
 763     Value *BOp = B.CreateBinOp(InductionBinOp->getOpcode() , StartValue,
 764                                MulExp, "induction");
 765     if (isa<Instruction>(BOp))
 766       cast<Instruction>(BOp)->setFastMathFlags(Flags);
 767
 768     return BOp;
 769   }
 770   case IK_NoInduction:
 771     return nullptr;
 772   }
 773   llvm_unreachable("invalid enum");
 774 }
 775
 776 bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
 777                                            ScalarEvolution *SE,
 778                                            InductionDescriptor &D) {
 779
 780   // Here we only handle FP induction variables.
 781   assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
 782
 783   if (TheLoop->getHeader() != Phi->getParent())
 784     return false;
 785
 786   // The loop may have multiple entrances or multiple exits; we can analyze
 787   // this phi if it has a unique entry value and a unique backedge value.
 788   if (Phi->getNumIncomingValues() != 2)
 789     return false;
 790   Value *BEValue = nullptr, *StartValue = nullptr;
 791   if (TheLoop->contains(Phi->getIncomingBlock(0))) {
 792     BEValue = Phi->getIncomingValue(0);
 793     StartValue = Phi->getIncomingValue(1);
 794   } else {
 795     assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
 796            "Unexpected Phi node in the loop");
 797     BEValue = Phi->getIncomingValue(1);
 798     StartValue = Phi->getIncomingValue(0);
 799   }
 800
 801   BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
 802   if (!BOp)
 803     return false;
 804
 805   Value *Addend = nullptr;
 806   if (BOp->getOpcode() == Instruction::FAdd) {
 807     if (BOp->getOperand(0) == Phi)
 808       Addend = BOp->getOperand(1);
 809     else if (BOp->getOperand(1) == Phi)
 810       Addend = BOp->getOperand(0);
 811   } else if (BOp->getOpcode() == Instruction::FSub)
 812     if (BOp->getOperand(0) == Phi)
 813       Addend = BOp->getOperand(1);
 814
 815   if (!Addend)
 816     return false;
 817
 818   // The addend should be loop invariant
 819   if (auto *I = dyn_cast<Instruction>(Addend))
 820     if (TheLoop->contains(I))
 821       return false;
 822
 823   // FP Step has unknown SCEV
 824   const SCEV *Step = SE->getUnknown(Addend);
 825   D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
 826   return true;
 827 }
 828
 829 bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
 830                                          PredicatedScalarEvolution &PSE,
 831                                          InductionDescriptor &D,
 832                                          bool Assume) {
 833   Type *PhiTy = Phi->getType();
 834
 835   // Handle integer and pointer inductions variables.
 836   // Now we handle also FP induction but not trying to make a
 837   // recurrent expression from the PHI node in-place.
 838
 839   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() &&
 840       !PhiTy->isFloatTy() && !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
 841     return false;
 842
 843   if (PhiTy->isFloatingPointTy())
 844     return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
 845
 846   const SCEV *PhiScev = PSE.getSCEV(Phi);
 847   const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
 848
 849   // We need this expression to be an AddRecExpr.
 850   if (Assume && !AR)
 851     AR = PSE.getAsAddRec(Phi);
 852
 853   if (!AR) {
 854     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
 855     return false;
 856   }
 857
 858   return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
 859 }
 860
 861 bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
 862                                          ScalarEvolution *SE,
 863                                          InductionDescriptor &D,
 864                                          const SCEV *Expr) {
 865   Type *PhiTy = Phi->getType();
 866   // We only handle integer and pointer inductions variables.
 867   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
 868     return false;
 869
 870   // Check that the PHI is consecutive.
 871   const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
 872   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
 873
 874   if (!AR) {
 875     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
 876     return false;
 877   }
 878
 879   if (AR->getLoop() != TheLoop) {
 880     // FIXME: We should treat this as a uniform. Unfortunately, we
 881     // don't currently know how to handled uniform PHIs.
 882     DEBUG(dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
 883     return false;
 884   }
 885
 886   Value *StartValue =
 887     Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
 888   const SCEV *Step = AR->getStepRecurrence(*SE);
 889   // Calculate the pointer stride and check if it is consecutive.
 890   // The stride may be a constant or a loop invariant integer value.
 891   const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
 892   if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
 893     return false;
 894
 895   if (PhiTy->isIntegerTy()) {
 896     D = InductionDescriptor(StartValue, IK_IntInduction, Step);
 897     return true;
 898   }
 899
 900   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
 901   // Pointer induction should be a constant.
 902   if (!ConstStep)
 903     return false;
 904
 905   ConstantInt *CV = ConstStep->getValue();
 906   Type *PointerElementType = PhiTy->getPointerElementType();
 907   // The pointer stride cannot be determined if the pointer element type is not
 908   // sized.
 909   if (!PointerElementType->isSized())
 910     return false;
 911
 912   const DataLayout &DL = Phi->getModule()->getDataLayout();
 913   int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
 914   if (!Size)
 915     return false;
 916
 917   int64_t CVSize = CV->getSExtValue();
 918   if (CVSize % Size)
 919     return false;
 920   auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size,
 921                                     true /* signed */);
 922   D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
 923   return true;
 924 }
 925
 926 /// \brief Returns the instructions that use values defined in the loop.
 927 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
 928   SmallVector<Instruction *, 8> UsedOutside;
 929
 930   for (auto *Block : L->getBlocks())
 931     // FIXME: I believe that this could use copy_if if the Inst reference could
 932     // be adapted into a pointer.
 933     for (auto &Inst : *Block) {
 934       auto Users = Inst.users();
 935       if (any_of(Users, [&](User *U) {
 936             auto *Use = cast<Instruction>(U);
 937             return !L->contains(Use->getParent());
 938           }))
 939         UsedOutside.push_back(&Inst);
 940     }
 941
 942   return UsedOutside;
 943 }
 944
 945 void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
 946   // By definition, all loop passes need the LoopInfo analysis and the
 947   // Dominator tree it depends on. Because they all participate in the loop
 948   // pass manager, they must also preserve these.
 949   AU.addRequired<DominatorTreeWrapperPass>();
 950   AU.addPreserved<DominatorTreeWrapperPass>();
 951   AU.addRequired<LoopInfoWrapperPass>();
 952   AU.addPreserved<LoopInfoWrapperPass>();
 953
 954   // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
 955   // here because users shouldn't directly get them from this header.
 956   extern char &LoopSimplifyID;
 957   extern char &LCSSAID;
 958   AU.addRequiredID(LoopSimplifyID);
 959   AU.addPreservedID(LoopSimplifyID);
 960   AU.addRequiredID(LCSSAID);
 961   AU.addPreservedID(LCSSAID);
 962   // This is used in the LPPassManager to perform LCSSA verification on passes
 963   // which preserve lcssa form
 964   AU.addRequired<LCSSAVerificationPass>();
 965   AU.addPreserved<LCSSAVerificationPass>();
 966
 967   // Loop passes are designed to run inside of a loop pass manager which means
 968   // that any function analyses they require must be required by the first loop
 969   // pass in the manager (so that it is computed before the loop pass manager
 970   // runs) and preserved by all loop pasess in the manager. To make this
 971   // reasonably robust, the set needed for most loop passes is maintained here.
 972   // If your loop pass requires an analysis not listed here, you will need to
 973   // carefully audit the loop pass manager nesting structure that results.
 974   AU.addRequired<AAResultsWrapperPass>();
 975   AU.addPreserved<AAResultsWrapperPass>();
 976   AU.addPreserved<BasicAAWrapperPass>();
 977   AU.addPreserved<GlobalsAAWrapperPass>();
 978   AU.addPreserved<SCEVAAWrapperPass>();
 979   AU.addRequired<ScalarEvolutionWrapperPass>();
 980   AU.addPreserved<ScalarEvolutionWrapperPass>();
 981 }
 982
 983 /// Manually defined generic "LoopPass" dependency initialization. This is used
 984 /// to initialize the exact set of passes from above in \c
 985 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
 986 /// with:
 987 ///
 988 ///   INITIALIZE_PASS_DEPENDENCY(LoopPass)
 989 ///
 990 /// As-if "LoopPass" were a pass.
 991 void llvm::initializeLoopPassPass(PassRegistry &Registry) {
 992   INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 993   INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 994   INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 995   INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 996   INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 997   INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
 998   INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 999   INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
1000   INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1001 }
1002
1003 /// \brief Find string metadata for loop
1004 ///
1005 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1006 /// operand or null otherwise.  If the string metadata is not found return
1007 /// Optional's not-a-value.
1008 Optional<const MDOperand *> llvm::findStringMetadataForLoop(Loop *TheLoop,
1009                                                             StringRef Name) {
1010   MDNode *LoopID = TheLoop->getLoopID();
1011   // Return none if LoopID is false.
1012   if (!LoopID)
1013     return None;
1014
1015   // First operand should refer to the loop id itself.
1016   assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1017   assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1018
1019   // Iterate over LoopID operands and look for MDString Metadata
1020   for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1021     MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1022     if (!MD)
1023       continue;
1024     MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1025     if (!S)
1026       continue;
1027     // Return true if MDString holds expected MetaData.
1028     if (Name.equals(S->getString()))
1029       switch (MD->getNumOperands()) {
1030       case 1:
1031         return nullptr;
1032       case 2:
1033         return &MD->getOperand(1);
1034       default:
1035         llvm_unreachable("loop metadata has 0 or 1 operand");
1036       }
1037   }
1038   return None;
1039 }
1040
1041 /// Returns true if the instruction in a loop is guaranteed to execute at least
1042 /// once.
1043 bool llvm::isGuaranteedToExecute(const Instruction &Inst,
1044                                  const DominatorTree *DT, const Loop *CurLoop,
1045                                  const LoopSafetyInfo *SafetyInfo) {
1046   // We have to check to make sure that the instruction dominates all
1047   // of the exit blocks.  If it doesn't, then there is a path out of the loop
1048   // which does not execute this instruction, so we can't hoist it.
1049
1050   // If the instruction is in the header block for the loop (which is very
1051   // common), it is always guaranteed to dominate the exit blocks.  Since this
1052   // is a common case, and can save some work, check it now.
1053   if (Inst.getParent() == CurLoop->getHeader())
1054     // If there's a throw in the header block, we can't guarantee we'll reach
1055     // Inst.
1056     return !SafetyInfo->HeaderMayThrow;
1057
1058   // Somewhere in this loop there is an instruction which may throw and make us
1059   // exit the loop.
1060   if (SafetyInfo->MayThrow)
1061     return false;
1062
1063   // Get the exit blocks for the current loop.
1064   SmallVector<BasicBlock *, 8> ExitBlocks;
1065   CurLoop->getExitBlocks(ExitBlocks);
1066
1067   // Verify that the block dominates each of the exit blocks of the loop.
1068   for (BasicBlock *ExitBlock : ExitBlocks)
1069     if (!DT->dominates(Inst.getParent(), ExitBlock))
1070       return false;
1071
1072   // As a degenerate case, if the loop is statically infinite then we haven't
1073   // proven anything since there are no exit blocks.
1074   if (ExitBlocks.empty())
1075     return false;
1076
1077   // FIXME: In general, we have to prove that the loop isn't an infinite loop.
1078   // See http::llvm.org/PR24078 .  (The "ExitBlocks.empty()" check above is
1079   // just a special case of this.)
1080   return true;
1081 }
1082
1083 Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
1084   // Only support loops with a unique exiting block, and a latch.
1085   if (!L->getExitingBlock())
1086     return None;
1087
1088   // Get the branch weights for the the loop's backedge.
1089   BranchInst *LatchBR =
1090       dyn_cast<BranchInst>(L->getLoopLatch()->getTerminator());
1091   if (!LatchBR || LatchBR->getNumSuccessors() != 2)
1092     return None;
1093
1094   assert((LatchBR->getSuccessor(0) == L->getHeader() ||
1095           LatchBR->getSuccessor(1) == L->getHeader()) &&
1096          "At least one edge out of the latch must go to the header");
1097
1098   // To estimate the number of times the loop body was executed, we want to
1099   // know the number of times the backedge was taken, vs. the number of times
1100   // we exited the loop.
1101   uint64_t TrueVal, FalseVal;
1102   if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
1103     return None;
1104
1105   if (!TrueVal || !FalseVal)
1106     return 0;
1107
1108   // Divide the count of the backedge by the count of the edge exiting the loop,
1109   // rounding to nearest.
1110   if (LatchBR->getSuccessor(0) == L->getHeader())
1111     return (TrueVal + (FalseVal / 2)) / FalseVal;
1112   else
1113     return (FalseVal + (TrueVal / 2)) / TrueVal;
1114 }
1115
1116 /// \brief Adds a 'fast' flag to floating point operations.
1117 static Value *addFastMathFlag(Value *V) {
1118   if (isa<FPMathOperator>(V)) {
1119     FastMathFlags Flags;
1120     Flags.setUnsafeAlgebra();
1121     cast<Instruction>(V)->setFastMathFlags(Flags);
1122   }
1123   return V;
1124 }
1125
1126 // Helper to generate a log2 shuffle reduction.
1127 Value *
1128 llvm::getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
1129                           RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
1130                           ArrayRef<Value *> RedOps) {
1131   unsigned VF = Src->getType()->getVectorNumElements();
1132   // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
1133   // and vector ops, reducing the set of values being computed by half each
1134   // round.
1135   assert(isPowerOf2_32(VF) &&
1136          "Reduction emission only supported for pow2 vectors!");
1137   Value *TmpVec = Src;
1138   SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
1139   for (unsigned i = VF; i != 1; i >>= 1) {
1140     // Move the upper half of the vector to the lower half.
1141     for (unsigned j = 0; j != i / 2; ++j)
1142       ShuffleMask[j] = Builder.getInt32(i / 2 + j);
1143
1144     // Fill the rest of the mask with undef.
1145     std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
1146               UndefValue::get(Builder.getInt32Ty()));
1147
1148     Value *Shuf = Builder.CreateShuffleVector(
1149         TmpVec, UndefValue::get(TmpVec->getType()),
1150         ConstantVector::get(ShuffleMask), "rdx.shuf");
1151
1152     if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1153       // Floating point operations had to be 'fast' to enable the reduction.
1154       TmpVec = addFastMathFlag(Builder.CreateBinOp((Instruction::BinaryOps)Op,
1155                                                    TmpVec, Shuf, "bin.rdx"));
1156     } else {
1157       assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
1158              "Invalid min/max");
1159       TmpVec = RecurrenceDescriptor::createMinMaxOp(Builder, MinMaxKind, TmpVec,
1160                                                     Shuf);
1161     }
1162     if (!RedOps.empty())
1163       propagateIRFlags(TmpVec, RedOps);
1164   }
1165   // The result is in the first element of the vector.
1166   return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1167 }
1168
1169 /// Create a simple vector reduction specified by an opcode and some
1170 /// flags (if generating min/max reductions).
1171 Value *llvm::createSimpleTargetReduction(
1172     IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
1173     Value *Src, TargetTransformInfo::ReductionFlags Flags,
1174     ArrayRef<Value *> RedOps) {
1175   assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
1176
1177   Value *ScalarUdf = UndefValue::get(Src->getType()->getVectorElementType());
1178   std::function<Value*()> BuildFunc;
1179   using RD = RecurrenceDescriptor;
1180   RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
1181   // TODO: Support creating ordered reductions.
1182   FastMathFlags FMFUnsafe;
1183   FMFUnsafe.setUnsafeAlgebra();
1184
1185   switch (Opcode) {
1186   case Instruction::Add:
1187     BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
1188     break;
1189   case Instruction::Mul:
1190     BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
1191     break;
1192   case Instruction::And:
1193     BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
1194     break;
1195   case Instruction::Or:
1196     BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
1197     break;
1198   case Instruction::Xor:
1199     BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
1200     break;
1201   case Instruction::FAdd:
1202     BuildFunc = [&]() {
1203       auto Rdx = Builder.CreateFAddReduce(ScalarUdf, Src);
1204       cast<CallInst>(Rdx)->setFastMathFlags(FMFUnsafe);
1205       return Rdx;
1206     };
1207     break;
1208   case Instruction::FMul:
1209     BuildFunc = [&]() {
1210       auto Rdx = Builder.CreateFMulReduce(ScalarUdf, Src);
1211       cast<CallInst>(Rdx)->setFastMathFlags(FMFUnsafe);
1212       return Rdx;
1213     };
1214     break;
1215   case Instruction::ICmp:
1216     if (Flags.IsMaxOp) {
1217       MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
1218       BuildFunc = [&]() {
1219         return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
1220       };
1221     } else {
1222       MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
1223       BuildFunc = [&]() {
1224         return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
1225       };
1226     }
1227     break;
1228   case Instruction::FCmp:
1229     if (Flags.IsMaxOp) {
1230       MinMaxKind = RD::MRK_FloatMax;
1231       BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
1232     } else {
1233       MinMaxKind = RD::MRK_FloatMin;
1234       BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
1235     }
1236     break;
1237   default:
1238     llvm_unreachable("Unhandled opcode");
1239     break;
1240   }
1241   if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
1242     return BuildFunc();
1243   return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
1244 }
1245
1246 /// Create a vector reduction using a given recurrence descriptor.
1247 Value *llvm::createTargetReduction(IRBuilder<> &Builder,
1248                                    const TargetTransformInfo *TTI,
1249                                    RecurrenceDescriptor &Desc, Value *Src,
1250                                    bool NoNaN) {
1251   // TODO: Support in-order reductions based on the recurrence descriptor.
1252   RecurrenceDescriptor::RecurrenceKind RecKind = Desc.getRecurrenceKind();
1253   TargetTransformInfo::ReductionFlags Flags;
1254   Flags.NoNaN = NoNaN;
1255   auto getSimpleRdx = [&](unsigned Opc) {
1256     return createSimpleTargetReduction(Builder, TTI, Opc, Src, Flags);
1257   };
1258   switch (RecKind) {
1259   case RecurrenceDescriptor::RK_FloatAdd:
1260     return getSimpleRdx(Instruction::FAdd);
1261   case RecurrenceDescriptor::RK_FloatMult:
1262     return getSimpleRdx(Instruction::FMul);
1263   case RecurrenceDescriptor::RK_IntegerAdd:
1264     return getSimpleRdx(Instruction::Add);
1265   case RecurrenceDescriptor::RK_IntegerMult:
1266     return getSimpleRdx(Instruction::Mul);
1267   case RecurrenceDescriptor::RK_IntegerAnd:
1268     return getSimpleRdx(Instruction::And);
1269   case RecurrenceDescriptor::RK_IntegerOr:
1270     return getSimpleRdx(Instruction::Or);
1271   case RecurrenceDescriptor::RK_IntegerXor:
1272     return getSimpleRdx(Instruction::Xor);
1273   case RecurrenceDescriptor::RK_IntegerMinMax: {
1274     switch (Desc.getMinMaxRecurrenceKind()) {
1275     case RecurrenceDescriptor::MRK_SIntMax:
1276       Flags.IsSigned = true;
1277       Flags.IsMaxOp = true;
1278       break;
1279     case RecurrenceDescriptor::MRK_UIntMax:
1280       Flags.IsMaxOp = true;
1281       break;
1282     case RecurrenceDescriptor::MRK_SIntMin:
1283       Flags.IsSigned = true;
1284       break;
1285     case RecurrenceDescriptor::MRK_UIntMin:
1286       break;
1287     default:
1288       llvm_unreachable("Unhandled MRK");
1289     }
1290     return getSimpleRdx(Instruction::ICmp);
1291   }
1292   case RecurrenceDescriptor::RK_FloatMinMax: {
1293     Flags.IsMaxOp =
1294         Desc.getMinMaxRecurrenceKind() == RecurrenceDescriptor::MRK_FloatMax;
1295     return getSimpleRdx(Instruction::FCmp);
1296   }
1297   default:
1298     llvm_unreachable("Unhandled RecKind");
1299   }
1300 }
1301
1302 void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL) {
1303   if (auto *VecOp = dyn_cast<Instruction>(I)) {
1304     if (auto *I0 = dyn_cast<Instruction>(VL[0])) {
1305       // VecOVp is initialized to the 0th scalar, so start counting from index
1306       // '1'.
1307       VecOp->copyIRFlags(I0);
1308       for (int i = 1, e = VL.size(); i < e; ++i) {
1309         if (auto *Scalar = dyn_cast<Instruction>(VL[i]))
1310           VecOp->andIRFlags(Scalar);
1311       }
1312     }
1313   }
1314 }