19fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===// 29fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// 39fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// The LLVM Compiler Infrastructure 49fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// 59fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// This file is distributed under the University of Illinois Open Source 69fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// License. See LICENSE.TXT for details. 79fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// 89fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner//===----------------------------------------------------------------------===// 99fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// 109fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// This file defines the DominanceFrontier class, which calculate and holds the 119fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// dominance frontier for a function. 129fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// 139fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// This should be considered deprecated, don't add any more uses of this data 149fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// structure. 159fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner// 169fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner//===----------------------------------------------------------------------===// 179fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 189fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H 199fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H 209fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 229fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include <map> 239fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include <set> 249fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 259fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnernamespace llvm { 2637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 279fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner//===----------------------------------------------------------------------===// 289fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// DominanceFrontierBase - Common base class for computing forward and inverse 299fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// dominance frontiers for a function. 309fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// 3137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class BlockT> 3237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass DominanceFrontierBase { 339fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerpublic: 3437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef std::set<BlockT *> DomSetType; // Dom set for a bb 3537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef std::map<BlockT *, DomSetType> DomSetMapType; // Dom set map 3637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 379fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerprotected: 3837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef GraphTraits<BlockT *> BlockTraits; 3937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 409fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DomSetMapType Frontiers; 4137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<BlockT *> Roots; 429fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const bool IsPostDominators; 439fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 449fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerpublic: 4537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DominanceFrontierBase(bool isPostDom) : IsPostDominators(isPostDom) {} 469fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 479fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// getRoots - Return the root blocks of the current CFG. This may include 489fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// multiple blocks if we are computing post dominators. For forward 499fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// dominators, this will always be a single block (the entry node). 509fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// 5137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines inline const std::vector<BlockT *> &getRoots() const { 5237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Roots; 5337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 5437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 5537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *getRoot() const { 5637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(Roots.size() == 1 && "Should always have entry node!"); 5737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Roots[0]; 5837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 599fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 609fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// isPostDominator - Returns true if analysis based of postdoms 619fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// 6237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool isPostDominator() const { 6337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return IsPostDominators; 6437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 659fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 6637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void releaseMemory() { 6737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Frontiers.clear(); 6837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 699fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 709fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner // Accessor interface: 7137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename DomSetMapType::iterator iterator; 7237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename DomSetMapType::const_iterator const_iterator; 7337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines iterator begin() { return Frontiers.begin(); } 749fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const_iterator begin() const { return Frontiers.begin(); } 7537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines iterator end() { return Frontiers.end(); } 7637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const_iterator end() const { return Frontiers.end(); } 7737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines iterator find(BlockT *B) { return Frontiers.find(B); } 7837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const_iterator find(BlockT *B) const { return Frontiers.find(B); } 799fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 8037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) { 819fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner assert(find(BB) == end() && "Block already in DominanceFrontier!"); 829fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return Frontiers.insert(std::make_pair(BB, frontier)).first; 839fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 849fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 859fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// removeBlock - Remove basic block BB's frontier. 8637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void removeBlock(BlockT *BB); 879fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 8837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void addToFrontier(iterator I, BlockT *Node); 899fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 9037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void removeFromFrontier(iterator I, BlockT *Node); 919fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 929fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// compareDomSet - Return false if two domsets match. Otherwise 939fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// return true; 9437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const; 959fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 969fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// compare - Return true if the other dominance frontier base matches 979fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// this dominance frontier base. Otherwise return false. 9837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool compare(DominanceFrontierBase<BlockT> &Other) const; 999fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1009fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// print - Convert to human readable form 1019fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// 10237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void print(raw_ostream &OS) const; 1039fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1049fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// dump - Dump the dominance frontier to dbgs(). 10537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1069fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner void dump() const; 10737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif 1089fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner}; 1099fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1109fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner//===------------------------------------- 1119fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is 1129fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// used to compute a forward dominator frontiers. 1139fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// 11437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class BlockT> 11537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass ForwardDominanceFrontierBase : public DominanceFrontierBase<BlockT> { 11637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesprivate: 11737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef GraphTraits<BlockT *> BlockTraits; 11837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 12037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DominatorTreeBase<BlockT> DomTreeT; 12137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DomTreeNodeBase<BlockT> DomTreeNodeT; 12237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename DominanceFrontierBase<BlockT>::DomSetType DomSetType; 12337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 12437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ForwardDominanceFrontierBase() : DominanceFrontierBase<BlockT>(false) {} 12537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 12637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void analyze(DomTreeT &DT) { 12737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines this->Roots = DT.getRoots(); 12837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(this->Roots.size() == 1 && 12937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines "Only one entry block for forward domfronts!"); 13037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines calculate(DT, DT[this->Roots[0]]); 13137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 13237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 13337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node); 13437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 13537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 13637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass DominanceFrontier : public FunctionPass { 13737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ForwardDominanceFrontierBase<BasicBlock> Base; 13837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 1399fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerpublic: 14037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DominatorTreeBase<BasicBlock> DomTreeT; 14137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DomTreeNodeBase<BasicBlock> DomTreeNodeT; 14237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DominanceFrontierBase<BasicBlock>::DomSetType DomSetType; 14337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DominanceFrontierBase<BasicBlock>::iterator iterator; 14437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DominanceFrontierBase<BasicBlock>::const_iterator const_iterator; 14537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 1469fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner static char ID; // Pass ID, replacement for typeid 1479fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 14837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DominanceFrontier(); 14937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 15037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ForwardDominanceFrontierBase<BasicBlock> &getBase() { return Base; } 15137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 15237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines inline const std::vector<BasicBlock *> &getRoots() const { 15337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Base.getRoots(); 1549fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1559fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 15637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BasicBlock *getRoot() const { return Base.getRoot(); } 15737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 15837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool isPostDominator() const { return Base.isPostDominator(); } 15937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 16037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines iterator begin() { return Base.begin(); } 16137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 16237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const_iterator begin() const { return Base.begin(); } 16337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 16437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines iterator end() { return Base.end(); } 16537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 16637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const_iterator end() const { return Base.end(); } 16737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 16837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines iterator find(BasicBlock *B) { return Base.find(B); } 16937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 17037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const_iterator find(BasicBlock *B) const { return Base.find(B); } 17137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 17237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 17337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Base.addBasicBlock(BB, frontier); 1749fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1759fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 17637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void removeBlock(BasicBlock *BB) { return Base.removeBlock(BB); } 17737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 17837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void addToFrontier(iterator I, BasicBlock *Node) { 17937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Base.addToFrontier(I, Node); 18037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 18137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 18237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void removeFromFrontier(iterator I, BasicBlock *Node) { 18337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Base.removeFromFrontier(I, Node); 1849fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1859fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 18637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { 18737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Base.compareDomSet(DS1, DS2); 18837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 18937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool compare(DominanceFrontierBase<BasicBlock> &Other) const { 19137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Base.compare(Other); 19237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 19337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void releaseMemory() override; 19537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool runOnFunction(Function &) override; 19737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 19937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 20037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void print(raw_ostream &OS, const Module * = nullptr) const override; 20137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 20237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void dump() const; 2039fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner}; 2049fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 205cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarextern template class DominanceFrontierBase<BasicBlock>; 206cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarextern template class ForwardDominanceFrontierBase<BasicBlock>; 20737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2089fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner} // End llvm namespace 2099fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 2109fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#endif 211