Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===-- DataflowEnvironment.h -----------------------------------*- 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 an Environment class that is used by dataflow analyses

//  that run over Control-Flow Graphs (CFGs) to keep track of the state of the

//  program at given program points.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

#include "clang/AST/Decl.h"

#include "clang/AST/DeclBase.h"

#include "clang/AST/Expr.h"

#include "clang/AST/Type.h"

#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"

#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"

#include "clang/Analysis/FlowSensitive/DataflowLattice.h"

#include "clang/Analysis/FlowSensitive/StorageLocation.h"

#include "clang/Analysis/FlowSensitive/Value.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/DenseSet.h"

#include "llvm/Support/ErrorHandling.h"

#include <memory>

#include <type_traits>

#include <utility>

namespace clang {

namespace dataflow {

/// Indicates what kind of indirections should be skipped past when retrieving

/// storage locations or values.

///

/// FIXME: Consider renaming this or replacing it with a more appropriate model.

/// See the discussion in https://reviews.llvm.org/D116596 for context.

enum class SkipPast {

  /// No indirections should be skipped past.

  None,

  /// An optional reference should be skipped past.

  Reference,

  /// An optional reference should be skipped past, then an optional pointer

  /// should be skipped past.

  ReferenceThenPointer,

};

/// Indicates the result of a tentative comparison.

enum class ComparisonResult {

  Same,

  Different,

  Unknown,

};

/// Holds the state of the program (store and heap) at a given program point.

///

/// WARNING: Symbolic values that are created by the environment for static

/// local and global variables are not currently invalidated on function calls.

/// This is unsound and should be taken into account when designing dataflow

/// analyses.

class Environment {

public:

  /// Supplements `Environment` with non-standard comparison and join

  /// operations.

  class ValueModel {

  public:

    virtual ~ValueModel() = default;

    /// Returns:

    ///   `Same`: `Val1` is equivalent to `Val2`, according to the model.

    ///   `Different`: `Val1` is distinct from `Val2`, according to the model.

    ///   `Unknown`: The model can't determine a relationship between `Val1` and

    ///    `Val2`.

    ///

    /// Requirements:

    ///

    ///  `Val1` and `Val2` must be distinct.

    ///

    ///  `Val1` and `Val2` must model values of type `Type`.

    ///

    ///  `Val1` and `Val2` must be assigned to the same storage location in

    ///  `Env1` and `Env2` respectively.

    virtual ComparisonResult compare(QualType Type, const Value &Val1,

                                     const Environment &Env1, const Value &Val2,

                                     const Environment &Env2) {

      // FIXME: Consider adding QualType to StructValue and removing the Type

      // argument here.

      return ComparisonResult::Unknown;

    }

    /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could

    /// be a strict lattice join or a more general widening operation.

    ///

    /// If this function returns true, `MergedVal` will be assigned to a storage

    /// location of type `Type` in `MergedEnv`.

    ///

    /// `Env1` and `Env2` can be used to query child values and path condition

    /// implications of `Val1` and `Val2` respectively.

    ///

    /// Requirements:

    ///

    ///  `Val1` and `Val2` must be distinct.

    ///

    ///  `Val1`, `Val2`, and `MergedVal` must model values of type `Type`.

    ///

    ///  `Val1` and `Val2` must be assigned to the same storage location in

    ///  `Env1` and `Env2` respectively.

    virtual bool merge(QualType Type, const Value &Val1,

                       const Environment &Env1, const Value &Val2,

                       const Environment &Env2, Value &MergedVal,

                       Environment &MergedEnv) {

      return true;

    }

    /// This function may widen the current value -- replace it with an

    /// approximation that can reach a fixed point more quickly than iterated

    /// application of the transfer function alone. The previous value is

    /// provided to inform the choice of widened value. The function must also

    /// serve as a comparison operation, by indicating whether the widened value

    /// is equivalent to the previous value.

    ///

    /// Returns either:

    ///

    ///   `nullptr`, if this value is not of interest to the model, or

    ///

    ///   `&Prev`, if the widened value is equivalent to `Prev`, or

    ///

    ///   A non-null value that approximates `Current`. `Prev` is available to

    ///   inform the chosen approximation.

    ///

    /// `PrevEnv` and `CurrentEnv` can be used to query child values and path

    /// condition implications of `Prev` and `Current`, respectively.

    ///

    /// Requirements:

