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