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