llvm/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/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
  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                            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
 125 const 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
 137 void 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
 157 void PhiValues::releaseMemory() {
 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;
 191 PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
 192   return PhiValues(F);
 193 }
 194
 195 PreservedAnalyses 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
 206 PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {
 207   initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry());
 208 }
 209
 210 bool PhiValuesWrapperPass::runOnFunction(Function &F) {
 211   Result.reset(new PhiValues(F));
 212   return false;
 213 }
 214
 215 void PhiValuesWrapperPass::releaseMemory() {
 216   Result->releaseMemory();
 217 }
 218
 219 void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 220   AU.setPreservesAll();
 221 }
 222
 223 char PhiValuesWrapperPass::ID = 0;
 224
 225 INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
 226                 true)