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