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. PhiValues(const Function & F)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: PhiValuesPrinterPass(raw_ostream & OS)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 getResult()133 PhiValues &getResult() { return *Result; } getResult()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 144