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 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
42 /// compute the a post-dominator tree.
44 struct PostDominatorTree : public DominatorTreeBase {
45 PostDominatorTree() : DominatorTreeBase(true) {}
47 virtual bool runOnFunction(Function &F) {
48 reset(); // Reset from the last time we were run...
49 ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>();
50 Roots = IPD.getRoots();
55 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
57 AU.addRequired<ImmediatePostDominators>();
60 void calculate(const ImmediatePostDominators &IPD);
61 Node *getNodeForBlock(BasicBlock *BB);
65 /// PostETForest Class - Concrete subclass of ETForestBase that is used to
66 /// compute a forwards post-dominator ET-Forest.
67 struct PostETForest : public ETForestBase {
68 PostETForest() : ETForestBase(true) {}
70 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
72 AU.addRequired<ImmediatePostDominators>();
75 virtual bool runOnFunction(Function &F) {
76 reset(); // Reset from the last time we were run...
77 ImmediatePostDominators &ID = getAnalysis<ImmediatePostDominators>();
78 Roots = ID.getRoots();
83 void calculate(const ImmediatePostDominators &ID);
84 ETNode *getNodeForBlock(BasicBlock *BB);
88 /// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
89 /// used to compute the a post-dominance frontier.
91 struct PostDominanceFrontier : public DominanceFrontierBase {
92 PostDominanceFrontier() : DominanceFrontierBase(true) {}
94 virtual bool runOnFunction(Function &) {
96 PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
97 Roots = DT.getRoots();
98 if (const DominatorTree::Node *Root = DT.getRootNode())
103 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
104 AU.setPreservesAll();
105 AU.addRequired<PostDominatorTree>();
109 const DomSetType &calculate(const PostDominatorTree &DT,
110 const DominatorTree::Node *Node);
113 } // End llvm namespace
115 // Make sure that any clients of this file link in PostDominators.cpp
116 FORCE_DEFINING_FILE_TO_BE_LINKED(PostDominanceFrontier)