PostDominators.h revision d0fde30ce850b78371fd1386338350591f9ff494
148486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===// 26fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 56fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// This file was developed by the LLVM research group and is distributed under 66fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 76fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 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 21a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 22420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner/// PostDominatorSet Class - Concrete subclass of DominatorSetBase that is used 23420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner/// to compute the post-dominator set. Because there can be multiple exit nodes 24420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner/// in an LLVM function, we calculate post dominators with a special null block 25420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner/// which is the virtual exit node that the real exit nodes all virtually branch 26420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner/// to. Clients should be prepared to see an entry in the dominator sets with a 27420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner/// null BasicBlock*. 28420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner/// 29a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerstruct PostDominatorSet : public DominatorSetBase { 30a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner PostDominatorSet() : DominatorSetBase(true) {} 31a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 32a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual bool runOnFunction(Function &F); 33a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 34420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner // getAnalysisUsage - This pass does not modify the function at all. 35a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner // 36420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 37420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner AU.setPreservesAll(); 38420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner } 39a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 40a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 41a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 42a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 43a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner//===------------------------------------- 44a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase 45a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// that is used to compute the immediate post-dominators. 46a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// 47a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerstruct ImmediatePostDominators : public ImmediateDominatorsBase { 48a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner ImmediatePostDominators() : ImmediateDominatorsBase(true) {} 49a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 50a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual bool runOnFunction(Function &F) { 51a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner IDoms.clear(); // Reset from the last time we were run... 52a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner PostDominatorSet &DS = getAnalysis<PostDominatorSet>(); 53420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner Roots = DS.getRoots(); 54a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner calcIDoms(DS); 55a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner return false; 56a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 57a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 58a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 59a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.setPreservesAll(); 60a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.addRequired<PostDominatorSet>(); 61a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 62a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 63a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 64a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 65a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner//===------------------------------------- 66a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to 67a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// compute the a post-dominator tree. 68a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// 69a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerstruct PostDominatorTree : public DominatorTreeBase { 70a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner PostDominatorTree() : DominatorTreeBase(true) {} 71a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 72a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual bool runOnFunction(Function &F) { 73a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner reset(); // Reset from the last time we were run... 74a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner PostDominatorSet &DS = getAnalysis<PostDominatorSet>(); 75420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner Roots = DS.getRoots(); 76a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner calculate(DS); 77a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner return false; 78a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 79a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 80a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 81a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.setPreservesAll(); 82a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.addRequired<PostDominatorSet>(); 83a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 84a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerprivate: 85a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner void calculate(const PostDominatorSet &DS); 86a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 87a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 88a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 89a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner//===------------------------------------- 90a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 91a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// used to compute the a post-dominance frontier. 92a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// 93a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerstruct PostDominanceFrontier : public DominanceFrontierBase { 94a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner PostDominanceFrontier() : DominanceFrontierBase(true) {} 95a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 96a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual bool runOnFunction(Function &) { 97a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner Frontiers.clear(); 98a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 99420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner Roots = DT.getRoots(); 100c72b249e9cb2f6c89fe3008bb8d1f49468bf5657Chris Lattner if (const DominatorTree::Node *Root = DT.getRootNode()) 101c72b249e9cb2f6c89fe3008bb8d1f49468bf5657Chris Lattner calculate(DT, Root); 102a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner return false; 103a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 104a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 105a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 106a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.setPreservesAll(); 107a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner AU.addRequired<PostDominatorTree>(); 108a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner } 109a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 110a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner // stub - dummy function, just ignore it 111a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner static void stub(); 112a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 113a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerprivate: 114a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner const DomSetType &calculate(const PostDominatorTree &DT, 115a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner const DominatorTree::Node *Node); 116a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner}; 117a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 118a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// Make sure that any clients of this file link in PostDominators.cpp 119a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnerstatic IncludeFile 120a69fd903585a665c031d5aa3fdfb8dc919b44befChris LattnerPOST_DOMINATOR_INCLUDE_FILE((void*)&PostDominanceFrontier::stub); 121a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 122d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 123d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 124a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#endif 125