1 | //===- CallGraphSCCPass.h - Pass that operates BU on call graph -*- 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 defines the CallGraphSCCPass class, which is used for passes which |
10 | // are implemented as bottom-up traversals on the call graph. Because there may |
11 | // be cycles in the call graph, passes of this type operate on the call-graph in |
12 | // SCC order: that is, they process function bottom-up, except for recursive |
13 | // functions, which they process all at once. |
14 | // |
15 | // These passes are inherently interprocedural, and are required to keep the |
16 | // call graph up-to-date if they do anything which could modify it. |
17 | // |
18 | //===----------------------------------------------------------------------===// |
19 | |
20 | #ifndef LLVM_ANALYSIS_CALLGRAPHSCCPASS_H |
21 | #define LLVM_ANALYSIS_CALLGRAPHSCCPASS_H |
22 | |
23 | #include "llvm/ADT/ArrayRef.h" |
24 | #include "llvm/Pass.h" |
25 | #include <vector> |
26 | |
27 | namespace llvm { |
28 | |
29 | class CallGraph; |
30 | class CallGraphNode; |
31 | class CallGraphSCC; |
32 | class PMStack; |
33 | |
34 | class CallGraphSCCPass : public Pass { |
35 | public: |
36 | explicit CallGraphSCCPass(char &pid) : Pass(PT_CallGraphSCC, pid) {} |
37 | |
38 | /// createPrinterPass - Get a pass that prints the Module |
39 | /// corresponding to a CallGraph. |
40 | Pass *createPrinterPass(raw_ostream &OS, |
41 | const std::string &Banner) const override; |
42 | |
43 | using llvm::Pass::doInitialization; |
44 | using llvm::Pass::doFinalization; |
45 | |
46 | /// doInitialization - This method is called before the SCC's of the program |
47 | /// has been processed, allowing the pass to do initialization as necessary. |
48 | virtual bool doInitialization(CallGraph &CG) { |
49 | return false; |
50 | } |
51 | |
52 | /// runOnSCC - This method should be implemented by the subclass to perform |
53 | /// whatever action is necessary for the specified SCC. Note that |
54 | /// non-recursive (or only self-recursive) functions will have an SCC size of |
55 | /// 1, where recursive portions of the call graph will have SCC size > 1. |
56 | /// |
57 | /// SCC passes that add or delete functions to the SCC are required to update |
58 | /// the SCC list, otherwise stale pointers may be dereferenced. |
59 | virtual bool runOnSCC(CallGraphSCC &SCC) = 0; |
60 | |
61 | /// doFinalization - This method is called after the SCC's of the program has |
62 | /// been processed, allowing the pass to do final cleanup as necessary. |
63 | virtual bool doFinalization(CallGraph &CG) { |
64 | return false; |
65 | } |
66 | |
67 | /// Assign pass manager to manager this pass |
68 | void assignPassManager(PMStack &PMS, PassManagerType PMT) override; |
69 | |
70 | /// Return what kind of Pass Manager can manage this pass. |
71 | PassManagerType getPotentialPassManagerType() const override { |
72 | return PMT_CallGraphPassManager; |
73 | } |
74 | |
75 | /// getAnalysisUsage - For this class, we declare that we require and preserve |
76 | /// the call graph. If the derived class implements this method, it should |
77 | /// always explicitly call the implementation here. |
78 | void getAnalysisUsage(AnalysisUsage &Info) const override; |
79 | |
80 | protected: |
81 | /// Optional passes call this function to check whether the pass should be |
82 | /// skipped. This is the case when optimization bisect is over the limit. |
83 | bool skipSCC(CallGraphSCC &SCC) const; |
84 | }; |
85 | |
86 | /// CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on. |
87 | class CallGraphSCC { |
88 | const CallGraph &CG; // The call graph for this SCC. |
89 | void *Context; // The CGPassManager object that is vending this. |
90 | std::vector<CallGraphNode *> Nodes; |
91 | |
92 | public: |
93 | CallGraphSCC(CallGraph &cg, void *context) : CG(cg), Context(context) {} |
94 | |
95 | void initialize(ArrayRef<CallGraphNode *> NewNodes) { |
96 | Nodes.assign(first: NewNodes.begin(), last: NewNodes.end()); |
97 | } |
98 | |
99 | bool isSingular() const { return Nodes.size() == 1; } |
100 | unsigned size() const { return Nodes.size(); } |
101 | |
102 | /// ReplaceNode - This informs the SCC and the pass manager that the specified |
103 | /// Old node has been deleted, and New is to be used in its place. |
104 | void ReplaceNode(CallGraphNode *Old, CallGraphNode *New); |
105 | |
106 | /// DeleteNode - This informs the SCC and the pass manager that the specified |
107 | /// Old node has been deleted. |
108 | void DeleteNode(CallGraphNode *Old); |
109 | |
110 | using iterator = std::vector<CallGraphNode *>::const_iterator; |
111 | |
112 | iterator begin() const { return Nodes.begin(); } |
113 | iterator end() const { return Nodes.end(); } |
114 | |
115 | const CallGraph &getCallGraph() { return CG; } |
116 | }; |
117 | |
118 | void initializeDummyCGSCCPassPass(PassRegistry &); |
119 | |
120 | /// This pass is required by interprocedural register allocation. It forces |
121 | /// codegen to follow bottom up order on call graph. |
122 | class DummyCGSCCPass : public CallGraphSCCPass { |
123 | public: |
124 | static char ID; |
125 | |
126 | DummyCGSCCPass() : CallGraphSCCPass(ID) { |
127 | PassRegistry &Registry = *PassRegistry::getPassRegistry(); |
128 | initializeDummyCGSCCPassPass(Registry); |
129 | } |
130 | |
131 | bool runOnSCC(CallGraphSCC &SCC) override { return false; } |
132 | |
133 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
134 | AU.setPreservesAll(); |
135 | } |
136 | }; |
137 | |
138 | } // end namespace llvm |
139 | |
140 | #endif // LLVM_ANALYSIS_CALLGRAPHSCCPASS_H |
141 | |