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 ///     FIXME: make it `static LatticeT join(const LatticeT&, const LatticeT&)`
65 ///   * `bool operator==(const LatticeT &) const` - returns true if and only if
66 ///     the object is equal to the argument.
67 ///
68 /// `LatticeT` can optionally provide the following members:
69 ///  * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the
70 ///    lattice element with an  approximation that can reach a fixed point more
71 ///    quickly than iterated application of the transfer function alone. The
72 ///    previous value is provided to inform the choice of widened value. The
73 ///    function must also serve as a comparison operation, by indicating whether
74 ///    the widened value is equivalent to the previous value with the returned
75 ///    `LatticeJoinEffect`.
76 template <typename Derived, typename LatticeT>
77 class DataflowAnalysis : public TypeErasedDataflowAnalysis {
78 public:
79   /// Bounded join-semilattice that is used in the analysis.
80   using Lattice = LatticeT;
81 
82   explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
83 
84   /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead.
85   explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
86       : DataflowAnalysis(
87             Context,
88             {ApplyBuiltinTransfer
89                  ? DataflowAnalysisContext::Options{}
90                  : std::optional<DataflowAnalysisContext::Options>()}) {}
91 
92   explicit DataflowAnalysis(ASTContext &Context,
93                             DataflowAnalysisOptions Options)
94       : TypeErasedDataflowAnalysis(Options), Context(Context) {}
95 
96   ASTContext &getASTContext() final { return Context; }
97 
98   TypeErasedLattice typeErasedInitialElement() final {
99     return {static_cast<Derived *>(this)->initialElement()};
100   }
101 
102   TypeErasedLattice joinTypeErased(const TypeErasedLattice &E1,
103                                    const TypeErasedLattice &E2) final {
104     // FIXME: change the signature of join() to avoid copying here.
105     Lattice L1 = llvm::any_cast<const Lattice &>(E1.Value);
106     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
107     L1.join(L2);
108     return {std::move(L1)};
109   }
110 
111   LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current,
112                                     const TypeErasedLattice &Previous) final {
113     Lattice &C = llvm::any_cast<Lattice &>(Current.Value);
114     const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value);
115     return widenInternal(Rank0{}, C, P);
116   }
117 
118   bool isEqualTypeErased(const TypeErasedLattice &E1,
119                          const TypeErasedLattice &E2) final {
120     const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
121     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
122     return L1 == L2;
123   }
124 
125   void transferTypeErased(const CFGElement &Element, TypeErasedLattice &E,
126                           Environment &Env) final {
127     Lattice &L = llvm::any_cast<Lattice &>(E.Value);
128     static_cast<Derived *>(this)->transfer(Element, L, Env);
129   }
130 
131   void transferBranchTypeErased(bool Branch, const Stmt *Stmt,
132                                 TypeErasedLattice &E, Environment &Env) final {
133     transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch, Stmt,
134                            E, Env);
135   }
136 
137 private:
138   // These `Rank` structs are used for template metaprogramming to choose
139   // between overloads.
140   struct Rank1 {};
141   struct Rank0 : Rank1 {};
142 
143   // The first-choice implementation: use `widen` when it is available.
144   template <typename T>
145   static auto widenInternal(Rank0, T &Current, const T &Prev)
146       -> decltype(Current.widen(Prev)) {
147     return Current.widen(Prev);
148   }
149 
150   // The second-choice implementation: `widen` is unavailable. Widening is
151   // merged with equality checking, so when widening is unimplemented, we
152   // default to equality checking.
153   static LatticeJoinEffect widenInternal(Rank1, const Lattice &Current,
154                                          const Lattice &Prev) {
155     return Prev == Current ? LatticeJoinEffect::Unchanged
156                            : LatticeJoinEffect::Changed;
157   }
158 
159   // The first-choice implementation: `transferBranch` is implemented.
160   template <typename Analysis>
161   static auto transferBranchInternal(Rank0, Analysis &A, bool Branch,
162                                      const Stmt *Stmt, TypeErasedLattice &L,
163                                      Environment &Env)
164       -> std::void_t<decltype(A.transferBranch(
165           Branch, Stmt, std::declval<LatticeT &>(), Env))> {
166     A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env);
167   }
168 
169   // The second-choice implementation: `transferBranch` is unimplemented. No-op.
170   template <typename Analysis>
171   static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *,
172                                      TypeErasedLattice &, Environment &) {}
173 
174   ASTContext &Context;
175 };
176 
177 // Model of the program at a given program point.
178 template <typename LatticeT> struct DataflowAnalysisState {
179   // Model of a program property.
180   LatticeT Lattice;
181 
182   // Model of the state of the program (store and heap).
183   Environment Env;
184 };
185 
186 /// Performs dataflow analysis and returns a mapping from basic block IDs to
187 /// dataflow analysis states that model the respective basic blocks. The
188 /// returned vector, if any, will have the same size as the number of CFG
189 /// blocks, with indices corresponding to basic block IDs. Returns an error if
190 /// the dataflow analysis cannot be performed successfully. Otherwise, calls
191 /// `PostVisitCFG` on each CFG element with the final analysis results at that
192 /// program point.
193 template <typename AnalysisT>
194 llvm::Expected<std::vector<
195     std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
196 runDataflowAnalysis(
197     const ControlFlowContext &CFCtx, AnalysisT &Analysis,
198     const Environment &InitEnv,
199     std::function<void(const CFGElement &, const DataflowAnalysisState<
200                                                typename AnalysisT::Lattice> &)>
201         PostVisitCFG = nullptr) {
202   std::function<void(const CFGElement &,
203                      const TypeErasedDataflowAnalysisState &)>
204       PostVisitCFGClosure = nullptr;
205   if (PostVisitCFG) {
206     PostVisitCFGClosure = [&PostVisitCFG](
207                               const CFGElement &Element,
208                               const TypeErasedDataflowAnalysisState &State) {
209       auto *Lattice =
210           llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
211       // FIXME: we should not be copying the environment here!
212       // Ultimately the PostVisitCFG only gets a const reference anyway.
213       PostVisitCFG(Element, DataflowAnalysisState<typename AnalysisT::Lattice>{
214                                 *Lattice, State.Env.fork()});
215     };
216   }
217 
218   auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis(
219       CFCtx, Analysis, InitEnv, PostVisitCFGClosure);
220   if (!TypeErasedBlockStates)
221     return TypeErasedBlockStates.takeError();
222 
223   std::vector<std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
224       BlockStates;
225   BlockStates.reserve(TypeErasedBlockStates->size());
226 
227   llvm::transform(
228       std::move(*TypeErasedBlockStates), std::back_inserter(BlockStates),
229       [](auto &OptState) {
230         return llvm::transformOptional(
231             std::move(OptState), [](TypeErasedDataflowAnalysisState &&State) {
232               return DataflowAnalysisState<typename AnalysisT::Lattice>{
233                   llvm::any_cast<typename AnalysisT::Lattice>(
234                       std::move(State.Lattice.Value)),
235                   std::move(State.Env)};
236             });
237       });
238   return std::move(BlockStates);
239 }
240 
241 /// Abstract base class for dataflow "models": reusable analysis components that
242 /// model a particular aspect of program semantics in the `Environment`. For
243 /// example, a model may capture a type and its related functions.
244 class DataflowModel : public Environment::ValueModel {
245 public:
246   /// Return value indicates whether the model processed the `Element`.
247   virtual bool transfer(const CFGElement &Element, Environment &Env) = 0;
248 };
249 
250 } // namespace dataflow
251 } // namespace clang
252 
253 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
254