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
42namespace {
43
44using namespace clang;
45using namespace dataflow;
46using namespace test;
47using namespace ast_matchers;
48using llvm::IsStringMapEntry;
49using ::testing::DescribeMatcher;
50using ::testing::IsEmpty;
51using ::testing::NotNull;
52using ::testing::Test;
53using ::testing::UnorderedElementsAre;
54
55class DataflowAnalysisTest : public Test {
56protected:
57 template <typename AnalysisT>
58 llvm::Expected<std::vector<
59 std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
60 runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
61 AST = tooling::buildASTFromCodeWithArgs(Code, Args: {"-std=c++11"});
62
63 auto *Func = selectFirst<FunctionDecl>(
64 BoundTo: "func",
65 Results: match(Matcher: functionDecl(ast_matchers::hasName(Name: "target")).bind(ID: "func"),
66 Context&: AST->getASTContext()));
67 assert(Func != nullptr);
68
69 ACFG =
70 std::make_unique<AdornedCFG>(args: llvm::cantFail(ValOrErr: AdornedCFG::build(Func: *Func)));
71
72 AnalysisT Analysis = MakeAnalysis(AST->getASTContext());
73 DACtx = std::make_unique<DataflowAnalysisContext>(
74 args: std::make_unique<WatchedLiteralsSolver>());
75 Environment Env(*DACtx, *Func);
76
77 return runDataflowAnalysis(*ACFG, Analysis, Env);
78 }
79
80 /// Returns the `CFGBlock` containing `S` (and asserts that it exists).
81 const CFGBlock *blockForStmt(const Stmt &S) {
82 const CFGBlock *Block = ACFG->getStmtToBlock().lookup(Val: &S);
83 assert(Block != nullptr);
84 return Block;
85 }
86
87 template <typename StateT>
88 const StateT &
89 blockStateForStmt(const std::vector<std::optional<StateT>> &BlockStates,
90 const Stmt &S) {
91 const std::optional<StateT> &MaybeState =
92 BlockStates[blockForStmt(S)->getBlockID()];
93 assert(MaybeState.has_value());
94 return *MaybeState;
95 }
96
97 /// Returns the first node that matches `Matcher` (and asserts that the match
98 /// was successful, i.e. the returned node is not null).
99 template <typename NodeT, typename MatcherT>
100 const NodeT &matchNode(MatcherT Matcher) {
101 const auto *Node = selectFirst<NodeT>(
102 "node", match(Matcher.bind("node"), AST->getASTContext()));
103 assert(Node != nullptr);
104 return *Node;
105 }
106
107 std::unique_ptr<ASTUnit> AST;
108 std::unique_ptr<AdornedCFG> ACFG;
109 std::unique_ptr<DataflowAnalysisContext> DACtx;
110};
111
112TEST_F(DataflowAnalysisTest, NoopAnalysis) {
113 auto BlockStates = llvm::cantFail(
114 ValOrErr: runAnalysis<NoopAnalysis>(Code: "void target() {}", MakeAnalysis: [](ASTContext &C) {
115 return NoopAnalysis(C,
116 // Don't use builtin transfer function.
117 DataflowAnalysisOptions{.BuiltinOpts: std::nullopt});
118 }));
119 EXPECT_EQ(BlockStates.size(), 2u);
120 EXPECT_TRUE(BlockStates[0].has_value());
121 EXPECT_TRUE(BlockStates[1].has_value());
122}
123
124// Basic test that `diagnoseFunction` calls the Diagnoser function for the
125// number of elements expected.
126TEST_F(DataflowAnalysisTest, DiagnoseFunctionDiagnoserCalledOnEachElement) {
127 std::string Code = R"(void target() { int x = 0; ++x; })";
128 std::unique_ptr<ASTUnit> AST =
129 tooling::buildASTFromCodeWithArgs(Code, Args: {"-std=c++11"});
130
131 auto *Func =
132 cast<FunctionDecl>(Val: findValueDecl(ASTCtx&: AST->getASTContext(), Name: "target"));
133 auto Diagnoser = [](const CFGElement &Elt, ASTContext &,
134 const TransferStateForDiagnostics<NoopLattice> &) {
135 llvm::SmallVector<std::string> Diagnostics(1);
136 llvm::raw_string_ostream OS(Diagnostics.front());
137 Elt.dumpToStream(OS);
138 return Diagnostics;
139 };
140 auto Result = diagnoseFunction<NoopAnalysis, std::string>(
141 FuncDecl: *Func, ASTCtx&: AST->getASTContext(), Diagnoser);
142 // `diagnoseFunction` provides no guarantees about the order in which elements
143 // are visited, so we use `UnorderedElementsAre`.
144 EXPECT_THAT_EXPECTED(Result, llvm::HasValue(UnorderedElementsAre(
145 "0\n", "int x = 0;\n", "x\n", "++x\n",
146 " (Lifetime ends)\n")));
147}
148
149// Tests for the statement-to-block map.
150using StmtToBlockTest = DataflowAnalysisTest;
151
152TEST_F(StmtToBlockTest, ConditionalOperator) {
153 std::string Code = R"(
154 void target(bool b) {
155 int i = b ? 1 : 0;
156 }
157 )";
158 ASSERT_THAT_ERROR(runAnalysis<NoopAnalysis>(
159 Code, [](ASTContext &C) { return NoopAnalysis(C); })
160 .takeError(),
161 llvm::Succeeded());
162
163 const auto &IDecl = matchNode<DeclStmt>(Matcher: declStmt(has(varDecl(hasName(Name: "i")))));
164 const auto &ConditionalOp =
165 matchNode<ConditionalOperator>(Matcher: conditionalOperator());
166
167 // The conditional operator should be associated with the same block as the
168 // `DeclStmt` for `i`. (Specifically, the conditional operator should not be
169 // associated with the block for which it is the terminator.)
170 EXPECT_EQ(blockForStmt(IDecl), blockForStmt(ConditionalOp));
171}
172
173TEST_F(StmtToBlockTest, LogicalAnd) {
174 std::string Code = R"(
175 void target(bool b1, bool b2) {
176 bool b = b1 && b2;
177 }
178 )";
179 ASSERT_THAT_ERROR(runAnalysis<NoopAnalysis>(
180 Code, [](ASTContext &C) { return NoopAnalysis(C); })
181 .takeError(),
182 llvm::Succeeded());
183
184 const auto &BDecl = matchNode<DeclStmt>(Matcher: declStmt(has(varDecl(hasName(Name: "b")))));
185 const auto &AndOp =
186 matchNode<BinaryOperator>(Matcher: binaryOperator(hasOperatorName(Name: "&&")));
187
188 // The `&&` operator should be associated with the same block as the
189 // `DeclStmt` for `b`. (Specifically, the `&&` operator should not be
190 // associated with the block for which it is the terminator.)
191 EXPECT_EQ(blockForStmt(BDecl), blockForStmt(AndOp));
192}
193
194TEST_F(StmtToBlockTest, IfStatementWithLogicalAnd) {
195 std::string Code = R"(
196 void target(bool b1, bool b2) {
197 if (b1 && b2)
198 ;
199 }
200 )";
201 ASSERT_THAT_ERROR(runAnalysis<NoopAnalysis>(
202 Code, [](ASTContext &C) { return NoopAnalysis(C); })
203 .takeError(),
204 llvm::Succeeded());
205
206 const auto &If = matchNode<IfStmt>(Matcher: ifStmt());
207 const auto &B2 =
208 matchNode<DeclRefExpr>(Matcher: declRefExpr(to(InnerMatcher: varDecl(hasName(Name: "b2")))));
209 const auto &AndOp =
210 matchNode<BinaryOperator>(Matcher: binaryOperator(hasOperatorName(Name: "&&")));
211
212 // The if statement is the terminator for the block that contains both `b2`
213 // and the `&&` operator (which appears only as a terminator condition, not
214 // as a regular `CFGElement`).
215 const CFGBlock *IfBlock = blockForStmt(If);
216 const CFGBlock *B2Block = blockForStmt(B2);
217 const CFGBlock *AndOpBlock = blockForStmt(AndOp);
218 EXPECT_EQ(IfBlock, B2Block);
219 EXPECT_EQ(IfBlock, AndOpBlock);
220}
221
222// Tests that check we discard state for expressions correctly.
223using DiscardExprStateTest = DataflowAnalysisTest;
224
225TEST_F(DiscardExprStateTest, WhileStatement) {
226 std::string Code = R"(
227 void foo(int *p);
228 void target(int *p) {
229 while (p != nullptr)
230 foo(p);
231 }
232 )";
233 auto BlockStates = llvm::cantFail(ValOrErr: runAnalysis<NoopAnalysis>(
234 Code, MakeAnalysis: [](ASTContext &C) { return NoopAnalysis(C); }));
235
236 const auto &NotEqOp =
237 matchNode<BinaryOperator>(Matcher: binaryOperator(hasOperatorName(Name: "!=")));
238 const auto &CallFoo =
239 matchNode<CallExpr>(Matcher: callExpr(callee(InnerMatcher: functionDecl(hasName(Name: "foo")))));
240
241 // In the block that evaluates the expression `p != nullptr`, this expression
242 // is associated with a value.
243 const auto &NotEqOpState = blockStateForStmt(BlockStates, NotEqOp);
244 EXPECT_NE(NotEqOpState.Env.getValue(NotEqOp), nullptr);
245
246 // In the block that calls `foo(p)`, the value for `p != nullptr` is discarded
247 // because it is not consumed outside the block it is in.
248 const auto &CallFooState = blockStateForStmt(BlockStates, CallFoo);
249 EXPECT_EQ(CallFooState.Env.getValue(NotEqOp), nullptr);
250}
251
252TEST_F(DiscardExprStateTest, BooleanOperator) {
253 std::string Code = R"(
254 void f();
255 void target(bool b1, bool b2) {
256 if (b1 && b2)
257 f();
258 }
259 )";
260 auto BlockStates = llvm::cantFail(ValOrErr: runAnalysis<NoopAnalysis>(
261 Code, MakeAnalysis: [](ASTContext &C) { return NoopAnalysis(C); }));
262
263 const auto &AndOp =
264 matchNode<BinaryOperator>(Matcher: binaryOperator(hasOperatorName(Name: "&&")));
265 const auto &CallF =
266 matchNode<CallExpr>(Matcher: callExpr(callee(InnerMatcher: functionDecl(hasName(Name: "f")))));
267
268 // In the block that evaluates the LHS of the `&&` operator, the LHS is
269 // associated with a value, while the right-hand side is not (unsurprisingly,
270 // as it hasn't been evaluated yet).
271 const auto &LHSState = blockStateForStmt(BlockStates, *AndOp.getLHS());
272 auto *LHSValue = cast<BoolValue>(LHSState.Env.getValue(*AndOp.getLHS()));
273 EXPECT_NE(LHSValue, nullptr);
274 EXPECT_EQ(LHSState.Env.getValue(*AndOp.getRHS()), nullptr);
275
276 // In the block that evaluates the RHS, both the LHS and RHS are associated
277 // with values, as they are both subexpressions of the `&&` operator, which
278 // is evaluated in a later block.
279 const auto &RHSState = blockStateForStmt(BlockStates, *AndOp.getRHS());
280 EXPECT_EQ(RHSState.Env.getValue(*AndOp.getLHS()), LHSValue);
281 auto *RHSValue = RHSState.Env.get<BoolValue>(*AndOp.getRHS());
282 EXPECT_NE(RHSValue, nullptr);
283
284 // In the block that evaluates `b1 && b2`, the `&&` as well as its operands
285 // are associated with values.
286 const auto &AndOpState = blockStateForStmt(BlockStates, AndOp);
287 EXPECT_EQ(AndOpState.Env.getValue(*AndOp.getLHS()), LHSValue);
288 EXPECT_EQ(AndOpState.Env.getValue(*AndOp.getRHS()), RHSValue);
289 EXPECT_EQ(AndOpState.Env.getValue(AndOp),
290 &AndOpState.Env.makeAnd(*LHSValue, *RHSValue));
291
292 // In the block that calls `f()`, none of `b1`, `b2`, or `b1 && b2` should be
293 // associated with values.
294 const auto &CallFState = blockStateForStmt(BlockStates, CallF);
295 EXPECT_EQ(CallFState.Env.getValue(*AndOp.getLHS()), nullptr);
296 EXPECT_EQ(CallFState.Env.getValue(*AndOp.getRHS()), nullptr);
297 EXPECT_EQ(CallFState.Env.getValue(AndOp), nullptr);
298}
299
300TEST_F(DiscardExprStateTest, ConditionalOperator) {
301 std::string Code = R"(
302 void f(int*, int);
303 void g();
304 bool cond();
305
306 void target() {
307 int i = 0;
308 if (cond())
309 f(&i, cond() ? 1 : 0);
310 g();
311 }
312 )";
313 auto BlockStates = llvm::cantFail(ValOrErr: runAnalysis<NoopAnalysis>(
314 Code, MakeAnalysis: [](ASTContext &C) { return NoopAnalysis(C); }));
315
316 const auto &AddrOfI =
317 matchNode<UnaryOperator>(Matcher: unaryOperator(hasOperatorName(Name: "&")));
318 const auto &CallF =
319 matchNode<CallExpr>(Matcher: callExpr(callee(InnerMatcher: functionDecl(hasName(Name: "f")))));
320 const auto &CallG =
321 matchNode<CallExpr>(Matcher: callExpr(callee(InnerMatcher: functionDecl(hasName(Name: "g")))));
322
323 // In the block that evaluates `&i`, it should obviously have a value.
324 const auto &AddrOfIState = blockStateForStmt(BlockStates, AddrOfI);
325 auto *AddrOfIVal = AddrOfIState.Env.get<PointerValue>(AddrOfI);
326 EXPECT_NE(AddrOfIVal, nullptr);
327
328 // Because of the conditional operator, the `f(...)` call is evaluated in a
329 // different block than `&i`, but `&i` still needs to have a value here
330 // because it's a subexpression of the call.
331 const auto &CallFState = blockStateForStmt(BlockStates, CallF);
332 EXPECT_NE(&CallFState, &AddrOfIState);
333 EXPECT_EQ(CallFState.Env.get<PointerValue>(AddrOfI), AddrOfIVal);
334
335 // In the block that calls `g()`, `&i` should no longer be associated with a
336 // value.
337 const auto &CallGState = blockStateForStmt(BlockStates, CallG);
338 EXPECT_EQ(CallGState.Env.get<PointerValue>(AddrOfI), nullptr);
339}
340
341struct NonConvergingLattice {
342 int State;
343
344 bool operator==(const NonConvergingLattice &Other) const {
345 return State == Other.State;
346 }
347
348 LatticeJoinEffect join(const NonConvergingLattice &Other) {
349 if (Other.State == 0)
350 return LatticeJoinEffect::Unchanged;
351 State += Other.State;
352 return LatticeJoinEffect::Changed;
353 }
354};
355
356class NonConvergingAnalysis
357 : public DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice> {
358public:
359 explicit NonConvergingAnalysis(ASTContext &Context)
360 : DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice>(
361 Context,
362 // Don't apply builtin transfer function.
363 DataflowAnalysisOptions{.BuiltinOpts: std::nullopt}) {}
364
365 static NonConvergingLattice initialElement() { return {.State: 0}; }
366
367 void transfer(const CFGElement &, NonConvergingLattice &E, Environment &) {
368 ++E.State;
369 }
370};
371
372TEST_F(DataflowAnalysisTest, NonConvergingAnalysis) {
373 std::string Code = R"(
374 void target() {
375 while(true) {}
376 }
377 )";
378 auto Res = runAnalysis<NonConvergingAnalysis>(
379 Code, MakeAnalysis: [](ASTContext &C) { return NonConvergingAnalysis(C); });
380 EXPECT_EQ(llvm::toString(Res.takeError()),
381 "maximum number of blocks processed");
382}
383
384// Regression test for joins of bool-typed lvalue expressions. The first loop
385// results in two passes through the code that follows. Each pass results in a
386// different `StorageLocation` for the pointee of `v`. Then, the second loop
387// causes a join at the loop head where the two environments map expresssion
388// `*v` to different `StorageLocation`s.
389//
390// An earlier version crashed for this condition (for boolean-typed lvalues), so
391// this test only verifies that the analysis runs successfully, without
392// examining any details of the results.
393TEST_F(DataflowAnalysisTest, JoinBoolLValues) {
394 std::string Code = R"(
395 void target() {
396 for (int x = 1; x; x = 0)
397 (void)x;
398 bool *v;
399 if (*v)
400 for (int x = 1; x; x = 0)
401 (void)x;
402 }
403 )";
404 ASSERT_THAT_ERROR(
405 runAnalysis<NoopAnalysis>(Code,
406 [](ASTContext &C) {
407 auto EnableBuiltIns = DataflowAnalysisOptions{
408 DataflowAnalysisContext::Options{}};
409 return NoopAnalysis(C, EnableBuiltIns);
410 })
411 .takeError(),
412 llvm::Succeeded());
413}
414
415struct FunctionCallLattice {
416 using FunctionSet = llvm::SmallSet<std::string, 8>;
417 FunctionSet CalledFunctions;
418
419 bool operator==(const FunctionCallLattice &Other) const {
420 return CalledFunctions == Other.CalledFunctions;
421 }
422
423 LatticeJoinEffect join(const FunctionCallLattice &Other) {
424 if (Other.CalledFunctions.empty())
425 return LatticeJoinEffect::Unchanged;
426 const size_t size_before = CalledFunctions.size();
427 CalledFunctions.insert(I: Other.CalledFunctions.begin(),
428 E: Other.CalledFunctions.end());
429 return CalledFunctions.size() == size_before ? LatticeJoinEffect::Unchanged
430 : LatticeJoinEffect::Changed;
431 }
432};
433
434std::ostream &operator<<(std::ostream &OS, const FunctionCallLattice &L) {
435 std::string S;
436 llvm::raw_string_ostream ROS(S);
437 llvm::interleaveComma(c: L.CalledFunctions, os&: ROS);
438 return OS << "{" << S << "}";
439}
440
441class FunctionCallAnalysis
442 : public DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice> {
443public:
444 explicit FunctionCallAnalysis(ASTContext &Context)
445 : DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice>(Context) {}
446
447 static FunctionCallLattice initialElement() { return {}; }
448
449 void transfer(const CFGElement &Elt, FunctionCallLattice &E, Environment &) {
450 auto CS = Elt.getAs<CFGStmt>();
451 if (!CS)
452 return;
453 const auto *S = CS->getStmt();
454 if (auto *C = dyn_cast<CallExpr>(Val: S)) {
455 if (auto *F = dyn_cast<FunctionDecl>(Val: C->getCalleeDecl())) {
456 E.CalledFunctions.insert(V: F->getNameInfo().getAsString());
457 }
458 }
459 }
460};
461
462class NoreturnDestructorTest : public Test {
463protected:
464 template <typename Matcher>
465 void runDataflow(llvm::StringRef Code, Matcher Expectations) {
466 tooling::FileContentMappings FilesContents;
467 FilesContents.push_back(x: std::make_pair<std::string, std::string>(
468 x: "noreturn_destructor_test_defs.h", y: R"(
469 int foo();
470
471 class Fatal {
472 public:
473 ~Fatal() __attribute__((noreturn));
474 int bar();
475 int baz();
476 };
477
478 class NonFatal {
479 public:
480 ~NonFatal();
481 int bar();
482 };
483 )"));
484
485 ASSERT_THAT_ERROR(
486 test::checkDataflow<FunctionCallAnalysis>(
487 AnalysisInputs<FunctionCallAnalysis>(
488 Code, ast_matchers::hasName("target"),
489 [](ASTContext &C, Environment &) {
490 return FunctionCallAnalysis(C);
491 })
492 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"})
493 .withASTBuildVirtualMappedFiles(std::move(FilesContents)),
494 /*VerifyResults=*/
495 [&Expectations](
496 const llvm::StringMap<
497 DataflowAnalysisState<FunctionCallLattice>> &Results,
498 const AnalysisOutputs &) {
499 EXPECT_THAT(Results, Expectations);
500 }),
501 llvm::Succeeded());
502 }
503};
504
505MATCHER_P(HoldsFunctionCallLattice, m,
506 ((negation ? "doesn't hold" : "holds") +
507 llvm::StringRef(" a lattice element that ") +
508 DescribeMatcher<FunctionCallLattice>(m))
509 .str()) {
510 return ExplainMatchResult(m, arg.Lattice, result_listener);
511}
512
513MATCHER_P(HasCalledFunctions, m,
514 ((negation ? "doesn't hold" : "holds") +
515 llvm::StringRef(" a set of called functions that ") +
516 DescribeMatcher<FunctionCallLattice::FunctionSet>(m))
517 .str()) {
518 return ExplainMatchResult(m, arg.CalledFunctions, result_listener);
519}
520
521TEST_F(NoreturnDestructorTest, ConditionalOperatorBothBranchesReturn) {
522 std::string Code = R"(
523 #include "noreturn_destructor_test_defs.h"
524
525 void target(bool b) {
526 int value = b ? foo() : NonFatal().bar();
527 (void)0;
528 // [[p]]
529 }
530 )";
531 runDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
532 KM: "p", VM: HoldsFunctionCallLattice(gmock_p0: HasCalledFunctions(
533 gmock_p0: UnorderedElementsAre(matchers: "foo", matchers: "bar"))))));
534}
535
536TEST_F(NoreturnDestructorTest, ConditionalOperatorLeftBranchReturns) {
537 std::string Code = R"(
538 #include "noreturn_destructor_test_defs.h"
539
540 void target(bool b) {
541 int value = b ? foo() : Fatal().bar();
542 (void)0;
543 // [[p]]
544 }
545 )";
546 runDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
547 KM: "p", VM: HoldsFunctionCallLattice(gmock_p0: HasCalledFunctions(
548 gmock_p0: UnorderedElementsAre(matchers: "foo"))))));
549}
550
551TEST_F(NoreturnDestructorTest,
552 ConditionalOperatorConstantCondition_LeftBranchReturns) {
553 std::string Code = R"(
554 #include "noreturn_destructor_test_defs.h"
555
556 void target() {
557 int value = true ? foo() : Fatal().bar();
558 (void)0;
559 // [[p]]
560 }
561 )";
562 runDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
563 KM: "p", VM: HoldsFunctionCallLattice(gmock_p0: HasCalledFunctions(
564 gmock_p0: UnorderedElementsAre(matchers: "foo"))))));
565}
566
567TEST_F(NoreturnDestructorTest, ConditionalOperatorRightBranchReturns) {
568 std::string Code = R"(
569 #include "noreturn_destructor_test_defs.h"
570
571 void target(bool b) {
572 int value = b ? Fatal().bar() : foo();
573 (void)0;
574 // [[p]]
575 }
576 )";
577 runDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
578 KM: "p", VM: HoldsFunctionCallLattice(gmock_p0: HasCalledFunctions(
579 gmock_p0: UnorderedElementsAre(matchers: "foo"))))));
580}
581
582TEST_F(NoreturnDestructorTest,
583 ConditionalOperatorConstantCondition_RightBranchReturns) {
584 std::string Code = R"(
585 #include "noreturn_destructor_test_defs.h"
586
587 void target() {
588 int value = false ? Fatal().bar() : foo();
589 (void)0;
590 // [[p]]
591 }
592 )";
593 runDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
594 KM: "p", VM: HoldsFunctionCallLattice(gmock_p0: HasCalledFunctions(
595 gmock_p0: UnorderedElementsAre(matchers: "foo"))))));
596}
597
598TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchesDoNotReturn) {
599 std::string Code = R"(
600 #include "noreturn_destructor_test_defs.h"
601
602 void target(bool b1, bool b2) {
603 int value = b1 ? foo() : (b2 ? Fatal().bar() : Fatal().baz());
604 (void)0;
605 // [[p]]
606 }
607 )";
608 runDataflow(Code, Expectations: IsEmpty());
609 // FIXME: Called functions at point `p` should contain "foo".
610}
611
612TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchReturns) {
613 std::string Code = R"(
614 #include "noreturn_destructor_test_defs.h"
615
616 void target(bool b1, bool b2) {
617 int value = b1 ? Fatal().bar() : (b2 ? Fatal().baz() : foo());
618 (void)0;
619 // [[p]]
620 }
621 )";
622 runDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
623 KM: "p", VM: HoldsFunctionCallLattice(gmock_p0: HasCalledFunctions(
624 gmock_p0: UnorderedElementsAre(matchers: "baz", matchers: "foo"))))));
625 // FIXME: Called functions at point `p` should contain only "foo".
626}
627
628// Models an analysis that uses flow conditions.
629class SpecialBoolAnalysis final
630 : public DataflowAnalysis<SpecialBoolAnalysis, NoopLattice> {
631public:
632 explicit SpecialBoolAnalysis(ASTContext &Context, Environment &Env)
633 : DataflowAnalysis<SpecialBoolAnalysis, NoopLattice>(Context) {
634 Env.getDataflowAnalysisContext().setSyntheticFieldCallback(
635 [](QualType Ty) -> llvm::StringMap<QualType> {
636 RecordDecl *RD = Ty->getAsRecordDecl();
637 if (RD == nullptr || RD->getIdentifier() == nullptr ||
638 RD->getName() != "SpecialBool")
639 return {};
640 return {{"is_set", RD->getASTContext().BoolTy}};
641 });
642 }
643
644 static NoopLattice initialElement() { return {}; }
645
646 void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
647 auto CS = Elt.getAs<CFGStmt>();
648 if (!CS)
649 return;
650 const auto *S = CS->getStmt();
651 auto SpecialBoolRecordDecl = recordDecl(hasName(Name: "SpecialBool"));
652 auto HasSpecialBoolType = hasType(InnerMatcher: SpecialBoolRecordDecl);
653
654 if (const auto *E = selectFirst<CXXConstructExpr>(
655 BoundTo: "call", Results: match(Matcher: cxxConstructExpr(HasSpecialBoolType).bind(ID: "call"), Node: *S,
656 Context&: getASTContext()))) {
657 Env.setValue(Loc: Env.getResultObjectLocation(*E).getSyntheticField(Name: "is_set"),
658 Val&: Env.getBoolLiteralValue(Value: false));
659 } else if (const auto *E = selectFirst<CXXMemberCallExpr>(
660 BoundTo: "call", Results: match(Matcher: cxxMemberCallExpr(callee(InnerMatcher: cxxMethodDecl(ofClass(
661 InnerMatcher: SpecialBoolRecordDecl))))
662 .bind(ID: "call"),
663 Node: *S, Context&: getASTContext()))) {
664 if (RecordStorageLocation *ObjectLoc = getImplicitObjectLocation(MCE: *E, Env))
665 Env.setValue(Loc: ObjectLoc->getSyntheticField(Name: "is_set"),
666 Val&: Env.getBoolLiteralValue(Value: true));
667 }
668 }
669};
670
671class JoinFlowConditionsTest : public Test {
672protected:
673 template <typename Matcher>
674 void runDataflow(llvm::StringRef Code, Matcher Match) {
675 ASSERT_THAT_ERROR(
676 test::checkDataflow<SpecialBoolAnalysis>(
677 AnalysisInputs<SpecialBoolAnalysis>(
678 Code, ast_matchers::hasName("target"),
679 [](ASTContext &Context, Environment &Env) {
680 return SpecialBoolAnalysis(Context, Env);
681 })
682 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
683 /*VerifyResults=*/[&Match](const llvm::StringMap<
684 DataflowAnalysisState<NoopLattice>>
685 &Results,
686 const AnalysisOutputs
687 &AO) { Match(Results, AO.ASTCtx); }),
688 llvm::Succeeded());
689 }
690};
691
692TEST_F(JoinFlowConditionsTest, JoinDistinctButProvablyEquivalentValues) {
693 std::string Code = R"(
694 struct SpecialBool {
695 SpecialBool() = default;
696 void set();
697 };
698
699 void target(bool Cond) {
700 SpecialBool Foo;
701 /*[[p1]]*/
702 if (Cond) {
703 Foo.set();
704 /*[[p2]]*/
705 } else {
706 Foo.set();
707 /*[[p3]]*/
708 }
709 (void)0;
710 /*[[p4]]*/
711 }
712 )";
713 runDataflow(
714 Code,
715 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
716 ASTContext &ASTCtx) {
717 ASSERT_THAT(Results.keys(),
718 UnorderedElementsAre("p1", "p2", "p3", "p4"));
719 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
720 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
721 const Environment &Env3 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p3");
722 const Environment &Env4 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p4");
723
724 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
725 ASSERT_THAT(FooDecl, NotNull());
726
727 auto GetFoo = [FooDecl](const Environment &Env) -> const Formula & {
728 auto *Loc =
729 cast<RecordStorageLocation>(Val: Env.getStorageLocation(D: *FooDecl));
730 return cast<BoolValue>(Val: Env.getValue(Loc: Loc->getSyntheticField(Name: "is_set")))
731 ->formula();
732 };
733
734 EXPECT_FALSE(Env1.proves(GetFoo(Env1)));
735 EXPECT_TRUE(Env2.proves(GetFoo(Env2)));
736 EXPECT_TRUE(Env3.proves(GetFoo(Env3)));
737 EXPECT_TRUE(Env4.proves(GetFoo(Env4)));
738 });
739}
740
741class NullPointerAnalysis final
742 : public DataflowAnalysis<NullPointerAnalysis, NoopLattice> {
743public:
744 explicit NullPointerAnalysis(ASTContext &Context)
745 : DataflowAnalysis<NullPointerAnalysis, NoopLattice>(Context) {}
746
747 static NoopLattice initialElement() { return {}; }
748
749 void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
750 auto CS = Elt.getAs<CFGStmt>();
751 if (!CS)
752 return;
753 const Stmt *S = CS->getStmt();
754 const Expr *E = dyn_cast<Expr>(Val: S);
755 if (!E)
756 return;
757
758 if (!E->getType()->isPointerType())
759 return;
760
761 // Make sure we have a `PointerValue` for `E`.
762 auto *PtrVal = cast_or_null<PointerValue>(Val: Env.getValue(E: *E));
763 if (PtrVal == nullptr) {
764 PtrVal = cast<PointerValue>(Val: Env.createValue(Type: E->getType()));
765 Env.setValue(E: *E, Val&: *PtrVal);
766 }
767
768 if (auto *Cast = dyn_cast<ImplicitCastExpr>(Val: E);
769 Cast && Cast->getCastKind() == CK_NullToPointer)
770 PtrVal->setProperty(Name: "is_null", Val&: Env.getBoolLiteralValue(Value: true));
771 else if (auto *Op = dyn_cast<UnaryOperator>(Val: E);
772 Op && Op->getOpcode() == UO_AddrOf)
773 PtrVal->setProperty(Name: "is_null", Val&: Env.getBoolLiteralValue(Value: false));
774 }
775
776 ComparisonResult compare(QualType Type, const Value &Val1,
777 const Environment &Env1, const Value &Val2,
778 const Environment &Env2) override {
779 // Nothing to say about a value that is not a pointer.
780 if (!Type->isPointerType())
781 return ComparisonResult::Unknown;
782
783 auto *Prop1 = Val1.getProperty(Name: "is_null");
784 auto *Prop2 = Val2.getProperty(Name: "is_null");
785 assert(Prop1 != nullptr && Prop2 != nullptr);
786 return areEquivalentValues(Val1: *Prop1, Val2: *Prop2) ? ComparisonResult::Same
787 : ComparisonResult::Different;
788 }
789
790 void join(QualType Type, const Value &Val1, const Environment &Env1,
791 const Value &Val2, const Environment &Env2, Value &JoinedVal,
792 Environment &JoinedEnv) override {
793 // Nothing to say about a value that is not a pointer...
794 if (!Type->isPointerType())
795 return;
796
797 // ... or, a pointer without the `is_null` property.
798 auto *IsNull1 = cast_or_null<BoolValue>(Val: Val1.getProperty(Name: "is_null"));
799 auto *IsNull2 = cast_or_null<BoolValue>(Val: Val2.getProperty(Name: "is_null"));
800 if (IsNull1 == nullptr || IsNull2 == nullptr)
801 return;
802
803 if (IsNull1 == IsNull2)
804 JoinedVal.setProperty(Name: "is_null", Val&: *IsNull1);
805 else
806 JoinedVal.setProperty(Name: "is_null", Val&: JoinedEnv.makeTopBoolValue());
807 }
808
809 std::optional<WidenResult> widen(QualType Type, Value &Prev,
810 const Environment &PrevEnv, Value &Current,
811 Environment &CurrentEnv) override {
812 switch (compare(Type, Val1: Prev, Env1: PrevEnv, Val2: Current, Env2: CurrentEnv)) {
813 case ComparisonResult::Same:
814 return WidenResult{.V: &Current, .Effect: LatticeJoinEffect::Unchanged};
815 case ComparisonResult::Different: {
816 auto &CurPtr = cast<PointerValue>(Val&: Current);
817 auto &WidenedPtr =
818 CurrentEnv.create<PointerValue>(args&: CurPtr.getPointeeLoc());
819 WidenedPtr.setProperty(Name: "is_null", Val&: CurrentEnv.makeTopBoolValue());
820 return WidenResult{.V: &WidenedPtr, .Effect: LatticeJoinEffect::Changed};
821 }
822 case ComparisonResult::Unknown:
823 return std::nullopt;
824 }
825 llvm_unreachable("all cases in switch covered");
826 }
827};
828
829class WideningTest : public Test {
830protected:
831 template <typename Matcher>
832 void runDataflow(llvm::StringRef Code, Matcher Match) {
833 ASSERT_THAT_ERROR(
834 checkDataflow<NullPointerAnalysis>(
835 AnalysisInputs<NullPointerAnalysis>(
836 Code, ast_matchers::hasName("target"),
837 [](ASTContext &Context, Environment &Env) {
838 return NullPointerAnalysis(Context);
839 })
840 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
841 /*VerifyResults=*/[&Match](const llvm::StringMap<
842 DataflowAnalysisState<NoopLattice>>
843 &Results,
844 const AnalysisOutputs
845 &AO) { Match(Results, AO.ASTCtx); }),
846 llvm::Succeeded());
847 }
848};
849
850TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) {
851 std::string Code = R"(
852 void target(bool Cond) {
853 int *Foo = nullptr;
854 int i = 0;
855 /*[[p1]]*/
856 if (Cond) {
857 Foo = &i;
858 /*[[p2]]*/
859 }
860 (void)0;
861 /*[[p3]]*/
862 }
863 )";
864 runDataflow(
865 Code,
866 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
867 ASTContext &ASTCtx) {
868 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
869 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
870 const Environment &Env3 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p3");
871
872 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
873 ASSERT_THAT(FooDecl, NotNull());
874
875 auto GetFooValue = [FooDecl](const Environment &Env) {
876 return Env.getValue(D: *FooDecl);
877 };
878
879 EXPECT_EQ(GetFooValue(Env1)->getProperty("is_null"),
880 &Env1.getBoolLiteralValue(true));
881 EXPECT_EQ(GetFooValue(Env2)->getProperty("is_null"),
882 &Env2.getBoolLiteralValue(false));
883 EXPECT_TRUE(
884 isa<TopBoolValue>(GetFooValue(Env3)->getProperty("is_null")));
885 });
886}
887
888TEST_F(WideningTest, JoinDistinctValuesWithSameProperties) {
889 std::string Code = R"(
890 void target(bool Cond) {
891 int *Foo = nullptr;
892 int i1 = 0;
893 int i2 = 0;
894 /*[[p1]]*/
895 if (Cond) {
896 Foo = &i1;
897 /*[[p2]]*/
898 } else {
899 Foo = &i2;
900 /*[[p3]]*/
901 }
902 (void)0;
903 /*[[p4]]*/
904 }
905 )";
906 runDataflow(
907 Code,
908 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
909 ASTContext &ASTCtx) {
910 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
911 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
912 const Environment &Env3 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p3");
913 const Environment &Env4 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p4");
914
915 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
916 ASSERT_THAT(FooDecl, NotNull());
917
918 auto GetFooValue = [FooDecl](const Environment &Env) {
919 return Env.getValue(D: *FooDecl);
920 };
921
922 EXPECT_EQ(GetFooValue(Env1)->getProperty("is_null"),
923 &Env1.getBoolLiteralValue(true));
924 EXPECT_EQ(GetFooValue(Env2)->getProperty("is_null"),
925 &Env2.getBoolLiteralValue(false));
926 EXPECT_EQ(GetFooValue(Env3)->getProperty("is_null"),
927 &Env3.getBoolLiteralValue(false));
928 EXPECT_EQ(GetFooValue(Env4)->getProperty("is_null"),
929 &Env4.getBoolLiteralValue(false));
930 });
931}
932
933TEST_F(WideningTest, DistinctPointersToTheSameLocationAreEquivalent) {
934 std::string Code = R"(
935 void target(int Foo, bool Cond) {
936 int *Bar = &Foo;
937 while (Cond) {
938 Bar = &Foo;
939 }
940 (void)0;
941 // [[p]]
942 }
943 )";
944 runDataflow(
945 Code,
946 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
947 ASTContext &ASTCtx) {
948 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
949 const auto &FooLoc =
950 getLocForDecl<ScalarStorageLocation>(ASTCtx, Env, Name: "Foo");
951 const auto &BarVal = getValueForDecl<PointerValue>(ASTCtx, Env, Name: "Bar");
952 EXPECT_EQ(&BarVal.getPointeeLoc(), &FooLoc);
953 });
954}
955
956TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) {
957 std::string Code = R"(
958 void target(bool Cond) {
959 int *Foo;
960 int i1 = 0;
961 int i2 = 0;
962 Foo = &i1;
963 while (Cond) {
964 Foo = &i2;
965 }
966 (void)0;
967 /*[[p]]*/
968 }
969 )";
970 runDataflow(
971 Code,
972 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
973 ASTContext &ASTCtx) {
974 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
975 const auto &FooVal = getValueForDecl<Value>(ASTCtx, Env, Name: "Foo");
976 EXPECT_EQ(FooVal.getProperty("is_null"),
977 &Env.getBoolLiteralValue(false));
978 });
979}
980
981TEST_F(WideningTest, DistinctValuesWithDifferentPropertiesWidenedToTop) {
982 std::string Code = R"(
983 void target(bool Cond) {
984 int *Foo;
985 int i = 0;
986 Foo = nullptr;
987 while (Cond) {
988 Foo = &i;
989 }
990 (void)0;
991 /*[[p]]*/
992 }
993 )";
994 runDataflow(
995 Code,
996 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
997 ASTContext &ASTCtx) {
998 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
999 const auto &FooVal = getValueForDecl<Value>(ASTCtx, Env, Name: "Foo");
1000 ASSERT_THAT(FooVal.getProperty("is_null"), NotNull());
1001 EXPECT_TRUE(areEquivalentValues(*FooVal.getProperty("is_null"),
1002 Env.makeTopBoolValue()));
1003 });
1004}
1005
1006class FlowConditionTest : public Test {
1007protected:
1008 template <typename Matcher>
1009 void runDataflow(llvm::StringRef Code, Matcher Match) {
1010 ASSERT_THAT_ERROR(
1011 checkDataflow<NoopAnalysis>(
1012 AnalysisInputs<NoopAnalysis>(
1013 Code, ast_matchers::hasName("target"),
1014 [](ASTContext &Context, Environment &Env) {
1015 return NoopAnalysis(Context);
1016 })
1017 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
1018 /*VerifyResults=*/[&Match](const llvm::StringMap<
1019 DataflowAnalysisState<NoopLattice>>
1020 &Results,
1021 const AnalysisOutputs
1022 &AO) { Match(Results, AO.ASTCtx); }),
1023 llvm::Succeeded());
1024 }
1025};
1026
1027TEST_F(FlowConditionTest, IfStmtSingleVar) {
1028 std::string Code = R"(
1029 void target(bool Foo) {
1030 if (Foo) {
1031 (void)0;
1032 /*[[p1]]*/
1033 } else {
1034 (void)1;
1035 /*[[p2]]*/
1036 }
1037 }
1038 )";
1039 runDataflow(
1040 Code,
1041 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1042 ASTContext &ASTCtx) {
1043 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1044 ASSERT_THAT(FooDecl, NotNull());
1045
1046 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1047
1048 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1049 auto &FooVal1 = cast<BoolValue>(Val: Env1.getValue(D: *FooDecl))->formula();
1050 EXPECT_TRUE(Env1.proves(FooVal1));
1051
1052 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1053 auto &FooVal2 = cast<BoolValue>(Val: Env2.getValue(D: *FooDecl))->formula();
1054 EXPECT_FALSE(Env2.proves(FooVal2));
1055 });
1056}
1057
1058TEST_F(FlowConditionTest, IfStmtSingleNegatedVar) {
1059 std::string Code = R"(
1060 void target(bool Foo) {
1061 if (!Foo) {
1062 (void)0;
1063 /*[[p1]]*/
1064 } else {
1065 (void)1;
1066 /*[[p2]]*/
1067 }
1068 }
1069 )";
1070 runDataflow(
1071 Code,
1072 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1073 ASTContext &ASTCtx) {
1074 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1075 ASSERT_THAT(FooDecl, NotNull());
1076
1077 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1078
1079 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1080 auto &FooVal1 = cast<BoolValue>(Val: Env1.getValue(D: *FooDecl))->formula();
1081 EXPECT_FALSE(Env1.proves(FooVal1));
1082
1083 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1084 auto &FooVal2 = cast<BoolValue>(Val: Env2.getValue(D: *FooDecl))->formula();
1085 EXPECT_TRUE(Env2.proves(FooVal2));
1086 });
1087}
1088
1089TEST_F(FlowConditionTest, WhileStmt) {
1090 std::string Code = R"(
1091 void target(bool Foo) {
1092 while (Foo) {
1093 (void)0;
1094 /*[[p]]*/
1095 }
1096 }
1097 )";
1098 runDataflow(
1099 Code,
1100 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1101 ASTContext &ASTCtx) {
1102 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1103 ASSERT_THAT(FooDecl, NotNull());
1104
1105 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1106 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
1107
1108 auto &FooVal = cast<BoolValue>(Val: Env.getValue(D: *FooDecl))->formula();
1109 EXPECT_TRUE(Env.proves(FooVal));
1110 });
1111}
1112
1113TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
1114 std::string Code = R"(
1115 void target(bool Foo) {
1116 // This test checks whether the analysis preserves the connection between
1117 // the value of `Foo` and the assignment expression, despite widening.
1118 // The equality operator generates a fresh boolean variable on each
1119 // interpretation, which forces use of widening.
1120 while ((Foo = (3 == 4))) {
1121 (void)0;
1122 /*[[p]]*/
1123 }
1124 }
1125 )";
1126 runDataflow(
1127 Code,
1128 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1129 ASTContext &ASTCtx) {
1130 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
1131 auto &FooVal = getValueForDecl<BoolValue>(ASTCtx, Env, Name: "Foo").formula();
1132 EXPECT_TRUE(Env.proves(FooVal));
1133 });
1134}
1135
1136TEST_F(FlowConditionTest, Conjunction) {
1137 std::string Code = R"(
1138 void target(bool Foo, bool Bar) {
1139 if (Foo && Bar) {
1140 (void)0;
1141 /*[[p1]]*/
1142 } else {
1143 (void)1;
1144 /*[[p2]]*/
1145 }
1146 }
1147 )";
1148 runDataflow(Code, Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
1149 &Results,
1150 ASTContext &ASTCtx) {
1151 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1152 ASSERT_THAT(FooDecl, NotNull());
1153
1154 const ValueDecl *BarDecl = findValueDecl(ASTCtx, Name: "Bar");
1155 ASSERT_THAT(BarDecl, NotNull());
1156
1157 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1158
1159 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1160 auto &FooVal1 = cast<BoolValue>(Val: Env1.getValue(D: *FooDecl))->formula();
1161 auto &BarVal1 = cast<BoolValue>(Val: Env1.getValue(D: *BarDecl))->formula();
1162 EXPECT_TRUE(Env1.proves(FooVal1));
1163 EXPECT_TRUE(Env1.proves(BarVal1));
1164
1165 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1166 auto &FooVal2 = cast<BoolValue>(Val: Env2.getValue(D: *FooDecl))->formula();
1167 auto &BarVal2 = cast<BoolValue>(Val: Env2.getValue(D: *BarDecl))->formula();
1168 EXPECT_FALSE(Env2.proves(FooVal2));
1169 EXPECT_FALSE(Env2.proves(BarVal2));
1170 });
1171}
1172
1173TEST_F(FlowConditionTest, Disjunction) {
1174 std::string Code = R"(
1175 void target(bool Foo, bool Bar) {
1176 if (Foo || Bar) {
1177 (void)0;
1178 /*[[p1]]*/
1179 } else {
1180 (void)1;
1181 /*[[p2]]*/
1182 }
1183 }
1184 )";
1185 runDataflow(Code, Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
1186 &Results,
1187 ASTContext &ASTCtx) {
1188 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1189 ASSERT_THAT(FooDecl, NotNull());
1190
1191 const ValueDecl *BarDecl = findValueDecl(ASTCtx, Name: "Bar");
1192 ASSERT_THAT(BarDecl, NotNull());
1193
1194 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1195
1196 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1197 auto &FooVal1 = cast<BoolValue>(Val: Env1.getValue(D: *FooDecl))->formula();
1198 auto &BarVal1 = cast<BoolValue>(Val: Env1.getValue(D: *BarDecl))->formula();
1199 EXPECT_FALSE(Env1.proves(FooVal1));
1200 EXPECT_FALSE(Env1.proves(BarVal1));
1201
1202 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1203 auto &FooVal2 = cast<BoolValue>(Val: Env2.getValue(D: *FooDecl))->formula();
1204 auto &BarVal2 = cast<BoolValue>(Val: Env2.getValue(D: *BarDecl))->formula();
1205 EXPECT_FALSE(Env2.proves(FooVal2));
1206 EXPECT_FALSE(Env2.proves(BarVal2));
1207 });
1208}
1209
1210TEST_F(FlowConditionTest, NegatedConjunction) {
1211 std::string Code = R"(
1212 void target(bool Foo, bool Bar) {
1213 if (!(Foo && Bar)) {
1214 (void)0;
1215 /*[[p1]]*/
1216 } else {
1217 (void)1;
1218 /*[[p2]]*/
1219 }
1220 }
1221 )";
1222 runDataflow(Code, Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
1223 &Results,
1224 ASTContext &ASTCtx) {
1225 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1226 ASSERT_THAT(FooDecl, NotNull());
1227
1228 const ValueDecl *BarDecl = findValueDecl(ASTCtx, Name: "Bar");
1229 ASSERT_THAT(BarDecl, NotNull());
1230
1231 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1232
1233 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1234 auto &FooVal1 = cast<BoolValue>(Val: Env1.getValue(D: *FooDecl))->formula();
1235 auto &BarVal1 = cast<BoolValue>(Val: Env1.getValue(D: *BarDecl))->formula();
1236 EXPECT_FALSE(Env1.proves(FooVal1));
1237 EXPECT_FALSE(Env1.proves(BarVal1));
1238
1239 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1240 auto &FooVal2 = cast<BoolValue>(Val: Env2.getValue(D: *FooDecl))->formula();
1241 auto &BarVal2 = cast<BoolValue>(Val: Env2.getValue(D: *BarDecl))->formula();
1242 EXPECT_TRUE(Env2.proves(FooVal2));
1243 EXPECT_TRUE(Env2.proves(BarVal2));
1244 });
1245}
1246
1247TEST_F(FlowConditionTest, DeMorgan) {
1248 std::string Code = R"(
1249 void target(bool Foo, bool Bar) {
1250 if (!(!Foo || !Bar)) {
1251 (void)0;
1252 /*[[p1]]*/
1253 } else {
1254 (void)1;
1255 /*[[p2]]*/
1256 }
1257 }
1258 )";
1259 runDataflow(Code, Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
1260 &Results,
1261 ASTContext &ASTCtx) {
1262 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1263 ASSERT_THAT(FooDecl, NotNull());
1264
1265 const ValueDecl *BarDecl = findValueDecl(ASTCtx, Name: "Bar");
1266 ASSERT_THAT(BarDecl, NotNull());
1267
1268 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1269
1270 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1271 auto &FooVal1 = cast<BoolValue>(Val: Env1.getValue(D: *FooDecl))->formula();
1272 auto &BarVal1 = cast<BoolValue>(Val: Env1.getValue(D: *BarDecl))->formula();
1273 EXPECT_TRUE(Env1.proves(FooVal1));
1274 EXPECT_TRUE(Env1.proves(BarVal1));
1275
1276 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1277 auto &FooVal2 = cast<BoolValue>(Val: Env2.getValue(D: *FooDecl))->formula();
1278 auto &BarVal2 = cast<BoolValue>(Val: Env2.getValue(D: *BarDecl))->formula();
1279 EXPECT_FALSE(Env2.proves(FooVal2));
1280 EXPECT_FALSE(Env2.proves(BarVal2));
1281 });
1282}
1283
1284TEST_F(FlowConditionTest, Join) {
1285 std::string Code = R"(
1286 void target(bool Foo, bool Bar) {
1287 if (Bar) {
1288 if (!Foo)
1289 return;
1290 } else {
1291 if (!Foo)
1292 return;
1293 }
1294 (void)0;
1295 /*[[p]]*/
1296 }
1297 )";
1298 runDataflow(
1299 Code,
1300 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1301 ASTContext &ASTCtx) {
1302 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1303
1304 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1305 ASSERT_THAT(FooDecl, NotNull());
1306
1307 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
1308 auto &FooVal = cast<BoolValue>(Val: Env.getValue(D: *FooDecl))->formula();
1309 EXPECT_TRUE(Env.proves(FooVal));
1310 });
1311}
1312
1313// Verifies that flow conditions are properly constructed even when the
1314// condition is not meaningfully interpreted.
1315//
1316// Note: currently, arbitrary function calls are uninterpreted, so the test
1317// exercises this case. If and when we change that, this test will not add to
1318// coverage (although it may still test a valuable case).
1319TEST_F(FlowConditionTest, OpaqueFlowConditionJoinsToOpaqueBool) {
1320 std::string Code = R"(
1321 bool foo();
1322
1323 void target() {
1324 bool Bar = true;
1325 if (foo())
1326 Bar = false;
1327 (void)0;
1328 /*[[p]]*/
1329 }
1330 )";
1331 runDataflow(
1332 Code,
1333 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1334 ASTContext &ASTCtx) {
1335 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1336 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
1337
1338 const ValueDecl *BarDecl = findValueDecl(ASTCtx, Name: "Bar");
1339 ASSERT_THAT(BarDecl, NotNull());
1340
1341 auto &BarVal = cast<BoolValue>(Val: Env.getValue(D: *BarDecl))->formula();
1342
1343 EXPECT_FALSE(Env.proves(BarVal));
1344 });
1345}
1346
1347// Verifies that flow conditions are properly constructed even when the
1348// condition is not meaningfully interpreted.
1349//
1350// Note: currently, fields with recursive type calls are uninterpreted (beneath
1351// the first instance), so the test exercises this case. If and when we change
1352// that, this test will not add to coverage (although it may still test a
1353// valuable case).
1354TEST_F(FlowConditionTest, OpaqueFieldFlowConditionJoinsToOpaqueBool) {
1355 std::string Code = R"(
1356 struct Rec {
1357 Rec* Next;
1358 };
1359
1360 struct Foo {
1361 Rec* X;
1362 };
1363
1364 void target(Foo F) {
1365 bool Bar = true;
1366 if (F.X->Next)
1367 Bar = false;
1368 (void)0;
1369 /*[[p]]*/
1370 }
1371 )";
1372 runDataflow(
1373 Code,
1374 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1375 ASTContext &ASTCtx) {
1376 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1377 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
1378
1379 const ValueDecl *BarDecl = findValueDecl(ASTCtx, Name: "Bar");
1380 ASSERT_THAT(BarDecl, NotNull());
1381
1382 auto &BarVal = cast<BoolValue>(Val: Env.getValue(D: *BarDecl))->formula();
1383
1384 EXPECT_FALSE(Env.proves(BarVal));
1385 });
1386}
1387
1388// Verifies that flow conditions are properly constructed even when the
1389// condition is not meaningfully interpreted. Adds to above by nesting the
1390// interestnig case inside a normal branch. This protects against degenerate
1391// solutions which only test for empty flow conditions, for example.
1392TEST_F(FlowConditionTest, OpaqueFlowConditionInsideBranchJoinsToOpaqueBool) {
1393 std::string Code = R"(
1394 bool foo();
1395
1396 void target(bool Cond) {
1397 bool Bar = true;
1398 if (Cond) {
1399 if (foo())
1400 Bar = false;
1401 (void)0;
1402 /*[[p]]*/
1403 }
1404 }
1405 )";
1406 runDataflow(
1407 Code,
1408 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1409 ASTContext &ASTCtx) {
1410 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1411 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
1412
1413 const ValueDecl *BarDecl = findValueDecl(ASTCtx, Name: "Bar");
1414 ASSERT_THAT(BarDecl, NotNull());
1415
1416 auto &BarVal = cast<BoolValue>(Val: Env.getValue(D: *BarDecl))->formula();
1417
1418 EXPECT_FALSE(Env.proves(BarVal));
1419 });
1420}
1421
1422TEST_F(FlowConditionTest, PointerToBoolImplicitCast) {
1423 std::string Code = R"(
1424 void target(int *Ptr) {
1425 bool Foo = false;
1426 if (Ptr) {
1427 Foo = true;
1428 /*[[p1]]*/
1429 }
1430
1431 (void)0;
1432 /*[[p2]]*/
1433 }
1434 )";
1435 runDataflow(
1436 Code,
1437 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1438 ASTContext &ASTCtx) {
1439 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1440
1441 const ValueDecl *FooDecl = findValueDecl(ASTCtx, Name: "Foo");
1442 ASSERT_THAT(FooDecl, NotNull());
1443
1444 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1445 auto &FooVal1 = cast<BoolValue>(Val: Env1.getValue(D: *FooDecl))->formula();
1446 EXPECT_TRUE(Env1.proves(FooVal1));
1447
1448 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1449 auto &FooVal2 = cast<BoolValue>(Val: Env2.getValue(D: *FooDecl))->formula();
1450 EXPECT_FALSE(Env2.proves(FooVal2));
1451 });
1452}
1453
1454class TopAnalysis final : public DataflowAnalysis<TopAnalysis, NoopLattice> {
1455public:
1456 explicit TopAnalysis(ASTContext &Context)
1457 : DataflowAnalysis<TopAnalysis, NoopLattice>(Context) {}
1458
1459 static NoopLattice initialElement() { return {}; }
1460
1461 void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
1462 auto CS = Elt.getAs<CFGStmt>();
1463 if (!CS)
1464 return;
1465 const Stmt *S = CS->getStmt();
1466 SmallVector<BoundNodes, 1> Matches =
1467 match(Matcher: callExpr(callee(InnerMatcher: functionDecl(hasName(Name: "makeTop")))).bind(ID: "top"),
1468 Node: *S, Context&: getASTContext());
1469 if (const auto *E = selectFirst<CallExpr>(BoundTo: "top", Results: Matches)) {
1470 Env.setValue(*E, Env.makeTopBoolValue());
1471 }
1472 }
1473
1474 ComparisonResult compare(QualType Type, const Value &Val1,
1475 const Environment &Env1, const Value &Val2,
1476 const Environment &Env2) override {
1477 // Changes to a sound approximation, which allows us to test whether we can
1478 // (soundly) converge for some loops.
1479 return ComparisonResult::Unknown;
1480 }
1481};
1482
1483class TopTest : public Test {
1484protected:
1485 template <typename Matcher>
1486 void runDataflow(llvm::StringRef Code, Matcher VerifyResults) {
1487 ASSERT_THAT_ERROR(
1488 checkDataflow<TopAnalysis>(
1489 AnalysisInputs<TopAnalysis>(
1490 Code, ast_matchers::hasName("target"),
1491 [](ASTContext &Context, Environment &Env) {
1492 return TopAnalysis(Context);
1493 })
1494 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
1495 VerifyResults),
1496 llvm::Succeeded());
1497 }
1498};
1499
1500// Tests that when Top is unused it remains Top.
1501TEST_F(TopTest, UnusedTopInitializer) {
1502 std::string Code = R"(
1503 bool makeTop();
1504
1505 void target() {
1506 bool Foo = makeTop();
1507 /*[[p1]]*/
1508 (void)0;
1509 /*[[p2]]*/
1510 }
1511 )";
1512 runDataflow(
1513 Code,
1514 VerifyResults: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1515 const AnalysisOutputs &AO) {
1516 ASSERT_THAT(Results.keys(),
1517 UnorderedElementsAre("p1", "p2"));
1518 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1519 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1520
1521 const ValueDecl *FooDecl = findValueDecl(ASTCtx&: AO.ASTCtx, Name: "Foo");
1522 ASSERT_THAT(FooDecl, NotNull());
1523
1524 auto GetFooValue = [FooDecl](const Environment &Env) {
1525 return Env.getValue(D: *FooDecl);
1526 };
1527
1528 Value *FooVal1 = GetFooValue(Env1);
1529 ASSERT_THAT(FooVal1, NotNull());
1530 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1531 << debugString(Kind: FooVal1->getKind());
1532
1533 Value *FooVal2 = GetFooValue(Env2);
1534 ASSERT_THAT(FooVal2, NotNull());
1535 EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1536 << debugString(Kind: FooVal2->getKind());
1537
1538 EXPECT_EQ(FooVal1, FooVal2);
1539 });
1540}
1541
1542// Tests that when Top is unused it remains Top. Like above, but uses the
1543// assignment form rather than initialization, which uses Top as an lvalue that
1544// is *not* in an rvalue position.
1545TEST_F(TopTest, UnusedTopAssignment) {
1546 std::string Code = R"(
1547 bool makeTop();
1548
1549 void target() {
1550 bool Foo;
1551 Foo = makeTop();
1552 /*[[p1]]*/
1553 (void)0;
1554 /*[[p2]]*/
1555 }
1556 )";
1557 runDataflow(
1558 Code,
1559 VerifyResults: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1560 const AnalysisOutputs &AO) {
1561 ASSERT_THAT(Results.keys(),
1562 UnorderedElementsAre("p1", "p2"));
1563 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1564 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1565
1566 const ValueDecl *FooDecl = findValueDecl(ASTCtx&: AO.ASTCtx, Name: "Foo");
1567 ASSERT_THAT(FooDecl, NotNull());
1568
1569 auto GetFooValue = [FooDecl](const Environment &Env) {
1570 return Env.getValue(D: *FooDecl);
1571 };
1572
1573 Value *FooVal1 = GetFooValue(Env1);
1574 ASSERT_THAT(FooVal1, NotNull());
1575 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1576 << debugString(Kind: FooVal1->getKind());
1577
1578 Value *FooVal2 = GetFooValue(Env2);
1579 ASSERT_THAT(FooVal2, NotNull());
1580 EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1581 << debugString(Kind: FooVal2->getKind());
1582
1583 EXPECT_EQ(FooVal1, FooVal2);
1584 });
1585}
1586
1587TEST_F(TopTest, UnusedTopJoinsToTop) {
1588 std::string Code = R"(
1589 bool makeTop();
1590
1591 void target(bool Cond, bool F) {
1592 bool Foo = makeTop();
1593 // Force a new CFG block.
1594 if (F) return;
1595 (void)0;
1596 /*[[p1]]*/
1597
1598 bool Zab1;
1599 bool Zab2;
1600 if (Cond) {
1601 Zab1 = true;
1602 } else {
1603 Zab2 = true;
1604 }
1605 (void)0;
1606 /*[[p2]]*/
1607 }
1608 )";
1609 runDataflow(
1610 Code,
1611 VerifyResults: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1612 const AnalysisOutputs &AO) {
1613 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1614 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1615 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1616
1617 const ValueDecl *FooDecl = findValueDecl(ASTCtx&: AO.ASTCtx, Name: "Foo");
1618 ASSERT_THAT(FooDecl, NotNull());
1619
1620 auto GetFooValue = [FooDecl](const Environment &Env) {
1621 return Env.getValue(D: *FooDecl);
1622 };
1623
1624 Value *FooVal1 = GetFooValue(Env1);
1625 ASSERT_THAT(FooVal1, NotNull());
1626 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1627 << debugString(Kind: FooVal1->getKind());
1628
1629 Value *FooVal2 = GetFooValue(Env2);
1630 ASSERT_THAT(FooVal2, NotNull());
1631 EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1632 << debugString(Kind: FooVal2->getKind());
1633 });
1634}
1635
1636TEST_F(TopTest, TopUsedBeforeBranchJoinsToSameAtomicBool) {
1637 std::string Code = R"(
1638 bool makeTop();
1639
1640 void target(bool Cond, bool F) {
1641 bool Foo = makeTop();
1642 /*[[p0]]*/
1643
1644 // Use `Top`.
1645 bool Bar = Foo;
1646 // Force a new CFG block.
1647 if (F) return;
1648 (void)0;
1649 /*[[p1]]*/
1650
1651 bool Zab1;
1652 bool Zab2;
1653 if (Cond) {
1654 Zab1 = true;
1655 } else {
1656 Zab2 = true;
1657 }
1658 (void)0;
1659 /*[[p2]]*/
1660 }
1661 )";
1662 runDataflow(
1663 Code,
1664 VerifyResults: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1665 const AnalysisOutputs &AO) {
1666 ASSERT_THAT(Results.keys(),
1667 UnorderedElementsAre("p0", "p1", "p2"));
1668 const Environment &Env0 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p0");
1669 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1670 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1671
1672 const ValueDecl *FooDecl = findValueDecl(ASTCtx&: AO.ASTCtx, Name: "Foo");
1673 ASSERT_THAT(FooDecl, NotNull());
1674
1675 auto GetFooValue = [FooDecl](const Environment &Env) {
1676 return Env.getValue(D: *FooDecl);
1677 };
1678
1679 Value *FooVal0 = GetFooValue(Env0);
1680 ASSERT_THAT(FooVal0, NotNull());
1681 EXPECT_TRUE(isa<TopBoolValue>(FooVal0))
1682 << debugString(Kind: FooVal0->getKind());
1683
1684 Value *FooVal1 = GetFooValue(Env1);
1685 ASSERT_THAT(FooVal1, NotNull());
1686 EXPECT_TRUE(isa<AtomicBoolValue>(FooVal1))
1687 << debugString(Kind: FooVal1->getKind());
1688
1689 Value *FooVal2 = GetFooValue(Env2);
1690 ASSERT_THAT(FooVal2, NotNull());
1691 EXPECT_TRUE(isa<AtomicBoolValue>(FooVal2))
1692 << debugString(Kind: FooVal2->getKind());
1693
1694 EXPECT_EQ(FooVal2, FooVal1);
1695 });
1696}
1697
1698TEST_F(TopTest, TopUsedInBothBranchesJoinsToAtomic) {
1699 std::string Code = R"(
1700 bool makeTop();
1701
1702 void target(bool Cond, bool F) {
1703 bool Foo = makeTop();
1704 // Force a new CFG block.
1705 if (F) return;
1706 (void)0;
1707 /*[[p1]]*/
1708
1709 bool Zab1;
1710 bool Zab2;
1711 if (Cond) {
1712 Zab1 = Foo;
1713 } else {
1714 Zab2 = Foo;
1715 }
1716 (void)0;
1717 /*[[p2]]*/
1718 }
1719 )";
1720 runDataflow(
1721 Code,
1722 VerifyResults: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1723 const AnalysisOutputs &AO) {
1724 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1725 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1726 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1727
1728 const ValueDecl *FooDecl = findValueDecl(ASTCtx&: AO.ASTCtx, Name: "Foo");
1729 ASSERT_THAT(FooDecl, NotNull());
1730
1731 auto GetFooValue = [FooDecl](const Environment &Env) {
1732 return Env.getValue(D: *FooDecl);
1733 };
1734
1735 Value *FooVal1 = GetFooValue(Env1);
1736 ASSERT_THAT(FooVal1, NotNull());
1737 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1738 << debugString(Kind: FooVal1->getKind());
1739
1740 Value *FooVal2 = GetFooValue(Env2);
1741 ASSERT_THAT(FooVal2, NotNull());
1742 EXPECT_TRUE(isa<AtomicBoolValue>(FooVal2))
1743 << debugString(Kind: FooVal2->getKind());
1744 });
1745}
1746
1747TEST_F(TopTest, TopUsedInBothBranchesWithoutPrecisionLoss) {
1748 std::string Code = R"(
1749 bool makeTop();
1750
1751 void target(bool Cond, bool F) {
1752 bool Foo = makeTop();
1753 // Force a new CFG block.
1754 if (F) return;
1755 (void)0;
1756
1757 bool Bar;
1758 if (Cond) {
1759 Bar = Foo;
1760 } else {
1761 Bar = Foo;
1762 }
1763 (void)0;
1764 /*[[p]]*/
1765 }
1766 )";
1767 runDataflow(
1768 Code,
1769 VerifyResults: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1770 const AnalysisOutputs &AO) {
1771 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
1772 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
1773
1774 const ValueDecl *FooDecl = findValueDecl(ASTCtx&: AO.ASTCtx, Name: "Foo");
1775 ASSERT_THAT(FooDecl, NotNull());
1776
1777 const ValueDecl *BarDecl = findValueDecl(ASTCtx&: AO.ASTCtx, Name: "Bar");
1778 ASSERT_THAT(BarDecl, NotNull());
1779
1780 auto *FooVal = dyn_cast_or_null<BoolValue>(Val: Env.getValue(D: *FooDecl));
1781 ASSERT_THAT(FooVal, NotNull());
1782
1783 auto *BarVal = dyn_cast_or_null<BoolValue>(Val: Env.getValue(D: *BarDecl));
1784 ASSERT_THAT(BarVal, NotNull());
1785
1786 EXPECT_TRUE(Env.proves(
1787 Env.arena().makeEquals(FooVal->formula(), BarVal->formula())));
1788 });
1789}
1790
1791TEST_F(TopTest, TopUnusedBeforeLoopHeadJoinsToTop) {
1792 std::string Code = R"(
1793 bool makeTop();
1794
1795 void target(bool Cond, bool F) {
1796 bool Foo = makeTop();
1797 // Force a new CFG block.
1798 if (F) return;
1799 (void)0;
1800 /*[[p1]]*/
1801
1802 while (Cond) {
1803 // Use `Foo`.
1804 bool Zab = Foo;
1805 Zab = false;
1806 Foo = makeTop();
1807 }
1808 (void)0;
1809 /*[[p2]]*/
1810 }
1811 )";
1812 runDataflow(
1813 Code,
1814 VerifyResults: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1815 const AnalysisOutputs &AO) {
1816 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
1817 const Environment &Env1 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p1");
1818 const Environment &Env2 = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p2");
1819
1820 const ValueDecl *FooDecl = findValueDecl(ASTCtx&: AO.ASTCtx, Name: "Foo");
1821 ASSERT_THAT(FooDecl, NotNull());
1822
1823 auto GetFooValue = [FooDecl](const Environment &Env) {
1824 return Env.getValue(D: *FooDecl);
1825 };
1826
1827 Value *FooVal1 = GetFooValue(Env1);
1828 ASSERT_THAT(FooVal1, NotNull());
1829 EXPECT_TRUE(isa<TopBoolValue>(FooVal1))
1830 << debugString(Kind: FooVal1->getKind());
1831
1832 Value *FooVal2 = GetFooValue(Env2);
1833 ASSERT_THAT(FooVal2, NotNull());
1834 EXPECT_TRUE(isa<TopBoolValue>(FooVal2))
1835 << debugString(Kind: FooVal2->getKind());
1836
1837 });
1838}
1839
1840TEST_F(TopTest, ForRangeStmtConverges) {
1841 std::string Code = R"(
1842 void target(bool Foo) {
1843 int Ints[10];
1844 bool B = false;
1845 for (int I : Ints)
1846 B = true;
1847 }
1848 )";
1849 runDataflow(Code,
1850 VerifyResults: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &,
1851 const AnalysisOutputs &) {
1852 // No additional expectations. We're only checking that the
1853 // analysis converged.
1854 });
1855}
1856} // namespace
1857

source code of clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp