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