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/Analysis/DominanceFrontier.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/GenericDomTree.h"
25
26namespace llvm {
27
28template <class BlockT>
29class DFCalculateWorkObject {
30public:
31  typedef DomTreeNodeBase<BlockT> DomTreeNodeT;
32
33  DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
34                        const DomTreeNodeT *PN)
35      : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
36  BlockT *currentBB;
37  BlockT *parentBB;
38  const DomTreeNodeT *Node;
39  const DomTreeNodeT *parentNode;
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 (const auto Succ : children<BlockT *>(currentBB)) {
178        // Does Node immediately dominate this successor?
179        if (DT[Succ]->getIDom() != currentNode)
180          S.insert(Succ);
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