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