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
|
//===------------------------ MapLattice.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 a parameterized lattice that maps keys to individual
// lattice elements (of the parameter lattice type). A typical usage is lifting
// a particular lattice to all variables in a lexical scope.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
#include <ostream>
#include <string>
#include <utility>
#include "DataflowAnalysis.h"
#include "clang/AST/Decl.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/StringRef.h"
namespace clang {
namespace dataflow {
/// A lattice that maps keys to individual lattice elements. When instantiated
/// with an `ElementLattice` that is a bounded semi-lattice, `MapLattice` is
/// itself a bounded semi-lattice, so long as the user limits themselves to a
/// finite number of keys. In that case, `top` is (implicitly), the map
/// containing all valid keys mapped to `top` of `ElementLattice`.
///
/// Requirements on `ElementLattice`:
/// * Provides standard declarations of a bounded semi-lattice.
template <typename Key, typename ElementLattice> class MapLattice {
using Container = llvm::DenseMap<Key, ElementLattice>;
Container C;
public:
using key_type = Key;
using mapped_type = ElementLattice;
using value_type = typename Container::value_type;
using iterator = typename Container::iterator;
using const_iterator = typename Container::const_iterator;
MapLattice() = default;
explicit MapLattice(Container C) { C = std::move(C); }
// The `bottom` element is the empty map.
static MapLattice bottom() { return MapLattice(); }
void insert(const std::pair<const key_type, mapped_type> &P) { C.insert(P); }
void insert(std::pair<const key_type, mapped_type> &&P) {
C.insert(std::move(P));
}
unsigned size() const { return C.size(); }
bool empty() const { return C.empty(); }
iterator begin() { return C.begin(); }
iterator end() { return C.end(); }
const_iterator begin() const { return C.begin(); }
const_iterator end() const { return C.end(); }
// Equality is direct equality of underlying map entries. One implication of
// this definition is that a map with (only) keys that map to bottom is not
// equal to the empty map.
friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) {
return LHS.C == RHS.C;
}
friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) {
return !(LHS == RHS);
}
bool contains(const key_type &K) const { return C.find(K) != C.end(); }
iterator find(const key_type &K) { return C.find(K); }
const_iterator find(const key_type &K) const { return C.find(K); }
mapped_type &operator[](const key_type &K) { return C[K]; }
/// If an entry exists in one map but not the other, the missing entry is
/// treated as implicitly mapping to `bottom`. So, the joined map contains the
/// entry as it was in the source map.
LatticeJoinEffect join(const MapLattice &Other) {
LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged;
for (const auto &O : Other.C) {
auto It = C.find(O.first);
if (It == C.end()) {
C.insert(O);
Effect = LatticeJoinEffect::Changed;
} else if (It->second.join(O.second) == LatticeJoinEffect::Changed)
Effect = LatticeJoinEffect::Changed;
}
return Effect;
}
};
/// Convenience alias that captures the common use of map lattices to model
/// in-scope variables.
template <typename ElementLattice>
using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>;
template <typename Key, typename ElementLattice>
std::ostream &
operator<<(std::ostream &Os,
const clang::dataflow::MapLattice<Key, ElementLattice> &M) {
std::string Separator = "";
Os << "{";
for (const auto &E : M) {
Os << std::exchange(Separator, ", ") << E.first << " => " << E.second;
}
Os << "}";
return Os;
}
template <typename ElementLattice>
std::ostream &
operator<<(std::ostream &Os,
const clang::dataflow::VarMapLattice<ElementLattice> &M) {
std::string Separator = "";
Os << "{";
for (const auto &E : M) {
Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => "
<< E.second;
}
Os << "}";
return Os;
}
} // namespace dataflow
} // namespace clang
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
|
