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" 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 ChildrenTy = SmallVector<NodeRef, 8>; 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 = 62 IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>; 63 64 IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {} 65 66 IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT, 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. 75 void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { 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. 84 void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { 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. 91 void resetLiveInBlocks() { 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: 105 DominatorTreeBase<NodeTy, IsPostDom> &DT; 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> 119 typename ChildrenGetterTy<NodeTy, IsPostDom>::ChildrenTy 120 ChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) { 121 using OrderedNodeTy = 122 typename IDFCalculatorBase<NodeTy, IsPostDom>::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> 131 void IDFCalculatorBase<NodeTy, IsPostDom>::calculate( 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()) { 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 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 210