blob: 975d618e99edc5cf8e9bd0e7826d2d5d301665d0 [file] [log] [blame]
//===- DataflowAnalysis.h ---------------------------------------*- C++ -*-===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See 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).
#include <iterator>
#include <utility>
#include <vector>
#include "clang/AST/ASTContext.h"
#include "clang/AST/Stmt.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
#include "llvm/ADT/Any.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.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;
/// * `LatticeT transfer(const Stmt *, const LatticeT &, Environment &)` -
/// applies the analysis transfer function for a given statement and lattice
/// element.
/// `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;
/// * `bool operator==(const LatticeT &) const` - returns true if and only if
/// the object is equal to the argument.
template <typename Derived, typename LatticeT>
class DataflowAnalysis : public TypeErasedDataflowAnalysis {
/// Bounded join-semilattice that is used in the analysis.
using Lattice = LatticeT;
explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
ASTContext &getASTContext() final { return Context; }
AnyLatticeElement typeErasedInitialElement() final {
return {static_cast<Derived *>(this)->initialElement()};
LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
const TypeErasedLattice &E2) final {
Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
return L1.join(L2);
bool isEqualTypeErased(const TypeErasedLattice &E1,
const TypeErasedLattice &E2) final {
const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
return L1 == L2;
AnyLatticeElement transferTypeErased(const Stmt *Stmt,
const AnyLatticeElement &E,
Environment &Env) final {
const Lattice &L = llvm::any_cast<const Lattice &>(E.Value);
return {static_cast<Derived *>(this)->transfer(Stmt, L, Env)};
ASTContext &Context;
// Model of the program at a given program point.
template <typename LatticeT> struct DataflowAnalysisState {
// Model of a program property.
LatticeT Lattice;
// Model of the state of the program (store and heap).
Environment Env;
/// Performs dataflow analysis and returns a mapping from basic block IDs to
/// dataflow analysis states that model the respective basic blocks. Indices
/// of the returned vector correspond to basic block IDs.
/// Requirements:
/// `Cfg` must have been built with `CFG::BuildOptions::setAllAlwaysAdd()` to
/// ensure that all sub-expressions in a basic block are evaluated.
template <typename AnalysisT>
std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
runDataflowAnalysis(const CFG &Cfg, AnalysisT &Analysis,
const Environment &InitEnv) {
auto TypeErasedBlockStates =
runTypeErasedDataflowAnalysis(Cfg, Analysis, InitEnv);
llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
std::back_inserter(BlockStates), [](auto &OptState) {
return std::move(OptState).map([](auto &&State) {
return DataflowAnalysisState<typename AnalysisT::Lattice>{
llvm::any_cast<typename AnalysisT::Lattice>(
return BlockStates;
} // namespace dataflow
} // namespace clang