LCOV - code coverage report
Current view: top level - lib/Analysis - PhiValues.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 91 92 98.9 %
Date: 2018-10-20 13:21:21 Functions: 16 16 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13