Coverage Report

Created: 2022-07-16 07:03

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
Line
Count
Source
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 "llvm/ADT/Any.h"
27
#include "llvm/ADT/Optional.h"
28
#include "llvm/Support/Error.h"
29
30
namespace clang {
31
namespace dataflow {
32
33
/// Type-erased lattice element container.
34
///
35
/// Requirements:
36
///
37
///  The type of the object stored in the container must be a bounded
38
///  join-semilattice.
39
struct TypeErasedLattice {
40
  llvm::Any Value;
41
};
42
43
/// Type-erased base class for dataflow analyses built on a single lattice type.
44
class TypeErasedDataflowAnalysis : public Environment::ValueModel {
45
  /// Determines whether to apply the built-in transfer functions.
46
  // FIXME: Remove this option once the framework supports composing analyses
47
  // (at which point the built-in transfer functions can be simply a standalone
48
  // analysis).
49
  bool ApplyBuiltinTransfer;
50
51
public:
52
281
  TypeErasedDataflowAnalysis() : ApplyBuiltinTransfer(true) {}
53
  TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer)
54
      : ApplyBuiltinTransfer(ApplyBuiltinTransfer) {}
55
56
393
  virtual ~TypeErasedDataflowAnalysis() {}
57
58
  /// Returns the `ASTContext` that is used by the analysis.
59
  virtual ASTContext &getASTContext() = 0;
60
61
  /// Returns a type-erased lattice element that models the initial state of a
62
  /// basic block.
63
  virtual TypeErasedLattice typeErasedInitialElement() = 0;
64
65
  /// Joins two type-erased lattice elements by computing their least upper
66
  /// bound. Places the join result in the left element and returns an effect
67
  /// indicating whether any changes were made to it.
68
  virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &,
69
                                           const TypeErasedLattice &) = 0;
70
71
  /// Returns true if and only if the two given type-erased lattice elements are
72
  /// equal.
73
  virtual bool isEqualTypeErased(const TypeErasedLattice &,
74
                                 const TypeErasedLattice &) = 0;
75
76
  /// Applies the analysis transfer function for a given statement and
77
  /// type-erased lattice element.
78
  virtual void transferTypeErased(const Stmt *, TypeErasedLattice &,
79
                                  Environment &) = 0;
80
81
  /// Determines whether to apply the built-in transfer functions, which model
82
  /// the heap and stack in the `Environment`.
83
12.2k
  bool applyBuiltinTransfer() const { return ApplyBuiltinTransfer; }
84
};
85
86
/// Type-erased model of the program at a given program point.
87
struct TypeErasedDataflowAnalysisState {
88
  /// Type-erased model of a program property.
89
  TypeErasedLattice Lattice;
90
91
  /// Model of the state of the program (store and heap).
92
  Environment Env;
93
94
  TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
95
784
      : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
96
};
97
98
/// Transfers the state of a basic block by evaluating each of its statements in
99
/// the context of `Analysis` and the states of its predecessors that are
100
/// available in `BlockStates`. `HandleTransferredStmt` (if provided) will be
101
/// applied to each statement in the block, after it is evaluated.
102
///
103
/// Requirements:
104
///
105
///   All predecessors of `Block` except those with loop back edges must have
106
///   already been transferred. States in `BlockStates` that are set to
107
///   `llvm::None` represent basic blocks that are not evaluated yet.
108
TypeErasedDataflowAnalysisState transferBlock(
109
    const ControlFlowContext &CFCtx,
110
    std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
111
    const CFGBlock &Block, const Environment &InitEnv,
112
    TypeErasedDataflowAnalysis &Analysis,
113
    std::function<void(const CFGStmt &,
114
                       const TypeErasedDataflowAnalysisState &)>
115
        HandleTransferredStmt = nullptr);
116
117
/// Performs dataflow analysis and returns a mapping from basic block IDs to
118
/// dataflow analysis states that model the respective basic blocks. Indices of
119
/// the returned vector correspond to basic block IDs. Returns an error if the
120
/// dataflow analysis cannot be performed successfully. Otherwise, calls
121
/// `PostVisitStmt` on each statement with the final analysis results at that
122
/// program point.
123
llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
124
runTypeErasedDataflowAnalysis(
125
    const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis,
126
    const Environment &InitEnv,
127
    std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)>
128
        PostVisitStmt = nullptr);
129
130
} // namespace dataflow
131
} // namespace clang
132
133
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H