Facts.h

Go to the documentation of this file.

//===- Facts.h - Lifetime Analysis Facts and Fact Manager ------*- 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
//
//===----------------------------------------------------------------------===//
//
// This file defines Facts, which are atomic lifetime-relevant events (such as
// loan issuance, loan expiration, origin flow, and use), and the FactManager,
// which manages the storage and retrieval of facts for each CFG block.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_FACTS_H
#define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_FACTS_H
 
#include "clang/AST/Decl.h"
#include "clang/Analysis/Analyses/LifetimeSafety/Loans.h"
#include "clang/Analysis/Analyses/LifetimeSafety/Origins.h"
#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h"
#include "clang/Analysis/AnalysisDeclContext.h"
#include "clang/Analysis/CFG.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cstdint>
#include <optional>
 
namespace clang::lifetimes::internal {
 
class FactsGenerator;
class LoanPropagationAnalysis;
 
using FactID = utils::ID<struct FactTag>;
 
/// An abstract base class for a single, atomic lifetime-relevant event.
class Fact {
 
public:
  enum class Kind : uint8_t {
    /// A new loan is issued from a borrow expression (e.g., &x).
    Issue,
    /// A loan expires as its underlying storage is freed (e.g., variable goes
    /// out of scope).
    Expire,
    /// An origin is propagated from a source to a destination (e.g., p = q).
    /// This can also optionally kill the destination origin before flowing into
    /// it. Otherwise, the source's loan set is merged into the destination's
    /// loan set.
    OriginFlow,
    /// An origin is used (eg. appears as l-value expression like DeclRefExpr).
    Use,
    /// An origin that is moved (e.g., passed to an rvalue reference parameter).
    MovedOrigin,
    /// A marker for a specific point in the code, for testing.
    TestPoint,
    /// An origin that escapes the function scope (e.g., via return).
    OriginEscapes,
    /// An origin is invalidated (e.g. vector resized, `delete` called).
    InvalidateOrigin,
    /// All loans of an origin are cleared.
    KillOrigin,
  };
 
private:
  Kind K;
  FactID ID;
 
protected:
  Fact(Kind K) : K(K) {}
 
public:
  virtual ~Fact() = default;
  Kind getKind() const { return K; }
 
  void setID(FactID ID) { this->ID = ID; }
  FactID getID() const { return ID; }
 
  template <typename T> const T *getAs() const {
    if (T::classof(this))
      return static_cast<const T *>(this);
    return nullptr;
  }
 
  virtual void dump(llvm::raw_ostream &OS, const LoanManager &,
                    const OriginManager &,
                    const LoanPropagationAnalysis *LPA = nullptr) const;
};
 
/// A `ProgramPoint` identifies a location in the CFG by pointing to a specific
/// `Fact`. identified by a lifetime-related event (`Fact`).
///
/// A `ProgramPoint` has "after" semantics: it represents the location
/// immediately after its corresponding `Fact`.
using ProgramPoint = const Fact *;
 
class IssueFact : public Fact {
  LoanID LID;
  OriginID OID;
 
public:
  static bool classof(const Fact *F) { return F->getKind() == Kind::Issue; }
 
