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 Value; 33 class PHINode; 34 class Function; 35 36 /// Class for calculating and caching the underlying values of phis in a 37 /// function. 38 /// 39 /// Initially the PhiValues is empty, and gets incrementally populated whenever 40 /// it is queried. 41 class PhiValues { 42 public: 43 using ValueSet = SmallPtrSet<Value *, 4>; 44 45 /// Construct an empty PhiValues. 46 PhiValues(const Function &F) : F(F) {} 47 48 /// Get the underlying values of a phi. 49 /// 50 /// This returns the cached value if PN has previously been processed, 51 /// otherwise it processes it first. 52 const ValueSet &getValuesForPhi(const PHINode *PN); 53 54 /// Notify PhiValues that the cached information using V is no longer valid 55 /// 56 /// Whenever a phi has its operands modified the cached values for that phi 57 /// (and the phis that use that phi) become invalid. A user of PhiValues has 58 /// to notify it of this by calling invalidateValue on either the operand or 59 /// the phi, which will then clear the relevant cached information. 60 void invalidateValue(const Value *V); 61 62 /// Free the memory used by this class. 63 void releaseMemory(); 64 65 /// Print out the values currently in the cache. 66 void print(raw_ostream &OS) const; 67 68 /// Handle invalidation events in the new pass manager. 69 bool invalidate(Function &, const PreservedAnalyses &, 70 FunctionAnalysisManager::Invalidator &); 71 72 private: 73 using PhiSet = SmallPtrSet<const PHINode *, 4>; 74 using ConstValueSet = SmallPtrSet<const Value *, 4>; 75 76 /// The next depth number to be used by processPhi. 77 unsigned int NextDepthNumber = 1; 78 79 /// Depth numbers of phis. Phis with the same depth number are part of the 80 /// same strongly connected component. 81 DenseMap<const PHINode *, unsigned int> DepthMap; 82 83 /// Non-phi values reachable from each component. 84 DenseMap<unsigned int, ValueSet> NonPhiReachableMap; 85 86 /// All values reachable from each component. 87 DenseMap<unsigned int, ConstValueSet> ReachableMap; 88 89 /// A CallbackVH to notify PhiValues when a value is deleted or replaced, so 90 /// that the cached information for that value can be cleared to avoid 91 /// dangling pointers to invalid values. 92 class PhiValuesCallbackVH final : public CallbackVH { 93 PhiValues *PV; 94 void deleted() override; 95 void allUsesReplacedWith(Value *New) override; 96 97 public: 98 PhiValuesCallbackVH(Value *V, PhiValues *PV = nullptr) 99 : CallbackVH(V), PV(PV) {} 100 }; 101 102 /// A set of callbacks to the values that processPhi has seen. 103 DenseSet<PhiValuesCallbackVH, DenseMapInfo<Value *>> TrackedValues; 104 105 /// The function that the PhiValues is for. 106 const Function &F; 107 108 /// Process a phi so that its entries in the depth and reachable maps are 109 /// fully populated. 110 void processPhi(const PHINode *PN, SmallVectorImpl<const PHINode *> &Stack); 111 }; 112 113 /// The analysis pass which yields a PhiValues 114 /// 115 /// The analysis does nothing by itself, and just returns an empty PhiValues 116 /// which will get filled in as it's used. 117 class PhiValuesAnalysis : public AnalysisInfoMixin<PhiValuesAnalysis> { 118 friend AnalysisInfoMixin<PhiValuesAnalysis>; 119 static AnalysisKey Key; 120 121 public: 122 using Result = PhiValues; 123 PhiValues run(Function &F, FunctionAnalysisManager &); 124 }; 125 126 /// A pass for printing the PhiValues for a function. 127 /// 128 /// This pass doesn't print whatever information the PhiValues happens to hold, 129 /// but instead first uses the PhiValues to analyze all the phis in the function 130 /// so the complete information is printed. 131 class PhiValuesPrinterPass : public PassInfoMixin<PhiValuesPrinterPass> { 132 raw_ostream &OS; 133 134 public: 135 explicit PhiValuesPrinterPass(raw_ostream &OS) : OS(OS) {} 136 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 137 }; 138 139 /// Wrapper pass for the legacy pass manager 140 class PhiValuesWrapperPass : public FunctionPass { 141 std::unique_ptr<PhiValues> Result; 142 143 public: 144 static char ID; 145 PhiValuesWrapperPass(); 146 147 PhiValues &getResult() { return *Result; } 148 const PhiValues &getResult() const { return *Result; } 149 150 bool runOnFunction(Function &F) override; 151 void releaseMemory() override; 152 void getAnalysisUsage(AnalysisUsage &AU) const override; 153 }; 154 155 } // namespace llvm 156 157 #endif 158