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 219fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include "llvm/Analysis/Dominators.h" 229fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include <map> 239fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include <set> 249fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 259fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnernamespace llvm { 269fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 279fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner//===----------------------------------------------------------------------===// 289fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// DominanceFrontierBase - Common base class for computing forward and inverse 299fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// dominance frontiers for a function. 309fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// 319fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerclass DominanceFrontierBase : public FunctionPass { 329fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerpublic: 339fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 349fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 359fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerprotected: 369fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DomSetMapType Frontiers; 379fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner std::vector<BasicBlock*> Roots; 389fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const bool IsPostDominators; 399fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 409fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerpublic: 419fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DominanceFrontierBase(char &ID, bool isPostDom) 429fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner : FunctionPass(ID), IsPostDominators(isPostDom) {} 439fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 449fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// getRoots - Return the root blocks of the current CFG. This may include 459fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// multiple blocks if we are computing post dominators. For forward 469fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// dominators, this will always be a single block (the entry node). 479fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// 489fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner inline const std::vector<BasicBlock*> &getRoots() const { return Roots; } 499fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 509fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// isPostDominator - Returns true if analysis based of postdoms 519fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// 529fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner bool isPostDominator() const { return IsPostDominators; } 539fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 549fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner virtual void releaseMemory() { Frontiers.clear(); } 559fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 569fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner // Accessor interface: 579fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner typedef DomSetMapType::iterator iterator; 589fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner typedef DomSetMapType::const_iterator const_iterator; 599fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner iterator begin() { return Frontiers.begin(); } 609fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const_iterator begin() const { return Frontiers.begin(); } 619fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner iterator end() { return Frontiers.end(); } 629fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const_iterator end() const { return Frontiers.end(); } 639fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner iterator find(BasicBlock *B) { return Frontiers.find(B); } 649fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } 659fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 669fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 679fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner assert(find(BB) == end() && "Block already in DominanceFrontier!"); 689fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return Frontiers.insert(std::make_pair(BB, frontier)).first; 699fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 709fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 719fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// removeBlock - Remove basic block BB's frontier. 729fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner void removeBlock(BasicBlock *BB) { 739fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner assert(find(BB) != end() && "Block is not in DominanceFrontier!"); 749fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner for (iterator I = begin(), E = end(); I != E; ++I) 759fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner I->second.erase(BB); 769fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner Frontiers.erase(BB); 779fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 789fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 799fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner void addToFrontier(iterator I, BasicBlock *Node) { 809fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner assert(I != end() && "BB is not in DominanceFrontier!"); 819fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner I->second.insert(Node); 829fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 839fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 849fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner void removeFromFrontier(iterator I, BasicBlock *Node) { 859fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner assert(I != end() && "BB is not in DominanceFrontier!"); 869fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 879fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner I->second.erase(Node); 889fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 899fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 909fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// compareDomSet - Return false if two domsets match. Otherwise 919fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// return true; 929fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { 939fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner std::set<BasicBlock *> tmpSet; 949fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner for (DomSetType::const_iterator I = DS2.begin(), 959fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner E = DS2.end(); I != E; ++I) 969fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner tmpSet.insert(*I); 979fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 989fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner for (DomSetType::const_iterator I = DS1.begin(), 999fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner E = DS1.end(); I != E; ) { 1009fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner BasicBlock *Node = *I++; 1019fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1029fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner if (tmpSet.erase(Node) == 0) 1039fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner // Node is in DS1 but not in DS2. 1049fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return true; 1059fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1069fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1079fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner if (!tmpSet.empty()) 1089fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner // There are nodes that are in DS2 but not in DS1. 1099fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return true; 1109fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1119fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner // DS1 and DS2 matches. 1129fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return false; 1139fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1149fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1159fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// compare - Return true if the other dominance frontier base matches 1169fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// this dominance frontier base. Otherwise return false. 1179fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner bool compare(DominanceFrontierBase &Other) const { 1189fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DomSetMapType tmpFrontiers; 1199fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner for (DomSetMapType::const_iterator I = Other.begin(), 1209fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner E = Other.end(); I != E; ++I) 1219fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner tmpFrontiers.insert(std::make_pair(I->first, I->second)); 1229fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1239fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner for (DomSetMapType::iterator I = tmpFrontiers.begin(), 1249fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner E = tmpFrontiers.end(); I != E; ) { 1259fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner BasicBlock *Node = I->first; 1269fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const_iterator DFI = find(Node); 1279fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner if (DFI == end()) 1289fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return true; 1299fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1309fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner if (compareDomSet(I->second, DFI->second)) 1319fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return true; 1329fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1339fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner ++I; 1349fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner tmpFrontiers.erase(Node); 1359fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1369fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1379fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner if (!tmpFrontiers.empty()) 1389fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return true; 1399fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1409fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return false; 1419fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1429fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1439fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// print - Convert to human readable form 1449fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// 1459fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner virtual void print(raw_ostream &OS, const Module* = 0) const; 1469fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1479fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner /// dump - Dump the dominance frontier to dbgs(). 1489fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner void dump() const; 1499fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner}; 1509fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1519fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1529fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner//===------------------------------------- 1539fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is 1549fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// used to compute a forward dominator frontiers. 1559fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner/// 1569fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerclass DominanceFrontier : public DominanceFrontierBase { 1572d24e2a396a1d211baaeedf32148a3b657240170David Blaikie virtual void anchor(); 1589fc5cdf77c812aaa80419036de27576d45894d0dChris Lattnerpublic: 1599fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner static char ID; // Pass ID, replacement for typeid 1609fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DominanceFrontier() : 1619fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DominanceFrontierBase(ID, false) { 1629fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner initializeDominanceFrontierPass(*PassRegistry::getPassRegistry()); 1639fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1649fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1659fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner BasicBlock *getRoot() const { 1669fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner assert(Roots.size() == 1 && "Should always have entry node!"); 1679fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return Roots[0]; 1689fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1699fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1709fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner virtual bool runOnFunction(Function &) { 1719fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner Frontiers.clear(); 1729fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 1739fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner Roots = DT.getRoots(); 1749fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); 1759fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner calculate(DT, DT[Roots[0]]); 1769fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner return false; 1779fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1789fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1799fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 1809fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner AU.setPreservesAll(); 1819fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner AU.addRequired<DominatorTree>(); 1829fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner } 1839fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1849fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const DomSetType &calculate(const DominatorTree &DT, 1859fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner const DomTreeNode *Node); 1869fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner}; 1879fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1889fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner} // End llvm namespace 1899fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner 1909fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#endif 191