Coverage Report

Created: 2022-07-16 07:03

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
Line
Count
Source
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
243
  explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
66
  explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
67
      : TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {}
68
69
6.91k
  ASTContext &getASTContext() final { return Context; }
70
71
486
  TypeErasedLattice typeErasedInitialElement() final {
72
486
    return {static_cast<Derived *>(this)->initialElement()};
73
486
  }
74
75
  LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
76
315
                                   const TypeErasedLattice &E2) final {
77
315
    Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
78
315
    const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
79
315
    return L1.join(L2);
80
315
  }
81
82
  bool isEqualTypeErased(const TypeErasedLattice &E1,
83
39
                         const TypeErasedLattice &E2) final {
84
39
    const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
85
39
    const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
86
39
    return L1 == L2;
87
39
  }
88
89
  void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E,
90
6.91k
                          Environment &Env) final {
91
6.91k
    Lattice &L = llvm::any_cast<Lattice &>(E.Value);
92
6.91k
    static_cast<Derived *>(this)->transfer(Stmt, L, Env);
93
6.91k
  }
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