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 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
22 /// compute the a post-dominator tree.
24 struct PostDominatorTree : public DominatorTreeBase {
25 PostDominatorTree() : DominatorTreeBase(true) {}
27 virtual bool runOnFunction(Function &F) {
28 reset(); // Reset from the last time we were run...
33 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
37 void calculate(Function &F);
38 Node *getNodeForBlock(BasicBlock *BB);
39 unsigned DFSPass(BasicBlock *V, InfoRec &VInfo,unsigned N);
40 void Compress(BasicBlock *V, InfoRec &VInfo);
41 BasicBlock *Eval(BasicBlock *V);
42 void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
44 inline BasicBlock *getIDom(BasicBlock *BB) const {
45 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
46 return I != IDoms.end() ? I->second : 0;
51 /// PostETForest Class - Concrete subclass of ETForestBase that is used to
52 /// compute a forwards post-dominator ET-Forest.
53 struct PostETForest : public ETForestBase {
54 PostETForest() : ETForestBase(true) {}
56 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
58 AU.addRequired<PostDominatorTree>();
61 virtual bool runOnFunction(Function &F) {
62 reset(); // Reset from the last time we were run...
63 PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
64 Roots = DT.getRoots();
69 void calculate(const PostDominatorTree &DT);
70 ETNode *getNodeForBlock(BasicBlock *BB);
74 /// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
75 /// used to compute the a post-dominance frontier.
77 struct PostDominanceFrontier : public DominanceFrontierBase {
78 PostDominanceFrontier() : DominanceFrontierBase(true) {}
80 virtual bool runOnFunction(Function &) {
82 PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
83 Roots = DT.getRoots();
84 if (const DominatorTree::Node *Root = DT.getRootNode())
89 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
91 AU.addRequired<PostDominatorTree>();
95 const DomSetType &calculate(const PostDominatorTree &DT,
96 const DominatorTree::Node *Node);
99 } // End llvm namespace
101 // Make sure that any clients of this file link in PostDominators.cpp
102 FORCE_DEFINING_FILE_TO_BE_LINKED(PostDominanceFrontier)