llvm/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

//===- DataflowAnalysis.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 base types and functions for building dataflow analyses
//  that run over Control-Flow Graphs (CFGs).
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H

#include <iterator>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

#include "clang/AST/ASTContext.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/FlowSensitive/AdornedCFG.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "clang/Analysis/FlowSensitive/MatchSwitch.h"
#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
#include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Errc.h"
#include "llvm/Support/Error.h"

namespace clang {
namespace dataflow {

/// Base class template for dataflow analyses built on a single lattice type.
///
/// Requirements:
///
///  `Derived` must be derived from a specialization of this class template and
///  must provide the following public members:
///   * `LatticeT initialElement()` - returns a lattice element that models the
///     initial state of a basic block;
///   * `void transfer(const CFGElement &, LatticeT &, Environment &)` - applies
///     the analysis transfer function for a given CFG element and lattice
///     element.
///
///  `Derived` can optionally provide the following members:
///  * `void transferBranch(bool Branch, const Stmt *Stmt, TypeErasedLattice &E,
///                         Environment &Env)` - applies the analysis transfer
///    function for a given edge from a CFG block of a conditional statement.
///
///  `Derived` can optionally override the virtual functions in the
///  `Environment::ValueModel` interface (which is an indirect base class of
///  this class).
///
///  `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
///  provide the following public members:
///   * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
///     argument by computing their least upper bound, modifies the object if
///     necessary, and returns an effect indicating whether any changes were
///     made to it;
///     FIXME: make it `static LatticeT join(const LatticeT&, const LatticeT&)`
///   * `bool operator==(const LatticeT &) const` - returns true if and only if
///     the object is equal to the argument.
///
/// `LatticeT` can optionally provide the following members:
///  * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the
///    lattice element 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 with the returned
///    `LatticeJoinEffect`.
template <typename Derived, typename LatticeT>
class DataflowAnalysis : public TypeErasedDataflowAnalysis { … };

// Model of the program at a given program point.
template <typename LatticeT> struct DataflowAnalysisState { … };

/// A callback to be called with the state before or after visiting a CFG
/// element.
CFGEltCallback;

/// A pair of callbacks to be called with the state before and after visiting a
/// CFG element.
/// Either or both of the callbacks may be null.
template <typename AnalysisT> struct CFGEltCallbacks { … };

/// A callback for performing diagnosis on a CFG element, called with the state
/// before or after visiting that CFG element. Returns a list of diagnostics
/// to emit (if any).
DiagnosisCallback;

/// A pair of callbacks for performing diagnosis on a CFG element, called with
/// the state before and after visiting that CFG element.
/// Either or both of the callbacks may be null.
template <typename AnalysisT, typename Diagnostic> struct DiagnosisCallbacks { … };

/// Default for the maximum number of SAT solver iterations during analysis.
inline constexpr std::int64_t kDefaultMaxSATIterations = …;

/// Default for the maximum number of block visits during analysis.
inline constexpr std::int32_t kDefaultMaxBlockVisits = …;

/// Performs dataflow analysis and returns a mapping from basic block IDs to
/// dataflow analysis states that model the respective basic blocks. The
/// returned vector, if any, will have the same size as the number of CFG
/// blocks, with indices corresponding to basic block IDs. Returns an error if
/// the dataflow analysis cannot be performed successfully. Otherwise, calls
/// `PostAnalysisCallbacks` on each CFG element with the final analysis results
/// before and after that program point.
///
/// `MaxBlockVisits` caps the number of block visits during analysis. See
/// `runTypeErasedDataflowAnalysis` for a full description. The default value is
/// essentially arbitrary -- large enough to accommodate what seems like any
/// reasonable CFG, but still small enough to limit the cost of hitting the
/// limit.
template <typename AnalysisT>
llvm::Expected<std::vector<
    std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
runDataflowAnalysis(const AdornedCFG &ACFG, AnalysisT &Analysis,
                    const Environment &InitEnv,
                    CFGEltCallbacks<AnalysisT> PostAnalysisCallbacks = { … }

// Create an analysis class that is derived from `DataflowAnalysis`. This is an
// SFINAE adapter that allows us to call two different variants of constructor
// (either with or without the optional `Environment` parameter).
// FIXME: Make all classes derived from `DataflowAnalysis` take an `Environment`
// parameter in their constructor so that we can get rid of this abomination.
template <typename AnalysisT>
auto createAnalysis(ASTContext &ASTCtx, Environment &Env)
    -> decltype(AnalysisT(ASTCtx, Env)) { … }
template <typename AnalysisT>
auto createAnalysis(ASTContext &ASTCtx, Environment &Env)
    -> decltype(AnalysisT(ASTCtx)) { … }

/// Runs a dataflow analysis over the given function and then runs `Diagnoser`
/// over the results. Returns a list of diagnostics for `FuncDecl` or an
/// error. Currently, errors can occur (at least) because the analysis requires
/// too many iterations over the CFG or the SAT solver times out.
///
/// The default value of `MaxSATIterations` was chosen based on the following
/// observations:
/// - Non-pathological calls to the solver typically require only a few hundred
///   iterations.
/// - This limit is still low enough to keep runtimes acceptable (on typical
///   machines) in cases where we hit the limit.
///
/// `MaxBlockVisits` caps the number of block visits during analysis. See
/// `runDataflowAnalysis` for a full description and explanation of the default
/// value.
template <typename AnalysisT, typename Diagnostic>
llvm::Expected<llvm::SmallVector<Diagnostic>>
diagnoseFunction(const FunctionDecl &FuncDecl, ASTContext &ASTCtx,
                 DiagnosisCallbacks<AnalysisT, Diagnostic> Diagnoser,
                 std::int64_t MaxSATIterations = kDefaultMaxSATIterations,
                 std::int32_t MaxBlockVisits = kDefaultMaxBlockVisits) { … }

/// Overload that takes only one diagnosis callback, which is run on the state
/// after visiting the `CFGElement`. This is provided for backwards
/// compatibility; new callers should call the overload taking
/// `DiagnosisCallbacks` instead.
template <typename AnalysisT, typename Diagnostic>
llvm::Expected<llvm::SmallVector<Diagnostic>>
diagnoseFunction(const FunctionDecl &FuncDecl, ASTContext &ASTCtx,
                 DiagnosisCallback<AnalysisT, Diagnostic> Diagnoser,
                 std::int64_t MaxSATIterations = kDefaultMaxSATIterations,
                 std::int32_t MaxBlockVisits = kDefaultMaxBlockVisits) { … }

/// Abstract base class for dataflow "models": reusable analysis components that
/// model a particular aspect of program semantics in the `Environment`. For
/// example, a model may capture a type and its related functions.
class DataflowModel : public Environment::ValueModel { … };

} // namespace dataflow
} // namespace clang

#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H