llvm/Analysis/PostDominators.h

0001 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation --*- C++ -*-=//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file exposes interfaces to post dominance information.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H
0014 #define LLVM_ANALYSIS_POSTDOMINATORS_H
0015
0016 #include "llvm/ADT/DepthFirstIterator.h"
0017 #include "llvm/IR/Dominators.h"
0018 #include "llvm/IR/PassManager.h"
0019 #include "llvm/Pass.h"
0020
0021 namespace llvm {
0022
0023 class Function;
0024 class raw_ostream;
0025
0026 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
0027 /// compute the post-dominator tree.
0028 class PostDominatorTree : public PostDomTreeBase<BasicBlock> {
0029 public:
0030   using Base = PostDomTreeBase<BasicBlock>;
0031
0032   PostDominatorTree() = default;
0033   explicit PostDominatorTree(Function &F) { recalculate(F); }
0034   /// Handle invalidation explicitly.
0035   bool invalidate(Function &F, const PreservedAnalyses &PA,
0036                   FunctionAnalysisManager::Invalidator &);
0037
0038   // Ensure base-class overloads are visible.
0039   using Base::dominates;
0040
0041   /// Return true if \p I1 dominates \p I2. This checks if \p I2 comes before
0042   /// \p I1 if they belongs to the same basic block.
0043   bool dominates(const Instruction *I1, const Instruction *I2) const;
0044 };
0045
0046 /// Analysis pass which computes a \c PostDominatorTree.
0047 class PostDominatorTreeAnalysis
0048     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
0049   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
0050
0051   static AnalysisKey Key;
0052
0053 public:
0054   /// Provide the result type for this analysis pass.
0055   using Result = PostDominatorTree;
0056
0057   /// Run the analysis pass over a function and produce a post dominator
0058   ///        tree.
0059   PostDominatorTree run(Function &F, FunctionAnalysisManager &);
0060 };
0061
0062 /// Printer pass for the \c PostDominatorTree.
0063 class PostDominatorTreePrinterPass
0064     : public PassInfoMixin<PostDominatorTreePrinterPass> {
0065   raw_ostream &OS;
0066
0067 public:
0068   explicit PostDominatorTreePrinterPass(raw_ostream &OS);
0069
0070   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0071
0072   static bool isRequired() { return true; }
0073 };
0074
0075 struct PostDominatorTreeWrapperPass : public FunctionPass {
0076   static char ID; // Pass identification, replacement for typeid
0077
0078   PostDominatorTree DT;
0079
0080   PostDominatorTreeWrapperPass();
0081
0082   PostDominatorTree &getPostDomTree() { return DT; }
0083   const PostDominatorTree &getPostDomTree() const { return DT; }
0084
0085   bool runOnFunction(Function &F) override;
0086
0087   void verifyAnalysis() const override;
0088
0089   void getAnalysisUsage(AnalysisUsage &AU) const override {
0090     AU.setPreservesAll();
0091   }
0092
0093   void releaseMemory() override { DT.reset(); }
0094
0095   void print(raw_ostream &OS, const Module*) const override;
0096 };
0097
0098 FunctionPass* createPostDomTree();
0099
0100 template <> struct GraphTraits<PostDominatorTree*>
0101   : public GraphTraits<DomTreeNode*> {
0102   static NodeRef getEntryNode(PostDominatorTree *DT) {
0103     return DT->getRootNode();
0104   }
0105
0106   static nodes_iterator nodes_begin(PostDominatorTree *N) {
0107     return df_begin(getEntryNode(N));
0108   }
0109
0110   static nodes_iterator nodes_end(PostDominatorTree *N) {
0111     return df_end(getEntryNode(N));
0112   }
0113 };
0114
0115 } // end namespace llvm
0116
0117 #endif // LLVM_ANALYSIS_POSTDOMINATORS_H