    ///

    ///  `Prev` and `Current` must model values of type `Type`.

    ///

    ///  `Prev` and `Current` must be assigned to the same storage location in

    ///  `PrevEnv` and `CurrentEnv`, respectively.

    virtual Value *widen(QualType Type, Value &Prev, const Environment &PrevEnv,

                         Value &Current, Environment &CurrentEnv) {

      // The default implementation reduces to just comparison, since comparison

      // is required by the API, even if no widening is performed.

      switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) {

        case ComparisonResult::Same:

          return &Prev;

        case ComparisonResult::Different:

          return &Current;

        case ComparisonResult::Unknown:

          return nullptr;

      }

      llvm_unreachable("all cases in switch covered");

    }

  };

  /// Creates an environment that uses `DACtx` to store objects that encompass

  /// the state of a program.

  explicit Environment(DataflowAnalysisContext &DACtx);

  Environment(const Environment &Other);

  Environment &operator=(const Environment &Other);

  Environment(Environment &&Other) = default;

  Environment &operator=(Environment &&Other) = default;

  /// Creates an environment that uses `DACtx` to store objects that encompass

  /// the state of a program.

  ///

  /// If `DeclCtx` is a function, initializes the environment with symbolic

  /// representations of the function parameters.

  ///

  /// If `DeclCtx` is a non-static member function, initializes the environment

  /// with a symbolic representation of the `this` pointee.

  Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);

  const DataflowAnalysisContext::Options &getAnalysisOptions() {

    return DACtx->getOptions();

  }

  /// Creates and returns an environment to use for an inline analysis  of the

  /// callee. Uses the storage location from each argument in the `Call` as the

  /// storage location for the corresponding parameter in the callee.

  ///

  /// Requirements:

  ///

  ///  The callee of `Call` must be a `FunctionDecl`.

  ///

  ///  The body of the callee must not reference globals.

  ///

  ///  The arguments of `Call` must map 1:1 to the callee's parameters.

  Environment pushCall(const CallExpr *Call) const;

  Environment pushCall(const CXXConstructExpr *Call) const;

  /// Moves gathered information back into `this` from a `CalleeEnv` created via

  /// `pushCall`.

  void popCall(const Environment &CalleeEnv);

  /// Returns true if and only if the environment is equivalent to `Other`, i.e

  /// the two environments:

  ///  - have the same mappings from declarations to storage locations,

  ///  - have the same mappings from expressions to storage locations,

  ///  - have the same or equivalent (according to `Model`) values assigned to

  ///    the same storage locations.

  ///

  /// Requirements:

  ///

  ///  `Other` and `this` must use the same `DataflowAnalysisContext`.

  bool equivalentTo(const Environment &Other,

                    Environment::ValueModel &Model) const;

  /// Joins the environment with `Other` by taking the intersection of storage

  /// locations and values that are stored in them. Distinct values that are

  /// assigned to the same storage locations in the environment and `Other` are

  /// merged using `Model`.

  ///

  /// Requirements:

  ///

  ///  `Other` and `this` must use the same `DataflowAnalysisContext`.

  LatticeJoinEffect join(const Environment &Other,

                         Environment::ValueModel &Model);

  /// Widens the environment point-wise, using `PrevEnv` as needed to inform the

  /// approximation.

  ///

  /// Requirements:

  ///

  ///  `PrevEnv` must be the immediate previous version of the environment.

  ///  `PrevEnv` and `this` must use the same `DataflowAnalysisContext`.

  LatticeJoinEffect widen(const Environment &PrevEnv,

                          Environment::ValueModel &Model);

  // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,

  // `getStableStorageLocation`, or something more appropriate.

  /// Creates a storage location appropriate for `Type`. Does not assign a value

  /// to the returned storage location in the environment.

  ///

  /// Requirements:

  ///

  ///  `Type` must not be null.

  StorageLocation &createStorageLocation(QualType Type);

  /// Creates a storage location for `D`. Does not assign the returned storage

  /// location to `D` in the environment. Does not assign a value to the

  /// returned storage location in the environment.

  StorageLocation &createStorageLocation(const VarDecl &D);

  /// Creates a storage location for `E`. Does not assign the returned storage

  /// location to `E` in the environment. Does not assign a value to the

  /// returned storage location in the environment.

  StorageLocation &createStorageLocation(const Expr &E);

