Coverage Report

Created: 2019-02-21 13:17

/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
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This is the generic implementation of the DominanceFrontier class, which
10
// calculate and holds the dominance frontier for a function for.
11
//
12
// This should be considered deprecated, don't add any more uses of this data
13
// structure.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
18
#define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
19
20
#include "llvm/ADT/GraphTraits.h"
21
#include "llvm/ADT/SmallPtrSet.h"
22
#include "llvm/Analysis/DominanceFrontier.h"
23
#include "llvm/Config/llvm-config.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
32
namespace llvm {
33
34
template <class BlockT>
35
class DFCalculateWorkObject {
36
public:
37
  using DomTreeNodeT = DomTreeNodeBase<BlockT>;
38
39
  DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
40
                        const DomTreeNodeT *PN)
41
52.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
41
37.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
41
15.4k
      : 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
49
template <class BlockT, bool IsPostDom>
50
0
void DominanceFrontierBase<BlockT, IsPostDom>::removeBlock(BlockT *BB) {
51
0
  assert(find(BB) != end() && "Block is not in DominanceFrontier!");
52
0
  for (iterator I = begin(), E = end(); I != E; ++I)
53
0
    I->second.erase(BB);
54
0
  Frontiers.erase(BB);
55
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*)
56
57
template <class BlockT, bool IsPostDom>
58
void DominanceFrontierBase<BlockT, IsPostDom>::addToFrontier(iterator I,
59
0
                                                             BlockT *Node) {
60
0
  assert(I != end() && "BB is not in DominanceFrontier!");
61
0
  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
62
0
  I->second.erase(Node);
63
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*)
64
65
template <class BlockT, bool IsPostDom>
66
void DominanceFrontierBase<BlockT, IsPostDom>::removeFromFrontier(
67
0
    iterator I, BlockT *Node) {
68
0
  assert(I != end() && "BB is not in DominanceFrontier!");
69
0
  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
70
0
  I->second.erase(Node);
71
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*)
72
73
template <class BlockT, bool IsPostDom>
74
bool DominanceFrontierBase<BlockT, IsPostDom>::compareDomSet(
75
0
    DomSetType &DS1, const DomSetType &DS2) const {
76
0
  std::set<BlockT *> tmpSet;
77
0
  for (BlockT *BB : DS2)
78
0
    tmpSet.insert(BB);
79
0
80
0
  for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
81
0
       I != E;) {
82
0
    BlockT *Node = *I++;
83
0
84
0
    if (tmpSet.erase(Node) == 0)
85
0
      // Node is in DS1 but tnot in DS2.
86
0
      return true;
87
0
  }
88
0
89
0
  if (!tmpSet.empty()) {
90
0
    // There are nodes that are in DS2 but not in DS1.
91
0
    return true;
92
0
  }
93
0
94
0
  // DS1 and DS2 matches.
95
0
  return false;
96
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
97
98
template <class BlockT, bool IsPostDom>
99
bool DominanceFrontierBase<BlockT, IsPostDom>::compare(
100
0
    DominanceFrontierBase<BlockT, IsPostDom> &Other) const {
101
0
  DomSetMapType tmpFrontiers;
102
0
  for (typename DomSetMapType::const_iterator I = Other.begin(),
103
0
                                              E = Other.end();
104
0
       I != E; ++I)
105
0
    tmpFrontiers.insert(std::make_pair(I->first, I->second));
106
0
107
0
  for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
108
0
                                        E = tmpFrontiers.end();
109
0
       I != E;) {
110
0
    BlockT *Node = I->first;
111
0
    const_iterator DFI = find(Node);
112
0
    if (DFI == end())
113
0
      return true;
114
0
115
0
    if (compareDomSet(I->second, DFI->second))
116
0
      return true;
117
0
118
0
    ++I;
119
0
    tmpFrontiers.erase(Node);
120
0
  }
121
0
122
0
  if (!tmpFrontiers.empty())
123
0
    return true;
124
0
125
0
  return false;
126
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
127
128
template <class BlockT, bool IsPostDom>
129
2
void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {
130
12
  for (const_iterator I = begin(), E = end(); I != E; 
++I10
) {
131
10
    OS << "  DomFrontier for BB ";
132
10
    if (I->first)
133
10
      I->first->printAsOperand(OS, false);
134
0
    else
135
0
      OS << " <<exit node>>";
136
10
    OS << " is:\t";
137
10
138
10
    const std::set<BlockT *> &BBs = I->second;
139
10
140
10
    for (const BlockT *BB : BBs) {
141
6
      OS << ' ';
142
6
      if (BB)
143
6
        BB->printAsOperand(OS, false);
144
0
      else
145
0
        OS << "<<exit node>>";
146
6
    }
147
10
    OS << '\n';
148
10
  }
149
2
}
llvm::DominanceFrontierBase<llvm::BasicBlock, false>::print(llvm::raw_ostream&) const
Line
Count
Source
129
2
void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {
130
12
  for (const_iterator I = begin(), E = end(); I != E; 
++I10
) {
131
10
    OS << "  DomFrontier for BB ";
132
10
    if (I->first)
133
10
      I->first->printAsOperand(OS, false);
134
0
    else
135
0
      OS << " <<exit node>>";
136
10
    OS << " is:\t";
137
10
138
10
    const std::set<BlockT *> &BBs = I->second;
139
10
140
10
    for (const BlockT *BB : BBs) {
141
6
      OS << ' ';
142
6
      if (BB)
143
6
        BB->printAsOperand(OS, false);
144
0
      else
145
0
        OS << "<<exit node>>";
146
6
    }
147
10
    OS << '\n';
148
10
  }
149
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
150
151
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
152
template <class BlockT, bool IsPostDom>
153
void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
154
  print(dbgs());
155
}
156
#endif
157
158
template <class BlockT>
159
const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
160
ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
161
34.9k
                                                const DomTreeNodeT *Node) {
162
34.9k
  BlockT *BB = Node->getBlock();
163
34.9k
  DomSetType *Result = nullptr;
164
34.9k
165
34.9k
  std::vector<DFCalculateWorkObject<BlockT>> workList;
166
34.9k
  SmallPtrSet<BlockT *, 32> visited;
167
34.9k
168
34.9k
  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
169
64.7k
  do {
170
64.7k
    DFCalculateWorkObject<BlockT> *currentW = &workList.back();
171
64.7k
    assert(currentW && "Missing work object.");
172
64.7k
173
64.7k
    BlockT *currentBB = currentW->currentBB;
174
64.7k
    BlockT *parentBB = currentW->parentBB;
175
64.7k
    const DomTreeNodeT *currentNode = currentW->Node;
176
64.7k
    const DomTreeNodeT *parentNode = currentW->parentNode;
177
64.7k
    assert(currentBB && "Invalid work object. Missing current Basic Block");
178
64.7k
    assert(currentNode && "Invalid work object. Missing current Node");
179
64.7k
    DomSetType &S = this->Frontiers[currentBB];
180
64.7k
181
64.7k
    // Visit each block only once.
182
64.7k
    if (visited.insert(currentBB).second) {
183
52.4k
      // Loop over CFG successors to calculate DFlocal[currentNode]
184
52.4k
      for (const auto Succ : children<BlockT *>(currentBB)) {
185
24.4k
        // Does Node immediately dominate this successor?
186
24.4k
        if (DT[Succ]->getIDom() != currentNode)
187
7.65k
          S.insert(Succ);
188
24.4k
      }
189
52.4k
    }
190
64.7k
191
64.7k
    // At this point, S is DFlocal.  Now we union in DFup's of our children...
192
64.7k
    // Loop through and visit the nodes that Node immediately dominates (Node's
193
64.7k
    // children in the IDomTree)
194
64.7k
    bool visitChild = false;
195
64.7k
    for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
196
64.7k
                                               NE = currentNode->end();
197
99.8k
         NI != NE; 
++NI35.0k
) {
198
35.0k
      DomTreeNodeT *IDominee = *NI;
199
35.0k
      BlockT *childBB = IDominee->getBlock();
200
35.0k
      if (visited.count(childBB) == 0) {
201
17.5k
        workList.push_back(DFCalculateWorkObject<BlockT>(
202
17.5k
            childBB, currentBB, IDominee, currentNode));
203
17.5k
        visitChild = true;
204
17.5k
      }
205
35.0k
    }
206
64.7k
207
64.7k
    // If all children are visited or there is any child then pop this block
208
64.7k
    // from the workList.
209
64.7k
    if (!visitChild) {
210
52.4k
      if (!parentBB) {
211
34.9k
        Result = &S;
212
34.9k
        break;
213
34.9k
      }
214
17.5k
215
17.5k
      typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
216
17.5k
      DomSetType &parentSet = this->Frontiers[parentBB];
217
32.2k
      for (; CDFI != CDFE; 
++CDFI14.7k
) {
218
14.7k
        if (!DT.properlyDominates(parentNode, DT[*CDFI]))
219
7.58k
          parentSet.insert(*CDFI);
220
14.7k
      }
221
17.5k
      workList.pop_back();
222
17.5k
    }
223
64.7k
224
64.7k
  } while (
!workList.empty()29.8k
);
225
34.9k
226
34.9k
  return *Result;
