xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/PhiValues.cpp (revision a3c35da61bb201168575f1d18f4ca3e96937d35c)
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  
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  
26  bool 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.
49  void PhiValues::processPhi(const PHINode *Phi,
50                             SmallVector<const PHINode *, 8> &Stack) {
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  
113  const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
114    if (DepthMap.count(PN) == 0) {
115      SmallVector<const PHINode *, 8> Stack;
116      processPhi(PN, Stack);
117      assert(Stack.empty());
118    }
119    assert(DepthMap.lookup(PN) != 0);
120    return NonPhiReachableMap[DepthMap[PN]];
121  }
122  
123  void PhiValues::invalidateValue(const Value *V) {
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  
143  void PhiValues::releaseMemory() {
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;
177  PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
178    return PhiValues(F);
179  }
180  
181  PreservedAnalyses PhiValuesPrinterPass::run(Function &F,
182                                              FunctionAnalysisManager &AM) {
183    OS << "PHI Values for function: " << F.getName() << "\n";
184    PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F);
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  
192  PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {
193    initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry());
194  }
195  
196  bool PhiValuesWrapperPass::runOnFunction(Function &F) {
197    Result.reset(new PhiValues(F));
198    return false;
199  }
200  
201  void PhiValuesWrapperPass::releaseMemory() {
202    Result->releaseMemory();
203  }
204  
205  void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
206    AU.setPreservesAll();
207  }
208  
209  char PhiValuesWrapperPass::ID = 0;
210  
211  INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
212                  true)
213