1 //===- DataflowAnalysis.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 base types and functions for building dataflow analyses
10 //  that run over Control-Flow Graphs (CFGs).
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
16 
17 #include <iterator>
18 #include <optional>
19 #include <type_traits>
20 #include <utility>
21 #include <vector>
22 
23 #include "clang/AST/ASTContext.h"
24 #include "clang/Analysis/CFG.h"
25 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
26 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
27 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
28 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
29 #include "llvm/ADT/Any.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/Support/Error.h"
32 
33 namespace clang {
34 namespace dataflow {
35 
36 /// Base class template for dataflow analyses built on a single lattice type.
37 ///
38 /// Requirements:
39 ///
40 ///  `Derived` must be derived from a specialization of this class template and
41 ///  must provide the following public members:
42 ///   * `LatticeT initialElement()` - returns a lattice element that models the
43 ///     initial state of a basic block;
44 ///   * `void transfer(const CFGElement *, LatticeT &, Environment &)` - applies
45 ///     the analysis transfer function for a given CFG element and lattice
46 ///     element.
47 ///
48 ///  `Derived` can optionally provide the following members:
49 ///  * `void transferBranch(bool Branch, const Stmt *Stmt, TypeErasedLattice &E,
50 ///                         Environment &Env)` - applies the analysis transfer
51 ///    function for a given edge from a CFG block of a conditional statement.
52 ///
53 ///  `Derived` can optionally override the following members:
54 ///   * `bool merge(QualType, const Value &, const Value &, Value &,
55 ///     Environment &)` -  joins distinct values. This could be a strict
56 ///     lattice join or a more general widening operation.
57 ///
58 ///  `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
59 ///  provide the following public members:
60 ///   * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
61 ///     argument by computing their least upper bound, modifies the object if
62 ///     necessary, and returns an effect indicating whether any changes were
63 ///     made to it;
64 ///   * `bool operator==(const LatticeT &) const` - returns true if and only if
65 ///     the object is equal to the argument.
66 ///
67 /// `LatticeT` can optionally provide the following members:
68 ///  * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the
69 ///    lattice element with an  approximation that can reach a fixed point more
70 ///    quickly than iterated application of the transfer function alone. The
71 ///    previous value is provided to inform the choice of widened value. The
72 ///    function must also serve as a comparison operation, by indicating whether
73 ///    the widened value is equivalent to the previous value with the returned
74 ///    `LatticeJoinEffect`.
75 template <typename Derived, typename LatticeT>
76 class DataflowAnalysis : public TypeErasedDataflowAnalysis {
77 public:
78   /// Bounded join-semilattice that is used in the analysis.
79   using Lattice = LatticeT;
80 
81   explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
82 
83   /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead.
84   explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
85       : DataflowAnalysis(
86             Context,
87             {ApplyBuiltinTransfer
88                  ? DataflowAnalysisContext::Options{}
89                  : std::optional<DataflowAnalysisContext::Options>()}) {}
90 
91   explicit DataflowAnalysis(ASTContext &Context,
92                             DataflowAnalysisOptions Options)
93       : TypeErasedDataflowAnalysis(Options), Context(Context) {}
94 
95   ASTContext &getASTContext() final { return Context; }
96 
97   TypeErasedLattice typeErasedInitialElement() final {
98     return {static_cast<Derived *>(this)->initialElement()};
99   }
100 
101   LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
102                                    const TypeErasedLattice &E2) final {
103     Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
104     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
105     return L1.join(L2);
106   }
107 
108   LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current,
109                                     const TypeErasedLattice &Previous) final {
110     Lattice &C = llvm::any_cast<Lattice &>(Current.Value);
111     const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value);
112     return widenInternal(Rank0{}, C, P);
113   }
114 
115   bool isEqualTypeErased(const TypeErasedLattice &E1,
116                          const TypeErasedLattice &E2) final {
117     const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
118     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
119     return L1 == L2;
120   }
121 
122   void transferTypeErased(const CFGElement *Element, TypeErasedLattice &E,
123                           Environment &Env) final {
124     Lattice &L = llvm::any_cast<Lattice &>(E.Value);
125     static_cast<Derived *>(this)->transfer(Element, L, Env);
126   }
127 
128   void transferBranchTypeErased(bool Branch, const Stmt *Stmt,
129                                 TypeErasedLattice &E, Environment &Env) final {
130     transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch, Stmt,
131                            E, Env);
132   }
133 
134 private:
135   // These `Rank` structs are used for template metaprogramming to choose
136   // between overloads.
137   struct Rank1 {};
138   struct Rank0 : Rank1 {};
139 
140   // The first-choice implementation: use `widen` when it is available.
141   template <typename T>
142   static auto widenInternal(Rank0, T &Current, const T &Prev)
143       -> decltype(Current.widen(Prev)) {
144     return Current.widen(Prev);
145   }
146 
147   // The second-choice implementation: `widen` is unavailable. Widening is
148   // merged with equality checking, so when widening is unimplemented, we
149   // default to equality checking.
150   static LatticeJoinEffect widenInternal(Rank1, const Lattice &Current,
151                                          const Lattice &Prev) {
152     return Prev == Current ? LatticeJoinEffect::Unchanged
153                            : LatticeJoinEffect::Changed;
154   }
155 
156   // The first-choice implementation: `transferBranch` is implemented.
157   template <typename Analysis>
158   static auto transferBranchInternal(Rank0, Analysis &A, bool Branch,
159                                      const Stmt *Stmt, TypeErasedLattice &L,
160                                      Environment &Env)
161       -> std::void_t<decltype(A.transferBranch(
162           Branch, Stmt, std::declval<LatticeT &>(), Env))> {
163     A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env);
164   }
165 
166   // The second-choice implementation: `transferBranch` is unimplemented. No-op.
167   template <typename Analysis>
168   static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *,
169                                      TypeErasedLattice &, Environment &) {}
170 
171   ASTContext &Context;
172 };
173 
174 // Model of the program at a given program point.
175 template <typename LatticeT> struct DataflowAnalysisState {
176   // Model of a program property.
177   LatticeT Lattice;
178 
179   // Model of the state of the program (store and heap).
180   Environment Env;
181 };
182 
183 /// Performs dataflow analysis and returns a mapping from basic block IDs to
184 /// dataflow analysis states that model the respective basic blocks. The
185 /// returned vector, if any, will have the same size as the number of CFG
186 /// blocks, with indices corresponding to basic block IDs. Returns an error if
187 /// the dataflow analysis cannot be performed successfully. Otherwise, calls
188 /// `PostVisitCFG` on each CFG element with the final analysis results at that
189 /// program point.
190 template <typename AnalysisT>
191 llvm::Expected<std::vector<
192     std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
193 runDataflowAnalysis(
194     const ControlFlowContext &CFCtx, AnalysisT &Analysis,
195     const Environment &InitEnv,
196     std::function<void(const CFGElement &, const DataflowAnalysisState<
197                                                typename AnalysisT::Lattice> &)>
198         PostVisitCFG = nullptr) {
199   std::function<void(const CFGElement &,
200                      const TypeErasedDataflowAnalysisState &)>
201       PostVisitCFGClosure = nullptr;
202   if (PostVisitCFG) {
203     PostVisitCFGClosure = [&PostVisitCFG](
204                               const CFGElement &Element,
205                               const TypeErasedDataflowAnalysisState &State) {
206       auto *Lattice =
207           llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
208       PostVisitCFG(Element, DataflowAnalysisState<typename AnalysisT::Lattice>{
209                                 *Lattice, State.Env});
210     };
211   }
212 
213   auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis(
214       CFCtx, Analysis, InitEnv, PostVisitCFGClosure);
215   if (!TypeErasedBlockStates)
216     return TypeErasedBlockStates.takeError();
217 
218   std::vector<std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
219       BlockStates;
220   BlockStates.reserve(TypeErasedBlockStates->size());
221 
222   llvm::transform(
223       std::move(*TypeErasedBlockStates), std::back_inserter(BlockStates),
224       [](auto &OptState) {
225         return llvm::transformOptional(std::move(OptState), [](auto &&State) {
226           return DataflowAnalysisState<typename AnalysisT::Lattice>{
227               llvm::any_cast<typename AnalysisT::Lattice>(
228                   std::move(State.Lattice.Value)),
229               std::move(State.Env)};
230         });
231       });
232   return BlockStates;
233 }
234 
235 /// Abstract base class for dataflow "models": reusable analysis components that
236 /// model a particular aspect of program semantics in the `Environment`. For
237 /// example, a model may capture a type and its related functions.
238 class DataflowModel : public Environment::ValueModel {
239 public:
240   /// Return value indicates whether the model processed the `Element`.
241   virtual bool transfer(const CFGElement *Element, Environment &Env) = 0;
242 };
243 
244 } // namespace dataflow
245 } // namespace clang
246 
247 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
248