  IssueFact(LoanID LID, OriginID OID) : Fact(Kind::Issue), LID(LID), OID(OID) {}
  LoanID getLoanID() const { return LID; }
  OriginID getOriginID() const { return OID; }
  void dump(llvm::raw_ostream &OS, const LoanManager &LM,
            const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
/// When an AccessPath expires (e.g., a variable goes out of scope), all loans
/// that are associated with this path expire. For example, if `x` expires, then
/// the loan to `x` expires.
class ExpireFact : public Fact {
  // The access path that expires.
  AccessPath AP;
 
  // Expired origin (e.g., its variable goes out of scope).
  std::optional<OriginID> OID;
  SourceLocation ExpiryLoc;
 
public:
  static bool classof(const Fact *F) { return F->getKind() == Kind::Expire; }
 
  ExpireFact(AccessPath AP, SourceLocation ExpiryLoc,
             std::optional<OriginID> OID = std::nullopt)
      : Fact(Kind::Expire), AP(AP), OID(OID), ExpiryLoc(ExpiryLoc) {}
 
  const AccessPath &getAccessPath() const { return AP; }
  std::optional<OriginID> getOriginID() const { return OID; }
  SourceLocation getExpiryLoc() const { return ExpiryLoc; }
 
  void dump(llvm::raw_ostream &OS, const LoanManager &LM,
            const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
class OriginFlowFact : public Fact {
  OriginID OIDDest;
  OriginID OIDSrc;
  // True if the destination origin should be killed (i.e., its current loans
  // cleared) before the source origin's loans are flowed into it.
  bool KillDest;
 
public:
  static bool classof(const Fact *F) {
    return F->getKind() == Kind::OriginFlow;
  }
 
  OriginFlowFact(OriginID OIDDest, OriginID OIDSrc, bool KillDest)
      : Fact(Kind::OriginFlow), OIDDest(OIDDest), OIDSrc(OIDSrc),
        KillDest(KillDest) {}
 
  OriginID getDestOriginID() const { return OIDDest; }
  OriginID getSrcOriginID() const { return OIDSrc; }
  bool getKillDest() const { return KillDest; }
 
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
/// Represents that an origin escapes the current scope through various means.
/// This is the base class for different escape scenarios.
class OriginEscapesFact : public Fact {
  OriginID OID;
 
public:
  /// The way an origin can escape the current scope.
  enum class EscapeKind : uint8_t {
    Return, /// Escapes via return statement.
    Field,  /// Escapes via assignment to a field.
    Global, /// Escapes via assignment to global storage.
  } EscKind;
 
  static bool classof(const Fact *F) {
    return F->getKind() == Kind::OriginEscapes;
  }
 
  OriginEscapesFact(OriginID OID, EscapeKind EscKind)
      : Fact(Kind::OriginEscapes), OID(OID), EscKind(EscKind) {}
  OriginID getEscapedOriginID() const { return OID; }
  EscapeKind getEscapeKind() const { return EscKind; }
};
 
/// Represents that an origin escapes via a return statement.
class ReturnEscapeFact : public OriginEscapesFact {
  const Expr *ReturnExpr;
 
public:
  ReturnEscapeFact(OriginID OID, const Expr *ReturnExpr)
      : OriginEscapesFact(OID, EscapeKind::Return), ReturnExpr(ReturnExpr) {}
 
  static bool classof(const Fact *F) {
    return F->getKind() == Kind::OriginEscapes &&
           static_cast<const OriginEscapesFact *>(F)->getEscapeKind() ==
               EscapeKind::Return;
  }
  const Expr *getReturnExpr() const { return ReturnExpr; };
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
/// Represents that an origin escapes via assignment to a field.
/// Example: `this->view = local_var;` where local_var outlives the assignment
/// but not the object containing the field.
class FieldEscapeFact : public OriginEscapesFact {
  const FieldDecl *FDecl;
 
public:
  FieldEscapeFact(OriginID OID, const FieldDecl *FDecl)
      : OriginEscapesFact(OID, EscapeKind::Field), FDecl(FDecl) {}
 
  static bool classof(const Fact *F) {
    return F->getKind() == Kind::OriginEscapes &&
           static_cast<const OriginEscapesFact *>(F)->getEscapeKind() ==
               EscapeKind::Field;
  }
  const FieldDecl *getFieldDecl() const { return FDecl; };
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
/// Represents that an origin escapes via assignment to global or static
/// storage. Example: `global_storage = local_var;`
class GlobalEscapeFact : public OriginEscapesFact {
  const VarDecl *Global;
 
public:
  GlobalEscapeFact(OriginID OID, const VarDecl *VDecl)
      : OriginEscapesFact(OID, EscapeKind::Global), Global(VDecl) {}
 
  static bool classof(const Fact *F) {
    return F->getKind() == Kind::OriginEscapes &&
           static_cast<const OriginEscapesFact *>(F)->getEscapeKind() ==
               EscapeKind::Global;
  }
  const VarDecl *getGlobal() const { return Global; };
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
class UseFact : public Fact {
  const Expr *UseExpr;
  const OriginList *OList;
  // True if this use is a write operation (e.g., left-hand side of assignment).
  // Write operations are exempted from use-after-free checks.
  bool IsWritten = false;
 
public:
  static bool classof(const Fact *F) { return F->getKind() == Kind::Use; }
 
  UseFact(const Expr *UseExpr, const OriginList *OList)
      : Fact(Kind::Use), UseExpr(UseExpr), OList(OList) {}
 
  const OriginList *getUsedOrigins() const { return OList; }
  void setUsedOrigins(const OriginList *NewList) { OList = NewList; }
  const Expr *getUseExpr() const { return UseExpr; }
  void markAsWritten() { IsWritten = true; }
  bool isWritten() const { return IsWritten; }
 
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
/// Represents that an origin's storage has been invalidated by a container
/// operation (e.g., vector::push_back may reallocate, invalidating iterators).
/// Created when a container method that may invalidate references/iterators
/// is called on the container.
class InvalidateOriginFact : public Fact {
  OriginID OID;
  const Expr *InvalidationExpr;
 
public:
  static bool classof(const Fact *F) {
    return F->getKind() == Kind::InvalidateOrigin;
  }
 
  InvalidateOriginFact(OriginID OID, const Expr *InvalidationExpr)
      : Fact(Kind::InvalidateOrigin), OID(OID),
        InvalidationExpr(InvalidationExpr) {}
 
  OriginID getInvalidatedOrigin() const { return OID; }
  const Expr *getInvalidationExpr() const { return InvalidationExpr; }
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
/// Top-level origin of the expression which was found to be moved, e.g, when
/// being used as an argument to an r-value reference parameter.
class MovedOriginFact : public Fact {
  const OriginID MovedOrigin;
  const Expr *MoveExpr;
 
public:
  static bool classof(const Fact *F) {
    return F->getKind() == Kind::MovedOrigin;
  }
 
  MovedOriginFact(const Expr *MoveExpr, OriginID MovedOrigin)
      : Fact(Kind::MovedOrigin), MovedOrigin(MovedOrigin), MoveExpr(MoveExpr) {}
 
  OriginID getMovedOrigin() const { return MovedOrigin; }
  const Expr *getMoveExpr() const { return MoveExpr; }
 
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
/// A dummy-fact used to mark a specific point in the code for testing.
/// It is generated by recognizing a `void("__lifetime_test_point_...")` cast.
class TestPointFact : public Fact {
  StringRef Annotation;
 
public:
  static bool classof(const Fact *F) { return F->getKind() == Kind::TestPoint; }
 
  explicit TestPointFact(StringRef Annotation)
      : Fact(Kind::TestPoint), Annotation(Annotation) {}
 
  StringRef getAnnotation() const { return Annotation; }
 
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
/// All loans are cleared from an origin (e.g., assigning a callable without
/// tracked origins to std::function).
class KillOriginFact : public Fact {
  OriginID OID;
 
public:
  static bool classof(const Fact *F) {
    return F->getKind() == Kind::KillOrigin;
  }
 
  KillOriginFact(OriginID OID) : Fact(Kind::KillOrigin), OID(OID) {}
 
  OriginID getKilledOrigin() const { return OID; }
 
  void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM,
            const LoanPropagationAnalysis *LPA = nullptr) const override;
};
 
class FactManager {
public:
  FactManager(const AnalysisDeclContext &AC, const CFG &Cfg) : OriginMgr(AC) {
    BlockToFacts.resize(Cfg.getNumBlockIDs());
  }
 
  llvm::ArrayRef<const Fact *> getFacts(const CFGBlock *B) const {
    return BlockToFacts[B->getBlockID()];
  }
 
  void addBlockFacts(const CFGBlock *B, llvm::ArrayRef<Fact *> NewFacts) {
    if (!NewFacts.empty())
      BlockToFacts[B->getBlockID()].assign(NewFacts.begin(), NewFacts.end());
  }
 
  void appendBlockFact(const CFGBlock *B, const Fact *F) {
    BlockToFacts[B->getBlockID()].push_back(F);
  }
 
  template <typename FactType, typename... Args>
  FactType *createFact(Args &&...args) {
    void *Mem = FactAllocator.Allocate<FactType>();
    FactType *Res = new (Mem) FactType(std::forward<Args>(args)...);
    Res->setID(NextFactID++);
    return Res;
  }
 
  void dump(const CFG &Cfg, AnalysisDeclContext &AC,
            const LoanPropagationAnalysis *LPA = nullptr) const;
 
  /// Retrieves program points that were specially marked in the source code
  /// for testing.
  ///
  /// The analysis recognizes special function calls of the form
  /// `void("__lifetime_test_point_<name>")` as test points. This method returns
  /// a map from the annotation string (<name>) to the corresponding
  /// `ProgramPoint`. This allows test harnesses to query the analysis state at
  /// user-defined locations in the code.
  /// \note This is intended for testing only.
  llvm::StringMap<ProgramPoint> getTestPoints() const;
  /// Retrieves all the facts in the block containing Program Point P.
  /// \note This is intended for testing only.
  llvm::ArrayRef<const Fact *> getBlockContaining(ProgramPoint P) const;
  size_t getBlockID(ProgramPoint P) const;
 
  unsigned getNumFacts() const { return NextFactID.Value; }
 
  /// Returns the origins that are referenced from more than one basic block.
  /// Only those need to survive block boundaries in the dataflow analyses; the
  /// rest are block-local.
  const llvm::BitVector &getPersistentOrigins() const {
    assert(PersistentOrigins.size() == OriginMgr.getNumOrigins() &&
           "persistent origins have not been computed");
    return PersistentOrigins;
  }
 
  LoanManager &getLoanMgr() { return LoanMgr; }
  const LoanManager &getLoanMgr() const { return LoanMgr; }
  OriginManager &getOriginMgr() { return OriginMgr; }
  const OriginManager &getOriginMgr() const { return OriginMgr; }
 
  void addCapturedField(const FieldDecl *FD) { CapturedFields.insert(FD); }
  bool isFieldCapturedByLambda(const FieldDecl *FD) const {
    return IsThisCapturedByLambda || CapturedFields.contains(FD);
  }
  void setThisCapturedByLambda() { IsThisCapturedByLambda = true; }
 
private:
  /// Classifies every origin as persistent or block-local. Called by
  /// `FactsGenerator` once all facts and origins have been created.
  void computePersistentOrigins(const CFG &Cfg);
 
  friend class FactsGenerator;
 
  FactID NextFactID{0};
  LoanManager LoanMgr;
  OriginManager OriginMgr;
  /// Facts for each CFG block, indexed by block ID.
  llvm::SmallVector<llvm::SmallVector<const Fact *>> BlockToFacts;
  llvm::BumpPtrAllocator FactAllocator;
  /// Bit vector indexed by origin ID. If set, the origin is referenced from
  /// more than one basic block and must participate in join operations. If
  /// unset, the origin is block-local and can be discarded at block
  /// boundaries.
  ///
  /// Shared by every analysis so that they all agree on which origins cross
  /// block boundaries.
  llvm::BitVector PersistentOrigins;
 
  /// Set of field declarations that are explicitly or init-captured in any
  /// lambda within the analyzed function.
  llvm::DenseSet<const FieldDecl *> CapturedFields;
  /// Whether the 'this' pointer is captured by any lambda within the analyzed
  /// function. When true, any field of 'this' is considered captured.
  bool IsThisCapturedByLambda = false;
};
} // namespace clang::lifetimes::internal
 
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_FACTS_H