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