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/SmallPtrSet.h"
11 #include "llvm/ADT/SmallVector.h"
12 #include "llvm/IR/Instructions.h"
13 #include "llvm/InitializePasses.h"
14 
15 using namespace llvm;
16 
17 void PhiValues::PhiValuesCallbackVH::deleted() {
18   PV->invalidateValue(getValPtr());
19 }
20 
21 void PhiValues::PhiValuesCallbackVH::allUsesReplacedWith(Value *) {
22   // We could potentially update the cached values we have with the new value,
23   // but it's simpler to just treat the old value as invalidated.
24   PV->invalidateValue(getValPtr());
25 }
26 
27 bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA,
28                            FunctionAnalysisManager::Invalidator &) {
29   // PhiValues is invalidated if it isn't preserved.
30   auto PAC = PA.getChecker<PhiValuesAnalysis>();
31   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>());
32 }
33 
34 // The goal here is to find all of the non-phi values reachable from this phi,
35 // and to do the same for all of the phis reachable from this phi, as doing so
36 // is necessary anyway in order to get the values for this phi. We do this using
37 // Tarjan's algorithm with Nuutila's improvements to find the strongly connected
38 // components of the phi graph rooted in this phi:
39 //  * All phis in a strongly connected component will have the same reachable
40 //    non-phi values. The SCC may not be the maximal subgraph for that set of
41 //    reachable values, but finding out that isn't really necessary (it would
42 //    only reduce the amount of memory needed to store the values).
43 //  * Tarjan's algorithm completes components in a bottom-up manner, i.e. it
44 //    never completes a component before the components reachable from it have
45 //    been completed. This means that when we complete a component we have
46 //    everything we need to collect the values reachable from that component.
47 //  * We collect both the non-phi values reachable from each SCC, as that's what
48 //    we're ultimately interested in, and all of the reachable values, i.e.
49 //    including phis, as that makes invalidateValue easier.
50 void PhiValues::processPhi(const PHINode *Phi,
51                            SmallVectorImpl<const PHINode *> &Stack) {
52   // Initialize the phi with the next depth number.
53   assert(DepthMap.lookup(Phi) == 0);
54   assert(NextDepthNumber != UINT_MAX);
55   unsigned int RootDepthNumber = ++NextDepthNumber;
56   DepthMap[Phi] = RootDepthNumber;
57 
58   // Recursively process the incoming phis of this phi.
59   TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this));
60   for (Value *PhiOp : Phi->incoming_values()) {
61     if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) {
62       // Recurse if the phi has not yet been visited.
63       unsigned int OpDepthNumber = DepthMap.lookup(PhiPhiOp);
64       if (OpDepthNumber == 0) {
65         processPhi(PhiPhiOp, Stack);
66         OpDepthNumber = DepthMap.lookup(PhiPhiOp);
67         assert(OpDepthNumber != 0);
68       }
69       // If the phi did not become part of a component then this phi and that
70       // phi are part of the same component, so adjust the depth number.
71       if (!ReachableMap.count(OpDepthNumber))
72         DepthMap[Phi] = std::min(DepthMap[Phi], OpDepthNumber);
73     } else {
74       TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
75     }
76   }
77 
78   // Now that incoming phis have been handled, push this phi to the stack.
79   Stack.push_back(Phi);
80 
81   // If the depth number has not changed then we've finished collecting the phis
82   // of a strongly connected component.
83   if (DepthMap[Phi] == RootDepthNumber) {
84     // Collect the reachable values for this component. The phis of this
85     // component will be those on top of the depth stack with the same or
86     // greater depth number.
87     ConstValueSet &Reachable = ReachableMap[RootDepthNumber];
88     while (true) {
89       const PHINode *ComponentPhi = Stack.pop_back_val();
90       Reachable.insert(ComponentPhi);
91 
92       for (Value *Op : ComponentPhi->incoming_values()) {
93         if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
94           // If this phi is not part of the same component then that component
95           // is guaranteed to have been completed before this one. Therefore we
96           // can just add its reachable values to the reachable values of this
97           // component.
98           unsigned int OpDepthNumber = DepthMap[PhiOp];
99           if (OpDepthNumber != RootDepthNumber) {
100             auto It = ReachableMap.find(OpDepthNumber);
101             if (It != ReachableMap.end())
102               Reachable.insert(It->second.begin(), It->second.end());
103           }
104         } else
105           Reachable.insert(Op);
106       }
107 
108       if (Stack.empty())
109         break;
110 
111       unsigned int &ComponentDepthNumber = DepthMap[Stack.back()];
112       if (ComponentDepthNumber < RootDepthNumber)
113         break;
114 
115       ComponentDepthNumber = RootDepthNumber;
116     }
117 
118     // Filter out phis to get the non-phi reachable values.
119     ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber];
120     for (const Value *V : Reachable)
121       if (!isa<PHINode>(V))
122         NonPhi.insert(const_cast<Value *>(V));
123   }
124 }
125 
126 const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
127   unsigned int DepthNumber = DepthMap.lookup(PN);
128   if (DepthNumber == 0) {
129     SmallVector<const PHINode *, 8> Stack;
130     processPhi(PN, Stack);
131     DepthNumber = DepthMap.lookup(PN);
132     assert(Stack.empty());
133     assert(DepthNumber != 0);
134   }
135   return NonPhiReachableMap[DepthNumber];
136 }
137 
138 void PhiValues::invalidateValue(const Value *V) {
139   // Components that can reach V are invalid.
140   SmallVector<unsigned int, 8> InvalidComponents;
141   for (auto &Pair : ReachableMap)
142     if (Pair.second.count(V))
143       InvalidComponents.push_back(Pair.first);
144 
145   for (unsigned int N : InvalidComponents) {
146     for (const Value *V : ReachableMap[N])
147       if (const PHINode *PN = dyn_cast<PHINode>(V))
148         DepthMap.erase(PN);
149     NonPhiReachableMap.erase(N);
150     ReachableMap.erase(N);
151   }
152   // This value is no longer tracked
153   auto It = TrackedValues.find_as(V);
154   if (It != TrackedValues.end())
155     TrackedValues.erase(It);
156 }
157 
158 void PhiValues::releaseMemory() {
159   DepthMap.clear();
160   NonPhiReachableMap.clear();
161   ReachableMap.clear();
162 }
163 
164 void PhiValues::print(raw_ostream &OS) const {
165   // Iterate through the phi nodes of the function rather than iterating through
166   // DepthMap in order to get predictable ordering.
167   for (const BasicBlock &BB : F) {
168     for (const PHINode &PN : BB.phis()) {
169       OS << "PHI ";
170       PN.printAsOperand(OS, false);
171       OS << " has values:\n";
172       unsigned int N = DepthMap.lookup(&PN);
173       auto It = NonPhiReachableMap.find(N);
174       if (It == NonPhiReachableMap.end())
175         OS << "  UNKNOWN\n";
176       else if (It->second.empty())
177         OS << "  NONE\n";
178       else
179         for (Value *V : It->second)
180           // Printing of an instruction prints two spaces at the start, so
181           // handle instructions and everything else slightly differently in
182           // order to get consistent indenting.
183           if (Instruction *I = dyn_cast<Instruction>(V))
184             OS << *I << "\n";
185           else
186             OS << "  " << *V << "\n";
187     }
188   }
189 }
190 
191 AnalysisKey PhiValuesAnalysis::Key;
192 PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
193   return PhiValues(F);
194 }
195 
196 PreservedAnalyses PhiValuesPrinterPass::run(Function &F,
197                                             FunctionAnalysisManager &AM) {
198   OS << "PHI Values for function: " << F.getName() << "\n";
199   PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F);
200   for (const BasicBlock &BB : F)
201     for (const PHINode &PN : BB.phis())
202       PI.getValuesForPhi(&PN);
203   PI.print(OS);
204   return PreservedAnalyses::all();
205 }
206 
207 PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {
208   initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry());
209 }
210 
211 bool PhiValuesWrapperPass::runOnFunction(Function &F) {
212   Result.reset(new PhiValues(F));
213   return false;
214 }
215 
216 void PhiValuesWrapperPass::releaseMemory() {
217   Result->releaseMemory();
218 }
219 
220 void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
221   AU.setPreservesAll();
222 }
223 
224 char PhiValuesWrapperPass::ID = 0;
225 
226 INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
227                 true)
228