1//=== AnalysisDeclContext.h - Analysis context for Path Sens analysis --*- C++ -*-// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines AnalysisDeclContext, a class that manages the analysis 11// context data for path sensitive analysis. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H 16#define LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H 17 18#include "clang/AST/Decl.h" 19#include "clang/Analysis/CFG.h" 20#include "clang/Analysis/CodeInjector.h" 21#include "llvm/ADT/DenseMap.h" 22#include "llvm/ADT/FoldingSet.h" 23#include "llvm/Support/Allocator.h" 24#include <memory> 25 26namespace clang { 27 28class Stmt; 29class CFGReverseBlockReachabilityAnalysis; 30class CFGStmtMap; 31class LiveVariables; 32class ManagedAnalysis; 33class ParentMap; 34class PseudoConstantAnalysis; 35class LocationContextManager; 36class StackFrameContext; 37class BlockInvocationContext; 38class AnalysisDeclContextManager; 39class LocationContext; 40 41namespace idx { class TranslationUnit; } 42 43/// The base class of a hierarchy of objects representing analyses tied 44/// to AnalysisDeclContext. 45class ManagedAnalysis { 46protected: 47 ManagedAnalysis() {} 48public: 49 virtual ~ManagedAnalysis(); 50 51 // Subclasses need to implement: 52 // 53 // static const void *getTag(); 54 // 55 // Which returns a fixed pointer address to distinguish classes of 56 // analysis objects. They also need to implement: 57 // 58 // static [Derived*] create(AnalysisDeclContext &Ctx); 59 // 60 // which creates the analysis object given an AnalysisDeclContext. 61}; 62 63 64/// AnalysisDeclContext contains the context data for the function or method 65/// under analysis. 66class AnalysisDeclContext { 67 /// Backpoint to the AnalysisManager object that created this 68 /// AnalysisDeclContext. This may be null. 69 AnalysisDeclContextManager *Manager; 70 71 const Decl * const D; 72 73 std::unique_ptr<CFG> cfg, completeCFG; 74 std::unique_ptr<CFGStmtMap> cfgStmtMap; 75 76 CFG::BuildOptions cfgBuildOptions; 77 CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs; 78 79 bool builtCFG, builtCompleteCFG; 80 std::unique_ptr<ParentMap> PM; 81 std::unique_ptr<PseudoConstantAnalysis> PCA; 82 std::unique_ptr<CFGReverseBlockReachabilityAnalysis> CFA; 83 84 llvm::BumpPtrAllocator A; 85 86 llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; 87 88 void *ManagedAnalyses; 89 90public: 91 AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 92 const Decl *D); 93 94 AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 95 const Decl *D, 96 const CFG::BuildOptions &BuildOptions); 97 98 ~AnalysisDeclContext(); 99 100 ASTContext &getASTContext() const { return D->getASTContext(); } 101 const Decl *getDecl() const { return D; } 102 103 /// Return the AnalysisDeclContextManager (if any) that created 104 /// this AnalysisDeclContext. 105 AnalysisDeclContextManager *getManager() const { 106 return Manager; 107 } 108 109 /// Return the build options used to construct the CFG. 110 CFG::BuildOptions &getCFGBuildOptions() { 111 return cfgBuildOptions; 112 } 113 114 const CFG::BuildOptions &getCFGBuildOptions() const { 115 return cfgBuildOptions; 116 } 117 118 /// getAddEHEdges - Return true iff we are adding exceptional edges from 119 /// callExprs. If this is false, then try/catch statements and blocks 120 /// reachable from them can appear to be dead in the CFG, analysis passes must 121 /// cope with that. 122 bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; } 123 bool getUseUnoptimizedCFG() const { 124 return !cfgBuildOptions.PruneTriviallyFalseEdges; 125 } 126 bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; } 127 bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; } 128 129 void registerForcedBlockExpression(const Stmt *stmt); 130 const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt); 131 132 /// \brief Get the body of the Declaration. 133 Stmt *getBody() const; 134 135 /// \brief Get the body of the Declaration. 136 /// \param[out] IsAutosynthesized Specifies if the body is auto-generated 137 /// by the BodyFarm. 138 Stmt *getBody(bool &IsAutosynthesized) const; 139 140 /// \brief Checks if the body of the Decl is generated by the BodyFarm. 141 /// 142 /// Note, the lookup is not free. We are going to call getBody behind 143 /// the scenes. 144 /// \sa getBody 145 bool isBodyAutosynthesized() const; 146 147 /// \brief Checks if the body of the Decl is generated by the BodyFarm from a 148 /// model file. 149 /// 150 /// Note, the lookup is not free. We are going to call getBody behind 151 /// the scenes. 152 /// \sa getBody 153 bool isBodyAutosynthesizedFromModelFile() const; 154 155 CFG *getCFG(); 156 157 CFGStmtMap *getCFGStmtMap(); 158 159 CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis(); 160 161 /// Return a version of the CFG without any edges pruned. 162 CFG *getUnoptimizedCFG(); 163 164 void dumpCFG(bool ShowColors); 165 166 /// \brief Returns true if we have built a CFG for this analysis context. 167 /// Note that this doesn't correspond to whether or not a valid CFG exists, it 168 /// corresponds to whether we *attempted* to build one. 169 bool isCFGBuilt() const { return builtCFG; } 170 171 ParentMap &getParentMap(); 172 PseudoConstantAnalysis *getPseudoConstantAnalysis(); 173 174 typedef const VarDecl * const * referenced_decls_iterator; 175 176 llvm::iterator_range<referenced_decls_iterator> 177 getReferencedBlockVars(const BlockDecl *BD); 178 179 /// Return the ImplicitParamDecl* associated with 'self' if this 180 /// AnalysisDeclContext wraps an ObjCMethodDecl. Returns NULL otherwise. 181 const ImplicitParamDecl *getSelfDecl() const; 182 183 const StackFrameContext *getStackFrame(LocationContext const *Parent, 184 const Stmt *S, 185 const CFGBlock *Blk, 186 unsigned Idx); 187 188 const BlockInvocationContext * 189 getBlockInvocationContext(const LocationContext *parent, 190 const BlockDecl *BD, 191 const void *ContextData); 192 193 /// Return the specified analysis object, lazily running the analysis if 194 /// necessary. Return NULL if the analysis could not run. 195 template <typename T> 196 T *getAnalysis() { 197 const void *tag = T::getTag(); 198 ManagedAnalysis *&data = getAnalysisImpl(tag); 199 if (!data) { 200 data = T::create(*this); 201 } 202 return static_cast<T*>(data); 203 } 204 205 /// Returns true if the root namespace of the given declaration is the 'std' 206 /// C++ namespace. 207 static bool isInStdNamespace(const Decl *D); 208private: 209 ManagedAnalysis *&getAnalysisImpl(const void* tag); 210 211 LocationContextManager &getLocationContextManager(); 212}; 213 214class LocationContext : public llvm::FoldingSetNode { 215public: 216 enum ContextKind { StackFrame, Scope, Block }; 217 218private: 219 ContextKind Kind; 220 221 // AnalysisDeclContext can't be const since some methods may modify its 222 // member. 223 AnalysisDeclContext *Ctx; 224 225 const LocationContext *Parent; 226 227protected: 228 LocationContext(ContextKind k, AnalysisDeclContext *ctx, 229 const LocationContext *parent) 230 : Kind(k), Ctx(ctx), Parent(parent) {} 231 232public: 233 virtual ~LocationContext(); 234 235 ContextKind getKind() const { return Kind; } 236 237 AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } 238 239 const LocationContext *getParent() const { return Parent; } 240 241 bool isParentOf(const LocationContext *LC) const; 242 243 const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); } 244 245 CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); } 246 247 template <typename T> 248 T *getAnalysis() const { 249 return getAnalysisDeclContext()->getAnalysis<T>(); 250 } 251 252 ParentMap &getParentMap() const { 253 return getAnalysisDeclContext()->getParentMap(); 254 } 255 256 const ImplicitParamDecl *getSelfDecl() const { 257 return Ctx->getSelfDecl(); 258 } 259 260 const StackFrameContext *getCurrentStackFrame() const; 261 262 /// Return true if the current LocationContext has no caller context. 263 virtual bool inTopFrame() const; 264 265 virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; 266 267 void dumpStack(raw_ostream &OS, StringRef Indent = "") const; 268 void dumpStack() const; 269 270public: 271 static void ProfileCommon(llvm::FoldingSetNodeID &ID, 272 ContextKind ck, 273 AnalysisDeclContext *ctx, 274 const LocationContext *parent, 275 const void *data); 276}; 277 278class StackFrameContext : public LocationContext { 279 // The callsite where this stack frame is established. 280 const Stmt *CallSite; 281 282 // The parent block of the callsite. 283 const CFGBlock *Block; 284 285 // The index of the callsite in the CFGBlock. 286 unsigned Index; 287 288 friend class LocationContextManager; 289 StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, 290 const Stmt *s, const CFGBlock *blk, 291 unsigned idx) 292 : LocationContext(StackFrame, ctx, parent), CallSite(s), 293 Block(blk), Index(idx) {} 294 295public: 296 ~StackFrameContext() override {} 297 298 const Stmt *getCallSite() const { return CallSite; } 299 300 const CFGBlock *getCallSiteBlock() const { return Block; } 301 302 /// Return true if the current LocationContext has no caller context. 303 bool inTopFrame() const override { return getParent() == nullptr; } 304 305 unsigned getIndex() const { return Index; } 306 307 void Profile(llvm::FoldingSetNodeID &ID) override; 308 309 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 310 const LocationContext *parent, const Stmt *s, 311 const CFGBlock *blk, unsigned idx) { 312 ProfileCommon(ID, StackFrame, ctx, parent, s); 313 ID.AddPointer(blk); 314 ID.AddInteger(idx); 315 } 316 317 static bool classof(const LocationContext *Ctx) { 318 return Ctx->getKind() == StackFrame; 319 } 320}; 321 322class ScopeContext : public LocationContext { 323 const Stmt *Enter; 324 325 friend class LocationContextManager; 326 ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, 327 const Stmt *s) 328 : LocationContext(Scope, ctx, parent), Enter(s) {} 329 330public: 331 ~ScopeContext() override {} 332 333 void Profile(llvm::FoldingSetNodeID &ID) override; 334 335 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 336 const LocationContext *parent, const Stmt *s) { 337 ProfileCommon(ID, Scope, ctx, parent, s); 338 } 339 340 static bool classof(const LocationContext *Ctx) { 341 return Ctx->getKind() == Scope; 342 } 343}; 344 345class BlockInvocationContext : public LocationContext { 346 const BlockDecl *BD; 347 348 // FIXME: Come up with a more type-safe way to model context-sensitivity. 349 const void *ContextData; 350 351 friend class LocationContextManager; 352 353 BlockInvocationContext(AnalysisDeclContext *ctx, 354 const LocationContext *parent, 355 const BlockDecl *bd, const void *contextData) 356 : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} 357 358public: 359 ~BlockInvocationContext() override {} 360 361 const BlockDecl *getBlockDecl() const { return BD; } 362 363 const void *getContextData() const { return ContextData; } 364 365 void Profile(llvm::FoldingSetNodeID &ID) override; 366 367 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 368 const LocationContext *parent, const BlockDecl *bd, 369 const void *contextData) { 370 ProfileCommon(ID, Block, ctx, parent, bd); 371 ID.AddPointer(contextData); 372 } 373 374 static bool classof(const LocationContext *Ctx) { 375 return Ctx->getKind() == Block; 376 } 377}; 378 379class LocationContextManager { 380 llvm::FoldingSet<LocationContext> Contexts; 381public: 382 ~LocationContextManager(); 383 384 const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, 385 const LocationContext *parent, 386 const Stmt *s, 387 const CFGBlock *blk, unsigned idx); 388 389 const ScopeContext *getScope(AnalysisDeclContext *ctx, 390 const LocationContext *parent, 391 const Stmt *s); 392 393 const BlockInvocationContext * 394 getBlockInvocationContext(AnalysisDeclContext *ctx, 395 const LocationContext *parent, 396 const BlockDecl *BD, 397 const void *ContextData); 398 399 /// Discard all previously created LocationContext objects. 400 void clear(); 401private: 402 template <typename LOC, typename DATA> 403 const LOC *getLocationContext(AnalysisDeclContext *ctx, 404 const LocationContext *parent, 405 const DATA *d); 406}; 407 408class AnalysisDeclContextManager { 409 typedef llvm::DenseMap<const Decl *, std::unique_ptr<AnalysisDeclContext>> 410 ContextMap; 411 412 ContextMap Contexts; 413 LocationContextManager LocContexts; 414 CFG::BuildOptions cfgBuildOptions; 415 416 /// Pointer to an interface that can provide function bodies for 417 /// declarations from external source. 418 std::unique_ptr<CodeInjector> Injector; 419 420 /// Flag to indicate whether or not bodies should be synthesized 421 /// for well-known functions. 422 bool SynthesizeBodies; 423 424public: 425 AnalysisDeclContextManager(bool useUnoptimizedCFG = false, 426 bool addImplicitDtors = false, 427 bool addInitializers = false, 428 bool addTemporaryDtors = false, 429 bool addLifetime = false, 430 bool addLoopExit = false, 431 bool synthesizeBodies = false, 432 bool addStaticInitBranches = false, 433 bool addCXXNewAllocator = true, 434 CodeInjector* injector = nullptr); 435 436 ~AnalysisDeclContextManager(); 437 438 AnalysisDeclContext *getContext(const Decl *D); 439 440 bool getUseUnoptimizedCFG() const { 441 return !cfgBuildOptions.PruneTriviallyFalseEdges; 442 } 443 444 CFG::BuildOptions &getCFGBuildOptions() { 445 return cfgBuildOptions; 446 } 447 448 /// Return true if faux bodies should be synthesized for well-known 449 /// functions. 450 bool synthesizeBodies() const { return SynthesizeBodies; } 451 452 const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, 453 LocationContext const *Parent, 454 const Stmt *S, 455 const CFGBlock *Blk, 456 unsigned Idx) { 457 return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); 458 } 459 460 // Get the top level stack frame. 461 const StackFrameContext *getStackFrame(const Decl *D) { 462 return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr, 463 0); 464 } 465 466 // Get a stack frame with parent. 467 StackFrameContext const *getStackFrame(const Decl *D, 468 LocationContext const *Parent, 469 const Stmt *S, 470 const CFGBlock *Blk, 471 unsigned Idx) { 472 return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); 473 } 474 475 /// Discard all previously created AnalysisDeclContexts. 476 void clear(); 477 478private: 479 friend class AnalysisDeclContext; 480 481 LocationContextManager &getLocationContextManager() { 482 return LocContexts; 483 } 484}; 485 486} // end clang namespace 487#endif 488