  /// Assigns `Loc` as the storage location of `D` in the environment.

  ///

  /// Requirements:

  ///

  ///  `D` must not be assigned a storage location in the environment.

  void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);

  /// Returns the storage location assigned to `D` in the environment, applying

  /// the `SP` policy for skipping past indirections, or null if `D` isn't

  /// assigned a storage location in the environment.

  StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const;

  /// Assigns `Loc` as the storage location of `E` in the environment.

  ///

  /// Requirements:

  ///

  ///  `E` must not be assigned a storage location in the environment.

  void setStorageLocation(const Expr &E, StorageLocation &Loc);

  /// Returns the storage location assigned to `E` in the environment, applying

  /// the `SP` policy for skipping past indirections, or null if `E` isn't

  /// assigned a storage location in the environment.

  StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const;

  /// Returns the storage location assigned to the `this` pointee in the

  /// environment or null if the `this` pointee has no assigned storage location

  /// in the environment.

  StorageLocation *getThisPointeeStorageLocation() const;

  /// Returns the storage location of the return value or null, if unset.

  StorageLocation *getReturnStorageLocation() const;

  /// Returns a pointer value that represents a null pointer. Calls with

  /// `PointeeType` that are canonically equivalent will return the same result.

  PointerValue &getOrCreateNullPointerValue(QualType PointeeType);

  /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise

  /// return null. If `Type` is a pointer or reference type, creates all the

  /// necessary storage locations and values for indirections until it finds a

  /// non-pointer/non-reference type.

  ///

  /// Requirements:

  ///

  ///  `Type` must not be null.

  Value *createValue(QualType Type);

  /// Assigns `Val` as the value of `Loc` in the environment.

  void setValue(const StorageLocation &Loc, Value &Val);

  /// Returns the value assigned to `Loc` in the environment or null if `Loc`

  /// isn't assigned a value in the environment.

  Value *getValue(const StorageLocation &Loc) const;

  /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`

  /// is assigned a storage location in the environment, otherwise returns null.

  Value *getValue(const ValueDecl &D, SkipPast SP) const;

  /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`

  /// is assigned a storage location in the environment, otherwise returns null.

  Value *getValue(const Expr &E, SkipPast SP) const;

  /// Transfers ownership of `Loc` to the analysis context and returns a

  /// reference to it.

  ///

  /// Requirements:

  ///

  ///  `Loc` must not be null.

  template <typename T>

  std::enable_if_t<std::is_base_of<StorageLocation, T>::value, T &>

  takeOwnership(std::unique_ptr<T> Loc) {

    return DACtx->takeOwnership(std::move(Loc));

  }

  /// Transfers ownership of `Val` to the analysis context and returns a

  /// reference to it.

  ///

  /// Requirements:

  ///

  ///  `Val` must not be null.

  template <typename T>

  std::enable_if_t<std::is_base_of<Value, T>::value, T &>

  takeOwnership(std::unique_ptr<T> Val) {

    return DACtx->takeOwnership(std::move(Val));

  }

  /// Returns a symbolic boolean value that models a boolean literal equal to

  /// `Value`

  AtomicBoolValue &getBoolLiteralValue(bool Value) const {

    return DACtx->getBoolLiteralValue(Value);

  }

  /// Returns an atomic boolean value.

  BoolValue &makeAtomicBoolValue() const {

    return DACtx->createAtomicBoolValue();

  }

  /// Returns a unique instance of boolean Top.

  BoolValue &makeTopBoolValue() const {

    return DACtx->createTopBoolValue();

  }

  /// Returns a boolean value that represents the conjunction of `LHS` and

  /// `RHS`. Subsequent calls with the same arguments, regardless of their

  /// order, will return the same result. If the given boolean values represent

  /// the same value, the result will be the value itself.

  BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const {

    return DACtx->getOrCreateConjunction(LHS, RHS);

  }

  /// Returns a boolean value that represents the disjunction of `LHS` and

  /// `RHS`. Subsequent calls with the same arguments, regardless of their

  /// order, will return the same result. If the given boolean values represent

  /// the same value, the result will be the value itself.

  BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const {

    return DACtx->getOrCreateDisjunction(LHS, RHS);

  }

  /// Returns a boolean value that represents the negation of `Val`. Subsequent

  /// calls with the same argument will return the same result.

  BoolValue &makeNot(BoolValue &Val) const {

    return DACtx->getOrCreateNegation(Val);

  }

  /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with

  /// the same arguments, will return the same result. If the given boolean

  /// values represent the same value, the result will be a value that

  /// represents the true boolean literal.

  BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const {

    return DACtx->getOrCreateImplication(LHS, RHS);

  }

  /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with

  /// the same arguments, regardless of their order, will return the same

  /// result. If the given boolean values represent the same value, the result

  /// will be a value that represents the true boolean literal.

  BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const {

    return DACtx->getOrCreateIff(LHS, RHS);

  }

  /// Returns the token that identifies the flow condition of the environment.

  AtomicBoolValue &getFlowConditionToken() const { return *FlowConditionToken; }

  /// Builds and returns the logical formula defining the flow condition

  /// identified by `Token`. If a value in the formula is present as a key in

  /// `Substitutions`, it will be substituted with the value it maps to.

  BoolValue &buildAndSubstituteFlowCondition(

      AtomicBoolValue &Token,

      llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) {

    return DACtx->buildAndSubstituteFlowCondition(Token,

                                                  std::move(Substitutions));

  }

  /// Adds `Val` to the set of clauses that constitute the flow condition.

  void addToFlowCondition(BoolValue &Val);

  /// Returns true if and only if the clauses that constitute the flow condition

  /// imply that `Val` is true.

  bool flowConditionImplies(BoolValue &Val) const;

  /// Returns the `DeclContext` of the block being analysed, if any. Otherwise,

  /// returns null.

  const DeclContext *getDeclCtx() const { return CallStack.back(); }

  /// Returns whether this `Environment` can be extended to analyze the given

  /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a

  /// given `MaxDepth`.

  bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const;

  /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise,

  /// returns null.

  const ControlFlowContext *getControlFlowContext(const FunctionDecl *F) {

    return DACtx->getControlFlowContext(F);

  }

  LLVM_DUMP_METHOD void dump() const;

  LLVM_DUMP_METHOD void dump(raw_ostream &OS) const;

