Debian Codegraph @

llvm-project/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

raw
1 //===- unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp ===//
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 #include "TestingSupport.h"
10 #include "clang/AST/Decl.h"
11 #include "clang/AST/ExprCXX.h"
12 #include "clang/AST/Type.h"
13 #include "clang/ASTMatchers/ASTMatchFinder.h"
14 #include "clang/ASTMatchers/ASTMatchers.h"
15 #include "clang/Analysis/CFG.h"
16 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
17 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
18 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
19 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
20 #include "clang/Analysis/FlowSensitive/DebugSupport.h"
21 #include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
22 #include "clang/Analysis/FlowSensitive/Value.h"
23 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
24 #include "clang/Tooling/Tooling.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/SmallSet.h"
27 #include "llvm/ADT/StringMap.h"
28 #include "llvm/ADT/StringRef.h"
29 #include "llvm/Support/Error.h"
30 #include "llvm/Testing/ADT/StringMapEntry.h"
31 #include "llvm/Testing/Support/Error.h"
32 #include "gmock/gmock.h"
33 #include "gtest/gtest.h"
34 #include <cassert>
35 #include <memory>
36 #include <optional>
37 #include <ostream>
38 #include <string>
39 #include <utility>
40 #include <vector>
41
42 namespace {
43
44 using namespace clang;
45 using namespace dataflow;
46 using namespace test;
47 using namespace ast_matchers;
48 using llvm::IsStringMapEntry;
49 using ::testing::DescribeMatcher;
50 using ::testing::IsEmpty;
51 using ::testing::NotNull;
52 using ::testing::Test;
53 using ::testing::UnorderedElementsAre;
54
55 template <typename AnalysisT>
56 llvm::Expected<std::vector<
57 std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
58 runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
59 std::unique_ptr<ASTUnit> AST =
60 tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
61
62 auto *Func = selectFirst<FunctionDecl>(
63 "func", match(functionDecl(ast_matchers::hasName("target")).bind("func"),
64 AST->getASTContext()));
65 assert(Func != nullptr);
66
67 Stmt *Body = Func->getBody();
68 assert(Body != nullptr);
69
70 auto CFCtx = llvm::cantFail(
71 ControlFlowContext::build(nullptr, *Body, AST->getASTContext()));
72
73 AnalysisT Analysis = MakeAnalysis(AST->getASTContext());
74 DataflowAnalysisContext DACtx(std::make_unique<WatchedLiteralsSolver>());
75 Environment Env(DACtx);
76
77 return runDataflowAnalysis(CFCtx, Analysis, Env);
78 }
79
80 TEST(DataflowAnalysisTest, NoopAnalysis) {
81 auto BlockStates = llvm::cantFail(
82 runAnalysis<NoopAnalysis>("void target() {}", [](ASTContext &C) {
83 return NoopAnalysis(C, false);
84 }));
85 EXPECT_EQ(BlockStates.size(), 2u);
86 EXPECT_TRUE(BlockStates[0].has_value());
87 EXPECT_TRUE(BlockStates[1].has_value());
88 }
89
90 struct NonConvergingLattice {
91 int State;
92
93 bool operator==(const NonConvergingLattice &Other) const {
94 return State == Other.State;
95 }
96
97 LatticeJoinEffect join(const NonConvergingLattice &Other) {
98 if (Other.State == 0)
99 return LatticeJoinEffect::Unchanged;
100 State += Other.State;
101 return LatticeJoinEffect::Changed;
102 }
103 };
104
105 class NonConvergingAnalysis
106 : public DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice> {
107 public:
108 explicit NonConvergingAnalysis(ASTContext &Context)
109 : DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice>(
110 Context,
111 /*ApplyBuiltinTransfer=*/false) {}
112
113 static NonConvergingLattice initialElement() { return {0}; }
114
115 void transfer(const CFGElement *, NonConvergingLattice &E, Environment &) {
116 ++E.State;
117 }
118 };
119
120 TEST(DataflowAnalysisTest, NonConvergingAnalysis) {
121 std::string Code = R"(
122 void target() {
123 while(true) {}
124 }
125 )";
126 auto Res = runAnalysis<NonConvergingAnalysis>(
127 Code, [](ASTContext &C) { return NonConvergingAnalysis(C); });
128 EXPECT_EQ(llvm::toString(Res.takeError()),
129 "maximum number of iterations reached");
130 }
131
132 // Regression test for joins of bool-typed lvalue expressions. The first loop
133 // results in two passes through the code that follows. Each pass results in a
134 // different `ReferenceValue` for the pointee of `v`. Then, the second loop
135 // causes a join at the loop head where the two environments map expresssion
136 // `*v` to different `ReferenceValue`s.
137 //
138 // An earlier version crashed for this condition (for boolean-typed lvalues), so
139 // this test only verifies that the analysis runs successfully, without
140 // examining any details of the results.
141 TEST(DataflowAnalysisTest, JoinBoolLValues) {
142 std::string Code = R"(
143 void target() {
144 for (int x = 1; x; x = 0)
145 (void)x;
146 bool *v;
147 if (*v)
148 for (int x = 1; x; x = 0)
149 (void)x;
150 }
151 )";
152 ASSERT_THAT_ERROR(
153 runAnalysis<NoopAnalysis>(Code,
154 [](ASTContext &C) {
155 auto EnableBuiltIns = DataflowAnalysisOptions{
156 DataflowAnalysisContext::Options{}};
157 return NoopAnalysis(C, EnableBuiltIns);
158 })
159 .takeError(),
160 llvm::Succeeded());
161 }
162
163 struct FunctionCallLattice {
164 using FunctionSet = llvm::SmallSet<std::string, 8>;
165 FunctionSet CalledFunctions;
166
167 bool operator==(const FunctionCallLattice &Other) const {
168 return CalledFunctions == Other.CalledFunctions;
169 }
170
171 LatticeJoinEffect join(const FunctionCallLattice &Other) {
172 if (Other.CalledFunctions.empty())
173 return LatticeJoinEffect::Unchanged;
174 const size_t size_before = CalledFunctions.size();
175 CalledFunctions.insert(Other.CalledFunctions.begin(),
176 Other.CalledFunctions.end());
177 return CalledFunctions.size() == size_before ? LatticeJoinEffect::Unchanged
178 : LatticeJoinEffect::Changed;
179 }
180 };
181
182 std::ostream &operator<<(std::ostream &OS, const FunctionCallLattice &L) {
183 std::string S;
184 llvm::raw_string_ostream ROS(S);
185 llvm::interleaveComma(L.CalledFunctions, ROS);
186 return OS << "{" << S << "}";
187 }
188
189 class FunctionCallAnalysis
190 : public DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice> {
191 public:
192 explicit FunctionCallAnalysis(ASTContext &Context)
193 : DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice>(Context) {}
194
195 static FunctionCallLattice initialElement() { return {}; }
196
197 void transfer(const CFGElement *Elt, FunctionCallLattice &E, Environment &) {
198 auto CS = Elt->getAs<CFGStmt>();
199 if (!CS)
200 return;
201 const auto *S = CS->getStmt();
202 if (auto *C = dyn_cast<CallExpr>(S)) {
203 if (auto *F = dyn_cast<FunctionDecl>(C->getCalleeDecl())) {
204 E.CalledFunctions.insert(F->getNameInfo().getAsString());
205 }
206 }
207 }
208 };
209
210 class NoreturnDestructorTest : public Test {
211 protected:
212 template <typename Matcher>
213 void runDataflow(llvm::StringRef Code, Matcher Expectations) {
214 tooling::FileContentMappings FilesContents;
215 FilesContents.push_back(std::make_pair<std::string, std::string>(
216 "noreturn_destructor_test_defs.h", R"(
217 int foo();
218
219 class Fatal {
220 public:
221 ~Fatal() __attribute__((noreturn));
222 int bar();
223 int baz();
224 };
225
226 class NonFatal {
227 public:
228 ~NonFatal();
229 int bar();
230 };
231 )"));
232
233 ASSERT_THAT_ERROR(
234 test::checkDataflow<FunctionCallAnalysis>(
235 AnalysisInputs<FunctionCallAnalysis>(
236 Code, ast_matchers::hasName("target"),
237 [](ASTContext &C, Environment &) {
238 return FunctionCallAnalysis(C);
239 })
240 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"})
241 .withASTBuildVirtualMappedFiles(std::move(FilesContents)),
242 /*VerifyResults=*/
243 [&Expectations](
244 const llvm::StringMap<
245 DataflowAnalysisState<FunctionCallLattice>> &Results,
246 const AnalysisOutputs &) {
247 EXPECT_THAT(Results, Expectations);
248 }),
249 llvm::Succeeded());
250 }
251 };
252
253 MATCHER_P(HoldsFunctionCallLattice, m,
254 ((negation ? "doesn't hold" : "holds") +
255 llvm::StringRef(" a lattice element that ") +
256 DescribeMatcher<FunctionCallLattice>(m))
257 .str()) {
258 return ExplainMatchResult(m, arg.Lattice, result_listener);
259 }
260
261 MATCHER_P(HasCalledFunctions, m,
262 ((negation ? "doesn't hold" : "holds") +
263 llvm::StringRef(" a set of called functions that ") +
264 DescribeMatcher<FunctionCallLattice::FunctionSet>(m))
265 .str()) {
266 return ExplainMatchResult(m, arg.CalledFunctions, result_listener);
267 }
268
269 TEST_F(NoreturnDestructorTest, ConditionalOperatorBothBranchesReturn) {
270 std::string Code = R"(
271 #include "noreturn_destructor_test_defs.h"
272
273 void target(bool b) {
274 int value = b ? foo() : NonFatal().bar();
275 (void)0;
276 // [[p]]
277 }
278 )";
279 runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
280 "p", HoldsFunctionCallLattice(HasCalledFunctions(
281 UnorderedElementsAre("foo", "bar"))))));
282 }
283
284 TEST_F(NoreturnDestructorTest, ConditionalOperatorLeftBranchReturns) {
285 std::string Code = R"(
286 #include "noreturn_destructor_test_defs.h"
287
288 void target(bool b) {
289 int value = b ? foo() : Fatal().bar();
290 (void)0;
291 // [[p]]
292 }
293 )";
294 runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
295 "p", HoldsFunctionCallLattice(HasCalledFunctions(
296 UnorderedElementsAre("foo"))))));
297 }
298
299 TEST_F(NoreturnDestructorTest, ConditionalOperatorRightBranchReturns) {
300 std::string Code = R"(
301 #include "noreturn_destructor_test_defs.h"
302
303 void target(bool b) {
304 int value = b ? Fatal().bar() : foo();
305 (void)0;
306 // [[p]]
307 }
308 )";
309 runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
310 "p", HoldsFunctionCallLattice(HasCalledFunctions(
311 UnorderedElementsAre("foo"))))));
312 }
313
314 TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchesDoNotReturn) {
315 std::string Code = R"(
316 #include "noreturn_destructor_test_defs.h"
317
318 void target(bool b1, bool b2) {
319 int value = b1 ? foo() : (b2 ? Fatal().bar() : Fatal().baz());
320 (void)0;
321 // [[p]]
322 }
323 )";
324 runDataflow(Code, IsEmpty());
325 // FIXME: Called functions at point `p` should contain "foo".
326 }
327
328 TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchReturns) {
329 std::string Code = R"(
330 #include "noreturn_destructor_test_defs.h"
331
332 void target(bool b1, bool b2) {
333 int value = b1 ? Fatal().bar() : (b2 ? Fatal().baz() : foo());
334 (void)0;
335 // [[p]]
336 }
337 )";
338 runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
339 "p", HoldsFunctionCallLattice(HasCalledFunctions(
340 UnorderedElementsAre("baz", "foo"))))));
341 // FIXME: Called functions at point `p` should contain only "foo".
342 }
343
344 // Models an analysis that uses flow conditions.
345 class SpecialBoolAnalysis final
346 : public DataflowAnalysis<SpecialBoolAnalysis, NoopLattice> {
347 public:
348 explicit SpecialBoolAnalysis(ASTContext &Context)
349 : DataflowAnalysis<SpecialBoolAnalysis, NoopLattice>(Context) {}
350
351 static NoopLattice initialElement() { return {}; }
352
353 void transfer(const CFGElement *Elt, NoopLattice &, Environment &Env) {
354 auto CS = Elt->getAs<CFGStmt>();
355 if (!CS)
356 return;
357 const auto *S = CS->getStmt();
358 auto SpecialBoolRecordDecl = recordDecl(hasName("SpecialBool"));
359 auto HasSpecialBoolType = hasType(SpecialBoolRecordDecl);
360
361 if (const auto *E = selectFirst<CXXConstructExpr>(
362 "call", match(cxxConstructExpr(HasSpecialBoolType).bind("call"), *S,
363 getASTContext()))) {
364 auto &ConstructorVal = *Env.createValue(E->getType());
365 ConstructorVal.setProperty("is_set", Env.getBoolLiteralValue(false));
366 Env.setValue(*Env.getStorageLocation(*E, SkipPast::None), ConstructorVal);
367 } else if (const auto *E = selectFirst<CXXMemberCallExpr>(
368 "call", match(cxxMemberCallExpr(callee(cxxMethodDecl(ofClass(
369 SpecialBoolRecordDecl))))
370 .bind("call"),
371 *S, getASTContext()))) {
372 auto *Object = E->getImplicitObjectArgument();
373 assert(Object != nullptr);
374
375 auto *ObjectLoc =
376 Env.getStorageLocation(*Object, SkipPast::ReferenceThenPointer);
377 assert(ObjectLoc != nullptr);
378
379 auto &ConstructorVal = *Env.createValue(Object->getType());
380 ConstructorVal.setProperty("is_set", Env.getBoolLiteralValue(true));
381 Env.setValue(*ObjectLoc, ConstructorVal);
382 }
383 }
384
385 ComparisonResult compare(QualType Type, const Value &Val1,
386 const Environment &Env1, const Value &Val2,
387 const Environment &Env2) override {
388 const auto *Decl = Type->getAsCXXRecordDecl();
389 if (Decl == nullptr || Decl->getIdentifier() == nullptr ||
390 Decl->getName() != "SpecialBool")
391 return ComparisonResult::Unknown;
392
393 auto *IsSet1 = cast_or_null<BoolValue>(Val1.getProperty("is_set"));
394 auto *IsSet2 = cast_or_null<BoolValue>(Val2.getProperty("is_set"));
395 if (IsSet1 == nullptr)
396 return IsSet2 == nullptr ? ComparisonResult::Same
397 : ComparisonResult::Different;
398
399 if (IsSet2 == nullptr)
400 return ComparisonResult::Different;
401
402 return Env1.flowConditionImplies(*IsSet1) ==
403 Env2.flowConditionImplies(*IsSet2)
404 ? ComparisonResult::Same
405 : ComparisonResult::Different;
406 }
407
408 // Always returns `true` to accept the `MergedVal`.
409 bool merge(QualType Type, const Value &Val1, const Environment &Env1,
410 const Value &Val2, const Environment &Env2, Value &MergedVal,
411 Environment &MergedEnv) override {
412 const auto *Decl = Type->getAsCXXRecordDecl();
413 if (Decl == nullptr || Decl->getIdentifier() == nullptr ||
414 Decl->getName() != "SpecialBool")
415 return true;
416
417 auto *IsSet1 = cast_or_null<BoolValue>(Val1.getProperty("is_set"));
418 if (IsSet1 == nullptr)
419 return true;
420
421 auto *IsSet2 = cast_or_null<BoolValue>(Val2.getProperty("is_set"));
422 if (IsSet2 == nullptr)
423 return true;
424
425 auto &IsSet = MergedEnv.makeAtomicBoolValue();
426 MergedVal.setProperty("is_set", IsSet);
427 if (Env1.flowConditionImplies(*IsSet1) &&
428 Env2.flowConditionImplies(*IsSet2))
429 MergedEnv.addToFlowCondition(IsSet);
430
431 return true;
432 }
433 };
434
435 class JoinFlowConditionsTest : public Test {
436 protected:
437 template <typename Matcher>
438 void runDataflow(llvm::StringRef Code, Matcher Match) {
439 ASSERT_THAT_ERROR(
440 test::checkDataflow<SpecialBoolAnalysis>(
441 AnalysisInputs<SpecialBoolAnalysis>(
442 Code, ast_matchers::hasName("target"),
443 [](ASTContext &Context, Environment &Env) {
444 return SpecialBoolAnalysis(Context);
445 })
446 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
447 /*VerifyResults=*/[&Match](const llvm::StringMap<
448 DataflowAnalysisState<NoopLattice>>
449 &Results,
450 const AnalysisOutputs
451 &AO) { Match(Results, AO.ASTCtx); }),
452 llvm::Succeeded());
453 }
454 };
455
456 TEST_F(JoinFlowConditionsTest, JoinDistinctButProvablyEquivalentValues) {
457 std::string Code = R"(
458 struct SpecialBool {
459 SpecialBool() = default;
460 void set();
461 };
462
463 void target(bool Cond) {
464 SpecialBool Foo;
465 /*[[p1]]*/
466 if (Cond) {
467 Foo.set();
468 /*[[p2]]*/
469 } else {
470 Foo.set();
471 /*[[p3]]*/
472 }
473 (void)0;
474 /*[[p4]]*/
475 }
476 )";
477 runDataflow(
478 Code,
479 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
480 ASTContext &ASTCtx) {
481 ASSERT_THAT(Results.keys(),
482 UnorderedElementsAre("p1", "p2", "p3", "p4"));
483 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
484 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
485 const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
486 const Environment &Env4 = getEnvironmentAtAnnotation(Results, "p4");
487
488 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
489 ASSERT_THAT(FooDecl, NotNull());
490
491 auto GetFooValue = [FooDecl](const Environment &Env) {
492 return cast<BoolValue>(
493 Env.getValue(*FooDecl, SkipPast::None)->getProperty("is_set"));
494 };
495
496 EXPECT_FALSE(Env1.flowConditionImplies(*GetFooValue(Env1)));
497 EXPECT_TRUE(Env2.flowConditionImplies(*GetFooValue(Env2)));
498 EXPECT_TRUE(Env3.flowConditionImplies(*GetFooValue(Env3)));
499 EXPECT_TRUE(Env4.flowConditionImplies(*GetFooValue(Env4)));
500 });
501 }
502
503 class OptionalIntAnalysis final
504 : public DataflowAnalysis<OptionalIntAnalysis, NoopLattice> {
505 public:
506 explicit OptionalIntAnalysis(ASTContext &Context)
507 : DataflowAnalysis<OptionalIntAnalysis, NoopLattice>(Context) {}
508
509 static NoopLattice initialElement() { return {}; }
510
511 void transfer(const CFGElement *Elt, NoopLattice &, Environment &Env) {
512 auto CS = Elt->getAs<CFGStmt>();
513 if (!CS)
514 return;
515 const Stmt *S = CS->getStmt();
516 auto OptionalIntRecordDecl = recordDecl(hasName("OptionalInt"));
517 auto HasOptionalIntType = hasType(OptionalIntRecordDecl);
518
519 SmallVector<BoundNodes, 1> Matches = match(
520 stmt(anyOf(cxxConstructExpr(HasOptionalIntType).bind("construct"),
521 cxxOperatorCallExpr(
522 callee(cxxMethodDecl(ofClass(OptionalIntRecordDecl))))
523 .bind("operator"))),
524 *S, getASTContext());
525 if (const auto *E = selectFirst<CXXConstructExpr>(
526 "construct", Matches)) {
527 auto &ConstructorVal = *Env.createValue(E->getType());
528 ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(false));
529 Env.setValue(*Env.getStorageLocation(*E, SkipPast::None), ConstructorVal);
530 } else if (const auto *E =
531 selectFirst<CXXOperatorCallExpr>("operator", Matches)) {
532 assert(E->getNumArgs() > 0);
533 auto *Object = E->getArg(0);
534 assert(Object != nullptr);
535
536 auto *ObjectLoc =
537 Env.getStorageLocation(*Object, SkipPast::ReferenceThenPointer);
538 assert(ObjectLoc != nullptr);
539
540 auto &ConstructorVal = *Env.createValue(Object->getType());
541 ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(true));
542 Env.setValue(*ObjectLoc, ConstructorVal);
543 }
544 }
545
546 ComparisonResult compare(QualType Type, const Value &Val1,
547 const Environment &Env1, const Value &Val2,
548 const Environment &Env2) override {
549 // Nothing to say about a value that does not model an `OptionalInt`.
550 if (!Type->isRecordType() ||
551 Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
552 return ComparisonResult::Unknown;
553
554 auto *Prop1 = Val1.getProperty("has_value");
555 auto *Prop2 = Val2.getProperty("has_value");
556 assert(Prop1 != nullptr && Prop2 != nullptr);
557 return areEquivalentValues(*Prop1, *Prop2) ? ComparisonResult::Same
558 : ComparisonResult::Different;
559 }
560
561 bool merge(QualType Type, const Value &Val1, const Environment &Env1,
562 const Value &Val2, const Environment &Env2, Value &MergedVal,
563 Environment &MergedEnv) override {
564 // Nothing to say about a value that does not model an `OptionalInt`.
565 if (!Type->isRecordType() ||
566 Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
567 return false;
568
569 auto *HasValue1 = cast_or_null<BoolValue>(Val1.getProperty("has_value"));
570 if (HasValue1 == nullptr)
571 return false;
572
573 auto *HasValue2 = cast_or_null<BoolValue>(Val2.getProperty("has_value"));
574 if (HasValue2 == nullptr)
575 return false;
576
577 if (HasValue1 == HasValue2)
578 MergedVal.setProperty("has_value", *HasValue1);
579 else
580 MergedVal.setProperty("has_value", MergedEnv.makeTopBoolValue());
581 return true;
582 }
583 };
584
585 class WideningTest : public Test {
586 protected:
587 template <typename Matcher>
588 void runDataflow(llvm::StringRef Code, Matcher Match) {
589 tooling::FileContentMappings FilesContents;
590 FilesContents.push_back(
591 std::make_pair<std::string, std::string>("widening_test_defs.h", R"(
592 struct OptionalInt {
593 OptionalInt() = default;
594 OptionalInt& operator=(int);
595 };
596 )"));
597 ASSERT_THAT_ERROR(
598 checkDataflow<OptionalIntAnalysis>(
599 AnalysisInputs<OptionalIntAnalysis>(
600 Code, ast_matchers::hasName("target"),
601 [](ASTContext &Context, Environment &Env) {
602 return OptionalIntAnalysis(Context);
603 })
604 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"})
605 .withASTBuildVirtualMappedFiles(std::move(FilesContents)),
606 /*VerifyResults=*/[&Match](const llvm::StringMap<
607 DataflowAnalysisState<NoopLattice>>
608 &Results,
609 const AnalysisOutputs
610 &AO) { Match(Results, AO.ASTCtx); }),
611 llvm::Succeeded());
612 }
613 };
614
615 TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) {
616 std::string Code = R"(
617 #include "widening_test_defs.h"
618
619 void target(bool Cond) {
620 OptionalInt Foo;
621 /*[[p1]]*/
622 if (Cond) {
623 Foo = 1;
624 /*[[p2]]*/
625 }
626 (void)0;
627 /*[[p3]]*/
628 }
629 )";
630 runDataflow(
631 Code,
632 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
633 ASTContext &ASTCtx) {
634 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2", "p3"));
635 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
636 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
637 const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
638
639 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
640 ASSERT_THAT(FooDecl, NotNull());
641
642 auto GetFooValue = [FooDecl](const Environment &Env) {
643 return Env.getValue(*FooDecl, SkipPast::None);
644 };
645
646 EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
647 &Env1.getBoolLiteralValue(false));
648 EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
649 &Env2.getBoolLiteralValue(true));
650 EXPECT_TRUE(
651 isa<TopBoolValue>(GetFooValue(Env3)->getProperty("has_value")));
652 });
653 }
654
655 TEST_F(WideningTest, JoinDistinctValuesWithSameProperties) {
656 std::string Code = R"(
657 #include "widening_test_defs.h"
658
659 void target(bool Cond) {
660 OptionalInt Foo;
661 /*[[p1]]*/
662 if (Cond) {
663 Foo = 1;
664 /*[[p2]]*/
665 } else {
666 Foo = 2;
667 /*[[p3]]*/
668 }
669 (void)0;
670 /*[[p4]]*/
671 }
672 )";
673 runDataflow(
674 Code,
675 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
676 ASTContext &ASTCtx) {
677 ASSERT_THAT(Results.keys(),
678 UnorderedElementsAre("p1", "p2", "p3", "p4"));
679 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
680 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
681 const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
682 const Environment &Env4 = getEnvironmentAtAnnotation(Results, "p4");
683
684 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
685 ASSERT_THAT(FooDecl, NotNull());
686
687 auto GetFooValue = [FooDecl](const Environment &Env) {
688 return Env.getValue(*FooDecl, SkipPast::None);
689 };
690
691 EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
692 &Env1.getBoolLiteralValue(false));
693 EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
694 &Env2.getBoolLiteralValue(true));
695 EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
696 &Env3.getBoolLiteralValue(true));
697 EXPECT_EQ(GetFooValue(Env4)->getProperty("has_value"),
698 &Env4.getBoolLiteralValue(true));
699 });
700 }
701
702 TEST_F(WideningTest, DistinctPointersToTheSameLocationAreEquivalent) {
703 std::string Code = R"(
704 void target(int Foo, bool Cond) {
705 int *Bar = &Foo;
706 while (Cond) {
707 Bar = &Foo;
708 }
709 (void)0;
710 // [[p]]
711 }
712 )";
713 runDataflow(
714 Code,
715 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
716 ASTContext &ASTCtx) {
717 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
718 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
719
720 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
721 ASSERT_THAT(FooDecl, NotNull());
722
723 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
724 ASSERT_THAT(BarDecl, NotNull());
725
726 const auto *FooLoc = cast<ScalarStorageLocation>(
727 Env.getStorageLocation(*FooDecl, SkipPast::None));
728 const auto *BarVal =
729 cast<PointerValue>(Env.getValue(*BarDecl, SkipPast::None));
730 EXPECT_EQ(&BarVal->getPointeeLoc(), FooLoc);
731 });
732 }
733
734 TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) {
735 std::string Code = R"(
736 #include "widening_test_defs.h"
737
738 void target(bool Cond) {
739 OptionalInt Foo;
740 Foo = 1;
741 while (Cond) {
742 Foo = 2;
743 }
744 (void)0;
745 /*[[p]]*/
746 }
747 )";
748 runDataflow(
749 Code,
750 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
751 ASTContext &ASTCtx) {
752 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
753 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
754
755 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
756 ASSERT_THAT(FooDecl, NotNull());
757
758 const auto *FooVal = Env.getValue(*FooDecl, SkipPast::None);
759 EXPECT_EQ(FooVal->getProperty("has_value"),
760 &Env.getBoolLiteralValue(true));
761 });
762 }
763
764 class FlowConditionTest : public Test {
765 protected:
766 template <typename Matcher>
767 void runDataflow(llvm::StringRef Code, Matcher Match) {
768 ASSERT_THAT_ERROR(
769 checkDataflow<NoopAnalysis>(
770 AnalysisInputs<NoopAnalysis>(
771 Code, ast_matchers::hasName("target"),
772 [](ASTContext &Context, Environment &Env) {
773 return NoopAnalysis(Context, true);
774 })
775 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
776 /*VerifyResults=*/[&Match](const llvm::StringMap<
777 DataflowAnalysisState<NoopLattice>>
778 &Results,
779 const AnalysisOutputs
780 &AO) { Match(Results, AO.ASTCtx); }),
781 llvm::Succeeded());
782 }
783 };
784
785 TEST_F(FlowConditionTest, IfStmtSingleVar) {
786 std::string Code = R"(
787 void target(bool Foo) {
788 if (Foo) {
789 (void)0;
790 /*[[p1]]*/
791 } else {
792 (void)1;
793 /*[[p2]]*/
794 }
795 }
796 )";
797 runDataflow(
798 Code,
799 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
800 ASTContext &ASTCtx) {
801 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
802 ASSERT_THAT(FooDecl, NotNull());
803
804 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
805
806 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
807 auto *FooVal1 =
808 cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
809 EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
810
811 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
812 auto *FooVal2 =
813 cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
814 EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
815 });
816 }
817
818 TEST_F(FlowConditionTest, IfStmtSingleNegatedVar) {
819 std::string Code = R"(
820 void target(bool Foo) {
821 if (!Foo) {
822 (void)0;
823 /*[[p1]]*/
824 } else {
825 (void)1;
826 /*[[p2]]*/
827 }
828 }
829 )";
830 runDataflow(
831 Code,
832 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
833 ASTContext &ASTCtx) {
834 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
835 ASSERT_THAT(FooDecl, NotNull());
836
837 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
838
839 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
840 auto *FooVal1 =
841 cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
842 EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
843
844 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
845 auto *FooVal2 =
846 cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
847 EXPECT_TRUE(Env2.flowConditionImplies(*FooVal2));
848 });
849 }
850
851 TEST_F(FlowConditionTest, WhileStmt) {
852 std::string Code = R"(
853 void target(bool Foo) {
854 while (Foo) {
855 (void)0;
856 /*[[p]]*/
857 }
858 }
859 )";
860 runDataflow(
861 Code,
862 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
863 ASTContext &ASTCtx) {
864 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
865 ASSERT_THAT(FooDecl, NotNull());
866
867 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
868 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
869
870 auto *FooVal = cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
871 EXPECT_TRUE(Env.flowConditionImplies(*FooVal));
872 });
873 }
874
875 TEST_F(FlowConditionTest, Conjunction) {
876 std::string Code = R"(
877 void target(bool Foo, bool Bar) {
878 if (Foo && Bar) {
879 (void)0;
880 /*[[p1]]*/
881 } else {
882 (void)1;
883 /*[[p2]]*/
884 }
885 }
886 )";
887 runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
888 &Results,
889 ASTContext &ASTCtx) {
890 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
891 ASSERT_THAT(FooDecl, NotNull());
892
893 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
894 ASSERT_THAT(BarDecl, NotNull());
895
896 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
897
898 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
899 auto *FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
900 auto *BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
901 EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
902 EXPECT_TRUE(Env1.flowConditionImplies(*BarVal1));
903
904 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
905 auto *FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
906 auto *BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
907 EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
908 EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
909 });
910 }
911
912 TEST_F(FlowConditionTest, Disjunction) {
913 std::string Code = R"(
914 void target(bool Foo, bool Bar) {
915 if (Foo || Bar) {
916 (void)0;
917 /*[[p1]]*/
918 } else {
919 (void)1;
920 /*[[p2]]*/
921 }
922 }
923 )";
924 runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
925 &Results,
926 ASTContext &ASTCtx) {
927 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
928 ASSERT_THAT(FooDecl, NotNull());
929
930 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
931 ASSERT_THAT(BarDecl, NotNull());
932
933 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
934
935 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
936 auto *FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
937 auto *BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
938 EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
939 EXPECT_FALSE(Env1.flowConditionImplies(*BarVal1));
940
941 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
942 auto *FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
943 auto *BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
944 EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
945 EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
946 });
947 }
948
949 TEST_F(FlowConditionTest, NegatedConjunction) {
950 std::string Code = R"(
951 void target(bool Foo, bool Bar) {
952 if (!(Foo && Bar)) {
953 (void)0;
954 /*[[p1]]*/
955 } else {
956 (void)1;
957 /*[[p2]]*/
958 }
959 }
960 )";
961 runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
962 &Results,
963 ASTContext &ASTCtx) {
964 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
965 ASSERT_THAT(FooDecl, NotNull());
966
967 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
968 ASSERT_THAT(BarDecl, NotNull());
969
970 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
971
972 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
973 auto *FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
974 auto *BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
975 EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
976 EXPECT_FALSE(Env1.flowConditionImplies(*BarVal1));
977
978 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
979 auto *FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
980 auto *BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
981 EXPECT_TRUE(Env2.flowConditionImplies(*FooVal2));
982 EXPECT_TRUE(Env2.flowConditionImplies(*BarVal2));
983 });
984 }
985
986 TEST_F(FlowConditionTest, DeMorgan) {
987 std::string Code = R"(
988 void target(bool Foo, bool Bar) {
989 if (!(!Foo || !Bar)) {
990 (void)0;
991 /*[[p1]]*/
992 } else {
993 (void)1;
994 /*[[p2]]*/
995 }
996 }
997 )";
998 runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
999 &Results,
1000 ASTContext &ASTCtx) {
1001 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
1002 ASSERT_THAT(FooDecl, NotNull());
1003
1004 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1005 ASSERT_THAT(BarDecl, NotNull());
1006
1007 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1008
1009 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1010 auto *FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
1011 auto *BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
1012 EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
1013 EXPECT_TRUE(Env1.flowConditionImplies(*BarVal1));
1014
1015 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1016 auto *FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
1017 auto *BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
1018 EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
1019 EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
1020 });
1021 }
1022
1023 TEST_F(FlowConditionTest, Join) {
1024 std::string Code = R"(
1025 void target(bool Foo, bool Bar) {
1026 if (Bar) {
1027 if (!Foo)
1028 return;
1029 } else {
1030 if (!Foo)
1031 return;
1032 }
1033 (void)0;
1034 /*[[p]]*/
1035 }
1036 )";
1037 runDataflow(
1038 Code,
1039 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1040 ASTContext &ASTCtx) {
1041 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1042
1043 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
1044 ASSERT_THAT(FooDecl, NotNull());
1045
1046 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1047 auto *FooVal = cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
1048 EXPECT_TRUE(Env.flowConditionImplies(*FooVal));
1049 });
1050 }
1051
1052 // Verifies that flow conditions are properly constructed even when the
1053 // condition is not meaningfully interpreted.
1054 //
1055 // Note: currently, arbitrary function calls are uninterpreted, so the test
1056 // exercises this case. If and when we change that, this test will not add to
1057 // coverage (although it may still test a valuable case).
1058 TEST_F(FlowConditionTest, OpaqueFlowConditionMergesToOpaqueBool) {
1059 std::string Code = R"(
1060 bool foo();
1061
1062 void target() {
1063 bool Bar = true;
1064 if (foo())
1065 Bar = false;
1066 (void)0;
1067 /*[[p]]*/
1068 }
1069 )";
1070 runDataflow(
1071 Code,
1072 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1073 ASTContext &ASTCtx) {
1074 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1075 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1076
1077 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1078 ASSERT_THAT(BarDecl, NotNull());
1079
1080 auto &BarVal =
1081 *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::Reference));
1082
1083 EXPECT_FALSE(Env.flowConditionImplies(BarVal));
1084 });
1085 }
1086
1087 // Verifies that flow conditions are properly constructed even when the
1088 // condition is not meaningfully interpreted.
1089 //
1090 // Note: currently, fields with recursive type calls are uninterpreted (beneath
1091 // the first instance), so the test exercises this case. If and when we change
1092 // that, this test will not add to coverage (although it may still test a
1093 // valuable case).
1094 TEST_F(FlowConditionTest, OpaqueFieldFlowConditionMergesToOpaqueBool) {
1095 std::string Code = R"(
1096 struct Rec {
1097 Rec* Next;
1098 };
1099
1100 struct Foo {
1101 Rec* X;
1102 };
1103
1104 void target(Foo F) {
1105 bool Bar = true;
1106 if (F.X->Next)
1107 Bar = false;
1108 (void)0;
1109 /*[[p]]*/
1110 }
1111 )";
1112 runDataflow(
1113 Code,
1114 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1115 ASTContext &ASTCtx) {
1116 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1117 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1118
1119 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1120 ASSERT_THAT(BarDecl, NotNull());
1121
1122 auto &BarVal =
1123 *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::Reference));
1124
1125 EXPECT_FALSE(Env.flowConditionImplies(BarVal));
1126 });
1127 }
1128
1129 // Verifies that flow conditions are properly constructed even when the
1130 // condition is not meaningfully interpreted. Adds to above by nesting the
1131 // interestnig case inside a normal branch. This protects against degenerate
1132 // solutions which only test for empty flow conditions, for example.
1133 TEST_F(FlowConditionTest, OpaqueFlowConditionInsideBranchMergesToOpaqueBool) {
1134 std::string Code = R"(
1135 bool foo();
1136
1137 void target(bool Cond) {
1138 bool Bar = true;
1139 if (Cond) {
1140 if (foo())
1141 Bar = false;
1142 (void)0;
1143 /*[[p]]*/
1144 }
1145 }
1146 )";
1147 runDataflow(
1148 Code,
1149 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1150 ASTContext &ASTCtx) {
1151 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1152 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1153
1154 const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
1155 ASSERT_THAT(BarDecl, NotNull());
1156
1157 auto &BarVal =
1158 *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::Reference));
1159
1160 EXPECT_FALSE(Env.flowConditionImplies(BarVal));
1161 });
1162 }
1163
1164 TEST_F(FlowConditionTest, PointerToBoolImplicitCast) {
1165 std::string Code = R"(
1166 void target(int *Ptr) {
1167 bool Foo = false;
1168 if (Ptr) {
1169 Foo = true;
1170 /*[[p1]]*/
1171 }
1172
1173 (void)0;
1174 /*[[p2]]*/
1175 }
1176 )";
1177 runDataflow(
1178 Code,
1179 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1180 ASTContext &ASTCtx) {
1181 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1182
1183 const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
1184 ASSERT_THAT(FooDecl, NotNull());
1185
1186 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1187 auto &FooVal1 =
1188 *cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::Reference));
1189 EXPECT_TRUE(Env1.flowConditionImplies(FooVal1));
1190
1191 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1192 auto &FooVal2 =
1193 *cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::Reference));
1194 EXPECT_FALSE(Env2.flowConditionImplies(FooVal2));
1195 });
1196 }
1197
1198 class TopAnalysis final : public DataflowAnalysis<TopAnalysis, NoopLattice> {
1199 public:
1200 explicit TopAnalysis(ASTContext &Context)
1201 : DataflowAnalysis<TopAnalysis, NoopLattice>(Context) {}
1202
1203 static NoopLattice initialElement() { return {}; }
1204
1205 void transfer(const CFGElement *Elt, NoopLattice &, Environment &Env) {
1206 auto CS = Elt->getAs<CFGStmt>();
1207 if (!CS)
1208 return;
1209 const Stmt *S = CS->getStmt();
1210 SmallVector<BoundNodes, 1> Matches =
1211 match(callExpr(callee(functionDecl(hasName("makeTop")))).bind("top"),
1212 *S, getASTContext());
1213 if (const auto *E = selectFirst<CallExpr>("top", Matches)) {
1214 auto &Loc = Env.createStorageLocation(*E);
1215 Env.setValue(Loc, Env.makeTopBoolValue());
1216 Env.setStorageLocation(*E, Loc);
1217 }
1218 }
1219
1220 ComparisonResult compare(QualType Type, const Value &Val1,
1221 const Environment &Env1, const Value &Val2,
1222 const Environment &Env2) override {
1223 // Changes to a sound approximation, which allows us to test whether we can
1224 // (soundly) converge for some loops.
1225 return ComparisonResult::Unknown;
1226 }
1227 };
1228
1229 class TopTest : public Test {
1230 protected:
1231 template <typename Matcher>
1232 void runDataflow(llvm::StringRef Code, Matcher VerifyResults) {
1233 ASSERT_THAT_ERROR(
1234 checkDataflow<TopAnalysis>(
1235 AnalysisInputs<TopAnalysis>(
1236 Code, ast_matchers::hasName("target"),
1237 [](ASTContext &Context, Environment &Env) {
1238 return TopAnalysis(Context);
1239 })
1240 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
1241 VerifyResults),
1242 llvm::Succeeded());
1243 }
1244 };
1245
1246 // Tests that when Top is unused it remains Top.
1247 TEST_F(TopTest, UnusedTopInitializer) {
1248 std::string Code = R"(
1249 bool makeTop();
1250
1251 void target() {
1252 bool Foo = makeTop();
1253 /*[[p1]]*/
1254 (void)0;
1255 /*[[p2]]*/
1256 }
1257 )";
1258 runDataflow(
1259 Code,
1260 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1261 const AnalysisOutputs &AO) {
1262 ASSERT_THAT(Results.keys(),
1263 UnorderedElementsAre("p1", "p2"));
1264 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1265 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1266
1267 const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1268 ASSERT_THAT(FooDecl, NotNull());
1269
1270
1271 auto GetFooValue = [FooDecl](const Environment &Env) {
1272 return Env.getValue(*FooDecl, SkipPast::None);
1273 };
1274
1275 Value *FooVal1 = GetFooValue(Env1);
1276 ASSERT_THAT(FooVal1, NotNull());
1277 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1278 << debugString(FooVal1->getKind());
1279
1280 Value *FooVal2 = GetFooValue(Env2);
1281 ASSERT_THAT(FooVal2, NotNull());
1282 EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1283 << debugString(FooVal2->getKind());
1284
1285 EXPECT_EQ(FooVal1, FooVal2);
1286 });
1287 }
1288
1289 // Tests that when Top is unused it remains Top. Like above, but uses the
1290 // assignment form rather than initialization, which uses Top as an lvalue that
1291 // is *not* in an rvalue position.
1292 TEST_F(TopTest, UnusedTopAssignment) {
1293 std::string Code = R"(
1294 bool makeTop();
1295
1296 void target() {
1297 bool Foo;
1298 Foo = makeTop();
1299 /*[[p1]]*/
1300 (void)0;
1301 /*[[p2]]*/
1302 }
1303 )";
1304 runDataflow(
1305 Code,
1306 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1307 const AnalysisOutputs &AO) {
1308 ASSERT_THAT(Results.keys(),
1309 UnorderedElementsAre("p1", "p2"));
1310 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1311 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1312
1313 const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1314 ASSERT_THAT(FooDecl, NotNull());
1315
1316
1317 auto GetFooValue = [FooDecl](const Environment &Env) {
1318 return Env.getValue(*FooDecl, SkipPast::None);
1319 };
1320
1321 Value *FooVal1 = GetFooValue(Env1);
1322 ASSERT_THAT(FooVal1, NotNull());
1323 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1324 << debugString(FooVal1->getKind());
1325
1326 Value *FooVal2 = GetFooValue(Env2);
1327 ASSERT_THAT(FooVal2, NotNull());
1328 EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1329 << debugString(FooVal2->getKind());
1330
1331 EXPECT_EQ(FooVal1, FooVal2);
1332 });
1333 }
1334
1335 TEST_F(TopTest, UnusedTopJoinsToTop) {
1336 std::string Code = R"(
1337 bool makeTop();
1338
1339 void target(bool Cond, bool F) {
1340 bool Foo = makeTop();
1341 // Force a new CFG block.
1342 if (F) return;
1343 (void)0;
1344 /*[[p1]]*/
1345
1346 bool Zab1;
1347 bool Zab2;
1348 if (Cond) {
1349 Zab1 = true;
1350 } else {
1351 Zab2 = true;
1352 }
1353 (void)0;
1354 /*[[p2]]*/
1355 }
1356 )";
1357 runDataflow(
1358 Code,
1359 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1360 const AnalysisOutputs &AO) {
1361 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1362 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1363 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1364
1365 const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1366 ASSERT_THAT(FooDecl, NotNull());
1367
1368 auto GetFooValue = [FooDecl](const Environment &Env) {
1369 return Env.getValue(*FooDecl, SkipPast::None);
1370 };
1371
1372 Value *FooVal1 = GetFooValue(Env1);
1373 ASSERT_THAT(FooVal1, NotNull());
1374 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1375 << debugString(FooVal1->getKind());
1376
1377 Value *FooVal2 = GetFooValue(Env2);
1378 ASSERT_THAT(FooVal2, NotNull());
1379 EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1380 << debugString(FooVal2->getKind());
1381 });
1382 }
1383
1384 TEST_F(TopTest, TopUsedBeforeBranchJoinsToSameAtomicBool) {
1385 std::string Code = R"(
1386 bool makeTop();
1387
1388 void target(bool Cond, bool F) {
1389 bool Foo = makeTop();
1390 /*[[p0]]*/
1391
1392 // Use `Top`.
1393 bool Bar = Foo;
1394 // Force a new CFG block.
1395 if (F) return;
1396 (void)0;
1397 /*[[p1]]*/
1398
1399 bool Zab1;
1400 bool Zab2;
1401 if (Cond) {
1402 Zab1 = true;
1403 } else {
1404 Zab2 = true;
1405 }
1406 (void)0;
1407 /*[[p2]]*/
1408 }
1409 )";
1410 runDataflow(
1411 Code,
1412 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1413 const AnalysisOutputs &AO) {
1414 ASSERT_THAT(Results.keys(),
1415 UnorderedElementsAre("p0", "p1", "p2"));
1416 const Environment &Env0 = getEnvironmentAtAnnotation(Results, "p0");
1417 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1418 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1419
1420 const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1421 ASSERT_THAT(FooDecl, NotNull());
1422
1423 auto GetFooValue = [FooDecl](const Environment &Env) {
1424 return Env.getValue(*FooDecl, SkipPast::None);
1425 };
1426
1427 Value *FooVal0 = GetFooValue(Env0);
1428 ASSERT_THAT(FooVal0, NotNull());
1429 EXPECT_TRUE(isa<TopBoolValue>(FooVal0))
1430 << debugString(FooVal0->getKind());
1431
1432 Value *FooVal1 = GetFooValue(Env1);
1433 ASSERT_THAT(FooVal1, NotNull());
1434 EXPECT_TRUE(isa<AtomicBoolValue>(FooVal1))
1435 << debugString(FooVal1->getKind());
1436
1437 Value *FooVal2 = GetFooValue(Env2);
1438 ASSERT_THAT(FooVal2, NotNull());
1439 EXPECT_TRUE(isa<AtomicBoolValue>(FooVal2))
1440 << debugString(FooVal2->getKind());
1441
1442 EXPECT_EQ(FooVal2, FooVal1);
1443 });
1444 }
1445
1446 TEST_F(TopTest, TopUsedInBothBranchesJoinsToAtomic) {
1447 std::string Code = R"(
1448 bool makeTop();
1449
1450 void target(bool Cond, bool F) {
1451 bool Foo = makeTop();
1452 // Force a new CFG block.
1453 if (F) return;
1454 (void)0;
1455 /*[[p1]]*/
1456
1457 bool Zab1;
1458 bool Zab2;
1459 if (Cond) {
1460 Zab1 = Foo;
1461 } else {
1462 Zab2 = Foo;
1463 }
1464 (void)0;
1465 /*[[p2]]*/
1466 }
1467 )";
1468 runDataflow(
1469 Code,
1470 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1471 const AnalysisOutputs &AO) {
1472 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1473 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1474 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1475
1476 const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1477 ASSERT_THAT(FooDecl, NotNull());
1478
1479 auto GetFooValue = [FooDecl](const Environment &Env) {
1480 return Env.getValue(*FooDecl, SkipPast::None);
1481 };
1482
1483 Value *FooVal1 = GetFooValue(Env1);
1484 ASSERT_THAT(FooVal1, NotNull());
1485 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1486 << debugString(FooVal1->getKind());
1487
1488 Value *FooVal2 = GetFooValue(Env2);
1489 ASSERT_THAT(FooVal2, NotNull());
1490 EXPECT_TRUE(isa<AtomicBoolValue>(FooVal2))
1491 << debugString(FooVal2->getKind());
1492 });
1493 }
1494
1495 TEST_F(TopTest, TopUsedInBothBranchesWithoutPrecisionLoss) {
1496 std::string Code = R"(
1497 bool makeTop();
1498
1499 void target(bool Cond, bool F) {
1500 bool Foo = makeTop();
1501 // Force a new CFG block.
1502 if (F) return;
1503 (void)0;
1504
1505 bool Bar;
1506 if (Cond) {
1507 Bar = Foo;
1508 } else {
1509 Bar = Foo;
1510 }
1511 (void)0;
1512 /*[[p]]*/
1513 }
1514 )";
1515 runDataflow(
1516 Code,
1517 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1518 const AnalysisOutputs &AO) {
1519 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1520 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
1521
1522 const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1523 ASSERT_THAT(FooDecl, NotNull());
1524
1525 const ValueDecl *BarDecl = findValueDecl(AO.ASTCtx, "Bar");
1526 ASSERT_THAT(BarDecl, NotNull());
1527
1528 auto *FooVal =
1529 dyn_cast_or_null<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
1530 ASSERT_THAT(FooVal, NotNull());
1531
1532 auto *BarVal =
1533 dyn_cast_or_null<BoolValue>(Env.getValue(*BarDecl, SkipPast::None));
1534 ASSERT_THAT(BarVal, NotNull());
1535
1536 EXPECT_TRUE(Env.flowConditionImplies(Env.makeIff(*FooVal, *BarVal)));
1537 });
1538 }
1539
1540 TEST_F(TopTest, TopUnusedBeforeLoopHeadJoinsToTop) {
1541 std::string Code = R"(
1542 bool makeTop();
1543
1544 void target(bool Cond, bool F) {
1545 bool Foo = makeTop();
1546 // Force a new CFG block.
1547 if (F) return;
1548 (void)0;
1549 /*[[p1]]*/
1550
1551 while (Cond) {
1552 // Use `Foo`.
1553 bool Zab = Foo;
1554 Zab = false;
1555 Foo = makeTop();
1556 }
1557 (void)0;
1558 /*[[p2]]*/
1559 }
1560 )";
1561 runDataflow(
1562 Code,
1563 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1564 const AnalysisOutputs &AO) {
1565 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1566 const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
1567 const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
1568
1569 const ValueDecl *FooDecl = findValueDecl(AO.ASTCtx, "Foo");
1570 ASSERT_THAT(FooDecl, NotNull());
1571
1572 auto GetFooValue = [FooDecl](const Environment &Env) {
1573 return Env.getValue(*FooDecl, SkipPast::None);
1574 };
1575
1576 Value *FooVal1 = GetFooValue(Env1);
1577 ASSERT_THAT(FooVal1, NotNull());
1578 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1579 << debugString(FooVal1->getKind());
1580
1581 Value *FooVal2 = GetFooValue(Env2);
1582 ASSERT_THAT(FooVal2, NotNull());
1583 EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1584 << debugString(FooVal2->getKind());
1585
1586 });
1587 }
1588 } // namespace