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 FIR_ANALYSIS_IDF_H 24 #define FIR_ANALYSIS_IDF_H 25 26 #include "mlir/Analysis/Dominance.h" 27 #include "mlir/IR/Block.h" 28 #include "mlir/Support/LLVM.h" 29 30 namespace mlir { 31 class Block; 32 class DominanceInfo; 33 } // namespace mlir 34 35 namespace fir { 36 37 /// Determine the iterated dominance frontier, given a set of defining 38 /// blocks, and optionally, a set of live-in blocks. 39 /// 40 /// In turn, the results can be used to place phi nodes. 41 /// 42 /// This algorithm is a linear time computation of Iterated Dominance Frontiers, 43 /// pruned using the live-in set. 44 /// By default, liveness is not used to prune the IDF computation. 45 /// The template parameters should be either BasicBlock* or Inverse<BasicBlock 46 /// *>, depending on if you want the forward or reverse IDF. 47 template <class NodeTy, bool IsPostDom> 48 class IDFCalculator { 49 public: IDFCalculator(mlir::DominanceInfo & DT)50 IDFCalculator(mlir::DominanceInfo &DT) : DT(DT), useLiveIn(false) {} 51 52 /// 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 llvm::SmallPtrSetImpl<NodeTy * > & Blocks)57 void setDefiningBlocks(const llvm::SmallPtrSetImpl<NodeTy *> &Blocks) { 58 DefBlocks = &Blocks; 59 } 60 61 /// 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 llvm::SmallPtrSetImpl<NodeTy * > & Blocks)67 void setLiveInBlocks(const llvm::SmallPtrSetImpl<NodeTy *> &Blocks) { 68 LiveInBlocks = &Blocks; 69 useLiveIn = true; 70 } 71 72 /// 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 /// 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(llvm::SmallVectorImpl<NodeTy *> &IDFBlocks); 86 87 private: 88 mlir::DominanceInfo &DT; 89 bool useLiveIn; 90 const llvm::SmallPtrSetImpl<NodeTy *> *LiveInBlocks; 91 const llvm::SmallPtrSetImpl<NodeTy *> *DefBlocks; 92 }; 93 94 typedef IDFCalculator<mlir::Block, false> ForwardIDFCalculator; 95 96 } // namespace fir 97 #endif 98