Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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