DominanceFrontier.h revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338 
1//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the DominanceFrontier class, which calculate and holds the
11// dominance frontier for a function.
12//
13// This should be considered deprecated, don't add any more uses of this data
14// structure.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
19#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
20
21#include "llvm/IR/Dominators.h"
22#include <map>
23#include <set>
24
25namespace llvm {
26
27//===----------------------------------------------------------------------===//
28/// DominanceFrontierBase - Common base class for computing forward and inverse
29/// dominance frontiers for a function.
30///
31class DominanceFrontierBase : public FunctionPass {
32public:
33  typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
34  typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
35protected:
36  DomSetMapType Frontiers;
37  std::vector<BasicBlock*> Roots;
38  const bool IsPostDominators;
39
40public:
41  DominanceFrontierBase(char &ID, bool isPostDom)
42    : FunctionPass(ID), IsPostDominators(isPostDom) {}
43
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).
47  ///
48  inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
49
50  /// isPostDominator - Returns true if analysis based of postdoms
51  ///
52  bool isPostDominator() const { return IsPostDominators; }
53
54  void releaseMemory() override { Frontiers.clear(); }
55
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); }
65
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;
69  }
70
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)
75      I->second.erase(BB);
76    Frontiers.erase(BB);
77  }
78
79  void addToFrontier(iterator I, BasicBlock *Node) {
80    assert(I != end() && "BB is not in DominanceFrontier!");
81    I->second.insert(Node);
82  }
83
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);
88  }
89
90  /// compareDomSet - Return false if two domsets match. Otherwise
91  /// return true;
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)
96      tmpSet.insert(*I);
97
98    for (DomSetType::const_iterator I = DS1.begin(),
99           E = DS1.end(); I != E; ) {
100      BasicBlock *Node = *I++;
101
102      if (tmpSet.erase(Node) == 0)
103        // Node is in DS1 but not in DS2.
104        return true;
105    }
106
107    if (!tmpSet.empty())
108      // There are nodes that are in DS2 but not in DS1.
109      return true;
110
111    // DS1 and DS2 matches.
112    return false;
113  }
114
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));
122
123    for (DomSetMapType::iterator I = tmpFrontiers.begin(),
124           E = tmpFrontiers.end(); I != E; ) {
125      BasicBlock *Node = I->first;
126      const_iterator DFI = find(Node);
127      if (DFI == end())
128        return true;
129
130      if (compareDomSet(I->second, DFI->second))
131        return true;
132
133      ++I;
134      tmpFrontiers.erase(Node);
135    }
136
137    if (!tmpFrontiers.empty())
138      return true;
139
140    return false;
141  }
142
143  /// print - Convert to human readable form
144  ///
145  void print(raw_ostream &OS, const Module* = 0) const override;
146
147  /// dump - Dump the dominance frontier to dbgs().
148  void dump() const;
149};
150
151
152//===-------------------------------------
153/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
154/// used to compute a forward dominator frontiers.
155///
156class DominanceFrontier : public DominanceFrontierBase {
157  virtual void anchor();
158public:
159  static char ID; // Pass ID, replacement for typeid
160  DominanceFrontier() :
161    DominanceFrontierBase(ID, false) {
162      initializeDominanceFrontierPass(*PassRegistry::getPassRegistry());
163    }
164
165  BasicBlock *getRoot() const {
166    assert(Roots.size() == 1 && "Should always have entry node!");
167    return Roots[0];
168  }
169
170  bool runOnFunction(Function &) override {
171    Frontiers.clear();
172    DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
173    Roots = DT.getRoots();
174    assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
175    calculate(DT, DT[Roots[0]]);
176    return false;
177  }
178
179  void getAnalysisUsage(AnalysisUsage &AU) const override {
180    AU.setPreservesAll();
181    AU.addRequired<DominatorTreeWrapperPass>();
182  }
183
184  const DomSetType &calculate(const DominatorTree &DT,
185                              const DomTreeNode *Node);
186};
187
188} // End llvm namespace
189
190#endif
191