clang 19.0.0git
TypeErasedDataflowAnalysis.h
Go to the documentation of this file.
1//===- TypeErasedDataflowAnalysis.h -----------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines type-erased base types and functions for building dataflow
10// analyses that run over Control-Flow Graphs (CFGs).
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
15#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
16
17#include <optional>
18#include <utility>
19#include <vector>
20
22#include "clang/AST/Stmt.h"
23#include "clang/Analysis/CFG.h"
28#include "llvm/ADT/Any.h"
29#include "llvm/Support/Error.h"
30
31namespace clang {
32namespace dataflow {
33
35 /// Options for the built-in model, or empty to not apply them.
36 // FIXME: Remove this option once the framework supports composing analyses
37 // (at which point the built-in transfer functions can be simply a standalone
38 // analysis).
39 std::optional<DataflowAnalysisContext::Options> BuiltinOpts =
41};
42
43/// Type-erased lattice element container.
44///
45/// Requirements:
46///
47/// The type of the object stored in the container must be a bounded
48/// join-semilattice.
50 llvm::Any Value;
51};
52
53/// Type-erased base class for dataflow analyses built on a single lattice type.
56
57public:
58 TypeErasedDataflowAnalysis() : Options({}) {}
59
61 : Options(Options) {}
62
64
65 /// Returns the `ASTContext` that is used by the analysis.
66 virtual ASTContext &getASTContext() = 0;
67
68 /// Returns a type-erased lattice element that models the initial state of a
69 /// basic block.
71
72 /// Joins two type-erased lattice elements by computing their least upper
73 /// bound. Places the join result in the left element and returns an effect
74 /// indicating whether any changes were made to it.
76 const TypeErasedLattice &) = 0;
77
78 /// Chooses a lattice element that approximates the current element at a
79 /// program point, given the previous element at that point. Places the
80 /// widened result in the current element (`Current`). Widening is optional --
81 /// it is only needed to either accelerate convergence (for lattices with
82 /// non-trivial height) or guarantee convergence (for lattices with infinite
83 /// height).
84 ///
85 /// Returns an indication of whether any changes were made to `Current` in
86 /// order to widen. This saves a separate call to `isEqualTypeErased` after
87 /// the widening.
88 virtual LatticeJoinEffect
90 const TypeErasedLattice &Previous) = 0;
91
92 /// Returns true if and only if the two given type-erased lattice elements are
93 /// equal.
95 const TypeErasedLattice &) = 0;
96
97 /// Applies the analysis transfer function for a given control flow graph
98 /// element and type-erased lattice element.
100 Environment &) = 0;
101
102 /// Applies the analysis transfer function for a given edge from a CFG block
103 /// of a conditional statement.
104 /// @param Stmt The condition which is responsible for the split in the CFG.
105 /// @param Branch True if the edge goes to the basic block where the
106 /// condition is true.
107 // FIXME: Change `Stmt` argument to a reference.
108 virtual void transferBranchTypeErased(bool Branch, const Stmt *,
110
111 /// If the built-in model is enabled, returns the options to be passed to
112 /// them. Otherwise returns empty.
113 const std::optional<DataflowAnalysisContext::Options> &
115 return Options.BuiltinOpts;
116 }
117};
118
119/// Type-erased model of the program at a given program point.
121 /// Type-erased model of a program property.
123
124 /// Model of the state of the program (store and heap).
126
128 : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
129
132 }
133};
134
135/// Performs dataflow analysis and returns a mapping from basic block IDs to
136/// dataflow analysis states that model the respective basic blocks. Indices of
137/// the returned vector correspond to basic block IDs. Returns an error if the
138/// dataflow analysis cannot be performed successfully. Otherwise, calls
139/// `PostVisitCFG` on each CFG element with the final analysis results at that
140/// program point.
141///
142/// `MaxBlockVisits` caps the number of block visits during analysis. It doesn't
143/// distinguish between repeat visits to the same block and visits to distinct
144/// blocks. This parameter is a backstop to prevent infinite loops, in the case
145/// of bugs in the lattice and/or transfer functions that prevent the analysis
146/// from converging.
149 const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,
150 const Environment &InitEnv,
151 std::function<void(const CFGElement &,
152 const TypeErasedDataflowAnalysisState &)>
153 PostVisitCFG,
154 std::int32_t MaxBlockVisits);
155
156} // namespace dataflow
157} // namespace clang
158
159#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
Defines the clang::ASTContext interface.
const Environment & InitEnv
Initial state to start the analysis.
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
StateNode * Previous
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:182
Represents a top-level expression in a basic block.
Definition: CFG.h:55
Stmt - This represents one statement.
Definition: Stmt.h:84
Supplements Environment with non-standard comparison and join operations.
Holds the state of the program (store and heap) at a given program point.
Environment fork() const
Returns a new environment that is a copy of this one.
Type-erased base class for dataflow analyses built on a single lattice type.
const std::optional< DataflowAnalysisContext::Options > & builtinOptions() const
If the built-in model is enabled, returns the options to be passed to them.
virtual void transferBranchTypeErased(bool Branch, const Stmt *, TypeErasedLattice &, Environment &)=0
Applies the analysis transfer function for a given edge from a CFG block of a conditional statement.
virtual LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, const TypeErasedLattice &Previous)=0
Chooses a lattice element that approximates the current element at a program point,...
virtual TypeErasedLattice typeErasedInitialElement()=0
Returns a type-erased lattice element that models the initial state of a basic block.
virtual void transferTypeErased(const CFGElement &, TypeErasedLattice &, Environment &)=0
Applies the analysis transfer function for a given control flow graph element and type-erased lattice...
virtual ASTContext & getASTContext()=0
Returns the ASTContext that is used by the analysis.
virtual bool isEqualTypeErased(const TypeErasedLattice &, const TypeErasedLattice &)=0
Returns true if and only if the two given type-erased lattice elements are equal.
virtual TypeErasedLattice joinTypeErased(const TypeErasedLattice &, const TypeErasedLattice &)=0
Joins two type-erased lattice elements by computing their least upper bound.
TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options)
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...
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
The JSON file list parser is used to communicate input to InstallAPI.
Definition: Format.h:5378
std::optional< DataflowAnalysisContext::Options > BuiltinOpts
Options for the built-in model, or empty to not apply them.
Type-erased model of the program at a given program point.
TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
TypeErasedLattice Lattice
Type-erased model of a program property.
Environment Env
Model of the state of the program (store and heap).
Type-erased lattice element container.