LLVM  14.0.0git
PostDominators.h
Go to the documentation of this file.
1 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation --*- C++ -*-=//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file exposes interfaces to post dominance information.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H
14 #define LLVM_ANALYSIS_POSTDOMINATORS_H
15 
17 #include "llvm/IR/Dominators.h"
18 #include "llvm/IR/PassManager.h"
19 #include "llvm/Pass.h"
20 
21 namespace llvm {
22 
23 class Function;
24 class raw_ostream;
25 
26 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
27 /// compute the post-dominator tree.
28 class PostDominatorTree : public PostDomTreeBase<BasicBlock> {
29 public:
31 
32  PostDominatorTree() = default;
34  /// Handle invalidation explicitly.
35  bool invalidate(Function &F, const PreservedAnalyses &PA,
37 
38  // Ensure base-class overloads are visible.
39  using Base::dominates;
40 
41  /// Return true if \p I1 dominates \p I2. This checks if \p I2 comes before
42  /// \p I1 if they belongs to the same basic block.
43  bool dominates(const Instruction *I1, const Instruction *I2) const;
44 };
45 
46 /// Analysis pass which computes a \c PostDominatorTree.
48  : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
50 
51  static AnalysisKey Key;
52 
53 public:
54  /// Provide the result type for this analysis pass.
56 
57  /// Run the analysis pass over a function and produce a post dominator
58  /// tree.
60 };
61 
62 /// Printer pass for the \c PostDominatorTree.
64  : public PassInfoMixin<PostDominatorTreePrinterPass> {
65  raw_ostream &OS;
66 
67 public:
69 
71 };
72 
74  static char ID; // Pass identification, replacement for typeid
75 
77 
79 
81  const PostDominatorTree &getPostDomTree() const { return DT; }
82 
83  bool runOnFunction(Function &F) override;
84 
85  void verifyAnalysis() const override;
86 
87  void getAnalysisUsage(AnalysisUsage &AU) const override {
88  AU.setPreservesAll();
89  }
90 
91  void releaseMemory() override { DT.reset(); }
92 
93  void print(raw_ostream &OS, const Module*) const override;
94 };
95 
96 FunctionPass* createPostDomTree();
97 
98 template <> struct GraphTraits<PostDominatorTree*>
99  : public GraphTraits<DomTreeNode*> {
101  return DT->getRootNode();
102  }
103 
105  if (getEntryNode(N))
106  return df_begin(getEntryNode(N));
107  else
108  return df_end(getEntryNode(N));
109  }
110 
112  return df_end(getEntryNode(N));
113  }
114 };
115 
116 } // end namespace llvm
117 
118 #endif // LLVM_ANALYSIS_POSTDOMINATORS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::PostDominatorTreeAnalysis::run
PostDominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a post dominator tree.
Definition: PostDominators.cpp:98
llvm::GraphTraits< DomTreeNode * >
Definition: Dominators.h:229
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
Pass.h
llvm::PostDominatorTree::PostDominatorTree
PostDominatorTree(Function &F)
Definition: PostDominators.h:33
llvm::df_end
df_iterator< T > df_end(const T &G)
Definition: DepthFirstIterator.h:223
llvm::GraphTraits< PostDominatorTree * >::getEntryNode
static NodeRef getEntryNode(PostDominatorTree *DT)
Definition: PostDominators.h:100
llvm::PostDominatorTreeWrapperPass::PostDominatorTreeWrapperPass
PostDominatorTreeWrapperPass()
Definition: PostDominators.cpp:37
llvm::PostDominatorTreeWrapperPass::getPostDomTree
const PostDominatorTree & getPostDomTree() const
Definition: PostDominators.h:81
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
llvm::PostDominatorTreeWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: PostDominators.cpp:76
llvm::PostDominatorTreeWrapperPass
Definition: PostDominators.h:73
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::PostDominatorTreeWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: PostDominators.h:87
llvm::PostDominatorTreeWrapperPass::DT
PostDominatorTree DT
Definition: PostDominators.h:76
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:666
llvm::createPostDomTree
FunctionPass * createPostDomTree()
Definition: PostDominators.cpp:92
llvm::PostDominatorTreeWrapperPass::print
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
Definition: PostDominators.cpp:88
llvm::PostDominatorTreePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PostDominators.cpp:108
llvm::PostDominatorTreeWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: PostDominators.h:91
llvm::PostDominatorTreeWrapperPass::ID
static char ID
Definition: PostDominators.h:74
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::df_begin
df_iterator< T > df_begin(const T &G)
Definition: DepthFirstIterator.h:218
llvm::PostDominatorTreePrinterPass
Printer pass for the PostDominatorTree.
Definition: PostDominators.h:63
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:397
llvm::df_iterator
Definition: DepthFirstIterator.h:85
llvm::DominatorTreeBase::reset
void reset()
Definition: GenericDomTree.h:806
llvm::DominatorTreeBase::recalculate
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
Definition: GenericDomTree.h:778
llvm::PostDominatorTreeWrapperPass::getPostDomTree
PostDominatorTree & getPostDomTree()
Definition: PostDominators.h:80
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::DomTreeNodeBase< BasicBlock >
llvm::DominatorTreeBase::dominates
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
Definition: GenericDomTree.h:416
llvm::PostDominatorTree::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
llvm::PostDominatorTreeWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: PostDominators.cpp:81
llvm::PostDominatorTreePrinterPass::PostDominatorTreePrinterPass
PostDominatorTreePrinterPass(raw_ostream &OS)
Definition: PostDominators.cpp:104
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
PassManager.h
llvm::GraphTraits< PostDominatorTree * >::nodes_end
static nodes_iterator nodes_end(PostDominatorTree *N)
Definition: PostDominators.h:111
Dominators.h
N
#define N
llvm::PostDominatorTree::PostDominatorTree
PostDominatorTree()=default
llvm::GraphTraits< PostDominatorTree * >::nodes_begin
static nodes_iterator nodes_begin(PostDominatorTree *N)
Definition: PostDominators.h:104
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::PostDominatorTreeAnalysis
Analysis pass which computes a PostDominatorTree.
Definition: PostDominators.h:47
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::PostDominatorTree::dominates
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
Definition: PostDominators.cpp:54
llvm::codeview::PublicSymFlags::Function
@ Function