102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks//==- Dominators.h - Implementation of dominators tree for Clang CFG C++ -*-==// 258f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek// 358f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek// The LLVM Compiler Infrastructure 458f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek// 558f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek// This file is distributed under the University of Illinois Open Source 658f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek// License. See LICENSE.TXT for details. 758f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek// 858f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek//===----------------------------------------------------------------------===// 958f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek// 1002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks// This file implements the dominators tree functionality for Clang CFGs. 1158f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek// 1258f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek//===----------------------------------------------------------------------===// 1358f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 1458f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek#ifndef LLVM_CLANG_DOMINATORS_H 1558f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek#define LLVM_CLANG_DOMINATORS_H 1658f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 1758f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek#include "clang/Analysis/AnalysisContext.h" 1802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks#include "clang/Analysis/CFG.h" 1930a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/ADT/GraphTraits.h" 2002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks#include "llvm/Analysis/DominatorInternals.h" 2130a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/Analysis/Dominators.h" 223b844ba7d5be205a9b4f5f0b0d1b7978977f4b8cChandler Carruth#include "llvm/IR/Module.h" 2358f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 2458f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremeneknamespace clang { 2558f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 2658f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenekclass CFGBlock; 2702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zakstypedef llvm::DomTreeNodeBase<CFGBlock> DomTreeNode; 2858f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 2902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks/// \brief Concrete subclass of DominatorTreeBase for Clang 3002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks/// This class implements the dominators tree functionality given a Clang CFG. 3102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks/// 3258f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenekclass DominatorTree : public ManagedAnalysis { 3399ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie virtual void anchor(); 3458f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenekpublic: 3502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks llvm::DominatorTreeBase<CFGBlock>* DT; 3658f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 3702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks DominatorTree() { 3802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks DT = new llvm::DominatorTreeBase<CFGBlock>(false); 3902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 4058f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 4102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks ~DominatorTree() { 4202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks delete DT; 4302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 4458f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 4502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks llvm::DominatorTreeBase<CFGBlock>& getBase() { return *DT; } 4658f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 4702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method returns the root CFGBlock of the dominators tree. 4802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 4902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks inline CFGBlock *getRoot() const { 5002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return DT->getRoot(); 5102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 5202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 5302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method returns the root DomTreeNode, which is the wrapper 5402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// for CFGBlock. 5502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks inline DomTreeNode *getRootNode() const { 5602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return DT->getRootNode(); 5702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 5802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 5902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method compares two dominator trees. 6002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// The method returns false if the other dominator tree matches this 6102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// dominator tree, otherwise returns true. 6202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 6302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks inline bool compare(DominatorTree &Other) const { 6402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks DomTreeNode *R = getRootNode(); 6502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks DomTreeNode *OtherR = Other.getRootNode(); 6658f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 6702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) 6802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return true; 6958f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 7002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks if (DT->compare(Other.getBase())) 7102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return true; 7258f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 7302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return false; 7402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 7502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 7602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method builds the dominator tree for a given CFG 7702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// The CFG information is passed via AnalysisDeclContext 7858f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek /// 7902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks void buildDominatorTree(AnalysisDeclContext &AC) { 8002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks cfg = AC.getCFG(); 8102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks DT->recalculate(*cfg); 8202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 8302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 8402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method dumps immediate dominators for each block, 8502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// mainly used for debug purposes. 8658f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek /// 8702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks void dump() { 8802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n"; 8902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks for (CFG::const_iterator I = cfg->begin(), 9002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks E = cfg->end(); I != E; ++I) { 9102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks if(DT->getNode(*I)->getIDom()) 9202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks llvm::errs() << "(" << (*I)->getBlockID() 9302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks << "," 9402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks << DT->getNode(*I)->getIDom()->getBlock()->getBlockID() 9502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks << ")\n"; 9602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks else llvm::errs() << "(" << (*I)->getBlockID() 9702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks << "," << (*I)->getBlockID() << ")\n"; 9802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 9902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 10002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 10102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method tests if one CFGBlock dominates the other. 10202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// The method return true if A dominates B, false otherwise. 10302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// Note a block always dominates itself. 10402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 10502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks inline bool dominates(const CFGBlock* A, const CFGBlock* B) const { 10602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return DT->dominates(A, B); 10702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 10802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 10902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method tests if one CFGBlock properly dominates the other. 11002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// The method return true if A properly dominates B, false otherwise. 11102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 11202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks bool properlyDominates(const CFGBlock*A, const CFGBlock*B) const { 11302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return DT->properlyDominates(A, B); 11402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 11558f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 11602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method finds the nearest common dominator CFG block 11702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// for CFG block A and B. If there is no such block then return NULL. 11802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 11902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks inline CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) { 12002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return DT->findNearestCommonDominator(A, B); 12102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 12202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 12302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A, 12402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks const CFGBlock *B) { 12502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return DT->findNearestCommonDominator(A, B); 12602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 12702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 12802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method is used to update the dominator 12902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// tree information when a node's immediate dominator changes. 13002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 13102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) { 13202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks DT->changeImmediateDominator(N, NewIDom); 13302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 13402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 13502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method tests if the given CFGBlock can be reachable from root. 13602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// Returns true if reachable, false otherwise. 13702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 13802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks bool isReachableFromEntry(const CFGBlock *A) { 13902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return DT->isReachableFromEntry(A); 14002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 14102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 14202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method releases the memory held by the dominator tree. 14302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 14402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks virtual void releaseMemory() { 14502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks DT->releaseMemory(); 14602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 14702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 14802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// \brief This method converts the dominator tree to human readable form. 14902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks /// 15002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks virtual void print(raw_ostream &OS, const llvm::Module* M= 0) const { 15102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks DT->print(OS); 15202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 15358f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 15458f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenekprivate: 15502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks CFG *cfg; 15658f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek}; 15758f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 15899ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikieinline void WriteAsOperand(raw_ostream &OS, const CFGBlock *BB, 15902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks bool t) { 16002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks OS << "BB#" << BB->getBlockID(); 16102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks} 16202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 16358f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek} // end namespace clang 16458f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 16502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks//===------------------------------------- 16602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks/// DominatorTree GraphTraits specialization so the DominatorTree can be 16702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks/// iterable by generic graph iterators. 16802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks/// 16902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaksnamespace llvm { 17002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zakstemplate <> struct GraphTraits< ::clang::DomTreeNode* > { 17102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks typedef ::clang::DomTreeNode NodeType; 17202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks typedef NodeType::iterator ChildIteratorType; 17302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 17402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks static NodeType *getEntryNode(NodeType *N) { 17502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return N; 17602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 17702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks static inline ChildIteratorType child_begin(NodeType *N) { 17802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return N->begin(); 17902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 18002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks static inline ChildIteratorType child_end(NodeType *N) { 18102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return N->end(); 18202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 18302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 18402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks typedef df_iterator< ::clang::DomTreeNode* > nodes_iterator; 18502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 18602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks static nodes_iterator nodes_begin(::clang::DomTreeNode *N) { 18702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return df_begin(getEntryNode(N)); 18802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 18902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 19002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks static nodes_iterator nodes_end(::clang::DomTreeNode *N) { 19102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return df_end(getEntryNode(N)); 19202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 19302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks}; 19402f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 19502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zakstemplate <> struct GraphTraits< ::clang::DominatorTree* > 19602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks : public GraphTraits< ::clang::DomTreeNode* > { 19702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks static NodeType *getEntryNode(::clang::DominatorTree *DT) { 19802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return DT->getRootNode(); 19902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 20002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 20102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks static nodes_iterator nodes_begin(::clang::DominatorTree *N) { 20202f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return df_begin(getEntryNode(N)); 20302f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 20458f6f1e37ab32fdd0c8bab6771d8e09bc139e9edTed Kremenek 20502f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks static nodes_iterator nodes_end(::clang::DominatorTree *N) { 20602f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks return df_end(getEntryNode(N)); 20702f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks } 20802f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks}; 20902f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks} // end namespace llvm 21002f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks 21102f34c5003b2c5067675f89ffce0a84c28faf722Anna Zaks#endif 212