lib/Analysis/LoopInfo.cpp

   1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
   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 the LoopInfo class that is used to identify natural loops
  10 // and determine the loop depth of various nodes of the CFG.  Note that the
  11 // loops identified may actually be several natural loops that share the same
  12 // header node... not just a single natural loop.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Analysis/LoopInfo.h"
  17 #include "llvm/ADT/DepthFirstIterator.h"
  18 #include "llvm/ADT/ScopeExit.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/Analysis/LoopInfoImpl.h"
  21 #include "llvm/Analysis/LoopIterator.h"
  22 #include "llvm/Analysis/ValueTracking.h"
  23 #include "llvm/Config/llvm-config.h"
  24 #include "llvm/IR/CFG.h"
  25 #include "llvm/IR/Constants.h"
  26 #include "llvm/IR/DebugLoc.h"
  27 #include "llvm/IR/Dominators.h"
  28 #include "llvm/IR/IRPrintingPasses.h"
  29 #include "llvm/IR/Instructions.h"
  30 #include "llvm/IR/LLVMContext.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/PassManager.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include <algorithm>
  37 using namespace llvm;
  38
  39 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
  40 template class llvm::LoopBase<BasicBlock, Loop>;
  41 template class llvm::LoopInfoBase<BasicBlock, Loop>;
  42
  43 // Always verify loopinfo if expensive checking is enabled.
  44 #ifdef EXPENSIVE_CHECKS
  45 bool llvm::VerifyLoopInfo = true;
  46 #else
  47 bool llvm::VerifyLoopInfo = false;
  48 #endif
  49 static cl::opt<bool, true>
  50     VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
  51                     cl::Hidden, cl::desc("Verify loop info (time consuming)"));
  52
  53 //===----------------------------------------------------------------------===//
  54 // Loop implementation
  55 //
  56
  57 bool Loop::isLoopInvariant(const Value *V) const {
  58   if (const Instruction *I = dyn_cast<Instruction>(V))
  59     return !contains(I);
  60   return true; // All non-instructions are loop invariant
  61 }
  62
  63 bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
  64   return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
  65 }
  66
  67 bool Loop::makeLoopInvariant(Value *V, bool &Changed,
  68                              Instruction *InsertPt) const {
  69   if (Instruction *I = dyn_cast<Instruction>(V))
  70     return makeLoopInvariant(I, Changed, InsertPt);
  71   return true; // All non-instructions are loop-invariant.
  72 }
  73
  74 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
  75                              Instruction *InsertPt) const {
  76   // Test if the value is already loop-invariant.
  77   if (isLoopInvariant(I))
  78     return true;
  79   if (!isSafeToSpeculativelyExecute(I))
  80     return false;
  81   if (I->mayReadFromMemory())
  82     return false;
  83   // EH block instructions are immobile.
  84   if (I->isEHPad())
  85     return false;
  86   // Determine the insertion point, unless one was given.
  87   if (!InsertPt) {
  88     BasicBlock *Preheader = getLoopPreheader();
  89     // Without a preheader, hoisting is not feasible.
  90     if (!Preheader)
  91       return false;
  92     InsertPt = Preheader->getTerminator();
  93   }
  94   // Don't hoist instructions with loop-variant operands.
  95   for (Value *Operand : I->operands())
  96     if (!makeLoopInvariant(Operand, Changed, InsertPt))
  97       return false;
  98
  99   // Hoist.
 100   I->moveBefore(InsertPt);
 101
 102   // There is possibility of hoisting this instruction above some arbitrary
 103   // condition. Any metadata defined on it can be control dependent on this
 104   // condition. Conservatively strip it here so that we don't give any wrong
 105   // information to the optimizer.
 106   I->dropUnknownNonDebugMetadata();
 107
 108   Changed = true;
 109   return true;
 110 }
 111
 112 bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
 113                                   BasicBlock *&Backedge) const {
 114   BasicBlock *H = getHeader();
 115
 116   Incoming = nullptr;
 117   Backedge = nullptr;
 118   pred_iterator PI = pred_begin(H);
 119   assert(PI != pred_end(H) && "Loop must have at least one backedge!");
 120   Backedge = *PI++;
 121   if (PI == pred_end(H))
 122     return false; // dead loop
 123   Incoming = *PI++;
 124   if (PI != pred_end(H))
 125     return false; // multiple backedges?
 126
 127   if (contains(Incoming)) {
 128     if (contains(Backedge))
 129       return false;
 130     std::swap(Incoming, Backedge);
 131   } else if (!contains(Backedge))
 132     return false;
 133
 134   assert(Incoming && Backedge && "expected non-null incoming and backedges");
 135   return true;
 136 }
 137
 138 PHINode *Loop::getCanonicalInductionVariable() const {
 139   BasicBlock *H = getHeader();
 140
 141   BasicBlock *Incoming = nullptr, *Backedge = nullptr;
 142   if (!getIncomingAndBackEdge(Incoming, Backedge))
 143     return nullptr;
 144
 145   // Loop over all of the PHI nodes, looking for a canonical indvar.
 146   for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
 147     PHINode *PN = cast<PHINode>(I);
 148     if (ConstantInt *CI =
 149             dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
 150       if (CI->isZero())
 151         if (Instruction *Inc =
 152                 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
 153           if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
 154             if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
 155               if (CI->isOne())
 156                 return PN;
 157   }
 158   return nullptr;
 159 }
 160
 161 // Check that 'BB' doesn't have any uses outside of the 'L'
 162 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
 163                                DominatorTree &DT) {
 164   for (const Instruction &I : BB) {
 165     // Tokens can't be used in PHI nodes and live-out tokens prevent loop
 166     // optimizations, so for the purposes of considered LCSSA form, we
 167     // can ignore them.
 168     if (I.getType()->isTokenTy())
 169       continue;
 170
 171     for (const Use &U : I.uses()) {
 172       const Instruction *UI = cast<Instruction>(U.getUser());
 173       const BasicBlock *UserBB = UI->getParent();
 174       if (const PHINode *P = dyn_cast<PHINode>(UI))
 175         UserBB = P->getIncomingBlock(U);
 176
 177       // Check the current block, as a fast-path, before checking whether
 178       // the use is anywhere in the loop.  Most values are used in the same
 179       // block they are defined in.  Also, blocks not reachable from the
 180       // entry are special; uses in them don't need to go through PHIs.
 181       if (UserBB != &BB && !L.contains(UserBB) &&
 182           DT.isReachableFromEntry(UserBB))
 183         return false;
 184     }
 185   }
 186   return true;
 187 }
 188
 189 bool Loop::isLCSSAForm(DominatorTree &DT) const {
 190   // For each block we check that it doesn't have any uses outside of this loop.
 191   return all_of(this->blocks(), [&](const BasicBlock *BB) {
 192     return isBlockInLCSSAForm(*this, *BB, DT);
 193   });
 194 }
 195
 196 bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const {
 197   // For each block we check that it doesn't have any uses outside of its
 198   // innermost loop. This process will transitively guarantee that the current
 199   // loop and all of the nested loops are in LCSSA form.
 200   return all_of(this->blocks(), [&](const BasicBlock *BB) {
 201     return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
 202   });
 203 }
 204
 205 bool Loop::isLoopSimplifyForm() const {
 206   // Normal-form loops have a preheader, a single backedge, and all of their
 207   // exits have all their predecessors inside the loop.
 208   return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
 209 }
 210
 211 // Routines that reform the loop CFG and split edges often fail on indirectbr.
 212 bool Loop::isSafeToClone() const {
 213   // Return false if any loop blocks contain indirectbrs, or there are any calls
 214   // to noduplicate functions.
 215   for (BasicBlock *BB : this->blocks()) {
 216     if (isa<IndirectBrInst>(BB->getTerminator()))
 217       return false;
 218
 219     for (Instruction &I : *BB)
 220       if (auto CS = CallSite(&I))
 221         if (CS.cannotDuplicate())
 222           return false;
 223   }
 224   return true;
 225 }
 226
 227 MDNode *Loop::getLoopID() const {
 228   MDNode *LoopID = nullptr;
 229
 230   // Go through the latch blocks and check the terminator for the metadata.
 231   SmallVector<BasicBlock *, 4> LatchesBlocks;
 232   getLoopLatches(LatchesBlocks);
 233   for (BasicBlock *BB : LatchesBlocks) {
 234     Instruction *TI = BB->getTerminator();
 235     MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
 236
 237     if (!MD)
 238       return nullptr;
 239
 240     if (!LoopID)
 241       LoopID = MD;
 242     else if (MD != LoopID)
 243       return nullptr;
 244   }
 245   if (!LoopID || LoopID->getNumOperands() == 0 ||
 246       LoopID->getOperand(0) != LoopID)
 247     return nullptr;
 248   return LoopID;
 249 }
 250
 251 void Loop::setLoopID(MDNode *LoopID) const {
 252   assert((!LoopID || LoopID->getNumOperands() > 0) &&
 253          "Loop ID needs at least one operand");
 254   assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
 255          "Loop ID should refer to itself");
 256
 257   SmallVector<BasicBlock *, 4> LoopLatches;
 258   getLoopLatches(LoopLatches);
 259   for (BasicBlock *BB : LoopLatches)
 260     BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
 261 }
 262
 263 void Loop::setLoopAlreadyUnrolled() {
 264   LLVMContext &Context = getHeader()->getContext();
 265
 266   MDNode *DisableUnrollMD =
 267       MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
 268   MDNode *LoopID = getLoopID();
 269   MDNode *NewLoopID = makePostTransformationMetadata(
 270       Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
 271   setLoopID(NewLoopID);
 272 }
 273
 274 bool Loop::isAnnotatedParallel() const {
 275   MDNode *DesiredLoopIdMetadata = getLoopID();
 276
 277   if (!DesiredLoopIdMetadata)
 278     return false;
 279
 280   MDNode *ParallelAccesses =
 281       findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
 282   SmallPtrSet<MDNode *, 4>
 283       ParallelAccessGroups; // For scalable 'contains' check.
 284   if (ParallelAccesses) {
 285     for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
 286       MDNode *AccGroup = cast<MDNode>(MD.get());
 287       assert(isValidAsAccessGroup(AccGroup) &&
 288              "List item must be an access group");
 289       ParallelAccessGroups.insert(AccGroup);
 290     }
 291   }
 292
 293   // The loop branch contains the parallel loop metadata. In order to ensure
 294   // that any parallel-loop-unaware optimization pass hasn't added loop-carried
 295   // dependencies (thus converted the loop back to a sequential loop), check
 296   // that all the memory instructions in the loop belong to an access group that
 297   // is parallel to this loop.
 298   for (BasicBlock *BB : this->blocks()) {
 299     for (Instruction &I : *BB) {
 300       if (!I.mayReadOrWriteMemory())
 301         continue;
 302
 303       if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
 304         auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
 305           if (AG->getNumOperands() == 0) {
 306             assert(isValidAsAccessGroup(AG) && "Item must be an access group");
 307             return ParallelAccessGroups.count(AG);
 308           }
 309
 310           for (const MDOperand &AccessListItem : AG->operands()) {
 311             MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
 312             assert(isValidAsAccessGroup(AccGroup) &&
 313                    "List item must be an access group");
 314             if (ParallelAccessGroups.count(AccGroup))
 315               return true;
 316           }
 317           return false;
 318         };
 319
 320         if (ContainsAccessGroup(AccessGroup))
 321           continue;
 322       }
 323
 324       // The memory instruction can refer to the loop identifier metadata
 325       // directly or indirectly through another list metadata (in case of
 326       // nested parallel loops). The loop identifier metadata refers to
 327       // itself so we can check both cases with the same routine.
 328       MDNode *LoopIdMD =
 329           I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
 330
 331       if (!LoopIdMD)
 332         return false;
 333
 334       bool LoopIdMDFound = false;
 335       for (const MDOperand &MDOp : LoopIdMD->operands()) {
 336         if (MDOp == DesiredLoopIdMetadata) {
 337           LoopIdMDFound = true;
 338           break;
 339         }
 340       }
 341
 342       if (!LoopIdMDFound)
 343         return false;
 344     }
 345   }
 346   return true;
 347 }
 348
 349 DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
 350
 351 Loop::LocRange Loop::getLocRange() const {
 352   // If we have a debug location in the loop ID, then use it.
 353   if (MDNode *LoopID = getLoopID()) {
 354     DebugLoc Start;
 355     // We use the first DebugLoc in the header as the start location of the loop
 356     // and if there is a second DebugLoc in the header we use it as end location
 357     // of the loop.
 358     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
 359       if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
 360         if (!Start)
 361           Start = DebugLoc(L);
 362         else
 363           return LocRange(Start, DebugLoc(L));
 364       }
 365     }
 366
 367     if (Start)
 368       return LocRange(Start);
 369   }
 370
 371   // Try the pre-header first.
 372   if (BasicBlock *PHeadBB = getLoopPreheader())
 373     if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
 374       return LocRange(DL);
 375
 376   // If we have no pre-header or there are no instructions with debug
 377   // info in it, try the header.
 378   if (BasicBlock *HeadBB = getHeader())
 379     return LocRange(HeadBB->getTerminator()->getDebugLoc());
 380
 381   return LocRange();
 382 }
 383
 384 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 385 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
 386
 387 LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
 388   print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
 389 }
 390 #endif
 391
 392 //===----------------------------------------------------------------------===//
 393 // UnloopUpdater implementation
 394 //
 395
 396 namespace {
 397 /// Find the new parent loop for all blocks within the "unloop" whose last
 398 /// backedges has just been removed.
 399 class UnloopUpdater {
 400   Loop &Unloop;
 401   LoopInfo *LI;
 402
 403   LoopBlocksDFS DFS;
 404
 405   // Map unloop's immediate subloops to their nearest reachable parents. Nested
 406   // loops within these subloops will not change parents. However, an immediate
 407   // subloop's new parent will be the nearest loop reachable from either its own
 408   // exits *or* any of its nested loop's exits.
 409   DenseMap<Loop *, Loop *> SubloopParents;
 410
 411   // Flag the presence of an irreducible backedge whose destination is a block
 412   // directly contained by the original unloop.
 413   bool FoundIB;
 414
 415 public:
 416   UnloopUpdater(Loop *UL, LoopInfo *LInfo)
 417       : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
 418
 419   void updateBlockParents();
 420
 421   void removeBlocksFromAncestors();
 422
 423   void updateSubloopParents();
 424
 425 protected:
 426   Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
 427 };
 428 } // end anonymous namespace
 429
 430 /// Update the parent loop for all blocks that are directly contained within the
 431 /// original "unloop".
 432 void UnloopUpdater::updateBlockParents() {
 433   if (Unloop.getNumBlocks()) {
 434     // Perform a post order CFG traversal of all blocks within this loop,
 435     // propagating the nearest loop from successors to predecessors.
 436     LoopBlocksTraversal Traversal(DFS, LI);
 437     for (BasicBlock *POI : Traversal) {
 438
 439       Loop *L = LI->getLoopFor(POI);
 440       Loop *NL = getNearestLoop(POI, L);
 441
 442       if (NL != L) {
 443         // For reducible loops, NL is now an ancestor of Unloop.
 444         assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
 445                "uninitialized successor");
 446         LI->changeLoopFor(POI, NL);
 447       } else {
 448         // Or the current block is part of a subloop, in which case its parent
 449         // is unchanged.
 450         assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
 451       }
 452     }
 453   }
 454   // Each irreducible loop within the unloop induces a round of iteration using
 455   // the DFS result cached by Traversal.
 456   bool Changed = FoundIB;
 457   for (unsigned NIters = 0; Changed; ++NIters) {
 458     assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
 459
 460     // Iterate over the postorder list of blocks, propagating the nearest loop
 461     // from successors to predecessors as before.
 462     Changed = false;
 463     for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
 464                                    POE = DFS.endPostorder();
 465          POI != POE; ++POI) {
 466
 467       Loop *L = LI->getLoopFor(*POI);
 468       Loop *NL = getNearestLoop(*POI, L);
 469       if (NL != L) {
 470         assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
 471                "uninitialized successor");
 472         LI->changeLoopFor(*POI, NL);
 473         Changed = true;
 474       }
 475     }
 476   }
 477 }
 478
 479 /// Remove unloop's blocks from all ancestors below their new parents.
 480 void UnloopUpdater::removeBlocksFromAncestors() {
 481   // Remove all unloop's blocks (including those in nested subloops) from
 482   // ancestors below the new parent loop.
 483   for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
 484        BI != BE; ++BI) {
 485     Loop *OuterParent = LI->getLoopFor(*BI);
 486     if (Unloop.contains(OuterParent)) {
 487       while (OuterParent->getParentLoop() != &Unloop)
 488         OuterParent = OuterParent->getParentLoop();
 489       OuterParent = SubloopParents[OuterParent];
 490     }
 491     // Remove blocks from former Ancestors except Unloop itself which will be
 492     // deleted.
 493     for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
 494          OldParent = OldParent->getParentLoop()) {
 495       assert(OldParent && "new loop is not an ancestor of the original");
 496       OldParent->removeBlockFromLoop(*BI);
 497     }
 498   }
 499 }
 500
 501 /// Update the parent loop for all subloops directly nested within unloop.
 502 void UnloopUpdater::updateSubloopParents() {
 503   while (!Unloop.empty()) {
 504     Loop *Subloop = *std::prev(Unloop.end());
 505     Unloop.removeChildLoop(std::prev(Unloop.end()));
 506
 507     assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
 508     if (Loop *Parent = SubloopParents[Subloop])
 509       Parent->addChildLoop(Subloop);
 510     else
 511       LI->addTopLevelLoop(Subloop);
 512   }
 513 }
 514
 515 /// Return the nearest parent loop among this block's successors. If a successor
 516 /// is a subloop header, consider its parent to be the nearest parent of the
 517 /// subloop's exits.
 518 ///
 519 /// For subloop blocks, simply update SubloopParents and return NULL.
 520 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
 521
 522   // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
 523   // is considered uninitialized.
 524   Loop *NearLoop = BBLoop;
 525
 526   Loop *Subloop = nullptr;
 527   if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
 528     Subloop = NearLoop;
 529     // Find the subloop ancestor that is directly contained within Unloop.
 530     while (Subloop->getParentLoop() != &Unloop) {
 531       Subloop = Subloop->getParentLoop();
 532       assert(Subloop && "subloop is not an ancestor of the original loop");
 533     }
 534     // Get the current nearest parent of the Subloop exits, initially Unloop.
 535     NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
 536   }
 537
 538   succ_iterator I = succ_begin(BB), E = succ_end(BB);
 539   if (I == E) {
 540     assert(!Subloop && "subloop blocks must have a successor");
 541     NearLoop = nullptr; // unloop blocks may now exit the function.
 542   }
 543   for (; I != E; ++I) {
 544     if (*I == BB)
 545       continue; // self loops are uninteresting
 546
 547     Loop *L = LI->getLoopFor(*I);
 548     if (L == &Unloop) {
 549       // This successor has not been processed. This path must lead to an
 550       // irreducible backedge.
 551       assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
 552       FoundIB = true;
 553     }
 554     if (L != &Unloop && Unloop.contains(L)) {
 555       // Successor is in a subloop.
 556       if (Subloop)
 557         continue; // Branching within subloops. Ignore it.
 558
 559       // BB branches from the original into a subloop header.
 560       assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
 561
 562       // Get the current nearest parent of the Subloop's exits.
 563       L = SubloopParents[L];
 564       // L could be Unloop if the only exit was an irreducible backedge.
 565     }
 566     if (L == &Unloop) {
 567       continue;
 568     }
 569     // Handle critical edges from Unloop into a sibling loop.
 570     if (L && !L->contains(&Unloop)) {
 571       L = L->getParentLoop();
 572     }
 573     // Remember the nearest parent loop among successors or subloop exits.
 574     if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
 575       NearLoop = L;
 576   }
 577   if (Subloop) {
 578     SubloopParents[Subloop] = NearLoop;
 579     return BBLoop;
 580   }
 581   return NearLoop;
 582 }
 583
 584 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
 585
 586 bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
 587                           FunctionAnalysisManager::Invalidator &) {
 588   // Check whether the analysis, all analyses on functions, or the function's
 589   // CFG have been preserved.
 590   auto PAC = PA.getChecker<LoopAnalysis>();
 591   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
 592            PAC.preservedSet<CFGAnalyses>());
 593 }
 594
 595 void LoopInfo::erase(Loop *Unloop) {
 596   assert(!Unloop->isInvalid() && "Loop has already been erased!");
 597
 598   auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
 599
 600   // First handle the special case of no parent loop to simplify the algorithm.
 601   if (!Unloop->getParentLoop()) {
 602     // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
 603     for (Loop::block_iterator I = Unloop->block_begin(),
 604                               E = Unloop->block_end();
 605          I != E; ++I) {
 606
 607       // Don't reparent blocks in subloops.
 608       if (getLoopFor(*I) != Unloop)
 609         continue;
 610
 611       // Blocks no longer have a parent but are still referenced by Unloop until
 612       // the Unloop object is deleted.
 613       changeLoopFor(*I, nullptr);
 614     }
 615
 616     // Remove the loop from the top-level LoopInfo object.
 617     for (iterator I = begin();; ++I) {
 618       assert(I != end() && "Couldn't find loop");
 619       if (*I == Unloop) {
 620         removeLoop(I);
 621         break;
 622       }
 623     }
 624
 625     // Move all of the subloops to the top-level.
 626     while (!Unloop->empty())
 627       addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
 628
 629     return;
 630   }
 631
 632   // Update the parent loop for all blocks within the loop. Blocks within
 633   // subloops will not change parents.
 634   UnloopUpdater Updater(Unloop, this);
 635   Updater.updateBlockParents();
 636
 637   // Remove blocks from former ancestor loops.
 638   Updater.removeBlocksFromAncestors();
 639
 640   // Add direct subloops as children in their new parent loop.
 641   Updater.updateSubloopParents();
 642
 643   // Remove unloop from its parent loop.
 644   Loop *ParentLoop = Unloop->getParentLoop();
 645   for (Loop::iterator I = ParentLoop->begin();; ++I) {
 646     assert(I != ParentLoop->end() && "Couldn't find loop");
 647     if (*I == Unloop) {
 648       ParentLoop->removeChildLoop(I);
 649       break;
 650     }
 651   }
 652 }
 653
 654 AnalysisKey LoopAnalysis::Key;
 655
 656 LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
 657   // FIXME: Currently we create a LoopInfo from scratch for every function.
 658   // This may prove to be too wasteful due to deallocating and re-allocating
 659   // memory each time for the underlying map and vector datastructures. At some
 660   // point it may prove worthwhile to use a freelist and recycle LoopInfo
 661   // objects. I don't want to add that kind of complexity until the scope of
 662   // the problem is better understood.
 663   LoopInfo LI;
 664   LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
 665   return LI;
 666 }
 667
 668 PreservedAnalyses LoopPrinterPass::run(Function &F,
 669                                        FunctionAnalysisManager &AM) {
 670   AM.getResult<LoopAnalysis>(F).print(OS);
 671   return PreservedAnalyses::all();
 672 }
 673
 674 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
 675
 676   if (forcePrintModuleIR()) {
 677     // handling -print-module-scope
 678     OS << Banner << " (loop: ";
 679     L.getHeader()->printAsOperand(OS, false);
 680     OS << ")\n";
 681
 682     // printing whole module
 683     OS << *L.getHeader()->getModule();
 684     return;
 685   }
 686
 687   OS << Banner;
 688
 689   auto *PreHeader = L.getLoopPreheader();
 690   if (PreHeader) {
 691     OS << "\n; Preheader:";
 692     PreHeader->print(OS);
 693     OS << "\n; Loop:";
 694   }
 695
 696   for (auto *Block : L.blocks())
 697     if (Block)
 698       Block->print(OS);
 699     else
 700       OS << "Printing <null> block";
 701
 702   SmallVector<BasicBlock *, 8> ExitBlocks;
 703   L.getExitBlocks(ExitBlocks);
 704   if (!ExitBlocks.empty()) {
 705     OS << "\n; Exit blocks";
 706     for (auto *Block : ExitBlocks)
 707       if (Block)
 708         Block->print(OS);
 709       else
 710         OS << "Printing <null> block";
 711   }
 712 }
 713
 714 MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
 715   // No loop metadata node, no loop properties.
 716   if (!LoopID)
 717     return nullptr;
 718
 719   // First operand should refer to the metadata node itself, for legacy reasons.
 720   assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
 721   assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
 722
 723   // Iterate over the metdata node operands and look for MDString metadata.
 724   for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
 725     MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
 726     if (!MD || MD->getNumOperands() < 1)
 727       continue;
 728     MDString *S = dyn_cast<MDString>(MD->getOperand(0));
 729     if (!S)
 730       continue;
 731     // Return the operand node if MDString holds expected metadata.
 732     if (Name.equals(S->getString()))
 733       return MD;
 734   }
 735
 736   // Loop property not found.
 737   return nullptr;
 738 }
 739
 740 MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
 741   return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
 742 }
 743
 744 bool llvm::isValidAsAccessGroup(MDNode *Node) {
 745   return Node->getNumOperands() == 0 && Node->isDistinct();
 746 }
 747
 748 MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
 749                                              MDNode *OrigLoopID,
 750                                              ArrayRef<StringRef> RemovePrefixes,
 751                                              ArrayRef<MDNode *> AddAttrs) {
 752   // First remove any existing loop metadata related to this transformation.
 753   SmallVector<Metadata *, 4> MDs;
 754
 755   // Reserve first location for self reference to the LoopID metadata node.
 756   TempMDTuple TempNode = MDNode::getTemporary(Context, None);
 757   MDs.push_back(TempNode.get());
 758
 759   // Remove metadata for the transformation that has been applied or that became
 760   // outdated.
 761   if (OrigLoopID) {
 762     for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
 763       bool IsVectorMetadata = false;
 764       Metadata *Op = OrigLoopID->getOperand(i);
 765       if (MDNode *MD = dyn_cast<MDNode>(Op)) {
 766         const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
 767         if (S)
 768           IsVectorMetadata =
 769               llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
 770                 return S->getString().startswith(Prefix);
 771               });
 772       }
 773       if (!IsVectorMetadata)
 774         MDs.push_back(Op);
 775     }
 776   }
 777
 778   // Add metadata to avoid reapplying a transformation, such as
 779   // llvm.loop.unroll.disable and llvm.loop.isvectorized.
 780   MDs.append(AddAttrs.begin(), AddAttrs.end());
 781
 782   MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
 783   // Replace the temporary node with a self-reference.
 784   NewLoopID->replaceOperandWith(0, NewLoopID);
 785   return NewLoopID;
 786 }
 787
 788 //===----------------------------------------------------------------------===//
 789 // LoopInfo implementation
 790 //
 791
 792 char LoopInfoWrapperPass::ID = 0;
 793 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
 794                       true, true)
 795 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 796 INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
 797                     true, true)
 798
 799 bool LoopInfoWrapperPass::runOnFunction(Function &) {
 800   releaseMemory();
 801   LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
 802   return false;
 803 }
 804
 805 void LoopInfoWrapperPass::verifyAnalysis() const {
 806   // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
 807   // function each time verifyAnalysis is called is very expensive. The
 808   // -verify-loop-info option can enable this. In order to perform some
 809   // checking by default, LoopPass has been taught to call verifyLoop manually
 810   // during loop pass sequences.
 811   if (VerifyLoopInfo) {
 812     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 813     LI.verify(DT);
 814   }
 815 }
 816
 817 void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 818   AU.setPreservesAll();
 819   AU.addRequired<DominatorTreeWrapperPass>();
 820 }
 821
 822 void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
 823   LI.print(OS);
 824 }
 825
 826 PreservedAnalyses LoopVerifierPass::run(Function &F,
 827                                         FunctionAnalysisManager &AM) {
 828   LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
 829   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 830   LI.verify(DT);
 831   return PreservedAnalyses::all();
 832 }
 833
 834 //===----------------------------------------------------------------------===//
 835 // LoopBlocksDFS implementation
 836 //
 837
 838 /// Traverse the loop blocks and store the DFS result.
 839 /// Useful for clients that just want the final DFS result and don't need to
 840 /// visit blocks during the initial traversal.
 841 void LoopBlocksDFS::perform(LoopInfo *LI) {
 842   LoopBlocksTraversal Traversal(*this, LI);
 843   for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
 844                                         POE = Traversal.end();
 845        POI != POE; ++POI)
 846     ;
 847 }