LLVM  10.0.0svn
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_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"
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  typename std::conditional<IsPostDom, Inverse<NodeTy *>, NodeTy *>::type;
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 *> &PHIBlocks) {
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  for (NodeTy *BB : *DefBlocks) {
148  if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB))
149  PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
150  }
151 
152  SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
153  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
154  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
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  Worklist.clear();
168  Worklist.push_back(Root);
169  VisitedWorklist.insert(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  PHIBlocks.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
uint64_t CallInst * C
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:969
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
void calculate(SmallVectorImpl< NodeTy *> &IDFBlocks)
Calculate iterated dominance frontiers.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
typename std::conditional< IsPostDom, Inverse< NodeTy * >, NodeTy * >::type OrderedNodeTy
void resetLiveInBlocks()
Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore...
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT, const ChildrenGetterTy &C)
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree...
NodeT * getBlock() const
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:78
Generic utility class used for getting the children of a basic block.
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...
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT)
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:370
void setDefiningBlocks(const SmallPtrSetImpl< NodeTy *> &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define N
unsigned getLevel() const
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
Specialization for BasicBlock for the optional use of GraphDiff.