LLVM  9.0.0svn
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 
10 #include "llvm/ADT/SmallPtrSet.h"
11 #include "llvm/ADT/SmallVector.h"
12 #include "llvm/IR/Instructions.h"
13 
14 using namespace llvm;
15 
16 void PhiValues::PhiValuesCallbackVH::deleted() {
17  PV->invalidateValue(getValPtr());
18 }
19 
20 void 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.
49 void 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 DepthNumber = ++NextDepthNumber;
55  DepthMap[Phi] = DepthNumber;
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  if (DepthMap.lookup(PhiPhiOp) == 0)
63  processPhi(PhiPhiOp, Stack);
64  assert(DepthMap.lookup(PhiPhiOp) != 0);
65  // If the phi did not become part of a component then this phi and that
66  // phi are part of the same component, so adjust the depth number.
67  if (!ReachableMap.count(DepthMap[PhiPhiOp]))
68  DepthMap[Phi] = std::min(DepthMap[Phi], DepthMap[PhiPhiOp]);
69  } else {
70  TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
71  }
72  }
73 
74  // Now that incoming phis have been handled, push this phi to the stack.
75  Stack.push_back(Phi);
76 
77  // If the depth number has not changed then we've finished collecting the phis
78  // of a strongly connected component.
79  if (DepthMap[Phi] == DepthNumber) {
80  // Collect the reachable values for this component. The phis of this
81  // component will be those on top of the depth stach with the same or
82  // greater depth number.
83  ConstValueSet Reachable;
84  while (!Stack.empty() && DepthMap[Stack.back()] >= DepthNumber) {
85  const PHINode *ComponentPhi = Stack.pop_back_val();
86  Reachable.insert(ComponentPhi);
87  DepthMap[ComponentPhi] = DepthNumber;
88  for (Value *Op : ComponentPhi->incoming_values()) {
89  if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
90  // If this phi is not part of the same component then that component
91  // is guaranteed to have been completed before this one. Therefore we
92  // can just add its reachable values to the reachable values of this
93  // component.
94  auto It = ReachableMap.find(DepthMap[PhiOp]);
95  if (It != ReachableMap.end())
96  Reachable.insert(It->second.begin(), It->second.end());
97  } else {
98  Reachable.insert(Op);
99  }
100  }
101  }
102  ReachableMap.insert({DepthNumber,Reachable});
103 
104  // Filter out phis to get the non-phi reachable values.
105  ValueSet NonPhi;
106  for (const Value *V : Reachable)
107  if (!isa<PHINode>(V))
108  NonPhi.insert(const_cast<Value*>(V));
109  NonPhiReachableMap.insert({DepthNumber,NonPhi});
110  }
111 }
112 
114  if (DepthMap.count(PN) == 0) {
116  processPhi(PN, Stack);
117  assert(Stack.empty());
118  }
119  assert(DepthMap.lookup(PN) != 0);
120  return NonPhiReachableMap[DepthMap[PN]];
121 }
122 
124  // Components that can reach V are invalid.
125  SmallVector<unsigned int, 8> InvalidComponents;
126  for (auto &Pair : ReachableMap)
127  if (Pair.second.count(V))
128  InvalidComponents.push_back(Pair.first);
129 
130  for (unsigned int N : InvalidComponents) {
131  for (const Value *V : ReachableMap[N])
132  if (const PHINode *PN = dyn_cast<PHINode>(V))
133  DepthMap.erase(PN);
134  NonPhiReachableMap.erase(N);
135  ReachableMap.erase(N);
136  }
137  // This value is no longer tracked
138  auto It = TrackedValues.find_as(V);
139  if (It != TrackedValues.end())
140  TrackedValues.erase(It);
141 }
142 
144  DepthMap.clear();
145  NonPhiReachableMap.clear();
146  ReachableMap.clear();
147 }
148 
149 void PhiValues::print(raw_ostream &OS) const {
150  // Iterate through the phi nodes of the function rather than iterating through
151  // DepthMap in order to get predictable ordering.
152  for (const BasicBlock &BB : F) {
153  for (const PHINode &PN : BB.phis()) {
154  OS << "PHI ";
155  PN.printAsOperand(OS, false);
156  OS << " has values:\n";
157  unsigned int N = DepthMap.lookup(&PN);
158  auto It = NonPhiReachableMap.find(N);
159  if (It == NonPhiReachableMap.end())
160  OS << " UNKNOWN\n";
161  else if (It->second.empty())
162  OS << " NONE\n";
163  else
164  for (Value *V : It->second)
165  // Printing of an instruction prints two spaces at the start, so
166  // handle instructions and everything else slightly differently in
167  // order to get consistent indenting.
168  if (Instruction *I = dyn_cast<Instruction>(V))
169  OS << *I << "\n";
170  else
171  OS << " " << *V << "\n";
172  }
173  }
174 }
175 
176 AnalysisKey PhiValuesAnalysis::Key;
178  return PhiValues(F);
179 }
180 
183  OS << "PHI Values for function: " << F.getName() << "\n";
185  for (const BasicBlock &BB : F)
186  for (const PHINode &PN : BB.phis())
187  PI.getValuesForPhi(&PN);
188  PI.print(OS);
189  return PreservedAnalyses::all();
190 }
191 
194 }
195 
197  Result.reset(new PhiValues(F));
198  return false;
199 }
200 
202  Result->releaseMemory();
203 }
204 
206  AU.setPreservesAll();
207 }
208 
209 char PhiValuesWrapperPass::ID = 0;
210 
211 INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
212  true)
void releaseMemory()
Free the memory used by this class.
Definition: PhiValues.cpp:143
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:201
F(f)
const ValueSet & getValuesForPhi(const PHINode *PN)
Get the underlying values of a phi.
Definition: PhiValues.cpp:113
The analysis pass which yields a PhiValues.
Definition: PhiValues.h:118
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
Wrapper pass for the legacy pass manager.
Definition: PhiValues.h:141
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: PhiValues.cpp:205
bool invalidate(Function &, const PreservedAnalyses &, FunctionAnalysisManager::Invalidator &)
Handle invalidation events in the new pass manager.
Definition: PhiValues.cpp:26
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void invalidateValue(const Value *V)
Notify PhiValues that the cached information using V is no longer valid.
Definition: PhiValues.cpp:123
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:33
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
PhiValues run(Function &F, FunctionAnalysisManager &)
Definition: PhiValues.cpp:177
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
Definition: PhiValues.cpp:196
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
void setPreservesAll()
Set by analyses that do not transform their input at all.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PhiValues.cpp:181
void print(raw_ostream &OS) const
Print out the values currently in the cache.
Definition: PhiValues.cpp:149
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
Class for calculating and caching the underlying values of phis in a function.
Definition: PhiValues.h:42
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:641
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
LLVM Value Representation.
Definition: Value.h:72
void initializePhiValuesWrapperPassPass(PassRegistry &)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
A container for analyses that lazily runs them and caches their results.
op_range incoming_values()
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
PhiValues(const Function &F)
Construct an empty PhiValues.
Definition: PhiValues.h:47