private:

  /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise

  /// return null.

  ///

  /// Recursively initializes storage locations and values until it sees a

  /// self-referential pointer or reference type. `Visited` is used to track

  /// which types appeared in the reference/pointer chain in order to avoid

  /// creating a cyclic dependency with self-referential pointers/references.

  ///

  /// Requirements:

  ///

  ///  `Type` must not be null.

  Value *createValueUnlessSelfReferential(QualType Type,

                                          llvm::DenseSet<QualType> &Visited,

                                          int Depth, int &CreatedValuesCount);

  StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;

  const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;

  /// Shared implementation of `pushCall` overloads. Note that unlike

  /// `pushCall`, this member is invoked on the environment of the callee, not

  /// of the caller.

  void pushCallInternal(const FunctionDecl *FuncDecl,

                        ArrayRef<const Expr *> Args);

  /// Assigns storage locations and values to all variables in `Vars`.

  void initVars(llvm::DenseSet<const VarDecl *> Vars);

  // `DACtx` is not null and not owned by this object.

  DataflowAnalysisContext *DACtx;

  // FIXME: move the fields `CallStack`, `ReturnLoc` and `ThisPointeeLoc` into a

  // separate call-context object, shared between environments in the same call.

  // https://github.com/llvm/llvm-project/issues/59005

  // `DeclContext` of the block being analysed if provided.

  std::vector<const DeclContext *> CallStack;

  // In a properly initialized `Environment`, `ReturnLoc` should only be null if

  // its `DeclContext` could not be cast to a `FunctionDecl`.

  StorageLocation *ReturnLoc = nullptr;

  // The storage location of the `this` pointee. Should only be null if the

  // function being analyzed is only a function and not a method.

  StorageLocation *ThisPointeeLoc = nullptr;

  // Maps from program declarations and statements to storage locations that are

  // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these

  // include only storage locations that are in scope for a particular basic

  // block.

  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;

  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;

  llvm::DenseMap<const StorageLocation *, Value *> LocToVal;

  // Maps locations of struct members to symbolic values of the structs that own

  // them and the decls of the struct members.

  llvm::DenseMap<const StorageLocation *,

                 std::pair<StructValue *, const ValueDecl *>>

      MemberLocToStruct;

  AtomicBoolValue *FlowConditionToken;

};

} // namespace dataflow

} // namespace clang

#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H