1 //===- llvm/PassAnalysisSupport.h - Analysis Pass Support code --*- 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 stuff that is used to define and "use" Analysis Passes. 10 // This file is automatically #included by Pass.h, so: 11 // 12 // NO .CPP FILES SHOULD INCLUDE THIS FILE DIRECTLY 13 // 14 // Instead, #include Pass.h 15 // 16 //===----------------------------------------------------------------------===// 17 18 #if !defined(LLVM_PASS_H) || defined(LLVM_PASSANALYSISSUPPORT_H) 19 #error "Do not include <PassAnalysisSupport.h>; include <Pass.h> instead" 20 #endif 21 22 #ifndef LLVM_PASSANALYSISSUPPORT_H 23 #define LLVM_PASSANALYSISSUPPORT_H 24 25 #include "llvm/ADT/STLExtras.h" 26 #include "llvm/ADT/SmallVector.h" 27 #include <cassert> 28 #include <tuple> 29 #include <utility> 30 #include <vector> 31 32 namespace llvm { 33 34 class Function; 35 class Pass; 36 class PMDataManager; 37 class StringRef; 38 39 //===----------------------------------------------------------------------===// 40 /// Represent the analysis usage information of a pass. This tracks analyses 41 /// that the pass REQUIRES (must be available when the pass runs), REQUIRES 42 /// TRANSITIVE (must be available throughout the lifetime of the pass), and 43 /// analyses that the pass PRESERVES (the pass does not invalidate the results 44 /// of these analyses). This information is provided by a pass to the Pass 45 /// infrastructure through the getAnalysisUsage virtual function. 46 /// 47 class AnalysisUsage { 48 public: 49 using VectorType = SmallVectorImpl<AnalysisID>; 50 51 private: 52 /// Sets of analyses required and preserved by a pass 53 // TODO: It's not clear that SmallVector is an appropriate data structure for 54 // this usecase. The sizes were picked to minimize wasted space, but are 55 // otherwise fairly meaningless. 56 SmallVector<AnalysisID, 8> Required; 57 SmallVector<AnalysisID, 2> RequiredTransitive; 58 SmallVector<AnalysisID, 2> Preserved; 59 SmallVector<AnalysisID, 0> Used; 60 bool PreservesAll = false; 61 62 void pushUnique(VectorType &Set, AnalysisID ID) { 63 if (!llvm::is_contained(Set, ID)) 64 Set.push_back(ID); 65 } 66 67 public: 68 AnalysisUsage() = default; 69 70 ///@{ 71 /// Add the specified ID to the required set of the usage info for a pass. 72 AnalysisUsage &addRequiredID(const void *ID); 73 AnalysisUsage &addRequiredID(char &ID); 74 template<class PassClass> 75 AnalysisUsage &addRequired() { 76 return addRequiredID(PassClass::ID); 77 } 78 79 AnalysisUsage &addRequiredTransitiveID(char &ID); 80 template<class PassClass> 81 AnalysisUsage &addRequiredTransitive() { 82 return addRequiredTransitiveID(PassClass::ID); 83 } 84 ///@} 85 86 ///@{ 87 /// Add the specified ID to the set of analyses preserved by this pass. 88 AnalysisUsage &addPreservedID(const void *ID) { 89 pushUnique(Preserved, ID); 90 return *this; 91 } 92 AnalysisUsage &addPreservedID(char &ID) { 93 pushUnique(Preserved, &ID); 94 return *this; 95 } 96 /// Add the specified Pass class to the set of analyses preserved by this pass. 97 template<class PassClass> 98 AnalysisUsage &addPreserved() { 99 pushUnique(Preserved, &PassClass::ID); 100 return *this; 101 } 102 ///@} 103 104 ///@{ 105 /// Add the specified ID to the set of analyses used by this pass if they are 106 /// available.. 107 AnalysisUsage &addUsedIfAvailableID(const void *ID) { 108 pushUnique(Used, ID); 109 return *this; 110 } 111 AnalysisUsage &addUsedIfAvailableID(char &ID) { 112 pushUnique(Used, &ID); 113 return *this; 114 } 115 /// Add the specified Pass class to the set of analyses used by this pass. 116 template<class PassClass> 117 AnalysisUsage &addUsedIfAvailable() { 118 pushUnique(Used, &PassClass::ID); 119 return *this; 120 } 121 ///@} 122 123 /// Add the Pass with the specified argument string to the set of analyses 124 /// preserved by this pass. If no such Pass exists, do nothing. This can be 125 /// useful when a pass is trivially preserved, but may not be linked in. Be 126 /// careful about spelling! 127 AnalysisUsage &addPreserved(StringRef Arg); 128 129 /// Set by analyses that do not transform their input at all 130 void setPreservesAll() { PreservesAll = true; } 131 132 /// Determine whether a pass said it does not transform its input at all 133 bool getPreservesAll() const { return PreservesAll; } 134 135 /// This function should be called by the pass, iff they do not: 136 /// 137 /// 1. Add or remove basic blocks from the function 138 /// 2. Modify terminator instructions in any way. 139 /// 140 /// This function annotates the AnalysisUsage info object to say that analyses 141 /// that only depend on the CFG are preserved by this pass. 142 void setPreservesCFG(); 143 144 const VectorType &getRequiredSet() const { return Required; } 145 const VectorType &getRequiredTransitiveSet() const { 146 return RequiredTransitive; 147 } 148 const VectorType &getPreservedSet() const { return Preserved; } 149 const VectorType &getUsedSet() const { return Used; } 150 }; 151 152 //===----------------------------------------------------------------------===// 153 /// AnalysisResolver - Simple interface used by Pass objects to pull all 154 /// analysis information out of pass manager that is responsible to manage 155 /// the pass. 156 /// 157 class AnalysisResolver { 158 public: 159 AnalysisResolver() = delete; 160 explicit AnalysisResolver(PMDataManager &P) : PM(P) {} 161 162 PMDataManager &getPMDataManager() { return PM; } 163 164 /// Find pass that is implementing PI. 165 Pass *findImplPass(AnalysisID PI) { 166 Pass *ResultPass = nullptr; 167 for (const auto &AnalysisImpl : AnalysisImpls) { 168 if (AnalysisImpl.first == PI) { 169 ResultPass = AnalysisImpl.second; 170 break; 171 } 172 } 173 return ResultPass; 174 } 175 176 /// Find pass that is implementing PI. Initialize pass for Function F. 177 std::tuple<Pass *, bool> findImplPass(Pass *P, AnalysisID PI, Function &F); 178 179 void addAnalysisImplsPair(AnalysisID PI, Pass *P) { 180 if (findImplPass(PI) == P) 181 return; 182 std::pair<AnalysisID, Pass*> pir = std::make_pair(PI,P); 183 AnalysisImpls.push_back(pir); 184 } 185 186 /// Clear cache that is used to connect a pass to the analysis (PassInfo). 187 void clearAnalysisImpls() { 188 AnalysisImpls.clear(); 189 } 190 191 /// Return analysis result or null if it doesn't exist. 192 Pass *getAnalysisIfAvailable(AnalysisID ID) const; 193 194 private: 195 /// This keeps track of which passes implements the interfaces that are 196 /// required by the current pass (to implement getAnalysis()). 197 std::vector<std::pair<AnalysisID, Pass *>> AnalysisImpls; 198 199 /// PassManager that is used to resolve analysis info 200 PMDataManager &PM; 201 }; 202 203 /// getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to 204 /// get analysis information that might be around, for example to update it. 205 /// This is different than getAnalysis in that it can fail (if the analysis 206 /// results haven't been computed), so should only be used if you can handle 207 /// the case when the analysis is not available. This method is often used by 208 /// transformation APIs to update analysis results for a pass automatically as 209 /// the transform is performed. 210 template<typename AnalysisType> 211 AnalysisType *Pass::getAnalysisIfAvailable() const { 212 assert(Resolver && "Pass not resident in a PassManager object!"); 213 214 const void *PI = &AnalysisType::ID; 215 216 Pass *ResultPass = Resolver->getAnalysisIfAvailable(PI); 217 if (!ResultPass) return nullptr; 218 219 // Because the AnalysisType may not be a subclass of pass (for 220 // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially 221 // adjust the return pointer (because the class may multiply inherit, once 222 // from pass, once from AnalysisType). 223 return (AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); 224 } 225 226 /// getAnalysis<AnalysisType>() - This function is used by subclasses to get 227 /// to the analysis information that they claim to use by overriding the 228 /// getAnalysisUsage function. 229 template<typename AnalysisType> 230 AnalysisType &Pass::getAnalysis() const { 231 assert(Resolver && "Pass has not been inserted into a PassManager object!"); 232 return getAnalysisID<AnalysisType>(&AnalysisType::ID); 233 } 234 235 template<typename AnalysisType> 236 AnalysisType &Pass::getAnalysisID(AnalysisID PI) const { 237 assert(PI && "getAnalysis for unregistered pass!"); 238 assert(Resolver&&"Pass has not been inserted into a PassManager object!"); 239 // PI *must* appear in AnalysisImpls. Because the number of passes used 240 // should be a small number, we just do a linear search over a (dense) 241 // vector. 242 Pass *ResultPass = Resolver->findImplPass(PI); 243 assert(ResultPass && 244 "getAnalysis*() called on an analysis that was not " 245 "'required' by pass!"); 246 247 // Because the AnalysisType may not be a subclass of pass (for 248 // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially 249 // adjust the return pointer (because the class may multiply inherit, once 250 // from pass, once from AnalysisType). 251 return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); 252 } 253 254 /// getAnalysis<AnalysisType>() - This function is used by subclasses to get 255 /// to the analysis information that they claim to use by overriding the 256 /// getAnalysisUsage function. If as part of the dependencies, an IR 257 /// transformation is triggered (e.g. because the analysis requires 258 /// BreakCriticalEdges), and Changed is non null, *Changed is updated. 259 template <typename AnalysisType> 260 AnalysisType &Pass::getAnalysis(Function &F, bool *Changed) { 261 assert(Resolver &&"Pass has not been inserted into a PassManager object!"); 262 263 return getAnalysisID<AnalysisType>(&AnalysisType::ID, F, Changed); 264 } 265 266 template <typename AnalysisType> 267 AnalysisType &Pass::getAnalysisID(AnalysisID PI, Function &F, bool *Changed) { 268 assert(PI && "getAnalysis for unregistered pass!"); 269 assert(Resolver && "Pass has not been inserted into a PassManager object!"); 270 // PI *must* appear in AnalysisImpls. Because the number of passes used 271 // should be a small number, we just do a linear search over a (dense) 272 // vector. 273 Pass *ResultPass; 274 bool LocalChanged; 275 std::tie(ResultPass, LocalChanged) = Resolver->findImplPass(this, PI, F); 276 277 assert(ResultPass && "Unable to find requested analysis info"); 278 if (Changed) 279 *Changed |= LocalChanged; 280 else 281 assert(!LocalChanged && 282 "A pass trigged a code update but the update status is lost"); 283 284 // Because the AnalysisType may not be a subclass of pass (for 285 // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially 286 // adjust the return pointer (because the class may multiply inherit, once 287 // from pass, once from AnalysisType). 288 return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); 289 } 290 291 } // end namespace llvm 292 293 #endif // LLVM_PASSANALYSISSUPPORT_H 294