Coverage Report

Created: 2022-01-18 06:27

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- DataflowEnvironment.cpp ---------------------------------*- 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 an Environment class that is used by dataflow analyses
10
//  that run over Control-Flow Graphs (CFGs) to keep track of the state of the
11
//  program at given program points.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
16
#include "clang/AST/Decl.h"
17
#include "clang/AST/DeclCXX.h"
18
#include "clang/AST/Type.h"
19
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
20
#include "clang/Analysis/FlowSensitive/StorageLocation.h"
21
#include "clang/Analysis/FlowSensitive/Value.h"
22
#include "llvm/ADT/DenseMap.h"
23
#include "llvm/ADT/DenseSet.h"
24
#include "llvm/Support/ErrorHandling.h"
25
#include <memory>
26
#include <utility>
27
28
namespace clang {
29
namespace dataflow {
30
31
/// Returns a map consisting of key-value entries that are present in both maps.
32
template <typename K, typename V>
33
llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
34
43.7k
                                        const llvm::DenseMap<K, V> &Map2) {
35
43.7k
  llvm::DenseMap<K, V> Result;
36
43.7k
  for (auto &Entry : Map1) {
37
250
    auto It = Map2.find(Entry.first);
38
250
    if (It != Map2.end() && 
Entry.second == It->second212
)
39
212
      Result.insert({Entry.first, Entry.second});
40
250
  }
41
43.7k
  return Result;
42
43.7k
}
llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > clang::dataflow::intersectDenseMaps<clang::ValueDecl const*, clang::dataflow::StorageLocation*>(llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > const&, llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > const&)
Line
Count
Source
34
21.8k
                                        const llvm::DenseMap<K, V> &Map2) {
35
21.8k
  llvm::DenseMap<K, V> Result;
36
21.8k
  for (auto &Entry : Map1) {
37
74
    auto It = Map2.find(Entry.first);
38
74
    if (It != Map2.end() && 
Entry.second == It->second66
)
39
66
      Result.insert({Entry.first, Entry.second});
40
74
  }
41
21.8k
  return Result;
42
21.8k
}
llvm::DenseMap<clang::dataflow::StorageLocation const*, clang::dataflow::Value*, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, clang::dataflow::Value*> > clang::dataflow::intersectDenseMaps<clang::dataflow::StorageLocation const*, clang::dataflow::Value*>(llvm::DenseMap<clang::dataflow::StorageLocation const*, clang::dataflow::Value*, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, clang::dataflow::Value*> > const&, llvm::DenseMap<clang::dataflow::StorageLocation const*, clang::dataflow::Value*, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, clang::dataflow::Value*> > const&)
Line
Count
Source
34
21.8k
                                        const llvm::DenseMap<K, V> &Map2) {
35
21.8k
  llvm::DenseMap<K, V> Result;
36
21.8k
  for (auto &Entry : Map1) {
37
176
    auto It = Map2.find(Entry.first);
38
176
    if (It != Map2.end() && 
Entry.second == It->second146
)
39
146
      Result.insert({Entry.first, Entry.second});
40
176
  }
41
21.8k
  return Result;
42
21.8k
}
43
44
Environment::Environment(DataflowAnalysisContext &DACtx,
45
                         const DeclContext &DeclCtx)
46
66
    : Environment(DACtx) {
47
66
  if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
48
66
    for (const auto *ParamDecl : FuncDecl->parameters()) {
49
33
      assert(ParamDecl != nullptr);
50
0
      auto &ParamLoc = createStorageLocation(*ParamDecl);
51
33
      setStorageLocation(*ParamDecl, ParamLoc);
52
33
      if (Value *ParamVal = createValue(ParamDecl->getType()))
53
33
        setValue(ParamLoc, *ParamVal);
54
33
    }
55
66
  }
56
57
66
  if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
58
5
    if (!MethodDecl->isStatic()) {
59
5
      QualType ThisPointeeType = MethodDecl->getThisObjectType();
60
      // FIXME: Add support for union types.
61
5
      if (!ThisPointeeType->isUnionType()) {
62
5
        auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
63
5
        DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
64
5
        if (Value *ThisPointeeVal = createValue(ThisPointeeType))
65
5
          setValue(ThisPointeeLoc, *ThisPointeeVal);
66
5
      }
67
5
    }
68
5
  }
69
66
}
Unexecuted instantiation: clang::dataflow::Environment::Environment(clang::dataflow::DataflowAnalysisContext&, clang::DeclContext const&)
clang::dataflow::Environment::Environment(clang::dataflow::DataflowAnalysisContext&, clang::DeclContext const&)
Line
Count
Source
46
66
    : Environment(DACtx) {
47
66
  if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
48
66
    for (const auto *ParamDecl : FuncDecl->parameters()) {
49
33
      assert(ParamDecl != nullptr);
50
0
      auto &ParamLoc = createStorageLocation(*ParamDecl);
51
33
      setStorageLocation(*ParamDecl, ParamLoc);
52
33
      if (Value *ParamVal = createValue(ParamDecl->getType()))
53
33
        setValue(ParamLoc, *ParamVal);
54
33
    }
55
66
  }
