lib/Analysis/PhiValues.cpp

   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)