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 
67   /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead.
68   explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
69       : TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {}
70 
71   explicit DataflowAnalysis(ASTContext &Context,
72                             DataflowAnalysisOptions Options)
73       : TypeErasedDataflowAnalysis(Options), Context(Context) {}
74 
75   ASTContext &getASTContext() final { return Context; }
76 
77   TypeErasedLattice typeErasedInitialElement() final {
78     return {static_cast<Derived *>(this)->initialElement()};
79   }
80 
81   LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
82                                    const TypeErasedLattice &E2) final {
83     Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
84     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
85     return L1.join(L2);
86   }
87 
88   bool isEqualTypeErased(const TypeErasedLattice &E1,
89                          const TypeErasedLattice &E2) final {
90     const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
91     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
92     return L1 == L2;
93   }
94 
95   void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E,
96                           Environment &Env) final {
97     Lattice &L = llvm::any_cast<Lattice &>(E.Value);
98     static_cast<Derived *>(this)->transfer(Stmt, L, Env);
99   }
100 
101 private:
102   ASTContext &Context;
103 };
104 
105 // Model of the program at a given program point.
106 template <typename LatticeT> struct DataflowAnalysisState {
107   // Model of a program property.
108   LatticeT Lattice;
109 
110   // Model of the state of the program (store and heap).
111   Environment Env;
112 };
113 
114 /// Performs dataflow analysis and returns a mapping from basic block IDs to
115 /// dataflow analysis states that model the respective basic blocks. The
116 /// returned vector, if any, will have the same size as the number of CFG
117 /// blocks, with indices corresponding to basic block IDs. Returns an error if
118 /// the dataflow analysis cannot be performed successfully. Otherwise, calls
119 /// `PostVisitStmt` on each statement with the final analysis results at that
120 /// program point.
121 template <typename AnalysisT>
122 llvm::Expected<std::vector<
123     llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
124 runDataflowAnalysis(
125     const ControlFlowContext &CFCtx, AnalysisT &Analysis,
126     const Environment &InitEnv,
127     std::function<void(const Stmt *, const DataflowAnalysisState<
128                                          typename AnalysisT::Lattice> &)>
129         PostVisitStmt = nullptr) {
130   std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)>
131       PostVisitStmtClosure = nullptr;
132   if (PostVisitStmt != nullptr) {
133     PostVisitStmtClosure = [&PostVisitStmt](
134                                const Stmt *Stmt,
135                                const TypeErasedDataflowAnalysisState &State) {
136       auto *Lattice =
137           llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
138       PostVisitStmt(Stmt, DataflowAnalysisState<typename AnalysisT::Lattice>{
139                               *Lattice, State.Env});
140     };
141   }
142 
143   auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis(
144       CFCtx, Analysis, InitEnv, PostVisitStmtClosure);
145   if (!TypeErasedBlockStates)
146     return TypeErasedBlockStates.takeError();
147 
148   std::vector<
149       llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
150       BlockStates;
151   BlockStates.reserve(TypeErasedBlockStates->size());
152 
153   llvm::transform(std::move(*TypeErasedBlockStates),
154                   std::back_inserter(BlockStates), [](auto &OptState) {
155                     return std::move(OptState).map([](auto &&State) {
156                       return DataflowAnalysisState<typename AnalysisT::Lattice>{
157                           llvm::any_cast<typename AnalysisT::Lattice>(
158                               std::move(State.Lattice.Value)),
159                           std::move(State.Env)};
160                     });
161                   });
162   return BlockStates;
163 }
164 
165 /// Abstract base class for dataflow "models": reusable analysis components that
166 /// model a particular aspect of program semantics in the `Environment`. For
167 /// example, a model may capture a type and its related functions.
168 class DataflowModel : public Environment::ValueModel {
169 public:
170   /// Return value indicates whether the model processed the `Stmt`.
171   virtual bool transfer(const Stmt *Stmt, Environment &Env) = 0;
172 };
173 
174 } // namespace dataflow
175 } // namespace clang
176 
177 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
178