DominanceFrontierImpl.h revision 37ed9c199ca639565f6ce88105f9e39e898d82d0 
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 is the generic implementation of the DominanceFrontier class, which
11// calculate and holds the dominance frontier for a function for.
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_DOMINANCEFRONTIERIMPL_H
19#define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
20
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/Support/Debug.h"
23
24namespace llvm {
25
26namespace {
27template <class BlockT>
28class DFCalculateWorkObject {
29public:
30  typedef DomTreeNodeBase<BlockT> DomTreeNodeT;
31
32  DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
33                        const DomTreeNodeT *PN)
34      : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
35  BlockT *currentBB;
36  BlockT *parentBB;
37  const DomTreeNodeT *Node;
38  const DomTreeNodeT *parentNode;
39};
40}
41
42template <class BlockT>
43void DominanceFrontierBase<BlockT>::removeBlock(BlockT *BB) {
44  assert(find(BB) != end() && "Block is not in DominanceFrontier!");
45  for (iterator I = begin(), E = end(); I != E; ++I)
46    I->second.erase(BB);
47  Frontiers.erase(BB);
48}
49
50template <class BlockT>
51void DominanceFrontierBase<BlockT>::addToFrontier(iterator I,
52                                                  BlockT *Node) {
53  assert(I != end() && "BB is not in DominanceFrontier!");
54  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
55  I->second.erase(Node);
56}
57
58template <class BlockT>
59void DominanceFrontierBase<BlockT>::removeFromFrontier(iterator I,
60                                                       BlockT *Node) {
61  assert(I != end() && "BB is not in DominanceFrontier!");
62  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
63  I->second.erase(Node);
64}
65
66template <class BlockT>
67bool DominanceFrontierBase<BlockT>::compareDomSet(DomSetType &DS1,
68                                                  const DomSetType &DS2) const {
69  std::set<BlockT *> tmpSet;
70  for (BlockT *BB : DS2)
71    tmpSet.insert(BB);
72
73  for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
74       I != E;) {
75    BlockT *Node = *I++;
76
77    if (tmpSet.erase(Node) == 0)
78      // Node is in DS1 but tnot in DS2.
79      return true;
80  }
81
82  if (!tmpSet.empty()) {
83    // There are nodes that are in DS2 but not in DS1.
84    return true;
85  }
86
87  // DS1 and DS2 matches.
88  return false;
89}
90
91template <class BlockT>
92bool DominanceFrontierBase<BlockT>::compare(
93    DominanceFrontierBase<BlockT> &Other) const {
94  DomSetMapType tmpFrontiers;
95  for (typename DomSetMapType::const_iterator I = Other.begin(),
96                                              E = Other.end();
97       I != E; ++I)
98    tmpFrontiers.insert(std::make_pair(I->first, I->second));
99
100  for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
101                                        E = tmpFrontiers.end();
102       I != E;) {
103    BlockT *Node = I->first;
104    const_iterator DFI = find(Node);
105    if (DFI == end())
106      return true;
107
108    if (compareDomSet(I->second, DFI->second))
109      return true;
110
111    ++I;
112    tmpFrontiers.erase(Node);
113  }
114
115  if (!tmpFrontiers.empty())
116    return true;
117
118  return false;
119}
120
121template <class BlockT>
122void DominanceFrontierBase<BlockT>::print(raw_ostream &OS) const {
123  for (const_iterator I = begin(), E = end(); I != E; ++I) {
124    OS << "  DomFrontier for BB ";
125    if (I->first)
126      I->first->printAsOperand(OS, false);
127    else
128      OS << " <<exit node>>";
129    OS << " is:\t";
130
131    const std::set<BlockT *> &BBs = I->second;
132
133    for (const BlockT *BB : BBs) {
134      OS << ' ';
135      if (BB)
136        BB->printAsOperand(OS, false);
137      else
138        OS << "<<exit node>>";
139    }
140    OS << '\n';
141  }
142}
143
144#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
145template <class BlockT>
146void DominanceFrontierBase<BlockT>::dump() const {
147  print(dbgs());
148}
149#endif
150
151template <class BlockT>
152const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
153ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
154                                                const DomTreeNodeT *Node) {
155  BlockT *BB = Node->getBlock();
156  DomSetType *Result = nullptr;
157
158  std::vector<DFCalculateWorkObject<BlockT>> workList;
159  SmallPtrSet<BlockT *, 32> visited;
160
161  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
162  do {
163    DFCalculateWorkObject<BlockT> *currentW = &workList.back();
164    assert(currentW && "Missing work object.");
165
166    BlockT *currentBB = currentW->currentBB;
167    BlockT *parentBB = currentW->parentBB;
168    const DomTreeNodeT *currentNode = currentW->Node;
169    const DomTreeNodeT *parentNode = currentW->parentNode;
170    assert(currentBB && "Invalid work object. Missing current Basic Block");
171    assert(currentNode && "Invalid work object. Missing current Node");
172    DomSetType &S = this->Frontiers[currentBB];
173
174    // Visit each block only once.
175    if (visited.insert(currentBB).second) {
176      // Loop over CFG successors to calculate DFlocal[currentNode]
177      for (auto SI = BlockTraits::child_begin(currentBB),
178                SE = BlockTraits::child_end(currentBB);
179           SI != SE; ++SI) {
180        // Does Node immediately dominate this successor?
181        if (DT[*SI]->getIDom() != currentNode)
182          S.insert(*SI);
183      }
184    }
185
186    // At this point, S is DFlocal.  Now we union in DFup's of our children...
187    // Loop through and visit the nodes that Node immediately dominates (Node's
188    // children in the IDomTree)
189    bool visitChild = false;
190    for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
191                                               NE = currentNode->end();
192         NI != NE; ++NI) {
193      DomTreeNodeT *IDominee = *NI;
194      BlockT *childBB = IDominee->getBlock();
195      if (visited.count(childBB) == 0) {
196        workList.push_back(DFCalculateWorkObject<BlockT>(
197            childBB, currentBB, IDominee, currentNode));
198        visitChild = true;
199      }
200    }
201
202    // If all children are visited or there is any child then pop this block
203    // from the workList.
204    if (!visitChild) {
205      if (!parentBB) {
206        Result = &S;
207        break;
208      }
209
210      typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
211      DomSetType &parentSet = this->Frontiers[parentBB];
212      for (; CDFI != CDFE; ++CDFI) {
213        if (!DT.properlyDominates(parentNode, DT[*CDFI]))
214          parentSet.insert(*CDFI);
215      }
216      workList.pop_back();
217    }
218
219  } while (!workList.empty());
220
221  return *Result;
222}
223
224} // End llvm namespace
225
226#endif
227