1 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation --*- C++ -*-=// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file exposes interfaces to post dominance information. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H 14 #define LLVM_ANALYSIS_POSTDOMINATORS_H 15 16 #include "llvm/ADT/DepthFirstIterator.h" 17 #include "llvm/IR/Dominators.h" 18 #include "llvm/IR/PassManager.h" 19 #include "llvm/Pass.h" 20 21 namespace llvm { 22 23 class Function; 24 class raw_ostream; 25 26 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to 27 /// compute the post-dominator tree. 28 class PostDominatorTree : public PostDomTreeBase<BasicBlock> { 29 public: 30 using Base = PostDomTreeBase<BasicBlock>; 31 32 PostDominatorTree() = default; 33 explicit PostDominatorTree(Function &F) { recalculate(F); } 34 /// Handle invalidation explicitly. 35 bool invalidate(Function &F, const PreservedAnalyses &PA, 36 FunctionAnalysisManager::Invalidator &); 37 }; 38 39 /// Analysis pass which computes a \c PostDominatorTree. 40 class PostDominatorTreeAnalysis 41 : public AnalysisInfoMixin<PostDominatorTreeAnalysis> { 42 friend AnalysisInfoMixin<PostDominatorTreeAnalysis>; 43 44 static AnalysisKey Key; 45 46 public: 47 /// Provide the result type for this analysis pass. 48 using Result = PostDominatorTree; 49 50 /// Run the analysis pass over a function and produce a post dominator 51 /// tree. 52 PostDominatorTree run(Function &F, FunctionAnalysisManager &); 53 }; 54 55 /// Printer pass for the \c PostDominatorTree. 56 class PostDominatorTreePrinterPass 57 : public PassInfoMixin<PostDominatorTreePrinterPass> { 58 raw_ostream &OS; 59 60 public: 61 explicit PostDominatorTreePrinterPass(raw_ostream &OS); 62 63 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 64 }; 65 66 struct PostDominatorTreeWrapperPass : public FunctionPass { 67 static char ID; // Pass identification, replacement for typeid 68 69 PostDominatorTree DT; 70 71 PostDominatorTreeWrapperPass() : FunctionPass(ID) { 72 initializePostDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); 73 } 74 75 PostDominatorTree &getPostDomTree() { return DT; } 76 const PostDominatorTree &getPostDomTree() const { return DT; } 77 78 bool runOnFunction(Function &F) override; 79 80 void verifyAnalysis() const override; 81 82 void getAnalysisUsage(AnalysisUsage &AU) const override { 83 AU.setPreservesAll(); 84 } 85 86 void releaseMemory() override { 87 DT.releaseMemory(); 88 } 89 90 void print(raw_ostream &OS, const Module*) const override; 91 }; 92 93 FunctionPass* createPostDomTree(); 94 95 template <> struct GraphTraits<PostDominatorTree*> 96 : public GraphTraits<DomTreeNode*> { 97 static NodeRef getEntryNode(PostDominatorTree *DT) { 98 return DT->getRootNode(); 99 } 100 101 static nodes_iterator nodes_begin(PostDominatorTree *N) { 102 if (getEntryNode(N)) 103 return df_begin(getEntryNode(N)); 104 else 105 return df_end(getEntryNode(N)); 106 } 107 108 static nodes_iterator nodes_end(PostDominatorTree *N) { 109 return df_end(getEntryNode(N)); 110 } 111 }; 112 113 } // end namespace llvm 114 115 #endif // LLVM_ANALYSIS_POSTDOMINATORS_H 116