1 //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 /// \brief Compute iterated dominance frontiers using a linear time algorithm. 11 /// 12 /// The algorithm used here is based on: 13 /// 14 /// Sreedhar and Gao. A linear time algorithm for placing phi-nodes. 15 /// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of 16 /// Programming Languages 17 /// POPL '95. ACM, New York, NY, 62-73. 18 /// 19 /// It has been modified to not explicitly use the DJ graph data structure and 20 /// to directly compute pruned SSA using per-variable liveness information. 21 // 22 //===----------------------------------------------------------------------===// 23 24 #ifndef LLVM_ANALYSIS_IDF_H 25 #define LLVM_ANALYSIS_IDF_H 26 27 #include "llvm/ADT/ArrayRef.h" 28 #include "llvm/ADT/DenseMap.h" 29 #include "llvm/ADT/SmallPtrSet.h" 30 #include "llvm/ADT/SmallVector.h" 31 32 namespace llvm { 33 34 class BasicBlock; 35 template <class T> class DomTreeNodeBase; 36 typedef DomTreeNodeBase<BasicBlock> DomTreeNode; 37 template <class T> class DominatorTreeBase; 38 39 /// \brief Determine the iterated dominance frontier, given a set of defining 40 /// blocks, and optionally, a set of live-in blocks. 41 /// 42 /// In turn, the results can be used to place phi nodes. 43 /// 44 /// This algorithm is a linear time computation of Iterated Dominance Frontiers, 45 /// pruned using the live-in set. 46 /// By default, liveness is not used to prune the IDF computation. 47 class IDFCalculator { 48 49 public: IDFCalculator(DominatorTreeBase<BasicBlock> & DT)50 IDFCalculator(DominatorTreeBase<BasicBlock> &DT) : DT(DT), useLiveIn(false) {} 51 52 /// \brief Give the IDF calculator the set of blocks in which the value is 53 /// defined. This is equivalent to the set of starting blocks it should be 54 /// calculating the IDF for (though later gets pruned based on liveness). 55 /// 56 /// Note: This set *must* live for the entire lifetime of the IDF calculator. setDefiningBlocks(const SmallPtrSetImpl<BasicBlock * > & Blocks)57 void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { 58 DefBlocks = &Blocks; 59 } 60 61 /// \brief Give the IDF calculator the set of blocks in which the value is 62 /// live on entry to the block. This is used to prune the IDF calculation to 63 /// not include blocks where any phi insertion would be dead. 64 /// 65 /// Note: This set *must* live for the entire lifetime of the IDF calculator. 66 setLiveInBlocks(const SmallPtrSetImpl<BasicBlock * > & Blocks)67 void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { 68 LiveInBlocks = &Blocks; 69 useLiveIn = true; 70 } 71 72 /// \brief Reset the live-in block set to be empty, and tell the IDF 73 /// calculator to not use liveness anymore. resetLiveInBlocks()74 void resetLiveInBlocks() { 75 LiveInBlocks = nullptr; 76 useLiveIn = false; 77 } 78 79 /// \brief Calculate iterated dominance frontiers 80 /// 81 /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in 82 /// the file-level comment. It performs DF->IDF pruning using the live-in 83 /// set, to avoid computing the IDF for blocks where an inserted PHI node 84 /// would be dead. 85 void calculate(SmallVectorImpl<BasicBlock *> &IDFBlocks); 86 87 private: 88 DominatorTreeBase<BasicBlock> &DT; 89 bool useLiveIn; 90 DenseMap<DomTreeNode *, unsigned> DomLevels; 91 const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks; 92 const SmallPtrSetImpl<BasicBlock *> *DefBlocks; 93 SmallVector<BasicBlock *, 32> PHIBlocks; 94 }; 95 } 96 #endif 97