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
21#include "clang/AST/ASTContext.h"
22#include "clang/AST/Stmt.h"
23#include "clang/Analysis/CFG.h"
24#include "clang/Analysis/FlowSensitive/AdornedCFG.h"
25#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
26#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
27#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
28#include "llvm/ADT/Any.h"
29#include "llvm/Support/Error.h"
30
31namespace clang {
32namespace dataflow {
33
34struct DataflowAnalysisOptions {
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 =
40 DataflowAnalysisContext::Options{};
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.
49struct TypeErasedLattice {
50 llvm::Any Value;
51};
52
53/// Type-erased base class for dataflow analyses built on a single lattice type.
54class TypeErasedDataflowAnalysis : public Environment::ValueModel {
55 DataflowAnalysisOptions Options;
56
57public:
58 TypeErasedDataflowAnalysis() : Options({}) {}
59
60 TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options)
61 : Options(Options) {}
62
63 virtual ~TypeErasedDataflowAnalysis() {}
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.
70 virtual TypeErasedLattice typeErasedInitialElement() = 0;
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.
75 virtual TypeErasedLattice joinTypeErased(const TypeErasedLattice &,
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
89 widenTypeErased(TypeErasedLattice &Current,
90 const TypeErasedLattice &Previous) = 0;
91
92 /// Returns true if and only if the two given type-erased lattice elements are
93 /// equal.
94 virtual bool isEqualTypeErased(const TypeErasedLattice &,
95 const TypeErasedLattice &) = 0;
96
97 /// Applies the analysis transfer function for a given control flow graph
98 /// element and type-erased lattice element.
99 virtual void transferTypeErased(const CFGElement &, TypeErasedLattice &,
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 *,
109 TypeErasedLattice &, Environment &) = 0;
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> &
114 builtinOptions() const {
115 return Options.BuiltinOpts;
116 }
117};
118
119/// Type-erased model of the program at a given program point.
120struct TypeErasedDataflowAnalysisState {
121 /// Type-erased model of a program property.
122 TypeErasedLattice Lattice;
123
124 /// Model of the state of the program (store and heap).
125 Environment Env;
126
127 TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
128 : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
129
130 TypeErasedDataflowAnalysisState fork() const {
131 return TypeErasedDataflowAnalysisState(Lattice, Env.fork());
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.
147llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>>
148runTypeErasedDataflowAnalysis(
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
160

source code of clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h