DataflowEnvironment.cpp | Explore in Territory

//===-- DataflowEnvironment.cpp ---------------------------------*- 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.
//
//===----------------------------------------------------------------------===//

#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/AST/Stmt.h"
#include "clang/AST/Type.h"
#include "clang/Analysis/FlowSensitive/ASTOps.h"
#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "clang/Analysis/FlowSensitive/Value.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include <cassert>
#include <memory>
#include <utility>

#define DEBUG_TYPE …

namespace clang {
namespace dataflow {

// FIXME: convert these to parameters of the analysis or environment. Current
// settings have been experimentaly validated, but only for a particular
// analysis.
static constexpr int MaxCompositeValueDepth = …;
static constexpr int MaxCompositeValueSize = …;

/// Returns a map consisting of key-value entries that are present in both maps.
static llvm::DenseMap<const ValueDecl *, StorageLocation *> intersectDeclToLoc(
    const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1,
    const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) { … }

// Performs a join on either `ExprToLoc` or `ExprToVal`.
// The maps must be consistent in the sense that any entries for the same
// expression must map to the same location / value. This is the case if we are
// performing a join for control flow within a full-expression (which is the
// only case when this function should be used).
template <typename MapT> MapT joinExprMaps(const MapT &Map1, const MapT &Map2) { … }

// Whether to consider equivalent two values with an unknown relation.
//
// FIXME: this function is a hack enabling unsoundness to support
// convergence. Once we have widening support for the reference/pointer and
// struct built-in models, this should be unconditionally `false` (and inlined
// as such at its call sites).
static bool equateUnknownValues(Value::Kind K) { … }

static bool compareDistinctValues(QualType Type, Value &Val1,
                                  const Environment &Env1, Value &Val2,
                                  const Environment &Env2,
                                  Environment::ValueModel &Model) { … }

/// Attempts to join distinct values `Val1` and `Val2` in `Env1` and `Env2`,
/// respectively, of the same type `Type`. Joining generally produces a single
/// value that (soundly) approximates the two inputs, although the actual
/// meaning depends on `Model`.
static Value *joinDistinctValues(QualType Type, Value &Val1,
                                 const Environment &Env1, Value &Val2,
                                 const Environment &Env2,
                                 Environment &JoinedEnv,
                                 Environment::ValueModel &Model) { … }

static WidenResult widenDistinctValues(QualType Type, Value &Prev,
                                       const Environment &PrevEnv,
                                       Value &Current, Environment &CurrentEnv,
                                       Environment::ValueModel &Model) { … }

// Returns whether the values in `Map1` and `Map2` compare equal for those
// keys that `Map1` and `Map2` have in common.
template <typename Key>
bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1,
                           const llvm::MapVector<Key, Value *> &Map2,
                           const Environment &Env1, const Environment &Env2,
                           Environment::ValueModel &Model) { … }

// Perform a join on two `LocToVal` maps.
static llvm::MapVector<const StorageLocation *, Value *>
joinLocToVal(const llvm::MapVector<const StorageLocation *, Value *> &LocToVal,
             const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2,
             const Environment &Env1, const Environment &Env2,
             Environment &JoinedEnv, Environment::ValueModel &Model) { … }

// Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either
// `const StorageLocation *` or `const Expr *`.
template <typename Key>
llvm::MapVector<Key, Value *>
widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap,
                   const llvm::MapVector<Key, Value *> &PrevMap,
                   Environment &CurEnv, const Environment &PrevEnv,
                   Environment::ValueModel &Model, LatticeEffect &Effect) { … }

namespace {

// Visitor that builds a map from record prvalues to result objects.
// For each result object that it encounters, it propagates the storage location
// of the result object to all record prvalues that can initialize it.
class ResultObjectVisitor : public AnalysisASTVisitor<ResultObjectVisitor> { … };

} // namespace

void Environment::initialize() { … }

// FIXME: Add support for resetting globals after function calls to enable the
// implementation of sound analyses.

void Environment::initFieldsGlobalsAndFuncs(const ReferencedDecls &Referenced) { … }

Environment Environment::fork() const { … }

bool Environment::canDescend(unsigned MaxDepth,
                             const FunctionDecl *Callee) const { … }

Environment Environment::pushCall(const CallExpr *Call) const { … }

Environment Environment::pushCall(const CXXConstructExpr *Call) const { … }

void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
                                   ArrayRef<const Expr *> Args) { … }

void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) { … }

void Environment::popCall(const CXXConstructExpr *Call,
                          const Environment &CalleeEnv) { … }

bool Environment::equivalentTo(const Environment &Other,
                               Environment::ValueModel &Model) const { … }

LatticeEffect Environment::widen(const Environment &PrevEnv,
                                 Environment::ValueModel &Model) { … }

Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
                              Environment::ValueModel &Model,
                              ExprJoinBehavior ExprBehavior) { … }

Value *Environment::joinValues(QualType Ty, Value *Val1,
                               const Environment &Env1, Value *Val2,
                               const Environment &Env2, Environment &JoinedEnv,
                               Environment::ValueModel &Model) { … }

StorageLocation &Environment::createStorageLocation(QualType Type) { … }

StorageLocation &Environment::createStorageLocation(const ValueDecl &D) { … }

StorageLocation &Environment::createStorageLocation(const Expr &E) { … }

void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { … }

StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const { … }

void Environment::removeDecl(const ValueDecl &D) { … }

void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) { … }

StorageLocation *Environment::getStorageLocation(const Expr &E) const { … }

RecordStorageLocation &
Environment::getResultObjectLocation(const Expr &RecordPRValue) const { … }

PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) { … }

void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc,
                                             QualType Type) { … }

void Environment::setValue(const StorageLocation &Loc, Value &Val) { … }

void Environment::setValue(const Expr &E, Value &Val) { … }

Value *Environment::getValue(const StorageLocation &Loc) const { … }

Value *Environment::getValue(const ValueDecl &D) const { … }

Value *Environment::getValue(const Expr &E) const { … }

Value *Environment::createValue(QualType Type) { … }

Value *Environment::createValueUnlessSelfReferential(
    QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
    int &CreatedValuesCount) { … }

StorageLocation &
Environment::createLocAndMaybeValue(QualType Ty,
                                    llvm::DenseSet<QualType> &Visited,
                                    int Depth, int &CreatedValuesCount) { … }

void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc,
                                             QualType Type,
                                             llvm::DenseSet<QualType> &Visited,
                                             int Depth,
                                             int &CreatedValuesCount) { … }

StorageLocation &Environment::createObjectInternal(const ValueDecl *D,
                                                   QualType Ty,
                                                   const Expr *InitExpr) { … }

void Environment::assume(const Formula &F) { … }

bool Environment::proves(const Formula &F) const { … }

bool Environment::allows(const Formula &F) const { … }

void Environment::dump(raw_ostream &OS) const { … }

void Environment::dump() const { … }

Environment::PrValueToResultObject Environment::buildResultObjectMap(
    DataflowAnalysisContext *DACtx, const FunctionDecl *FuncDecl,
    RecordStorageLocation *ThisPointeeLoc,
    RecordStorageLocation *LocForRecordReturnVal) { … }

Environment::PrValueToResultObject Environment::buildResultObjectMap(
    DataflowAnalysisContext *DACtx, Stmt *S,
    RecordStorageLocation *ThisPointeeLoc,
    RecordStorageLocation *LocForRecordReturnVal) { … }

RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
                                                 const Environment &Env) { … }

RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
                                             const Environment &Env) { … }

} // namespace dataflow
} // namespace clang
llvm/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
