LLVM  14.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 
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallVector.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 {
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  std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>;
61  using ChildrenGetterTy =
63 
65 
67  const ChildrenGetterTy &C)
68  : 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.
76  DefBlocks = &Blocks;
77  }
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.
85  LiveInBlocks = &Blocks;
86  useLiveIn = true;
87  }
88 
89  /// Reset the live-in block set to be empty, and tell the IDF
90  /// calculator to not use liveness anymore.
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:
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>
121  using 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>
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>,
141  less_second>;
142 
143  IDFPriorityQueue PQ;
144 
145  DT.updateDFSNumbers();
146 
147  SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
148  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
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
llvm::less_second
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:1286
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::IDFCalculatorBase::setLiveInBlocks
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.
Definition: GenericIteratedDominanceFrontier.h:84
llvm::IDFCalculatorDetail::ChildrenGetterTy::get
ChildrenTy get(const NodeRef &N)
Definition: GenericIteratedDominanceFrontier.h:120
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
DenseMap.h
llvm::IDFCalculatorDetail::ChildrenGetterTy::NodeRef
typename GraphTraits< NodeTy >::NodeRef NodeRef
Definition: GenericIteratedDominanceFrontier.h:40
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::IDFCalculatorBase::calculate
void calculate(SmallVectorImpl< NodeTy * > &IDFBlocks)
Calculate iterated dominance frontiers.
Definition: GenericIteratedDominanceFrontier.h:131
llvm::IDFCalculatorBase::IDFCalculatorBase
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT)
Definition: GenericIteratedDominanceFrontier.h:64
llvm::DomTreeNodeBase::getDFSNumIn
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
Definition: GenericDomTree.h:143
llvm::IDFCalculatorBase::OrderedNodeTy
std::conditional_t< IsPostDom, Inverse< NodeTy * >, NodeTy * > OrderedNodeTy
Definition: GenericIteratedDominanceFrontier.h:60
llvm::IDFCalculatorBase::resetLiveInBlocks
void resetLiveInBlocks()
Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore.
Definition: GenericIteratedDominanceFrontier.h:91
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
SmallPtrSet.h
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::IDFCalculatorBase::setDefiningBlocks
void setDefiningBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
Definition: GenericIteratedDominanceFrontier.h:75
llvm::IDFCalculatorDetail::ChildrenGetterTy::ChildrenTy
SmallVector< NodeRef, 8 > ChildrenTy
Definition: GenericIteratedDominanceFrontier.h:41
llvm::DominatorTreeBase< NodeTy, IsPostDom >
Node
Definition: ItaniumDemangle.h:235
llvm::DomTreeNodeBase< NodeTy >
llvm::IDFCalculatorBase::IDFCalculatorBase
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT, const ChildrenGetterTy &C)
Definition: GenericIteratedDominanceFrontier.h:66
llvm::DomTreeNodeBase::getLevel
unsigned getLevel() const
Definition: GenericDomTree.h:90
GenericDomTree.h
llvm::IDFCalculatorDetail::ChildrenGetterTy
Generic utility class used for getting the children of a basic block.
Definition: GenericIteratedDominanceFrontier.h:39
llvm::IDFCalculatorBase
Determine the iterated dominance frontier, given a set of defining blocks, and optionally,...
Definition: GenericIteratedDominanceFrontier.h:57
llvm::IDFCalculatorBase::ChildrenGetterTy
IDFCalculatorDetail::ChildrenGetterTy< NodeTy, IsPostDom > ChildrenGetterTy
Definition: GenericIteratedDominanceFrontier.h:62
SmallVector.h
N
#define N
llvm::IDFCalculatorDetail::ChildrenGetterTy< BasicBlock, IsPostDom >
Specialization for BasicBlock for the optional use of GraphDiff.
Definition: IteratedDominanceFrontier.h:22
llvm::SmallVectorImpl< NodeTy * >
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::GraphTraits::NodeRef
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:78
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::SmallPtrSetImpl::insert
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:364