1 | //===- PhiValues.h - Phi Value Analysis -------------------------*- 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 PhiValues class, and associated passes, which can be |
10 | // used to find the underlying values of the phis in a function, i.e. the |
11 | // non-phi values that can be found by traversing the phi graph. |
12 | // |
13 | // This information is computed lazily and cached. If new phis are added to the |
14 | // function they are handled correctly, but if an existing phi has its operands |
15 | // modified PhiValues has to be notified by calling invalidateValue. |
16 | // |
17 | //===----------------------------------------------------------------------===// |
18 | |
19 | #ifndef LLVM_ANALYSIS_PHIVALUES_H |
20 | #define LLVM_ANALYSIS_PHIVALUES_H |
21 | |
22 | #include "llvm/ADT/DenseMap.h" |
23 | #include "llvm/ADT/DenseSet.h" |
24 | #include "llvm/ADT/SetVector.h" |
25 | #include "llvm/IR/PassManager.h" |
26 | #include "llvm/IR/ValueHandle.h" |
27 | #include "llvm/Pass.h" |
28 | |
29 | namespace llvm { |
30 | |
31 | class Value; |
32 | class PHINode; |
33 | class Function; |
34 | |
35 | /// Class for calculating and caching the underlying values of phis in a |
36 | /// function. |
37 | /// |
38 | /// Initially the PhiValues is empty, and gets incrementally populated whenever |
39 | /// it is queried. |
40 | class PhiValues { |
41 | public: |
42 | using ValueSet = SmallSetVector<Value *, 4>; |
43 | |
44 | /// Construct an empty PhiValues. |
45 | PhiValues(const Function &F) : F(F) {} |
46 | |
47 | /// Get the underlying values of a phi. |
48 | /// |
49 | /// This returns the cached value if PN has previously been processed, |
50 | /// otherwise it processes it first. |
51 | const ValueSet &getValuesForPhi(const PHINode *PN); |
52 | |
53 | /// Notify PhiValues that the cached information using V is no longer valid |
54 | /// |
55 | /// Whenever a phi has its operands modified the cached values for that phi |
56 | /// (and the phis that use that phi) become invalid. A user of PhiValues has |
57 | /// to notify it of this by calling invalidateValue on either the operand or |
58 | /// the phi, which will then clear the relevant cached information. |
59 | void invalidateValue(const Value *V); |
60 | |
61 | /// Free the memory used by this class. |
62 | void releaseMemory(); |
63 | |
64 | /// Print out the values currently in the cache. |
65 | void print(raw_ostream &OS) const; |
66 | |
67 | /// Handle invalidation events in the new pass manager. |
68 | bool invalidate(Function &, const PreservedAnalyses &, |
69 | FunctionAnalysisManager::Invalidator &); |
70 | |
71 | private: |
72 | using ConstValueSet = SmallSetVector<const Value *, 4>; |
73 | |
74 | /// The next depth number to be used by processPhi. |
75 | unsigned int NextDepthNumber = 1; |
76 | |
77 | /// Depth numbers of phis. Phis with the same depth number are part of the |
78 | /// same strongly connected component. |
79 | DenseMap<const PHINode *, unsigned int> DepthMap; |
80 | |
81 | /// Non-phi values reachable from each component. |
82 | DenseMap<unsigned int, ValueSet> NonPhiReachableMap; |
83 | |
84 | /// All values reachable from each component. |
85 | DenseMap<unsigned int, ConstValueSet> ReachableMap; |
86 | |
87 | /// A CallbackVH to notify PhiValues when a value is deleted or replaced, so |
88 | /// that the cached information for that value can be cleared to avoid |
89 | /// dangling pointers to invalid values. |
90 | class PhiValuesCallbackVH final : public CallbackVH { |
91 | PhiValues *PV; |
92 | void deleted() override; |
93 | void allUsesReplacedWith(Value *New) override; |
94 | |
95 | public: |
96 | PhiValuesCallbackVH(Value *V, PhiValues *PV = nullptr) |
97 | : CallbackVH(V), PV(PV) {} |
98 | }; |
99 | |
100 | /// A set of callbacks to the values that processPhi has seen. |
101 | DenseSet<PhiValuesCallbackVH, DenseMapInfo<Value *>> TrackedValues; |
102 | |
103 | /// The function that the PhiValues is for. |
104 | const Function &F; |
105 | |
106 | /// Process a phi so that its entries in the depth and reachable maps are |
107 | /// fully populated. |
108 | void processPhi(const PHINode *PN, SmallVectorImpl<const PHINode *> &Stack); |
109 | }; |
110 | |
111 | /// The analysis pass which yields a PhiValues |
112 | /// |
113 | /// The analysis does nothing by itself, and just returns an empty PhiValues |
114 | /// which will get filled in as it's used. |
115 | class PhiValuesAnalysis : public AnalysisInfoMixin<PhiValuesAnalysis> { |
116 | friend AnalysisInfoMixin<PhiValuesAnalysis>; |
117 | static AnalysisKey Key; |
118 | |
119 | public: |
120 | using Result = PhiValues; |
121 | PhiValues run(Function &F, FunctionAnalysisManager &); |
122 | }; |
123 | |
124 | /// A pass for printing the PhiValues for a function. |
125 | /// |
126 | /// This pass doesn't print whatever information the PhiValues happens to hold, |
127 | /// but instead first uses the PhiValues to analyze all the phis in the function |
128 | /// so the complete information is printed. |
129 | class PhiValuesPrinterPass : public PassInfoMixin<PhiValuesPrinterPass> { |
130 | raw_ostream &OS; |
131 | |
132 | public: |
133 | explicit PhiValuesPrinterPass(raw_ostream &OS) : OS(OS) {} |
134 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
135 | static bool isRequired() { return true; } |
136 | }; |
137 | |
138 | /// Wrapper pass for the legacy pass manager |
139 | class PhiValuesWrapperPass : public FunctionPass { |
140 | std::unique_ptr<PhiValues> Result; |
141 | |
142 | public: |
143 | static char ID; |
144 | PhiValuesWrapperPass(); |
145 | |
146 | PhiValues &getResult() { return *Result; } |
147 | const PhiValues &getResult() const { return *Result; } |
148 | |
149 | bool runOnFunction(Function &F) override; |
150 | void releaseMemory() override; |
151 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
152 | }; |
153 | |
154 | } // namespace llvm |
155 | |
156 | #endif |
157 | |