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 30namespace llvm { 31 32class Value; 33class PHINode; 34class 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. 41class PhiValues { 42public: 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 72private: 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. 116class PhiValuesAnalysis : public AnalysisInfoMixin<PhiValuesAnalysis> { 117 friend AnalysisInfoMixin<PhiValuesAnalysis>; 118 static AnalysisKey Key; 119 120public: 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. 130class PhiValuesPrinterPass : public PassInfoMixin<PhiValuesPrinterPass> { 131 raw_ostream &OS; 132 133public: 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 139class PhiValuesWrapperPass : public FunctionPass { 140 std::unique_ptr<PhiValues> Result; 141 142public: 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