contrib/llvm-project/llvm/lib/Transforms/Utils/LoopUtils.cpp

   1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
   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 defines common loop utility functions.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Transforms/Utils/LoopUtils.h"
  14 #include "llvm/ADT/DenseSet.h"
  15 #include "llvm/ADT/Optional.h"
  16 #include "llvm/ADT/PriorityWorklist.h"
  17 #include "llvm/ADT/ScopeExit.h"
  18 #include "llvm/ADT/SetVector.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/Analysis/AliasAnalysis.h"
  22 #include "llvm/Analysis/BasicAliasAnalysis.h"
  23 #include "llvm/Analysis/DomTreeUpdater.h"
  24 #include "llvm/Analysis/GlobalsModRef.h"
  25 #include "llvm/Analysis/InstructionSimplify.h"
  26 #include "llvm/Analysis/LoopAccessAnalysis.h"
  27 #include "llvm/Analysis/LoopInfo.h"
  28 #include "llvm/Analysis/LoopPass.h"
  29 #include "llvm/Analysis/MemorySSA.h"
  30 #include "llvm/Analysis/MemorySSAUpdater.h"
  31 #include "llvm/Analysis/MustExecute.h"
  32 #include "llvm/Analysis/ScalarEvolution.h"
  33 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  34 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  35 #include "llvm/Analysis/TargetTransformInfo.h"
  36 #include "llvm/Analysis/ValueTracking.h"
  37 #include "llvm/IR/DIBuilder.h"
  38 #include "llvm/IR/Dominators.h"
  39 #include "llvm/IR/Instructions.h"
  40 #include "llvm/IR/IntrinsicInst.h"
  41 #include "llvm/IR/MDBuilder.h"
  42 #include "llvm/IR/Module.h"
  43 #include "llvm/IR/Operator.h"
  44 #include "llvm/IR/PatternMatch.h"
  45 #include "llvm/IR/ValueHandle.h"
  46 #include "llvm/InitializePasses.h"
  47 #include "llvm/Pass.h"
  48 #include "llvm/Support/Debug.h"
  49 #include "llvm/Support/KnownBits.h"
  50 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  51 #include "llvm/Transforms/Utils/Local.h"
  52 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
  53
  54 using namespace llvm;
  55 using namespace llvm::PatternMatch;
  56
  57 static cl::opt<bool> ForceReductionIntrinsic(
  58     "force-reduction-intrinsics", cl::Hidden,
  59     cl::desc("Force creating reduction intrinsics for testing."),
  60     cl::init(false));
  61
  62 #define DEBUG_TYPE "loop-utils"
  63
  64 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
  65 static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
  66
  67 bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
  68                                    MemorySSAUpdater *MSSAU,
  69                                    bool PreserveLCSSA) {
  70   bool Changed = false;
  71
  72   // We re-use a vector for the in-loop predecesosrs.
  73   SmallVector<BasicBlock *, 4> InLoopPredecessors;
  74
  75   auto RewriteExit = [&](BasicBlock *BB) {
  76     assert(InLoopPredecessors.empty() &&
  77            "Must start with an empty predecessors list!");
  78     auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
  79
  80     // See if there are any non-loop predecessors of this exit block and
  81     // keep track of the in-loop predecessors.
  82     bool IsDedicatedExit = true;
  83     for (auto *PredBB : predecessors(BB))
  84       if (L->contains(PredBB)) {
  85         if (isa<IndirectBrInst>(PredBB->getTerminator()))
  86           // We cannot rewrite exiting edges from an indirectbr.
  87           return false;
  88         if (isa<CallBrInst>(PredBB->getTerminator()))
  89           // We cannot rewrite exiting edges from a callbr.
  90           return false;
  91
  92         InLoopPredecessors.push_back(PredBB);
  93       } else {
  94         IsDedicatedExit = false;
  95       }
  96
  97     assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
  98
  99     // Nothing to do if this is already a dedicated exit.
 100     if (IsDedicatedExit)
 101       return false;
 102
 103     auto *NewExitBB = SplitBlockPredecessors(
 104         BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
 105
 106     if (!NewExitBB)
 107       LLVM_DEBUG(
 108           dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
 109                  << *L << "\n");
 110     else
 111       LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
 112                         << NewExitBB->getName() << "\n");
 113     return true;
 114   };
 115
 116   // Walk the exit blocks directly rather than building up a data structure for
 117   // them, but only visit each one once.
 118   SmallPtrSet<BasicBlock *, 4> Visited;
 119   for (auto *BB : L->blocks())
 120     for (auto *SuccBB : successors(BB)) {
 121       // We're looking for exit blocks so skip in-loop successors.
 122       if (L->contains(SuccBB))
 123         continue;
 124
 125       // Visit each exit block exactly once.
 126       if (!Visited.insert(SuccBB).second)
 127         continue;
 128
 129       Changed |= RewriteExit(SuccBB);
 130     }
 131
 132   return Changed;
 133 }
 134
 135 /// Returns the instructions that use values defined in the loop.
 136 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
 137   SmallVector<Instruction *, 8> UsedOutside;
 138
 139   for (auto *Block : L->getBlocks())
 140     // FIXME: I believe that this could use copy_if if the Inst reference could
 141     // be adapted into a pointer.
 142     for (auto &Inst : *Block) {
 143       auto Users = Inst.users();
 144       if (any_of(Users, [&](User *U) {
 145             auto *Use = cast<Instruction>(U);
 146             return !L->contains(Use->getParent());
 147           }))
 148         UsedOutside.push_back(&Inst);
 149     }
 150
 151   return UsedOutside;
 152 }
 153
 154 void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
 155   // By definition, all loop passes need the LoopInfo analysis and the
 156   // Dominator tree it depends on. Because they all participate in the loop
 157   // pass manager, they must also preserve these.
 158   AU.addRequired<DominatorTreeWrapperPass>();
 159   AU.addPreserved<DominatorTreeWrapperPass>();
 160   AU.addRequired<LoopInfoWrapperPass>();
 161   AU.addPreserved<LoopInfoWrapperPass>();
 162
 163   // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
 164   // here because users shouldn't directly get them from this header.
 165   extern char &LoopSimplifyID;
 166   extern char &LCSSAID;
 167   AU.addRequiredID(LoopSimplifyID);
 168   AU.addPreservedID(LoopSimplifyID);
 169   AU.addRequiredID(LCSSAID);
 170   AU.addPreservedID(LCSSAID);
 171   // This is used in the LPPassManager to perform LCSSA verification on passes
 172   // which preserve lcssa form
 173   AU.addRequired<LCSSAVerificationPass>();
 174   AU.addPreserved<LCSSAVerificationPass>();
 175
 176   // Loop passes are designed to run inside of a loop pass manager which means
 177   // that any function analyses they require must be required by the first loop
 178   // pass in the manager (so that it is computed before the loop pass manager
 179   // runs) and preserved by all loop pasess in the manager. To make this
 180   // reasonably robust, the set needed for most loop passes is maintained here.
 181   // If your loop pass requires an analysis not listed here, you will need to
 182   // carefully audit the loop pass manager nesting structure that results.
 183   AU.addRequired<AAResultsWrapperPass>();
 184   AU.addPreserved<AAResultsWrapperPass>();
 185   AU.addPreserved<BasicAAWrapperPass>();
 186   AU.addPreserved<GlobalsAAWrapperPass>();
 187   AU.addPreserved<SCEVAAWrapperPass>();
 188   AU.addRequired<ScalarEvolutionWrapperPass>();
 189   AU.addPreserved<ScalarEvolutionWrapperPass>();
 190   // FIXME: When all loop passes preserve MemorySSA, it can be required and
 191   // preserved here instead of the individual handling in each pass.
 192 }
 193
 194 /// Manually defined generic "LoopPass" dependency initialization. This is used
 195 /// to initialize the exact set of passes from above in \c
 196 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
 197 /// with:
 198 ///
 199 ///   INITIALIZE_PASS_DEPENDENCY(LoopPass)
 200 ///
 201 /// As-if "LoopPass" were a pass.
 202 void llvm::initializeLoopPassPass(PassRegistry &Registry) {
 203   INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 204   INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 205   INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 206   INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 207   INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 208   INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
 209   INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 210   INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 211   INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 212   INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 213 }
 214
 215 /// Create MDNode for input string.
 216 static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
 217   LLVMContext &Context = TheLoop->getHeader()->getContext();
 218   Metadata *MDs[] = {
 219       MDString::get(Context, Name),
 220       ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))};
 221   return MDNode::get(Context, MDs);
 222 }
 223
 224 /// Set input string into loop metadata by keeping other values intact.
 225 /// If the string is already in loop metadata update value if it is
 226 /// different.
 227 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD,
 228                                    unsigned V) {
 229   SmallVector<Metadata *, 4> MDs(1);
 230   // If the loop already has metadata, retain it.
 231   MDNode *LoopID = TheLoop->getLoopID();
 232   if (LoopID) {
 233     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
 234       MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
 235       // If it is of form key = value, try to parse it.
 236       if (Node->getNumOperands() == 2) {
 237         MDString *S = dyn_cast<MDString>(Node->getOperand(0));
 238         if (S && S->getString().equals(StringMD)) {
 239           ConstantInt *IntMD =
 240               mdconst::extract_or_null<ConstantInt>(Node->getOperand(1));
 241           if (IntMD && IntMD->getSExtValue() == V)
 242             // It is already in place. Do nothing.
 243             return;
 244           // We need to update the value, so just skip it here and it will
 245           // be added after copying other existed nodes.
 246           continue;
 247         }
 248       }
 249       MDs.push_back(Node);
 250     }
 251   }
 252   // Add new metadata.
 253   MDs.push_back(createStringMetadata(TheLoop, StringMD, V));
 254   // Replace current metadata node with new one.
 255   LLVMContext &Context = TheLoop->getHeader()->getContext();
 256   MDNode *NewLoopID = MDNode::get(Context, MDs);
 257   // Set operand 0 to refer to the loop id itself.
 258   NewLoopID->replaceOperandWith(0, NewLoopID);
 259   TheLoop->setLoopID(NewLoopID);
 260 }
 261
 262 /// Find string metadata for loop
 263 ///
 264 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
 265 /// operand or null otherwise.  If the string metadata is not found return
 266 /// Optional's not-a-value.
 267 Optional<const MDOperand *> llvm::findStringMetadataForLoop(const Loop *TheLoop,
 268                                                             StringRef Name) {
 269   MDNode *MD = findOptionMDForLoop(TheLoop, Name);
 270   if (!MD)
 271     return None;
 272   switch (MD->getNumOperands()) {
 273   case 1:
 274     return nullptr;
 275   case 2:
 276     return &MD->getOperand(1);
 277   default:
 278     llvm_unreachable("loop metadata has 0 or 1 operand");
 279   }
 280 }
 281
 282 static Optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop,
 283                                                    StringRef Name) {
 284   MDNode *MD = findOptionMDForLoop(TheLoop, Name);
 285   if (!MD)
 286     return None;
 287   switch (MD->getNumOperands()) {
 288   case 1:
 289     // When the value is absent it is interpreted as 'attribute set'.
 290     return true;
 291   case 2:
 292     if (ConstantInt *IntMD =
 293             mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
 294       return IntMD->getZExtValue();
 295     return true;
 296   }
 297   llvm_unreachable("unexpected number of options");
 298 }
 299
 300 static bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
 301   return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
 302 }
 303
 304 llvm::Optional<int> llvm::getOptionalIntLoopAttribute(Loop *TheLoop,
 305                                                       StringRef Name) {
 306   const MDOperand *AttrMD =
 307       findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
 308   if (!AttrMD)
 309     return None;
 310
 311   ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
 312   if (!IntMD)
 313     return None;
 314
 315   return IntMD->getSExtValue();
 316 }
 317
 318 Optional<MDNode *> llvm::makeFollowupLoopID(
 319     MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
 320     const char *InheritOptionsExceptPrefix, bool AlwaysNew) {
 321   if (!OrigLoopID) {
 322     if (AlwaysNew)
 323       return nullptr;
 324     return None;
 325   }
 326
 327   assert(OrigLoopID->getOperand(0) == OrigLoopID);
 328
 329   bool InheritAllAttrs = !InheritOptionsExceptPrefix;
 330   bool InheritSomeAttrs =
 331       InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0';
 332   SmallVector<Metadata *, 8> MDs;
 333   MDs.push_back(nullptr);
 334
 335   bool Changed = false;
 336   if (InheritAllAttrs || InheritSomeAttrs) {
 337     for (const MDOperand &Existing : drop_begin(OrigLoopID->operands(), 1)) {
 338       MDNode *Op = cast<MDNode>(Existing.get());
 339
 340       auto InheritThisAttribute = [InheritSomeAttrs,
 341                                    InheritOptionsExceptPrefix](MDNode *Op) {
 342         if (!InheritSomeAttrs)
 343           return false;
 344
 345         // Skip malformatted attribute metadata nodes.
 346         if (Op->getNumOperands() == 0)
 347           return true;
 348         Metadata *NameMD = Op->getOperand(0).get();
 349         if (!isa<MDString>(NameMD))
 350           return true;
 351         StringRef AttrName = cast<MDString>(NameMD)->getString();
 352
 353         // Do not inherit excluded attributes.
 354         return !AttrName.startswith(InheritOptionsExceptPrefix);
 355       };
 356
 357       if (InheritThisAttribute(Op))
 358         MDs.push_back(Op);
 359       else
 360         Changed = true;
 361     }
 362   } else {
 363     // Modified if we dropped at least one attribute.
 364     Changed = OrigLoopID->getNumOperands() > 1;
 365   }
 366
 367   bool HasAnyFollowup = false;
 368   for (StringRef OptionName : FollowupOptions) {
 369     MDNode *FollowupNode = findOptionMDForLoopID(OrigLoopID, OptionName);
 370     if (!FollowupNode)
 371       continue;
 372
 373     HasAnyFollowup = true;
 374     for (const MDOperand &Option : drop_begin(FollowupNode->operands(), 1)) {
 375       MDs.push_back(Option.get());
 376       Changed = true;
 377     }
 378   }
 379
 380   // Attributes of the followup loop not specified explicity, so signal to the
 381   // transformation pass to add suitable attributes.
 382   if (!AlwaysNew && !HasAnyFollowup)
 383     return None;
 384
 385   // If no attributes were added or remove, the previous loop Id can be reused.
 386   if (!AlwaysNew && !Changed)
 387     return OrigLoopID;
 388
 389   // No attributes is equivalent to having no !llvm.loop metadata at all.
 390   if (MDs.size() == 1)
 391     return nullptr;
 392
 393   // Build the new loop ID.
 394   MDTuple *FollowupLoopID = MDNode::get(OrigLoopID->getContext(), MDs);
 395   FollowupLoopID->replaceOperandWith(0, FollowupLoopID);
 396   return FollowupLoopID;
 397 }
 398
 399 bool llvm::hasDisableAllTransformsHint(const Loop *L) {
 400   return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced);
 401 }
 402
 403 bool llvm::hasDisableLICMTransformsHint(const Loop *L) {
 404   return getBooleanLoopAttribute(L, LLVMLoopDisableLICM);
 405 }
 406
 407 TransformationMode llvm::hasUnrollTransformation(Loop *L) {
 408   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
 409     return TM_SuppressedByUser;
 410
 411   Optional<int> Count =
 412       getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
 413   if (Count.hasValue())
 414     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
 415
 416   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable"))
 417     return TM_ForcedByUser;
 418
 419   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.full"))
 420     return TM_ForcedByUser;
 421
 422   if (hasDisableAllTransformsHint(L))
 423     return TM_Disable;
 424
 425   return TM_Unspecified;
 426 }
 427
 428 TransformationMode llvm::hasUnrollAndJamTransformation(Loop *L) {
 429   if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.disable"))
 430     return TM_SuppressedByUser;
 431
 432   Optional<int> Count =
 433       getOptionalIntLoopAttribute(L, "llvm.loop.unroll_and_jam.count");
 434   if (Count.hasValue())
 435     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
 436
 437   if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.enable"))
 438     return TM_ForcedByUser;
 439
 440   if (hasDisableAllTransformsHint(L))
 441     return TM_Disable;
 442
 443   return TM_Unspecified;
 444 }
 445
 446 TransformationMode llvm::hasVectorizeTransformation(Loop *L) {
 447   Optional<bool> Enable =
 448       getOptionalBoolLoopAttribute(L, "llvm.loop.vectorize.enable");
 449
 450   if (Enable == false)
 451     return TM_SuppressedByUser;
 452
 453   Optional<int> VectorizeWidth =
 454       getOptionalIntLoopAttribute(L, "llvm.loop.vectorize.width");
 455   Optional<int> InterleaveCount =
 456       getOptionalIntLoopAttribute(L, "llvm.loop.interleave.count");
 457
 458   // 'Forcing' vector width and interleave count to one effectively disables
 459   // this tranformation.
 460   if (Enable == true && VectorizeWidth == 1 && InterleaveCount == 1)
 461     return TM_SuppressedByUser;
 462
 463   if (getBooleanLoopAttribute(L, "llvm.loop.isvectorized"))
 464     return TM_Disable;
 465
 466   if (Enable == true)
 467     return TM_ForcedByUser;
 468
 469   if (VectorizeWidth == 1 && InterleaveCount == 1)
 470     return TM_Disable;
 471
 472   if (VectorizeWidth > 1 || InterleaveCount > 1)
 473     return TM_Enable;
 474
 475   if (hasDisableAllTransformsHint(L))
 476     return TM_Disable;
 477
 478   return TM_Unspecified;
 479 }
 480
 481 TransformationMode llvm::hasDistributeTransformation(Loop *L) {
 482   if (getBooleanLoopAttribute(L, "llvm.loop.distribute.enable"))
 483     return TM_ForcedByUser;
 484
 485   if (hasDisableAllTransformsHint(L))
 486     return TM_Disable;
 487
 488   return TM_Unspecified;
 489 }
 490
 491 TransformationMode llvm::hasLICMVersioningTransformation(Loop *L) {
 492   if (getBooleanLoopAttribute(L, "llvm.loop.licm_versioning.disable"))
 493     return TM_SuppressedByUser;
 494
 495   if (hasDisableAllTransformsHint(L))
 496     return TM_Disable;
 497
 498   return TM_Unspecified;
 499 }
 500
 501 /// Does a BFS from a given node to all of its children inside a given loop.
 502 /// The returned vector of nodes includes the starting point.
 503 SmallVector<DomTreeNode *, 16>
 504 llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
 505   SmallVector<DomTreeNode *, 16> Worklist;
 506   auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
 507     // Only include subregions in the top level loop.
 508     BasicBlock *BB = DTN->getBlock();
 509     if (CurLoop->contains(BB))
 510       Worklist.push_back(DTN);
 511   };
 512
 513   AddRegionToWorklist(N);
 514
 515   for (size_t I = 0; I < Worklist.size(); I++) {
 516     for (DomTreeNode *Child : Worklist[I]->children())
 517       AddRegionToWorklist(Child);
 518   }
 519
 520   return Worklist;
 521 }
 522
 523 void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
 524                           LoopInfo *LI, MemorySSA *MSSA) {
 525   assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
 526   auto *Preheader = L->getLoopPreheader();
 527   assert(Preheader && "Preheader should exist!");
 528
 529   std::unique_ptr<MemorySSAUpdater> MSSAU;
 530   if (MSSA)
 531     MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
 532
 533   // Now that we know the removal is safe, remove the loop by changing the
 534   // branch from the preheader to go to the single exit block.
 535   //
 536   // Because we're deleting a large chunk of code at once, the sequence in which
 537   // we remove things is very important to avoid invalidation issues.
 538
 539   // Tell ScalarEvolution that the loop is deleted. Do this before
 540   // deleting the loop so that ScalarEvolution can look at the loop
 541   // to determine what it needs to clean up.
 542   if (SE)
 543     SE->forgetLoop(L);
 544
 545   auto *ExitBlock = L->getUniqueExitBlock();
 546   assert(ExitBlock && "Should have a unique exit block!");
 547   assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
 548
 549   auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
 550   assert(OldBr && "Preheader must end with a branch");
 551   assert(OldBr->isUnconditional() && "Preheader must have a single successor");
 552   // Connect the preheader to the exit block. Keep the old edge to the header
 553   // around to perform the dominator tree update in two separate steps
 554   // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
 555   // preheader -> header.
 556   //
 557   //
 558   // 0.  Preheader          1.  Preheader           2.  Preheader
 559   //        |                    |   |                   |
 560   //        V                    |   V                   |
 561   //      Header <--\            | Header <--\           | Header <--\
 562   //       |  |     |            |  |  |     |           |  |  |     |
 563   //       |  V     |            |  |  V     |           |  |  V     |
 564   //       | Body --/            |  | Body --/           |  | Body --/
 565   //       V                     V  V                    V  V
 566   //      Exit                   Exit                    Exit
 567   //
 568   // By doing this is two separate steps we can perform the dominator tree
 569   // update without using the batch update API.
 570   //
 571   // Even when the loop is never executed, we cannot remove the edge from the
 572   // source block to the exit block. Consider the case where the unexecuted loop
 573   // branches back to an outer loop. If we deleted the loop and removed the edge
 574   // coming to this inner loop, this will break the outer loop structure (by
 575   // deleting the backedge of the outer loop). If the outer loop is indeed a
 576   // non-loop, it will be deleted in a future iteration of loop deletion pass.
 577   IRBuilder<> Builder(OldBr);
 578   Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
 579   // Remove the old branch. The conditional branch becomes a new terminator.
 580   OldBr->eraseFromParent();
 581
 582   // Rewrite phis in the exit block to get their inputs from the Preheader
 583   // instead of the exiting block.
 584   for (PHINode &P : ExitBlock->phis()) {
 585     // Set the zero'th element of Phi to be from the preheader and remove all
 586     // other incoming values. Given the loop has dedicated exits, all other
 587     // incoming values must be from the exiting blocks.
 588     int PredIndex = 0;
 589     P.setIncomingBlock(PredIndex, Preheader);
 590     // Removes all incoming values from all other exiting blocks (including
 591     // duplicate values from an exiting block).
 592     // Nuke all entries except the zero'th entry which is the preheader entry.
 593     // NOTE! We need to remove Incoming Values in the reverse order as done
 594     // below, to keep the indices valid for deletion (removeIncomingValues
 595     // updates getNumIncomingValues and shifts all values down into the operand
 596     // being deleted).
 597     for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
 598       P.removeIncomingValue(e - i, false);
 599
 600     assert((P.getNumIncomingValues() == 1 &&
 601             P.getIncomingBlock(PredIndex) == Preheader) &&
 602            "Should have exactly one value and that's from the preheader!");
 603   }
 604
 605   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 606   if (DT) {
 607     DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
 608     if (MSSA) {
 609       MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}, *DT);
 610       if (VerifyMemorySSA)
 611         MSSA->verifyMemorySSA();
 612     }
 613   }
 614
 615   // Disconnect the loop body by branching directly to its exit.
 616   Builder.SetInsertPoint(Preheader->getTerminator());
 617   Builder.CreateBr(ExitBlock);
 618   // Remove the old branch.
 619   Preheader->getTerminator()->eraseFromParent();
 620
 621   if (DT) {
 622     DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}});
 623     if (MSSA) {
 624       MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}},
 625                           *DT);
 626       SmallSetVector<BasicBlock *, 8> DeadBlockSet(L->block_begin(),
 627                                                    L->block_end());
 628       MSSAU->removeBlocks(DeadBlockSet);
 629       if (VerifyMemorySSA)
 630         MSSA->verifyMemorySSA();
 631     }
 632   }
 633
 634   // Use a map to unique and a vector to guarantee deterministic ordering.
 635   llvm::SmallDenseSet<std::pair<DIVariable *, DIExpression *>, 4> DeadDebugSet;
 636   llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
 637
 638   // Given LCSSA form is satisfied, we should not have users of instructions
 639   // within the dead loop outside of the loop. However, LCSSA doesn't take
 640   // unreachable uses into account. We handle them here.
 641   // We could do it after drop all references (in this case all users in the
 642   // loop will be already eliminated and we have less work to do but according
 643   // to API doc of User::dropAllReferences only valid operation after dropping
 644   // references, is deletion. So let's substitute all usages of
 645   // instruction from the loop with undef value of corresponding type first.
 646   for (auto *Block : L->blocks())
 647     for (Instruction &I : *Block) {
 648       auto *Undef = UndefValue::get(I.getType());
 649       for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
 650         Use &U = *UI;
 651         ++UI;
 652         if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
 653           if (L->contains(Usr->getParent()))
 654             continue;
 655         // If we have a DT then we can check that uses outside a loop only in
 656         // unreachable block.
 657         if (DT)
 658           assert(!DT->isReachableFromEntry(U) &&
 659                  "Unexpected user in reachable block");
 660         U.set(Undef);
 661       }
 662       auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
 663       if (!DVI)
 664         continue;
 665       auto Key = DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()});
 666       if (Key != DeadDebugSet.end())
 667         continue;
 668       DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()});
 669       DeadDebugInst.push_back(DVI);
 670     }
 671
 672   // After the loop has been deleted all the values defined and modified
 673   // inside the loop are going to be unavailable.
 674   // Since debug values in the loop have been deleted, inserting an undef
 675   // dbg.value truncates the range of any dbg.value before the loop where the
 676   // loop used to be. This is particularly important for constant values.
 677   DIBuilder DIB(*ExitBlock->getModule());
 678   Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
 679   assert(InsertDbgValueBefore &&
 680          "There should be a non-PHI instruction in exit block, else these "
 681          "instructions will have no parent.");
 682   for (auto *DVI : DeadDebugInst)
 683     DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()),
 684                                 DVI->getVariable(), DVI->getExpression(),
 685                                 DVI->getDebugLoc(), InsertDbgValueBefore);
 686
 687   // Remove the block from the reference counting scheme, so that we can
 688   // delete it freely later.
 689   for (auto *Block : L->blocks())
 690     Block->dropAllReferences();
 691
 692   if (MSSA && VerifyMemorySSA)
 693     MSSA->verifyMemorySSA();
 694
 695   if (LI) {
 696     // Erase the instructions and the blocks without having to worry
 697     // about ordering because we already dropped the references.
 698     // NOTE: This iteration is safe because erasing the block does not remove
 699     // its entry from the loop's block list.  We do that in the next section.
 700     for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
 701          LpI != LpE; ++LpI)
 702       (*LpI)->eraseFromParent();
 703
 704     // Finally, the blocks from loopinfo.  This has to happen late because
 705     // otherwise our loop iterators won't work.
 706
 707     SmallPtrSet<BasicBlock *, 8> blocks;
 708     blocks.insert(L->block_begin(), L->block_end());
 709     for (BasicBlock *BB : blocks)
 710       LI->removeBlock(BB);
 711
 712     // The last step is to update LoopInfo now that we've eliminated this loop.
 713     // Note: LoopInfo::erase remove the given loop and relink its subloops with
 714     // its parent. While removeLoop/removeChildLoop remove the given loop but
 715     // not relink its subloops, which is what we want.
 716     if (Loop *ParentLoop = L->getParentLoop()) {
 717       Loop::iterator I = find(*ParentLoop, L);
 718       assert(I != ParentLoop->end() && "Couldn't find loop");
 719       ParentLoop->removeChildLoop(I);
 720     } else {
 721       Loop::iterator I = find(*LI, L);
 722       assert(I != LI->end() && "Couldn't find loop");
 723       LI->removeLoop(I);
 724     }
 725     LI->destroy(L);
 726   }
 727 }
 728
 729 /// Checks if \p L has single exit through latch block except possibly
 730 /// "deoptimizing" exits. Returns branch instruction terminating the loop
 731 /// latch if above check is successful, nullptr otherwise.
 732 static BranchInst *getExpectedExitLoopLatchBranch(Loop *L) {
 733   BasicBlock *Latch = L->getLoopLatch();
 734   if (!Latch)
 735     return nullptr;
 736
 737   BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
 738   if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
 739     return nullptr;
 740
 741   assert((LatchBR->getSuccessor(0) == L->getHeader() ||
 742           LatchBR->getSuccessor(1) == L->getHeader()) &&
 743          "At least one edge out of the latch must go to the header");
 744
 745   SmallVector<BasicBlock *, 4> ExitBlocks;
 746   L->getUniqueNonLatchExitBlocks(ExitBlocks);
 747   if (any_of(ExitBlocks, [](const BasicBlock *EB) {
 748         return !EB->getTerminatingDeoptimizeCall();
 749       }))
 750     return nullptr;
 751
 752   return LatchBR;
 753 }
 754
 755 Optional<unsigned>
 756 llvm::getLoopEstimatedTripCount(Loop *L,
 757                                 unsigned *EstimatedLoopInvocationWeight) {
 758   // Support loops with an exiting latch and other existing exists only
 759   // deoptimize.
 760   BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L);
 761   if (!LatchBranch)
 762     return None;
 763
 764   // To estimate the number of times the loop body was executed, we want to
 765   // know the number of times the backedge was taken, vs. the number of times
 766   // we exited the loop.
 767   uint64_t BackedgeTakenWeight, LatchExitWeight;
 768   if (!LatchBranch->extractProfMetadata(BackedgeTakenWeight, LatchExitWeight))
 769     return None;
 770
 771   if (LatchBranch->getSuccessor(0) != L->getHeader())
 772     std::swap(BackedgeTakenWeight, LatchExitWeight);
 773
 774   if (!LatchExitWeight)
 775     return None;
 776
 777   if (EstimatedLoopInvocationWeight)
 778     *EstimatedLoopInvocationWeight = LatchExitWeight;
 779
 780   // Estimated backedge taken count is a ratio of the backedge taken weight by
 781   // the weight of the edge exiting the loop, rounded to nearest.
 782   uint64_t BackedgeTakenCount =
 783       llvm::divideNearest(BackedgeTakenWeight, LatchExitWeight);
 784   // Estimated trip count is one plus estimated backedge taken count.
 785   return BackedgeTakenCount + 1;
 786 }
 787
 788 bool llvm::setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
 789                                      unsigned EstimatedloopInvocationWeight) {
 790   // Support loops with an exiting latch and other existing exists only
 791   // deoptimize.
 792   BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L);
 793   if (!LatchBranch)
 794     return false;
 795
 796   // Calculate taken and exit weights.
 797   unsigned LatchExitWeight = 0;
 798   unsigned BackedgeTakenWeight = 0;
 799
 800   if (EstimatedTripCount > 0) {
 801     LatchExitWeight = EstimatedloopInvocationWeight;
 802     BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
 803   }
 804
 805   // Make a swap if back edge is taken when condition is "false".
 806   if (LatchBranch->getSuccessor(0) != L->getHeader())
 807     std::swap(BackedgeTakenWeight, LatchExitWeight);
 808
 809   MDBuilder MDB(LatchBranch->getContext());
 810
 811   // Set/Update profile metadata.
 812   LatchBranch->setMetadata(
 813       LLVMContext::MD_prof,
 814       MDB.createBranchWeights(BackedgeTakenWeight, LatchExitWeight));
 815
 816   return true;
 817 }
 818
 819 bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop,
 820                                               ScalarEvolution &SE) {
 821   Loop *OuterL = InnerLoop->getParentLoop();
 822   if (!OuterL)
 823     return true;
 824
 825   // Get the backedge taken count for the inner loop
 826   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 827   const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
 828   if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
 829       !InnerLoopBECountSC->getType()->isIntegerTy())
 830     return false;
 831
 832   // Get whether count is invariant to the outer loop
 833   ScalarEvolution::LoopDisposition LD =
 834       SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
 835   if (LD != ScalarEvolution::LoopInvariant)
 836     return false;
 837
 838   return true;
 839 }
 840
 841 Value *llvm::createMinMaxOp(IRBuilderBase &Builder,
 842                             RecurrenceDescriptor::MinMaxRecurrenceKind RK,
 843                             Value *Left, Value *Right) {
 844   CmpInst::Predicate P = CmpInst::ICMP_NE;
 845   switch (RK) {
 846   default:
 847     llvm_unreachable("Unknown min/max recurrence kind");
 848   case RecurrenceDescriptor::MRK_UIntMin:
 849     P = CmpInst::ICMP_ULT;
 850     break;
 851   case RecurrenceDescriptor::MRK_UIntMax:
 852     P = CmpInst::ICMP_UGT;
 853     break;
 854   case RecurrenceDescriptor::MRK_SIntMin:
 855     P = CmpInst::ICMP_SLT;
 856     break;
 857   case RecurrenceDescriptor::MRK_SIntMax:
 858     P = CmpInst::ICMP_SGT;
 859     break;
 860   case RecurrenceDescriptor::MRK_FloatMin:
 861     P = CmpInst::FCMP_OLT;
 862     break;
 863   case RecurrenceDescriptor::MRK_FloatMax:
 864     P = CmpInst::FCMP_OGT;
 865     break;
 866   }
 867
 868   // We only match FP sequences that are 'fast', so we can unconditionally
 869   // set it on any generated instructions.
 870   IRBuilderBase::FastMathFlagGuard FMFG(Builder);
 871   FastMathFlags FMF;
 872   FMF.setFast();
 873   Builder.setFastMathFlags(FMF);
 874   Value *Cmp = Builder.CreateCmp(P, Left, Right, "rdx.minmax.cmp");
 875   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
 876   return Select;
 877 }
 878
 879 // Helper to generate an ordered reduction.
 880 Value *
 881 llvm::getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
 882                           unsigned Op,
 883                           RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
 884                           ArrayRef<Value *> RedOps) {
 885   unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
 886
 887   // Extract and apply reduction ops in ascending order:
 888   // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
 889   Value *Result = Acc;
 890   for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
 891     Value *Ext =
 892         Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
 893
 894     if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
 895       Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
 896                                    "bin.rdx");
 897     } else {
 898       assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
 899              "Invalid min/max");
 900       Result = createMinMaxOp(Builder, MinMaxKind, Result, Ext);
 901     }
 902
 903     if (!RedOps.empty())
 904       propagateIRFlags(Result, RedOps);
 905   }
 906
 907   return Result;
 908 }
 909
 910 // Helper to generate a log2 shuffle reduction.
 911 Value *
 912 llvm::getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op,
 913                           RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
 914                           ArrayRef<Value *> RedOps) {
 915   unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
 916   // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
 917   // and vector ops, reducing the set of values being computed by half each
 918   // round.
 919   assert(isPowerOf2_32(VF) &&
 920          "Reduction emission only supported for pow2 vectors!");
 921   Value *TmpVec = Src;
 922   SmallVector<int, 32> ShuffleMask(VF);
 923   for (unsigned i = VF; i != 1; i >>= 1) {
 924     // Move the upper half of the vector to the lower half.
 925     for (unsigned j = 0; j != i / 2; ++j)
 926       ShuffleMask[j] = i / 2 + j;
 927
 928     // Fill the rest of the mask with undef.
 929     std::fill(&ShuffleMask[i / 2], ShuffleMask.end(), -1);
 930
 931     Value *Shuf = Builder.CreateShuffleVector(
 932         TmpVec, UndefValue::get(TmpVec->getType()), ShuffleMask, "rdx.shuf");
 933
 934     if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
 935       // The builder propagates its fast-math-flags setting.
 936       TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
 937                                    "bin.rdx");
 938     } else {
 939       assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
 940              "Invalid min/max");
 941       TmpVec = createMinMaxOp(Builder, MinMaxKind, TmpVec, Shuf);
 942     }
 943     if (!RedOps.empty())
 944       propagateIRFlags(TmpVec, RedOps);
 945
 946     // We may compute the reassociated scalar ops in a way that does not
 947     // preserve nsw/nuw etc. Conservatively, drop those flags.
 948     if (auto *ReductionInst = dyn_cast<Instruction>(TmpVec))
 949       ReductionInst->dropPoisonGeneratingFlags();
 950   }
 951   // The result is in the first element of the vector.
 952   return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
 953 }
 954
 955 /// Create a simple vector reduction specified by an opcode and some
 956 /// flags (if generating min/max reductions).
 957 Value *llvm::createSimpleTargetReduction(
 958     IRBuilderBase &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
 959     Value *Src, TargetTransformInfo::ReductionFlags Flags,
 960     ArrayRef<Value *> RedOps) {
 961   auto *SrcVTy = cast<VectorType>(Src->getType());
 962
 963   std::function<Value *()> BuildFunc;
 964   using RD = RecurrenceDescriptor;
 965   RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
 966
 967   switch (Opcode) {
 968   case Instruction::Add:
 969     BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
 970     break;
 971   case Instruction::Mul:
 972     BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
 973     break;
 974   case Instruction::And:
 975     BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
 976     break;
 977   case Instruction::Or:
 978     BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
 979     break;
 980   case Instruction::Xor:
 981     BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
 982     break;
 983   case Instruction::FAdd:
 984     BuildFunc = [&]() {
 985       auto Rdx = Builder.CreateFAddReduce(
 986           Constant::getNullValue(SrcVTy->getElementType()), Src);
 987       return Rdx;
 988     };
 989     break;
 990   case Instruction::FMul:
 991     BuildFunc = [&]() {
 992       Type *Ty = SrcVTy->getElementType();
 993       auto Rdx = Builder.CreateFMulReduce(ConstantFP::get(Ty, 1.0), Src);
 994       return Rdx;
 995     };
 996     break;
 997   case Instruction::ICmp:
 998     if (Flags.IsMaxOp) {
 999       MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
1000       BuildFunc = [&]() {
1001         return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
1002       };
1003     } else {
1004       MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
1005       BuildFunc = [&]() {
1006         return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
1007       };
1008     }
1009     break;
1010   case Instruction::FCmp:
1011     if (Flags.IsMaxOp) {
1012       MinMaxKind = RD::MRK_FloatMax;
1013       BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
1014     } else {
1015       MinMaxKind = RD::MRK_FloatMin;
1016       BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
1017     }
1018     break;
1019   default:
1020     llvm_unreachable("Unhandled opcode");
1021     break;
1022   }
1023   if (ForceReductionIntrinsic ||
1024       TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
1025     return BuildFunc();
1026   return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
1027 }
1028
1029 /// Create a vector reduction using a given recurrence descriptor.
1030 Value *llvm::createTargetReduction(IRBuilderBase &B,
1031                                    const TargetTransformInfo *TTI,
1032                                    RecurrenceDescriptor &Desc, Value *Src,
1033                                    bool NoNaN) {
1034   // TODO: Support in-order reductions based on the recurrence descriptor.
1035   using RD = RecurrenceDescriptor;
1036   RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
1037   TargetTransformInfo::ReductionFlags Flags;
1038   Flags.NoNaN = NoNaN;
1039
1040   // All ops in the reduction inherit fast-math-flags from the recurrence
1041   // descriptor.
1042   IRBuilderBase::FastMathFlagGuard FMFGuard(B);
1043   B.setFastMathFlags(Desc.getFastMathFlags());
1044
1045   switch (RecKind) {
1046   case RD::RK_FloatAdd:
1047     return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
1048   case RD::RK_FloatMult:
1049     return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
1050   case RD::RK_IntegerAdd:
1051     return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
1052   case RD::RK_IntegerMult:
1053     return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
1054   case RD::RK_IntegerAnd:
1055     return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
1056   case RD::RK_IntegerOr:
1057     return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
1058   case RD::RK_IntegerXor:
1059     return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
1060   case RD::RK_IntegerMinMax: {
1061     RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
1062     Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
1063     Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
1064     return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
1065   }
1066   case RD::RK_FloatMinMax: {
1067     Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
1068     return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
1069   }
1070   default:
1071     llvm_unreachable("Unhandled RecKind");
1072   }
1073 }
1074
1075 void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) {
1076   auto *VecOp = dyn_cast<Instruction>(I);
1077   if (!VecOp)
1078     return;
1079   auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1080                                             : dyn_cast<Instruction>(OpValue);
1081   if (!Intersection)
1082     return;
1083   const unsigned Opcode = Intersection->getOpcode();
1084   VecOp->copyIRFlags(Intersection);
1085   for (auto *V : VL) {
1086     auto *Instr = dyn_cast<Instruction>(V);
1087     if (!Instr)
1088       continue;
1089     if (OpValue == nullptr || Opcode == Instr->getOpcode())
1090       VecOp->andIRFlags(V);
1091   }
1092 }
1093
1094 bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
1095                                  ScalarEvolution &SE) {
1096   const SCEV *Zero = SE.getZero(S->getType());
1097   return SE.isAvailableAtLoopEntry(S, L) &&
1098          SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, S, Zero);
1099 }
1100
1101 bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
1102                                     ScalarEvolution &SE) {
1103   const SCEV *Zero = SE.getZero(S->getType());
1104   return SE.isAvailableAtLoopEntry(S, L) &&
1105          SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero);
1106 }
1107
1108 bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1109                              bool Signed) {
1110   unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1111   APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) :
1112     APInt::getMinValue(BitWidth);
1113   auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1114   return SE.isAvailableAtLoopEntry(S, L) &&
1115          SE.isLoopEntryGuardedByCond(L, Predicate, S,
1116                                      SE.getConstant(Min));
1117 }
1118
1119 bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1120                              bool Signed) {
1121   unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1122   APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
1123     APInt::getMaxValue(BitWidth);
1124   auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1125   return SE.isAvailableAtLoopEntry(S, L) &&
1126          SE.isLoopEntryGuardedByCond(L, Predicate, S,
1127                                      SE.getConstant(Max));
1128 }
1129
1130 //===----------------------------------------------------------------------===//
1131 // rewriteLoopExitValues - Optimize IV users outside the loop.
1132 // As a side effect, reduces the amount of IV processing within the loop.
1133 //===----------------------------------------------------------------------===//
1134
1135 // Return true if the SCEV expansion generated by the rewriter can replace the
1136 // original value. SCEV guarantees that it produces the same value, but the way
1137 // it is produced may be illegal IR.  Ideally, this function will only be
1138 // called for verification.
1139 static bool isValidRewrite(ScalarEvolution *SE, Value *FromVal, Value *ToVal) {
1140   // If an SCEV expression subsumed multiple pointers, its expansion could
1141   // reassociate the GEP changing the base pointer. This is illegal because the
1142   // final address produced by a GEP chain must be inbounds relative to its
1143   // underlying object. Otherwise basic alias analysis, among other things,
1144   // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
1145   // producing an expression involving multiple pointers. Until then, we must
1146   // bail out here.
1147   //
1148   // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject
1149   // because it understands lcssa phis while SCEV does not.
1150   Value *FromPtr = FromVal;
1151   Value *ToPtr = ToVal;
1152   if (auto *GEP = dyn_cast<GEPOperator>(FromVal))
1153     FromPtr = GEP->getPointerOperand();
1154
1155   if (auto *GEP = dyn_cast<GEPOperator>(ToVal))
1156     ToPtr = GEP->getPointerOperand();
1157
1158   if (FromPtr != FromVal || ToPtr != ToVal) {
1159     // Quickly check the common case
1160     if (FromPtr == ToPtr)
1161       return true;
1162
1163     // SCEV may have rewritten an expression that produces the GEP's pointer
1164     // operand. That's ok as long as the pointer operand has the same base
1165     // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the
1166     // base of a recurrence. This handles the case in which SCEV expansion
1167     // converts a pointer type recurrence into a nonrecurrent pointer base
1168     // indexed by an integer recurrence.
1169
1170     // If the GEP base pointer is a vector of pointers, abort.
1171     if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
1172       return false;
1173
1174     const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
1175     const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
1176     if (FromBase == ToBase)
1177       return true;
1178
1179     LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: GEP rewrite bail out "
1180                       << *FromBase << " != " << *ToBase << "\n");
1181
1182     return false;
1183   }
1184   return true;
1185 }
1186
1187 static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
1188   SmallPtrSet<const Instruction *, 8> Visited;
1189   SmallVector<const Instruction *, 8> WorkList;
1190   Visited.insert(I);
1191   WorkList.push_back(I);
1192   while (!WorkList.empty()) {
1193     const Instruction *Curr = WorkList.pop_back_val();
1194     // This use is outside the loop, nothing to do.
1195     if (!L->contains(Curr))
1196       continue;
1197     // Do we assume it is a "hard" use which will not be eliminated easily?
1198     if (Curr->mayHaveSideEffects())
1199       return true;
1200     // Otherwise, add all its users to worklist.
1201     for (auto U : Curr->users()) {
1202       auto *UI = cast<Instruction>(U);
1203       if (Visited.insert(UI).second)
1204         WorkList.push_back(UI);
1205     }
1206   }
1207   return false;
1208 }
1209
1210 // Collect information about PHI nodes which can be transformed in
1211 // rewriteLoopExitValues.
1212 struct RewritePhi {
1213   PHINode *PN;               // For which PHI node is this replacement?
1214   unsigned Ith;              // For which incoming value?
1215   const SCEV *ExpansionSCEV; // The SCEV of the incoming value we are rewriting.
1216   Instruction *ExpansionPoint; // Where we'd like to expand that SCEV?
1217   bool HighCost;               // Is this expansion a high-cost?
1218
1219   Value *Expansion = nullptr;
1220   bool ValidRewrite = false;
1221
1222   RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt,
1223              bool H)
1224       : PN(P), Ith(I), ExpansionSCEV(Val), ExpansionPoint(ExpansionPt),
1225         HighCost(H) {}
1226 };
1227
1228 // Check whether it is possible to delete the loop after rewriting exit
1229 // value. If it is possible, ignore ReplaceExitValue and do rewriting
1230 // aggressively.
1231 static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
1232   BasicBlock *Preheader = L->getLoopPreheader();
1233   // If there is no preheader, the loop will not be deleted.
1234   if (!Preheader)
1235     return false;
1236
1237   // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
1238   // We obviate multiple ExitingBlocks case for simplicity.
1239   // TODO: If we see testcase with multiple ExitingBlocks can be deleted
1240   // after exit value rewriting, we can enhance the logic here.
1241   SmallVector<BasicBlock *, 4> ExitingBlocks;
1242   L->getExitingBlocks(ExitingBlocks);
1243   SmallVector<BasicBlock *, 8> ExitBlocks;
1244   L->getUniqueExitBlocks(ExitBlocks);
1245   if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
1246     return false;
1247
1248   BasicBlock *ExitBlock = ExitBlocks[0];
1249   BasicBlock::iterator BI = ExitBlock->begin();
1250   while (PHINode *P = dyn_cast<PHINode>(BI)) {
1251     Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
1252
1253     // If the Incoming value of P is found in RewritePhiSet, we know it
1254     // could be rewritten to use a loop invariant value in transformation
1255     // phase later. Skip it in the loop invariant check below.
1256     bool found = false;
1257     for (const RewritePhi &Phi : RewritePhiSet) {
1258       if (!Phi.ValidRewrite)
1259         continue;
1260       unsigned i = Phi.Ith;
1261       if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1262         found = true;
1263         break;
1264       }
1265     }
1266
1267     Instruction *I;
1268     if (!found && (I = dyn_cast<Instruction>(Incoming)))
1269       if (!L->hasLoopInvariantOperands(I))
1270         return false;
1271
1272     ++BI;
1273   }
1274
1275   for (auto *BB : L->blocks())
1276     if (llvm::any_of(*BB, [](Instruction &I) {
1277           return I.mayHaveSideEffects();
1278         }))
1279       return false;
1280
1281   return true;
1282 }
1283
1284 int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
1285                                 ScalarEvolution *SE,
1286                                 const TargetTransformInfo *TTI,
1287                                 SCEVExpander &Rewriter, DominatorTree *DT,
1288                                 ReplaceExitVal ReplaceExitValue,
1289                                 SmallVector<WeakTrackingVH, 16> &DeadInsts) {
1290   // Check a pre-condition.
1291   assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1292          "Indvars did not preserve LCSSA!");
1293
1294   SmallVector<BasicBlock*, 8> ExitBlocks;
1295   L->getUniqueExitBlocks(ExitBlocks);
1296
1297   SmallVector<RewritePhi, 8> RewritePhiSet;
1298   // Find all values that are computed inside the loop, but used outside of it.
1299   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
1300   // the exit blocks of the loop to find them.
1301   for (BasicBlock *ExitBB : ExitBlocks) {
1302     // If there are no PHI nodes in this exit block, then no values defined
1303     // inside the loop are used on this path, skip it.
1304     PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1305     if (!PN) continue;
1306
1307     unsigned NumPreds = PN->getNumIncomingValues();
1308
1309     // Iterate over all of the PHI nodes.
1310     BasicBlock::iterator BBI = ExitBB->begin();
1311     while ((PN = dyn_cast<PHINode>(BBI++))) {
1312       if (PN->use_empty())
1313         continue; // dead use, don't replace it
1314
1315       if (!SE->isSCEVable(PN->getType()))
1316         continue;
1317
1318       // It's necessary to tell ScalarEvolution about this explicitly so that
1319       // it can walk the def-use list and forget all SCEVs, as it may not be
1320       // watching the PHI itself. Once the new exit value is in place, there
1321       // may not be a def-use connection between the loop and every instruction
1322       // which got a SCEVAddRecExpr for that loop.
1323       SE->forgetValue(PN);
1324
1325       // Iterate over all of the values in all the PHI nodes.
1326       for (unsigned i = 0; i != NumPreds; ++i) {
1327         // If the value being merged in is not integer or is not defined
1328         // in the loop, skip it.
1329         Value *InVal = PN->getIncomingValue(i);
1330         if (!isa<Instruction>(InVal))
1331           continue;
1332
1333         // If this pred is for a subloop, not L itself, skip it.
1334         if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
1335           continue; // The Block is in a subloop, skip it.
1336
1337         // Check that InVal is defined in the loop.
1338         Instruction *Inst = cast<Instruction>(InVal);
1339         if (!L->contains(Inst))
1340           continue;
1341
1342         // Okay, this instruction has a user outside of the current loop
1343         // and varies predictably *inside* the loop.  Evaluate the value it
1344         // contains when the loop exits, if possible.  We prefer to start with
1345         // expressions which are true for all exits (so as to maximize
1346         // expression reuse by the SCEVExpander), but resort to per-exit
1347         // evaluation if that fails.
1348         const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
1349         if (isa<SCEVCouldNotCompute>(ExitValue) ||
1350             !SE->isLoopInvariant(ExitValue, L) ||
1351             !isSafeToExpand(ExitValue, *SE)) {
1352           // TODO: This should probably be sunk into SCEV in some way; maybe a
1353           // getSCEVForExit(SCEV*, L, ExitingBB)?  It can be generalized for
1354           // most SCEV expressions and other recurrence types (e.g. shift
1355           // recurrences).  Is there existing code we can reuse?
1356           const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
1357           if (isa<SCEVCouldNotCompute>(ExitCount))
1358             continue;
1359           if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst)))
1360             if (AddRec->getLoop() == L)
1361               ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1362           if (isa<SCEVCouldNotCompute>(ExitValue) ||
1363               !SE->isLoopInvariant(ExitValue, L) ||
1364               !isSafeToExpand(ExitValue, *SE))
1365             continue;
1366         }
1367
1368         // Computing the value outside of the loop brings no benefit if it is
1369         // definitely used inside the loop in a way which can not be optimized
1370         // away. Avoid doing so unless we know we have a value which computes
1371         // the ExitValue already. TODO: This should be merged into SCEV
1372         // expander to leverage its knowledge of existing expressions.
1373         if (ReplaceExitValue != AlwaysRepl && !isa<SCEVConstant>(ExitValue) &&
1374             !isa<SCEVUnknown>(ExitValue) && hasHardUserWithinLoop(L, Inst))
1375           continue;
1376
1377         // Check if expansions of this SCEV would count as being high cost.
1378         bool HighCost = Rewriter.isHighCostExpansion(
1379             ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
1380
1381         // Note that we must not perform expansions until after
1382         // we query *all* the costs, because if we perform temporary expansion
1383         // inbetween, one that we might not intend to keep, said expansion
1384         // *may* affect cost calculation of the the next SCEV's we'll query,
1385         // and next SCEV may errneously get smaller cost.
1386
1387         // Collect all the candidate PHINodes to be rewritten.
1388         RewritePhiSet.emplace_back(PN, i, ExitValue, Inst, HighCost);
1389       }
1390     }
1391   }
1392
1393   // Now that we've done preliminary filtering and billed all the SCEV's,
1394   // we can perform the last sanity check - the expansion must be valid.
1395   for (RewritePhi &Phi : RewritePhiSet) {
1396     Phi.Expansion = Rewriter.expandCodeFor(Phi.ExpansionSCEV, Phi.PN->getType(),
1397                                            Phi.ExpansionPoint);
1398
1399     LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = "
1400                       << *(Phi.Expansion) << '\n'
1401                       << "  LoopVal = " << *(Phi.ExpansionPoint) << "\n");
1402
1403     // FIXME: isValidRewrite() is a hack. it should be an assert, eventually.
1404     Phi.ValidRewrite = isValidRewrite(SE, Phi.ExpansionPoint, Phi.Expansion);
1405     if (!Phi.ValidRewrite) {
1406       DeadInsts.push_back(Phi.Expansion);
1407       continue;
1408     }
1409
1410 #ifndef NDEBUG
1411     // If we reuse an instruction from a loop which is neither L nor one of
1412     // its containing loops, we end up breaking LCSSA form for this loop by
1413     // creating a new use of its instruction.
1414     if (auto *ExitInsn = dyn_cast<Instruction>(Phi.Expansion))
1415       if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
1416         if (EVL != L)
1417           assert(EVL->contains(L) && "LCSSA breach detected!");
1418 #endif
1419   }
1420
1421   // TODO: after isValidRewrite() is an assertion, evaluate whether
1422   // it is beneficial to change how we calculate high-cost:
1423   // if we have SCEV 'A' which we know we will expand, should we calculate
1424   // the cost of other SCEV's after expanding SCEV 'A',
1425   // thus potentially giving cost bonus to those other SCEV's?
1426
1427   bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
1428   int NumReplaced = 0;
1429
1430   // Transformation.
1431   for (const RewritePhi &Phi : RewritePhiSet) {
1432     if (!Phi.ValidRewrite)
1433       continue;
1434
1435     PHINode *PN = Phi.PN;
1436     Value *ExitVal = Phi.Expansion;
1437
1438     // Only do the rewrite when the ExitValue can be expanded cheaply.
1439     // If LoopCanBeDel is true, rewrite exit value aggressively.
1440     if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
1441       DeadInsts.push_back(ExitVal);
1442       continue;
1443     }
1444
1445     NumReplaced++;
1446     Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
1447     PN->setIncomingValue(Phi.Ith, ExitVal);
1448
1449     // If this instruction is dead now, delete it. Don't do it now to avoid
1450     // invalidating iterators.
1451     if (isInstructionTriviallyDead(Inst, TLI))
1452       DeadInsts.push_back(Inst);
1453
1454     // Replace PN with ExitVal if that is legal and does not break LCSSA.
1455     if (PN->getNumIncomingValues() == 1 &&
1456         LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
1457       PN->replaceAllUsesWith(ExitVal);
1458       PN->eraseFromParent();
1459     }
1460   }
1461
1462   // The insertion point instruction may have been deleted; clear it out
1463   // so that the rewriter doesn't trip over it later.
1464   Rewriter.clearInsertPoint();
1465   return NumReplaced;
1466 }
1467
1468 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
1469 /// \p OrigLoop.
1470 void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
1471                                         Loop *RemainderLoop, uint64_t UF) {
1472   assert(UF > 0 && "Zero unrolled factor is not supported");
1473   assert(UnrolledLoop != RemainderLoop &&
1474          "Unrolled and Remainder loops are expected to distinct");
1475
1476   // Get number of iterations in the original scalar loop.
1477   unsigned OrigLoopInvocationWeight = 0;
1478   Optional<unsigned> OrigAverageTripCount =
1479       getLoopEstimatedTripCount(OrigLoop, &OrigLoopInvocationWeight);
1480   if (!OrigAverageTripCount)
1481     return;
1482
1483   // Calculate number of iterations in unrolled loop.
1484   unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1485   // Calculate number of iterations for remainder loop.
1486   unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1487
1488   setLoopEstimatedTripCount(UnrolledLoop, UnrolledAverageTripCount,
1489                             OrigLoopInvocationWeight);
1490   setLoopEstimatedTripCount(RemainderLoop, RemainderAverageTripCount,
1491                             OrigLoopInvocationWeight);
1492 }
1493
1494 /// Utility that implements appending of loops onto a worklist.
1495 /// Loops are added in preorder (analogous for reverse postorder for trees),
1496 /// and the worklist is processed LIFO.
1497 template <typename RangeT>
1498 void llvm::appendReversedLoopsToWorklist(
1499     RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) {
1500   // We use an internal worklist to build up the preorder traversal without
1501   // recursion.
1502   SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
1503
1504   // We walk the initial sequence of loops in reverse because we generally want
1505   // to visit defs before uses and the worklist is LIFO.
1506   for (Loop *RootL : Loops) {
1507     assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
1508     assert(PreOrderWorklist.empty() &&
1509            "Must start with an empty preorder walk worklist.");
1510     PreOrderWorklist.push_back(RootL);
1511     do {
1512       Loop *L = PreOrderWorklist.pop_back_val();
1513       PreOrderWorklist.append(L->begin(), L->end());
1514       PreOrderLoops.push_back(L);
1515     } while (!PreOrderWorklist.empty());
1516
1517     Worklist.insert(std::move(PreOrderLoops));
1518     PreOrderLoops.clear();
1519   }
1520 }
1521
1522 template <typename RangeT>
1523 void llvm::appendLoopsToWorklist(RangeT &&Loops,
1524                                  SmallPriorityWorklist<Loop *, 4> &Worklist) {
1525   appendReversedLoopsToWorklist(reverse(Loops), Worklist);
1526 }
1527
1528 template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1529     ArrayRef<Loop *> &Loops, SmallPriorityWorklist<Loop *, 4> &Worklist);
1530
1531 template void
1532 llvm::appendLoopsToWorklist<Loop &>(Loop &L,
1533                                     SmallPriorityWorklist<Loop *, 4> &Worklist);
1534
1535 void llvm::appendLoopsToWorklist(LoopInfo &LI,
1536                                  SmallPriorityWorklist<Loop *, 4> &Worklist) {
1537   appendReversedLoopsToWorklist(LI, Worklist);
1538 }
1539
1540 Loop *llvm::cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
1541                       LoopInfo *LI, LPPassManager *LPM) {
1542   Loop &New = *LI->AllocateLoop();
1543   if (PL)
1544     PL->addChildLoop(&New);
1545   else
1546     LI->addTopLevelLoop(&New);
1547
1548   if (LPM)
1549     LPM->addLoop(New);
1550
1551   // Add all of the blocks in L to the new loop.
1552   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
1553        I != E; ++I)
1554     if (LI->getLoopFor(*I) == L)
1555       New.addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI);
1556
1557   // Add all of the subloops to the new loop.
1558   for (Loop *I : *L)
1559     cloneLoop(I, &New, VM, LI, LPM);
1560
1561   return &New;
1562 }
1563
1564 /// IR Values for the lower and upper bounds of a pointer evolution.  We
1565 /// need to use value-handles because SCEV expansion can invalidate previously
1566 /// expanded values.  Thus expansion of a pointer can invalidate the bounds for
1567 /// a previous one.
1568 struct PointerBounds {
1569   TrackingVH<Value> Start;
1570   TrackingVH<Value> End;
1571 };
1572
1573 /// Expand code for the lower and upper bound of the pointer group \p CG
1574 /// in \p TheLoop.  \return the values for the bounds.
1575 static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG,
1576                                   Loop *TheLoop, Instruction *Loc,
1577                                   SCEVExpander &Exp, ScalarEvolution *SE) {
1578   // TODO: Add helper to retrieve pointers to CG.
1579   Value *Ptr = CG->RtCheck.Pointers[CG->Members[0]].PointerValue;
1580   const SCEV *Sc = SE->getSCEV(Ptr);
1581
1582   unsigned AS = Ptr->getType()->getPointerAddressSpace();
1583   LLVMContext &Ctx = Loc->getContext();
1584
1585   // Use this type for pointer arithmetic.
1586   Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
1587
1588   if (SE->isLoopInvariant(Sc, TheLoop)) {
1589     LLVM_DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:"
1590                       << *Ptr << "\n");
1591     // Ptr could be in the loop body. If so, expand a new one at the correct
1592     // location.
1593     Instruction *Inst = dyn_cast<Instruction>(Ptr);
1594     Value *NewPtr = (Inst && TheLoop->contains(Inst))
1595                         ? Exp.expandCodeFor(Sc, PtrArithTy, Loc)
1596                         : Ptr;
1597     // We must return a half-open range, which means incrementing Sc.
1598     const SCEV *ScPlusOne = SE->getAddExpr(Sc, SE->getOne(PtrArithTy));
1599     Value *NewPtrPlusOne = Exp.expandCodeFor(ScPlusOne, PtrArithTy, Loc);
1600     return {NewPtr, NewPtrPlusOne};
1601   } else {
1602     Value *Start = nullptr, *End = nullptr;
1603     LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
1604     Start = Exp.expandCodeFor(CG->Low, PtrArithTy, Loc);
1605     End = Exp.expandCodeFor(CG->High, PtrArithTy, Loc);
1606     LLVM_DEBUG(dbgs() << "Start: " << *CG->Low << " End: " << *CG->High
1607                       << "\n");
1608     return {Start, End};
1609   }
1610 }
1611
1612 /// Turns a collection of checks into a collection of expanded upper and
1613 /// lower bounds for both pointers in the check.
1614 static SmallVector<std::pair<PointerBounds, PointerBounds>, 4>
1615 expandBounds(const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, Loop *L,
1616              Instruction *Loc, ScalarEvolution *SE, SCEVExpander &Exp) {
1617   SmallVector<std::pair<PointerBounds, PointerBounds>, 4> ChecksWithBounds;
1618
1619   // Here we're relying on the SCEV Expander's cache to only emit code for the
1620   // same bounds once.
1621   transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1622             [&](const RuntimePointerCheck &Check) {
1623               PointerBounds First = expandBounds(Check.first, L, Loc, Exp, SE),
1624                             Second =
1625                                 expandBounds(Check.second, L, Loc, Exp, SE);
1626               return std::make_pair(First, Second);
1627             });
1628
1629   return ChecksWithBounds;
1630 }
1631
1632 std::pair<Instruction *, Instruction *> llvm::addRuntimeChecks(
1633     Instruction *Loc, Loop *TheLoop,
1634     const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
1635     ScalarEvolution *SE) {
1636   // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible.
1637   // TODO: Pass  RtPtrChecking instead of PointerChecks and SE separately, if possible
1638   const DataLayout &DL = TheLoop->getHeader()->getModule()->getDataLayout();
1639   SCEVExpander Exp(*SE, DL, "induction");
1640   auto ExpandedChecks = expandBounds(PointerChecks, TheLoop, Loc, SE, Exp);
1641
1642   LLVMContext &Ctx = Loc->getContext();
1643   Instruction *FirstInst = nullptr;
1644   IRBuilder<> ChkBuilder(Loc);
1645   // Our instructions might fold to a constant.
1646   Value *MemoryRuntimeCheck = nullptr;
1647
1648   // FIXME: this helper is currently a duplicate of the one in
1649   // LoopVectorize.cpp.
1650   auto GetFirstInst = [](Instruction *FirstInst, Value *V,
1651                          Instruction *Loc) -> Instruction * {
1652     if (FirstInst)
1653       return FirstInst;
1654     if (Instruction *I = dyn_cast<Instruction>(V))
1655       return I->getParent() == Loc->getParent() ? I : nullptr;
1656     return nullptr;
1657   };
1658
1659   for (const auto &Check : ExpandedChecks) {
1660     const PointerBounds &A = Check.first, &B = Check.second;
1661     // Check if two pointers (A and B) conflict where conflict is computed as:
1662     // start(A) <= end(B) && start(B) <= end(A)
1663     unsigned AS0 = A.Start->getType()->getPointerAddressSpace();
1664     unsigned AS1 = B.Start->getType()->getPointerAddressSpace();
1665
1666     assert((AS0 == B.End->getType()->getPointerAddressSpace()) &&
1667            (AS1 == A.End->getType()->getPointerAddressSpace()) &&
1668            "Trying to bounds check pointers with different address spaces");
1669
1670     Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
1671     Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
1672
1673     Value *Start0 = ChkBuilder.CreateBitCast(A.Start, PtrArithTy0, "bc");
1674     Value *Start1 = ChkBuilder.CreateBitCast(B.Start, PtrArithTy1, "bc");
1675     Value *End0 = ChkBuilder.CreateBitCast(A.End, PtrArithTy1, "bc");
1676     Value *End1 = ChkBuilder.CreateBitCast(B.End, PtrArithTy0, "bc");
1677
1678     // [A|B].Start points to the first accessed byte under base [A|B].
1679     // [A|B].End points to the last accessed byte, plus one.
1680     // There is no conflict when the intervals are disjoint:
1681     // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
1682     //
1683     // bound0 = (B.Start < A.End)
1684     // bound1 = (A.Start < B.End)
1685     //  IsConflict = bound0 & bound1
1686     Value *Cmp0 = ChkBuilder.CreateICmpULT(Start0, End1, "bound0");
1687     FirstInst = GetFirstInst(FirstInst, Cmp0, Loc);
1688     Value *Cmp1 = ChkBuilder.CreateICmpULT(Start1, End0, "bound1");
1689     FirstInst = GetFirstInst(FirstInst, Cmp1, Loc);
1690     Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
1691     FirstInst = GetFirstInst(FirstInst, IsConflict, Loc);
1692     if (MemoryRuntimeCheck) {
1693       IsConflict =
1694           ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
1695       FirstInst = GetFirstInst(FirstInst, IsConflict, Loc);
1696     }
1697     MemoryRuntimeCheck = IsConflict;
1698   }
1699
1700   if (!MemoryRuntimeCheck)
1701     return std::make_pair(nullptr, nullptr);
1702
1703   // We have to do this trickery because the IRBuilder might fold the check to a
1704   // constant expression in which case there is no Instruction anchored in a
1705   // the block.
1706   Instruction *Check =
1707       BinaryOperator::CreateAnd(MemoryRuntimeCheck, ConstantInt::getTrue(Ctx));
1708   ChkBuilder.Insert(Check, "memcheck.conflict");
1709   FirstInst = GetFirstInst(FirstInst, Check, Loc);
1710   return std::make_pair(FirstInst, Check);
1711 }