56
57
66
  if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
58
5
    if (!MethodDecl->isStatic()) {
59
5
      QualType ThisPointeeType = MethodDecl->getThisObjectType();
60
      // FIXME: Add support for union types.
61
5
      if (!ThisPointeeType->isUnionType()) {
62
5
        auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
63
5
        DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
64
5
        if (Value *ThisPointeeVal = createValue(ThisPointeeType))
65
5
          setValue(ThisPointeeLoc, *ThisPointeeVal);
66
5
      }
67
5
    }
68
5
  }
69
66
}
70
71
0
bool Environment::operator==(const Environment &Other) const {
72
0
  assert(DACtx == Other.DACtx);
73
0
  return DeclToLoc == Other.DeclToLoc && LocToVal == Other.LocToVal;
74
0
}
75
76
21.8k
LatticeJoinEffect Environment::join(const Environment &Other) {
77
21.8k
  assert(DACtx == Other.DACtx);
78
79
0
  auto Effect = LatticeJoinEffect::Unchanged;
80
81
21.8k
  const unsigned DeclToLocSizeBefore = DeclToLoc.size();
82
21.8k
  DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
83
21.8k
  if (DeclToLocSizeBefore != DeclToLoc.size())
84
8
    Effect = LatticeJoinEffect::Changed;
85
86
  // FIXME: Add support for joining distinct values that are assigned to the
87
  // same storage locations in `LocToVal` and `Other.LocToVal`.
88
21.8k
  const unsigned LocToValSizeBefore = LocToVal.size();
89
21.8k
  LocToVal = intersectDenseMaps(LocToVal, Other.LocToVal);
90
21.8k
  if (LocToValSizeBefore != LocToVal.size())
91
24
    Effect = LatticeJoinEffect::Changed;
92
93
21.8k
  return Effect;
94
21.8k
}
95
96
398
StorageLocation &Environment::createStorageLocation(QualType Type) {
97
398
  assert(!Type.isNull());
98
398
  if (Type->isStructureOrClassType()) {
99
    // FIXME: Explore options to avoid eager initialization of fields as some of
100
    // them might not be needed for a particular analysis.
101
86
    llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
102
86
    for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
103
81
      FieldLocs.insert({Field, &createStorageLocation(Field->getType())});
104
81
    }
105
86
    return takeOwnership(
106
86
        std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
107
86
  }
108
312
  return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
109
398
}
110
111
203
StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
112
  // Evaluated declarations are always assigned the same storage locations to
113
  // ensure that the environment stabilizes across loop iterations. Storage
114
  // locations for evaluated declarations are stored in the analysis context.
115
203
  if (auto *Loc = DACtx->getStorageLocation(D))
116
85
    return *Loc;
117
118
  auto &Loc = createStorageLocation(D.getType());
118
118
  DACtx->setStorageLocation(D, Loc);
119
118
  return Loc;
120
203
}
121
122
316
StorageLocation &Environment::createStorageLocation(const Expr &E) {
123
  // Evaluated expressions are always assigned the same storage locations to
124
  // ensure that the environment stabilizes across loop iterations. Storage
125
  // locations for evaluated expressions are stored in the analysis context.
126
316
  if (auto *Loc = DACtx->getStorageLocation(E))
127
158
    return *Loc;
128
158
  auto &Loc = createStorageLocation(E.getType());
129
158
  DACtx->setStorageLocation(E, Loc);
130
158
  return Loc;
131
316
}
132
133
203
void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
134
203
  assert(DeclToLoc.find(&D) == DeclToLoc.end());
135
0
  DeclToLoc[&D] = &Loc;
136
203
}
137
138
StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
139
254
                                                 SkipPast SP) const {
140
254
  auto It = DeclToLoc.find(&D);
141
254
  return It == DeclToLoc.end() ? 
nullptr34
:
&skip(*It->second, SP)220
;
142
254
}
143
144
390
void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
145
390
  assert(ExprToLoc.find(&E) == ExprToLoc.end());
146
0
  ExprToLoc[&E] = &Loc;
147
390
}
148
149
StorageLocation *Environment::getStorageLocation(const Expr &E,
150
428
                                                 SkipPast SP) const {
151
428
  auto It = ExprToLoc.find(&E);
152
428
  return It == ExprToLoc.end() ? 
nullptr102
:
&skip(*It->second, SP)326
;
153
428
}
154
155
37
StorageLocation *Environment::getThisPointeeStorageLocation() const {
156
37
  return DACtx->getThisPointeeStorageLocation();
157
37
}
158
159
664
void Environment::setValue(const StorageLocation &Loc, Value &Val) {
160
664
  LocToVal[&Loc] = &Val;
161
162
664
  if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
163
102
    auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
164
165
102
    const QualType Type = AggregateLoc.getType();
166
102
    assert(Type->isStructureOrClassType());
167
168
90
    for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
169
90
      assert(Field != nullptr);
170
0
      setValue(AggregateLoc.getChild(*Field), StructVal->getChild(*Field));
171
90
    }
