Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h
Line
Count
Source
1
//===- IteratedDominanceFrontier.h - Calculate IDF --------------*- 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
/// Compute iterated dominance frontiers using a linear time algorithm.
10
///
11
/// The algorithm used here is based on:
12
///
13
///   Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
14
///   In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
15
///   Programming Languages
16
///   POPL '95. ACM, New York, NY, 62-73.
17
///
18
/// It has been modified to not explicitly use the DJ graph data structure and
19
/// to directly compute pruned SSA using per-variable liveness information.
20
//
21
//===----------------------------------------------------------------------===//
22
23
#ifndef LLVM_SUPPORT_GENERIC_IDF_H
24
#define LLVM_SUPPORT_GENERIC_IDF_H
25
26
#include "llvm/ADT/DenseMap.h"
27
#include "llvm/ADT/SmallPtrSet.h"
28
#include "llvm/ADT/SmallVector.h"
29
#include "llvm/Support/GenericDomTree.h"
30
#include <queue>
31
32
namespace llvm {
33
34
namespace IDFCalculatorDetail {
35
36
/// Generic utility class used for getting the children of a basic block.
37
/// May be specialized if, for example, one wouldn't like to return nullpointer
38
/// successors.
39
template <class NodeTy, bool IsPostDom> struct ChildrenGetterTy {
40
  using NodeRef = typename GraphTraits<NodeTy>::NodeRef;
41
  using ChildrenTy = SmallVector<NodeRef, 8>;
42
43
  ChildrenTy get(const NodeRef &N);
44
};
45
46
} // end of namespace IDFCalculatorDetail
47
48
/// Determine the iterated dominance frontier, given a set of defining
49
/// blocks, and optionally, a set of live-in blocks.
50
///
51
/// In turn, the results can be used to place phi nodes.
52
///
53
/// This algorithm is a linear time computation of Iterated Dominance Frontiers,
54
/// pruned using the live-in set.
55
/// By default, liveness is not used to prune the IDF computation.
56
/// The template parameters should be of a CFG block type.
57
template <class NodeTy, bool IsPostDom> class IDFCalculatorBase {
58
public:
59
  using OrderedNodeTy =
60
      typename std::conditional<IsPostDom, Inverse<NodeTy *>, NodeTy *>::type;
61
  using ChildrenGetterTy =
62
      IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>;
63
64
1.16M
  IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
llvm::IDFCalculatorBase<llvm::BasicBlock, false>::IDFCalculatorBase(llvm::DominatorTreeBase<llvm::BasicBlock, false>&)
Line
Count
Source
64
1.00M
  IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
llvm::IDFCalculatorBase<llvm::BasicBlock, true>::IDFCalculatorBase(llvm::DominatorTreeBase<llvm::BasicBlock, true>&)
Line
Count
Source
64
161k
  IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
llvm::IDFCalculatorBase<clang::CFGBlock, true>::IDFCalculatorBase(llvm::DominatorTreeBase<clang::CFGBlock, true>&)
Line
Count
Source
64
99
  IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
65
66
  IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT,
67
                    const ChildrenGetterTy &C)
68
115
      : DT(DT), ChildrenGetter(C) {}
69
70
  /// Give the IDF calculator the set of blocks in which the value is
71
  /// defined.  This is equivalent to the set of starting blocks it should be
72
  /// calculating the IDF for (though later gets pruned based on liveness).
73
  ///
74
  /// Note: This set *must* live for the entire lifetime of the IDF calculator.
75
1.02M
  void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
76
1.02M
    DefBlocks = &Blocks;
77
1.02M
  }
llvm::IDFCalculatorBase<llvm::BasicBlock, false>::setDefiningBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&)
Line
Count
Source
75
862k
  void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
76
862k
    DefBlocks = &Blocks;
77
862k
  }
llvm::IDFCalculatorBase<llvm::BasicBlock, true>::setDefiningBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&)
Line
Count
Source
75
160k
  void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
76
160k
    DefBlocks = &Blocks;
77
160k
  }
