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(Func&: 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 static bool isRequired() { return true; }
73};
74
75struct PostDominatorTreeWrapperPass : public FunctionPass {
76 static char ID; // Pass identification, replacement for typeid
77
78 PostDominatorTree DT;
79
80 PostDominatorTreeWrapperPass();
81
82 PostDominatorTree &getPostDomTree() { return DT; }
83 const PostDominatorTree &getPostDomTree() const { return DT; }
84
85 bool runOnFunction(Function &F) override;
86
87 void verifyAnalysis() const override;
88
89 void getAnalysisUsage(AnalysisUsage &AU) const override {
90 AU.setPreservesAll();
91 }
92
93 void releaseMemory() override { DT.reset(); }
94
95 void print(raw_ostream &OS, const Module*) const override;
96};
97
98FunctionPass* createPostDomTree();
99
100template <> 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 return df_begin(G: getEntryNode(DT: N));
108 }
109
110 static nodes_iterator nodes_end(PostDominatorTree *N) {
111 return df_end(G: getEntryNode(DT: N));
112 }
113};
114
115} // end namespace llvm
116
117#endif // LLVM_ANALYSIS_POSTDOMINATORS_H
118