Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Support/GenericDomTree.h
Line
Count
Source (jump to first uncovered line)
1
//===- GenericDomTree.h - Generic dominator trees for graphs ----*- 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
/// \file
9
///
10
/// This file defines a set of templates that efficiently compute a dominator
11
/// tree over a generic graph. This is used typically in LLVM for fast
12
/// dominance queries on the CFG, but is fully generic w.r.t. the underlying
13
/// graph types.
14
///
15
/// Unlike ADT/* graph algorithms, generic dominator tree has more requirements
16
/// on the graph's NodeRef. The NodeRef should be a pointer and,
17
/// NodeRef->getParent() must return the parent node that is also a pointer.
18
///
19
/// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
20
///
21
//===----------------------------------------------------------------------===//
22
23
#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
24
#define LLVM_SUPPORT_GENERICDOMTREE_H
25
26
#include "llvm/ADT/DenseMap.h"
27
#include "llvm/ADT/GraphTraits.h"
28
#include "llvm/ADT/PointerIntPair.h"
29
#include "llvm/ADT/STLExtras.h"
30
#include "llvm/ADT/SmallPtrSet.h"
31
#include "llvm/ADT/SmallVector.h"
32
#include "llvm/Support/CFGUpdate.h"
33
#include "llvm/Support/raw_ostream.h"
34
#include <algorithm>
35
#include <cassert>
36
#include <cstddef>
37
#include <iterator>
38
#include <memory>
39
#include <type_traits>
40
#include <utility>
41
#include <vector>
42
43
namespace llvm {
44
45
template <typename NodeT, bool IsPostDom>
46
class DominatorTreeBase;
47
48
namespace DomTreeBuilder {
49
template <typename DomTreeT>
50
struct SemiNCAInfo;
51
}  // namespace DomTreeBuilder
52
53
/// Base class for the actual dominator tree node.
54
template <class NodeT> class DomTreeNodeBase {
55
  friend class PostDominatorTree;
56
  friend class DominatorTreeBase<NodeT, false>;
57
  friend class DominatorTreeBase<NodeT, true>;
58
  friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
59
  friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
60
61
  NodeT *TheBB;
62
  DomTreeNodeBase *IDom;
63
  unsigned Level;
64
  std::vector<DomTreeNodeBase *> Children;
65
  mutable unsigned DFSNumIn = ~0;
66
  mutable unsigned DFSNumOut = ~0;
67
68
 public:
69
  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
70
91.8M
      : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::DomTreeNodeBase(llvm::MachineBasicBlock*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*)
Line
Count
Source
70
22.2M
      : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
llvm::DomTreeNodeBase<llvm::BasicBlock>::DomTreeNodeBase(llvm::BasicBlock*, llvm::DomTreeNodeBase<llvm::BasicBlock>*)
Line
Count
Source
70
69.5M
      : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
llvm::DomTreeNodeBase<llvm::VPBlockBase>::DomTreeNodeBase(llvm::VPBlockBase*, llvm::DomTreeNodeBase<llvm::VPBlockBase>*)
Line
Count
Source
70
135
      : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
llvm::DomTreeNodeBase<clang::CFGBlock>::DomTreeNodeBase(clang::CFGBlock*, llvm::DomTreeNodeBase<clang::CFGBlock>*)
Line
Count
Source
70
722
      : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
71
72
  using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
73
  using const_iterator =
74
      typename std::vector<DomTreeNodeBase *>::const_iterator;
75
76
46.9M
  iterator begin() { return Children.begin(); }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::begin()
Line
Count
Source
76
6.30M
  iterator begin() { return Children.begin(); }
llvm::DomTreeNodeBase<llvm::BasicBlock>::begin()
Line
Count
Source
76
40.6M
  iterator begin() { return Children.begin(); }
llvm::DomTreeNodeBase<clang::CFGBlock>::begin()
Line
Count
Source
76
646
  iterator begin() { return Children.begin(); }
77
62.5M
  iterator end() { return Children.end(); }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::end()
Line
Count
Source
77
11.5M
  iterator end() { return Children.end(); }
llvm::DomTreeNodeBase<llvm::BasicBlock>::end()
Line
Count
Source
77
50.9M
  iterator end() { return Children.end(); }
llvm::DomTreeNodeBase<clang::CFGBlock>::end()
Line
Count
Source
77
646
  iterator end() { return Children.end(); }
78
80.0M
  const_iterator begin() const { return Children.begin(); }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::begin() const
Line
Count
Source
78
15.2M
  const_iterator begin() const { return Children.begin(); }
llvm::DomTreeNodeBase<llvm::BasicBlock>::begin() const
Line
Count
Source
78
64.8M
  const_iterator begin() const { return Children.begin(); }
llvm::DomTreeNodeBase<llvm::VPBlockBase>::begin() const
Line
Count
Source
78
111
  const_iterator begin() const { return Children.begin(); }
llvm::DomTreeNodeBase<clang::CFGBlock>::begin() const
Line
Count
Source
78
568
  const_iterator begin() const { return Children.begin(); }
79
148M
  const_iterator end() const { return Children.end(); }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::end() const
Line
Count
Source
79
28.0M
  const_iterator end() const { return Children.end(); }
llvm::DomTreeNodeBase<llvm::BasicBlock>::end() const
Line
Count
Source
79
120M
  const_iterator end() const { return Children.end(); }
llvm::DomTreeNodeBase<llvm::VPBlockBase>::end() const
Line
Count
Source
79
197
  const_iterator end() const { return Children.end(); }
llvm::DomTreeNodeBase<clang::CFGBlock>::end() const
Line
Count
Source
79
1.03k
  const_iterator end() const { return Children.end(); }
80
81
201M
  NodeT *getBlock() const { return TheBB; }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::getBlock() const
Line
Count
Source
81
62.1M
  NodeT *getBlock() const { return TheBB; }
llvm::DomTreeNodeBase<llvm::BasicBlock>::getBlock() const
Line
Count
Source
81
139M
  NodeT *getBlock() const { return TheBB; }
llvm::DomTreeNodeBase<llvm::VPBlockBase>::getBlock() const
Line
Count
Source
81
189
  NodeT *getBlock() const { return TheBB; }
llvm::DomTreeNodeBase<clang::CFGBlock>::getBlock() const
Line
Count
Source
81
1.10k
  NodeT *getBlock() const { return TheBB; }
82
422M
  DomTreeNodeBase *getIDom() const { return IDom; }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::getIDom() const
Line
Count
Source
82
100M
  DomTreeNodeBase *getIDom() const { return IDom; }
llvm::DomTreeNodeBase<llvm::BasicBlock>::getIDom() const
Line
Count
Source
82
321M
  DomTreeNodeBase *getIDom() const { return IDom; }
llvm::DomTreeNodeBase<llvm::VPBlockBase>::getIDom() const
Line
Count
Source
82
472
  DomTreeNodeBase *getIDom() const { return IDom; }
llvm::DomTreeNodeBase<clang::CFGBlock>::getIDom() const
Line
Count
Source
82
181
  DomTreeNodeBase *getIDom() const { return IDom; }
83
385M
  unsigned getLevel() const { return Level; }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::getLevel() const
Line
Count
Source
83
96.7M
  unsigned getLevel() const { return Level; }
llvm::DomTreeNodeBase<llvm::BasicBlock>::getLevel() const
Line
Count
Source
83
288M
  unsigned getLevel() const { return Level; }
llvm::DomTreeNodeBase<llvm::VPBlockBase>::getLevel() const
Line
Count
Source
83
368
  unsigned getLevel() const { return Level; }
llvm::DomTreeNodeBase<clang::CFGBlock>::getLevel() const
Line
Count
Source
83
816
  unsigned getLevel() const { return Level; }
84
85
13.2M
  const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::getChildren() const
Line
Count
Source
85
8.99M
  const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
llvm::DomTreeNodeBase<llvm::BasicBlock>::getChildren() const
Line
Count
Source
85
4.20M
  const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
86
87
  std::unique_ptr<DomTreeNodeBase> addChild(
88
76.7M
      std::unique_ptr<DomTreeNodeBase> C) {
89
76.7M
    Children.push_back(C.get());
90
76.7M
    return C;
91
76.7M
  }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::addChild(std::__1::unique_ptr<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>, std::__1::default_delete<llvm::DomTreeNodeBase<llvm::MachineBasicBlock> > >)
Line
Count
Source
88
18.1M
      std::unique_ptr<DomTreeNodeBase> C) {
89
18.1M
    Children.push_back(C.get());
90
18.1M
    return C;
91
18.1M
  }
llvm::DomTreeNodeBase<llvm::BasicBlock>::addChild(std::__1::unique_ptr<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::__1::default_delete<llvm::DomTreeNodeBase<llvm::BasicBlock> > >)
Line
Count
Source
88
58.5M
      std::unique_ptr<DomTreeNodeBase> C) {
89
58.5M
    Children.push_back(C.get());
90
58.5M
    return C;
91
58.5M
  }
llvm::DomTreeNodeBase<llvm::VPBlockBase>::addChild(std::__1::unique_ptr<llvm::DomTreeNodeBase<llvm::VPBlockBase>, std::__1::default_delete<llvm::DomTreeNodeBase<llvm::VPBlockBase> > >)
Line
Count
Source
88
107
      std::unique_ptr<DomTreeNodeBase> C) {
89
107
    Children.push_back(C.get());
90
107
    return C;
91
107
  }
llvm::DomTreeNodeBase<clang::CFGBlock>::addChild(std::__1::unique_ptr<llvm::DomTreeNodeBase<clang::CFGBlock>, std::__1::default_delete<llvm::DomTreeNodeBase<clang::CFGBlock> > >)
Line
Count
Source
88
607
      std::unique_ptr<DomTreeNodeBase> C) {
89
607
    Children.push_back(C.get());
90
607
    return C;
91
607
  }
92
93
27.3k
  size_t getNumChildren() const { return Children.size(); }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::getNumChildren() const
Line
Count
Source
93
13.8k
  size_t getNumChildren() const { return Children.size(); }
llvm::DomTreeNodeBase<llvm::BasicBlock>::getNumChildren() const
Line
Count
Source
93
13.4k
  size_t getNumChildren() const { return Children.size(); }
94
95
0
  void clearAllChildren() { Children.clear(); }
Unexecuted instantiation: llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::clearAllChildren()
Unexecuted instantiation: llvm::DomTreeNodeBase<llvm::BasicBlock>::clearAllChildren()
96
97
6.71k
  bool compare(const DomTreeNodeBase *Other) const {
98
6.71k
    if (getNumChildren() != Other->getNumChildren())
99
1
      return true;
100
6.71k
101
6.71k
    if (Level != Other->Level) 
return true0
;
102
6.71k
103
6.71k
    SmallPtrSet<const NodeT *, 4> OtherChildren;
104
6.71k
    for (const DomTreeNodeBase *I : *Other) {
105
5.99k
      const NodeT *Nd = I->getBlock();
106
5.99k
      OtherChildren.insert(Nd);
107
5.99k
    }
108
6.71k
109
6.71k
    for (const DomTreeNodeBase *I : *this) {
110
5.99k
      const NodeT *N = I->getBlock();
111
5.99k
      if (OtherChildren.count(N) == 0)
112
0
        return true;
113
5.99k
    }
114
6.71k
    return false;
115
6.71k
  }