llvm::IDFCalculatorBase<clang::CFGBlock, true>::setDefiningBlocks(llvm::SmallPtrSetImpl<clang::CFGBlock*> const&)
Line
Count
Source
75
154
  void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
76
154
    DefBlocks = &Blocks;
77
154
  }
78
79
  /// Give the IDF calculator the set of blocks in which the value is
80
  /// live on entry to the block.   This is used to prune the IDF calculation to
81
  /// not include blocks where any phi insertion would be dead.
82
  ///
83
  /// Note: This set *must* live for the entire lifetime of the IDF calculator.
84
297k
  void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
85
297k
    LiveInBlocks = &Blocks;
86
297k
    useLiveIn = true;
87
297k
  }
llvm::IDFCalculatorBase<llvm::BasicBlock, true>::setLiveInBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&)
Line
Count
Source
84
160k
  void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
85
160k
    LiveInBlocks = &Blocks;
86
160k
    useLiveIn = true;
87
160k
  }
llvm::IDFCalculatorBase<llvm::BasicBlock, false>::setLiveInBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&)
Line
Count
Source
84
137k
  void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
85
137k
    LiveInBlocks = &Blocks;
86
137k
    useLiveIn = true;
87
137k
  }
88
89
  /// Reset the live-in block set to be empty, and tell the IDF
90
  /// calculator to not use liveness anymore.
91
  void resetLiveInBlocks() {
92
    LiveInBlocks = nullptr;
93
    useLiveIn = false;
94
  }
95
96
  /// Calculate iterated dominance frontiers
97
  ///
98
  /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
99
  /// the file-level comment.  It performs DF->IDF pruning using the live-in
100
  /// set, to avoid computing the IDF for blocks where an inserted PHI node
101
  /// would be dead.
102
  void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks);
103
104
private:
105
  DominatorTreeBase<NodeTy, IsPostDom> &DT;
106
  ChildrenGetterTy ChildrenGetter;
107
  bool useLiveIn = false;
108
  const SmallPtrSetImpl<NodeTy *> *LiveInBlocks;
109
  const SmallPtrSetImpl<NodeTy *> *DefBlocks;
110
};
111
112
//===----------------------------------------------------------------------===//
113
// Implementation.
114
//===----------------------------------------------------------------------===//
115
116
namespace IDFCalculatorDetail {
117
118
template <class NodeTy, bool IsPostDom>
119
typename ChildrenGetterTy<NodeTy, IsPostDom>::ChildrenTy
120
ChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) {
121
  using OrderedNodeTy =
122
      typename IDFCalculatorBase<NodeTy, IsPostDom>::OrderedNodeTy;
123
124
  auto Children = children<OrderedNodeTy>(N);
125
  return {Children.begin(), Children.end()};
126
}
127
128
} // end of namespace IDFCalculatorDetail
129
130
template <class NodeTy, bool IsPostDom>
131
void IDFCalculatorBase<NodeTy, IsPostDom>::calculate(
132
1.02M
    SmallVectorImpl<NodeTy *> &PHIBlocks) {
133
1.02M
  // Use a priority queue keyed on dominator tree level so that inserted nodes
134
1.02M
  // are handled from the bottom of the dominator tree upwards. We also augment
135
1.02M
  // the level with a DFS number to ensure that the blocks are ordered in a
136
1.02M
  // deterministic way.
137
1.02M
  using DomTreeNodePair =
138
1.02M
      std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
139
1.02M
  using IDFPriorityQueue =
140
1.02M
      std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
141
1.02M
                          less_second>;
142
1.02M
143
1.02M
  IDFPriorityQueue PQ;
144
1.02M
145
1.02M
  DT.updateDFSNumbers();
146
1.02M
147
4.87M
  for (NodeTy *BB : *DefBlocks) {
148
4.87M
    if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB))
149
4.87M
      PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
150
4.87M
  }
151
1.02M
152
1.02M
  SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
153
1.02M
  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
154
1.02M
  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
