PostDominators.h revision 794fd75c67a2cdc128d67342c6d88a504d186896 
1//=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
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.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file exposes interfaces to post dominance information.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_POST_DOMINATORS_H
15#define LLVM_ANALYSIS_POST_DOMINATORS_H
16
17#include "llvm/Analysis/Dominators.h"
18
19namespace llvm {
20
21/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
22/// compute the a post-dominator tree.
23///
24struct PostDominatorTree : public DominatorTreeBase {
25  static const int ID; // Pass identifcation, replacement for typeid
26
27  PostDominatorTree() :
28    DominatorTreeBase((intptr_t)&ID, true) {}
29
30  virtual bool runOnFunction(Function &F) {
31    reset();     // Reset from the last time we were run...
32    calculate(F);
33    return false;
34  }
35
36  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
37    AU.setPreservesAll();
38  }
39private:
40  void calculate(Function &F);
41  Node *getNodeForBlock(BasicBlock *BB);
42  unsigned DFSPass(BasicBlock *V, InfoRec &VInfo,unsigned N);
43  void Compress(BasicBlock *V, InfoRec &VInfo);
44  BasicBlock *Eval(BasicBlock *V);
45  void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
46
47  inline BasicBlock *getIDom(BasicBlock *BB) const {
48    std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
49    return I != IDoms.end() ? I->second : 0;
50  }
51};
52
53
54/// PostETForest Class - Concrete subclass of ETForestBase that is used to
55/// compute a forwards post-dominator ET-Forest.
56struct PostETForest : public ETForestBase {
57  static const int ID;
58  PostETForest() : ETForestBase((intptr_t)&ID, true) {}
59
60  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
61    AU.setPreservesAll();
62    AU.addRequired<PostDominatorTree>();
63  }
64
65  virtual bool runOnFunction(Function &F) {
66    reset();     // Reset from the last time we were run...
67    PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
68    Roots = DT.getRoots();
69    calculate(DT);
70    return false;
71  }
72
73  void calculate(const PostDominatorTree &DT);
74  ETNode *getNodeForBlock(BasicBlock *BB);
75};
76
77
78/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
79/// used to compute the a post-dominance frontier.
80///
81struct PostDominanceFrontier : public DominanceFrontierBase {
82  static const int ID;
83  PostDominanceFrontier()
84    : DominanceFrontierBase((intptr_t) &ID, true) {}
85
86  virtual bool runOnFunction(Function &) {
87    Frontiers.clear();
88    PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
89    Roots = DT.getRoots();
90    if (const DominatorTree::Node *Root = DT.getRootNode())
91      calculate(DT, Root);
92    return false;
93  }
94
95  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
96    AU.setPreservesAll();
97    AU.addRequired<PostDominatorTree>();
98  }
99
100private:
101  const DomSetType &calculate(const PostDominatorTree &DT,
102                              const DominatorTree::Node *Node);
103};
104
105} // End llvm namespace
106
107// Make sure that any clients of this file link in PostDominators.cpp
108FORCE_DEFINING_FILE_TO_BE_LINKED(PostDominanceFrontier)
109
110#endif
111