1351278Sdim//===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===// 2351278Sdim// 3351278Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351278Sdim// See https://llvm.org/LICENSE.txt for license information. 5351278Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351278Sdim// 7351278Sdim//===----------------------------------------------------------------------===// 8351278Sdim/// \file 9351278Sdim/// Compute iterated dominance frontiers using a linear time algorithm. 10351278Sdim/// 11351278Sdim/// The algorithm used here is based on: 12351278Sdim/// 13351278Sdim/// Sreedhar and Gao. A linear time algorithm for placing phi-nodes. 14351278Sdim/// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of 15351278Sdim/// Programming Languages 16351278Sdim/// POPL '95. ACM, New York, NY, 62-73. 17351278Sdim/// 18351278Sdim/// It has been modified to not explicitly use the DJ graph data structure and 19351278Sdim/// to directly compute pruned SSA using per-variable liveness information. 20351278Sdim// 21351278Sdim//===----------------------------------------------------------------------===// 22351278Sdim 23351278Sdim#ifndef LLVM_SUPPORT_GENERIC_IDF_H 24351278Sdim#define LLVM_SUPPORT_GENERIC_IDF_H 25351278Sdim 26351278Sdim#include "llvm/ADT/DenseMap.h" 27351278Sdim#include "llvm/ADT/SmallPtrSet.h" 28351278Sdim#include "llvm/ADT/SmallVector.h" 29351278Sdim#include "llvm/Support/GenericDomTree.h" 30351278Sdim#include <queue> 31351278Sdim 32351278Sdimnamespace llvm { 33351278Sdim 34351278Sdimnamespace IDFCalculatorDetail { 35351278Sdim 36351278Sdim/// Generic utility class used for getting the children of a basic block. 37351278Sdim/// May be specialized if, for example, one wouldn't like to return nullpointer 38351278Sdim/// successors. 39351278Sdimtemplate <class NodeTy, bool IsPostDom> struct ChildrenGetterTy { 40351278Sdim using NodeRef = typename GraphTraits<NodeTy>::NodeRef; 41351278Sdim using ChildrenTy = SmallVector<NodeRef, 8>; 42351278Sdim 43351278Sdim ChildrenTy get(const NodeRef &N); 44351278Sdim}; 45351278Sdim 46351278Sdim} // end of namespace IDFCalculatorDetail 47351278Sdim 48351278Sdim/// Determine the iterated dominance frontier, given a set of defining 49351278Sdim/// blocks, and optionally, a set of live-in blocks. 50351278Sdim/// 51351278Sdim/// In turn, the results can be used to place phi nodes. 52351278Sdim/// 53351278Sdim/// This algorithm is a linear time computation of Iterated Dominance Frontiers, 54351278Sdim/// pruned using the live-in set. 55351278Sdim/// By default, liveness is not used to prune the IDF computation. 56351278Sdim/// The template parameters should be of a CFG block type. 57351278Sdimtemplate <class NodeTy, bool IsPostDom> class IDFCalculatorBase { 58351278Sdimpublic: 59351278Sdim using OrderedNodeTy = 60351278Sdim typename std::conditional<IsPostDom, Inverse<NodeTy *>, NodeTy *>::type; 61351278Sdim using ChildrenGetterTy = 62351278Sdim IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>; 63351278Sdim 64351278Sdim IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {} 65351278Sdim 66351278Sdim IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT, 67351278Sdim const ChildrenGetterTy &C) 68351278Sdim : DT(DT), ChildrenGetter(C) {} 69351278Sdim 70351278Sdim /// Give the IDF calculator the set of blocks in which the value is 71351278Sdim /// defined. This is equivalent to the set of starting blocks it should be 72351278Sdim /// calculating the IDF for (though later gets pruned based on liveness). 73351278Sdim /// 74351278Sdim /// Note: This set *must* live for the entire lifetime of the IDF calculator. 75351278Sdim void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { 76351278Sdim DefBlocks = &Blocks; 77351278Sdim } 78351278Sdim 79351278Sdim /// Give the IDF calculator the set of blocks in which the value is 80351278Sdim /// live on entry to the block. This is used to prune the IDF calculation to 81351278Sdim /// not include blocks where any phi insertion would be dead. 82351278Sdim /// 83351278Sdim /// Note: This set *must* live for the entire lifetime of the IDF calculator. 84351278Sdim void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { 85351278Sdim LiveInBlocks = &Blocks; 86351278Sdim useLiveIn = true; 87351278Sdim } 88351278Sdim 89351278Sdim /// Reset the live-in block set to be empty, and tell the IDF 90351278Sdim /// calculator to not use liveness anymore. 91351278Sdim void resetLiveInBlocks() { 92351278Sdim LiveInBlocks = nullptr; 93351278Sdim useLiveIn = false; 94351278Sdim } 95351278Sdim 96351278Sdim /// Calculate iterated dominance frontiers 97351278Sdim /// 98351278Sdim /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in 99351278Sdim /// the file-level comment. It performs DF->IDF pruning using the live-in 100351278Sdim /// set, to avoid computing the IDF for blocks where an inserted PHI node 101351278Sdim /// would be dead. 102351278Sdim void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks); 103351278Sdim 104351278Sdimprivate: 105351278Sdim DominatorTreeBase<NodeTy, IsPostDom> &DT; 106351278Sdim ChildrenGetterTy ChildrenGetter; 107351278Sdim bool useLiveIn = false; 108351278Sdim const SmallPtrSetImpl<NodeTy *> *LiveInBlocks; 109351278Sdim const SmallPtrSetImpl<NodeTy *> *DefBlocks; 110351278Sdim}; 111351278Sdim 112351278Sdim//===----------------------------------------------------------------------===// 113351278Sdim// Implementation. 114351278Sdim//===----------------------------------------------------------------------===// 115351278Sdim 116351278Sdimnamespace IDFCalculatorDetail { 117351278Sdim 118351278Sdimtemplate <class NodeTy, bool IsPostDom> 119351278Sdimtypename ChildrenGetterTy<NodeTy, IsPostDom>::ChildrenTy 120351278SdimChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) { 121351278Sdim using OrderedNodeTy = 122351278Sdim typename IDFCalculatorBase<NodeTy, IsPostDom>::OrderedNodeTy; 123351278Sdim 124351278Sdim auto Children = children<OrderedNodeTy>(N); 125351278Sdim return {Children.begin(), Children.end()}; 126351278Sdim} 127351278Sdim 128351278Sdim} // end of namespace IDFCalculatorDetail 129351278Sdim 130351278Sdimtemplate <class NodeTy, bool IsPostDom> 131351278Sdimvoid IDFCalculatorBase<NodeTy, IsPostDom>::calculate( 132351278Sdim SmallVectorImpl<NodeTy *> &PHIBlocks) { 133351278Sdim // Use a priority queue keyed on dominator tree level so that inserted nodes 134351278Sdim // are handled from the bottom of the dominator tree upwards. We also augment 135351278Sdim // the level with a DFS number to ensure that the blocks are ordered in a 136351278Sdim // deterministic way. 137351278Sdim using DomTreeNodePair = 138351278Sdim std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>; 139351278Sdim using IDFPriorityQueue = 140351278Sdim std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>, 141351278Sdim less_second>; 142351278Sdim 143351278Sdim IDFPriorityQueue PQ; 144351278Sdim 145351278Sdim DT.updateDFSNumbers(); 146351278Sdim 147351278Sdim for (NodeTy *BB : *DefBlocks) { 148351278Sdim if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB)) 149351278Sdim PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())}); 150351278Sdim } 151351278Sdim 152351278Sdim SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist; 153351278Sdim SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ; 154351278Sdim SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist; 155351278Sdim 156351278Sdim while (!PQ.empty()) { 157351278Sdim DomTreeNodePair RootPair = PQ.top(); 158351278Sdim PQ.pop(); 159351278Sdim DomTreeNodeBase<NodeTy> *Root = RootPair.first; 160351278Sdim unsigned RootLevel = RootPair.second.first; 161351278Sdim 162351278Sdim // Walk all dominator tree children of Root, inspecting their CFG edges with 163351278Sdim // targets elsewhere on the dominator tree. Only targets whose level is at 164351278Sdim // most Root's level are added to the iterated dominance frontier of the 165351278Sdim // definition set. 166351278Sdim 167351278Sdim Worklist.clear(); 168351278Sdim Worklist.push_back(Root); 169351278Sdim VisitedWorklist.insert(Root); 170351278Sdim 171351278Sdim while (!Worklist.empty()) { 172351278Sdim DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val(); 173351278Sdim NodeTy *BB = Node->getBlock(); 174351278Sdim // Succ is the successor in the direction we are calculating IDF, so it is 175351278Sdim // successor for IDF, and predecessor for Reverse IDF. 176351278Sdim auto DoWork = [&](NodeTy *Succ) { 177351278Sdim DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ); 178351278Sdim 179351278Sdim const unsigned SuccLevel = SuccNode->getLevel(); 180351278Sdim if (SuccLevel > RootLevel) 181351278Sdim return; 182351278Sdim 183351278Sdim if (!VisitedPQ.insert(SuccNode).second) 184351278Sdim return; 185351278Sdim 186351278Sdim NodeTy *SuccBB = SuccNode->getBlock(); 187351278Sdim if (useLiveIn && !LiveInBlocks->count(SuccBB)) 188351278Sdim return; 189351278Sdim 190351278Sdim PHIBlocks.emplace_back(SuccBB); 191351278Sdim if (!DefBlocks->count(SuccBB)) 192351278Sdim PQ.push(std::make_pair( 193351278Sdim SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn()))); 194351278Sdim }; 195351278Sdim 196351278Sdim for (auto Succ : ChildrenGetter.get(BB)) 197351278Sdim DoWork(Succ); 198351278Sdim 199351278Sdim for (auto DomChild : *Node) { 200351278Sdim if (VisitedWorklist.insert(DomChild).second) 201351278Sdim Worklist.push_back(DomChild); 202351278Sdim } 203351278Sdim } 204351278Sdim } 205351278Sdim} 206351278Sdim 207351278Sdim} // end of namespace llvm 208351278Sdim 209351278Sdim#endif 210