227
34.9k
}
llvm::ForwardDominanceFrontierBase<llvm::BasicBlock>::calculate(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&, llvm::DomTreeNodeBase<llvm::BasicBlock> const*)
Line
Count
Source
161
24.6k
                                                const DomTreeNodeT *Node) {
162
24.6k
  BlockT *BB = Node->getBlock();
163
24.6k
  DomSetType *Result = nullptr;
164
24.6k
165
24.6k
  std::vector<DFCalculateWorkObject<BlockT>> workList;
166
24.6k
  SmallPtrSet<BlockT *, 32> visited;
167
24.6k
168
24.6k
  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
169
45.9k
  do {
170
45.9k
    DFCalculateWorkObject<BlockT> *currentW = &workList.back();
171
45.9k
    assert(currentW && "Missing work object.");
172
45.9k
173
45.9k
    BlockT *currentBB = currentW->currentBB;
174
45.9k
    BlockT *parentBB = currentW->parentBB;
175
45.9k
    const DomTreeNodeT *currentNode = currentW->Node;
176
45.9k
    const DomTreeNodeT *parentNode = currentW->parentNode;
177
45.9k
    assert(currentBB && "Invalid work object. Missing current Basic Block");
178
45.9k
    assert(currentNode && "Invalid work object. Missing current Node");
179
45.9k
    DomSetType &S = this->Frontiers[currentBB];
180
45.9k
181
45.9k
    // Visit each block only once.
182
45.9k
    if (visited.insert(currentBB).second) {
183
37.0k
      // Loop over CFG successors to calculate DFlocal[currentNode]
184
37.0k
      for (const auto Succ : children<BlockT *>(currentBB)) {
185
17.0k
        // Does Node immediately dominate this successor?
186
17.0k
        if (DT[Succ]->getIDom() != currentNode)
187
5.07k
          S.insert(Succ);
188
17.0k
      }
189
37.0k
    }
190
45.9k
191
45.9k
    // At this point, S is DFlocal.  Now we union in DFup's of our children...
192
45.9k
    // Loop through and visit the nodes that Node immediately dominates (Node's
193
45.9k
    // children in the IDomTree)
194
45.9k
    bool visitChild = false;
195
45.9k
    for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
196
45.9k
                                               NE = currentNode->end();
197
70.8k
         NI != NE; 
++NI24.8k
) {
198
24.8k
      DomTreeNodeT *IDominee = *NI;
199
24.8k
      BlockT *childBB = IDominee->getBlock();
200
24.8k
      if (visited.count(childBB) == 0) {
201
12.4k
        workList.push_back(DFCalculateWorkObject<BlockT>(
202
12.4k
            childBB, currentBB, IDominee, currentNode));
203
12.4k
        visitChild = true;
204
12.4k
      }
205
24.8k
    }
206
45.9k
207
45.9k
    // If all children are visited or there is any child then pop this block
208
45.9k
    // from the workList.
209
45.9k
    if (!visitChild) {
210
37.0k
      if (!parentBB) {
211
24.6k
        Result = &S;
212
24.6k
        break;
213
24.6k
      }
214
12.4k
215
12.4k
      typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
216
12.4k
      DomSetType &parentSet = this->Frontiers[parentBB];
217
22.8k
      for (; CDFI != CDFE; 
++CDFI10.4k
) {
218
10.4k
        if (!DT.properlyDominates(parentNode, DT[*CDFI]))
219
5.62k
          parentSet.insert(*CDFI);
220
10.4k
      }
221
12.4k
      workList.pop_back();
222
12.4k
    }
223
45.9k
224
45.9k
  } while (
!workList.empty()21.3k
);
225
24.6k
226
24.6k
  return *Result;
