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 <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/ControlFlowContext.h"
25 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
26 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
27 #include "llvm/ADT/Any.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/Support/Error.h"
31 
32 namespace clang {
33 namespace dataflow {
34 
35 /// Base class template for dataflow analyses built on a single lattice type.
36 ///
37 /// Requirements:
38 ///
39 ///  `Derived` must be derived from a specialization of this class template and
40 ///  must provide the following public members:
41 ///   * `LatticeT initialElement()` - returns a lattice element that models the
42 ///     initial state of a basic block;
43 ///   * `void transfer(const Stmt *, LatticeT &, Environment &)` - applies the
44 ///     analysis transfer function for a given statement and lattice element.
45 ///
46 ///  `Derived` can optionally override the following members:
47 ///   * `bool merge(QualType, const Value &, const Value &, Value &,
48 ///     Environment &)` -  joins distinct values. This could be a strict
49 ///     lattice join or a more general widening operation.
50 ///
51 ///  `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
52 ///  provide the following public members:
53 ///   * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
54 ///     argument by computing their least upper bound, modifies the object if
55 ///     necessary, and returns an effect indicating whether any changes were
56 ///     made to it;
57 ///   * `bool operator==(const LatticeT &) const` - returns true if and only if
58 ///     the object is equal to the argument.
59 template <typename Derived, typename LatticeT>
60 class DataflowAnalysis : public TypeErasedDataflowAnalysis {
61 public:
62   /// Bounded join-semilattice that is used in the analysis.
63   using Lattice = LatticeT;
64 
65   explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
66   explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
67       : TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {}
68 
69   ASTContext &getASTContext() final { return Context; }
70 
71   TypeErasedLattice typeErasedInitialElement() final {
72     return {static_cast<Derived *>(this)->initialElement()};
73   }
74 
75   LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
76                                    const TypeErasedLattice &E2) final {
77     Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
78     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
79     return L1.join(L2);
80   }
81 
82   bool isEqualTypeErased(const TypeErasedLattice &E1,
83                          const TypeErasedLattice &E2) final {
84     const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
85     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
86     return L1 == L2;
87   }
88 
89   void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E,
90                           Environment &Env) final {
91     Lattice &L = llvm::any_cast<Lattice &>(E.Value);
92     static_cast<Derived *>(this)->transfer(Stmt, L, Env);
93   }
94 
95 private:
96   ASTContext &Context;
97 };
98 
99 // Model of the program at a given program point.
100 template <typename LatticeT> struct DataflowAnalysisState {
101   // Model of a program property.
102   LatticeT Lattice;
103 
104   // Model of the state of the program (store and heap).
105   Environment Env;
106 };
107 
108 /// Performs dataflow analysis and returns a mapping from basic block IDs to
109 /// dataflow analysis states that model the respective basic blocks. The
110 /// returned vector, if any, will have the same size as the number of CFG
111 /// blocks, with indices corresponding to basic block IDs. Returns an error if
112 /// the dataflow analysis cannot be performed successfully. Otherwise, calls
113 /// `PostVisitStmt` on each statement with the final analysis results at that
114 /// program point.
115 template <typename AnalysisT>
116 llvm::Expected<std::vector<
117     llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
118 runDataflowAnalysis(
119     const ControlFlowContext &CFCtx, AnalysisT &Analysis,
120     const Environment &InitEnv,
121     std::function<void(const Stmt *, const DataflowAnalysisState<
122                                          typename AnalysisT::Lattice> &)>
123         PostVisitStmt = nullptr) {
124   std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)>
125       PostVisitStmtClosure = nullptr;
126   if (PostVisitStmt != nullptr) {
127     PostVisitStmtClosure = [&PostVisitStmt](
128                                const Stmt *Stmt,
129                                const TypeErasedDataflowAnalysisState &State) {
130       auto *Lattice =
131           llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
132       PostVisitStmt(Stmt, DataflowAnalysisState<typename AnalysisT::Lattice>{
133                               *Lattice, State.Env});
134     };
135   }
136 
137   auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis(
138       CFCtx, Analysis, InitEnv, PostVisitStmtClosure);
139   if (!TypeErasedBlockStates)
140     return TypeErasedBlockStates.takeError();
141 
142   std::vector<
143       llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
144       BlockStates;
145   BlockStates.reserve(TypeErasedBlockStates->size());
146 
147   llvm::transform(std::move(*TypeErasedBlockStates),
148                   std::back_inserter(BlockStates), [](auto &OptState) {
149                     return std::move(OptState).map([](auto &&State) {
150                       return DataflowAnalysisState<typename AnalysisT::Lattice>{
151                           llvm::any_cast<typename AnalysisT::Lattice>(
152                               std::move(State.Lattice.Value)),
153                           std::move(State.Env)};
154                     });
155                   });
156   return BlockStates;
157 }
158 
159 /// Abstract base class for dataflow "models": reusable analysis components that
160 /// model a particular aspect of program semantics in the `Environment`. For
161 /// example, a model may capture a type and its related functions.
162 class DataflowModel : public Environment::ValueModel {
163 public:
164   /// Return value indicates whether the model processed the `Stmt`.
165   virtual bool transfer(const Stmt *Stmt, Environment &Env) = 0;
166 };
167 
168 } // namespace dataflow
169 } // namespace clang
170 
171 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
172