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