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/ADT/iterator_range.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 ChildIteratorType = typename GraphTraits<NodeTy *>::ChildIteratorType; 42 using range = iterator_range<ChildIteratorType>; 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. 58 template <class NodeTy, bool IsPostDom> class IDFCalculatorBase { 59 public: 60 using OrderedNodeTy = 61 std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>; 62 using ChildrenGetterTy = 63 IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>; 64 65 IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {} 66 67 IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT, 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. 76 void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { 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. 85 void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { 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. 92 void resetLiveInBlocks() { 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. 103 void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks); 104 105 private: 106 DominatorTreeBase<NodeTy, IsPostDom> &DT; 107 ChildrenGetterTy ChildrenGetter; 108 bool useLiveIn = false; 109 const SmallPtrSetImpl<NodeTy *> *LiveInBlocks; 110 const SmallPtrSetImpl<NodeTy *> *DefBlocks; 111 }; 112 113 //===----------------------------------------------------------------------===// 114 // Implementation. 115 //===----------------------------------------------------------------------===// 116 117 namespace IDFCalculatorDetail { 118 119 template <class NodeTy, bool IsPostDom> 120 typename ChildrenGetterTy<NodeTy, IsPostDom>::range 121 ChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) { 122 using OrderedNodeTy = 123 typename IDFCalculatorBase<NodeTy, IsPostDom>::OrderedNodeTy; 124 125 return children<OrderedNodeTy>(N); 126 } 127 128 } // end of namespace IDFCalculatorDetail 129 130 template <class NodeTy, bool IsPostDom> 131 void IDFCalculatorBase<NodeTy, IsPostDom>::calculate( 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> *, 16> VisitedPQ; 149 SmallPtrSet<DomTreeNodeBase<NodeTy> *, 16> VisitedWorklist; 150 if (useLiveIn) { 151 VisitedPQ.reserve(LiveInBlocks->size()); 152 VisitedWorklist.reserve(LiveInBlocks->size()); 153 } 154 155 for (NodeTy *BB : *DefBlocks) 156 if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB)) { 157 PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())}); 158 VisitedWorklist.insert(Node); 159 } 160 161 while (!PQ.empty()) { 162 DomTreeNodePair RootPair = PQ.top(); 163 PQ.pop(); 164 DomTreeNodeBase<NodeTy> *Root = RootPair.first; 165 unsigned RootLevel = RootPair.second.first; 166 167 // Walk all dominator tree children of Root, inspecting their CFG edges with 168 // targets elsewhere on the dominator tree. Only targets whose level is at 169 // most Root's level are added to the iterated dominance frontier of the 170 // definition set. 171 172 assert(Worklist.empty()); 173 Worklist.push_back(Root); 174 175 while (!Worklist.empty()) { 176 DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val(); 177 NodeTy *BB = Node->getBlock(); 178 // Succ is the successor in the direction we are calculating IDF, so it is 179 // successor for IDF, and predecessor for Reverse IDF. 180 auto DoWork = [&](NodeTy *Succ) { 181 DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ); 182 183 const unsigned SuccLevel = SuccNode->getLevel(); 184 if (SuccLevel > RootLevel) 185 return; 186 187 if (!VisitedPQ.insert(SuccNode).second) 188 return; 189 190 NodeTy *SuccBB = SuccNode->getBlock(); 191 if (useLiveIn && !LiveInBlocks->count(SuccBB)) 192 return; 193 194 IDFBlocks.emplace_back(SuccBB); 195 if (!DefBlocks->count(SuccBB)) 196 PQ.push(std::make_pair( 197 SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn()))); 198 }; 199 200 for (auto *Succ : ChildrenGetter.get(BB)) 201 DoWork(Succ); 202 203 for (auto DomChild : *Node) { 204 if (VisitedWorklist.insert(DomChild).second) 205 Worklist.push_back(DomChild); 206 } 207 } 208 } 209 } 210 211 } // end of namespace llvm 212 213 #endif 214