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/DenseMap.h" 28 #include "llvm/ADT/SmallPtrSet.h" 29 #include "llvm/ADT/SmallVector.h" 30 #include "llvm/IR/BasicBlock.h" 31 #include "llvm/IR/Dominators.h" 32 33 namespace llvm { 34 35 /// \brief Determine the iterated dominance frontier, given a set of defining 36 /// blocks, and optionally, a set of live-in blocks. 37 /// 38 /// In turn, the results can be used to place phi nodes. 39 /// 40 /// This algorithm is a linear time computation of Iterated Dominance Frontiers, 41 /// pruned using the live-in set. 42 /// By default, liveness is not used to prune the IDF computation. 43 /// The template parameters should be either BasicBlock* or Inverse<BasicBlock 44 /// *>, depending on if you want the forward or reverse IDF. 45 template <class NodeTy> 46 class IDFCalculator { 47 48 public: 49 IDFCalculator(DominatorTreeBase<BasicBlock> &DT) : DT(DT), useLiveIn(false) {} 50 51 /// \brief Give the IDF calculator the set of blocks in which the value is 52 /// defined. This is equivalent to the set of starting blocks it should be 53 /// calculating the IDF for (though later gets pruned based on liveness). 54 /// 55 /// Note: This set *must* live for the entire lifetime of the IDF calculator. 56 void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { 57 DefBlocks = &Blocks; 58 } 59 60 /// \brief Give the IDF calculator the set of blocks in which the value is 61 /// live on entry to the block. This is used to prune the IDF calculation to 62 /// not include blocks where any phi insertion would be dead. 63 /// 64 /// Note: This set *must* live for the entire lifetime of the IDF calculator. 65 66 void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { 67 LiveInBlocks = &Blocks; 68 useLiveIn = true; 69 } 70 71 /// \brief Reset the live-in block set to be empty, and tell the IDF 72 /// calculator to not use liveness anymore. 73 void resetLiveInBlocks() { 74 LiveInBlocks = nullptr; 75 useLiveIn = false; 76 } 77 78 /// \brief Calculate iterated dominance frontiers 79 /// 80 /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in 81 /// the file-level comment. It performs DF->IDF pruning using the live-in 82 /// set, to avoid computing the IDF for blocks where an inserted PHI node 83 /// would be dead. 84 void calculate(SmallVectorImpl<BasicBlock *> &IDFBlocks); 85 86 private: 87 DominatorTreeBase<BasicBlock> &DT; 88 bool useLiveIn; 89 DenseMap<DomTreeNode *, unsigned> DomLevels; 90 const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks; 91 const SmallPtrSetImpl<BasicBlock *> *DefBlocks; 92 }; 93 typedef IDFCalculator<BasicBlock *> ForwardIDFCalculator; 94 typedef IDFCalculator<Inverse<BasicBlock *>> ReverseIDFCalculator; 95 } 96 #endif 97
