LLVM 19.0.0git
PhiValues.cpp
Go to the documentation of this file.
1//===- PhiValues.cpp - Phi Value Analysis ---------------------------------===//
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
13
14using namespace llvm;
15
16void PhiValues::PhiValuesCallbackVH::deleted() {
17 PV->invalidateValue(getValPtr());
18}
19
20void PhiValues::PhiValuesCallbackVH::allUsesReplacedWith(Value *) {
21 // We could potentially update the cached values we have with the new value,
22 // but it's simpler to just treat the old value as invalidated.
23 PV->invalidateValue(getValPtr());
24}
25
28 // PhiValues is invalidated if it isn't preserved.
29 auto PAC = PA.getChecker<PhiValuesAnalysis>();
30 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>());
31}
32
33// The goal here is to find all of the non-phi values reachable from this phi,
34// and to do the same for all of the phis reachable from this phi, as doing so
35// is necessary anyway in order to get the values for this phi. We do this using
36// Tarjan's algorithm with Nuutila's improvements to find the strongly connected
37// components of the phi graph rooted in this phi:
38// * All phis in a strongly connected component will have the same reachable
39// non-phi values. The SCC may not be the maximal subgraph for that set of
40// reachable values, but finding out that isn't really necessary (it would
41// only reduce the amount of memory needed to store the values).
42// * Tarjan's algorithm completes components in a bottom-up manner, i.e. it
43// never completes a component before the components reachable from it have
44// been completed. This means that when we complete a component we have
45// everything we need to collect the values reachable from that component.
46// * We collect both the non-phi values reachable from each SCC, as that's what
47// we're ultimately interested in, and all of the reachable values, i.e.
48// including phis, as that makes invalidateValue easier.
49void PhiValues::processPhi(const PHINode *Phi,
51 // Initialize the phi with the next depth number.
52 assert(DepthMap.lookup(Phi) == 0);
53 assert(NextDepthNumber != UINT_MAX);
54 unsigned int RootDepthNumber = ++NextDepthNumber;
55 DepthMap[Phi] = RootDepthNumber;
56
57 // Recursively process the incoming phis of this phi.
58 TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this));
59 for (Value *PhiOp : Phi->incoming_values()) {
60 if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) {
61 // Recurse if the phi has not yet been visited.
62 unsigned int OpDepthNumber = DepthMap.lookup(PhiPhiOp);
63 if (OpDepthNumber == 0) {
64 processPhi(PhiPhiOp, Stack);
65 OpDepthNumber = DepthMap.lookup(PhiPhiOp);
66 assert(OpDepthNumber != 0);
67 }
68 // If the phi did not become part of a component then this phi and that
69 // phi are part of the same component, so adjust the depth number.
70 if (!ReachableMap.count(OpDepthNumber))
71 DepthMap[Phi] = std::min(DepthMap[Phi], OpDepthNumber);
72 } else {
73 TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
74 }
75 }
76
77 // Now that incoming phis have been handled, push this phi to the stack.
78 Stack.push_back(Phi);
79
80 // If the depth number has not changed then we've finished collecting the phis
81 // of a strongly connected component.
82 if (DepthMap[Phi] == RootDepthNumber) {
83 // Collect the reachable values for this component. The phis of this
84 // component will be those on top of the depth stack with the same or
85 // greater depth number.
86 ConstValueSet &Reachable = ReachableMap[RootDepthNumber];
87 while (true) {
88 const PHINode *ComponentPhi = Stack.pop_back_val();
89 Reachable.insert(ComponentPhi);
90
91 for (Value *Op : ComponentPhi->incoming_values()) {
92 if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
93 // If this phi is not part of the same component then that component
94 // is guaranteed to have been completed before this one. Therefore we
95 // can just add its reachable values to the reachable values of this
96 // component.
97 unsigned int OpDepthNumber = DepthMap[PhiOp];
98 if (OpDepthNumber != RootDepthNumber) {
99 auto It = ReachableMap.find(OpDepthNumber);
100 if (It != ReachableMap.end())
101 Reachable.insert(It->second.begin(), It->second.end());
102 }
103 } else
104 Reachable.insert(Op);
105 }
106
107 if (Stack.empty())
108 break;
109
110 unsigned int &ComponentDepthNumber = DepthMap[Stack.back()];
111 if (ComponentDepthNumber < RootDepthNumber)
112 break;
113
114 ComponentDepthNumber = RootDepthNumber;
115 }
116
117 // Filter out phis to get the non-phi reachable values.
118 ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber];
119 for (const Value *V : Reachable)
120 if (!isa<PHINode>(V))
121 NonPhi.insert(const_cast<Value *>(V));
122 }
123}
124
126 unsigned int DepthNumber = DepthMap.lookup(PN);
127 if (DepthNumber == 0) {
129 processPhi(PN, Stack);
130 DepthNumber = DepthMap.lookup(PN);
131 assert(Stack.empty());
132 assert(DepthNumber != 0);
133 }
134 return NonPhiReachableMap[DepthNumber];
135}
136
138 // Components that can reach V are invalid.
139 SmallVector<unsigned int, 8> InvalidComponents;
140 for (auto &Pair : ReachableMap)
141 if (Pair.second.count(V))
142 InvalidComponents.push_back(Pair.first);
143
144 for (unsigned int N : InvalidComponents) {
145 for (const Value *V : ReachableMap[N])
146 if (const PHINode *PN = dyn_cast<PHINode>(V))
147 DepthMap.erase(PN);
148 NonPhiReachableMap.erase(N);
149 ReachableMap.erase(N);
150 }
151 // This value is no longer tracked
152 auto It = TrackedValues.find_as(V);
153 if (It != TrackedValues.end())
154 TrackedValues.erase(It);
155}
156
158 DepthMap.clear();
159 NonPhiReachableMap.clear();
160 ReachableMap.clear();
161}
162
164 // Iterate through the phi nodes of the function rather than iterating through
165 // DepthMap in order to get predictable ordering.
166 for (const BasicBlock &BB : F) {
167 for (const PHINode &PN : BB.phis()) {
168 OS << "PHI ";
169 PN.printAsOperand(OS, false);
170 OS << " has values:\n";
171 unsigned int N = DepthMap.lookup(&PN);
172 auto It = NonPhiReachableMap.find(N);
173 if (It == NonPhiReachableMap.end())
174 OS << " UNKNOWN\n";
175 else if (It->second.empty())
176 OS << " NONE\n";
177 else
178 for (Value *V : It->second)
179 // Printing of an instruction prints two spaces at the start, so
180 // handle instructions and everything else slightly differently in
181 // order to get consistent indenting.
182 if (Instruction *I = dyn_cast<Instruction>(V))
183 OS << *I << "\n";
184 else
185 OS << " " << *V << "\n";
186 }
187 }
188}
189
190AnalysisKey PhiValuesAnalysis::Key;
192 return PhiValues(F);
193}
194
197 OS << "PHI Values for function: " << F.getName() << "\n";
199 for (const BasicBlock &BB : F)
200 for (const PHINode &PN : BB.phis())
201 PI.getValuesForPhi(&PN);
202 PI.print(OS);
203 return PreservedAnalyses::all();
204}
205
208}
209
211 Result.reset(new PhiValues(F));
212 return false;
213}
214
216 Result->releaseMemory();
217}
218
220 AU.setPreservesAll();
221}
222
224
225INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
226 true)
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallVector class.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: Analysis.h:47
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:387
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
This class represents an Operation in the Expression.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
op_range incoming_values()
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
The analysis pass which yields a PhiValues.
Definition: PhiValues.h:115
PhiValues run(Function &F, FunctionAnalysisManager &)
Definition: PhiValues.cpp:191
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PhiValues.cpp:195
Wrapper pass for the legacy pass manager.
Definition: PhiValues.h:139
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: PhiValues.cpp:215
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: PhiValues.cpp:210
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: PhiValues.cpp:219
Class for calculating and caching the underlying values of phis in a function.
Definition: PhiValues.h:40
void invalidateValue(const Value *V)
Notify PhiValues that the cached information using V is no longer valid.
Definition: PhiValues.cpp:137
const ValueSet & getValuesForPhi(const PHINode *PN)
Get the underlying values of a phi.
Definition: PhiValues.cpp:125
SmallSetVector< Value *, 4 > ValueSet
Definition: PhiValues.h:42
bool invalidate(Function &, const PreservedAnalyses &, FunctionAnalysisManager::Invalidator &)
Handle invalidation events in the new pass manager.
Definition: PhiValues.cpp:26
void releaseMemory()
Free the memory used by this class.
Definition: PhiValues.cpp:157
void print(raw_ostream &OS) const
Print out the values currently in the cache.
Definition: PhiValues.cpp:163
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void initializePhiValuesWrapperPassPass(PassRegistry &)
#define N
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26