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> *, 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()) { 172 DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val(); 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 210