LLVM 19.0.0git
GenericIteratedDominanceFrontier.h
Go to the documentation of this file.
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
30#include <queue>
31
32namespace llvm {
33
34namespace 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.
39template <class NodeTy, bool IsPostDom> struct ChildrenGetterTy {
43
44 range get(const NodeRef &N);
45};
46
47} // end of namespace IDFCalculatorDetail
48
49/// Determine the iterated dominance frontier, given a set of defining
50/// blocks, and optionally, a set of live-in blocks.
51///
52/// In turn, the results can be used to place phi nodes.
53///
54/// This algorithm is a linear time computation of Iterated Dominance Frontiers,
55/// pruned using the live-in set.
56/// By default, liveness is not used to prune the IDF computation.
57/// The template parameters should be of a CFG block type.
58template <class NodeTy, bool IsPostDom> class IDFCalculatorBase {
59public:
61 std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>;
64
66
68 const ChildrenGetterTy &C)
69 : DT(DT), ChildrenGetter(C) {}
70
71 /// Give the IDF calculator the set of blocks in which the value is
72 /// defined. This is equivalent to the set of starting blocks it should be
73 /// calculating the IDF for (though later gets pruned based on liveness).
74 ///
75 /// Note: This set *must* live for the entire lifetime of the IDF calculator.
77 DefBlocks = &Blocks;
78 }
79
80 /// Give the IDF calculator the set of blocks in which the value is
81 /// live on entry to the block. This is used to prune the IDF calculation to
82 /// not include blocks where any phi insertion would be dead.
83 ///
84 /// Note: This set *must* live for the entire lifetime of the IDF calculator.
86 LiveInBlocks = &Blocks;
87 useLiveIn = true;
88 }
89
90 /// Reset the live-in block set to be empty, and tell the IDF
91 /// calculator to not use liveness anymore.
93 LiveInBlocks = nullptr;
94 useLiveIn = false;
95 }
96
97 /// Calculate iterated dominance frontiers
98 ///
99 /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
100 /// the file-level comment. It performs DF->IDF pruning using the live-in
101 /// set, to avoid computing the IDF for blocks where an inserted PHI node
102 /// would be dead.
104
105private:
107 ChildrenGetterTy ChildrenGetter;
108 bool useLiveIn = false;
109 const SmallPtrSetImpl<NodeTy *> *LiveInBlocks;
110 const SmallPtrSetImpl<NodeTy *> *DefBlocks;
111};
112
113//===----------------------------------------------------------------------===//
114// Implementation.
115//===----------------------------------------------------------------------===//
116
117namespace IDFCalculatorDetail {
118
119template <class NodeTy, bool IsPostDom>
122 using OrderedNodeTy =
124
125 return children<OrderedNodeTy>(N);
126}
127
128} // end of namespace IDFCalculatorDetail
129
130template <class NodeTy, bool IsPostDom>
132 SmallVectorImpl<NodeTy *> &IDFBlocks) {
133 // Use a priority queue keyed on dominator tree level so that inserted nodes
134 // are handled from the bottom of the dominator tree upwards. We also augment
135 // the level with a DFS number to ensure that the blocks are ordered in a
136 // deterministic way.
137 using DomTreeNodePair =
138 std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
139 using IDFPriorityQueue =
140 std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
142
143 IDFPriorityQueue PQ;
144
145 DT.updateDFSNumbers();
146
149 SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
150
151 for (NodeTy *BB : *DefBlocks)
152 if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB)) {
153 PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
154 VisitedWorklist.insert(Node);
155 }
156
157 while (!PQ.empty()) {
158 DomTreeNodePair RootPair = PQ.top();
159 PQ.pop();
160 DomTreeNodeBase<NodeTy> *Root = RootPair.first;
161 unsigned RootLevel = RootPair.second.first;
162
163 // Walk all dominator tree children of Root, inspecting their CFG edges with
164 // targets elsewhere on the dominator tree. Only targets whose level is at
165 // most Root's level are added to the iterated dominance frontier of the
166 // definition set.
167
168 assert(Worklist.empty());
169 Worklist.push_back(Root);
170
171 while (!Worklist.empty()) {
173 NodeTy *BB = Node->getBlock();
174 // Succ is the successor in the direction we are calculating IDF, so it is
175 // successor for IDF, and predecessor for Reverse IDF.
176 auto DoWork = [&](NodeTy *Succ) {
177 DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
178
179 const unsigned SuccLevel = SuccNode->getLevel();
180 if (SuccLevel > RootLevel)
181 return;
182
183 if (!VisitedPQ.insert(SuccNode).second)
184 return;
185
186 NodeTy *SuccBB = SuccNode->getBlock();
187 if (useLiveIn && !LiveInBlocks->count(SuccBB))
188 return;
189
190 IDFBlocks.emplace_back(SuccBB);
191 if (!DefBlocks->count(SuccBB))
192 PQ.push(std::make_pair(
193 SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
194 };
195
196 for (auto *Succ : ChildrenGetter.get(BB))
197 DoWork(Succ);
198
199 for (auto DomChild : *Node) {
200 if (VisitedWorklist.insert(DomChild).second)
201 Worklist.push_back(DomChild);
202 }
203 }
204 }
205}
206
207} // end of namespace llvm
208
209#endif
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Base class for the actual dominator tree node.
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
NodeT * getBlock() const
unsigned getLevel() const
Core dominator tree base class.
Determine the iterated dominance frontier, given a set of defining blocks, and optionally,...
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT)
void resetLiveInBlocks()
Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore.
void calculate(SmallVectorImpl< NodeTy * > &IDFBlocks)
Calculate iterated dominance frontiers.
void setLiveInBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is live on entry to the block.
void setDefiningBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT, const ChildrenGetterTy &C)
std::conditional_t< IsPostDom, Inverse< NodeTy * >, NodeTy * > OrderedNodeTy
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:323
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:344
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:479
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
A range adaptor for a pair of iterators.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
#define N
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:80
Specialization for BasicBlock for the optional use of GraphDiff.
Generic utility class used for getting the children of a basic block.
typename GraphTraits< NodeTy * >::ChildIteratorType ChildIteratorType
typename GraphTraits< NodeTy * >::NodeRef NodeRef
Function object to check whether the second component of a container supported by std::get (like std:...
Definition: STLExtras.h:1459