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 | |
31 | namespace clang { |
32 | namespace dataflow { |
33 | |
34 | struct 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. |
49 | struct TypeErasedLattice { |
50 | llvm::Any Value; |
51 | }; |
52 | |
53 | /// Type-erased base class for dataflow analyses built on a single lattice type. |
54 | class TypeErasedDataflowAnalysis : public Environment::ValueModel { |
55 | DataflowAnalysisOptions Options; |
56 | |
57 | public: |
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. |
120 | struct 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. |
147 | llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>> |
148 | runTypeErasedDataflowAnalysis( |
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 | |