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"
80template <
typename Derived,
typename LatticeT>
95 return {
static_cast<Derived *
>(
this)->initialElement()};
101 Lattice L1 = llvm::any_cast<const Lattice &>(E1.Value);
102 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
104 return {std::move(L1)};
109 Lattice &
C = llvm::any_cast<Lattice &>(Current.Value);
111 return widenInternal(Rank0{},
C,
P);
116 const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
117 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
123 Lattice &L = llvm::any_cast<Lattice &>(E.Value);
124 static_cast<Derived *
>(
this)->
transfer(Element, L,
Env);
129 transferBranchInternal(Rank0{}, *
static_cast<Derived *
>(
this), Branch,
Stmt,
137 struct Rank0 : Rank1 {};
140 template <
typename T>
141 static auto widenInternal(Rank0, T &Current,
const T &Prev)
142 ->
decltype(Current.widen(Prev)) {
143 return Current.widen(Prev);
156 template <
typename Analysis>
157 static auto transferBranchInternal(Rank0,
Analysis &A,
bool Branch,
158 const Stmt *Stmt, TypeErasedLattice &L,
160 -> std::void_t<
decltype(A.transferBranch(
161 Branch, Stmt, std::declval<LatticeT &>(),
Env))> {
162 A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value),
Env);
166 template <
typename Analysis>
167 static void transferBranchInternal(Rank1,
Analysis &A,
bool,
const Stmt *,
168 TypeErasedLattice &, Environment &) {}
189template <
typename AnalysisT>
191 std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
196 typename AnalysisT::Lattice> &)>
197 PostVisitCFG =
nullptr) {
200 PostVisitCFGClosure =
nullptr;
202 PostVisitCFGClosure = [&PostVisitCFG](
206 llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
210 *Lattice, State.Env.fork()});
216 if (!TypeErasedBlockStates)
217 return TypeErasedBlockStates.takeError();
219 std::vector<std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
221 BlockStates.reserve(TypeErasedBlockStates->size());
224 std::move(*TypeErasedBlockStates), std::back_inserter(
BlockStates),
226 return llvm::transformOptional(
229 llvm::any_cast<typename AnalysisT::Lattice>(
230 std::move(State.Lattice.Value)),
231 std::move(State.Env)};
248template <
typename AnalysisT,
typename Diagnostic>
255 std::int64_t MaxSATIterations = 1'000'000'000) {
259 return Context.takeError();
261 auto OwnedSolver = std::make_unique<WatchedLiteralsSolver>(MaxSATIterations);
267 if (llvm::Error Err =
270 [&ASTCtx, &Diagnoser, &Diagnostics](
273 auto EltDiagnostics = Diagnoser(
276 llvm::any_cast<const typename AnalysisT::Lattice &>(
277 State.Lattice.Value),
279 llvm::move(EltDiagnostics, std::back_inserter(Diagnostics));
282 return std::move(Err);
284 if (
Solver->reachedLimit())
285 return llvm::createStringError(llvm::errc::interrupted,
286 "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 ControlFlowContext & CFCtx
Contains the CFG being analyzed.
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 and other derived context that is needed to perform dataflow analysis.
static llvm::Expected< ControlFlowContext > build(const FunctionDecl &Func)
Builds a ControlFlowContext 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< std::vector< std::optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG=nullptr)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
llvm::Expected< std::vector< std::optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > > runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const DataflowAnalysisState< typename AnalysisT::Lattice > &)> PostVisitCFG=nullptr)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env)
Evaluates S and updates Env accordingly.
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
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)
Runs a dataflow analysis over the given function and then runs Diagnoser over the results.
A read-only version of TransferState.
Type-erased model of the program at a given program point.
Type-erased lattice element container.