14#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
15#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
31#include "llvm/ADT/STLExtras.h"
32#include "llvm/ADT/STLFunctionalExtras.h"
33#include "llvm/ADT/SmallVector.h"
34#include "llvm/Support/Errc.h"
35#include "llvm/Support/Error.h"
79template <
typename Derived,
typename LatticeT>
94 return {
static_cast<Derived *
>(
this)->initialElement()};
100 Lattice L1 = llvm::any_cast<const Lattice &>(E1.Value);
101 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
103 return {std::move(L1)};
108 Lattice &
C = llvm::any_cast<Lattice &>(Current.Value);
110 return widenInternal(Rank0{},
C,
P);
115 const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
116 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
122 Lattice &L = llvm::any_cast<Lattice &>(E.Value);
123 static_cast<Derived *
>(
this)->
transfer(Element, L,
Env);
128 transferBranchInternal(Rank0{}, *
static_cast<Derived *
>(
this), Branch,
Stmt,
136 struct Rank0 : Rank1 {};
139 template <
typename T>
140 static auto widenInternal(Rank0,
T &Current,
const T &Prev)
141 ->
decltype(Current.widen(Prev)) {
142 return Current.widen(Prev);
155 template <
typename Analysis>
156 static auto transferBranchInternal(Rank0,
Analysis &A,
bool Branch,
157 const Stmt *Stmt, TypeErasedLattice &L,
159 -> std::void_t<
decltype(A.transferBranch(
160 Branch, Stmt, std::declval<LatticeT &>(),
Env))> {
161 A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value),
Env);
165 template <
typename Analysis>
166 static void transferBranchInternal(Rank1,
Analysis &A,
bool,
const Stmt *,
167 TypeErasedLattice &, Environment &) {}
194template <
typename AnalysisT>
196 std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
200 typename AnalysisT::Lattice> &)>
201 PostVisitCFG =
nullptr,
202 std::int32_t MaxBlockVisits = 20'000) {
205 PostVisitCFGClosure =
nullptr;
207 PostVisitCFGClosure = [&PostVisitCFG](
211 llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
215 *Lattice, State.Env.fork()});
221 if (!TypeErasedBlockStates)
222 return TypeErasedBlockStates.takeError();
224 std::vector<std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
226 BlockStates.reserve(TypeErasedBlockStates->size());
229 std::move(*TypeErasedBlockStates), std::back_inserter(
BlockStates),
231 return llvm::transformOptional(
234 llvm::any_cast<typename AnalysisT::Lattice>(
235 std::move(State.Lattice.Value)),
236 std::move(State.Env)};
247template <
typename AnalysisT>
249 ->
decltype(AnalysisT(ASTCtx,
Env)) {
250 return AnalysisT(ASTCtx,
Env);
252template <
typename AnalysisT>
254 ->
decltype(AnalysisT(ASTCtx)) {
255 return AnalysisT(ASTCtx);
273template <
typename AnalysisT,
typename Diagnostic>
280 std::int64_t MaxSATIterations = 1'000'000'000,
281 std::int32_t MaxBlockVisits = 20'000) {
284 return Context.takeError();
286 auto OwnedSolver = std::make_unique<WatchedLiteralsSolver>(MaxSATIterations);
290 AnalysisT
Analysis = createAnalysis<AnalysisT>(ASTCtx,
Env);
292 if (llvm::Error Err =
295 [&ASTCtx, &Diagnoser, &Diagnostics](
298 auto EltDiagnostics = Diagnoser(
301 llvm::any_cast<const typename AnalysisT::Lattice &>(
302 State.Lattice.Value),
304 llvm::move(EltDiagnostics, std::back_inserter(Diagnostics));
308 return std::move(Err);
310 if (
Solver->reachedLimit())
311 return llvm::createStringError(llvm::errc::interrupted,
312 "SAT solver timed out");
Defines the clang::ASTContext interface.
llvm::ArrayRef< std::optional< TypeErasedDataflowAnalysisState > > BlockStates
Stores the state of a CFG block if it has been evaluated by the analysis.
const Environment & InitEnv
Initial state to start the analysis.
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Represents a top-level expression in a basic block.
Represents a function declaration or definition.
Stmt - This represents one statement.
Holds CFG with additional information derived from it that is needed to perform dataflow analysis.
static llvm::Expected< AdornedCFG > build(const FunctionDecl &Func)
Builds an AdornedCFG from a FunctionDecl.
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
Base class template for dataflow analyses built on a single lattice type.
LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, const TypeErasedLattice &Previous) final
Chooses a lattice element that approximates the current element at a program point,...
ASTContext & getASTContext() final
Returns the ASTContext that is used by the analysis.
DataflowAnalysis(ASTContext &Context, DataflowAnalysisOptions Options)
bool isEqualTypeErased(const TypeErasedLattice &E1, const TypeErasedLattice &E2) final
Returns true if and only if the two given type-erased lattice elements are equal.
DataflowAnalysis(ASTContext &Context)
TypeErasedLattice joinTypeErased(const TypeErasedLattice &E1, const TypeErasedLattice &E2) final
Joins two type-erased lattice elements by computing their least upper bound.
void transferBranchTypeErased(bool Branch, const Stmt *Stmt, TypeErasedLattice &E, Environment &Env) final
Applies the analysis transfer function for a given edge from a CFG block of a conditional statement.
TypeErasedLattice typeErasedInitialElement() final
Returns a type-erased lattice element that models the initial state of a basic block.
LatticeT Lattice
Bounded join-semilattice that is used in the analysis.
void transferTypeErased(const CFGElement &Element, TypeErasedLattice &E, Environment &Env) final
Applies the analysis transfer function for a given control flow graph element and type-erased lattice...
Abstract base class for dataflow "models": reusable analysis components that model a particular aspec...
virtual bool transfer(const CFGElement &Element, Environment &Env)=0
Return value indicates whether the model processed the Element.
Supplements Environment with non-standard comparison and join operations.
Holds the state of the program (store and heap) at a given program point.
An interface for a SAT solver that can be used by dataflow analyses.
Type-erased base class for dataflow analyses built on a single lattice type.
A SAT solver that is an implementation of Algorithm D from Knuth's The Art of Computer Programming Vo...
llvm::Expected< llvm::SmallVector< Diagnostic > > diagnoseFunction(const FunctionDecl &FuncDecl, ASTContext &ASTCtx, llvm::function_ref< llvm::SmallVector< Diagnostic >(const CFGElement &, ASTContext &, const TransferStateForDiagnostics< typename AnalysisT::Lattice > &)> Diagnoser, std::int64_t MaxSATIterations=1 '000 '000 '000, std::int32_t MaxBlockVisits=20 '000)
Runs a dataflow analysis over the given function and then runs Diagnoser over the results.
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, Environment::ValueModel &Model)
Evaluates S and updates Env accordingly.
llvm::Expected< std::vector< std::optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > > runDataflowAnalysis(const AdornedCFG &ACFG, AnalysisT &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const DataflowAnalysisState< typename AnalysisT::Lattice > &)> PostVisitCFG=nullptr, std::int32_t MaxBlockVisits=20 '000)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
llvm::Expected< std::vector< std::optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG, std::int32_t MaxBlockVisits)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
LatticeEffect LatticeJoinEffect
auto createAnalysis(ASTContext &ASTCtx, Environment &Env) -> decltype(AnalysisT(ASTCtx, Env))
LatticeEffect
Effect indicating whether a lattice operation resulted in a new value.
The JSON file list parser is used to communicate input to InstallAPI.
const FunctionProtoType * T
A read-only version of TransferState.
Type-erased model of the program at a given program point.
Type-erased lattice element container.