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
21namespace llvm {
22
23class Function;
24class raw_ostream;
25
26/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
27/// compute the post-dominator tree.
28class PostDominatorTree : public PostDomTreeBase<BasicBlock> {
29public:
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 // 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.
47class PostDominatorTreeAnalysis
48 : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
49 friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
50
51 static AnalysisKey Key;
52
53public:
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.
63class PostDominatorTreePrinterPass
64 : public PassInfoMixin<PostDominatorTreePrinterPass> {
65 raw_ostream &OS;
66
67public:
68 explicit PostDominatorTreePrinterPass(raw_ostream &OS);
69
70 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
71};
72
73struct PostDominatorTreeWrapperPass : public FunctionPass {
74 static char ID; // Pass identification, replacement for typeid
75
76 PostDominatorTree DT;
77
78 PostDominatorTreeWrapperPass();
79
80 PostDominatorTree &getPostDomTree() { return DT; }
81 const PostDominatorTree &getPostDomTree() const { return DT; }
82
83 bool runOnFunction(Function &F) override;
84
85 void verifyAnalysis() const override;
86
87 void getAnalysisUsage(AnalysisUsage &AU) const override {
88 AU.setPreservesAll();
89 }
90
91 void releaseMemory() override { DT.reset(); }
92
93 void print(raw_ostream &OS, const Module*) const override;
94};
95
96FunctionPass* createPostDomTree();
97
98template <> struct GraphTraits<PostDominatorTree*>
99 : public GraphTraits<DomTreeNode*> {
100 static NodeRef getEntryNode(PostDominatorTree *DT) {
101 return DT->getRootNode();
102 }
103
104 static nodes_iterator nodes_begin(PostDominatorTree *N) {
105 return df_begin(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

source code of llvm/include/llvm/Analysis/PostDominators.h