Dominators.cpp | Explore in Territory

//===- Dominators.cpp - Dominator Calculation -----------------------------===//
//
// 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 implements simple dominator construction algorithms for finding
// forward dominators.  Postdominators are available in libanalysis, but are not
// included in libvmcore, because it's not needed.  Forward dominators are
// needed to support the Verifier pass.
//
//===----------------------------------------------------------------------===//

#include "llvm/IR/Dominators.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/InitializePasses.h"
#include "llvm/PassRegistry.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/GenericDomTreeConstruction.h"
#include "llvm/Support/raw_ostream.h"

#include <cassert>

namespace llvm {
class Argument;
class Constant;
class Value;
} // namespace llvm
usingnamespacellvm;

bool llvm::VerifyDomInfo = …;
static cl::opt<bool, true>
    VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden,
                   cl::desc("Verify dominator info (time consuming)"));

#ifdef EXPENSIVE_CHECKS
static constexpr bool ExpensiveChecksEnabled = true;
#else
static constexpr bool ExpensiveChecksEnabled = …;
#endif

bool BasicBlockEdge::isSingleEdge() const { … }

//===----------------------------------------------------------------------===//
//  DominatorTree Implementation
//===----------------------------------------------------------------------===//
//
// Provide public access to DominatorTree information.  Implementation details
// can be found in Dominators.h, GenericDomTree.h, and
// GenericDomTreeConstruction.h.
//
//===----------------------------------------------------------------------===//

template class llvm::DomTreeNodeBase<BasicBlock>;
template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase

template class llvm::cfg::Update<BasicBlock *>;

template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
    DomTreeBuilder::BBDomTree &DT);
template void
llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
    DomTreeBuilder::BBDomTree &DT, BBUpdates U);

template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
    DomTreeBuilder::BBPostDomTree &DT);
// No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.

template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
    DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
    DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);

template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
    DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
    DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);

template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
    DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &,
    DomTreeBuilder::BBDomTreeGraphDiff *);
template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
    DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBPostDomTreeGraphDiff &,
    DomTreeBuilder::BBPostDomTreeGraphDiff *);

template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
    const DomTreeBuilder::BBDomTree &DT,
    DomTreeBuilder::BBDomTree::VerificationLevel VL);
template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
    const DomTreeBuilder::BBPostDomTree &DT,
    DomTreeBuilder::BBPostDomTree::VerificationLevel VL);

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

bool DominatorTree::dominates(const BasicBlock *BB, const Use &U) const { … }

// dominates - Return true if Def dominates a use in User. This performs
// the special checks necessary if Def and User are in the same basic block.
// Note that Def doesn't dominate a use in Def itself!
bool DominatorTree::dominates(const Value *DefV,
                              const Instruction *User) const { … }

// true if Def would dominate a use in any instruction in UseBB.
// note that dominates(Def, Def->getParent()) is false.
bool DominatorTree::dominates(const Instruction *Def,
                              const BasicBlock *UseBB) const { … }

bool DominatorTree::dominates(const BasicBlockEdge &BBE,
                              const BasicBlock *UseBB) const { … }

bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const { … }

bool DominatorTree::dominates(const Value *DefV, const Use &U) const { … }

bool DominatorTree::isReachableFromEntry(const Use &U) const { … }

// Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
bool DominatorTree::dominates(const BasicBlockEdge &BBE1,
                              const BasicBlockEdge &BBE2) const { … }

Instruction *DominatorTree::findNearestCommonDominator(Instruction *I1,
                                                       Instruction *I2) const { … }

//===----------------------------------------------------------------------===//
//  DominatorTreeAnalysis and related pass implementations
//===----------------------------------------------------------------------===//
//
// This implements the DominatorTreeAnalysis which is used with the new pass
// manager. It also implements some methods from utility passes.
//
//===----------------------------------------------------------------------===//

DominatorTree DominatorTreeAnalysis::run(Function &F,
                                         FunctionAnalysisManager &) { … }

AnalysisKey DominatorTreeAnalysis::Key;

DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : … { … }

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

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

//===----------------------------------------------------------------------===//
//  DominatorTreeWrapperPass Implementation
//===----------------------------------------------------------------------===//
//
// The implementation details of the wrapper pass that holds a DominatorTree
// suitable for use with the legacy pass manager.
//
//===----------------------------------------------------------------------===//

char DominatorTreeWrapperPass::ID = …;

DominatorTreeWrapperPass::DominatorTreeWrapperPass() : … { … }

INITIALIZE_PASS(…)

bool DominatorTreeWrapperPass::runOnFunction(Function &F) { … }

void DominatorTreeWrapperPass::verifyAnalysis() const { … }

void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { … }
llvm/llvm/lib/IR/Dominators.cpp
