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 <utility>
18 #include <vector>
19 
20 #include "clang/AST/ASTContext.h"
21 #include "clang/AST/Stmt.h"
22 #include "clang/Analysis/CFG.h"
23 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
25 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
26 #include "clang/Analysis/FlowSensitive/Transfer.h"
27 #include "llvm/ADT/Any.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/Support/Error.h"
30 
31 namespace clang {
32 namespace dataflow {
33 
34 struct DataflowAnalysisOptions {
35   /// Determines whether to apply the built-in transfer functions.
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   bool ApplyBuiltinTransfer = true;
40 
41   /// Only has an effect if `ApplyBuiltinTransfer` is true.
42   TransferOptions BuiltinTransferOptions;
43 };
44 
45 /// Type-erased lattice element container.
46 ///
47 /// Requirements:
48 ///
49 ///  The type of the object stored in the container must be a bounded
50 ///  join-semilattice.
51 struct TypeErasedLattice {
52   llvm::Any Value;
53 };
54 
55 /// Type-erased base class for dataflow analyses built on a single lattice type.
56 class TypeErasedDataflowAnalysis : public Environment::ValueModel {
57   DataflowAnalysisOptions Options;
58 
59 public:
60   TypeErasedDataflowAnalysis() : Options({}) {}
61 
62   /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead.
63   TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer)
64       : Options({ApplyBuiltinTransfer, TransferOptions{}}) {}
65 
66   TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options)
67       : Options(Options) {}
68 
69   virtual ~TypeErasedDataflowAnalysis() {}
70 
71   /// Returns the `ASTContext` that is used by the analysis.
72   virtual ASTContext &getASTContext() = 0;
73 
74   /// Returns a type-erased lattice element that models the initial state of a
75   /// basic block.
76   virtual TypeErasedLattice typeErasedInitialElement() = 0;
77 
78   /// Joins two type-erased lattice elements by computing their least upper
79   /// bound. Places the join result in the left element and returns an effect
80   /// indicating whether any changes were made to it.
81   virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &,
82                                            const TypeErasedLattice &) = 0;
83 
84   /// Returns true if and only if the two given type-erased lattice elements are
85   /// equal.
86   virtual bool isEqualTypeErased(const TypeErasedLattice &,
87                                  const TypeErasedLattice &) = 0;
88 
89   /// Applies the analysis transfer function for a given statement and
90   /// type-erased lattice element.
91   virtual void transferTypeErased(const Stmt *, TypeErasedLattice &,
92                                   Environment &) = 0;
93 
94   /// Determines whether to apply the built-in transfer functions, which model
95   /// the heap and stack in the `Environment`.
96   bool applyBuiltinTransfer() const { return Options.ApplyBuiltinTransfer; }
97 
98   /// Returns the options to be passed to the built-in transfer functions.
99   TransferOptions builtinTransferOptions() const {
100     return Options.BuiltinTransferOptions;
101   }
102 };
103 
104 /// Type-erased model of the program at a given program point.
105 struct TypeErasedDataflowAnalysisState {
106   /// Type-erased model of a program property.
107   TypeErasedLattice Lattice;
108 
109   /// Model of the state of the program (store and heap).
110   Environment Env;
111 
112   TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
113       : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
114 };
115 
116 /// Transfers the state of a basic block by evaluating each of its statements in
117 /// the context of `Analysis` and the states of its predecessors that are
118 /// available in `BlockStates`. `HandleTransferredStmt` (if provided) will be
119 /// applied to each statement in the block, after it is evaluated.
120 ///
121 /// Requirements:
122 ///
123 ///   All predecessors of `Block` except those with loop back edges must have
124 ///   already been transferred. States in `BlockStates` that are set to
125 ///   `llvm::None` represent basic blocks that are not evaluated yet.
126 TypeErasedDataflowAnalysisState transferBlock(
127     const ControlFlowContext &CFCtx,
128     std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
129     const CFGBlock &Block, const Environment &InitEnv,
130     TypeErasedDataflowAnalysis &Analysis,
131     std::function<void(const CFGStmt &,
132                        const TypeErasedDataflowAnalysisState &)>
133         HandleTransferredStmt = nullptr);
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 /// `PostVisitStmt` on each statement with the final analysis results at that
140 /// program point.
141 llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
142 runTypeErasedDataflowAnalysis(
143     const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis,
144     const Environment &InitEnv,
145     std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)>
146         PostVisitStmt = nullptr);
147 
148 } // namespace dataflow
149 } // namespace clang
150 
151 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
152