155
1.02M
156
7.00M
  while (!PQ.empty()) {
157
5.98M
    DomTreeNodePair RootPair = PQ.top();
158
5.98M
    PQ.pop();
159
5.98M
    DomTreeNodeBase<NodeTy> *Root = RootPair.first;
160
5.98M
    unsigned RootLevel = RootPair.second.first;
161
5.98M
162
5.98M
    // Walk all dominator tree children of Root, inspecting their CFG edges with
163
5.98M
    // targets elsewhere on the dominator tree. Only targets whose level is at
164
5.98M
    // most Root's level are added to the iterated dominance frontier of the
165
5.98M
    // definition set.
166
5.98M
167
5.98M
    Worklist.clear();
168
5.98M
    Worklist.push_back(Root);
169
5.98M
    VisitedWorklist.insert(Root);
170
5.98M
171
14.9M
    while (!Worklist.empty()) {
172
8.97M
      DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val();
173
8.97M
      NodeTy *BB = Node->getBlock();
174
8.97M
      // Succ is the successor in the direction we are calculating IDF, so it is
175
8.97M
      // successor for IDF, and predecessor for Reverse IDF.
176
12.3M
      auto DoWork = [&](NodeTy *Succ) {
177
12.3M
        DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
178
12.3M
179
12.3M
        const unsigned SuccLevel = SuccNode->getLevel();
180
12.3M
        if (SuccLevel > RootLevel)
181
8.04M
          return;
182
4.27M
183
4.27M
        if (!VisitedPQ.insert(SuccNode).second)
184
1.56M
          return;
185
2.71M
186
2.71M
        NodeTy *SuccBB = SuccNode->getBlock();
187
2.71M
        if (useLiveIn && 
!LiveInBlocks->count(SuccBB)1.48M
)
188
379k
          return;
189
2.33M
190
2.33M
        PHIBlocks.emplace_back(SuccBB);
191
2.33M
        if (!DefBlocks->count(SuccBB))
192
1.10M
          PQ.push(std::make_pair(
193
1.10M
              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
194
2.33M
      };
llvm::IDFCalculatorBase<llvm::BasicBlock, false>::calculate(llvm::SmallVectorImpl<llvm::BasicBlock*>&)::'lambda'(llvm::BasicBlock*)::operator()(llvm::BasicBlock*) const
Line
Count
Source
176
8.92M
      auto DoWork = [&](NodeTy *Succ) {
177
8.92M
        DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
178
8.92M
179
8.92M
        const unsigned SuccLevel = SuccNode->getLevel();
180
8.92M
        if (SuccLevel > RootLevel)
181
6.39M
          return;
182
2.53M
183
2.53M
        if (!VisitedPQ.insert(SuccNode).second)
184
996k
          return;
185
1.53M
186
1.53M
        NodeTy *SuccBB = SuccNode->getBlock();
187
1.53M
        if (useLiveIn && 
!LiveInBlocks->count(SuccBB)309k
)
188
113k
          return;
189
1.42M
190
1.42M
        PHIBlocks.emplace_back(SuccBB);
191
1.42M
        if (!DefBlocks->count(SuccBB))
192
824k
          PQ.push(std::make_pair(
193
824k
              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
194
1.42M
      };
llvm::IDFCalculatorBase<llvm::BasicBlock, true>::calculate(llvm::SmallVectorImpl<llvm::BasicBlock*>&)::'lambda'(llvm::BasicBlock*)::operator()(llvm::BasicBlock*) const
Line
Count
Source
176
3.39M
      auto DoWork = [&](NodeTy *Succ) {
177
3.39M
        DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
178
3.39M
179
3.39M
        const unsigned SuccLevel = SuccNode->getLevel();
180
3.39M
        if (SuccLevel > RootLevel)
181
1.64M
          return;
182
1.74M
183
1.74M
        if (!VisitedPQ.insert(SuccNode).second)
184
565k
          return;
185
1.17M
186
1.17M
        NodeTy *SuccBB = SuccNode->getBlock();
187
1.17M
        if (useLiveIn && 
!LiveInBlocks->count(SuccBB)1.17M
)
188
265k
          return;
189
913k
190
913k
        PHIBlocks.emplace_back(SuccBB);
191
913k
        if (!DefBlocks->count(SuccBB))
192
284k
          PQ.push(std::make_pair(
193
284k
              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
194
913k
      };
llvm::IDFCalculatorBase<clang::CFGBlock, true>::calculate(llvm::SmallVectorImpl<clang::CFGBlock*>&)::'lambda'(clang::CFGBlock*)::operator()(clang::CFGBlock*) const
Line
Count
Source
176
608
      auto DoWork = [&](NodeTy *Succ) {
177
608
        DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
178
608
179
608
        const unsigned SuccLevel = SuccNode->getLevel();
180
608
        if (SuccLevel > RootLevel)
181
503
          return;
182
105
183
105
        if (!VisitedPQ.insert(SuccNode).second)
184
0
          return;
185
105
186
105
        NodeTy *SuccBB = SuccNode->getBlock();
187
105
        if (useLiveIn && 
!LiveInBlocks->count(SuccBB)0
)
188
0
          return;
189
105
190
105
        PHIBlocks.emplace_back(SuccBB);
191
105
        if (!DefBlocks->count(SuccBB))
192
97
          PQ.push(std::make_pair(
193
97
              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
194
105
      };
195
8.97M
196
8.97M
      for (auto Succ : ChildrenGetter.get(BB))
197
12.3M
        DoWork(Succ);
198
8.97M
199
8.97M
      for (auto DomChild : *Node) {
200
7.51M
        if (VisitedWorklist.insert(DomChild).second)
201
2.98M
          Worklist.push_back(DomChild);
202
7.51M
      }
203
8.97M
    }
204
5.98M
  }
205
1.02M
}
llvm::IDFCalculatorBase<llvm::BasicBlock, false>::calculate(llvm::SmallVectorImpl<llvm::BasicBlock*>&)
Line
Count
Source
132
862k
    SmallVectorImpl<NodeTy *> &PHIBlocks) {
133
862k
  // Use a priority queue keyed on dominator tree level so that inserted nodes
134
862k
  // are handled from the bottom of the dominator tree upwards. We also augment
135
862k
  // the level with a DFS number to ensure that the blocks are ordered in a
136
862k
  // deterministic way.
137
862k
  using DomTreeNodePair =
138
862k
      std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
139
862k
  using IDFPriorityQueue =
140
862k
      std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
141
862k
                          less_second>;
142
862k
143
862k
  IDFPriorityQueue PQ;
144
862k
145
862k
  DT.updateDFSNumbers();
146
862k
147
2.85M
  for (NodeTy *BB : *DefBlocks) {
148
2.85M
    if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB))
149
2.84M
      PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
150
2.85M
  }
151
862k
152
862k
  SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
153
862k
  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
154
862k
  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
155
862k
156
4.53M
  while (!PQ.empty()) {
157
3.67M
    DomTreeNodePair RootPair = PQ.top();
158
3.67M
    PQ.pop();
159
3.67M
    DomTreeNodeBase<NodeTy> *Root = RootPair.first;
160
3.67M
    unsigned RootLevel = RootPair.second.first;
161
3.67M
162
3.67M
    // Walk all dominator tree children of Root, inspecting their CFG edges with
163
3.67M
    // targets elsewhere on the dominator tree. Only targets whose level is at
164
3.67M
    // most Root's level are added to the iterated dominance frontier of the
165
3.67M
    // definition set.
166
3.67M
167
3.67M
    Worklist.clear();
168
3.67M
    Worklist.push_back(Root);
169
3.67M
    VisitedWorklist.insert(Root);
170
3.67M
171
10.2M
    while (!Worklist.empty()) {
172
6.62M
      DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val();
173
6.62M
      NodeTy *BB = Node->getBlock();
174
6.62M
      // Succ is the successor in the direction we are calculating IDF, so it is
175
6.62M
      // successor for IDF, and predecessor for Reverse IDF.
176
6.62M
      auto DoWork = [&](NodeTy *Succ) {
177
6.62M
        DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
178
6.62M
179
6.62M
        const unsigned SuccLevel = SuccNode->getLevel();
180
6.62M
        if (SuccLevel > RootLevel)
181
6.62M
          return;
182
6.62M
183
6.62M
        if (!VisitedPQ.insert(SuccNode).second)
184
6.62M
          return;
185
6.62M
186
6.62M
        NodeTy *SuccBB = SuccNode->getBlock();
187
6.62M
        if (useLiveIn && !LiveInBlocks->count(SuccBB))
188
6.62M
          return;
189
6.62M
190
6.62M
        PHIBlocks.emplace_back(SuccBB);
191
6.62M
        if (!DefBlocks->count(SuccBB))
192
6.62M
          PQ.push(std::make_pair(
193
6.62M
              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
194
6.62M
      };
195
6.62M
196
6.62M
      for (auto Succ : ChildrenGetter.get(BB))
197
8.92M
        DoWork(Succ);
198
6.62M
199
6.62M
      for (auto DomChild : *Node) {
200
5.40M
        if (VisitedWorklist.insert(DomChild).second)
201
2.95M
          Worklist.push_back(DomChild);
202
5.40M
      }
203
6.62M
    }
204
3.67M
  }
205
862k
}
llvm::IDFCalculatorBase<llvm::BasicBlock, true>::calculate(llvm::SmallVectorImpl<llvm::BasicBlock*>&)
Line
Count
Source
132
160k
    SmallVectorImpl<NodeTy *> &PHIBlocks) {
133
160k
  // Use a priority queue keyed on dominator tree level so that inserted nodes
134
160k
  // are handled from the bottom of the dominator tree upwards. We also augment
135
160k
  // the level with a DFS number to ensure that the blocks are ordered in a
136
160k
  // deterministic way.
137
160k
  using DomTreeNodePair =
138
160k
      std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
139
160k
  using IDFPriorityQueue =
140
160k
      std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
141
160k
                          less_second>;
142
160k
143
160k
  IDFPriorityQueue PQ;
144
160k
145
160k
  DT.updateDFSNumbers();
146
160k
147
2.02M
  for (NodeTy *BB : *DefBlocks) {
148
2.02M
    if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB))
149
2.02M
      PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
150
2.02M
  }
151
160k
152
160k
  SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
153
160k
  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
154
160k
  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
155
160k
156
2.47M
  while (!PQ.empty()) {
157
2.31M
    DomTreeNodePair RootPair = PQ.top();
158
2.31M
    PQ.pop();
159
2.31M
    DomTreeNodeBase<NodeTy> *Root = RootPair.first;
160
2.31M
    unsigned RootLevel = RootPair.second.first;
161
2.31M
162
2.31M
    // Walk all dominator tree children of Root, inspecting their CFG edges with
163
2.31M
    // targets elsewhere on the dominator tree. Only targets whose level is at
164
2.31M
    // most Root's level are added to the iterated dominance frontier of the
165
2.31M
    // definition set.
166
2.31M
167
2.31M
    Worklist.clear();
168
2.31M
    Worklist.push_back(Root);
169
2.31M
    VisitedWorklist.insert(Root);
170
2.31M
171
4.65M
    while (!Worklist.empty()) {
172
2.34M
      DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val();
173
2.34M
      NodeTy *BB = Node->getBlock();
174
2.34M
      // Succ is the successor in the direction we are calculating IDF, so it is
175
2.34M
      // successor for IDF, and predecessor for Reverse IDF.
176
2.34M
      auto DoWork = [&](NodeTy *Succ) {
177
2.34M
        DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
178
2.34M
179
2.34M
        const unsigned SuccLevel = SuccNode->getLevel();
180
2.34M
        if (SuccLevel > RootLevel)
181
2.34M
          return;
182
2.34M
183
2.34M
        if (!VisitedPQ.insert(SuccNode).second)
184
2.34M
          return;
185
2.34M
186
2.34M
        NodeTy *SuccBB = SuccNode->getBlock();
187
2.34M
        if (useLiveIn && !LiveInBlocks->count(SuccBB))
188
2.34M
          return;
189
2.34M
190
2.34M
        PHIBlocks.emplace_back(SuccBB);
191
2.34M
        if (!DefBlocks->count(SuccBB))
192
2.34M
          PQ.push(std::make_pair(
193
2.34M
              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
194
2.34M
      };
195
2.34M
196
2.34M
      for (auto Succ : ChildrenGetter.get(BB))
197
3.39M
        DoWork(Succ);
198
2.34M
199
2.34M
      for (auto DomChild : *Node) {
200
2.10M
        if (VisitedWorklist.insert(DomChild).second)
201
30.4k
          Worklist.push_back(DomChild);
202
2.10M
      }
203
2.34M
    }
204
2.31M
  }
205
160k
}
llvm::IDFCalculatorBase<clang::CFGBlock, true>::calculate(llvm::SmallVectorImpl<clang::CFGBlock*>&)
Line
Count
Source
132
154
    SmallVectorImpl<NodeTy *> &PHIBlocks) {
133
154
  // Use a priority queue keyed on dominator tree level so that inserted nodes
134
154
  // are handled from the bottom of the dominator tree upwards. We also augment
135
154
  // the level with a DFS number to ensure that the blocks are ordered in a
136
154
  // deterministic way.
137
154
  using DomTreeNodePair =
138
154
      std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
139
154
  using IDFPriorityQueue =
140
154
      std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
141
154
                          less_second>;
142
154
143
154
  IDFPriorityQueue PQ;
144
154
145
154
  DT.updateDFSNumbers();
146
154
147
154
  for (NodeTy *BB : *DefBlocks) {
148
154
    if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB))
149
154
      PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
150
154
  }
151
154
152
154
  SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
153
154
  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
154
154
  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
155
154
156
405
  while (!PQ.empty()) {
157
251
    DomTreeNodePair RootPair = PQ.top();
158
251
    PQ.pop();
159
251
    DomTreeNodeBase<NodeTy> *Root = RootPair.first;
160
251
    unsigned RootLevel = RootPair.second.first;
161
251
162
251
    // Walk all dominator tree children of Root, inspecting their CFG edges with
163
251
    // targets elsewhere on the dominator tree. Only targets whose level is at
164
251
    // most Root's level are added to the iterated dominance frontier of the
165
251
    // definition set.
166
251
167
251
    Worklist.clear();
168
251
    Worklist.push_back(Root);
169
251
    VisitedWorklist.insert(Root);
170
251
171
897
    while (!Worklist.empty()) {
172
646
      DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val();
173
646
      NodeTy *BB = Node->getBlock();
174
646
      // Succ is the successor in the direction we are calculating IDF, so it is
175
646
      // successor for IDF, and predecessor for Reverse IDF.
176
646
      auto DoWork = [&](NodeTy *Succ) {
177
646
        DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
178
646
179
646
        const unsigned SuccLevel = SuccNode->getLevel();
180
646
        if (SuccLevel > RootLevel)
181
646
          return;
182
646
183
646
        if (!VisitedPQ.insert(SuccNode).second)
184
646
          return;
185
646
186
646
        NodeTy *SuccBB = SuccNode->getBlock();
187
646
        if (useLiveIn && !LiveInBlocks->count(SuccBB))
188
646
          return;
189
646
190
646
        PHIBlocks.emplace_back(SuccBB);
191
646
        if (!DefBlocks->count(SuccBB))
192
646
          PQ.push(std::make_pair(
193
646
              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
194
646
      };
195
646
196
646
      for (auto Succ : ChildrenGetter.get(BB))
197
608
        DoWork(Succ);
198
646
199
646
      for (auto DomChild : *Node) {
200
429
        if (VisitedWorklist.insert(DomChild).second)
201
395
          Worklist.push_back(DomChild);
202
429
      }
203
646
    }
204
251
  }
205
154
}
206
207
} // end of namespace llvm
208
209
#endif