1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
//===- DataflowAnalysis.h ---------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines base types and functions for building dataflow analyses
// that run over Control-Flow Graphs (CFGs).
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
#include <iterator>
#include <utility>
#include <vector>
#include "clang/AST/ASTContext.h"
#include "clang/AST/Stmt.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
#include "llvm/ADT/Any.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Error.h"
namespace clang {
namespace dataflow {
/// Base class template for dataflow analyses built on a single lattice type.
///
/// Requirements:
///
/// `Derived` must be derived from a specialization of this class template and
/// must provide the following public members:
/// * `LatticeT initialElement()` - returns a lattice element that models the
/// initial state of a basic block;
/// * `void transfer(const Stmt *, LatticeT &, Environment &)` - applies the
/// analysis transfer function for a given statement and lattice element.
///
/// `Derived` can optionally override the following members:
/// * `bool merge(QualType, const Value &, const Value &, Value &,
/// Environment &)` - joins distinct values. This could be a strict
/// lattice join or a more general widening operation.
///
/// `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
/// provide the following public members:
/// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
/// argument by computing their least upper bound, modifies the object if
/// necessary, and returns an effect indicating whether any changes were
/// made to it;
/// * `bool operator==(const LatticeT &) const` - returns true if and only if
/// the object is equal to the argument.
template <typename Derived, typename LatticeT>
class DataflowAnalysis : public TypeErasedDataflowAnalysis {
public:
/// Bounded join-semilattice that is used in the analysis.
using Lattice = LatticeT;
explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
: TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {}
ASTContext &getASTContext() final { return Context; }
TypeErasedLattice typeErasedInitialElement() final {
return {static_cast<Derived *>(this)->initialElement()};
}
LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
const TypeErasedLattice &E2) final {
Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
return L1.join(L2);
}
bool isEqualTypeErased(const TypeErasedLattice &E1,
const TypeErasedLattice &E2) final {
const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
return L1 == L2;
}
void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E,
Environment &Env) final {
Lattice &L = llvm::any_cast<Lattice &>(E.Value);
static_cast<Derived *>(this)->transfer(Stmt, L, Env);
}
private:
ASTContext &Context;
};
// Model of the program at a given program point.
template <typename LatticeT> struct DataflowAnalysisState {
// Model of a program property.
LatticeT Lattice;
// Model of the state of the program (store and heap).
Environment Env;
};
/// Performs dataflow analysis and returns a mapping from basic block IDs to
/// dataflow analysis states that model the respective basic blocks. Indices
/// of the returned vector correspond to basic block IDs. Returns an error if
/// the dataflow analysis cannot be performed successfully.
template <typename AnalysisT>
llvm::Expected<std::vector<
llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis,
const Environment &InitEnv) {
auto TypeErasedBlockStates =
runTypeErasedDataflowAnalysis(CFCtx, Analysis, InitEnv);
if (!TypeErasedBlockStates)
return TypeErasedBlockStates.takeError();
std::vector<
llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
BlockStates;
BlockStates.reserve(TypeErasedBlockStates->size());
llvm::transform(std::move(*TypeErasedBlockStates),
std::back_inserter(BlockStates), [](auto &OptState) {
return std::move(OptState).map([](auto &&State) {
return DataflowAnalysisState<typename AnalysisT::Lattice>{
llvm::any_cast<typename AnalysisT::Lattice>(
std::move(State.Lattice.Value)),
std::move(State.Env)};
});
});
return BlockStates;
}
} // namespace dataflow
} // namespace clang
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
|
