contrib/llvm/lib/Analysis/PhiValues.cpp

   1 //===- PhiValues.cpp - Phi Value Analysis ---------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/PhiValues.h"
  11 #include "llvm/ADT/SmallPtrSet.h"
  12 #include "llvm/ADT/SmallVector.h"
  13 #include "llvm/IR/Instructions.h"
  14
  15 using namespace llvm;
  16
  17 bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA,
  18                            FunctionAnalysisManager::Invalidator &) {
  19   // PhiValues is invalidated if it isn't preserved.
  20   auto PAC = PA.getChecker<PhiValuesAnalysis>();
  21   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>());
  22 }
  23
  24 // The goal here is to find all of the non-phi values reachable from this phi,
  25 // and to do the same for all of the phis reachable from this phi, as doing so
  26 // is necessary anyway in order to get the values for this phi. We do this using
  27 // Tarjan's algorithm with Nuutila's improvements to find the strongly connected
  28 // components of the phi graph rooted in this phi:
  29 //  * All phis in a strongly connected component will have the same reachable
  30 //    non-phi values. The SCC may not be the maximal subgraph for that set of
  31 //    reachable values, but finding out that isn't really necessary (it would
  32 //    only reduce the amount of memory needed to store the values).
  33 //  * Tarjan's algorithm completes components in a bottom-up manner, i.e. it
  34 //    never completes a component before the components reachable from it have
  35 //    been completed. This means that when we complete a component we have
  36 //    everything we need to collect the values reachable from that component.
  37 //  * We collect both the non-phi values reachable from each SCC, as that's what
  38 //    we're ultimately interested in, and all of the reachable values, i.e.
  39 //    including phis, as that makes invalidateValue easier.
  40 void PhiValues::processPhi(const PHINode *Phi,
  41                            SmallVector<const PHINode *, 8> &Stack) {
  42   // Initialize the phi with the next depth number.
  43   assert(DepthMap.lookup(Phi) == 0);
  44   assert(NextDepthNumber != UINT_MAX);
  45   unsigned int DepthNumber = ++NextDepthNumber;
  46   DepthMap[Phi] = DepthNumber;
  47
  48   // Recursively process the incoming phis of this phi.
  49   for (Value *PhiOp : Phi->incoming_values()) {
  50     if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) {
  51       // Recurse if the phi has not yet been visited.
  52       if (DepthMap.lookup(PhiPhiOp) == 0)
  53         processPhi(PhiPhiOp, Stack);
  54       assert(DepthMap.lookup(PhiPhiOp) != 0);
  55       // If the phi did not become part of a component then this phi and that
  56       // phi are part of the same component, so adjust the depth number.
  57       if (!ReachableMap.count(DepthMap[PhiPhiOp]))
  58         DepthMap[Phi] = std::min(DepthMap[Phi], DepthMap[PhiPhiOp]);
  59     }
  60   }
  61
  62   // Now that incoming phis have been handled, push this phi to the stack.
  63   Stack.push_back(Phi);
  64
  65   // If the depth number has not changed then we've finished collecting the phis
  66   // of a strongly connected component.
  67   if (DepthMap[Phi] == DepthNumber) {
  68     // Collect the reachable values for this component. The phis of this
  69     // component will be those on top of the depth stach with the same or
  70     // greater depth number.
  71     ConstValueSet Reachable;
  72     while (!Stack.empty() && DepthMap[Stack.back()] >= DepthNumber) {
  73       const PHINode *ComponentPhi = Stack.pop_back_val();
  74       Reachable.insert(ComponentPhi);
  75       DepthMap[ComponentPhi] = DepthNumber;
  76       for (Value *Op : ComponentPhi->incoming_values()) {
  77         if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
  78           // If this phi is not part of the same component then that component
  79           // is guaranteed to have been completed before this one. Therefore we
  80           // can just add its reachable values to the reachable values of this
  81           // component.
  82           auto It = ReachableMap.find(DepthMap[PhiOp]);
  83           if (It != ReachableMap.end())
  84             Reachable.insert(It->second.begin(), It->second.end());
  85         } else {
  86           Reachable.insert(Op);
  87         }
  88       }
  89     }
  90     ReachableMap.insert({DepthNumber,Reachable});
  91
  92     // Filter out phis to get the non-phi reachable values.
  93     ValueSet NonPhi;
  94     for (const Value *V : Reachable)
  95       if (!isa<PHINode>(V))
  96         NonPhi.insert(const_cast<Value*>(V));
  97     NonPhiReachableMap.insert({DepthNumber,NonPhi});
  98   }
  99 }
 100
 101 const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
 102   if (DepthMap.count(PN) == 0) {
 103     SmallVector<const PHINode *, 8> Stack;
 104     processPhi(PN, Stack);
 105     assert(Stack.empty());
 106   }
 107   assert(DepthMap.lookup(PN) != 0);
 108   return NonPhiReachableMap[DepthMap[PN]];
 109 }
 110
 111 void PhiValues::invalidateValue(const Value *V) {
 112   // Components that can reach V are invalid.
 113   SmallVector<unsigned int, 8> InvalidComponents;
 114   for (auto &Pair : ReachableMap)
 115     if (Pair.second.count(V))
 116       InvalidComponents.push_back(Pair.first);
 117
 118   for (unsigned int N : InvalidComponents) {
 119     for (const Value *V : ReachableMap[N])
 120       if (const PHINode *PN = dyn_cast<PHINode>(V))
 121         DepthMap.erase(PN);
 122     NonPhiReachableMap.erase(N);
 123     ReachableMap.erase(N);
 124   }
 125 }
 126
 127 void PhiValues::releaseMemory() {
 128   DepthMap.clear();
 129   NonPhiReachableMap.clear();
 130   ReachableMap.clear();
 131 }
 132
 133 void PhiValues::print(raw_ostream &OS) const {
 134   // Iterate through the phi nodes of the function rather than iterating through
 135   // DepthMap in order to get predictable ordering.
 136   for (const BasicBlock &BB : F) {
 137     for (const PHINode &PN : BB.phis()) {
 138       OS << "PHI ";
 139       PN.printAsOperand(OS, false);
 140       OS << " has values:\n";
 141       unsigned int N = DepthMap.lookup(&PN);
 142       auto It = NonPhiReachableMap.find(N);
 143       if (It == NonPhiReachableMap.end())
 144         OS << "  UNKNOWN\n";
 145       else if (It->second.empty())
 146         OS << "  NONE\n";
 147       else
 148         for (Value *V : It->second)
 149           // Printing of an instruction prints two spaces at the start, so
 150           // handle instructions and everything else slightly differently in
 151           // order to get consistent indenting.
 152           if (Instruction *I = dyn_cast<Instruction>(V))
 153             OS << *I << "\n";
 154           else
 155             OS << "  " << *V << "\n";
 156     }
 157   }
 158 }
 159
 160 AnalysisKey PhiValuesAnalysis::Key;
 161 PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
 162   return PhiValues(F);
 163 }
 164
 165 PreservedAnalyses PhiValuesPrinterPass::run(Function &F,
 166                                             FunctionAnalysisManager &AM) {
 167   OS << "PHI Values for function: " << F.getName() << "\n";
 168   PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F);
 169   for (const BasicBlock &BB : F)
 170     for (const PHINode &PN : BB.phis())
 171       PI.getValuesForPhi(&PN);
 172   PI.print(OS);
 173   return PreservedAnalyses::all();
 174 }
 175
 176 PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {
 177   initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry());
 178 }
 179
 180 bool PhiValuesWrapperPass::runOnFunction(Function &F) {
 181   Result.reset(new PhiValues(F));
 182   return false;
 183 }
 184
 185 void PhiValuesWrapperPass::releaseMemory() {
 186   Result->releaseMemory();
 187 }
 188
 189 void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 190   AU.setPreservesAll();
 191 }
 192
 193 char PhiValuesWrapperPass::ID = 0;
 194
 195 INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
 196                 true)