PostDominators.h revision 2833fac27324b956cfb31be987652d2304d10761
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 17a69fd903585a665c031d5aa3fdfb8dc919b44befChris 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 28ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman PostDominatorTree() : FunctionPass(&ID) { 297feb3be0b76c72134c515995b1a37466171cf83bOwen Anderson DT = new DominatorTreeBase<BasicBlock>(true); 30d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 31a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 32f6055806d4a6a39c49c441215a9a5d3a8e933de0Torok Edwin ~PostDominatorTree(); 33f6055806d4a6a39c49c441215a9a5d3a8e933de0Torok Edwin 34471ab54df756f2f48c9146ad897672662c3f25f9Owen Anderson virtual bool runOnFunction(Function &F); 35a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 36a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 37a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.setPreservesAll(); 38a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 39d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson 40d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline const std::vector<BasicBlock*> &getRoots() const { 41d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->getRoots(); 42d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 43d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson 44d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline DomTreeNode *getRootNode() const { 45d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->getRootNode(); 46d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 47d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson 48d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline DomTreeNode *operator[](BasicBlock *BB) const { 49d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->getNode(BB); 50d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 51d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson 5222bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { 5322bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman return DT->dominates(A, B); 5422bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman } 5522bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman 5622bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { 5722bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman return DT->dominates(A, B); 5822bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman } 5922bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman 60d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { 61d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->properlyDominates(A, B); 62d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 63d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson 64d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const { 65d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson return DT->properlyDominates(A, B); 66d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson } 67e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman 6822bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman virtual void releaseMemory() { 6922bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman DT->releaseMemory(); 7022bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman } 7122bf8f21b4e91eadc27207c4b0a7db3dd1756b4fDan Gohman 7245cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner virtual void print(raw_ostream &OS, const Module*) const; 73a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 74a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 755771d6c16d71dc3bba59b88592686c76f07f4721Owen AndersonFunctionPass* createPostDomTree(); 76a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 77f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattnertemplate <> struct GraphTraits<PostDominatorTree*> 78f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner : public GraphTraits<DomTreeNode*> { 79f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static NodeType *getEntryNode(PostDominatorTree *DT) { 80f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner return DT->getRootNode(); 81f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 82f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 83f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static nodes_iterator nodes_begin(PostDominatorTree *N) { 842833fac27324b956cfb31be987652d2304d10761Tobias Grosser if (getEntryNode(N)) 852833fac27324b956cfb31be987652d2304d10761Tobias Grosser return df_begin(getEntryNode(N)); 862833fac27324b956cfb31be987652d2304d10761Tobias Grosser else 872833fac27324b956cfb31be987652d2304d10761Tobias Grosser return df_end(getEntryNode(N)); 88f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 89f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 90f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner static nodes_iterator nodes_end(PostDominatorTree *N) { 91f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner return df_end(getEntryNode(N)); 92f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner } 93f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner}; 94f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner 95201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 96201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// used to compute the a post-dominance frontier. 97201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// 98a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerstruct PostDominanceFrontier : public DominanceFrontierBase { 991997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; 100794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel PostDominanceFrontier() 101ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : DominanceFrontierBase(&ID, true) {} 102a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 103a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual bool runOnFunction(Function &) { 104a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner Frontiers.clear(); 105a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 106420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner Roots = DT.getRoots(); 10726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel if (const DomTreeNode *Root = DT.getRootNode()) 108c72b249e9cb2f6c89fe3008bb8d1f49468bf5657Chris Lattner calculate(DT, Root); 109a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner return false; 110a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 111a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 112a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 113a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.setPreservesAll(); 114a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.addRequired<PostDominatorTree>(); 115a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 116a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 117a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerprivate: 118a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner const DomSetType &calculate(const PostDominatorTree &DT, 11926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node); 120a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 121a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 1225771d6c16d71dc3bba59b88592686c76f07f4721Owen AndersonFunctionPass* createPostDomFrontier(); 1235771d6c16d71dc3bba59b88592686c76f07f4721Owen Anderson 124d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 125d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 126a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#endif 127