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; PostDominatorTree(Function & F)33 explicit PostDominatorTree(Function &F) { recalculate(F); } 34 /// Handle invalidation explicitly. 35 bool invalidate(Function &F, const PreservedAnalyses &PA, 36 FunctionAnalysisManager::Invalidator &); 37 38 // Ensure base-class overloads are visible. 39 using Base::dominates; 40 41 /// Return true if \p I1 dominates \p I2. This checks if \p I2 comes before 42 /// \p I1 if they belongs to the same basic block. 43 bool dominates(const Instruction *I1, const Instruction *I2) const; 44 }; 45 46 /// Analysis pass which computes a \c PostDominatorTree. 47 class PostDominatorTreeAnalysis 48 : public AnalysisInfoMixin<PostDominatorTreeAnalysis> { 49 friend AnalysisInfoMixin<PostDominatorTreeAnalysis>; 50 51 static AnalysisKey Key; 52 53 public: 54 /// Provide the result type for this analysis pass. 55 using Result = PostDominatorTree; 56 57 /// Run the analysis pass over a function and produce a post dominator 58 /// tree. 59 PostDominatorTree run(Function &F, FunctionAnalysisManager &); 60 }; 61 62 /// Printer pass for the \c PostDominatorTree. 63 class PostDominatorTreePrinterPass 64 : public PassInfoMixin<PostDominatorTreePrinterPass> { 65 raw_ostream &OS; 66 67 public: 68 explicit PostDominatorTreePrinterPass(raw_ostream &OS); 69 70 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 71 }; 72 73 struct PostDominatorTreeWrapperPass : public FunctionPass { 74 static char ID; // Pass identification, replacement for typeid 75 76 PostDominatorTree DT; 77 78 PostDominatorTreeWrapperPass(); 79 getPostDomTreePostDominatorTreeWrapperPass80 PostDominatorTree &getPostDomTree() { return DT; } getPostDomTreePostDominatorTreeWrapperPass81 const PostDominatorTree &getPostDomTree() const { return DT; } 82 83 bool runOnFunction(Function &F) override; 84 85 void verifyAnalysis() const override; 86 getAnalysisUsagePostDominatorTreeWrapperPass87 void getAnalysisUsage(AnalysisUsage &AU) const override { 88 AU.setPreservesAll(); 89 } 90 releaseMemoryPostDominatorTreeWrapperPass91 void releaseMemory() override { 92 DT.releaseMemory(); 93 } 94 95 void print(raw_ostream &OS, const Module*) const override; 96 }; 97 98 FunctionPass* createPostDomTree(); 99 100 template <> struct GraphTraits<PostDominatorTree*> 101 : public GraphTraits<DomTreeNode*> { 102 static NodeRef getEntryNode(PostDominatorTree *DT) { 103 return DT->getRootNode(); 104 } 105 106 static nodes_iterator nodes_begin(PostDominatorTree *N) { 107 if (getEntryNode(N)) 108 return df_begin(getEntryNode(N)); 109 else 110 return df_end(getEntryNode(N)); 111 } 112 113 static nodes_iterator nodes_end(PostDominatorTree *N) { 114 return df_end(getEntryNode(N)); 115 } 116 }; 117 118 } // end namespace llvm 119 120 #endif // LLVM_ANALYSIS_POSTDOMINATORS_H 121