Coverage Report

Created: 2018-07-12 09:57

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