llvm/llvm/lib/Analysis/MustExecute.cpp

//===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/MustExecute.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/raw_ostream.h"

usingnamespacellvm;

#define DEBUG_TYPE …

const DenseMap<BasicBlock *, ColorVector> &
LoopSafetyInfo::getBlockColors() const { … }

void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) { … }

bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const { … }

bool SimpleLoopSafetyInfo::anyBlockMayThrow() const { … }

void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) { … }

bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const { … }

bool ICFLoopSafetyInfo::anyBlockMayThrow() const { … }

void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) { … }

void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
                                            const BasicBlock *BB) { … }

void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) { … }

void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) { … }

/// Return true if we can prove that the given ExitBlock is not reached on the
/// first iteration of the given loop.  That is, the backedge of the loop must
/// be executed before the ExitBlock is executed in any dynamic execution trace.
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
                                           const DominatorTree *DT,
                                           const Loop *CurLoop) { … }

/// Collect all blocks from \p CurLoop which lie on all possible paths from
/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
static void collectTransitivePredecessors(
    const Loop *CurLoop, const BasicBlock *BB,
    SmallPtrSetImpl<const BasicBlock *> &Predecessors) { … }

bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
                                             const BasicBlock *BB,
                                             const DominatorTree *DT) const { … }

/// Returns true if the instruction in a loop is guaranteed to execute at least
/// once.
bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
                                                 const DominatorTree *DT,
                                                 const Loop *CurLoop) const { … }

bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
                                              const DominatorTree *DT,
                                              const Loop *CurLoop) const { … }

bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
                                                 const Loop *CurLoop) const { … }

bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
                                                 const Loop *CurLoop) const { … }

static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) { … }

namespace {
/// An assembly annotator class to print must execute information in
/// comments.
class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter { … };
} // namespace

/// Return true if \p L might be an endless loop.
static bool maybeEndlessLoop(const Loop &L) { … }

bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) { … }

/// Lookup \p Key in \p Map and return the result, potentially after
/// initializing the optional through \p Fn(\p args).
template <typename K, typename V, typename FnTy, typename... ArgsTy>
static V getOrCreateCachedOptional(K Key, DenseMap<K, std::optional<V>> &Map,
                                   FnTy &&Fn, ArgsTy &&...args) { … }

const BasicBlock *
MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) { … }
const BasicBlock *
MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) { … }

const Instruction *
MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
    MustBeExecutedIterator &It, const Instruction *PP) { … }

const Instruction *
MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
    MustBeExecutedIterator &It, const Instruction *PP) { … }

MustBeExecutedIterator::MustBeExecutedIterator(
    MustBeExecutedContextExplorer &Explorer, const Instruction *I)
    : … { … }

void MustBeExecutedIterator::reset(const Instruction *I) { … }

void MustBeExecutedIterator::resetInstruction(const Instruction *I) { … }

const Instruction *MustBeExecutedIterator::advance() { … }

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

PreservedAnalyses
MustBeExecutedContextPrinterPass::run(Module &M, ModuleAnalysisManager &AM) { … }