148486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 9a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// 10a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// This file exposes interfaces to post dominance information. 11a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// 12a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner//===----------------------------------------------------------------------===// 13a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 14a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#ifndef LLVM_ANALYSIS_POST_DOMINATORS_H 15a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#define LLVM_ANALYSIS_POST_DOMINATORS_H 16a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 171a8b9dd7fb945ab78232f3853219cc693bcb5fadChris Lattner#include "llvm/Analysis/Dominators.h" 18a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 19d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 20d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 21201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to 22201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// compute the a post-dominator tree. 23201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// 24d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Andersonstruct PostDominatorTree : public FunctionPass { 25ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 26d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson DominatorTreeBase<BasicBlock>* DT; 27794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 2890c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson PostDominatorTree() : FunctionPass(ID) { 29081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializePostDominatorTreePass(*PassRegistry::getPassRegistry()); 307feb3be0b76c72134c515995b1a37466171cf83bOwen Anderson DT = new DominatorTreeBase<BasicBlock>(true); 31d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 32a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 33f6055806d4a6a39c49c441215a9a5d3a8e933de0Torok Edwin ~PostDominatorTree(); 34f6055806d4a6a39c49c441215a9a5d3a8e933de0Torok Edwin 35471ab54df756f2f48c9146ad897672662c3f25f9Owen Anderson virtual bool runOnFunction(Function &F); 36a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 37a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 38a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.setPreservesAll(); 39a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 40d53e42efe93f6a716d082ad63862794da0e59895Tobias Grosser 41d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline const std::vector<BasicBlock*> &getRoots() const { 42d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->getRoots(); 43d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 44d53e42efe93f6a716d082ad63862794da0e59895Tobias Grosser 45d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline DomTreeNode *getRootNode() const { 46d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->getRootNode(); 47d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 48d53e42efe93f6a716d082ad63862794da0e59895Tobias Grosser 49d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline DomTreeNode *operator[](BasicBlock *BB) const { 50d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->getNode(BB); 51d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 52d53e42efe93f6a716d082ad63862794da0e59895Tobias Grosser 53af4421d6efff5a1c91e7669933738487c609238bTobias Grosser inline DomTreeNode *getNode(BasicBlock *BB) const { 54af4421d6efff5a1c91e7669933738487c609238bTobias Grosser return DT->getNode(BB); 55af4421d6efff5a1c91e7669933738487c609238bTobias Grosser } 56af4421d6efff5a1c91e7669933738487c609238bTobias Grosser 5722bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { 5822bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman return DT->dominates(A, B); 5922bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman } 6022bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman 6122bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { 6222bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman return DT->dominates(A, B); 6322bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman } 6422bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman 65d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { 66d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->properlyDominates(A, B); 67d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 68d53e42efe93f6a716d082ad63862794da0e59895Tobias Grosser 69d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const { 70d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->properlyDominates(A, B); 71d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 72e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman 738f9db4c1d58114f54b585251f5bf61a498613b7cTobias Grosser inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) { 748f9db4c1d58114f54b585251f5bf61a498613b7cTobias Grosser return DT->findNearestCommonDominator(A, B); 758f9db4c1d58114f54b585251f5bf61a498613b7cTobias Grosser } 768f9db4c1d58114f54b585251f5bf61a498613b7cTobias Grosser 7722bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman virtual void releaseMemory() { 7822bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman DT->releaseMemory(); 7922bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman } 8022bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman 8145cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner virtual void print(raw_ostream &OS, const Module*) const; 82a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 83a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 845771d6c16d71dc3bba59b88592686c76f07f4721Owen AndersonFunctionPass* createPostDomTree(); 85a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 86f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattnertemplate <> struct GraphTraits<PostDominatorTree*> 87f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner : public GraphTraits<DomTreeNode*> { 88f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static NodeType *getEntryNode(PostDominatorTree *DT) { 89f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner return DT->getRootNode(); 90f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 91f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 92f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static nodes_iterator nodes_begin(PostDominatorTree *N) { 932833fac27324b956cfb31be987652d2304d10761Tobias Grosser if (getEntryNode(N)) 942833fac27324b956cfb31be987652d2304d10761Tobias Grosser return df_begin(getEntryNode(N)); 952833fac27324b956cfb31be987652d2304d10761Tobias Grosser else 962833fac27324b956cfb31be987652d2304d10761Tobias Grosser return df_end(getEntryNode(N)); 97f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 98f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 99f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static nodes_iterator nodes_end(PostDominatorTree *N) { 100f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner return df_end(getEntryNode(N)); 101f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 102f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner}; 103f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 104d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 105d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 106a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#endif 107