1 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file exposes interfaces to post dominance information.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_POST_DOMINATORS_H
15 #define LLVM_ANALYSIS_POST_DOMINATORS_H
17 #include "llvm/Analysis/Dominators.h"
21 //===-------------------------------------
22 /// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
23 /// that is used to compute a normal immediate dominator set.
25 struct ImmediatePostDominators : public ImmediateDominatorsBase {
26 ImmediatePostDominators() : ImmediateDominatorsBase(false) {}
28 virtual bool runOnFunction(Function &F);
30 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
35 unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
36 void Compress(BasicBlock *V, InfoRec &VInfo);
37 BasicBlock *Eval(BasicBlock *v);
38 void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
41 /// PostDominatorSet Class - Concrete subclass of DominatorSetBase that is used
42 /// to compute the post-dominator set. Because there can be multiple exit nodes
43 /// in an LLVM function, we calculate post dominators with a special null block
44 /// which is the virtual exit node that the real exit nodes all virtually branch
45 /// to. Clients should be prepared to see an entry in the dominator sets with a
48 struct PostDominatorSet : public DominatorSetBase {
49 PostDominatorSet() : DominatorSetBase(true) {}
51 virtual bool runOnFunction(Function &F);
53 /// getAnalysisUsage - This simply provides a dominator set
55 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
56 AU.addRequired<ImmediatePostDominators>();
60 // stub - dummy function, just ignore it
64 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
65 /// compute the a post-dominator tree.
67 struct PostDominatorTree : public DominatorTreeBase {
68 PostDominatorTree() : DominatorTreeBase(true) {}
70 virtual bool runOnFunction(Function &F) {
71 reset(); // Reset from the last time we were run...
72 ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>();
73 Roots = IPD.getRoots();
78 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
80 AU.addRequired<ImmediatePostDominators>();
83 void calculate(const ImmediatePostDominators &IPD);
84 Node *getNodeForBlock(BasicBlock *BB);
88 /// PostETForest Class - Concrete subclass of ETForestBase that is used to
89 /// compute a forwards post-dominator ET-Forest.
90 struct PostETForest : public ETForestBase {
91 PostETForest() : ETForestBase(true) {}
93 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
95 AU.addRequired<ImmediatePostDominators>();
98 virtual bool runOnFunction(Function &F) {
99 reset(); // Reset from the last time we were run...
100 ImmediatePostDominators &ID = getAnalysis<ImmediatePostDominators>();
101 Roots = ID.getRoots();
106 void calculate(const ImmediatePostDominators &ID);
107 ETNode *getNodeForBlock(BasicBlock *BB);
111 /// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
112 /// used to compute the a post-dominance frontier.
114 struct PostDominanceFrontier : public DominanceFrontierBase {
115 PostDominanceFrontier() : DominanceFrontierBase(true) {}
117 virtual bool runOnFunction(Function &) {
119 PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
120 Roots = DT.getRoots();
121 if (const DominatorTree::Node *Root = DT.getRootNode())
126 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
127 AU.setPreservesAll();
128 AU.addRequired<PostDominatorTree>();
132 const DomSetType &calculate(const PostDominatorTree &DT,
133 const DominatorTree::Node *Node);
136 } // End llvm namespace
138 // Make sure that any clients of this file link in PostDominators.cpp
139 FORCE_DEFINING_FILE_TO_BE_LINKED(PostDominanceFrontier)