Unexecuted instantiation: llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::compare(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
llvm::DomTreeNodeBase<llvm::BasicBlock>::compare(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
97
6.71k
  bool compare(const DomTreeNodeBase *Other) const {
98
6.71k
    if (getNumChildren() != Other->getNumChildren())
99
1
      return true;
100
6.71k
101
6.71k
    if (Level != Other->Level) 
return true0
;
102
6.71k
103
6.71k
    SmallPtrSet<const NodeT *, 4> OtherChildren;
104
6.71k
    for (const DomTreeNodeBase *I : *Other) {
105
5.99k
      const NodeT *Nd = I->getBlock();
106
5.99k
      OtherChildren.insert(Nd);
107
5.99k
    }
108
6.71k
109
6.71k
    for (const DomTreeNodeBase *I : *this) {
110
5.99k
      const NodeT *N = I->getBlock();
111
5.99k
      if (OtherChildren.count(N) == 0)
112
0
        return true;
113
5.99k
    }
114
6.71k
    return false;
115
6.71k
  }
116
117
14.5M
  void setIDom(DomTreeNodeBase *NewIDom) {
118
14.5M
    assert(IDom && "No immediate dominator?");
119
14.5M
    if (IDom == NewIDom) 
return13.5M
;
120
1.01M
121
1.01M
    auto I = find(IDom->Children, this);
122
1.01M
    assert(I != IDom->Children.end() &&
123
1.01M
           "Not in immediate dominator children set!");
124
1.01M
    // I am no longer your child...
125
1.01M
    IDom->Children.erase(I);
126
1.01M
127
1.01M
    // Switch to new dominator
128
1.01M
    IDom = NewIDom;
129
1.01M
    IDom->Children.push_back(this);
130
1.01M
131
1.01M
    UpdateLevel();
132
1.01M
  }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::setIDom(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*)
Line
Count
Source
117
23.4k
  void setIDom(DomTreeNodeBase *NewIDom) {
118
23.4k
    assert(IDom && "No immediate dominator?");
119
23.4k
    if (IDom == NewIDom) 
return0
;
120
23.4k
121
23.4k
    auto I = find(IDom->Children, this);
122
23.4k
    assert(I != IDom->Children.end() &&
123
23.4k
           "Not in immediate dominator children set!");
124
23.4k
    // I am no longer your child...
125
23.4k
    IDom->Children.erase(I);
126
23.4k
127
23.4k
    // Switch to new dominator
128
23.4k
    IDom = NewIDom;
129
23.4k
    IDom->Children.push_back(this);
130
23.4k
131
23.4k
    UpdateLevel();
132
23.4k
  }
llvm::DomTreeNodeBase<llvm::BasicBlock>::setIDom(llvm::DomTreeNodeBase<llvm::BasicBlock>*)
Line
Count
Source
117
14.4M
  void setIDom(DomTreeNodeBase *NewIDom) {
118
14.4M
    assert(IDom && "No immediate dominator?");
119
14.4M
    if (IDom == NewIDom) 
return13.5M
;
120
993k
121
993k
    auto I = find(IDom->Children, this);
122
993k
    assert(I != IDom->Children.end() &&
123
993k
           "Not in immediate dominator children set!");
124
993k
    // I am no longer your child...
125
993k
    IDom->Children.erase(I);
126
993k
127
993k
    // Switch to new dominator
128
993k
    IDom = NewIDom;
129
993k
    IDom->Children.push_back(this);
130
993k
131
993k
    UpdateLevel();
132
993k
  }
133
134
  /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
135
  /// in the dominator tree. They are only guaranteed valid if
136
  /// updateDFSNumbers() has been called.
137
24.8M
  unsigned getDFSNumIn() const { return DFSNumIn; }
llvm::DomTreeNodeBase<llvm::BasicBlock>::getDFSNumIn() const
Line
Count
Source
137
24.8M
  unsigned getDFSNumIn() const { return DFSNumIn; }
Unexecuted instantiation: llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::getDFSNumIn() const
llvm::DomTreeNodeBase<clang::CFGBlock>::getDFSNumIn() const
Line
Count
Source
137
251
  unsigned getDFSNumIn() const { return DFSNumIn; }
138
6.90M
  unsigned getDFSNumOut() const { return DFSNumOut; }
llvm::DomTreeNodeBase<llvm::BasicBlock>::getDFSNumOut() const
Line
Count
Source
138
6.90M
  unsigned getDFSNumOut() const { return DFSNumOut; }
Unexecuted instantiation: llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::getDFSNumOut() const
Unexecuted instantiation: llvm::DomTreeNodeBase<clang::CFGBlock>::getDFSNumOut() const
139
140
private:
141
  // Return true if this node is dominated by other. Use this only if DFS info
142
  // is valid.
143
23.6M
  bool DominatedBy(const DomTreeNodeBase *other) const {
144
23.6M
    return this->DFSNumIn >= other->DFSNumIn &&
145
23.6M
           
this->DFSNumOut <= other->DFSNumOut16.5M
;
146
23.6M
  }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::DominatedBy(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Line
Count
Source
143
8.65M
  bool DominatedBy(const DomTreeNodeBase *other) const {
144
8.65M
    return this->DFSNumIn >= other->DFSNumIn &&
145
8.65M
           
this->DFSNumOut <= other->DFSNumOut7.56M
;
146
8.65M
  }
llvm::DomTreeNodeBase<llvm::BasicBlock>::DominatedBy(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
143
15.0M
  bool DominatedBy(const DomTreeNodeBase *other) const {
144
15.0M
    return this->DFSNumIn >= other->DFSNumIn &&
145
15.0M
           
this->DFSNumOut <= other->DFSNumOut9.01M
;
146
15.0M
  }
Unexecuted instantiation: llvm::DomTreeNodeBase<llvm::VPBlockBase>::DominatedBy(llvm::DomTreeNodeBase<llvm::VPBlockBase> const*) const
147
148
1.01M
  void UpdateLevel() {
149
1.01M
    assert(IDom);
150
1.01M
    if (Level == IDom->Level + 1) 
return5
;
151
1.01M
152
1.01M
    SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
153
1.01M
154
14.1M
    while (!WorkStack.empty()) {
155
13.1M
      DomTreeNodeBase *Current = WorkStack.pop_back_val();
156
13.1M
      Current->Level = Current->IDom->Level + 1;
157
13.1M
158
13.1M
      for (DomTreeNodeBase *C : *Current) {
159
12.1M
        assert(C->IDom);
160
12.1M
        if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
161
12.1M
      }
162
13.1M
    }
163
1.01M
  }
llvm::DomTreeNodeBase<llvm::MachineBasicBlock>::UpdateLevel()
Line
Count
Source
148
23.4k
  void UpdateLevel() {
149
23.4k
    assert(IDom);
150
23.4k
    if (Level == IDom->Level + 1) 
return0
;
151
23.4k
152
23.4k
    SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
153
23.4k
154
202k
    while (!WorkStack.empty()) {
155
179k
      DomTreeNodeBase *Current = WorkStack.pop_back_val();
156
179k
      Current->Level = Current->IDom->Level + 1;
157
179k
158
179k
      for (DomTreeNodeBase *C : *Current) {
159
155k
        assert(C->IDom);
160
155k
        if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
161
155k
      }
162
179k
    }
163
23.4k
  }
llvm::DomTreeNodeBase<llvm::BasicBlock>::UpdateLevel()
Line
Count
Source
148
993k
  void UpdateLevel() {
149
993k
    assert(IDom);
150
993k
    if (Level == IDom->Level + 1) 
return5
;
151
993k
152
993k
    SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
153
993k
154
13.9M
    while (!WorkStack.empty()) {
155
12.9M
      DomTreeNodeBase *Current = WorkStack.pop_back_val();
156
12.9M
      Current->Level = Current->IDom->Level + 1;
157
12.9M
158
12.9M
      for (DomTreeNodeBase *C : *Current) {
159
11.9M
        assert(C->IDom);
160
11.9M
        if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
161
11.9M
      }
162
12.9M
    }
163
993k
  }
164
};
165
166
template <class NodeT>
167
183
raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
168
183
  if (Node->getBlock())
169
167
    Node->getBlock()->printAsOperand(O, false);
170
16
  else
171
16
    O << " <<exit node>>";
172
183
173
183
  O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
174
183
    << Node->getLevel() << "]\n";
175
183
176
183
  return O;
177
183
}
llvm::raw_ostream& llvm::operator<<<llvm::BasicBlock>(llvm::raw_ostream&, llvm::DomTreeNodeBase<llvm::BasicBlock> const*)
Line
Count
Source
167
183
raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
168
183
  if (Node->getBlock())
169
167
    Node->getBlock()->printAsOperand(O, false);
170
16
  else
171
16
    O << " <<exit node>>";
172
183
173
183
  O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
174
183
    << Node->getLevel() << "]\n";
175
183
176
183
  return O;
177
183
}
Unexecuted instantiation: llvm::raw_ostream& llvm::operator<<<llvm::MachineBasicBlock>(llvm::raw_ostream&, llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*)
Unexecuted instantiation: llvm::raw_ostream& llvm::operator<<<clang::CFGBlock>(llvm::raw_ostream&, llvm::DomTreeNodeBase<clang::CFGBlock> const*)
178
179
template <class NodeT>
180
void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
181
183
                  unsigned Lev) {
182
183
  O.indent(2 * Lev) << "[" << Lev << "] " << N;
183
183
  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
184
183
                                                       E = N->end();
185
339
       I != E; 
++I156
)
186
156
    PrintDomTree<NodeT>(*I, O, Lev + 1);
187
183
}
void llvm::PrintDomTree<llvm::BasicBlock>(llvm::DomTreeNodeBase<llvm::BasicBlock> const*, llvm::raw_ostream&, unsigned int)
Line
Count
Source
181
183
                  unsigned Lev) {
182
183
  O.indent(2 * Lev) << "[" << Lev << "] " << N;
183
183
  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
184
183
                                                       E = N->end();
185
339
       I != E; 
++I156
)
186
156
    PrintDomTree<NodeT>(*I, O, Lev + 1);
187
183
}
Unexecuted instantiation: void llvm::PrintDomTree<llvm::MachineBasicBlock>(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*, llvm::raw_ostream&, unsigned int)
Unexecuted instantiation: void llvm::PrintDomTree<clang::CFGBlock>(llvm::DomTreeNodeBase<clang::CFGBlock> const*, llvm::raw_ostream&, unsigned int)
188
189
namespace DomTreeBuilder {
190
// The routines below are provided in a separate header but referenced here.
191
template <typename DomTreeT>
192
void Calculate(DomTreeT &DT);
193
194
template <typename DomTreeT>
195
void CalculateWithUpdates(DomTreeT &DT,
196
                          ArrayRef<typename DomTreeT::UpdateType> Updates);
197
198
template <typename DomTreeT>
199
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
200
                typename DomTreeT::NodePtr To);
201
202
template <typename DomTreeT>
203
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
204
                typename DomTreeT::NodePtr To);
205
206
template <typename DomTreeT>
207
void ApplyUpdates(DomTreeT &DT,
208
                  ArrayRef<typename DomTreeT::UpdateType> Updates);
209
210
template <typename DomTreeT>
211
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
212
}  // namespace DomTreeBuilder
213
214
/// Core dominator tree base class.
215
///
216
/// This class is a generic template over graph nodes. It is instantiated for
217
/// various graphs in the LLVM IR or in the code generator.
218
template <typename NodeT, bool IsPostDom>
219
class DominatorTreeBase {
220
 public:
221
  static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
222
                "Currently DominatorTreeBase supports only pointer nodes");
223
  using NodeType = NodeT;
224
  using NodePtr = NodeT *;
225
  using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
226
  static_assert(std::is_pointer<ParentPtr>::value,
227
                "Currently NodeT's parent must be a pointer type");
228
  using ParentType = typename std::remove_pointer<ParentPtr>::type;
229
  static constexpr bool IsPostDominator = IsPostDom;
230
231
  using UpdateType = cfg::Update<NodePtr>;
232
  using UpdateKind = cfg::UpdateKind;
233
  static constexpr UpdateKind Insert = UpdateKind::Insert;
234
  static constexpr UpdateKind Delete = UpdateKind::Delete;
235
236
  enum class VerificationLevel { Fast, Basic, Full };
237
238
protected:
239
  // Dominators always have a single root, postdominators can have more.
240
  SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
241
242
  using DomTreeNodeMapType =
243
     DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
244
  DomTreeNodeMapType DomTreeNodes;
245
  DomTreeNodeBase<NodeT> *RootNode;
246
  ParentPtr Parent = nullptr;
247
248
  mutable bool DFSInfoValid = false;
249
  mutable unsigned int SlowQueries = 0;
250
251
  friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
252
253
 public:
254
3.91M
  DominatorTreeBase() {}
llvm::DominatorTreeBase<llvm::BasicBlock, false>::DominatorTreeBase()
Line
Count
Source
254
1.15M
  DominatorTreeBase() {}
llvm::DominatorTreeBase<llvm::BasicBlock, true>::DominatorTreeBase()
Line
Count
Source
254
30.0k
  DominatorTreeBase() {}
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::DominatorTreeBase()
Line
Count
Source
254
2.61M
  DominatorTreeBase() {}
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::DominatorTreeBase()
Line
Count
Source
254
109k
  DominatorTreeBase() {}
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::DominatorTreeBase()
Line
Count
Source
254
29
  DominatorTreeBase() {}
llvm::DominatorTreeBase<clang::CFGBlock, false>::DominatorTreeBase()
Line
Count
Source
254
8
  DominatorTreeBase() {}
llvm::DominatorTreeBase<clang::CFGBlock, true>::DominatorTreeBase()
Line
Count
Source
254
107
  DominatorTreeBase() {}
255
256
  DominatorTreeBase(DominatorTreeBase &&Arg)
257
      : Roots(std::move(Arg.Roots)),
258
        DomTreeNodes(std::move(Arg.DomTreeNodes)),
259
        RootNode(Arg.RootNode),
260
        Parent(Arg.Parent),
261
        DFSInfoValid(Arg.DFSInfoValid),
