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/SmallVector.h"
11#include "llvm/IR/Instructions.h"
12#include "llvm/InitializePasses.h"
13
14using namespace llvm;
15
16void PhiValues::PhiValuesCallbackVH::deleted() {
17  PV->invalidateValue(getValPtr());
18}
19
20void 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
26bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA,
27                           FunctionAnalysisManager::Invalidator &) {
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.
49void PhiValues::processPhi(const PHINode *Phi,
50                           SmallVectorImpl<const PHINode *> &Stack) {
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
125const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
126  unsigned int DepthNumber = DepthMap.lookup(PN);
127  if (DepthNumber == 0) {
128    SmallVector<const PHINode *, 8> Stack;
129    processPhi(PN, Stack);
130    DepthNumber = DepthMap.lookup(PN);
131    assert(Stack.empty());
132    assert(DepthNumber != 0);
133  }
134  return NonPhiReachableMap[DepthNumber];
135}
136
137void PhiValues::invalidateValue(const Value *V) {
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
157void PhiValues::releaseMemory() {
158  DepthMap.clear();
159  NonPhiReachableMap.clear();
160  ReachableMap.clear();
161}
162
163void 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
190AnalysisKey PhiValuesAnalysis::Key;
191PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
192  return PhiValues(F);
193}
194
195PreservedAnalyses PhiValuesPrinterPass::run(Function &F,
196                                            FunctionAnalysisManager &AM) {
197  OS << "PHI Values for function: " << F.getName() << "\n";
198  PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F);
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
206PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {
207  initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry());
208}
209
210bool PhiValuesWrapperPass::runOnFunction(Function &F) {
211  Result.reset(new PhiValues(F));
212  return false;
213}
214
215void PhiValuesWrapperPass::releaseMemory() {
216  Result->releaseMemory();
217}
218
219void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
220  AU.setPreservesAll();
221}
222
223char PhiValuesWrapperPass::ID = 0;
224
225INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
226                true)
227