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