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