LLVM  14.0.0git
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/SmallVector.h"
11 #include "llvm/IR/Instructions.h"
12 #include "llvm/InitializePasses.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 RootDepthNumber = ++NextDepthNumber;
55  DepthMap[Phi] = RootDepthNumber;
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  unsigned int OpDepthNumber = DepthMap.lookup(PhiPhiOp);
63  if (OpDepthNumber == 0) {
64  processPhi(PhiPhiOp, Stack);
65  OpDepthNumber = DepthMap.lookup(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(OpDepthNumber))
71  DepthMap[Phi] = std::min(DepthMap[Phi], OpDepthNumber);
72  } else {
73  TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
74  }
75  }
76 
77  // Now that incoming phis have been handled, push this phi to the stack.
78  Stack.push_back(Phi);
79 
80  // If the depth number has not changed then we've finished collecting the phis
81  // of a strongly connected component.
82  if (DepthMap[Phi] == RootDepthNumber) {
83  // Collect the reachable values for this component. The phis of this
84  // component will be those on top of the depth stack with the same or
85  // greater depth number.
86  ConstValueSet &Reachable = ReachableMap[RootDepthNumber];
87  while (true) {
88  const PHINode *ComponentPhi = Stack.pop_back_val();
89  Reachable.insert(ComponentPhi);
90 
91  for (Value *Op : ComponentPhi->incoming_values()) {
92  if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
93  // If this phi is not part of the same component then that component
94  // is guaranteed to have been completed before this one. Therefore we
95  // can just add its reachable values to the reachable values of this
96  // component.
97  unsigned int OpDepthNumber = DepthMap[PhiOp];
98  if (OpDepthNumber != RootDepthNumber) {
99  auto It = ReachableMap.find(OpDepthNumber);
100  if (It != ReachableMap.end())
101  Reachable.insert(It->second.begin(), It->second.end());
102  }
103  } else
104  Reachable.insert(Op);
105  }
106 
107  if (Stack.empty())
108  break;
109 
110  unsigned int &ComponentDepthNumber = DepthMap[Stack.back()];
111  if (ComponentDepthNumber < RootDepthNumber)
112  break;
113 
114  ComponentDepthNumber = RootDepthNumber;
115  }
116 
117  // Filter out phis to get the non-phi reachable values.
118  ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber];
119  for (const Value *V : Reachable)
120  if (!isa<PHINode>(V))
121  NonPhi.insert(const_cast<Value *>(V));
122  }
123 }
124 
126  unsigned int DepthNumber = DepthMap.lookup(PN);
127  if (DepthNumber == 0) {
129  processPhi(PN, Stack);
130  DepthNumber = DepthMap.lookup(PN);
131  assert(Stack.empty());
132  assert(DepthNumber != 0);
133  }
134  return NonPhiReachableMap[DepthNumber];
135 }
136 
138  // Components that can reach V are invalid.
139  SmallVector<unsigned int, 8> InvalidComponents;
140  for (auto &Pair : ReachableMap)
141  if (Pair.second.count(V))
142  InvalidComponents.push_back(Pair.first);
143 
144  for (unsigned int N : InvalidComponents) {
145  for (const Value *V : ReachableMap[N])
146  if (const PHINode *PN = dyn_cast<PHINode>(V))
147  DepthMap.erase(PN);
148  NonPhiReachableMap.erase(N);
149  ReachableMap.erase(N);
150  }
151  // This value is no longer tracked
152  auto It = TrackedValues.find_as(V);
153  if (It != TrackedValues.end())
154  TrackedValues.erase(It);
155 }
156 
158  DepthMap.clear();
159  NonPhiReachableMap.clear();
160  ReachableMap.clear();
161 }
162 
163 void PhiValues::print(raw_ostream &OS) const {
164  // Iterate through the phi nodes of the function rather than iterating through
165  // DepthMap in order to get predictable ordering.
166  for (const BasicBlock &BB : F) {
167  for (const PHINode &PN : BB.phis()) {
168  OS << "PHI ";
169  PN.printAsOperand(OS, false);
170  OS << " has values:\n";
171  unsigned int N = DepthMap.lookup(&PN);
172  auto It = NonPhiReachableMap.find(N);
173  if (It == NonPhiReachableMap.end())
174  OS << " UNKNOWN\n";
175  else if (It->second.empty())
176  OS << " NONE\n";
177  else
178  for (Value *V : It->second)
179  // Printing of an instruction prints two spaces at the start, so
180  // handle instructions and everything else slightly differently in
181  // order to get consistent indenting.
182  if (Instruction *I = dyn_cast<Instruction>(V))
183  OS << *I << "\n";
184  else
185  OS << " " << *V << "\n";
186  }
187  }
188 }
189 
190 AnalysisKey PhiValuesAnalysis::Key;
192  return PhiValues(F);
193 }
194 
197  OS << "PHI Values for function: " << F.getName() << "\n";
199  for (const BasicBlock &BB : F)
200  for (const PHINode &PN : BB.phis())
201  PI.getValuesForPhi(&PN);
202  PI.print(OS);
203  return PreservedAnalyses::all();
204 }
205 
208 }
209 
211  Result.reset(new PhiValues(F));
212  return false;
213 }
214 
216  Result->releaseMemory();
217 }
218 
220  AU.setPreservesAll();
221 }
222 
223 char PhiValuesWrapperPass::ID = 0;
224 
225 INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
226  true)
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::PhiValues::invalidate
bool invalidate(Function &, const PreservedAnalyses &, FunctionAnalysisManager::Invalidator &)
Handle invalidation events in the new pass manager.
Definition: PhiValues.cpp:26
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::PhiValuesPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PhiValues.cpp:195
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2734
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:783
llvm::Function
Definition: Function.h:62
llvm::PhiValues::ValueSet
SmallSetVector< Value *, 4 > ValueSet
Definition: PhiValues.h:43
llvm::PhiValues::print
void print(raw_ostream &OS) const
Print out the values currently in the cache.
Definition: PhiValues.cpp:163
llvm::PhiValuesWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: PhiValues.cpp:219
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:93
llvm::PhiValuesWrapperPass
Wrapper pass for the legacy pass manager.
Definition: PhiValues.h:139
llvm::initializePhiValuesWrapperPassPass
void initializePhiValuesWrapperPassPass(PassRegistry &)
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PhiValuesAnalysis::run
PhiValues run(Function &F, FunctionAnalysisManager &)
Definition: PhiValues.cpp:191
llvm::PhiValuesWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: PhiValues.cpp:210
llvm::PhiValuesWrapperPass::releaseMemory
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:215
llvm::PhiValues::releaseMemory
void releaseMemory()
Free the memory used by this class.
Definition: PhiValues.cpp:157
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
llvm::PhiValues::getValuesForPhi
const ValueSet & getValuesForPhi(const PHINode *PN)
Get the underlying values of a phi.
Definition: PhiValues.cpp:125
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::PhiValuesAnalysis
The analysis pass which yields a PhiValues.
Definition: PhiValues.h:116
llvm::PhiValuesWrapperPass::ID
static char ID
Definition: PhiValues.h:143
llvm::pdb::PDB_MemoryType::Stack
@ Stack
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
PhiValues.h
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::PhiValues::invalidateValue
void invalidateValue(const Value *V)
Notify PhiValues that the cached information using V is no longer valid.
Definition: PhiValues.cpp:137
Instructions.h
llvm::PhiValues
Class for calculating and caching the underlying values of phis in a function.
Definition: PhiValues.h:41
SmallVector.h
N
#define N
llvm::PHINode
Definition: Instructions.h:2648
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:313
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::PhiValuesWrapperPass::PhiValuesWrapperPass
PhiValuesWrapperPass()
Definition: PhiValues.cpp:206
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38