1//===- Dominators.h - Dominator Info Calculation ----------------*- C++ -*-===// 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 7//===----------------------------------------------------------------------===// 9// This file defines the DominatorTree class, which provides fast and efficient 12//===----------------------------------------------------------------------===// 14#ifndef LLVM_IR_DOMINATORS_H 15#define LLVM_IR_DOMINATORS_H 44template <
class GraphType>
structGraphTraits;
46externtemplateclassDomTreeNodeBase<BasicBlock>;
47externtemplateclassDominatorTreeBase<BasicBlock, false>;
// DomTree 48externtemplateclassDominatorTreeBase<BasicBlock, true>;
// PostDomTree 50externtemplateclasscfg::Update<BasicBlock *>;
52namespaceDomTreeBuilder {
61externtemplatevoid Calculate<BBDomTree>(
BBDomTree &DT);
62externtemplatevoid CalculateWithUpdates<BBDomTree>(
BBDomTree &DT,
79externtemplatevoid ApplyUpdates<BBDomTree>(
BBDomTree &DT,
86externtemplatebool Verify<BBDomTree>(
constBBDomTree &DT,
90}
// namespace DomTreeBuilder 100 Start(Start_),
End(End_) {}
103 : Start(Pair.first),
End(Pair.second) {}
106 : Start(Pair.first),
End(Pair.second) {}
116 /// Check if this is the only edge between Start and End. 117bool isSingleEdge()
const;
126returnBasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
130returnBasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
135 BBInfo::getHashValue(Edge.
getEnd()));
139return BBInfo::isEqual(
LHS.getStart(),
RHS.getStart()) &&
140 BBInfo::isEqual(
LHS.getEnd(),
RHS.getEnd());
144/// Concrete subclass of DominatorTreeBase that is used to compute a 145/// normal dominator tree. 147/// Definition: A block is said to be forward statically reachable if there is 148/// a path from the entry of the function to the block. A statically reachable 149/// block may become statically unreachable during optimization. 151/// A forward unreachable block may appear in the dominator tree, or it may 152/// not. If it does, dominance queries will return results as if all reachable 153/// blocks dominate it. When asking for a Node corresponding to a potentially 154/// unreachable block, calling code must handle the case where the block was 155/// unreachable and the result of getNode() is nullptr. 157/// Generally, a block known to be unreachable when the dominator tree is 158/// constructed will not be in the tree. One which becomes unreachable after 159/// the dominator tree is initially constructed may still exist in the tree, 160/// even if the tree is properly updated. Calling code should not rely on the 161/// preceding statements; this is stated only to assist human understanding. 169 recalculate(*DT.
Parent, U);
172 /// Handle invalidation explicitly. 176// Ensure base-class overloads are visible. 179 /// Return true if the (end of the) basic block BB dominates the use U. 182 /// Return true if value Def dominates use U, in the sense that Def is 183 /// available at U, and could be substituted as the used value without 184 /// violating the SSA dominance requirement. 186 /// In particular, it is worth noting that: 187 /// * Non-instruction Defs dominate everything. 188 /// * Def does not dominate a use in Def itself (outside of degenerate cases 189 /// like unreachable code or trivial phi cycles). 190 /// * Invoke Defs only dominate uses in their default destination. 193 /// Return true if value Def dominates all possible uses inside instruction 194 /// User. Same comments as for the Use-based API apply. 200 /// Returns true if Def would dominate a use in any instruction in BB. 201 /// If Def is an instruction in BB, then Def does not dominate BB. 203 /// Does not accept Value to avoid ambiguity with dominance checks between 204 /// two basic blocks. 207 /// Return true if an edge dominates a use. 209 /// If BBE is not a unique edge between start and end of the edge, it can 210 /// never dominate the use. 213 /// Returns true if edge \p BBE1 dominates edge \p BBE2. 216// Ensure base class overloads are visible. 217usingBase::isReachableFromEntry;
219 /// Provide an overload for a Use. 220bool isReachableFromEntry(
constUse &U)
const;
222// Ensure base class overloads are visible. 223usingBase::findNearestCommonDominator;
225 /// Find the nearest instruction I that dominates both I1 and I2, in the sense 226 /// that a result produced before I will be available at both I1 and I2. 230// Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`. 235//===------------------------------------- 236// DominatorTree GraphTraits specializations so the DominatorTree can be 237// iterable by generic graph iterators. 278/// Analysis pass which computes a \c DominatorTree. 284 /// Provide the result typedef for this analysis pass. 287 /// Run the analysis pass over a function and produce a dominator tree. 291/// Printer pass for the \c DominatorTree. 304/// Verifier pass for the \c DominatorTree. 310/// Enables verification of dominator trees. 312/// This check is expensive and is disabled by default. `-verify-dom-info` 313/// allows selectively enabling the check without needing to recompile. 316/// Legacy analysis pass which computes a \c DominatorTree. 340}
// end namespace llvm 342#endif// LLVM_IR_DOMINATORS_H This file implements a class to represent arbitrary precision integral constant values and operations...
BlockVerifier::State From
This file defines DenseMapInfo traits for DenseMap.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This header defines various interfaces for pass management in LLVM.
This defines the Use class.
Machine Check Debug Module
This file defines the PointerIntPair class.
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
This file defines the SmallVector class.
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const BasicBlock * getEnd() const
const BasicBlock * getStart() const
BasicBlockEdge(const std::pair< const BasicBlock *, const BasicBlock * > &Pair)
BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_)
BasicBlockEdge(const std::pair< BasicBlock *, BasicBlock * > &Pair)
LLVM Basic Block Representation.
InstListType::iterator iterator
Instruction iterators...
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Analysis pass which computes a DominatorTree.
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Core dominator tree base class.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Printer pass for the DominatorTree.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Legacy analysis pass which computes a DominatorTree.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
DominatorTreeWrapperPass()
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
DominatorTree & getDomTree()
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
const DominatorTree & getDomTree() const
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const Value *Def, BasicBlock::iterator User) const
DominatorTree(Function &F)
DominatorTree(DominatorTree &DT, DomTreeBuilder::BBUpdates U)
FunctionPass class - This class is used to implement most global optimizations.
A Module instance is used to store all the information related to an LLVM module.
A set of analyses that are preserved following a run of a transformation pass.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
df_iterator< T > df_begin(const T &G)
DomTreeNodeBase< BasicBlock > DomTreeNode
bool VerifyDomInfo
Enables verification of dominator trees.
df_iterator< T > df_end(const T &G)
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static BasicBlockEdge getEmptyKey()
static BasicBlockEdge getTombstoneKey()
static unsigned getHashValue(const BasicBlockEdge *V)
static unsigned getHashValue(const BasicBlockEdge &Edge)
static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
static ChildIteratorType child_end(NodeRef N)
static NodeRef getEntryNode(NodeRef N)
ChildIterator ChildIteratorType
static nodes_iterator nodes_begin(NodeRef N)
static nodes_iterator nodes_end(NodeRef N)
static ChildIteratorType child_begin(NodeRef N)
Verifier pass for the DominatorTree.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static nodes_iterator nodes_end(DominatorTree *N)
static NodeRef getEntryNode(DominatorTree *DT)
static nodes_iterator nodes_begin(DominatorTree *N)
A CRTP mix-in to automatically provide informational APIs needed for passes.
