PostDominators.h revision 22bf8f21b4e91eadc27207c4b0a7db3dd1756b4f
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 77201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 78201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// used to compute the a post-dominance frontier. 79201ff603a79a677ca5feb438dd3fbe4b42fded14Misha Brukman/// 80a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerstruct PostDominanceFrontier : public DominanceFrontierBase { 811997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; 82794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel PostDominanceFrontier() 83ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : DominanceFrontierBase(&ID, true) {} 84a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 85a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual bool runOnFunction(Function &) { 86a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner Frontiers.clear(); 87a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 88420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner Roots = DT.getRoots(); 8926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel if (const DomTreeNode *Root = DT.getRootNode()) 90c72b249e9cb2f6c89fe3008bb8d1f49468bf5657Chris Lattner calculate(DT, Root); 91a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner return false; 92a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 93a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 94a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 95a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.setPreservesAll(); 96a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.addRequired<PostDominatorTree>(); 97a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 98a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 99a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerprivate: 100a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner const DomSetType &calculate(const PostDominatorTree &DT, 10126042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node); 102a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 103a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 1045771d6c16d71dc3bba59b88592686c76f07f4721Owen AndersonFunctionPass* createPostDomFrontier(); 1055771d6c16d71dc3bba59b88592686c76f07f4721Owen Anderson 106d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 107d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 108a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#endif 109