LoopInfo.cpp | Explore in Territory

//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the LoopInfo class that is used to identify natural loops
// and determine the loop depth of various nodes of the CFG.  Note that the
// loops identified may actually be several natural loops that share the same
// header node... not just a single natural loop.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopInfo.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PrintPasses.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/GenericLoopInfoImpl.h"
#include "llvm/Support/raw_ostream.h"
usingnamespacellvm;

// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
template class llvm::LoopBase<BasicBlock, Loop>;
template class llvm::LoopInfoBase<BasicBlock, Loop>;

// Always verify loopinfo if expensive checking is enabled.
#ifdef EXPENSIVE_CHECKS
bool llvm::VerifyLoopInfo = true;
#else
bool llvm::VerifyLoopInfo = …;
#endif
static cl::opt<bool, true>
    VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
                    cl::Hidden, cl::desc("Verify loop info (time consuming)"));

//===----------------------------------------------------------------------===//
// Loop implementation
//

bool Loop::isLoopInvariant(const Value *V) const { … }

bool Loop::hasLoopInvariantOperands(const Instruction *I) const { … }

bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
                             MemorySSAUpdater *MSSAU,
                             ScalarEvolution *SE) const { … }

bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
                             Instruction *InsertPt, MemorySSAUpdater *MSSAU,
                             ScalarEvolution *SE) const { … }

bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
                                  BasicBlock *&Backedge) const { … }

PHINode *Loop::getCanonicalInductionVariable() const { … }

/// Get the latch condition instruction.
ICmpInst *Loop::getLatchCmpInst() const { … }

/// Return the final value of the loop induction variable if found.
static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar,
                               const Instruction &StepInst) { … }

std::optional<Loop::LoopBounds>
Loop::LoopBounds::getBounds(const Loop &L, PHINode &IndVar,
                            ScalarEvolution &SE) { … }

Direction;

ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const { … }

Direction Loop::LoopBounds::getDirection() const { … }

std::optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const { … }

PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const { … }

bool Loop::getInductionDescriptor(ScalarEvolution &SE,
                                  InductionDescriptor &IndDesc) const { … }

bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
                                        ScalarEvolution &SE) const { … }

BranchInst *Loop::getLoopGuardBranch() const { … }

bool Loop::isCanonical(ScalarEvolution &SE) const { … }

// Check that 'BB' doesn't have any uses outside of the 'L'
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
                               const DominatorTree &DT, bool IgnoreTokens) { … }

bool Loop::isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens) const { … }

bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI,
                                  bool IgnoreTokens) const { … }

bool Loop::isLoopSimplifyForm() const { … }

// Routines that reform the loop CFG and split edges often fail on indirectbr.
bool Loop::isSafeToClone() const { … }

MDNode *Loop::getLoopID() const { … }

void Loop::setLoopID(MDNode *LoopID) const { … }

void Loop::setLoopAlreadyUnrolled() { … }

void Loop::setLoopMustProgress() { … }

bool Loop::isAnnotatedParallel() const { … }

DebugLoc Loop::getStartLoc() const { … }

Loop::LocRange Loop::getLocRange() const { … }

std::string Loop::getLocStr() const { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }

LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
  print(dbgs(), /*Verbose=*/true);
}
#endif

//===----------------------------------------------------------------------===//
// UnloopUpdater implementation
//

namespace {
/// Find the new parent loop for all blocks within the "unloop" whose last
/// backedges has just been removed.
class UnloopUpdater { … };
} // end anonymous namespace

/// Update the parent loop for all blocks that are directly contained within the
/// original "unloop".
void UnloopUpdater::updateBlockParents() { … }

/// Remove unloop's blocks from all ancestors below their new parents.
void UnloopUpdater::removeBlocksFromAncestors() { … }

/// Update the parent loop for all subloops directly nested within unloop.
void UnloopUpdater::updateSubloopParents() { … }

/// Return the nearest parent loop among this block's successors. If a successor
/// is a subloop header, consider its parent to be the nearest parent of the
/// subloop's exits.
///
/// For subloop blocks, simply update SubloopParents and return NULL.
Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { … }

LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { … }

bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
                          FunctionAnalysisManager::Invalidator &) { … }

void LoopInfo::erase(Loop *Unloop) { … }

bool LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(
    const Value *V, const BasicBlock *ExitBB) const { … }

AnalysisKey LoopAnalysis::Key;

LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) { … }

PreservedAnalyses LoopPrinterPass::run(Function &F,
                                       FunctionAnalysisManager &AM) { … }

void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) { … }

MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) { … }

MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) { … }

/// Find string metadata for loop
///
/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
/// operand or null otherwise.  If the string metadata is not found return
/// Optional's not-a-value.
std::optional<const MDOperand *>
llvm::findStringMetadataForLoop(const Loop *TheLoop, StringRef Name) { … }

std::optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop,
                                                       StringRef Name) { … }

bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) { … }

std::optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop,
                                                     StringRef Name) { … }

int llvm::getIntLoopAttribute(const Loop *TheLoop, StringRef Name,
                              int Default) { … }

CallBase *llvm::getLoopConvergenceHeart(const Loop *TheLoop) { … }

bool llvm::isFinite(const Loop *L) { … }

static const char *LLVMLoopMustProgress = …;

bool llvm::hasMustProgress(const Loop *L) { … }

bool llvm::isMustProgress(const Loop *L) { … }

bool llvm::isValidAsAccessGroup(MDNode *Node) { … }

MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
                                             MDNode *OrigLoopID,
                                             ArrayRef<StringRef> RemovePrefixes,
                                             ArrayRef<MDNode *> AddAttrs) { … }

//===----------------------------------------------------------------------===//
// LoopInfo implementation
//

LoopInfoWrapperPass::LoopInfoWrapperPass() : … { … }

char LoopInfoWrapperPass::ID = …;
INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
                      true, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
                    true, true)

bool LoopInfoWrapperPass::runOnFunction(Function &) { … }

void LoopInfoWrapperPass::verifyAnalysis() const { … }

void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { … }

PreservedAnalyses LoopVerifierPass::run(Function &F,
                                        FunctionAnalysisManager &AM) { … }

//===----------------------------------------------------------------------===//
// LoopBlocksDFS implementation
//

/// Traverse the loop blocks and store the DFS result.
/// Useful for clients that just want the final DFS result and don't need to
/// visit blocks during the initial traversal.
void LoopBlocksDFS::perform(const LoopInfo *LI) { … }
llvm/llvm/lib/Analysis/LoopInfo.cpp