262
20.5k
        SlowQueries(Arg.SlowQueries) {
263
20.5k
    Arg.wipe();
264
20.5k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::DominatorTreeBase(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>&&)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::DominatorTreeBase(llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>&&)
llvm::DominatorTreeBase<llvm::BasicBlock, false>::DominatorTreeBase(llvm::DominatorTreeBase<llvm::BasicBlock, false>&&)
Line
Count
Source
262
18.0k
        SlowQueries(Arg.SlowQueries) {
263
18.0k
    Arg.wipe();
264
18.0k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::DominatorTreeBase(llvm::DominatorTreeBase<llvm::BasicBlock, true>&&)
Line
Count
Source
262
2.50k
        SlowQueries(Arg.SlowQueries) {
263
2.50k
    Arg.wipe();
264
2.50k
  }
265
266
0
  DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
267
0
    Roots = std::move(RHS.Roots);
268
0
    DomTreeNodes = std::move(RHS.DomTreeNodes);
269
0
    RootNode = RHS.RootNode;
270
0
    Parent = RHS.Parent;
271
0
    DFSInfoValid = RHS.DFSInfoValid;
272
0
    SlowQueries = RHS.SlowQueries;
273
0
    RHS.wipe();
274
0
    return *this;
275
0
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::operator=(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>&&)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::operator=(llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>&&)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, false>::operator=(llvm::DominatorTreeBase<llvm::BasicBlock, false>&&)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::operator=(llvm::DominatorTreeBase<llvm::BasicBlock, true>&&)
276
277
  DominatorTreeBase(const DominatorTreeBase &) = delete;
278
  DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
279
280
  /// getRoots - Return the root blocks of the current CFG.  This may include
281
  /// multiple blocks if we are computing post dominators.  For forward
282
  /// dominators, this will always be a single block (the entry node).
283
  ///
284
25.3k
  const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::getRoots() const
llvm::DominatorTreeBase<llvm::BasicBlock, true>::getRoots() const
Line
Count
Source
284
25.3k
  const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::getRoots() const
llvm::DominatorTreeBase<llvm::BasicBlock, false>::getRoots() const
Line
Count
Source
284
1
  const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
285
286
  /// isPostDominator - Returns true if analysis based of postdoms
287
  ///
288
2.66M
  bool isPostDominator() const { return IsPostDominator; }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::isPostDominator() const
Line
Count
Source
288
278k
  bool isPostDominator() const { return IsPostDominator; }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::isPostDominator() const
Line
Count
Source
288
2.25M
  bool isPostDominator() const { return IsPostDominator; }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::isPostDominator() const
Line
Count
Source
288
123k
  bool isPostDominator() const { return IsPostDominator; }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::isPostDominator() const
Line
Count
Source
288
4.86k
  bool isPostDominator() const { return IsPostDominator; }
289
290
  /// compare - Return false if the other dominator tree base matches this
291
  /// dominator tree base. Otherwise return true.
292
723
  bool compare(const DominatorTreeBase &Other) const {
293
723
    if (Parent != Other.Parent) 
return true0
;
294
723
295
723
    if (Roots.size() != Other.Roots.size())
296
0
      return true;
297
723
298
723
    if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
299
0
      return true;
300
723
301
723
    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
302
723
    if (DomTreeNodes.size() != OtherDomTreeNodes.size())
303
1
      return true;
304
722
305
6.71k
    
for (const auto &DomTreeNode : DomTreeNodes)722
{
306
6.71k
      NodeT *BB = DomTreeNode.first;
307
6.71k
      typename DomTreeNodeMapType::const_iterator OI =
308
6.71k
          OtherDomTreeNodes.find(BB);
309
6.71k
      if (OI == OtherDomTreeNodes.end())
310
0
        return true;
311
6.71k
312
6.71k
      DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
313
6.71k
      DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
314
6.71k
315
6.71k
      if (MyNd.compare(&OtherNd))
316
1
        return true;
317
6.71k
    }
318
722
319
722
    
return false721
;
320
722
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::compare(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::compare(llvm::DominatorTreeBase<llvm::MachineBasicBlock, true> const&) const
llvm::DominatorTreeBase<llvm::BasicBlock, false>::compare(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&) const
Line
Count
Source
292
371
  bool compare(const DominatorTreeBase &Other) const {
293
371
    if (Parent != Other.Parent) 
return true0
;
294
371
295
371
    if (Roots.size() != Other.Roots.size())
296
0
      return true;
297
371
298
371
    if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
299
0
      return true;
300
371
301
371
    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
302
371
    if (DomTreeNodes.size() != OtherDomTreeNodes.size())
303
1
      return true;
304
370
305
2.84k
    
for (const auto &DomTreeNode : DomTreeNodes)370
{
306
2.84k
      NodeT *BB = DomTreeNode.first;
307
2.84k
      typename DomTreeNodeMapType::const_iterator OI =
308
2.84k
          OtherDomTreeNodes.find(BB);
309
2.84k
      if (OI == OtherDomTreeNodes.end())
310
0
        return true;
311
2.84k
312
2.84k
      DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
313
2.84k
      DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
314
2.84k
315
2.84k
      if (MyNd.compare(&OtherNd))
316
0
        return true;
317
2.84k
    }
318
370
319
370
    return false;
320
370
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::compare(llvm::DominatorTreeBase<llvm::BasicBlock, true> const&) const
Line
Count
Source
292
352
  bool compare(const DominatorTreeBase &Other) const {
293
352
    if (Parent != Other.Parent) 
return true0
;
294
352
295
352
    if (Roots.size() != Other.Roots.size())
296
0
      return true;
297
352
298
352
    if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
299
0
      return true;
300
352
301
352
    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
302
352
    if (DomTreeNodes.size() != OtherDomTreeNodes.size())
303
0
      return true;
304
352
305
3.86k
    
for (const auto &DomTreeNode : DomTreeNodes)352
{
306
3.86k
      NodeT *BB = DomTreeNode.first;
307
3.86k
      typename DomTreeNodeMapType::const_iterator OI =
308
3.86k
          OtherDomTreeNodes.find(BB);
309
3.86k
      if (OI == OtherDomTreeNodes.end())
310
0
        return true;
311
3.86k
312
3.86k
      DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
313
3.86k
      DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
314
3.86k
315
3.86k
      if (MyNd.compare(&OtherNd))
316
1
        return true;
317
3.86k
    }
318
352
319
352
    
return false351
;
320
352
  }
321
322
9.84M
  void releaseMemory() { reset(); }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::releaseMemory()
Line
Count
Source
322
9.23M
  void releaseMemory() { reset(); }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::releaseMemory()
Line
Count
Source
322
603k
  void releaseMemory() { reset(); }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::releaseMemory()
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::releaseMemory()
Unexecuted instantiation: llvm::DominatorTreeBase<clang::CFGBlock, false>::releaseMemory()
Unexecuted instantiation: llvm::DominatorTreeBase<clang::CFGBlock, true>::releaseMemory()
323
324
  /// getNode - return the (Post)DominatorTree node for the specified basic
325
  /// block.  This is the same as using operator[] on this class.  The result
326
  /// may (but is not required to) be null for a forward (backwards)
327
  /// statically unreachable block.
328
747M
  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329
747M
    auto I = DomTreeNodes.find(BB);
330
747M
    if (I != DomTreeNodes.end())
331
637M
      return I->second.get();
332
109M
    return nullptr;
333
109M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::getNode(llvm::MachineBasicBlock const*) const
Line
Count
Source
328
94.4M
  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329
94.4M
    auto I = DomTreeNodes.find(BB);
330
94.4M
    if (I != DomTreeNodes.end())
331
80.6M
      return I->second.get();
332
13.7M
    return nullptr;
333
13.7M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::getNode(llvm::BasicBlock const*) const
Line
Count
Source
328
607M
  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329
607M
    auto I = DomTreeNodes.find(BB);
330
607M
    if (I != DomTreeNodes.end())
331
526M
      return I->second.get();
332
81.7M
    return nullptr;
333
81.7M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::getNode(llvm::MachineBasicBlock const*) const
Line
Count
Source
328
32.6M
  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329
32.6M
    auto I = DomTreeNodes.find(BB);
330
32.6M
    if (I != DomTreeNodes.end())
331
22.1M
      return I->second.get();
332
10.4M
    return nullptr;
333
10.4M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::getNode(llvm::BasicBlock const*) const
Line
Count
Source
328
12.2M
  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329
12.2M
    auto I = DomTreeNodes.find(BB);
330
12.2M
    if (I != DomTreeNodes.end())
331
8.54M
      return I->second.get();
332
3.67M
    return nullptr;
333
3.67M
  }
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::getNode(llvm::VPBlockBase const*) const
Line
Count
Source
328
765
  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329
765
    auto I = DomTreeNodes.find(BB);
330
765
    if (I != DomTreeNodes.end())
331
626
      return I->second.get();
332
139
    return nullptr;
333
139
  }
llvm::DominatorTreeBase<clang::CFGBlock, false>::getNode(clang::CFGBlock const*) const
Line
Count
Source
328
206
  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329
206
    auto I = DomTreeNodes.find(BB);
330
206
    if (I != DomTreeNodes.end())
331
132
      return I->second.get();
332
74
    return nullptr;
333
74
  }
llvm::DominatorTreeBase<clang::CFGBlock, true>::getNode(clang::CFGBlock const*) const
Line
Count
Source
328
1.98k
  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329
1.98k
    auto I = DomTreeNodes.find(BB);
330
1.98k
    if (I != DomTreeNodes.end())
331
1.39k
      return I->second.get();
332
589
    return nullptr;
333
589
  }
334
335
  /// See getNode.
336
1.92M
  DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
337
1.92M
    return getNode(BB);
338
1.92M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::operator[](llvm::BasicBlock const*) const
Line
Count
Source
336
1.89M
  DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
337
1.89M
    return getNode(BB);
338
1.89M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::operator[](llvm::MachineBasicBlock const*) const
Line
Count
Source
336
23.0k
  DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
337
23.0k
    return getNode(BB);
338
23.0k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::operator[](llvm::MachineBasicBlock const*) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::operator[](llvm::BasicBlock const*) const
339
340
  /// getRootNode - This returns the entry node for the CFG of the function.  If
341
  /// this tree represents the post-dominance relations for a function, however,
342
  /// this root may be a node with the block == NULL.  This is the case when
343
  /// there are multiple exit nodes from a particular function.  Consumers of
344
  /// post-dominance information must be capable of dealing with this
345
  /// possibility.
346
  ///
347
9.19M
  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::getRootNode()
Line
Count
Source
347
6.86M
  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::getRootNode()
Line
Count
Source
347
466k
  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::getRootNode()
Line
Count
Source
347
1.85M
  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::getRootNode()
Unexecuted instantiation: llvm::DominatorTreeBase<clang::CFGBlock, false>::getRootNode()
348
11.2M
  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::getRootNode() const
Line
Count
Source
348
2.39M
  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::getRootNode() const
Line
Count
Source
348
12
  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::getRootNode() const
Line
Count
Source
348
8.68M
  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::getRootNode() const
Line
Count
Source
348
159k
  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::getRootNode() const
Line
Count
Source
348
25
  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
Unexecuted instantiation: llvm::DominatorTreeBase<clang::CFGBlock, false>::getRootNode() const
llvm::DominatorTreeBase<clang::CFGBlock, true>::getRootNode() const
Line
Count
Source
348
97
  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
349
350
  /// Get all nodes dominated by R, including R itself.
351
6.63k
  void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
352
6.63k
    Result.clear();
353
6.63k
    const DomTreeNodeBase<NodeT> *RN = getNode(R);
354
6.63k
    if (!RN)
355
3
      return; // If R is unreachable, it will not be present in the DOM tree.
356
6.62k
    SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
357
6.62k
    WL.push_back(RN);
358
6.62k
359
15.0k
    while (!WL.empty()) {
360
8.43k
      const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
361
8.43k
      Result.push_back(N->getBlock());
362
8.43k
      WL.append(N->begin(), N->end());
363
8.43k
    }
364
6.62k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::getDescendants(llvm::MachineBasicBlock*, llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::getDescendants(llvm::MachineBasicBlock*, llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
llvm::DominatorTreeBase<llvm::BasicBlock, false>::getDescendants(llvm::BasicBlock*, llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
351
6.63k
  void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
352
6.63k
    Result.clear();
353
6.63k
    const DomTreeNodeBase<NodeT> *RN = getNode(R);
354
6.63k
    if (!RN)
355
3
      return; // If R is unreachable, it will not be present in the DOM tree.
356
6.62k
    SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
357
6.62k
    WL.push_back(RN);
358
6.62k
359
15.0k
    while (!WL.empty()) {
360
8.43k
      const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
361
8.43k
      Result.push_back(N->getBlock());
362
8.43k
      WL.append(N->begin(), N->end());
363
8.43k
    }
364
6.62k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::getDescendants(llvm::BasicBlock*, llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
351
1
  void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
352
1
    Result.clear();
353
1
    const DomTreeNodeBase<NodeT> *RN = getNode(R);
354
1
    if (!RN)
355
0
      return; // If R is unreachable, it will not be present in the DOM tree.
356
1
    SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
357
1
    WL.push_back(RN);
358
1
359
2
    while (!WL.empty()) {
360
1
      const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
361
1
      Result.push_back(N->getBlock());
362
1
      WL.append(N->begin(), N->end());
363
1
    }
364
1
  }
365
366
  /// properlyDominates - Returns true iff A dominates B and A != B.
367
  /// Note that this is not a constant time operation!
368
  ///
369
  bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
370
16.7k
                         const DomTreeNodeBase<NodeT> *B) const {
371
16.7k
    if (!A || !B)
372
0
      return false;
373
16.7k
    if (A == B)
374
1.99k
      return false;
375
14.7k
    return dominates(A, B);
376
14.7k
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::properlyDominates(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Line
Count
Source
370
4.35k
                         const DomTreeNodeBase<NodeT> *B) const {
371
4.35k
    if (!A || !B)
372
0
      return false;
373
4.35k
    if (A == B)
374
195
      return false;
375
4.16k
    return dominates(A, B);
376
4.16k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::properlyDominates(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
llvm::DominatorTreeBase<llvm::BasicBlock, false>::properlyDominates(llvm::DomTreeNodeBase<llvm::BasicBlock> const*, llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
370
12.3k
                         const DomTreeNodeBase<NodeT> *B) const {
371
12.3k
    if (!A || !B)
372
0
      return false;
373
12.3k
    if (A == B)
374
1.80k
      return false;
375
10.5k
    return dominates(A, B);
376
10.5k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::properlyDominates(llvm::DomTreeNodeBase<llvm::BasicBlock> const*, llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
377
378
  bool properlyDominates(const NodeT *A, const NodeT *B) const;
379
380
  /// isReachableFromEntry - Return true if A is dominated by the entry
381
  /// block of the function containing it.
382
113M
  bool isReachableFromEntry(const NodeT *A) const {
383
113M
    assert(!this->isPostDominator() &&
384
113M
           "This is not implemented for post dominators");
385
113M
    return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
386
113M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::isReachableFromEntry(llvm::MachineBasicBlock const*) const
Line
Count
Source
382
6.54M
  bool isReachableFromEntry(const NodeT *A) const {
383
6.54M
    assert(!this->isPostDominator() &&
384
6.54M
           "This is not implemented for post dominators");
385
6.54M
    return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
386
6.54M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::isReachableFromEntry(llvm::BasicBlock const*) const
Line
Count
Source
382
106M
  bool isReachableFromEntry(const NodeT *A) const {
383
106M
    assert(!this->isPostDominator() &&
384
106M
           "This is not implemented for post dominators");
385
106M
    return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
386
106M
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::isReachableFromEntry(llvm::MachineBasicBlock const*) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::isReachableFromEntry(llvm::BasicBlock const*) const
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::isReachableFromEntry(llvm::VPBlockBase const*) const
Line
Count
Source
382
101
  bool isReachableFromEntry(const NodeT *A) const {
383
101
    assert(!this->isPostDominator() &&
384
101
           "This is not implemented for post dominators");
385
101
    return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
386
101
  }
387
388
420M
  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::isReachableFromEntry(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Line
Count
Source
388
64.1M
  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::isReachableFromEntry(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Line
Count
Source
388
13.5M
  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::isReachableFromEntry(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
388
342M
  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::isReachableFromEntry(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
388
1.81k
  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::isReachableFromEntry(llvm::DomTreeNodeBase<llvm::VPBlockBase> const*) const
Line
Count
Source
388
469
  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
389
390
  /// dominates - Returns true iff A dominates B.  Note that this is not a
391
  /// constant time operation!
392
  ///
393
  bool dominates(const DomTreeNodeBase<NodeT> *A,
394
153M
                 const DomTreeNodeBase<NodeT> *B) const {
395
153M
    // A node trivially dominates itself.
396
153M
    if (B == A)
397
14.7k
      return true;
398
153M
399
153M
    // An unreachable node is dominated by anything.
400
153M
    if (!isReachableFromEntry(B))
401
244
      return true;
402
153M
403
153M
    // And dominates nothing.
404
153M
    if (!isReachableFromEntry(A))
405
209k
      return false;
406
153M
407
153M
    if (B->getIDom() == A) 
return true9.79M
;
408
143M
409
143M
    if (A->getIDom() == B) 
return false54.3M
;
410
89.1M
411
89.1M
    // A can only dominate B if it is higher in the tree.
412
89.1M
    if (A->getLevel() >= B->getLevel()) 
return false49.0M
;
413
40.1M
414
40.1M
    // Compare the result of the tree walk and the dfs numbers, if expensive
415
40.1M
    // checks are enabled.
416
#ifdef EXPENSIVE_CHECKS
417
    assert((!DFSInfoValid ||
418
            (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
419
           "Tree walk disagrees with dfs numbers!");
420
#endif
421
422
40.1M
    if (DFSInfoValid)
423
23.4M
      return B->DominatedBy(A);
424
16.6M
425
16.6M
    // If we end up with too many slow queries, just update the
426
16.6M
    // DFS numbers on the theory that we are going to keep querying.
427
16.6M
    SlowQueries++;
428
16.6M
    if (SlowQueries > 32) {
429
182k
      updateDFSNumbers();
430
182k
      return B->DominatedBy(A);
431
182k
    }
432
16.4M
433
16.4M
    return dominatedBySlowTreeWalk(A, B);
434
16.4M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::dominates(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Line
Count
Source
394
28.7M
                 const DomTreeNodeBase<NodeT> *B) const {
395
28.7M
    // A node trivially dominates itself.
396
28.7M
    if (B == A)
397
14.7k
      return true;
398
28.7M
399
28.7M
    // An unreachable node is dominated by anything.
400
28.7M
    if (!isReachableFromEntry(B))
401
21
      return true;
402
28.7M
403
28.7M
    // And dominates nothing.
404
28.7M
    if (!isReachableFromEntry(A))
405
0
      return false;
406
28.7M
407
28.7M
    if (B->getIDom() == A) 
return true2.45M
;
408
26.3M
409
26.3M
    if (A->getIDom() == B) 
return false9.15M
;
410
17.1M
411
17.1M
    // A can only dominate B if it is higher in the tree.
412
17.1M
    if (A->getLevel() >= B->getLevel()) 
return false4.50M
;
413
12.6M
414
12.6M
    // Compare the result of the tree walk and the dfs numbers, if expensive
415
12.6M
    // checks are enabled.
416
#ifdef EXPENSIVE_CHECKS
417
    assert((!DFSInfoValid ||
418
            (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
419
           "Tree walk disagrees with dfs numbers!");
420
#endif
421
422
12.6M
    if (DFSInfoValid)
423
8.60M
      return B->DominatedBy(A);
424
4.05M
425
4.05M
    // If we end up with too many slow queries, just update the
426
4.05M
    // DFS numbers on the theory that we are going to keep querying.
427
4.05M
    SlowQueries++;
428
4.05M
    if (SlowQueries > 32) {
429
52.0k
      updateDFSNumbers();
430
52.0k
      return B->DominatedBy(A);
431
52.0k
    }
432
4.00M
433
4.00M
    return dominatedBySlowTreeWalk(A, B);
434
4.00M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::dominates(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Line
Count
Source
394
6.75M
                 const DomTreeNodeBase<NodeT> *B) const {
395
6.75M
    // A node trivially dominates itself.
396
6.75M
    if (B == A)
397
0
      return true;
398
6.75M
399
6.75M
    // An unreachable node is dominated by anything.
400
6.75M
    if (!isReachableFromEntry(B))
401
0
      return true;
402
6.75M
403
6.75M
    // And dominates nothing.
404
6.75M
    if (!isReachableFromEntry(A))
405
203k
      return false;
406
6.54M
407
6.54M
    if (B->getIDom() == A) 
return true1.54M
;
408
5.00M
409
5.00M
    if (A->getIDom() == B) 
return false50.1k
;
410
4.95M
411
4.95M
    // A can only dominate B if it is higher in the tree.
412
4.95M
    if (A->getLevel() >= B->getLevel()) 
return false4.90M
;
413
49.6k
414
49.6k
    // Compare the result of the tree walk and the dfs numbers, if expensive
415
49.6k
    // checks are enabled.
416
#ifdef EXPENSIVE_CHECKS
417
    assert((!DFSInfoValid ||
418
            (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
419
           "Tree walk disagrees with dfs numbers!");
420
#endif
421
422
49.6k
    if (DFSInfoValid)
423
260
      return B->DominatedBy(A);
424
49.3k
425
49.3k
    // If we end up with too many slow queries, just update the
426
49.3k
    // DFS numbers on the theory that we are going to keep querying.
427
49.3k
    SlowQueries++;
428
49.3k
    if (SlowQueries > 32) {
429
12
      updateDFSNumbers();
430
12
      return B->DominatedBy(A);
431
12
    }
432
49.3k
433
49.3k
    return dominatedBySlowTreeWalk(A, B);
434
49.3k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::dominates(llvm::DomTreeNodeBase<llvm::BasicBlock> const*, llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
394
117M
                 const DomTreeNodeBase<NodeT> *B) const {
395
117M
    // A node trivially dominates itself.
396
117M
    if (B == A)
397
0
      return true;
398
117M
399
117M
    // An unreachable node is dominated by anything.
400
117M
    if (!isReachableFromEntry(B))
401
223
      return true;
402
117M
403
117M
    // And dominates nothing.
404
117M
    if (!isReachableFromEntry(A))
405
6.24k
      return false;
406
117M
407
117M
    if (B->getIDom() == A) 
return true5.80M
;
408
112M
409
112M
    if (A->getIDom() == B) 
return false45.1M
;
410
66.9M
411
66.9M
    // A can only dominate B if it is higher in the tree.
412
66.9M
    if (A->getLevel() >= B->getLevel()) 
return false39.5M
;
413
27.4M
414
27.4M
    // Compare the result of the tree walk and the dfs numbers, if expensive
415
27.4M
    // checks are enabled.
416
#ifdef EXPENSIVE_CHECKS
417
    assert((!DFSInfoValid ||
418
            (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
419
           "Tree walk disagrees with dfs numbers!");
420
#endif
421
422
27.4M
    if (DFSInfoValid)
423
14.8M
      return B->DominatedBy(A);
424
12.5M
425
12.5M
    // If we end up with too many slow queries, just update the
426
12.5M
    // DFS numbers on the theory that we are going to keep querying.
427
12.5M
    SlowQueries++;
428
12.5M
    if (SlowQueries > 32) {
429
130k
      updateDFSNumbers();
430
130k
      return B->DominatedBy(A);
431
130k
    }
432
12.4M
433
12.4M
    return dominatedBySlowTreeWalk(A, B);
434
12.4M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::dominates(llvm::DomTreeNodeBase<llvm::BasicBlock> const*, llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
394
906
                 const DomTreeNodeBase<NodeT> *B) const {
395
906
    // A node trivially dominates itself.
396
906
    if (B == A)
397
0
      return true;
398
906
399
906
    // An unreachable node is dominated by anything.
400
906
    if (!isReachableFromEntry(B))
401
0
      return true;
402
906
403
906
    // And dominates nothing.
404
906
    if (!isReachableFromEntry(A))
405
0
      return false;
406
906
407
906
    if (B->getIDom() == A) 
return true229
;
408
677
409
677
    if (A->getIDom() == B) 
return false36
;
410
641
411
641
    // A can only dominate B if it is higher in the tree.
412
641
    if (A->getLevel() >= B->getLevel()) 
return false517
;
413
124
414
124
    // Compare the result of the tree walk and the dfs numbers, if expensive
415
124
    // checks are enabled.
416
#ifdef EXPENSIVE_CHECKS
417
    assert((!DFSInfoValid ||
418
            (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
419
           "Tree walk disagrees with dfs numbers!");
420
#endif
421
422
124
    if (DFSInfoValid)
423
0
      return B->DominatedBy(A);
424
124
425
124
    // If we end up with too many slow queries, just update the
426
124
    // DFS numbers on the theory that we are going to keep querying.
427
124
    SlowQueries++;
428
124
    if (SlowQueries > 32) {
429
0
      updateDFSNumbers();
430
0
      return B->DominatedBy(A);
431
0
    }
432
124
433
124
    return dominatedBySlowTreeWalk(A, B);
434
124
  }
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::dominates(llvm::DomTreeNodeBase<llvm::VPBlockBase> const*, llvm::DomTreeNodeBase<llvm::VPBlockBase> const*) const
Line
Count
Source
394
184
                 const DomTreeNodeBase<NodeT> *B) const {
395
184
    // A node trivially dominates itself.
396
184
    if (B == A)
397
0
      return true;
398
184
399
184
    // An unreachable node is dominated by anything.
400
184
    if (!isReachableFromEntry(B))
401
0
      return true;
402
184
403
184
    // And dominates nothing.
404
184
    if (!isReachableFromEntry(A))
405
0
      return false;
406
184
407
184
    if (B->getIDom() == A) 
return true19
;
408
165
409
165
    if (A->getIDom() == B) 
return false93
;
410
72
411
72
    // A can only dominate B if it is higher in the tree.
412
72
    if (A->getLevel() >= B->getLevel()) 
return false33
;
413
39
414
39
    // Compare the result of the tree walk and the dfs numbers, if expensive
415
39
    // checks are enabled.
416
#ifdef EXPENSIVE_CHECKS
417
    assert((!DFSInfoValid ||
418
            (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
419
           "Tree walk disagrees with dfs numbers!");
420
#endif
421
422
39
    if (DFSInfoValid)
423
0
      return B->DominatedBy(A);
424
39
425
39
    // If we end up with too many slow queries, just update the
426
39
    // DFS numbers on the theory that we are going to keep querying.
427
39
    SlowQueries++;
428
39
    if (SlowQueries > 32) {
429
0
      updateDFSNumbers();
430
0
      return B->DominatedBy(A);
431
0
    }
432
39
433
39
    return dominatedBySlowTreeWalk(A, B);
434
39
  }
435
436
  bool dominates(const NodeT *A, const NodeT *B) const;
437
438
888k
  NodeT *getRoot() const {
439
888k
    assert(this->Roots.size() == 1 && "Should always have entry node!");
440
888k
    return this->Roots[0];
441
888k
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::getRoot() const
Line
Count
Source
438
14.5k
  NodeT *getRoot() const {
439
14.5k
    assert(this->Roots.size() == 1 && "Should always have entry node!");
440
14.5k
    return this->Roots[0];
441
14.5k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::getRoot() const
Line
Count
Source
438
873k
  NodeT *getRoot() const {
439
873k
    assert(this->Roots.size() == 1 && "Should always have entry node!");
440
873k
    return this->Roots[0];
441
873k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::getRoot() const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::getRoot() const
442
443
  /// findNearestCommonDominator - Find nearest common dominator basic block
444
  /// for basic block A and B. If there is no such block then return nullptr.
445
2.63M
  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
446
2.63M
    assert(A && B && "Pointers are not valid");
447
2.63M
    assert(A->getParent() == B->getParent() &&
448
2.63M
           "Two blocks are not in same function");
449
2.63M
450
2.63M
    // If either A or B is a entry block then it is nearest common dominator
451
2.63M
    // (for forward-dominators).
452
2.63M
    if (!isPostDominator()) {
453
2.51M
      NodeT &Entry = A->getParent()->front();
454
2.51M
      if (A == &Entry || 
B == &Entry2.42M
)
455
106k
        return &Entry;
456
2.53M
    }
457
2.53M
458
2.53M
    DomTreeNodeBase<NodeT> *NodeA = getNode(A);
459
2.53M
    DomTreeNodeBase<NodeT> *NodeB = getNode(B);
460
2.53M
461
2.53M
    if (!NodeA || 
!NodeB2.53M
)
return nullptr2
;
462
2.53M
463
2.53M
    // Use level information to go up the tree until the levels match. Then
464
2.53M
    // continue going up til we arrive at the same node.
465
21.7M
    
while (2.53M
NodeA && NodeA != NodeB) {
466
19.2M
      if (NodeA->getLevel() < NodeB->getLevel()) 
std::swap(NodeA, NodeB)2.46M
;
467
19.2M
468
19.2M
      NodeA = NodeA->IDom;
469
19.2M
    }
470
2.53M
471
2.53M
    return NodeA ? NodeA->getBlock() : 
nullptr0
;
472
2.53M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::findNearestCommonDominator(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*) const
Line
Count
Source
445
278k
  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
446
278k
    assert(A && B && "Pointers are not valid");
447
278k
    assert(A->getParent() == B->getParent() &&
448
278k
           "Two blocks are not in same function");
449
278k
450
278k
    // If either A or B is a entry block then it is nearest common dominator
451
278k
    // (for forward-dominators).
452
278k
    if (!isPostDominator()) {
453
278k
      NodeT &Entry = A->getParent()->front();
454
278k
      if (A == &Entry || 
B == &Entry271k
)
455
25.4k
        return &Entry;
456
253k
    }
457
253k
458
253k
    DomTreeNodeBase<NodeT> *NodeA = getNode(A);
459
253k
    DomTreeNodeBase<NodeT> *NodeB = getNode(B);
460
253k
461
253k
    if (!NodeA || 
!NodeB253k
)
return nullptr2
;
462
253k
463
253k
    // Use level information to go up the tree until the levels match. Then
464
253k
    // continue going up til we arrive at the same node.
465
13.6M
    
while (253k
NodeA && NodeA != NodeB) {
466
13.4M
      if (NodeA->getLevel() < NodeB->getLevel()) 
std::swap(NodeA, NodeB)394k
;
467
13.4M
468
13.4M
      NodeA = NodeA->IDom;
469
13.4M
    }
470
253k
471
253k
    return NodeA ? NodeA->getBlock() : 
nullptr0
;
472
253k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::findNearestCommonDominator(llvm::BasicBlock*, llvm::BasicBlock*) const
Line
Count
Source
445
2.23M
  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
446
2.23M
    assert(A && B && "Pointers are not valid");
447
2.23M
    assert(A->getParent() == B->getParent() &&
448
2.23M
           "Two blocks are not in same function");
449
2.23M
450
2.23M
    // If either A or B is a entry block then it is nearest common dominator
451
2.23M
    // (for forward-dominators).
452
2.23M
    if (!isPostDominator()) {
453
2.23M
      NodeT &Entry = A->getParent()->front();
454
2.23M
      if (A == &Entry || 
B == &Entry2.15M
)
455
80.9k
        return &Entry;
456
2.15M
    }
457
2.15M
458
2.15M
    DomTreeNodeBase<NodeT> *NodeA = getNode(A);
459
2.15M
    DomTreeNodeBase<NodeT> *NodeB = getNode(B);
460
2.15M
461
2.15M
    if (!NodeA || !NodeB) 
return nullptr0
;
462
2.15M
463
2.15M
    // Use level information to go up the tree until the levels match. Then
464
2.15M
    // continue going up til we arrive at the same node.
465
7.76M
    
while (2.15M
NodeA && NodeA != NodeB) {
466
5.61M
      if (NodeA->getLevel() < NodeB->getLevel()) 
std::swap(NodeA, NodeB)2.00M
;
467
5.61M
468
5.61M
      NodeA = NodeA->IDom;
469
5.61M
    }
470
2.15M
471
2.15M
    return NodeA ? NodeA->getBlock() : 
nullptr0
;
472
2.15M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::findNearestCommonDominator(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*) const
Line
Count
Source
445
123k
  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
446
123k
    assert(A && B && "Pointers are not valid");
447
123k
    assert(A->getParent() == B->getParent() &&
448
123k
           "Two blocks are not in same function");
449
123k
450
123k
    // If either A or B is a entry block then it is nearest common dominator
451
123k
    // (for forward-dominators).
452
123k
    if (!isPostDominator()) {
453
0
      NodeT &Entry = A->getParent()->front();
454
0
      if (A == &Entry || B == &Entry)
455
0
        return &Entry;
456
123k
    }
457
123k
458
123k
    DomTreeNodeBase<NodeT> *NodeA = getNode(A);
459
123k
    DomTreeNodeBase<NodeT> *NodeB = getNode(B);
460
123k
461
123k
    if (!NodeA || !NodeB) 
return nullptr0
;
462
123k
463
123k
    // Use level information to go up the tree until the levels match. Then
464
123k
    // continue going up til we arrive at the same node.
465
270k
    
while (123k
NodeA && NodeA != NodeB) {
466
147k
      if (NodeA->getLevel() < NodeB->getLevel()) 
std::swap(NodeA, NodeB)63.3k
;
467
147k
468
147k
      NodeA = NodeA->IDom;
469
147k
    }
470
123k
471
123k
    return NodeA ? NodeA->getBlock() : 
nullptr0
;
472
123k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::findNearestCommonDominator(llvm::BasicBlock*, llvm::BasicBlock*) const
Line
Count
Source
445
458
  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
446
458
    assert(A && B && "Pointers are not valid");
447
458
    assert(A->getParent() == B->getParent() &&
448
458
           "Two blocks are not in same function");
449
458
450
458
    // If either A or B is a entry block then it is nearest common dominator
451
458
    // (for forward-dominators).
452
458
    if (!isPostDominator()) {
453
0
      NodeT &Entry = A->getParent()->front();
454
0
      if (A == &Entry || B == &Entry)
455
0
        return &Entry;
456
458
    }
457
458
458
458
    DomTreeNodeBase<NodeT> *NodeA = getNode(A);
459
458
    DomTreeNodeBase<NodeT> *NodeB = getNode(B);
460
458
461
458
    if (!NodeA || !NodeB) 
return nullptr0
;
462
458
463
458
    // Use level information to go up the tree until the levels match. Then
464
458
    // continue going up til we arrive at the same node.
465
1.50k
    
while (458
NodeA && NodeA != NodeB) {
466
1.04k
      if (NodeA->getLevel() < NodeB->getLevel()) 
std::swap(NodeA, NodeB)470
;
467
1.04k
468
1.04k
      NodeA = NodeA->IDom;
469
1.04k
    }
470
458
471
458
    return NodeA ? NodeA->getBlock() : 
nullptr0
;
472
458
  }
473
474
  const NodeT *findNearestCommonDominator(const NodeT *A,
475
0
                                          const NodeT *B) const {
476
0
    // Cast away the const qualifiers here. This is ok since
477
0
    // const is re-introduced on the return type.
478
0
    return findNearestCommonDominator(const_cast<NodeT *>(A),
479
0
                                      const_cast<NodeT *>(B));
480
0
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::findNearestCommonDominator(llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::findNearestCommonDominator(llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, false>::findNearestCommonDominator(llvm::BasicBlock const*, llvm::BasicBlock const*) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::findNearestCommonDominator(llvm::BasicBlock const*, llvm::BasicBlock const*) const
481
482
6.91k
  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
483
6.91k
    return isPostDominator() && 
!A->getBlock()4.08k
;
484
6.91k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::isVirtualRoot(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::isVirtualRoot(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
llvm::DominatorTreeBase<llvm::BasicBlock, false>::isVirtualRoot(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
482
2.83k
  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
483
2.83k
    return isPostDominator() && 
!A->getBlock()0
;
484
2.83k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::isVirtualRoot(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
482
4.08k
  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
483
4.08k
    return isPostDominator() && !A->getBlock();
484
4.08k
  }
485
486
  //===--------------------------------------------------------------------===//
487
  // API to update (Post)DominatorTree information based on modifications to
488
  // the CFG...
489
490
  /// Inform the dominator tree about a sequence of CFG edge insertions and
491
  /// deletions and perform a batch update on the tree.
492
  ///
493
  /// This function should be used when there were multiple CFG updates after
494
  /// the last dominator tree update. It takes care of performing the updates
495
  /// in sync with the CFG and optimizes away the redundant operations that
496
  /// cancel each other.
497
  /// The functions expects the sequence of updates to be balanced. Eg.:
498
  ///  - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
499
  ///    logically it results in a single insertions.
500
  ///  - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
501
  ///    sense to insert the same edge twice.
502
  ///
503
  /// What's more, the functions assumes that it's safe to ask every node in the
504
  /// CFG about its children and inverse children. This implies that deletions
505
  /// of CFG edges must not delete the CFG nodes before calling this function.
506
  ///
507
  /// The applyUpdates function can reorder the updates and remove redundant
508
  /// ones internally. The batch updater is also able to detect sequences of
509
  /// zero and exactly one update -- it's optimized to do less work in these
510
  /// cases.
511
  ///
512
  /// Note that for postdominators it automatically takes care of applying
513
  /// updates on reverse edges internally (so there's no need to swap the
514
  /// From and To pointers when constructing DominatorTree::UpdateType).
515
  /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
516
  /// with the same template parameter T.
517
  ///
518
  /// \param Updates An unordered sequence of updates to perform.
519
  ///
520
521k
  void applyUpdates(ArrayRef<UpdateType> Updates) {
521
521k
    DomTreeBuilder::ApplyUpdates(*this, Updates);
522
521k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::applyUpdates(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*> >)
Line
Count
Source
520
521k
  void applyUpdates(ArrayRef<UpdateType> Updates) {
521
521k
    DomTreeBuilder::ApplyUpdates(*this, Updates);
522
521k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::applyUpdates(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*> >)
Line
Count
Source
520
326
  void applyUpdates(ArrayRef<UpdateType> Updates) {
521
326
    DomTreeBuilder::ApplyUpdates(*this, Updates);
522
326
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::applyUpdates(llvm::ArrayRef<llvm::cfg::Update<llvm::MachineBasicBlock*> >)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::applyUpdates(llvm::ArrayRef<llvm::cfg::Update<llvm::MachineBasicBlock*> >)
523
524
  /// Inform the dominator tree about a CFG edge insertion and update the tree.
525
  ///
526
  /// This function has to be called just before or just after making the update
527
  /// on the actual CFG. There cannot be any other updates that the dominator
528
  /// tree doesn't know about.
529
  ///
530
  /// Note that for postdominators it automatically takes care of inserting
531
  /// a reverse edge internally (so there's no need to swap the parameters).
532
  ///
533
4.53k
  void insertEdge(NodeT *From, NodeT *To) {
534
4.53k
    assert(From);
535
4.53k
    assert(To);
536
4.53k
    assert(From->getParent() == Parent);
537
4.53k
    assert(To->getParent() == Parent);
538
4.53k
    DomTreeBuilder::InsertEdge(*this, From, To);
539
4.53k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::insertEdge(llvm::BasicBlock*, llvm::BasicBlock*)
Line
Count
Source
533
4.39k
  void insertEdge(NodeT *From, NodeT *To) {
534
4.39k
    assert(From);
535
4.39k
    assert(To);
536
4.39k
    assert(From->getParent() == Parent);
537
4.39k
    assert(To->getParent() == Parent);
538
4.39k
    DomTreeBuilder::InsertEdge(*this, From, To);
539
4.39k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::insertEdge(llvm::BasicBlock*, llvm::BasicBlock*)
Line
Count
Source
533
142
  void insertEdge(NodeT *From, NodeT *To) {
534
142
    assert(From);
535
142
    assert(To);
536
142
    assert(From->getParent() == Parent);
537
142
    assert(To->getParent() == Parent);
538
142
    DomTreeBuilder::InsertEdge(*this, From, To);
539
142
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::insertEdge(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::insertEdge(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
540
541
  /// Inform the dominator tree about a CFG edge deletion and update the tree.
542
  ///
543
  /// This function has to be called just after making the update on the actual
544
  /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
545
  /// DEBUG mode. There cannot be any other updates that the
546
  /// dominator tree doesn't know about.
547
  ///
548
  /// Note that for postdominators it automatically takes care of deleting
549
  /// a reverse edge internally (so there's no need to swap the parameters).
550
  ///
551
12.9k
  void deleteEdge(NodeT *From, NodeT *To) {
552
12.9k
    assert(From);
553
12.9k
    assert(To);
554
12.9k
    assert(From->getParent() == Parent);
555
12.9k
    assert(To->getParent() == Parent);
556
12.9k
    DomTreeBuilder::DeleteEdge(*this, From, To);
557
12.9k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::deleteEdge(llvm::BasicBlock*, llvm::BasicBlock*)
Line
Count
Source
551
12.7k
  void deleteEdge(NodeT *From, NodeT *To) {
552
12.7k
    assert(From);
553
12.7k
    assert(To);
554
12.7k
    assert(From->getParent() == Parent);
555
12.7k
    assert(To->getParent() == Parent);
556
12.7k
    DomTreeBuilder::DeleteEdge(*this, From, To);
557
12.7k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::deleteEdge(llvm::BasicBlock*, llvm::BasicBlock*)
Line
Count
Source
551
182
  void deleteEdge(NodeT *From, NodeT *To) {
552
182
    assert(From);
553
182
    assert(To);
554
182
    assert(From->getParent() == Parent);
555
182
    assert(To->getParent() == Parent);
556
182
    DomTreeBuilder::DeleteEdge(*this, From, To);
557
182
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::deleteEdge(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::deleteEdge(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
558
559
  /// Add a new node to the dominator tree information.
560
  ///
561
  /// This creates a new node as a child of DomBB dominator node, linking it
562
  /// into the children list of the immediate dominator.
563
  ///
564
  /// \param BB New node in CFG.
565
  /// \param DomBB CFG node that is dominator for BB.
566
  /// \returns New dominator tree node that represents new CFG node.
567
  ///
568
1.90M
  DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
569
1.90M
    assert(getNode(BB) == nullptr && "Block already in dominator tree!");
570
1.90M
    DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
571
1.90M
    assert(IDomNode && "Not immediate dominator specified for block!");
572
1.90M
    DFSInfoValid = false;
573
1.90M
    return (DomTreeNodes[BB] = IDomNode->addChild(
574
1.90M
                llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
575
1.90M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::addNewBlock(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
Line
Count
Source
568
252k
  DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
569
252k
    assert(getNode(BB) == nullptr && "Block already in dominator tree!");
570
252k
    DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
571
252k
    assert(IDomNode && "Not immediate dominator specified for block!");
572
252k
    DFSInfoValid = false;
573
252k
    return (DomTreeNodes[BB] = IDomNode->addChild(
574
252k
                llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
575
252k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::addNewBlock(llvm::BasicBlock*, llvm::BasicBlock*)
Line
Count
Source
568
1.65M
  DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
569
1.65M
    assert(getNode(BB) == nullptr && "Block already in dominator tree!");
570
1.65M
    DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
571
1.65M
    assert(IDomNode && "Not immediate dominator specified for block!");
572
1.65M
    DFSInfoValid = false;
573
1.65M
    return (DomTreeNodes[BB] = IDomNode->addChild(
574
1.65M
                llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
575
1.65M
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::addNewBlock(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::addNewBlock(llvm::BasicBlock*, llvm::BasicBlock*)
576
577
  /// Add a new node to the forward dominator tree and make it a new root.
578
  ///
579
  /// \param BB New node in CFG.
580
  /// \returns New dominator tree node that represents new CFG node.
581
  ///
582
2
  DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
583
2
    assert(getNode(BB) == nullptr && "Block already in dominator tree!");
584
2
    assert(!this->isPostDominator() &&
585
2
           "Cannot change root of post-dominator tree");
586
2
    DFSInfoValid = false;
587
2
    DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
588
2
      llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
589
2
    if (Roots.empty()) {
590
0
      addRoot(BB);
591
2
    } else {
592
2
      assert(Roots.size() == 1);
593
2
      NodeT *OldRoot = Roots.front();
594
2
      auto &OldNode = DomTreeNodes[OldRoot];
595
2
      OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
596
2
      OldNode->IDom = NewNode;
597
2
      OldNode->UpdateLevel();
598
2
      Roots[0] = BB;
599
2
    }
600
2
    return RootNode = NewNode;
601
2
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::setNewRoot(llvm::MachineBasicBlock*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::setNewRoot(llvm::MachineBasicBlock*)
llvm::DominatorTreeBase<llvm::BasicBlock, false>::setNewRoot(llvm::BasicBlock*)
Line
Count
Source
582
2
  DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
583
2
    assert(getNode(BB) == nullptr && "Block already in dominator tree!");
584
2
    assert(!this->isPostDominator() &&
585
2
           "Cannot change root of post-dominator tree");
586
2
    DFSInfoValid = false;
587
2
    DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
588
2
      llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
589
2
    if (Roots.empty()) {
590
0
      addRoot(BB);
591
2
    } else {
592
2
      assert(Roots.size() == 1);
593
2
      NodeT *OldRoot = Roots.front();
594
2
      auto &OldNode = DomTreeNodes[OldRoot];
595
2
      OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
596
2
      OldNode->IDom = NewNode;
597
2
      OldNode->UpdateLevel();
598
2
      Roots[0] = BB;
599
2
    }
600
2
    return RootNode = NewNode;
601
2
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::setNewRoot(llvm::BasicBlock*)
602
603
  /// changeImmediateDominator - This method is used to update the dominator
604
  /// tree information when a node's immediate dominator changes.
605
  ///
606
  void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
607
585k
                                DomTreeNodeBase<NodeT> *NewIDom) {
608
585k
    assert(N && NewIDom && "Cannot change null node pointers!");
609
585k
    DFSInfoValid = false;
610
585k
    N->setIDom(NewIDom);
611
585k
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::changeImmediateDominator(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*)
Line
Count
Source
607
23.4k
                                DomTreeNodeBase<NodeT> *NewIDom) {
608
23.4k
    assert(N && NewIDom && "Cannot change null node pointers!");
609
23.4k
    DFSInfoValid = false;
610
23.4k
    N->setIDom(NewIDom);
611
23.4k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::changeImmediateDominator(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::DomTreeNodeBase<llvm::BasicBlock>*)
Line
Count
Source
607
561k
                                DomTreeNodeBase<NodeT> *NewIDom) {
608
561k
    assert(N && NewIDom && "Cannot change null node pointers!");
609
561k
    DFSInfoValid = false;
610
561k
    N->setIDom(NewIDom);
611
561k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::changeImmediateDominator(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::changeImmediateDominator(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::DomTreeNodeBase<llvm::BasicBlock>*)
612
613
52.0k
  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
614
52.0k
    changeImmediateDominator(getNode(BB), getNode(NewBB));
615
52.0k
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::changeImmediateDominator(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
Line
Count
Source
613
37
  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
614
37
    changeImmediateDominator(getNode(BB), getNode(NewBB));
615
37
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::changeImmediateDominator(llvm::BasicBlock*, llvm::BasicBlock*)
Line
Count
Source
613
52.0k
  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
614
52.0k
    changeImmediateDominator(getNode(BB), getNode(NewBB));
615
52.0k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::changeImmediateDominator(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::changeImmediateDominator(llvm::BasicBlock*, llvm::BasicBlock*)
616
617
  /// eraseNode - Removes a node from the dominator tree. Block must not
618
  /// dominate any other blocks. Removes node from its immediate dominator's
619
  /// children list. Deletes dominator node associated with basic block BB.
620
15.0k
  void eraseNode(NodeT *BB) {
621
15.0k
    DomTreeNodeBase<NodeT> *Node = getNode(BB);
622
15.0k
    assert(Node && "Removing node that isn't in dominator tree.");
623
15.0k
    assert(Node->getChildren().empty() && "Node is not a leaf node.");
624
15.0k
625
15.0k
    DFSInfoValid = false;
626
15.0k
627
15.0k
    // Remove node from immediate dominator's children list.
628
15.0k
    DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
629
15.0k
    if (IDom) {
630
15.0k
      const auto I = find(IDom->Children, Node);
631
15.0k
      assert(I != IDom->Children.end() &&
632
15.0k
             "Not in immediate dominator children set!");
633
15.0k
      // I am no longer your child...
634
15.0k
      IDom->Children.erase(I);
635
15.0k
    }
636
15.0k
637
15.0k
    DomTreeNodes.erase(BB);
638
15.0k
639
15.0k
    if (!IsPostDom) 
return15.0k
;
640
31
641
31
    // Remember to update PostDominatorTree roots.
642
31
    auto RIt = llvm::find(Roots, BB);
643
31
    if (RIt != Roots.end()) {
644
30
      std::swap(*RIt, Roots.back());
645
30
      Roots.pop_back();
646
30
    }
647
31
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::eraseNode(llvm::MachineBasicBlock*)
Line
Count
Source
620
11.6k
  void eraseNode(NodeT *BB) {
621
11.6k
    DomTreeNodeBase<NodeT> *Node = getNode(BB);
622
11.6k
    assert(Node && "Removing node that isn't in dominator tree.");
623
11.6k
    assert(Node->getChildren().empty() && "Node is not a leaf node.");
624
11.6k
625
11.6k
    DFSInfoValid = false;
626
11.6k
627
11.6k
    // Remove node from immediate dominator's children list.
628
11.6k
    DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
629
11.6k
    if (IDom) {
630
11.6k
      const auto I = find(IDom->Children, Node);
631
11.6k
      assert(I != IDom->Children.end() &&
632
11.6k
             "Not in immediate dominator children set!");
633
11.6k
      // I am no longer your child...
634
11.6k
      IDom->Children.erase(I);
635
11.6k
    }
636
11.6k
637
11.6k
    DomTreeNodes.erase(BB);
638
11.6k
639
11.6k
    if (!IsPostDom) return;
640
0
641
0
    // Remember to update PostDominatorTree roots.
642
0
    auto RIt = llvm::find(Roots, BB);
643
0
    if (RIt != Roots.end()) {
644
0
      std::swap(*RIt, Roots.back());
645
0
      Roots.pop_back();
646
0
    }
647
0
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::eraseNode(llvm::BasicBlock*)
Line
Count
Source
620
3.44k
  void eraseNode(NodeT *BB) {
621
3.44k
    DomTreeNodeBase<NodeT> *Node = getNode(BB);
622
3.44k
    assert(Node && "Removing node that isn't in dominator tree.");
623
3.44k
    assert(Node->getChildren().empty() && "Node is not a leaf node.");
624
3.44k
625
3.44k
    DFSInfoValid = false;
626
3.44k
627
3.44k
    // Remove node from immediate dominator's children list.
628
3.44k
    DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
629
3.44k
    if (IDom) {
630
3.43k
      const auto I = find(IDom->Children, Node);
631
3.43k
      assert(I != IDom->Children.end() &&
632
3.43k
             "Not in immediate dominator children set!");
633
3.43k
      // I am no longer your child...
634
3.43k
      IDom->Children.erase(I);
635
3.43k
    }
636
3.44k
637
3.44k
    DomTreeNodes.erase(BB);
638
3.44k
639
3.44k
    if (!IsPostDom) return;
640
0
641
0
    // Remember to update PostDominatorTree roots.
642
0
    auto RIt = llvm::find(Roots, BB);
643
0
    if (RIt != Roots.end()) {
644
0
      std::swap(*RIt, Roots.back());
645
0
      Roots.pop_back();
646
0
    }
647
0
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::eraseNode(llvm::BasicBlock*)
Line
Count
Source
620
31
  void eraseNode(NodeT *BB) {
621
31
    DomTreeNodeBase<NodeT> *Node = getNode(BB);
622
31
    assert(Node && "Removing node that isn't in dominator tree.");
623
31
    assert(Node->getChildren().empty() && "Node is not a leaf node.");
624
31
625
31
    DFSInfoValid = false;
626
31
627
31
    // Remove node from immediate dominator's children list.
628
31
    DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
629
31
    if (IDom) {
630
31
      const auto I = find(IDom->Children, Node);
631
31
      assert(I != IDom->Children.end() &&
632
31
             "Not in immediate dominator children set!");
633
31
      // I am no longer your child...
634
31
      IDom->Children.erase(I);
635
31
    }
636
31
637
31
    DomTreeNodes.erase(BB);
638
31
639
31
    if (!IsPostDom) 
return0
;
640
31
641
31
    // Remember to update PostDominatorTree roots.
642
31
    auto RIt = llvm::find(Roots, BB);
643
31
    if (RIt != Roots.end()) {
644
30
      std::swap(*RIt, Roots.back());
645
30
      Roots.pop_back();
646
30
    }
647
31
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::eraseNode(llvm::MachineBasicBlock*)
648
649
  /// splitBlock - BB is split and now it has one successor. Update dominator
650
  /// tree to reflect this change.
651
1.28M
  void splitBlock(NodeT *NewBB) {
652
1.28M
    if (IsPostDominator)
653
0
      Split<Inverse<NodeT *>>(NewBB);
654
1.28M
    else
655
1.28M
      Split<NodeT *>(NewBB);
656
1.28M
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::splitBlock(llvm::MachineBasicBlock*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::splitBlock(llvm::MachineBasicBlock*)
llvm::DominatorTreeBase<llvm::BasicBlock, false>::splitBlock(llvm::BasicBlock*)
Line
Count
Source
651
1.28M
  void splitBlock(NodeT *NewBB) {
652
1.28M
    if (IsPostDominator)
653
0
      Split<Inverse<NodeT *>>(NewBB);
654
1.28M
    else
655
1.28M
      Split<NodeT *>(NewBB);
656
1.28M
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::splitBlock(llvm::BasicBlock*)
657
658
  /// print - Convert to human readable form
659
  ///
660
27
  void print(raw_ostream &O) const {
661
27
    O << "=============================--------------------------------\n";
662
27
    if (IsPostDominator)
663
16
      O << "Inorder PostDominator Tree: ";
664
11
    else
665
11
      O << "Inorder Dominator Tree: ";
666
27
    if (!DFSInfoValid)
667
27
      O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
668
27
    O << "\n";
669
27
670
27
    // The postdom tree can have a null root if there are no returns.
671
27
    if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
672
27
    O << "Roots: ";
673
43
    for (const NodePtr Block : Roots) {
674
43
      Block->printAsOperand(O, false);
675
43
      O << " ";
676
43
    }
677
27
    O << "\n";
678
27
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::print(llvm::raw_ostream&) const
Line
Count
Source
660
16
  void print(raw_ostream &O) const {
661
16
    O << "=============================--------------------------------\n";
662
16
    if (IsPostDominator)
663
16
      O << "Inorder PostDominator Tree: ";
664
0
    else
665
0
      O << "Inorder Dominator Tree: ";
666
16
    if (!DFSInfoValid)
667
16
      O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
668
16
    O << "\n";
669
16
670
16
    // The postdom tree can have a null root if there are no returns.
671
16
    if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
672
16
    O << "Roots: ";
673
32
    for (const NodePtr Block : Roots) {
674
32
      Block->printAsOperand(O, false);
675
32
      O << " ";
676
32
    }
677
16
    O << "\n";
678
16
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::print(llvm::raw_ostream&) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::print(llvm::raw_ostream&) const
llvm::DominatorTreeBase<llvm::BasicBlock, false>::print(llvm::raw_ostream&) const
Line
Count
Source
660
11
  void print(raw_ostream &O) const {
661
11
    O << "=============================--------------------------------\n";
662
11
    if (IsPostDominator)
663
0
      O << "Inorder PostDominator Tree: ";
664
11
    else
665
11
      O << "Inorder Dominator Tree: ";
666
11
    if (!DFSInfoValid)
667
11
      O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
668
11
    O << "\n";
669
11
670
11
    // The postdom tree can have a null root if there are no returns.
671
11
    if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
672
11
    O << "Roots: ";
673
11
    for (const NodePtr Block : Roots) {
674
11
      Block->printAsOperand(O, false);
675
11
      O << " ";
676
11
    }
677
11
    O << "\n";
678
11
  }
Unexecuted instantiation: llvm::DominatorTreeBase<clang::CFGBlock, false>::print(llvm::raw_ostream&) const
Unexecuted instantiation: llvm::DominatorTreeBase<clang::CFGBlock, true>::print(llvm::raw_ostream&) const
679
680
public:
681
  /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
682
  /// dominator tree in dfs order.
683
1.79M
  void updateDFSNumbers() const {
684
1.79M
    if (DFSInfoValid) {
685
89.9k
      SlowQueries = 0;
686
89.9k
      return;
687
89.9k
    }
688
1.70M
689
1.70M
    SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
690
1.70M
                          typename DomTreeNodeBase<NodeT>::const_iterator>,
691
1.70M
                32> WorkStack;
692
1.70M
693
1.70M
    const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694
1.70M
    assert((!Parent || ThisRoot) && "Empty constructed DomTree");
695
1.70M
    if (!ThisRoot)
696
0
      return;
697
1.70M
698
1.70M
    // Both dominators and postdominators have a single root node. In the case
699
1.70M
    // case of PostDominatorTree, this node is a virtual root.
700
1.70M
    WorkStack.push_back({ThisRoot, ThisRoot->begin()});
701
1.70M
702
1.70M
    unsigned DFSNum = 0;
703
1.70M
    ThisRoot->DFSNumIn = DFSNum++;
704
1.70M
705
54.1M
    while (!WorkStack.empty()) {
706
52.4M
      const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707
52.4M
      const auto ChildIt = WorkStack.back().second;
708
52.4M
709
52.4M
      // If we visited all of the children of this node, "recurse" back up the
710
52.4M
      // stack setting the DFOutNum.
711
52.4M
      if (ChildIt == Node->end()) {
712
27.0M
        Node->DFSNumOut = DFSNum++;
713
27.0M
        WorkStack.pop_back();
714
27.0M
      } else {
715
25.3M
        // Otherwise, recursively visit this child.
716
25.3M
        const DomTreeNodeBase<NodeT> *Child = *ChildIt;
717
25.3M
        ++WorkStack.back().second;
718
25.3M
719
25.3M
        WorkStack.push_back({Child, Child->begin()});
720
25.3M
        Child->DFSNumIn = DFSNum++;
721
25.3M
      }
722
52.4M
    }
723
1.70M
724
1.70M
    SlowQueries = 0;
725
1.70M
    DFSInfoValid = true;
726
1.70M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::updateDFSNumbers() const
Line
Count
Source
683
52.0k
  void updateDFSNumbers() const {
684
52.0k
    if (DFSInfoValid) {
685
0
      SlowQueries = 0;
686
0
      return;
687
0
    }
688
52.0k
689
52.0k
    SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
690
52.0k
                          typename DomTreeNodeBase<NodeT>::const_iterator>,
691
52.0k
                32> WorkStack;
692
52.0k
693
52.0k
    const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694
52.0k
    assert((!Parent || ThisRoot) && "Empty constructed DomTree");
695
52.0k
    if (!ThisRoot)
696
0
      return;
697
52.0k
698
52.0k
    // Both dominators and postdominators have a single root node. In the case
699
52.0k
    // case of PostDominatorTree, this node is a virtual root.
700
52.0k
    WorkStack.push_back({ThisRoot, ThisRoot->begin()});
701
52.0k
702
52.0k
    unsigned DFSNum = 0;
703
52.0k
    ThisRoot->DFSNumIn = DFSNum++;
704
52.0k
705
7.54M
    while (!WorkStack.empty()) {
706
7.49M
      const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707
7.49M
      const auto ChildIt = WorkStack.back().second;
708
7.49M
709
7.49M
      // If we visited all of the children of this node, "recurse" back up the
710
7.49M
      // stack setting the DFOutNum.
711
7.49M
      if (ChildIt == Node->end()) {
712
3.77M
        Node->DFSNumOut = DFSNum++;
713
3.77M
        WorkStack.pop_back();
714
3.77M
      } else {
715
3.72M
        // Otherwise, recursively visit this child.
716
3.72M
        const DomTreeNodeBase<NodeT> *Child = *ChildIt;
717
3.72M
        ++WorkStack.back().second;
718
3.72M
719
3.72M
        WorkStack.push_back({Child, Child->begin()});
720
3.72M
        Child->DFSNumIn = DFSNum++;
721
3.72M
      }
722
7.49M
    }
723
52.0k
724
52.0k
    SlowQueries = 0;
725
52.0k
    DFSInfoValid = true;
726
52.0k
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::updateDFSNumbers() const
Line
Count
Source
683
12
  void updateDFSNumbers() const {
684
12
    if (DFSInfoValid) {
685
0
      SlowQueries = 0;
686
0
      return;
687
0
    }
688
12
689
12
    SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
690
12
                          typename DomTreeNodeBase<NodeT>::const_iterator>,
691
12
                32> WorkStack;
692
12
693
12
    const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694
12
    assert((!Parent || ThisRoot) && "Empty constructed DomTree");
695
12
    if (!ThisRoot)
696
0
      return;
697
12
698
12
    // Both dominators and postdominators have a single root node. In the case
699
12
    // case of PostDominatorTree, this node is a virtual root.
700
12
    WorkStack.push_back({ThisRoot, ThisRoot->begin()});
701
12
702
12
    unsigned DFSNum = 0;
703
12
    ThisRoot->DFSNumIn = DFSNum++;
704
12
705
13.3k
    while (!WorkStack.empty()) {
706
13.3k
      const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707
13.3k
      const auto ChildIt = WorkStack.back().second;
708
13.3k
709
13.3k
      // If we visited all of the children of this node, "recurse" back up the
710
13.3k
      // stack setting the DFOutNum.
711
13.3k
      if (ChildIt == Node->end()) {
712
6.68k
        Node->DFSNumOut = DFSNum++;
713
6.68k
        WorkStack.pop_back();
714
6.68k
      } else {
715
6.67k
        // Otherwise, recursively visit this child.
716
6.67k
        const DomTreeNodeBase<NodeT> *Child = *ChildIt;
717
6.67k
        ++WorkStack.back().second;
718
6.67k
719
6.67k
        WorkStack.push_back({Child, Child->begin()});
720
6.67k
        Child->DFSNumIn = DFSNum++;
721
6.67k
      }
722
13.3k
    }
723
12
724
12
    SlowQueries = 0;
725
12
    DFSInfoValid = true;
726
12
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::updateDFSNumbers() const
Line
Count
Source
683
1.58M
  void updateDFSNumbers() const {
684
1.58M
    if (DFSInfoValid) {
685
89.0k
      SlowQueries = 0;
686
89.0k
      return;
687
89.0k
    }
688
1.49M
689
1.49M
    SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
690
1.49M
                          typename DomTreeNodeBase<NodeT>::const_iterator>,
691
1.49M
                32> WorkStack;
692
1.49M
693
1.49M
    const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694
1.49M
    assert((!Parent || ThisRoot) && "Empty constructed DomTree");
695
1.49M
    if (!ThisRoot)
696
0
      return;
697
1.49M
698
1.49M
    // Both dominators and postdominators have a single root node. In the case
699
1.49M
    // case of PostDominatorTree, this node is a virtual root.
700
1.49M
    WorkStack.push_back({ThisRoot, ThisRoot->begin()});
701
1.49M
702
1.49M
    unsigned DFSNum = 0;
703
1.49M
    ThisRoot->DFSNumIn = DFSNum++;
704
1.49M
705
41.5M
    while (!WorkStack.empty()) {
706
40.0M
      const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707
40.0M
      const auto ChildIt = WorkStack.back().second;
708
40.0M
709
40.0M
      // If we visited all of the children of this node, "recurse" back up the
710
40.0M
      // stack setting the DFOutNum.
711
40.0M
      if (ChildIt == Node->end()) {
712
20.7M
        Node->DFSNumOut = DFSNum++;
713
20.7M
        WorkStack.pop_back();
714
20.7M
      } else {
715
19.3M
        // Otherwise, recursively visit this child.
716
19.3M
        const DomTreeNodeBase<NodeT> *Child = *ChildIt;
717
19.3M
        ++WorkStack.back().second;
718
19.3M
719
19.3M
        WorkStack.push_back({Child, Child->begin()});
720
19.3M
        Child->DFSNumIn = DFSNum++;
721
19.3M
      }
722
40.0M
    }
723
1.49M
724
1.49M
    SlowQueries = 0;
725
1.49M
    DFSInfoValid = true;
726
1.49M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::updateDFSNumbers() const
Line
Count
Source
683
160k
  void updateDFSNumbers() const {
684
160k
    if (DFSInfoValid) {
685
863
      SlowQueries = 0;
686
863
      return;
687
863
    }
688
159k
689
159k
    SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
690
159k
                          typename DomTreeNodeBase<NodeT>::const_iterator>,
691
159k
                32> WorkStack;
692
159k
693
159k
    const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694
159k
    assert((!Parent || ThisRoot) && "Empty constructed DomTree");
695
159k
    if (!ThisRoot)
696
0
      return;
697
159k
698
159k
    // Both dominators and postdominators have a single root node. In the case
699
159k
    // case of PostDominatorTree, this node is a virtual root.
700
159k
    WorkStack.push_back({ThisRoot, ThisRoot->begin()});
701
159k
702
159k
    unsigned DFSNum = 0;
703
159k
    ThisRoot->DFSNumIn = DFSNum++;
704
159k
705
4.96M
    while (!WorkStack.empty()) {
706
4.80M
      const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707
4.80M
      const auto ChildIt = WorkStack.back().second;
708
4.80M
709
4.80M
      // If we visited all of the children of this node, "recurse" back up the
710
4.80M
      // stack setting the DFOutNum.
711
4.80M
      if (ChildIt == Node->end()) {
712
2.48M
        Node->DFSNumOut = DFSNum++;
713
2.48M
        WorkStack.pop_back();
714
2.48M
      } else {
715
2.32M
        // Otherwise, recursively visit this child.
716
2.32M
        const DomTreeNodeBase<NodeT> *Child = *ChildIt;
717
2.32M
        ++WorkStack.back().second;
718
2.32M
719
2.32M
        WorkStack.push_back({Child, Child->begin()});
720
2.32M
        Child->DFSNumIn = DFSNum++;
721
2.32M
      }
722
4.80M
    }
723
159k
724
159k
    SlowQueries = 0;
725
159k
    DFSInfoValid = true;
726
159k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::VPBlockBase, false>::updateDFSNumbers() const
llvm::DominatorTreeBase<clang::CFGBlock, true>::updateDFSNumbers() const
Line
Count
Source
683
154
  void updateDFSNumbers() const {
684
154
    if (DFSInfoValid) {
685
57
      SlowQueries = 0;
686
57
      return;
687
57
    }
688
97
689
97
    SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
690
97
                          typename DomTreeNodeBase<NodeT>::const_iterator>,
691
97
                32> WorkStack;
692
97
693
97
    const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694
97
    assert((!Parent || ThisRoot) && "Empty constructed DomTree");
695
97
    if (!ThisRoot)
696
0
      return;
697
97
698
97
    // Both dominators and postdominators have a single root node. In the case
699
97
    // case of PostDominatorTree, this node is a virtual root.
700
97
    WorkStack.push_back({ThisRoot, ThisRoot->begin()});
701
97
702
97
    unsigned DFSNum = 0;
703
97
    ThisRoot->DFSNumIn = DFSNum++;
704
97
705
1.13k
    while (!WorkStack.empty()) {
706
1.03k
      const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707
1.03k
      const auto ChildIt = WorkStack.back().second;
708
1.03k
709
1.03k
      // If we visited all of the children of this node, "recurse" back up the
710
1.03k
      // stack setting the DFOutNum.
711
1.03k
      if (ChildIt == Node->end()) {
712
568
        Node->DFSNumOut = DFSNum++;
713
568
        WorkStack.pop_back();
714
568
      } else {
715
471
        // Otherwise, recursively visit this child.
716
471
        const DomTreeNodeBase<NodeT> *Child = *ChildIt;
717
471
        ++WorkStack.back().second;
718
471
719
471
        WorkStack.push_back({Child, Child->begin()});
720
471
        Child->DFSNumIn = DFSNum++;
721
471
      }
722
1.03k
    }
723
97
724
97
    SlowQueries = 0;
725
97
    DFSInfoValid = true;
726
97
  }
727
728
  /// recalculate - compute a dominator tree for the given function
729
14.9M
  void recalculate(ParentType &Func) {
730
14.9M
    Parent = &Func;
731
14.9M
    DomTreeBuilder::Calculate(*this);
732
14.9M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::recalculate(llvm::Function&)
Line
Count
Source
729
10.2M
  void recalculate(ParentType &Func) {
730
10.2M
    Parent = &Func;
731
10.2M
    DomTreeBuilder::Calculate(*this);
732
10.2M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::recalculate(llvm::Function&)
Line
Count
Source
729
605k
  void recalculate(ParentType &Func) {
730
605k
    Parent = &Func;
731
605k
    DomTreeBuilder::Calculate(*this);
732
605k
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::recalculate(llvm::MachineFunction&)
Line
Count
Source
729
2.61M
  void recalculate(ParentType &Func) {
730
2.61M
    Parent = &Func;
731
2.61M
    DomTreeBuilder::Calculate(*this);
732
2.61M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::recalculate(llvm::MachineFunction&)
Line
Count
Source
729
1.50M
  void recalculate(ParentType &Func) {
730
1.50M
    Parent = &Func;
731
1.50M
    DomTreeBuilder::Calculate(*this);
732
1.50M
  }
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::recalculate(llvm::VPRegionBlock&)
Line
Count
Source
729
28
  void recalculate(ParentType &Func) {
730
28
    Parent = &Func;
731
28
    DomTreeBuilder::Calculate(*this);
732
28
  }
llvm::DominatorTreeBase<clang::CFGBlock, false>::recalculate(clang::CFG&)
Line
Count
Source
729
8
  void recalculate(ParentType &Func) {
730
8
    Parent = &Func;
731
8
    DomTreeBuilder::Calculate(*this);
732
8
  }
llvm::DominatorTreeBase<clang::CFGBlock, true>::recalculate(clang::CFG&)
Line
Count
Source
729
107
  void recalculate(ParentType &Func) {
730
107
    Parent = &Func;
731
107
    DomTreeBuilder::Calculate(*this);
732
107
  }
733
734
52
  void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
735
52
    Parent = &Func;
736
52
    DomTreeBuilder::CalculateWithUpdates(*this, Updates);
737
52
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::recalculate(llvm::Function&, llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*> >)
Line
Count
Source
734
52
  void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
735
52
    Parent = &Func;
736
52
    DomTreeBuilder::CalculateWithUpdates(*this, Updates);
737
52
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::recalculate(llvm::MachineFunction&, llvm::ArrayRef<llvm::cfg::Update<llvm::MachineBasicBlock*> >)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::recalculate(llvm::MachineFunction&, llvm::ArrayRef<llvm::cfg::Update<llvm::MachineBasicBlock*> >)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::recalculate(llvm::Function&, llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*> >)
738
739
  /// verify - checks if the tree is correct. There are 3 level of verification:
740
  ///  - Full --  verifies if the tree is correct by making sure all the
741
  ///             properties (including the parent and the sibling property)
742
  ///             hold.
743
  ///             Takes O(N^3) time.
744
  ///
745
  ///  - Basic -- checks if the tree is correct, but compares it to a freshly
746
  ///             constructed tree instead of checking the sibling property.
747
  ///             Takes O(N^2) time.
748
  ///
749
  ///  - Fast  -- checks basic tree structure and compares it with a freshly
750
  ///             constructed tree.
751
  ///             Takes O(N^2) time worst case, but is faster in practise (same
752
  ///             as tree construction).
753
717
  bool verify(VerificationLevel VL = VerificationLevel::Full) const {
754
717
    return DomTreeBuilder::Verify(*this, VL);
755
717
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::verify(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::VerificationLevel) const
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::verify(llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::VerificationLevel) const
llvm::DominatorTreeBase<llvm::BasicBlock, false>::verify(llvm::DominatorTreeBase<llvm::BasicBlock, false>::VerificationLevel) const
Line
Count
Source
753
368
  bool verify(VerificationLevel VL = VerificationLevel::Full) const {
754
368
    return DomTreeBuilder::Verify(*this, VL);
755
368
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::verify(llvm::DominatorTreeBase<llvm::BasicBlock, true>::VerificationLevel) const
Line
Count
Source
753
349
  bool verify(VerificationLevel VL = VerificationLevel::Full) const {
754
349
    return DomTreeBuilder::Verify(*this, VL);
755
349
  }
756
757
protected:
758
0
  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::addRoot(llvm::MachineBasicBlock*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, false>::addRoot(llvm::BasicBlock*)
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::addRoot(llvm::BasicBlock*)
759
760
24.9M
  void reset() {
761
24.9M
    DomTreeNodes.clear();
762
24.9M
    Roots.clear();
763
24.9M
    RootNode = nullptr;
764
24.9M
    Parent = nullptr;
765
24.9M
    DFSInfoValid = false;
766
24.9M
    SlowQueries = 0;
767
24.9M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::reset()
Line
Count
Source
760
19.6M
  void reset() {
761
19.6M
    DomTreeNodes.clear();
762
19.6M
    Roots.clear();
763
19.6M
    RootNode = nullptr;
764
19.6M
    Parent = nullptr;
765
19.6M
    DFSInfoValid = false;
766
19.6M
    SlowQueries = 0;
767
19.6M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::reset()
Line
Count
Source
760
1.20M
  void reset() {
761
1.20M
    DomTreeNodes.clear();
762
1.20M
    Roots.clear();
763
1.20M
    RootNode = nullptr;
764
1.20M
    Parent = nullptr;
765
1.20M
    DFSInfoValid = false;
766
1.20M
    SlowQueries = 0;
767
1.20M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::reset()
Line
Count
Source
760
2.61M
  void reset() {
761
2.61M
    DomTreeNodes.clear();
762
2.61M
    Roots.clear();
763
2.61M
    RootNode = nullptr;
764
2.61M
    Parent = nullptr;
765
2.61M
    DFSInfoValid = false;
766
2.61M
    SlowQueries = 0;
767
2.61M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::reset()
Line
Count
Source
760
1.50M
  void reset() {
761
1.50M
    DomTreeNodes.clear();
762
1.50M
    Roots.clear();
763
1.50M
    RootNode = nullptr;
764
1.50M
    Parent = nullptr;
765
1.50M
    DFSInfoValid = false;
766
1.50M
    SlowQueries = 0;
767
1.50M
  }
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::reset()
Line
Count
Source
760
28
  void reset() {
761
28
    DomTreeNodes.clear();
762
28
    Roots.clear();
763
28
    RootNode = nullptr;
764
28
    Parent = nullptr;
765
28
    DFSInfoValid = false;
766
28
    SlowQueries = 0;
767
28
  }
llvm::DominatorTreeBase<clang::CFGBlock, false>::reset()
Line
Count
Source
760
8
  void reset() {
761
8
    DomTreeNodes.clear();
762
8
    Roots.clear();
763
8
    RootNode = nullptr;
764
8
    Parent = nullptr;
765
8
    DFSInfoValid = false;
766
8
    SlowQueries = 0;
767
8
  }
llvm::DominatorTreeBase<clang::CFGBlock, true>::reset()
Line
Count
Source
760
107
  void reset() {
761
107
    DomTreeNodes.clear();
762
107
    Roots.clear();
763
107
    RootNode = nullptr;
764
107
    Parent = nullptr;
765
107
    DFSInfoValid = false;
766
107
    SlowQueries = 0;
767
107
  }
768
769
  // NewBB is split and now it has one successor. Update dominator tree to
770
  // reflect this change.
771
  template <class N>
772
1.28M
  void Split(typename GraphTraits<N>::NodeRef NewBB) {
773
1.28M
    using GraphT = GraphTraits<N>;
774
1.28M
    using NodeRef = typename GraphT::NodeRef;
775
1.28M
    assert(std::distance(GraphT::child_begin(NewBB),
776
1.28M
                         GraphT::child_end(NewBB)) == 1 &&
777
1.28M
           "NewBB should have a single successor!");
778
1.28M
    NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
779
1.28M
780
1.28M
    std::vector<NodeRef> PredBlocks;
781
1.28M
    for (const auto &Pred : children<Inverse<N>>(NewBB))
782
1.39M
      PredBlocks.push_back(Pred);
783
1.28M
784
1.28M
    assert(!PredBlocks.empty() && "No predblocks?");
785
1.28M
786
1.28M
    bool NewBBDominatesNewBBSucc = true;
787
2.56M
    for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
788
2.56M
      if (Pred != NewBB && 
!dominates(NewBBSucc, Pred)1.28M
&&
789
2.56M
          
isReachableFromEntry(Pred)782k
) {
790
782k
        NewBBDominatesNewBBSucc = false;
791
782k
        break;
792
782k
      }
793
2.56M
    }
794
1.28M
795
1.28M
    // Find NewBB's immediate dominator and create new dominator tree node for
796
1.28M
    // NewBB.
797
1.28M
    NodeT *NewBBIDom = nullptr;
798
1.28M
    unsigned i = 0;
799
1.28M
    for (i = 0; i < PredBlocks.size(); 
++i0
)
800
1.28M
      if (isReachableFromEntry(PredBlocks[i])) {
801
1.28M
        NewBBIDom = PredBlocks[i];
802
1.28M
        break;
803
1.28M
      }
804
1.28M
805
1.28M
    // It's possible that none of the predecessors of NewBB are reachable;
806
1.28M
    // in that case, NewBB itself is unreachable, so nothing needs to be
807
1.28M
    // changed.
808
1.28M
    if (!NewBBIDom) 
return0
;
809
1.28M
810
1.39M
    
for (i = i + 1; 1.28M
i < PredBlocks.size();
++i114k
) {
811
114k
      if (isReachableFromEntry(PredBlocks[i]))
812
114k
        NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
813
114k
    }
814
1.28M
815
1.28M
    // Create the new dominator tree node... and set the idom of NewBB.
816
1.28M
    DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
817
1.28M
818
1.28M
    // If NewBB strictly dominates other blocks, then it is now the immediate
819
1.28M
    // dominator of NewBBSucc.  Update the dominator tree as appropriate.
820
1.28M
    if (NewBBDominatesNewBBSucc) {
821
499k
      DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
822
499k
      changeImmediateDominator(NewBBSuccNode, NewBBNode);
823
499k
    }
824
1.28M
  }
Unexecuted instantiation: void llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::Split<llvm::Inverse<llvm::MachineBasicBlock*> >(llvm::GraphTraits<llvm::Inverse<llvm::MachineBasicBlock*> >::NodeRef)
Unexecuted instantiation: void llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::Split<llvm::MachineBasicBlock*>(llvm::GraphTraits<llvm::MachineBasicBlock*>::NodeRef)
Unexecuted instantiation: void llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::Split<llvm::Inverse<llvm::MachineBasicBlock*> >(llvm::GraphTraits<llvm::Inverse<llvm::MachineBasicBlock*> >::NodeRef)
Unexecuted instantiation: void llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::Split<llvm::MachineBasicBlock*>(llvm::GraphTraits<llvm::MachineBasicBlock*>::NodeRef)
void llvm::DominatorTreeBase<llvm::BasicBlock, false>::Split<llvm::BasicBlock*>(llvm::GraphTraits<llvm::BasicBlock*>::NodeRef)
Line
Count
Source
772
1.28M
  void Split(typename GraphTraits<N>::NodeRef NewBB) {
773
1.28M
    using GraphT = GraphTraits<N>;
774
1.28M
    using NodeRef = typename GraphT::NodeRef;
775
1.28M
    assert(std::distance(GraphT::child_begin(NewBB),
776
1.28M
                         GraphT::child_end(NewBB)) == 1 &&
777
1.28M
           "NewBB should have a single successor!");
778
1.28M
    NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
779
1.28M
780
1.28M
    std::vector<NodeRef> PredBlocks;
781
1.28M
    for (const auto &Pred : children<Inverse<N>>(NewBB))
782
1.39M
      PredBlocks.push_back(Pred);
783
1.28M
784
1.28M
    assert(!PredBlocks.empty() && "No predblocks?");
785
1.28M
786
1.28M
    bool NewBBDominatesNewBBSucc = true;
787
2.56M
    for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
788
2.56M
      if (Pred != NewBB && 
!dominates(NewBBSucc, Pred)1.28M
&&
789
2.56M
          
isReachableFromEntry(Pred)782k
) {
790
782k
        NewBBDominatesNewBBSucc = false;
791
782k
        break;
792
782k
      }
793
2.56M
    }
794
1.28M
795
1.28M
    // Find NewBB's immediate dominator and create new dominator tree node for
796
1.28M
    // NewBB.
797
1.28M
    NodeT *NewBBIDom = nullptr;
798
1.28M
    unsigned i = 0;
799
1.28M
    for (i = 0; i < PredBlocks.size(); 
++i0
)
800
1.28M
      if (isReachableFromEntry(PredBlocks[i])) {
801
1.28M
        NewBBIDom = PredBlocks[i];
802
1.28M
        break;
803
1.28M
      }
804
1.28M
805
1.28M
    // It's possible that none of the predecessors of NewBB are reachable;
806
1.28M
    // in that case, NewBB itself is unreachable, so nothing needs to be
807
1.28M
    // changed.
808
1.28M
    if (!NewBBIDom) 
return0
;
809
1.28M
810
1.39M
    
for (i = i + 1; 1.28M
i < PredBlocks.size();
++i114k
) {
811
114k
      if (isReachableFromEntry(PredBlocks[i]))
812
114k
        NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
813
114k
    }
814
1.28M
815
1.28M
    // Create the new dominator tree node... and set the idom of NewBB.
816
1.28M
    DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
817
1.28M
818
1.28M
    // If NewBB strictly dominates other blocks, then it is now the immediate
819
1.28M
    // dominator of NewBBSucc.  Update the dominator tree as appropriate.
820
1.28M
    if (NewBBDominatesNewBBSucc) {
821
499k
      DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
822
499k
      changeImmediateDominator(NewBBSuccNode, NewBBNode);
823
499k
    }
824
1.28M
  }
Unexecuted instantiation: void llvm::DominatorTreeBase<llvm::BasicBlock, true>::Split<llvm::Inverse<llvm::BasicBlock*> >(llvm::GraphTraits<llvm::Inverse<llvm::BasicBlock*> >::NodeRef)
Unexecuted instantiation: void llvm::DominatorTreeBase<llvm::BasicBlock, false>::Split<llvm::Inverse<llvm::BasicBlock*> >(llvm::GraphTraits<llvm::Inverse<llvm::BasicBlock*> >::NodeRef)
Unexecuted instantiation: void llvm::DominatorTreeBase<llvm::BasicBlock, true>::Split<llvm::BasicBlock*>(llvm::GraphTraits<llvm::BasicBlock*>::NodeRef)
825
826
 private:
827
  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
828
16.4M
                               const DomTreeNodeBase<NodeT> *B) const {
829
16.4M
    assert(A != B);
830
16.4M
    assert(isReachableFromEntry(B));
831
16.4M
    assert(isReachableFromEntry(A));
832
16.4M
833
16.4M
    const unsigned ALevel = A->getLevel();
834
16.4M
    const DomTreeNodeBase<NodeT> *IDom;
835
16.4M
836
16.4M
    // Don't walk nodes above A's subtree. When we reach A's level, we must
837
16.4M
    // either find A or be in some other subtree not dominated by A.
838
92.2M
    while ((IDom = B->getIDom()) != nullptr && 
IDom->getLevel() >= ALevel91.8M
)
839
75.7M
      B = IDom;  // Walk up the tree
840
16.4M
841
16.4M
    return B == A;
842
16.4M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::dominatedBySlowTreeWalk(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Line
Count
Source
828
4.00M
                               const DomTreeNodeBase<NodeT> *B) const {
829
4.00M
    assert(A != B);
830
4.00M
    assert(isReachableFromEntry(B));
831
4.00M
    assert(isReachableFromEntry(A));
832
4.00M
833
4.00M
    const unsigned ALevel = A->getLevel();
834
4.00M
    const DomTreeNodeBase<NodeT> *IDom;
835
4.00M
836
4.00M
    // Don't walk nodes above A's subtree. When we reach A's level, we must
837
4.00M
    // either find A or be in some other subtree not dominated by A.
838
20.8M
    while ((IDom = B->getIDom()) != nullptr && 
IDom->getLevel() >= ALevel20.8M
)
839
16.8M
      B = IDom;  // Walk up the tree
840
4.00M
841
4.00M
    return B == A;
842
4.00M
  }
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::dominatedBySlowTreeWalk(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*, llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*) const
Line
Count
Source
828
49.3k
                               const DomTreeNodeBase<NodeT> *B) const {
829
49.3k
    assert(A != B);
830
49.3k
    assert(isReachableFromEntry(B));
831
49.3k
    assert(isReachableFromEntry(A));
832
49.3k
833
49.3k
    const unsigned ALevel = A->getLevel();
834
49.3k
    const DomTreeNodeBase<NodeT> *IDom;
835
49.3k
836
49.3k
    // Don't walk nodes above A's subtree. When we reach A's level, we must
837
49.3k
    // either find A or be in some other subtree not dominated by A.
838
389k
    while ((IDom = B->getIDom()) != nullptr && 
IDom->getLevel() >= ALevel389k
)
839
339k
      B = IDom;  // Walk up the tree
840
49.3k
841
49.3k
    return B == A;
842
49.3k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, false>::dominatedBySlowTreeWalk(llvm::DomTreeNodeBase<llvm::BasicBlock> const*, llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
828
12.4M
                               const DomTreeNodeBase<NodeT> *B) const {
829
12.4M
    assert(A != B);
830
12.4M
    assert(isReachableFromEntry(B));
831
12.4M
    assert(isReachableFromEntry(A));
832
12.4M
833
12.4M
    const unsigned ALevel = A->getLevel();
834
12.4M
    const DomTreeNodeBase<NodeT> *IDom;
835
12.4M
836
12.4M
    // Don't walk nodes above A's subtree. When we reach A's level, we must
837
12.4M
    // either find A or be in some other subtree not dominated by A.
838
70.9M
    while ((IDom = B->getIDom()) != nullptr && 
IDom->getLevel() >= ALevel70.5M
)
839
58.5M
      B = IDom;  // Walk up the tree
840
12.4M
841
12.4M
    return B == A;
842
12.4M
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::dominatedBySlowTreeWalk(llvm::DomTreeNodeBase<llvm::BasicBlock> const*, llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const
Line
Count
Source
828
124
                               const DomTreeNodeBase<NodeT> *B) const {
829
124
    assert(A != B);
830
124
    assert(isReachableFromEntry(B));
831
124
    assert(isReachableFromEntry(A));
832
124
833
124
    const unsigned ALevel = A->getLevel();
834
124
    const DomTreeNodeBase<NodeT> *IDom;
835
124
836
124
    // Don't walk nodes above A's subtree. When we reach A's level, we must
837
124
    // either find A or be in some other subtree not dominated by A.
838
412
    while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
839
288
      B = IDom;  // Walk up the tree
840
124
841
124
    return B == A;
842
124
  }
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::dominatedBySlowTreeWalk(llvm::DomTreeNodeBase<llvm::VPBlockBase> const*, llvm::DomTreeNodeBase<llvm::VPBlockBase> const*) const
Line
Count
Source
828
39
                               const DomTreeNodeBase<NodeT> *B) const {
829
39
    assert(A != B);
830
39
    assert(isReachableFromEntry(B));
831
39
    assert(isReachableFromEntry(A));
832
39
833
39
    const unsigned ALevel = A->getLevel();
834
39
    const DomTreeNodeBase<NodeT> *IDom;
835
39
836
39
    // Don't walk nodes above A's subtree. When we reach A's level, we must
837
39
    // either find A or be in some other subtree not dominated by A.
838
123
    while ((IDom = B->getIDom()) != nullptr && 
IDom->getLevel() >= ALevel113
)
839
84
      B = IDom;  // Walk up the tree
840
39
841
39
    return B == A;
842
39
  }
843
844
  /// Wipe this tree's state without releasing any resources.
845
  ///
846
  /// This is essentially a post-move helper only. It leaves the object in an
847
  /// assignable and destroyable state, but otherwise invalid.
848
20.5k
  void wipe() {
849
20.5k
    DomTreeNodes.clear();
850
20.5k
    RootNode = nullptr;
851
20.5k
    Parent = nullptr;
852
20.5k
  }
llvm::DominatorTreeBase<llvm::BasicBlock, true>::wipe()
Line
Count
Source
848
2.50k
  void wipe() {
849
2.50k
    DomTreeNodes.clear();
850
2.50k
    RootNode = nullptr;
851
2.50k
    Parent = nullptr;
852
2.50k
  }
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::wipe()
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::wipe()
llvm::DominatorTreeBase<llvm::BasicBlock, false>::wipe()
Line
Count
Source
848
18.0k
  void wipe() {
849
18.0k
    DomTreeNodes.clear();
850
18.0k
    RootNode = nullptr;
851
18.0k
    Parent = nullptr;
852
18.0k
  }
853
};
854
855
template <typename T>
856
using DomTreeBase = DominatorTreeBase<T, false>;
857
858
template <typename T>
859
using PostDomTreeBase = DominatorTreeBase<T, true>;
860
861
// These two functions are declared out of line as a workaround for building
862
// with old (< r147295) versions of clang because of pr11642.
863
template <typename NodeT, bool IsPostDom>
864
bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
865
161M
                                                    const NodeT *B) const {
866
161M
  if (A == B)
867
10.9M
    return true;
868
150M
869
150M
  // Cast away the const qualifiers here. This is ok since
870
150M
  // this function doesn't actually return the values returned
871
150M
  // from getNode.
872
150M
  return dominates(getNode(const_cast<NodeT *>(A)),
873
150M
                   getNode(const_cast<NodeT *>(B)));
874
150M
}
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::dominates(llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*) const
Line
Count
Source
865
31.6M
                                                    const NodeT *B) const {
866
31.6M
  if (A == B)
867
3.75M
    return true;
868
27.9M
869
27.9M
  // Cast away the const qualifiers here. This is ok since
870
27.9M
  // this function doesn't actually return the values returned
871
27.9M
  // from getNode.
872
27.9M
  return dominates(getNode(const_cast<NodeT *>(A)),
873
27.9M
                   getNode(const_cast<NodeT *>(B)));
874
27.9M
}
llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::dominates(llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*) const
Line
Count
Source
865
7.09M
                                                    const NodeT *B) const {
866
7.09M
  if (A == B)
867
342k
    return true;
868
6.75M
869
6.75M
  // Cast away the const qualifiers here. This is ok since
870
6.75M
  // this function doesn't actually return the values returned
871
6.75M
  // from getNode.
872
6.75M
  return dominates(getNode(const_cast<NodeT *>(A)),
873
6.75M
                   getNode(const_cast<NodeT *>(B)));
874
6.75M
}
llvm::DominatorTreeBase<llvm::BasicBlock, false>::dominates(llvm::BasicBlock const*, llvm::BasicBlock const*) const
Line
Count
Source
865
123M
                                                    const NodeT *B) const {
866
123M
  if (A == B)
867
6.88M
    return true;
868
116M
869
116M
  // Cast away the const qualifiers here. This is ok since
870
116M
  // this function doesn't actually return the values returned
871
116M
  // from getNode.
872
116M
  return dominates(getNode(const_cast<NodeT *>(A)),
873
116M
                   getNode(const_cast<NodeT *>(B)));
874
116M
}
llvm::DominatorTreeBase<llvm::BasicBlock, true>::dominates(llvm::BasicBlock const*, llvm::BasicBlock const*) const
Line
Count
Source
865
1.33k
                                                    const NodeT *B) const {
866
1.33k
  if (A == B)
867
432
    return true;
868
901
869
901
  // Cast away the const qualifiers here. This is ok since
870
901
  // this function doesn't actually return the values returned
871
901
  // from getNode.
872
901
  return dominates(getNode(const_cast<NodeT *>(A)),
873
901
                   getNode(const_cast<NodeT *>(B)));
874
901
}
llvm::DominatorTreeBase<llvm::VPBlockBase, false>::dominates(llvm::VPBlockBase const*, llvm::VPBlockBase const*) const
Line
Count
Source
865
181
                                                    const NodeT *B) const {
866
181
  if (A == B)
867
27
    return true;
868
154
869
154
  // Cast away the const qualifiers here. This is ok since
870
154
  // this function doesn't actually return the values returned
871
154
  // from getNode.
872
154
  return dominates(getNode(const_cast<NodeT *>(A)),
873
154
                   getNode(const_cast<NodeT *>(B)));
874
154
}
875
template <typename NodeT, bool IsPostDom>
876
bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
877
741k
    const NodeT *A, const NodeT *B) const {
878
741k
  if (A == B)
879
176k
    return false;
880
565k
881
565k
  // Cast away the const qualifiers here. This is ok since
882
565k
  // this function doesn't actually return the values returned
883
565k
  // from getNode.
884
565k
  return dominates(getNode(const_cast<NodeT *>(A)),
885
565k
                   getNode(const_cast<NodeT *>(B)));
886
565k
}
llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::properlyDominates(llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*) const
Line
Count
Source
877
14.2k
    const NodeT *A, const NodeT *B) const {
878
14.2k
  if (A == B)
879
250
    return false;
880
13.9k
881
13.9k
  // Cast away the const qualifiers here. This is ok since
882
13.9k
  // this function doesn't actually return the values returned
883
13.9k
  // from getNode.
884
13.9k
  return dominates(getNode(const_cast<NodeT *>(A)),
885
13.9k
                   getNode(const_cast<NodeT *>(B)));
886
13.9k
}
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::MachineBasicBlock, true>::properlyDominates(llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*) const
llvm::DominatorTreeBase<llvm::BasicBlock, false>::properlyDominates(llvm::BasicBlock const*, llvm::BasicBlock const*) const
Line
Count
Source
877
726k
    const NodeT *A, const NodeT *B) const {
878
726k
  if (A == B)
879
175k
    return false;
880
551k
881
551k
  // Cast away the const qualifiers here. This is ok since
882
551k
  // this function doesn't actually return the values returned
883
551k
  // from getNode.
884
551k
  return dominates(getNode(const_cast<NodeT *>(A)),
885
551k
                   getNode(const_cast<NodeT *>(B)));
886
551k
}
Unexecuted instantiation: llvm::DominatorTreeBase<llvm::BasicBlock, true>::properlyDominates(llvm::BasicBlock const*, llvm::BasicBlock const*) const
887
888
} // end namespace llvm
889
890
#endif // LLVM_SUPPORT_GENERICDOMTREE_H