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

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

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