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_GENERICITERATEDDOMINANCEFRONTIER_H |
24 | #define LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H |
25 | |
26 | #include "llvm/ADT/SmallPtrSet.h" |
27 | #include "llvm/ADT/SmallVector.h" |
28 | #include "llvm/Support/GenericDomTree.h" |
29 | #include <queue> |
30 | |
31 | namespace llvm { |
32 | |
33 | namespace IDFCalculatorDetail { |
34 | |
35 | /// Generic utility class used for getting the children of a basic block. |
36 | /// May be specialized if, for example, one wouldn't like to return nullpointer |
37 | /// successors. |
38 | template <class NodeTy, bool IsPostDom> struct ChildrenGetterTy { |
39 | using NodeRef = typename GraphTraits<NodeTy *>::NodeRef; |
40 | using ChildrenTy = SmallVector<NodeRef, 8>; |
41 | |
42 | ChildrenTy get(const NodeRef &N); |
43 | }; |
44 | |
45 | } // end of namespace IDFCalculatorDetail |
46 | |
47 | /// Determine the iterated dominance frontier, given a set of defining |
48 | /// blocks, and optionally, a set of live-in blocks. |
49 | /// |
50 | /// In turn, the results can be used to place phi nodes. |
51 | /// |
52 | /// This algorithm is a linear time computation of Iterated Dominance Frontiers, |
53 | /// pruned using the live-in set. |
54 | /// By default, liveness is not used to prune the IDF computation. |
55 | /// The template parameters should be of a CFG block type. |
56 | template <class NodeTy, bool IsPostDom> class IDFCalculatorBase { |
57 | public: |
58 | using OrderedNodeTy = |
59 | std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>; |
60 | using ChildrenGetterTy = |
61 | IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>; |
62 | |
63 | IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {} |
64 | |
65 | IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT, |
66 | const ChildrenGetterTy &C) |
67 | : DT(DT), ChildrenGetter(C) {} |
68 | |
69 | /// Give the IDF calculator the set of blocks in which the value is |
70 | /// defined. This is equivalent to the set of starting blocks it should be |
71 | /// calculating the IDF for (though later gets pruned based on liveness). |
72 | /// |
73 | /// Note: This set *must* live for the entire lifetime of the IDF calculator. |
74 | void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { |
75 | DefBlocks = &Blocks; |
76 | } |
77 | |
78 | /// Give the IDF calculator the set of blocks in which the value is |
79 | /// live on entry to the block. This is used to prune the IDF calculation to |
80 | /// not include blocks where any phi insertion would be dead. |
81 | /// |
82 | /// Note: This set *must* live for the entire lifetime of the IDF calculator. |
83 | void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { |
84 | LiveInBlocks = &Blocks; |
85 | useLiveIn = true; |
86 | } |
87 | |
88 | /// Reset the live-in block set to be empty, and tell the IDF |
89 | /// calculator to not use liveness anymore. |
90 | void resetLiveInBlocks() { |
91 | LiveInBlocks = nullptr; |
92 | useLiveIn = false; |
93 | } |
94 | |
95 | /// Calculate iterated dominance frontiers |
96 | /// |
97 | /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in |
98 | /// the file-level comment. It performs DF->IDF pruning using the live-in |
99 | /// set, to avoid computing the IDF for blocks where an inserted PHI node |
100 | /// would be dead. |
101 | void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks); |
102 | |
103 | private: |
104 | DominatorTreeBase<NodeTy, IsPostDom> &DT; |
105 | ChildrenGetterTy ChildrenGetter; |
106 | bool useLiveIn = false; |
107 | const SmallPtrSetImpl<NodeTy *> *LiveInBlocks; |
108 | const SmallPtrSetImpl<NodeTy *> *DefBlocks; |
109 | }; |
110 | |
111 | //===----------------------------------------------------------------------===// |
112 | // Implementation. |
113 | //===----------------------------------------------------------------------===// |
114 | |
115 | namespace IDFCalculatorDetail { |
116 | |
117 | template <class NodeTy, bool IsPostDom> |
118 | typename ChildrenGetterTy<NodeTy, IsPostDom>::ChildrenTy |
119 | ChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) { |
120 | using OrderedNodeTy = |
121 | typename IDFCalculatorBase<NodeTy, IsPostDom>::OrderedNodeTy; |
122 | |
123 | auto Children = children<OrderedNodeTy>(N); |
124 | return {Children.begin(), Children.end()}; |
125 | } |
126 | |
127 | } // end of namespace IDFCalculatorDetail |
128 | |
129 | template <class NodeTy, bool IsPostDom> |
130 | void IDFCalculatorBase<NodeTy, IsPostDom>::calculate( |
131 | SmallVectorImpl<NodeTy *> &IDFBlocks) { |
132 | // Use a priority queue keyed on dominator tree level so that inserted nodes |
133 | // are handled from the bottom of the dominator tree upwards. We also augment |
134 | // the level with a DFS number to ensure that the blocks are ordered in a |
135 | // deterministic way. |
136 | using DomTreeNodePair = |
137 | std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>; |
138 | using IDFPriorityQueue = |
139 | std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>, |
140 | less_second>; |
141 | |
142 | IDFPriorityQueue PQ; |
143 | |
144 | DT.updateDFSNumbers(); |
145 | |
146 | SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist; |
147 | SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ; |
148 | SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist; |
149 | |
150 | for (NodeTy *BB : *DefBlocks) |
151 | if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB)) { |
152 | PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())}); |
153 | VisitedWorklist.insert(Node); |
154 | } |
155 | |
156 | while (!PQ.empty()) { |
157 | DomTreeNodePair RootPair = PQ.top(); |
158 | PQ.pop(); |
159 | DomTreeNodeBase<NodeTy> *Root = RootPair.first; |
160 | unsigned RootLevel = RootPair.second.first; |
161 | |
162 | // Walk all dominator tree children of Root, inspecting their CFG edges with |
163 | // targets elsewhere on the dominator tree. Only targets whose level is at |
164 | // most Root's level are added to the iterated dominance frontier of the |
165 | // definition set. |
166 | |
167 | assert(Worklist.empty()); |
168 | Worklist.push_back(Root); |
169 | |
170 | while (!Worklist.empty()) { |
171 | DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val(); |
172 | NodeTy *BB = Node->getBlock(); |
173 | // Succ is the successor in the direction we are calculating IDF, so it is |
174 | // successor for IDF, and predecessor for Reverse IDF. |
175 | auto DoWork = [&](NodeTy *Succ) { |
176 | DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ); |
177 | |
178 | const unsigned SuccLevel = SuccNode->getLevel(); |
179 | if (SuccLevel > RootLevel) |
180 | return; |
181 | |
182 | if (!VisitedPQ.insert(SuccNode).second) |
183 | return; |
184 | |
185 | NodeTy *SuccBB = SuccNode->getBlock(); |
186 | if (useLiveIn && !LiveInBlocks->count(SuccBB)) |
187 | return; |
188 | |
189 | IDFBlocks.emplace_back(SuccBB); |
190 | if (!DefBlocks->count(SuccBB)) |
191 | PQ.push(std::make_pair( |
192 | SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn()))); |
193 | }; |
194 | |
195 | for (auto *Succ : ChildrenGetter.get(BB)) |
196 | DoWork(Succ); |
197 | |
198 | for (auto DomChild : *Node) { |
199 | if (VisitedWorklist.insert(DomChild).second) |
200 | Worklist.push_back(DomChild); |
201 | } |
202 | } |
203 | } |
204 | } |
205 | |
206 | } // end of namespace llvm |
207 | |
208 | #endif |
209 | |