227
24.6k
}
llvm::ForwardDominanceFrontierBase<llvm::MachineBasicBlock>::calculate(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&, llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*)
Line
Count
Source
161
10.3k
                                                const DomTreeNodeT *Node) {
162
10.3k
  BlockT *BB = Node->getBlock();
163
10.3k
  DomSetType *Result = nullptr;
164
10.3k
165
10.3k
  std::vector<DFCalculateWorkObject<BlockT>> workList;
166
10.3k
  SmallPtrSet<BlockT *, 32> visited;
167
10.3k
168
10.3k
  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
169
18.8k
  do {
170
18.8k
    DFCalculateWorkObject<BlockT> *currentW = &workList.back();
171
18.8k
    assert(currentW && "Missing work object.");
172
18.8k
173
18.8k
    BlockT *currentBB = currentW->currentBB;
174
18.8k
    BlockT *parentBB = currentW->parentBB;
175
18.8k
    const DomTreeNodeT *currentNode = currentW->Node;
176
18.8k
    const DomTreeNodeT *parentNode = currentW->parentNode;
177
18.8k
    assert(currentBB && "Invalid work object. Missing current Basic Block");
178
18.8k
    assert(currentNode && "Invalid work object. Missing current Node");
179
18.8k
    DomSetType &S = this->Frontiers[currentBB];
180
18.8k
181
18.8k
    // Visit each block only once.
182
18.8k
    if (visited.insert(currentBB).second) {
183
15.4k
      // Loop over CFG successors to calculate DFlocal[currentNode]
184
15.4k
      for (const auto Succ : children<BlockT *>(currentBB)) {
185
7.37k
        // Does Node immediately dominate this successor?
186
7.37k
        if (DT[Succ]->getIDom() != currentNode)
187
2.58k
          S.insert(Succ);
188
7.37k
      }
189
15.4k
    }
190
18.8k
191
18.8k
    // At this point, S is DFlocal.  Now we union in DFup's of our children...
192
18.8k
    // Loop through and visit the nodes that Node immediately dominates (Node's
193
18.8k
    // children in the IDomTree)
194
18.8k
    bool visitChild = false;
195
18.8k
    for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
196
18.8k
                                               NE = currentNode->end();
197
29.0k
         NI != NE; 
++NI10.2k
) {
198
10.2k
      DomTreeNodeT *IDominee = *NI;
199
10.2k
      BlockT *childBB = IDominee->getBlock();
200
10.2k
      if (visited.count(childBB) == 0) {
201
5.11k
        workList.push_back(DFCalculateWorkObject<BlockT>(
202
5.11k
            childBB, currentBB, IDominee, currentNode));
203
5.11k
        visitChild = true;
204
5.11k
      }
205
10.2k
    }
206
18.8k
207
18.8k
    // If all children are visited or there is any child then pop this block
208
18.8k
    // from the workList.
209
18.8k
    if (!visitChild) {
210
15.4k
      if (!parentBB) {
211
10.3k
        Result = &S;
212
10.3k
        break;
213
10.3k
      }
214
5.11k
215
5.11k
      typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
216
5.11k
      DomSetType &parentSet = this->Frontiers[parentBB];
217
9.38k
      for (; CDFI != CDFE; 
++CDFI4.26k
) {
218
4.26k
        if (!DT.properlyDominates(parentNode, DT[*CDFI]))
219
1.96k
          parentSet.insert(*CDFI);
220
4.26k
      }
221
5.11k
      workList.pop_back();
222
5.11k
    }
223
18.8k
224
18.8k
  } while (
!workList.empty()8.49k
);
225
10.3k
226
10.3k
  return *Result;
227
10.3k
}
228
229
} // end namespace llvm
230
231
#endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H