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