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/ScopeExit.h"
  15 #include "llvm/Analysis/AliasAnalysis.h"
  16 #include "llvm/Analysis/BasicAliasAnalysis.h"
  17 #include "llvm/Analysis/DomTreeUpdater.h"
  18 #include "llvm/Analysis/GlobalsModRef.h"
  19 #include "llvm/Analysis/InstructionSimplify.h"
  20 #include "llvm/Analysis/LoopInfo.h"
  21 #include "llvm/Analysis/LoopPass.h"
  22 #include "llvm/Analysis/MemorySSAUpdater.h"
  23 #include "llvm/Analysis/MustExecute.h"
  24 #include "llvm/Analysis/ScalarEvolution.h"
  25 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  26 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  27 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  28 #include "llvm/Analysis/TargetTransformInfo.h"
  29 #include "llvm/Analysis/ValueTracking.h"
  30 #include "llvm/IR/DIBuilder.h"
  31 #include "llvm/IR/Dominators.h"
  32 #include "llvm/IR/Instructions.h"
  33 #include "llvm/IR/IntrinsicInst.h"
  34 #include "llvm/IR/Module.h"
  35 #include "llvm/IR/PatternMatch.h"
  36 #include "llvm/IR/ValueHandle.h"
  37 #include "llvm/Pass.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/KnownBits.h"
  40 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  41
  42 using namespace llvm;
  43 using namespace llvm::PatternMatch;
  44
  45 #define DEBUG_TYPE "loop-utils"
  46
  47 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
  48 static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
  49
  50 bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
  51                                    MemorySSAUpdater *MSSAU,
  52                                    bool PreserveLCSSA) {
  53   bool Changed = false;
  54
  55   // We re-use a vector for the in-loop predecesosrs.
  56   SmallVector<BasicBlock *, 4> InLoopPredecessors;
  57
  58   auto RewriteExit = [&](BasicBlock *BB) {
  59     assert(InLoopPredecessors.empty() &&
  60            "Must start with an empty predecessors list!");
  61     auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
  62
  63     // See if there are any non-loop predecessors of this exit block and
  64     // keep track of the in-loop predecessors.
  65     bool IsDedicatedExit = true;
  66     for (auto *PredBB : predecessors(BB))
  67       if (L->contains(PredBB)) {
  68         if (isa<IndirectBrInst>(PredBB->getTerminator()))
  69           // We cannot rewrite exiting edges from an indirectbr.
  70           return false;
  71         if (isa<CallBrInst>(PredBB->getTerminator()))
  72           // We cannot rewrite exiting edges from a callbr.
  73           return false;
  74
  75         InLoopPredecessors.push_back(PredBB);
  76       } else {
  77         IsDedicatedExit = false;
  78       }
  79
  80     assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
  81
  82     // Nothing to do if this is already a dedicated exit.
  83     if (IsDedicatedExit)
  84       return false;
  85
  86     auto *NewExitBB = SplitBlockPredecessors(
  87         BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
  88
  89     if (!NewExitBB)
  90       LLVM_DEBUG(
  91           dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
  92                  << *L << "\n");
  93     else
  94       LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
  95                         << NewExitBB->getName() << "\n");
  96     return true;
  97   };
  98
  99   // Walk the exit blocks directly rather than building up a data structure for
 100   // them, but only visit each one once.
 101   SmallPtrSet<BasicBlock *, 4> Visited;
 102   for (auto *BB : L->blocks())
 103     for (auto *SuccBB : successors(BB)) {
 104       // We're looking for exit blocks so skip in-loop successors.
 105       if (L->contains(SuccBB))
 106         continue;
 107
 108       // Visit each exit block exactly once.
 109       if (!Visited.insert(SuccBB).second)
 110         continue;
 111
 112       Changed |= RewriteExit(SuccBB);
 113     }
 114
 115   return Changed;
 116 }
 117
 118 /// Returns the instructions that use values defined in the loop.
 119 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
 120   SmallVector<Instruction *, 8> UsedOutside;
 121
 122   for (auto *Block : L->getBlocks())
 123     // FIXME: I believe that this could use copy_if if the Inst reference could
 124     // be adapted into a pointer.
 125     for (auto &Inst : *Block) {
 126       auto Users = Inst.users();
 127       if (any_of(Users, [&](User *U) {
 128             auto *Use = cast<Instruction>(U);
 129             return !L->contains(Use->getParent());
 130           }))
 131         UsedOutside.push_back(&Inst);
 132     }
 133
 134   return UsedOutside;
 135 }
 136
 137 void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
 138   // By definition, all loop passes need the LoopInfo analysis and the
 139   // Dominator tree it depends on. Because they all participate in the loop
 140   // pass manager, they must also preserve these.
 141   AU.addRequired<DominatorTreeWrapperPass>();
 142   AU.addPreserved<DominatorTreeWrapperPass>();
 143   AU.addRequired<LoopInfoWrapperPass>();
 144   AU.addPreserved<LoopInfoWrapperPass>();
 145
 146   // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
 147   // here because users shouldn't directly get them from this header.
 148   extern char &LoopSimplifyID;
 149   extern char &LCSSAID;
 150   AU.addRequiredID(LoopSimplifyID);
 151   AU.addPreservedID(LoopSimplifyID);
 152   AU.addRequiredID(LCSSAID);
 153   AU.addPreservedID(LCSSAID);
 154   // This is used in the LPPassManager to perform LCSSA verification on passes
 155   // which preserve lcssa form
 156   AU.addRequired<LCSSAVerificationPass>();
 157   AU.addPreserved<LCSSAVerificationPass>();
 158
 159   // Loop passes are designed to run inside of a loop pass manager which means
 160   // that any function analyses they require must be required by the first loop
 161   // pass in the manager (so that it is computed before the loop pass manager
 162   // runs) and preserved by all loop pasess in the manager. To make this
 163   // reasonably robust, the set needed for most loop passes is maintained here.
 164   // If your loop pass requires an analysis not listed here, you will need to
 165   // carefully audit the loop pass manager nesting structure that results.
 166   AU.addRequired<AAResultsWrapperPass>();
 167   AU.addPreserved<AAResultsWrapperPass>();
 168   AU.addPreserved<BasicAAWrapperPass>();
 169   AU.addPreserved<GlobalsAAWrapperPass>();
 170   AU.addPreserved<SCEVAAWrapperPass>();
 171   AU.addRequired<ScalarEvolutionWrapperPass>();
 172   AU.addPreserved<ScalarEvolutionWrapperPass>();
 173 }
 174
 175 /// Manually defined generic "LoopPass" dependency initialization. This is used
 176 /// to initialize the exact set of passes from above in \c
 177 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
 178 /// with:
 179 ///
 180 ///   INITIALIZE_PASS_DEPENDENCY(LoopPass)
 181 ///
 182 /// As-if "LoopPass" were a pass.
 183 void llvm::initializeLoopPassPass(PassRegistry &Registry) {
 184   INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 185   INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 186   INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 187   INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 188   INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 189   INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
 190   INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 191   INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 192   INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 193 }
 194
 195 /// Create MDNode for input string.
 196 static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
 197   LLVMContext &Context = TheLoop->getHeader()->getContext();
 198   Metadata *MDs[] = {
 199       MDString::get(Context, Name),
 200       ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))};
 201   return MDNode::get(Context, MDs);
 202 }
 203
 204 /// Set input string into loop metadata by keeping other values intact.
 205 /// If the string is already in loop metadata update value if it is
 206 /// different.
 207 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD,
 208                                    unsigned V) {
 209   SmallVector<Metadata *, 4> MDs(1);
 210   // If the loop already has metadata, retain it.
 211   MDNode *LoopID = TheLoop->getLoopID();
 212   if (LoopID) {
 213     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
 214       MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
 215       // If it is of form key = value, try to parse it.
 216       if (Node->getNumOperands() == 2) {
 217         MDString *S = dyn_cast<MDString>(Node->getOperand(0));
 218         if (S && S->getString().equals(StringMD)) {
 219           ConstantInt *IntMD =
 220               mdconst::extract_or_null<ConstantInt>(Node->getOperand(1));
 221           if (IntMD && IntMD->getSExtValue() == V)
 222             // It is already in place. Do nothing.
 223             return;
 224           // We need to update the value, so just skip it here and it will
 225           // be added after copying other existed nodes.
 226           continue;
 227         }
 228       }
 229       MDs.push_back(Node);
 230     }
 231   }
 232   // Add new metadata.
 233   MDs.push_back(createStringMetadata(TheLoop, StringMD, V));
 234   // Replace current metadata node with new one.
 235   LLVMContext &Context = TheLoop->getHeader()->getContext();
 236   MDNode *NewLoopID = MDNode::get(Context, MDs);
 237   // Set operand 0 to refer to the loop id itself.
 238   NewLoopID->replaceOperandWith(0, NewLoopID);
 239   TheLoop->setLoopID(NewLoopID);
 240 }
 241
 242 /// Find string metadata for loop
 243 ///
 244 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
 245 /// operand or null otherwise.  If the string metadata is not found return
 246 /// Optional's not-a-value.
 247 Optional<const MDOperand *> llvm::findStringMetadataForLoop(const Loop *TheLoop,
 248                                                             StringRef Name) {
 249   MDNode *MD = findOptionMDForLoop(TheLoop, Name);
 250   if (!MD)
 251     return None;
 252   switch (MD->getNumOperands()) {
 253   case 1:
 254     return nullptr;
 255   case 2:
 256     return &MD->getOperand(1);
 257   default:
 258     llvm_unreachable("loop metadata has 0 or 1 operand");
 259   }
 260 }
 261
 262 static Optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop,
 263                                                    StringRef Name) {
 264   MDNode *MD = findOptionMDForLoop(TheLoop, Name);
 265   if (!MD)
 266     return None;
 267   switch (MD->getNumOperands()) {
 268   case 1:
 269     // When the value is absent it is interpreted as 'attribute set'.
 270     return true;
 271   case 2:
 272     if (ConstantInt *IntMD =
 273             mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
 274       return IntMD->getZExtValue();
 275     return true;
 276   }
 277   llvm_unreachable("unexpected number of options");
 278 }
 279
 280 static bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
 281   return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
 282 }
 283
 284 llvm::Optional<int> llvm::getOptionalIntLoopAttribute(Loop *TheLoop,
 285                                                       StringRef Name) {
 286   const MDOperand *AttrMD =
 287       findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
 288   if (!AttrMD)
 289     return None;
 290
 291   ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
 292   if (!IntMD)
 293     return None;
 294
 295   return IntMD->getSExtValue();
 296 }
 297
 298 Optional<MDNode *> llvm::makeFollowupLoopID(
 299     MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
 300     const char *InheritOptionsExceptPrefix, bool AlwaysNew) {
 301   if (!OrigLoopID) {
 302     if (AlwaysNew)
 303       return nullptr;
 304     return None;
 305   }
 306
 307   assert(OrigLoopID->getOperand(0) == OrigLoopID);
 308
 309   bool InheritAllAttrs = !InheritOptionsExceptPrefix;
 310   bool InheritSomeAttrs =
 311       InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0';
 312   SmallVector<Metadata *, 8> MDs;
 313   MDs.push_back(nullptr);
 314
 315   bool Changed = false;
 316   if (InheritAllAttrs || InheritSomeAttrs) {
 317     for (const MDOperand &Existing : drop_begin(OrigLoopID->operands(), 1)) {
 318       MDNode *Op = cast<MDNode>(Existing.get());
 319
 320       auto InheritThisAttribute = [InheritSomeAttrs,
 321                                    InheritOptionsExceptPrefix](MDNode *Op) {
 322         if (!InheritSomeAttrs)
 323           return false;
 324
 325         // Skip malformatted attribute metadata nodes.
 326         if (Op->getNumOperands() == 0)
 327           return true;
 328         Metadata *NameMD = Op->getOperand(0).get();
 329         if (!isa<MDString>(NameMD))
 330           return true;
 331         StringRef AttrName = cast<MDString>(NameMD)->getString();
 332
 333         // Do not inherit excluded attributes.
 334         return !AttrName.startswith(InheritOptionsExceptPrefix);
 335       };
 336
 337       if (InheritThisAttribute(Op))
 338         MDs.push_back(Op);
 339       else
 340         Changed = true;
 341     }
 342   } else {
 343     // Modified if we dropped at least one attribute.
 344     Changed = OrigLoopID->getNumOperands() > 1;
 345   }
 346
 347   bool HasAnyFollowup = false;
 348   for (StringRef OptionName : FollowupOptions) {
 349     MDNode *FollowupNode = findOptionMDForLoopID(OrigLoopID, OptionName);
 350     if (!FollowupNode)
 351       continue;
 352
 353     HasAnyFollowup = true;
 354     for (const MDOperand &Option : drop_begin(FollowupNode->operands(), 1)) {
 355       MDs.push_back(Option.get());
 356       Changed = true;
 357     }
 358   }
 359
 360   // Attributes of the followup loop not specified explicity, so signal to the
 361   // transformation pass to add suitable attributes.
 362   if (!AlwaysNew && !HasAnyFollowup)
 363     return None;
 364
 365   // If no attributes were added or remove, the previous loop Id can be reused.
 366   if (!AlwaysNew && !Changed)
 367     return OrigLoopID;
 368
 369   // No attributes is equivalent to having no !llvm.loop metadata at all.
 370   if (MDs.size() == 1)
 371     return nullptr;
 372
 373   // Build the new loop ID.
 374   MDTuple *FollowupLoopID = MDNode::get(OrigLoopID->getContext(), MDs);
 375   FollowupLoopID->replaceOperandWith(0, FollowupLoopID);
 376   return FollowupLoopID;
 377 }
 378
 379 bool llvm::hasDisableAllTransformsHint(const Loop *L) {
 380   return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced);
 381 }
 382
 383 bool llvm::hasDisableLICMTransformsHint(const Loop *L) {
 384   return getBooleanLoopAttribute(L, LLVMLoopDisableLICM);
 385 }
 386
 387 TransformationMode llvm::hasUnrollTransformation(Loop *L) {
 388   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
 389     return TM_SuppressedByUser;
 390
 391   Optional<int> Count =
 392       getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
 393   if (Count.hasValue())
 394     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
 395
 396   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable"))
 397     return TM_ForcedByUser;
 398
 399   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.full"))
 400     return TM_ForcedByUser;
 401
 402   if (hasDisableAllTransformsHint(L))
 403     return TM_Disable;
 404
 405   return TM_Unspecified;
 406 }
 407
 408 TransformationMode llvm::hasUnrollAndJamTransformation(Loop *L) {
 409   if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.disable"))
 410     return TM_SuppressedByUser;
 411
 412   Optional<int> Count =
 413       getOptionalIntLoopAttribute(L, "llvm.loop.unroll_and_jam.count");
 414   if (Count.hasValue())
 415     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
 416
 417   if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.enable"))
 418     return TM_ForcedByUser;
 419
 420   if (hasDisableAllTransformsHint(L))
 421     return TM_Disable;
 422
 423   return TM_Unspecified;
 424 }
 425
 426 TransformationMode llvm::hasVectorizeTransformation(Loop *L) {
 427   Optional<bool> Enable =
 428       getOptionalBoolLoopAttribute(L, "llvm.loop.vectorize.enable");
 429
 430   if (Enable == false)
 431     return TM_SuppressedByUser;
 432
 433   Optional<int> VectorizeWidth =
 434       getOptionalIntLoopAttribute(L, "llvm.loop.vectorize.width");
 435   Optional<int> InterleaveCount =
 436       getOptionalIntLoopAttribute(L, "llvm.loop.interleave.count");
 437
 438   // 'Forcing' vector width and interleave count to one effectively disables
 439   // this tranformation.
 440   if (Enable == true && VectorizeWidth == 1 && InterleaveCount == 1)
 441     return TM_SuppressedByUser;
 442
 443   if (getBooleanLoopAttribute(L, "llvm.loop.isvectorized"))
 444     return TM_Disable;
 445
 446   if (Enable == true)
 447     return TM_ForcedByUser;
 448
 449   if (VectorizeWidth == 1 && InterleaveCount == 1)
 450     return TM_Disable;
 451
 452   if (VectorizeWidth > 1 || InterleaveCount > 1)
 453     return TM_Enable;
 454
 455   if (hasDisableAllTransformsHint(L))
 456     return TM_Disable;
 457
 458   return TM_Unspecified;
 459 }
 460
 461 TransformationMode llvm::hasDistributeTransformation(Loop *L) {
 462   if (getBooleanLoopAttribute(L, "llvm.loop.distribute.enable"))
 463     return TM_ForcedByUser;
 464
 465   if (hasDisableAllTransformsHint(L))
 466     return TM_Disable;
 467
 468   return TM_Unspecified;
 469 }
 470
 471 TransformationMode llvm::hasLICMVersioningTransformation(Loop *L) {
 472   if (getBooleanLoopAttribute(L, "llvm.loop.licm_versioning.disable"))
 473     return TM_SuppressedByUser;
 474
 475   if (hasDisableAllTransformsHint(L))
 476     return TM_Disable;
 477
 478   return TM_Unspecified;
 479 }
 480
 481 /// Does a BFS from a given node to all of its children inside a given loop.
 482 /// The returned vector of nodes includes the starting point.
 483 SmallVector<DomTreeNode *, 16>
 484 llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
 485   SmallVector<DomTreeNode *, 16> Worklist;
 486   auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
 487     // Only include subregions in the top level loop.
 488     BasicBlock *BB = DTN->getBlock();
 489     if (CurLoop->contains(BB))
 490       Worklist.push_back(DTN);
 491   };
 492
 493   AddRegionToWorklist(N);
 494
 495   for (size_t I = 0; I < Worklist.size(); I++)
 496     for (DomTreeNode *Child : Worklist[I]->getChildren())
 497       AddRegionToWorklist(Child);
 498
 499   return Worklist;
 500 }
 501
 502 void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
 503                           ScalarEvolution *SE = nullptr,
 504                           LoopInfo *LI = nullptr) {
 505   assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
 506   auto *Preheader = L->getLoopPreheader();
 507   assert(Preheader && "Preheader should exist!");
 508
 509   // Now that we know the removal is safe, remove the loop by changing the
 510   // branch from the preheader to go to the single exit block.
 511   //
 512   // Because we're deleting a large chunk of code at once, the sequence in which
 513   // we remove things is very important to avoid invalidation issues.
 514
 515   // Tell ScalarEvolution that the loop is deleted. Do this before
 516   // deleting the loop so that ScalarEvolution can look at the loop
 517   // to determine what it needs to clean up.
 518   if (SE)
 519     SE->forgetLoop(L);
 520
 521   auto *ExitBlock = L->getUniqueExitBlock();
 522   assert(ExitBlock && "Should have a unique exit block!");
 523   assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
 524
 525   auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
 526   assert(OldBr && "Preheader must end with a branch");
 527   assert(OldBr->isUnconditional() && "Preheader must have a single successor");
 528   // Connect the preheader to the exit block. Keep the old edge to the header
 529   // around to perform the dominator tree update in two separate steps
 530   // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
 531   // preheader -> header.
 532   //
 533   //
 534   // 0.  Preheader          1.  Preheader           2.  Preheader
 535   //        |                    |   |                   |
 536   //        V                    |   V                   |
 537   //      Header <--\            | Header <--\           | Header <--\
 538   //       |  |     |            |  |  |     |           |  |  |     |
 539   //       |  V     |            |  |  V     |           |  |  V     |
 540   //       | Body --/            |  | Body --/           |  | Body --/
 541   //       V                     V  V                    V  V
 542   //      Exit                   Exit                    Exit
 543   //
 544   // By doing this is two separate steps we can perform the dominator tree
 545   // update without using the batch update API.
 546   //
 547   // Even when the loop is never executed, we cannot remove the edge from the
 548   // source block to the exit block. Consider the case where the unexecuted loop
 549   // branches back to an outer loop. If we deleted the loop and removed the edge
 550   // coming to this inner loop, this will break the outer loop structure (by
 551   // deleting the backedge of the outer loop). If the outer loop is indeed a
 552   // non-loop, it will be deleted in a future iteration of loop deletion pass.
 553   IRBuilder<> Builder(OldBr);
 554   Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
 555   // Remove the old branch. The conditional branch becomes a new terminator.
 556   OldBr->eraseFromParent();
 557
 558   // Rewrite phis in the exit block to get their inputs from the Preheader
 559   // instead of the exiting block.
 560   for (PHINode &P : ExitBlock->phis()) {
 561     // Set the zero'th element of Phi to be from the preheader and remove all
 562     // other incoming values. Given the loop has dedicated exits, all other
 563     // incoming values must be from the exiting blocks.
 564     int PredIndex = 0;
 565     P.setIncomingBlock(PredIndex, Preheader);
 566     // Removes all incoming values from all other exiting blocks (including
 567     // duplicate values from an exiting block).
 568     // Nuke all entries except the zero'th entry which is the preheader entry.
 569     // NOTE! We need to remove Incoming Values in the reverse order as done
 570     // below, to keep the indices valid for deletion (removeIncomingValues
 571     // updates getNumIncomingValues and shifts all values down into the operand
 572     // being deleted).
 573     for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
 574       P.removeIncomingValue(e - i, false);
 575
 576     assert((P.getNumIncomingValues() == 1 &&
 577             P.getIncomingBlock(PredIndex) == Preheader) &&
 578            "Should have exactly one value and that's from the preheader!");
 579   }
 580
 581   // Disconnect the loop body by branching directly to its exit.
 582   Builder.SetInsertPoint(Preheader->getTerminator());
 583   Builder.CreateBr(ExitBlock);
 584   // Remove the old branch.
 585   Preheader->getTerminator()->eraseFromParent();
 586
 587   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 588   if (DT) {
 589     // Update the dominator tree by informing it about the new edge from the
 590     // preheader to the exit and the removed edge.
 591     DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock},
 592                       {DominatorTree::Delete, Preheader, L->getHeader()}});
 593   }
 594
 595   // Use a map to unique and a vector to guarantee deterministic ordering.
 596   llvm::SmallDenseSet<std::pair<DIVariable *, DIExpression *>, 4> DeadDebugSet;
 597   llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
 598
 599   // Given LCSSA form is satisfied, we should not have users of instructions
 600   // within the dead loop outside of the loop. However, LCSSA doesn't take
 601   // unreachable uses into account. We handle them here.
 602   // We could do it after drop all references (in this case all users in the
 603   // loop will be already eliminated and we have less work to do but according
 604   // to API doc of User::dropAllReferences only valid operation after dropping
 605   // references, is deletion. So let's substitute all usages of
 606   // instruction from the loop with undef value of corresponding type first.
 607   for (auto *Block : L->blocks())
 608     for (Instruction &I : *Block) {
 609       auto *Undef = UndefValue::get(I.getType());
 610       for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
 611         Use &U = *UI;
 612         ++UI;
 613         if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
 614           if (L->contains(Usr->getParent()))
 615             continue;
 616         // If we have a DT then we can check that uses outside a loop only in
 617         // unreachable block.
 618         if (DT)
 619           assert(!DT->isReachableFromEntry(U) &&
 620                  "Unexpected user in reachable block");
 621         U.set(Undef);
 622       }
 623       auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
 624       if (!DVI)
 625         continue;
 626       auto Key = DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()});
 627       if (Key != DeadDebugSet.end())
 628         continue;
 629       DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()});
 630       DeadDebugInst.push_back(DVI);
 631     }
 632
 633   // After the loop has been deleted all the values defined and modified
 634   // inside the loop are going to be unavailable.
 635   // Since debug values in the loop have been deleted, inserting an undef
 636   // dbg.value truncates the range of any dbg.value before the loop where the
 637   // loop used to be. This is particularly important for constant values.
 638   DIBuilder DIB(*ExitBlock->getModule());
 639   Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
 640   assert(InsertDbgValueBefore &&
 641          "There should be a non-PHI instruction in exit block, else these "
 642          "instructions will have no parent.");
 643   for (auto *DVI : DeadDebugInst)
 644     DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()),
 645                                 DVI->getVariable(), DVI->getExpression(),
 646                                 DVI->getDebugLoc(), InsertDbgValueBefore);
 647
 648   // Remove the block from the reference counting scheme, so that we can
 649   // delete it freely later.
 650   for (auto *Block : L->blocks())
 651     Block->dropAllReferences();
 652
 653   if (LI) {
 654     // Erase the instructions and the blocks without having to worry
 655     // about ordering because we already dropped the references.
 656     // NOTE: This iteration is safe because erasing the block does not remove
 657     // its entry from the loop's block list.  We do that in the next section.
 658     for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
 659          LpI != LpE; ++LpI)
 660       (*LpI)->eraseFromParent();
 661
 662     // Finally, the blocks from loopinfo.  This has to happen late because
 663     // otherwise our loop iterators won't work.
 664
 665     SmallPtrSet<BasicBlock *, 8> blocks;
 666     blocks.insert(L->block_begin(), L->block_end());
 667     for (BasicBlock *BB : blocks)
 668       LI->removeBlock(BB);
 669
 670     // The last step is to update LoopInfo now that we've eliminated this loop.
 671     LI->erase(L);
 672   }
 673 }
 674
 675 Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
 676   // Support loops with an exiting latch and other existing exists only
 677   // deoptimize.
 678
 679   // Get the branch weights for the loop's backedge.
 680   BasicBlock *Latch = L->getLoopLatch();
 681   if (!Latch)
 682     return None;
 683   BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
 684   if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
 685     return None;
 686
 687   assert((LatchBR->getSuccessor(0) == L->getHeader() ||
 688           LatchBR->getSuccessor(1) == L->getHeader()) &&
 689          "At least one edge out of the latch must go to the header");
 690
 691   SmallVector<BasicBlock *, 4> ExitBlocks;
 692   L->getUniqueNonLatchExitBlocks(ExitBlocks);
 693   if (any_of(ExitBlocks, [](const BasicBlock *EB) {
 694         return !EB->getTerminatingDeoptimizeCall();
 695       }))
 696     return None;
 697
 698   // To estimate the number of times the loop body was executed, we want to
 699   // know the number of times the backedge was taken, vs. the number of times
 700   // we exited the loop.
 701   uint64_t TrueVal, FalseVal;
 702   if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
 703     return None;
 704
 705   if (!TrueVal || !FalseVal)
 706     return 0;
 707
 708   // Divide the count of the backedge by the count of the edge exiting the loop,
 709   // rounding to nearest.
 710   if (LatchBR->getSuccessor(0) == L->getHeader())
 711     return (TrueVal + (FalseVal / 2)) / FalseVal;
 712   else
 713     return (FalseVal + (TrueVal / 2)) / TrueVal;
 714 }
 715
 716 bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop,
 717                                               ScalarEvolution &SE) {
 718   Loop *OuterL = InnerLoop->getParentLoop();
 719   if (!OuterL)
 720     return true;
 721
 722   // Get the backedge taken count for the inner loop
 723   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 724   const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
 725   if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
 726       !InnerLoopBECountSC->getType()->isIntegerTy())
 727     return false;
 728
 729   // Get whether count is invariant to the outer loop
 730   ScalarEvolution::LoopDisposition LD =
 731       SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
 732   if (LD != ScalarEvolution::LoopInvariant)
 733     return false;
 734
 735   return true;
 736 }
 737
 738 Value *llvm::createMinMaxOp(IRBuilder<> &Builder,
 739                             RecurrenceDescriptor::MinMaxRecurrenceKind RK,
 740                             Value *Left, Value *Right) {
 741   CmpInst::Predicate P = CmpInst::ICMP_NE;
 742   switch (RK) {
 743   default:
 744     llvm_unreachable("Unknown min/max recurrence kind");
 745   case RecurrenceDescriptor::MRK_UIntMin:
 746     P = CmpInst::ICMP_ULT;
 747     break;
 748   case RecurrenceDescriptor::MRK_UIntMax:
 749     P = CmpInst::ICMP_UGT;
 750     break;
 751   case RecurrenceDescriptor::MRK_SIntMin:
 752     P = CmpInst::ICMP_SLT;
 753     break;
 754   case RecurrenceDescriptor::MRK_SIntMax:
 755     P = CmpInst::ICMP_SGT;
 756     break;
 757   case RecurrenceDescriptor::MRK_FloatMin:
 758     P = CmpInst::FCMP_OLT;
 759     break;
 760   case RecurrenceDescriptor::MRK_FloatMax:
 761     P = CmpInst::FCMP_OGT;
 762     break;
 763   }
 764
 765   // We only match FP sequences that are 'fast', so we can unconditionally
 766   // set it on any generated instructions.
 767   IRBuilder<>::FastMathFlagGuard FMFG(Builder);
 768   FastMathFlags FMF;
 769   FMF.setFast();
 770   Builder.setFastMathFlags(FMF);
 771
 772   Value *Cmp;
 773   if (RK == RecurrenceDescriptor::MRK_FloatMin ||
 774       RK == RecurrenceDescriptor::MRK_FloatMax)
 775     Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
 776   else
 777     Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
 778
 779   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
 780   return Select;
 781 }
 782
 783 // Helper to generate an ordered reduction.
 784 Value *
 785 llvm::getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src,
 786                           unsigned Op,
 787                           RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
 788                           ArrayRef<Value *> RedOps) {
 789   unsigned VF = Src->getType()->getVectorNumElements();
 790
 791   // Extract and apply reduction ops in ascending order:
 792   // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
 793   Value *Result = Acc;
 794   for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
 795     Value *Ext =
 796         Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
 797
 798     if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
 799       Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
 800                                    "bin.rdx");
 801     } else {
 802       assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
 803              "Invalid min/max");
 804       Result = createMinMaxOp(Builder, MinMaxKind, Result, Ext);
 805     }
 806
 807     if (!RedOps.empty())
 808       propagateIRFlags(Result, RedOps);
 809   }
 810
 811   return Result;
 812 }
 813
 814 // Helper to generate a log2 shuffle reduction.
 815 Value *
 816 llvm::getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
 817                           RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
 818                           ArrayRef<Value *> RedOps) {
 819   unsigned VF = Src->getType()->getVectorNumElements();
 820   // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
 821   // and vector ops, reducing the set of values being computed by half each
 822   // round.
 823   assert(isPowerOf2_32(VF) &&
 824          "Reduction emission only supported for pow2 vectors!");
 825   Value *TmpVec = Src;
 826   SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
 827   for (unsigned i = VF; i != 1; i >>= 1) {
 828     // Move the upper half of the vector to the lower half.
 829     for (unsigned j = 0; j != i / 2; ++j)
 830       ShuffleMask[j] = Builder.getInt32(i / 2 + j);
 831
 832     // Fill the rest of the mask with undef.
 833     std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
 834               UndefValue::get(Builder.getInt32Ty()));
 835
 836     Value *Shuf = Builder.CreateShuffleVector(
 837         TmpVec, UndefValue::get(TmpVec->getType()),
 838         ConstantVector::get(ShuffleMask), "rdx.shuf");
 839
 840     if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
 841       // The builder propagates its fast-math-flags setting.
 842       TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
 843                                    "bin.rdx");
 844     } else {
 845       assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
 846              "Invalid min/max");
 847       TmpVec = createMinMaxOp(Builder, MinMaxKind, TmpVec, Shuf);
 848     }
 849     if (!RedOps.empty())
 850       propagateIRFlags(TmpVec, RedOps);
 851   }
 852   // The result is in the first element of the vector.
 853   return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
 854 }
 855
 856 /// Create a simple vector reduction specified by an opcode and some
 857 /// flags (if generating min/max reductions).
 858 Value *llvm::createSimpleTargetReduction(
 859     IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
 860     Value *Src, TargetTransformInfo::ReductionFlags Flags,
 861     ArrayRef<Value *> RedOps) {
 862   assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
 863
 864   std::function<Value *()> BuildFunc;
 865   using RD = RecurrenceDescriptor;
 866   RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
 867
 868   switch (Opcode) {
 869   case Instruction::Add:
 870     BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
 871     break;
 872   case Instruction::Mul:
 873     BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
 874     break;
 875   case Instruction::And:
 876     BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
 877     break;
 878   case Instruction::Or:
 879     BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
 880     break;
 881   case Instruction::Xor:
 882     BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
 883     break;
 884   case Instruction::FAdd:
 885     BuildFunc = [&]() {
 886       auto Rdx = Builder.CreateFAddReduce(
 887           Constant::getNullValue(Src->getType()->getVectorElementType()), Src);
 888       return Rdx;
 889     };
 890     break;
 891   case Instruction::FMul:
 892     BuildFunc = [&]() {
 893       Type *Ty = Src->getType()->getVectorElementType();
 894       auto Rdx = Builder.CreateFMulReduce(ConstantFP::get(Ty, 1.0), Src);
 895       return Rdx;
 896     };
 897     break;
 898   case Instruction::ICmp:
 899     if (Flags.IsMaxOp) {
 900       MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
 901       BuildFunc = [&]() {
 902         return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
 903       };
 904     } else {
 905       MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
 906       BuildFunc = [&]() {
 907         return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
 908       };
 909     }
 910     break;
 911   case Instruction::FCmp:
 912     if (Flags.IsMaxOp) {
 913       MinMaxKind = RD::MRK_FloatMax;
 914       BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
 915     } else {
 916       MinMaxKind = RD::MRK_FloatMin;
 917       BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
 918     }
 919     break;
 920   default:
 921     llvm_unreachable("Unhandled opcode");
 922     break;
 923   }
 924   if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
 925     return BuildFunc();
 926   return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
 927 }
 928
 929 /// Create a vector reduction using a given recurrence descriptor.
 930 Value *llvm::createTargetReduction(IRBuilder<> &B,
 931                                    const TargetTransformInfo *TTI,
 932                                    RecurrenceDescriptor &Desc, Value *Src,
 933                                    bool NoNaN) {
 934   // TODO: Support in-order reductions based on the recurrence descriptor.
 935   using RD = RecurrenceDescriptor;
 936   RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
 937   TargetTransformInfo::ReductionFlags Flags;
 938   Flags.NoNaN = NoNaN;
 939
 940   // All ops in the reduction inherit fast-math-flags from the recurrence
 941   // descriptor.
 942   IRBuilder<>::FastMathFlagGuard FMFGuard(B);
 943   B.setFastMathFlags(Desc.getFastMathFlags());
 944
 945   switch (RecKind) {
 946   case RD::RK_FloatAdd:
 947     return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
 948   case RD::RK_FloatMult:
 949     return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
 950   case RD::RK_IntegerAdd:
 951     return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
 952   case RD::RK_IntegerMult:
 953     return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
 954   case RD::RK_IntegerAnd:
 955     return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
 956   case RD::RK_IntegerOr:
 957     return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
 958   case RD::RK_IntegerXor:
 959     return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
 960   case RD::RK_IntegerMinMax: {
 961     RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
 962     Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
 963     Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
 964     return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
 965   }
 966   case RD::RK_FloatMinMax: {
 967     Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
 968     return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
 969   }
 970   default:
 971     llvm_unreachable("Unhandled RecKind");
 972   }
 973 }
 974
 975 void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) {
 976   auto *VecOp = dyn_cast<Instruction>(I);
 977   if (!VecOp)
 978     return;
 979   auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
 980                                             : dyn_cast<Instruction>(OpValue);
 981   if (!Intersection)
 982     return;
 983   const unsigned Opcode = Intersection->getOpcode();
 984   VecOp->copyIRFlags(Intersection);
 985   for (auto *V : VL) {
 986     auto *Instr = dyn_cast<Instruction>(V);
 987     if (!Instr)
 988       continue;
 989     if (OpValue == nullptr || Opcode == Instr->getOpcode())
 990       VecOp->andIRFlags(V);
 991   }
 992 }
 993
 994 bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
 995                                  ScalarEvolution &SE) {
 996   const SCEV *Zero = SE.getZero(S->getType());
 997   return SE.isAvailableAtLoopEntry(S, L) &&
 998          SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, S, Zero);
 999 }
1000
1001 bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
1002                                     ScalarEvolution &SE) {
1003   const SCEV *Zero = SE.getZero(S->getType());
1004   return SE.isAvailableAtLoopEntry(S, L) &&
1005          SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero);
1006 }
1007
1008 bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1009                              bool Signed) {
1010   unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1011   APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) :
1012     APInt::getMinValue(BitWidth);
1013   auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1014   return SE.isAvailableAtLoopEntry(S, L) &&
1015          SE.isLoopEntryGuardedByCond(L, Predicate, S,
1016                                      SE.getConstant(Min));
1017 }
1018
1019 bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1020                              bool Signed) {
1021   unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1022   APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
1023     APInt::getMaxValue(BitWidth);
1024   auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1025   return SE.isAvailableAtLoopEntry(S, L) &&
1026          SE.isLoopEntryGuardedByCond(L, Predicate, S,
1027                                      SE.getConstant(Max));
1028 }