1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the DominanceFrontier class, which calculate and holds the
11 // dominance frontier for a function.
13 // This should be considered deprecated, don't add any more uses of this data
16 //===----------------------------------------------------------------------===//
18 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
19 #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
21 #include "llvm/Analysis/Dominators.h"
27 //===----------------------------------------------------------------------===//
28 /// DominanceFrontierBase - Common base class for computing forward and inverse
29 /// dominance frontiers for a function.
31 class DominanceFrontierBase : public FunctionPass {
33 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
34 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
36 DomSetMapType Frontiers;
37 std::vector<BasicBlock*> Roots;
38 const bool IsPostDominators;
41 DominanceFrontierBase(char &ID, bool isPostDom)
42 : FunctionPass(ID), IsPostDominators(isPostDom) {}
44 /// getRoots - Return the root blocks of the current CFG. This may include
45 /// multiple blocks if we are computing post dominators. For forward
46 /// dominators, this will always be a single block (the entry node).
48 inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
50 /// isPostDominator - Returns true if analysis based of postdoms
52 bool isPostDominator() const { return IsPostDominators; }
54 virtual void releaseMemory() { Frontiers.clear(); }
56 // Accessor interface:
57 typedef DomSetMapType::iterator iterator;
58 typedef DomSetMapType::const_iterator const_iterator;
59 iterator begin() { return Frontiers.begin(); }
60 const_iterator begin() const { return Frontiers.begin(); }
61 iterator end() { return Frontiers.end(); }
62 const_iterator end() const { return Frontiers.end(); }
63 iterator find(BasicBlock *B) { return Frontiers.find(B); }
64 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
66 iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
67 assert(find(BB) == end() && "Block already in DominanceFrontier!");
68 return Frontiers.insert(std::make_pair(BB, frontier)).first;
71 /// removeBlock - Remove basic block BB's frontier.
72 void removeBlock(BasicBlock *BB) {
73 assert(find(BB) != end() && "Block is not in DominanceFrontier!");
74 for (iterator I = begin(), E = end(); I != E; ++I)
79 void addToFrontier(iterator I, BasicBlock *Node) {
80 assert(I != end() && "BB is not in DominanceFrontier!");
81 I->second.insert(Node);
84 void removeFromFrontier(iterator I, BasicBlock *Node) {
85 assert(I != end() && "BB is not in DominanceFrontier!");
86 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
87 I->second.erase(Node);
90 /// compareDomSet - Return false if two domsets match. Otherwise
92 bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
93 std::set<BasicBlock *> tmpSet;
94 for (DomSetType::const_iterator I = DS2.begin(),
95 E = DS2.end(); I != E; ++I)
98 for (DomSetType::const_iterator I = DS1.begin(),
99 E = DS1.end(); I != E; ) {
100 BasicBlock *Node = *I++;
102 if (tmpSet.erase(Node) == 0)
103 // Node is in DS1 but not in DS2.
108 // There are nodes that are in DS2 but not in DS1.
111 // DS1 and DS2 matches.
115 /// compare - Return true if the other dominance frontier base matches
116 /// this dominance frontier base. Otherwise return false.
117 bool compare(DominanceFrontierBase &Other) const {
118 DomSetMapType tmpFrontiers;
119 for (DomSetMapType::const_iterator I = Other.begin(),
120 E = Other.end(); I != E; ++I)
121 tmpFrontiers.insert(std::make_pair(I->first, I->second));
123 for (DomSetMapType::iterator I = tmpFrontiers.begin(),
124 E = tmpFrontiers.end(); I != E; ) {
125 BasicBlock *Node = I->first;
126 const_iterator DFI = find(Node);
130 if (compareDomSet(I->second, DFI->second))
134 tmpFrontiers.erase(Node);
137 if (!tmpFrontiers.empty())
143 /// print - Convert to human readable form
145 virtual void print(raw_ostream &OS, const Module* = 0) const;
147 /// dump - Dump the dominance frontier to dbgs().
152 //===-------------------------------------
153 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
154 /// used to compute a forward dominator frontiers.
156 class DominanceFrontier : public DominanceFrontierBase {
157 virtual void anchor();
159 static char ID; // Pass ID, replacement for typeid
160 DominanceFrontier() :
161 DominanceFrontierBase(ID, false) {
162 initializeDominanceFrontierPass(*PassRegistry::getPassRegistry());
165 BasicBlock *getRoot() const {
166 assert(Roots.size() == 1 && "Should always have entry node!");
170 virtual bool runOnFunction(Function &) {
172 DominatorTree &DT = getAnalysis<DominatorTree>();
173 Roots = DT.getRoots();
174 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
175 calculate(DT, DT[Roots[0]]);
179 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
180 AU.setPreservesAll();
181 AU.addRequired<DominatorTree>();
184 const DomSetType &calculate(const DominatorTree &DT,
185 const DomTreeNode *Node);
188 } // End llvm namespace