172
102
  }
173
664
}
174
175
529
Value *Environment::getValue(const StorageLocation &Loc) const {
176
529
  auto It = LocToVal.find(&Loc);
177
529
  return It == LocToVal.end() ? 
nullptr4
:
It->second525
;
178
529
}
179
180
34
Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const {
181
34
  auto *Loc = getStorageLocation(D, SP);
182
34
  if (Loc == nullptr)
183
0
    return nullptr;
184
34
  return getValue(*Loc);
185
34
}
186
187
262
Value *Environment::getValue(const Expr &E, SkipPast SP) const {
188
262
  auto *Loc = getStorageLocation(E, SP);
189
262
  if (Loc == nullptr)
190
94
    return nullptr;
191
168
  return getValue(*Loc);
192
262
}
193
194
182
Value *Environment::createValue(QualType Type) {
195
182
  llvm::DenseSet<QualType> Visited;
196
182
  return createValueUnlessSelfReferential(Type, Visited);
197
182
}
198
199
Value *Environment::createValueUnlessSelfReferential(
200
266
    QualType Type, llvm::DenseSet<QualType> &Visited) {
201
266
  assert(!Type.isNull());
202
203
266
  if (Type->isIntegerType()) {
204
162
    return &takeOwnership(std::make_unique<IntegerValue>());
205
162
  }
206
207
104
  if (Type->isReferenceType()) {
208
19
    QualType PointeeType = Type->getAs<ReferenceType>()->getPointeeType();
209
19
    auto &PointeeLoc = createStorageLocation(PointeeType);
210
211
19
    if (!Visited.contains(PointeeType.getCanonicalType())) {
212
15
      Visited.insert(PointeeType.getCanonicalType());
213
15
      Value *PointeeVal =
214
15
          createValueUnlessSelfReferential(PointeeType, Visited);
215
15
      Visited.erase(PointeeType.getCanonicalType());
216
217
15
      if (PointeeVal != nullptr)
218
15
        setValue(PointeeLoc, *PointeeVal);
219
15
    }
220
221
19
    return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
222
19
  }
223
224
85
  if (Type->isPointerType()) {
225
17
    QualType PointeeType = Type->getAs<PointerType>()->getPointeeType();
226
17
    auto &PointeeLoc = createStorageLocation(PointeeType);
227
228
17
    if (!Visited.contains(PointeeType.getCanonicalType())) {
229
13
      Visited.insert(PointeeType.getCanonicalType());
230
13
      Value *PointeeVal =
231
13
          createValueUnlessSelfReferential(PointeeType, Visited);
232
13
      Visited.erase(PointeeType.getCanonicalType());
233
234
13
      if (PointeeVal != nullptr)
235
13
        setValue(PointeeLoc, *PointeeVal);
236
13
    }
237
238
17
    return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
239
17
  }
240
241
68
  if (Type->isStructureOrClassType()) {
242
    // FIXME: Initialize only fields that are accessed in the context that is
243
    // being analyzed.
244
68
    llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
245
68
    for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
246
56
      assert(Field != nullptr);
247
248
0
      QualType FieldType = Field->getType();
249
56
      if (Visited.contains(FieldType.getCanonicalType()))
250
0
        continue;
251
252
56
      Visited.insert(FieldType.getCanonicalType());
253
56
      FieldValues.insert(
254
56
          {Field, createValueUnlessSelfReferential(FieldType, Visited)});
255
56
      Visited.erase(FieldType.getCanonicalType());
256
56
    }
257
258
68
    return &takeOwnership(
259
68
        std::make_unique<StructValue>(std::move(FieldValues)));
260
68
  }
261
262
0
  return nullptr;
263
68
}
264
265
StorageLocation &
266
398
Environment::takeOwnership(std::unique_ptr<StorageLocation> Loc) {
267
398
  return DACtx->takeOwnership(std::move(Loc));
268
398
}
269
270
462
Value &Environment::takeOwnership(std::unique_ptr<Value> Val) {
271
462
  return DACtx->takeOwnership(std::move(Val));
272
462
}
273
274
576
StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
275
576
  switch (SP) {
276
325
  case SkipPast::None:
277
325
    return Loc;
278
221
  case SkipPast::Reference:
279
    // References cannot be chained so we only need to skip past one level of
280
    // indirection.
281
221
    if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
282
181
      return Val->getPointeeLoc();
283
40
    return Loc;
284
30
  case SkipPast::ReferenceThenPointer:
285
30
    StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference);
286
30
    if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef)))
287
18
      return Val->getPointeeLoc();
288
12
    return LocPastRef;
289
576
  }
290
0
  llvm_unreachable("bad SkipPast kind");
291
0
}
292
293
const StorageLocation &Environment::skip(const StorageLocation &Loc,
294
0
                                         SkipPast SP) const {
295
0
  return skip(*const_cast<StorageLocation *>(&Loc), SP);
296
0
}
297
298
} // namespace dataflow
299
} // namespace clang