14#ifndef LLVM_IR_DOMINATORS_H
15#define LLVM_IR_DOMINATORS_H
47template <
class GraphType>
struct GraphTraits;
49extern template class DomTreeNodeBase<BasicBlock>;
50extern template class DominatorTreeBase<BasicBlock, false>;
51extern template class DominatorTreeBase<BasicBlock, true>;
53extern template class cfg::Update<BasicBlock *>;
55namespace DomTreeBuilder {
64extern template void Calculate<BBDomTree>(
BBDomTree &DT);
65extern template void CalculateWithUpdates<BBDomTree>(
BBDomTree &DT,
82extern template void ApplyUpdates<BBDomTree>(
BBDomTree &DT,
89extern template bool Verify<BBDomTree>(
const BBDomTree &DT,
103 Start(Start_),
End(End_) {}
106 : Start(Pair.first),
End(Pair.second) {}
109 : Start(Pair.first),
End(Pair.second) {}
120 bool isSingleEdge()
const;
129 return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
133 return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
138 BBInfo::getHashValue(Edge.
getEnd()));
142 return BBInfo::isEqual(
LHS.getStart(),
RHS.getStart()) &&
143 BBInfo::isEqual(
LHS.getEnd(),
RHS.getEnd());
172 recalculate(*DT.
Parent, U);
180 using Base::dominates;
216 using Base::isReachableFromEntry;
219 bool isReachableFromEntry(
const Use &U)
const;
222 using Base::findNearestCommonDominator;
273 return df_end(getEntryNode(
N));
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 defines the DenseMap class.
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...
Machine Check Debug Module
This header defines various interfaces for pass management in LLVM.
This file defines the PointerIntPair class.
static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B)
This file defines the SmallVector class.
This defines the Use 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.
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.
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 provides a very simple, boring adaptor for a begin and end iterator into a range type.
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.