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
9#include "llvm/Analysis/PhiValues.h"
10#include "llvm/ADT/SmallVector.h"
11#include "llvm/IR/Instructions.h"
12#include "llvm/InitializePasses.h"
13
14using namespace llvm;
15
16void PhiValues::PhiValuesCallbackVH::deleted() {
17 PV->invalidateValue(V: 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(V: getValPtr());
24}
25
26bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA,
27 FunctionAnalysisManager::Invalidator &) {
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,
50 SmallVectorImpl<const PHINode *> &Stack) {
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(V: PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this));
59 for (Value *PhiOp : Phi->incoming_values()) {
60 if (PHINode *PhiPhiOp = dyn_cast<PHINode>(Val: PhiOp)) {
61 // Recurse if the phi has not yet been visited.
62 unsigned int OpDepthNumber = DepthMap.lookup(Val: PhiPhiOp);
63 if (OpDepthNumber == 0) {
64 processPhi(Phi: PhiPhiOp, Stack);
65 OpDepthNumber = DepthMap.lookup(Val: 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(Val: OpDepthNumber)) {
71 unsigned &Depth = DepthMap[Phi];
72 Depth = std::min(a: Depth, b: OpDepthNumber);
73 }
74 } else {
75 TrackedValues.insert(V: PhiValuesCallbackVH(PhiOp, this));
76 }
77 }
78
79 // Now that incoming phis have been handled, push this phi to the stack.
80 Stack.push_back(Elt: Phi);
81
82 // If the depth number has not changed then we've finished collecting the phis
83 // of a strongly connected component.
84 if (DepthMap[Phi] == RootDepthNumber) {
85 // Collect the reachable values for this component. The phis of this
86 // component will be those on top of the depth stack with the same or
87 // greater depth number.
88 ConstValueSet &Reachable = ReachableMap[RootDepthNumber];
89 while (true) {
90 const PHINode *ComponentPhi = Stack.pop_back_val();
91 Reachable.insert(X: ComponentPhi);
92
93 for (Value *Op : ComponentPhi->incoming_values()) {
94 if (PHINode *PhiOp = dyn_cast<PHINode>(Val: Op)) {
95 // If this phi is not part of the same component then that component
96 // is guaranteed to have been completed before this one. Therefore we
97 // can just add its reachable values to the reachable values of this
98 // component.
99 unsigned int OpDepthNumber = DepthMap[PhiOp];
100 if (OpDepthNumber != RootDepthNumber) {
101 auto It = ReachableMap.find(Val: OpDepthNumber);
102 if (It != ReachableMap.end())
103 Reachable.insert_range(R&: It->second);
104 }
105 } else
106 Reachable.insert(X: Op);
107 }
108
109 if (Stack.empty())
110 break;
111
112 unsigned int &ComponentDepthNumber = DepthMap[Stack.back()];
113 if (ComponentDepthNumber < RootDepthNumber)
114 break;
115
116 ComponentDepthNumber = RootDepthNumber;
117 }
118
119 // Filter out phis to get the non-phi reachable values.
120 ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber];
121 for (const Value *V : Reachable)
122 if (!isa<PHINode>(Val: V))
123 NonPhi.insert(X: const_cast<Value *>(V));
124 }
125}
126
127const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
128 unsigned int DepthNumber = DepthMap.lookup(Val: PN);
129 if (DepthNumber == 0) {
130 SmallVector<const PHINode *, 8> Stack;
131 processPhi(Phi: PN, Stack);
132 DepthNumber = DepthMap.lookup(Val: PN);
133 assert(Stack.empty());
134 assert(DepthNumber != 0);
135 }
136 return NonPhiReachableMap[DepthNumber];
137}
138
139void PhiValues::invalidateValue(const Value *V) {
140 // Components that can reach V are invalid.
141 SmallVector<unsigned int, 8> InvalidComponents;
142 for (auto &Pair : ReachableMap)
143 if (Pair.second.count(key: V))
144 InvalidComponents.push_back(Elt: Pair.first);
145
146 for (unsigned int N : InvalidComponents) {
147 for (const Value *V : ReachableMap[N])
148 if (const PHINode *PN = dyn_cast<PHINode>(Val: V))
149 DepthMap.erase(Val: PN);
150 NonPhiReachableMap.erase(Val: N);
151 ReachableMap.erase(Val: N);
152 }
153 // This value is no longer tracked
154 auto It = TrackedValues.find_as(Val: V);
155 if (It != TrackedValues.end())
156 TrackedValues.erase(I: It);
157}
158
159void PhiValues::releaseMemory() {
160 DepthMap.clear();
161 NonPhiReachableMap.clear();
162 ReachableMap.clear();
163}
164
165void PhiValues::print(raw_ostream &OS) const {
166 // Iterate through the phi nodes of the function rather than iterating through
167 // DepthMap in order to get predictable ordering.
168 for (const BasicBlock &BB : F) {
169 for (const PHINode &PN : BB.phis()) {
170 OS << "PHI ";
171 PN.printAsOperand(O&: OS, PrintType: false);
172 OS << " has values:\n";
173 unsigned int N = DepthMap.lookup(Val: &PN);
174 auto It = NonPhiReachableMap.find(Val: N);
175 if (It == NonPhiReachableMap.end())
176 OS << " UNKNOWN\n";
177 else if (It->second.empty())
178 OS << " NONE\n";
179 else
180 for (Value *V : It->second)
181 // Printing of an instruction prints two spaces at the start, so
182 // handle instructions and everything else slightly differently in
183 // order to get consistent indenting.
184 if (Instruction *I = dyn_cast<Instruction>(Val: V))
185 OS << *I << "\n";
186 else
187 OS << " " << *V << "\n";
188 }
189 }
190}
191
192AnalysisKey PhiValuesAnalysis::Key;
193PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
194 return PhiValues(F);
195}
196
197PreservedAnalyses PhiValuesPrinterPass::run(Function &F,
198 FunctionAnalysisManager &AM) {
199 OS << "PHI Values for function: " << F.getName() << "\n";
200 PhiValues &PI = AM.getResult<PhiValuesAnalysis>(IR&: F);
201 for (const BasicBlock &BB : F)
202 for (const PHINode &PN : BB.phis())
203 PI.getValuesForPhi(PN: &PN);
204 PI.print(OS);
205 return PreservedAnalyses::all();
206}
207
208PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {}
209
210bool PhiValuesWrapperPass::runOnFunction(Function &F) {
211 Result.reset(p: new PhiValues(F));
212 return false;
213}
214
215void PhiValuesWrapperPass::releaseMemory() {
216 Result->releaseMemory();
217}
218
219void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
220 AU.setPreservesAll();
221}
222
223char PhiValuesWrapperPass::ID = 0;
224
225INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
226 true)
227