Line data Source code
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 :
17 1688 : void PhiValues::PhiValuesCallbackVH::deleted() {
18 1688 : PV->invalidateValue(getValPtr());
19 1688 : }
20 :
21 1257 : 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 1257 : PV->invalidateValue(getValPtr());
25 1257 : }
26 :
27 227 : 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 227 : 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 49673 : void PhiValues::processPhi(const PHINode *Phi,
51 : SmallVector<const PHINode *, 8> &Stack) {
52 : // Initialize the phi with the next depth number.
53 : assert(DepthMap.lookup(Phi) == 0);
54 : assert(NextDepthNumber != UINT_MAX);
55 49673 : unsigned int DepthNumber = ++NextDepthNumber;
56 49673 : DepthMap[Phi] = DepthNumber;
57 :
58 : // Recursively process the incoming phis of this phi.
59 49673 : TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this));
60 211362 : 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 6482 : if (DepthMap.lookup(PhiPhiOp) == 0)
64 3522 : processPhi(PhiPhiOp, Stack);
65 : assert(DepthMap.lookup(PhiPhiOp) != 0);
66 : // If the phi did not become part of a component then this phi and that
67 : // phi are part of the same component, so adjust the depth number.
68 10034 : if (!ReachableMap.count(DepthMap[PhiPhiOp]))
69 5860 : DepthMap[Phi] = std::min(DepthMap[Phi], DepthMap[PhiPhiOp]);
70 : } else {
71 105534 : TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
72 : }
73 : }
74 :
75 : // Now that incoming phis have been handled, push this phi to the stack.
76 49673 : Stack.push_back(Phi);
77 :
78 : // If the depth number has not changed then we've finished collecting the phis
79 : // of a strongly connected component.
80 49673 : if (DepthMap[Phi] == DepthNumber) {
81 : // Collect the reachable values for this component. The phis of this
82 : // component will be those on top of the depth stach with the same or
83 : // greater depth number.
84 : ConstValueSet Reachable;
85 147833 : while (!Stack.empty() && DepthMap[Stack.back()] >= DepthNumber) {
86 49673 : const PHINode *ComponentPhi = Stack.pop_back_val();
87 49673 : Reachable.insert(ComponentPhi);
88 49673 : DepthMap[ComponentPhi] = DepthNumber;
89 211362 : for (Value *Op : ComponentPhi->incoming_values()) {
90 : if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
91 : // If this phi is not part of the same component then that component
92 : // is guaranteed to have been completed before this one. Therefore we
93 : // can just add its reachable values to the reachable values of this
94 : // component.
95 6482 : auto It = ReachableMap.find(DepthMap[PhiOp]);
96 6482 : if (It != ReachableMap.end())
97 3552 : Reachable.insert(It->second.begin(), It->second.end());
98 : } else {
99 105534 : Reachable.insert(Op);
100 : }
101 : }
102 : }
103 96906 : ReachableMap.insert({DepthNumber,Reachable});
104 :
105 : // Filter out phis to get the non-phi reachable values.
106 : ValueSet NonPhi;
107 216796 : for (const Value *V : Reachable)
108 : if (!isa<PHINode>(V))
109 112467 : NonPhi.insert(const_cast<Value*>(V));
110 96906 : NonPhiReachableMap.insert({DepthNumber,NonPhi});
111 : }
112 49673 : }
113 :
114 3226707 : const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
115 6453414 : if (DepthMap.count(PN) == 0) {
116 : SmallVector<const PHINode *, 8> Stack;
117 46151 : processPhi(PN, Stack);
118 : assert(Stack.empty());
119 : }
120 : assert(DepthMap.lookup(PN) != 0);
121 3226707 : return NonPhiReachableMap[DepthMap[PN]];
122 : }
123 :
124 266713 : void PhiValues::invalidateValue(const Value *V) {
125 : // Components that can reach V are invalid.
126 : SmallVector<unsigned int, 8> InvalidComponents;
127 2264955 : for (auto &Pair : ReachableMap)
128 1998242 : if (Pair.second.count(V))
129 4885 : InvalidComponents.push_back(Pair.first);
130 :
131 271598 : for (unsigned int N : InvalidComponents) {
132 29628 : for (const Value *V : ReachableMap[N])
133 24743 : if (const PHINode *PN = dyn_cast<PHINode>(V))
134 11003 : DepthMap.erase(PN);
135 4885 : NonPhiReachableMap.erase(N);
136 4885 : ReachableMap.erase(N);
137 : }
138 : // This value is no longer tracked
139 : auto It = TrackedValues.find_as(V);
140 266713 : if (It != TrackedValues.end())
141 : TrackedValues.erase(It);
142 266713 : }
143 :
144 150891 : void PhiValues::releaseMemory() {
145 150891 : DepthMap.clear();
146 150891 : NonPhiReachableMap.clear();
147 150891 : ReachableMap.clear();
148 150891 : }
149 :
150 11 : void PhiValues::print(raw_ostream &OS) const {
151 : // Iterate through the phi nodes of the function rather than iterating through
152 : // DepthMap in order to get predictable ordering.
153 106 : for (const BasicBlock &BB : F) {
154 135 : for (const PHINode &PN : BB.phis()) {
155 40 : OS << "PHI ";
156 40 : PN.printAsOperand(OS, false);
157 40 : OS << " has values:\n";
158 40 : unsigned int N = DepthMap.lookup(&PN);
159 40 : auto It = NonPhiReachableMap.find(N);
160 40 : if (It == NonPhiReachableMap.end())
161 0 : OS << " UNKNOWN\n";
162 40 : else if (It->second.empty())
163 1 : OS << " NONE\n";
164 : else
165 115 : for (Value *V : It->second)
166 : // Printing of an instruction prints two spaces at the start, so
167 : // handle instructions and everything else slightly differently in
168 : // order to get consistent indenting.
169 : if (Instruction *I = dyn_cast<Instruction>(V))
170 3 : OS << *I << "\n";
171 : else
172 146 : OS << " " << *V << "\n";
173 : }
174 : }
175 11 : }
176 :
177 : AnalysisKey PhiValuesAnalysis::Key;
178 329 : PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
179 329 : return PhiValues(F);
180 : }
181 :
182 11 : PreservedAnalyses PhiValuesPrinterPass::run(Function &F,
183 : FunctionAnalysisManager &AM) {
184 11 : OS << "PHI Values for function: " << F.getName() << "\n";
185 : PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F);
186 106 : for (const BasicBlock &BB : F)
187 135 : for (const PHINode &PN : BB.phis())
188 40 : PI.getValuesForPhi(&PN);
189 11 : PI.print(OS);
190 11 : return PreservedAnalyses::all();
191 : }
192 :
193 13642 : PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {
194 6821 : initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry());
195 6821 : }
196 :
197 150891 : bool PhiValuesWrapperPass::runOnFunction(Function &F) {
198 150891 : Result.reset(new PhiValues(F));
199 150891 : return false;
200 : }
201 :
202 150891 : void PhiValuesWrapperPass::releaseMemory() {
203 150891 : Result->releaseMemory();
204 150890 : }
205 :
206 6821 : void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
207 : AU.setPreservesAll();
208 6821 : }
209 :
210 : char PhiValuesWrapperPass::ID = 0;
211 :
212 187811 : INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
213 : true)
|
