//===- AnalysisDeclContext.h - Context for path sensitivity -----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file defines AnalysisDeclContext, a class that manages the analysis
/// context data for context sensitive and path sensitive analysis.
/// It also defines the helper classes to model entering, leaving or inlining
/// function calls.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H
#define LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H
#include "clang/AST/DeclBase.h"
#include "clang/Analysis/BodyFarm.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/CodeInjector.h"
#include "clang/Basic/LLVM.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/Allocator.h"
#include <functional>
#include <memory>
namespace clang {
class AnalysisDeclContextManager;
class ASTContext;
class BlockDecl;
class BlockInvocationContext;
class CFGReverseBlockReachabilityAnalysis;
class CFGStmtMap;
class ImplicitParamDecl;
class LocationContext;
class LocationContextManager;
class ParentMap;
class StackFrameContext;
class Stmt;
class VarDecl;
/// The base class of a hierarchy of objects representing analyses tied
/// to AnalysisDeclContext.
class ManagedAnalysis {
protected:
ManagedAnalysis() = default;
public:
virtual ~ManagedAnalysis();
// Subclasses need to implement:
//
// static const void *getTag();
//
// Which returns a fixed pointer address to distinguish classes of
// analysis objects. They also need to implement:
//
// static [Derived*] create(AnalysisDeclContext &Ctx);
//
// which creates the analysis object given an AnalysisDeclContext.
};
/// AnalysisDeclContext contains the context data for the function, method
/// or block under analysis.
class AnalysisDeclContext {
// Backpoint to the AnalysisManager object that created this
// AnalysisDeclContext. This may be null.
AnalysisDeclContextManager *ADCMgr;
const Decl *const D;
std::unique_ptr<CFG> cfg, completeCFG;
std::unique_ptr<CFGStmtMap> cfgStmtMap;
CFG::BuildOptions cfgBuildOptions;
CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs = nullptr;
bool builtCFG = false;
bool builtCompleteCFG = false;
std::unique_ptr<ParentMap> PM;
std::unique_ptr<CFGReverseBlockReachabilityAnalysis> CFA;
llvm::BumpPtrAllocator A;
llvm::DenseMap<const BlockDecl *, void *> *ReferencedBlockVars = nullptr;
void *ManagedAnalyses = nullptr;
public:
AnalysisDeclContext(AnalysisDeclContextManager *Mgr, const Decl *D);
AnalysisDeclContext(AnalysisDeclContextManager *Mgr, const Decl *D,
const CFG::BuildOptions &BuildOptions);
~AnalysisDeclContext();
ASTContext &getASTContext() const { return D->getASTContext(); }
const Decl *getDecl() const { return D; }
AnalysisDeclContextManager *getManager() const { return ADCMgr; }
CFG::BuildOptions &getCFGBuildOptions() { return cfgBuildOptions; }
const CFG::BuildOptions &getCFGBuildOptions() const {
return cfgBuildOptions;
}
/// \returns Whether we are adding exception handling edges from CallExprs.
/// If this is false, then try/catch statements and blocks reachable from them
/// can appear to be dead in the CFG, analysis passes must cope with that.
bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; }
bool getUseUnoptimizedCFG() const {
return !cfgBuildOptions.PruneTriviallyFalseEdges;
}
bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; }
bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; }
void registerForcedBlockExpression(const Stmt *stmt);
const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt);
/// \returns The body of the stored Decl \c D.
Stmt *getBody() const;
/// \copydoc AnalysisDeclContext::getBody()
/// \param[out] IsAutosynthesized Specifies if the body is auto-generated
/// by the BodyFarm.
Stmt *getBody(bool &IsAutosynthesized) const;
/// \returns Whether the body of the Decl \c D is generated by the BodyFarm.
///
/// \note The lookup is not free. We are going to call getBody behind
/// the scenes.
/// \sa getBody
bool isBodyAutosynthesized() const;
/// \returns Whether the body of the Decl \c D is generated by the BodyFarm
/// from a model file.
///
/// \note The lookup is not free. We are going to call getBody behind
/// the scenes.
/// \sa getBody
bool isBodyAutosynthesizedFromModelFile() const;
CFG *getCFG();
CFGStmtMap *getCFGStmtMap();
CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis();
/// \returns A version of the CFG without any edges pruned.
CFG *getUnoptimizedCFG();
void dumpCFG(bool ShowColors);
/// \returns Whether we have built a CFG for this analysis context.
///
/// \note This doesn't correspond to whether or not a valid CFG exists, it
/// corresponds to whether we *attempted* to build one.
bool isCFGBuilt() const { return builtCFG; }
ParentMap &getParentMap();
using referenced_decls_iterator = const VarDecl *const *;
llvm::iterator_range<referenced_decls_iterator>
getReferencedBlockVars(const BlockDecl *BD);
/// \returns The ImplicitParamDecl associated with \c self if this
/// AnalysisDeclContext wraps an ObjCMethodDecl or nullptr otherwise.
const ImplicitParamDecl *getSelfDecl() const;
/// \copydoc LocationContextManager::getStackFrame()
const StackFrameContext *getStackFrame(LocationContext const *ParentLC,
const Stmt *S, const CFGBlock *Blk,
unsigned BlockCount, unsigned Index);
/// \copydoc LocationContextManager::getBlockInvocationContext()
const BlockInvocationContext *
getBlockInvocationContext(const LocationContext *ParentLC,
const BlockDecl *BD, const void *Data);
/// \returns The specified analysis object, lazily running the analysis if
/// necessary or nullptr if the analysis could not run.
template <typename T> T *getAnalysis() {
const void *tag = T::getTag();
std::unique_ptr<ManagedAnalysis> &data = getAnalysisImpl(tag);
if (!data)
data = T::create(*this);
return static_cast<T *>(data.get());
}
/// \returns Whether the root namespace of \p D is the \c std C++ namespace.
static bool isInStdNamespace(const Decl *D);
static std::string getFunctionName(const Decl *D);
private:
std::unique_ptr<ManagedAnalysis> &getAnalysisImpl(const void *tag);
LocationContextManager &getLocationContextManager();
};
/// It wraps the AnalysisDeclContext to represent both the call stack with
/// the help of StackFrameContext and inside the function calls the
/// BlockInvocationContext. It is needed for context sensitive analysis to
/// model entering, leaving or inlining function calls.
class LocationContext : public llvm::FoldingSetNode {
public:
enum ContextKind { StackFrame, Block };
private:
ContextKind Kind;
// AnalysisDeclContext can't be const since some methods may modify its
// member.
AnalysisDeclContext *Ctx;
const LocationContext *Parent;
int64_t ID;
protected:
LocationContext(ContextKind k, AnalysisDeclContext *ctx,
const LocationContext *parent, int64_t ID)
: Kind(k), Ctx(ctx), Parent(parent), ID(ID) {
assert(ctx);
}
public:
virtual ~LocationContext();
ContextKind getKind() const { return Kind; }
int64_t getID() const { return ID; }
LLVM_ATTRIBUTE_RETURNS_NONNULL
AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; }
/// It might return null.
const LocationContext *getParent() const { return Parent; }
bool isParentOf(const LocationContext *LC) const;
const Decl *getDecl() const { return Ctx->getDecl(); }
CFG *getCFG() const { return Ctx->getCFG(); }
template <typename T> T *getAnalysis() const { return Ctx->getAnalysis<T>(); }
const ParentMap &getParentMap() const { return Ctx->getParentMap(); }
/// \copydoc AnalysisDeclContext::getSelfDecl()
const ImplicitParamDecl *getSelfDecl() const { return Ctx->getSelfDecl(); }
const StackFrameContext *getStackFrame() const;
/// \returns Whether the current LocationContext has no caller context.
virtual bool inTopFrame() const;
virtual void Profile(llvm::FoldingSetNodeID &ID) = 0;
/// Prints out the call stack.
///
/// \param Out The out stream.
LLVM_DUMP_METHOD void dumpStack(raw_ostream &Out) const;
/// Prints out the call stack in \c json format.
///
/// \param Out The out stream.
/// \param NL The newline.
/// \param Space The space count for indentation.
/// \param IsDot Whether the output format is \c dot.
/// \param printMoreInfoPerContext
/// A callback to print more information for each context, for example:
/// \code
/// [&](const LocationContext *LC) { LC->dump(); }
/// \endcode
void printJson(
raw_ostream &Out, const char *NL = "\n", unsigned int Space = 0,
bool IsDot = false,
std::function<void(const LocationContext *)> printMoreInfoPerContext =
[](const LocationContext *) {}) const;
LLVM_DUMP_METHOD void dump() const;
static void ProfileCommon(llvm::FoldingSetNodeID &ID, ContextKind ck,
AnalysisDeclContext *ctx,
const LocationContext *parent, const void *data);
};
/// It represents a stack frame of the call stack (based on CallEvent).
class StackFrameContext : public LocationContext {
friend class LocationContextManager;
// The call site where this stack frame is established.
const Stmt *CallSite;
// The parent block of the call site.
const CFGBlock *Block;
// The number of times the 'Block' has been visited.
// It allows discriminating between stack frames of the same call that is
// called multiple times in a loop.
const unsigned BlockCount;
// The index of the call site in the CFGBlock.
const unsigned Index;
StackFrameContext(AnalysisDeclContext *ADC, const LocationContext *ParentLC,
const Stmt *S, const CFGBlock *Block, unsigned BlockCount,
unsigned Index, int64_t ID)
: LocationContext(StackFrame, ADC, ParentLC, ID), CallSite(S),
Block(Block), BlockCount(BlockCount), Index(Index) {}
public:
~StackFrameContext() override = default;
const Stmt *getCallSite() const { return CallSite; }
const CFGBlock *getCallSiteBlock() const { return Block; }
bool inTopFrame() const override { return getParent() == nullptr; }
unsigned getIndex() const { return Index; }
CFGElement getCallSiteCFGElement() const { return (*Block)[Index]; }
void Profile(llvm::FoldingSetNodeID &ID) override;
static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ADC,
const LocationContext *ParentLC, const Stmt *S,
const CFGBlock *Block, unsigned BlockCount,
unsigned Index) {
ProfileCommon(ID, StackFrame, ADC, ParentLC, S);
ID.AddPointer(Block);
ID.AddInteger(BlockCount);
ID.AddInteger(Index);
}
static bool classof(const LocationContext *LC) {
return LC->getKind() == StackFrame;
}
};
/// It represents a block invocation (based on BlockCall).
class BlockInvocationContext : public LocationContext {
friend class LocationContextManager;
const BlockDecl *BD;
// FIXME: Come up with a more type-safe way to model context-sensitivity.
const void *Data;
BlockInvocationContext(AnalysisDeclContext *ADC,
const LocationContext *ParentLC, const BlockDecl *BD,
const void *Data, int64_t ID)
: LocationContext(Block, ADC, ParentLC, ID), BD(BD), Data(Data) {}
public:
~BlockInvocationContext() override = default;
const BlockDecl *getBlockDecl() const { return BD; }
const void *getData() const { return Data; }
void Profile(llvm::FoldingSetNodeID &ID) override;
static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ADC,
const LocationContext *ParentLC, const BlockDecl *BD,
const void *Data) {
ProfileCommon(ID, Block, ADC, ParentLC, BD);
ID.AddPointer(Data);
}
static bool classof(const LocationContext *LC) {
return LC->getKind() == Block;
}
};
class LocationContextManager {
llvm::FoldingSet<LocationContext> Contexts;
// ID used for generating a new location context.
int64_t NewID = 0;
public:
~LocationContextManager();
/// Obtain a context of the call stack using its parent context.
///
/// \param ADC The AnalysisDeclContext.
/// \param ParentLC The parent context of this newly created context.
/// \param S The call.
/// \param Block The basic block.
/// \param BlockCount The current count of entering into \p Blk.
/// \param Index The index of \p Blk.
/// \returns The context for \p D with parent context \p ParentLC.
const StackFrameContext *getStackFrame(AnalysisDeclContext *ADC,
const LocationContext *ParentLC,
const Stmt *S, const CFGBlock *Block,
unsigned BlockCount, unsigned Index);
/// Obtain a context of the block invocation using its parent context.
///
/// \param ADC The AnalysisDeclContext.
/// \param ParentLC The parent context of this newly created context.
/// \param BD The BlockDecl.
/// \param Data The raw data to store as part of the context.
const BlockInvocationContext *
getBlockInvocationContext(AnalysisDeclContext *ADC,
const LocationContext *ParentLC,
const BlockDecl *BD, const void *Data);
/// Discard all previously created LocationContext objects.
void clear();
};
class AnalysisDeclContextManager {
using ContextMap =
llvm::DenseMap<const Decl *, std::unique_ptr<AnalysisDeclContext>>;
ContextMap Contexts;
LocationContextManager LocCtxMgr;
CFG::BuildOptions cfgBuildOptions;
// Pointer to an interface that can provide function bodies for
// declarations from external source.
std::unique_ptr<CodeInjector> Injector;
// A factory for creating and caching implementations for common
// methods during the analysis.
BodyFarm FunctionBodyFarm;
// Flag to indicate whether or not bodies should be synthesized
// for well-known functions.
bool SynthesizeBodies;
public:
AnalysisDeclContextManager(
ASTContext &ASTCtx, bool useUnoptimizedCFG = false,
bool addImplicitDtors = false, bool addInitializers = false,
bool addTemporaryDtors = false, bool addLifetime = false,
bool addLoopExit = false, bool addScopes = false,
bool synthesizeBodies = false, bool addStaticInitBranches = false,
bool addCXXNewAllocator = true, bool addRichCXXConstructors = true,
bool markElidedCXXConstructors = true, bool addVirtualBaseBranches = true,
CodeInjector *injector = nullptr);
AnalysisDeclContext *getContext(const Decl *D);
bool getUseUnoptimizedCFG() const {
return !cfgBuildOptions.PruneTriviallyFalseEdges;
}
CFG::BuildOptions &getCFGBuildOptions() { return cfgBuildOptions; }
/// \returns Whether faux bodies should be synthesized for known functions.
bool synthesizeBodies() const { return SynthesizeBodies; }
/// Obtain the beginning context of the analysis.
///
/// \returns The top level stack frame for \p D.
const StackFrameContext *getStackFrame(const Decl *D) {
return LocCtxMgr.getStackFrame(getContext(D), nullptr, nullptr, nullptr, 0,
0);
}
/// \copydoc LocationContextManager::getStackFrame()
const StackFrameContext *getStackFrame(AnalysisDeclContext *ADC,
const LocationContext *Parent,
const Stmt *S, const CFGBlock *Block,
unsigned BlockCount, unsigned Index) {
return LocCtxMgr.getStackFrame(ADC, Parent, S, Block, BlockCount, Index);
}
BodyFarm &getBodyFarm();
/// Discard all previously created AnalysisDeclContexts.
void clear();
private:
friend class AnalysisDeclContext;
LocationContextManager &getLocationContextManager() { return LocCtxMgr; }
};
} // namespace clang
#endif // LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H