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   /// A CallbackVH to notify PhiValues when a value is deleted or replaced, so
  92   /// that the cached information for that value can be cleared to avoid
  93   /// dangling pointers to invalid values.
  94   class PhiValuesCallbackVH final : public CallbackVH {
  95     PhiValues *PV;
  96     void deleted() override;
  97     void allUsesReplacedWith(Value *New) override;
  98
  99   public:
 100     PhiValuesCallbackVH(Value *V, PhiValues *PV = nullptr)
 101         : CallbackVH(V), PV(PV) {}
 102   };
 103
 104   /// A set of callbacks to the values that processPhi has seen.
 105   DenseSet<PhiValuesCallbackVH, DenseMapInfo<Value *>> TrackedValues;
 106
 107   /// The function that the PhiValues is for.
 108   const Function &F;
 109
 110   /// Process a phi so that its entries in the depth and reachable maps are
 111   /// fully populated.
 112   void processPhi(const PHINode *PN, SmallVector<const PHINode *, 8> &Stack);
 113 };
 114
 115 /// The analysis pass which yields a PhiValues
 116 ///
 117 /// The analysis does nothing by itself, and just returns an empty PhiValues
 118 /// which will get filled in as it's used.
 119 class PhiValuesAnalysis : public AnalysisInfoMixin<PhiValuesAnalysis> {
 120   friend AnalysisInfoMixin<PhiValuesAnalysis>;
 121   static AnalysisKey Key;
 122
 123 public:
 124   using Result = PhiValues;
 125   PhiValues run(Function &F, FunctionAnalysisManager &);
 126 };
 127
 128 /// A pass for printing the PhiValues for a function.
 129 ///
 130 /// This pass doesn't print whatever information the PhiValues happens to hold,
 131 /// but instead first uses the PhiValues to analyze all the phis in the function
 132 /// so the complete information is printed.
 133 class PhiValuesPrinterPass : public PassInfoMixin<PhiValuesPrinterPass> {
 134   raw_ostream &OS;
 135
 136 public:
 137   explicit PhiValuesPrinterPass(raw_ostream &OS) : OS(OS) {}
 138   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 139 };
 140
 141 /// Wrapper pass for the legacy pass manager
 142 class PhiValuesWrapperPass : public FunctionPass {
 143   std::unique_ptr<PhiValues> Result;
 144
 145 public:
 146   static char ID;
 147   PhiValuesWrapperPass();
 148
 149   PhiValues &getResult() { return *Result; }
 150   const PhiValues &getResult() const { return *Result; }
 151
 152   bool runOnFunction(Function &F) override;
 153   void releaseMemory() override;
 154   void getAnalysisUsage(AnalysisUsage &AU) const override;
 155 };
 156
 157 } // namespace llvm
 158
 159 #endif