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 14674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_POSTDOMINATORS_H 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_POSTDOMINATORS_H 16a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 18a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 19d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 20d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 21201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to 2237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// compute the 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 330c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar ~PostDominatorTree() override; 34f6055806d4a6a39c49c441215a9a5d3a8e933de0Torok Edwin 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 36a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 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 773ade978551927cfb0e6dd4e26f0768908b1898bbBenjamin Kramer inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A, 783ade978551927cfb0e6dd4e26f0768908b1898bbBenjamin Kramer const BasicBlock *B) { 793ade978551927cfb0e6dd4e26f0768908b1898bbBenjamin Kramer return DT->findNearestCommonDominator(A, B); 803ade978551927cfb0e6dd4e26f0768908b1898bbBenjamin Kramer } 813ade978551927cfb0e6dd4e26f0768908b1898bbBenjamin Kramer 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Get all nodes post-dominated by R, including R itself. 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getDescendants(BasicBlock *R, 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVectorImpl<BasicBlock *> &Result) const { 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT->getDescendants(R, Result); 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseMemory() override { 8922bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman DT->releaseMemory(); 9022bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman } 9122bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void print(raw_ostream &OS, const Module*) const override; 93a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 94a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 955771d6c16d71dc3bba59b88592686c76f07f4721Owen AndersonFunctionPass* createPostDomTree(); 96a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 97f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattnertemplate <> struct GraphTraits<PostDominatorTree*> 98f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner : public GraphTraits<DomTreeNode*> { 99f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static NodeType *getEntryNode(PostDominatorTree *DT) { 100f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner return DT->getRootNode(); 101f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 102f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 103f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static nodes_iterator nodes_begin(PostDominatorTree *N) { 1042833fac27324b956cfb31be987652d2304d10761Tobias Grosser if (getEntryNode(N)) 1052833fac27324b956cfb31be987652d2304d10761Tobias Grosser return df_begin(getEntryNode(N)); 1062833fac27324b956cfb31be987652d2304d10761Tobias Grosser else 1072833fac27324b956cfb31be987652d2304d10761Tobias Grosser return df_end(getEntryNode(N)); 108f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 109f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 110f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static nodes_iterator nodes_end(PostDominatorTree *N) { 111f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner return df_end(getEntryNode(N)); 112f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 113f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner}; 114f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 115d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 116d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 117a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#endif 118