include/llvm/Analysis/PhiValues.h

   1 //===- PhiValues.h - Phi Value Analysis -------------------------*- C++ -*-===//
   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 // This file defines the PhiValues class, and associated passes, which can be
  11 // used to find the underlying values of the phis in a function, i.e. the
  12 // non-phi values that can be found by traversing the phi graph.
  13 //
  14 // This information is computed lazily and cached. If new phis are added to the
  15 // function they are handled correctly, but if an existing phi has its operands
  16 // modified PhiValues has to be notified by calling invalidateValue.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef LLVM_ANALYSIS_PHIVALUES_H
  21 #define LLVM_ANALYSIS_PHIVALUES_H
  22
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/DenseSet.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26 #include "llvm/ADT/SmallVector.h"
  27 #include "llvm/IR/PassManager.h"
  28 #include "llvm/IR/ValueHandle.h"
  29 #include "llvm/Pass.h"
  30
  31 namespace llvm {
  32
  33 class Use;
  34 class Value;
  35 class PHINode;
  36 class Function;
  37
  38 /// Class for calculating and caching the underlying values of phis in a
  39 /// function.
  40 ///
  41 /// Initially the PhiValues is empty, and gets incrementally populated whenever
  42 /// it is queried.
  43 class PhiValues {
  44 public:
  45   using ValueSet = SmallPtrSet<Value *, 4>;
  46
  47   /// Construct an empty PhiValues.
  48   PhiValues(const Function &F) : F(F) {}
  49
  50   /// Get the underlying values of a phi.
  51   ///
  52   /// This returns the cached value if PN has previously been processed,
  53   /// otherwise it processes it first.
  54   const ValueSet &getValuesForPhi(const PHINode *PN);
  55
  56   /// Notify PhiValues that the cached information using V is no longer valid
  57   ///
  58   /// Whenever a phi has its operands modified the cached values for that phi
  59   /// (and the phis that use that phi) become invalid. A user of PhiValues has
  60   /// to notify it of this by calling invalidateValue on either the operand or
  61   /// the phi, which will then clear the relevant cached information.
  62   void invalidateValue(const Value *V);
  63
  64   /// Free the memory used by this class.
  65   void releaseMemory();
  66
  67   /// Print out the values currently in the cache.
  68   void print(raw_ostream &OS) const;
  69
  70   /// Handle invalidation events in the new pass manager.
  71   bool invalidate(Function &, const PreservedAnalyses &,
  72                   FunctionAnalysisManager::Invalidator &);
  73
  74 private:
  75   using PhiSet = SmallPtrSet<const PHINode *, 4>;
  76   using ConstValueSet = SmallPtrSet<const Value *, 4>;
  77
  78   /// The next depth number to be used by processPhi.
  79   unsigned int NextDepthNumber = 1;
  80
  81   /// Depth numbers of phis. Phis with the same depth number are part of the
  82   /// same strongly connected component.
  83   DenseMap<const PHINode *, unsigned int> DepthMap;
  84
  85   /// Non-phi values reachable from each component.
  86   DenseMap<unsigned int, ValueSet> NonPhiReachableMap;
  87
  88   /// All values reachable from each component.
  89   DenseMap<unsigned int, ConstValueSet> ReachableMap;
  90
  91   /// The function that the PhiValues is for.
  92   const Function &F;
  93
  94   /// Process a phi so that its entries in the depth and reachable maps are
  95   /// fully populated.
  96   void processPhi(const PHINode *PN, SmallVector<const PHINode *, 8> &Stack);
  97 };
  98
  99 /// The analysis pass which yields a PhiValues
 100 ///
 101 /// The analysis does nothing by itself, and just returns an empty PhiValues
 102 /// which will get filled in as it's used.
 103 class PhiValuesAnalysis : public AnalysisInfoMixin<PhiValuesAnalysis> {
 104   friend AnalysisInfoMixin<PhiValuesAnalysis>;
 105   static AnalysisKey Key;
 106
 107 public:
 108   using Result = PhiValues;
 109   PhiValues run(Function &F, FunctionAnalysisManager &);
 110 };
 111
 112 /// A pass for printing the PhiValues for a function.
 113 ///
 114 /// This pass doesn't print whatever information the PhiValues happens to hold,
 115 /// but instead first uses the PhiValues to analyze all the phis in the function
 116 /// so the complete information is printed.
 117 class PhiValuesPrinterPass : public PassInfoMixin<PhiValuesPrinterPass> {
 118   raw_ostream &OS;
 119
 120 public:
 121   explicit PhiValuesPrinterPass(raw_ostream &OS) : OS(OS) {}
 122   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 123 };
 124
 125 /// Wrapper pass for the legacy pass manager
 126 class PhiValuesWrapperPass : public FunctionPass {
 127   std::unique_ptr<PhiValues> Result;
 128
 129 public:
 130   static char ID;
 131   PhiValuesWrapperPass();
 132
 133   PhiValues &getResult() { return *Result; }
 134   const PhiValues &getResult() const { return *Result; }
 135
 136   bool runOnFunction(Function &F) override;
 137   void releaseMemory() override;
 138   void getAnalysisUsage(AnalysisUsage &AU) const override;
 139 };
 140
 141 } // namespace llvm
 142
 143 #endif