1 //===- unittests/Analysis/FlowSensitive/DeterminismTest.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/Analysis/FlowSensitive/AdornedCFG.h"
12 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
13 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
14 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
15 #include "clang/Analysis/FlowSensitive/Formula.h"
16 #include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
17 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
18 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
19 #include "clang/Basic/LLVM.h"
20 #include "clang/Testing/TestAST.h"
21 #include "llvm/Support/Error.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include "gtest/gtest.h"
24 #include <memory>
25 #include <string>
26
27 namespace clang::dataflow {
28
29 // Run a no-op analysis, and return a textual representation of the
30 // flow-condition at function exit.
analyzeAndPrintExitCondition(llvm::StringRef Code)31 std::string analyzeAndPrintExitCondition(llvm::StringRef Code) {
32 DataflowAnalysisContext DACtx(std::make_unique<WatchedLiteralsSolver>());
33 TestInputs Inputs(Code);
34 Inputs.Language = TestLanguage::Lang_CXX17;
35 clang::TestAST AST(Inputs);
36 const auto *Target =
37 cast<FunctionDecl>(test::findValueDecl(AST.context(), "target"));
38 Environment InitEnv(DACtx, *Target);
39 auto ACFG = cantFail(AdornedCFG::build(*Target));
40
41 NoopAnalysis Analysis(AST.context(), DataflowAnalysisOptions{});
42
43 auto Result = runDataflowAnalysis(ACFG, Analysis, InitEnv);
44 EXPECT_FALSE(!Result) << Result.takeError();
45
46 Atom FinalFC = (*Result)[ACFG.getCFG().getExit().getBlockID()]
47 ->Env.getFlowConditionToken();
48 std::string Textual;
49 llvm::raw_string_ostream OS(Textual);
50 DACtx.dumpFlowCondition(FinalFC, OS);
51 return Textual;
52 }
53
TEST(DeterminismTest,NestedSwitch)54 TEST(DeterminismTest, NestedSwitch) {
55 // Example extracted from real-world code that had wildly nondeterministic
56 // analysis times.
57 // Its flow condition depends on the order we join predecessor blocks.
58 const char *Code = R"cpp(
59 struct Tree;
60 struct Rep {
61 Tree *tree();
62 int length;
63 };
64 struct Tree {
65 int height();
66 Rep *edge(int);
67 int length;
68 };
69 struct RetVal {};
70 int getInt();
71 bool maybe();
72
73 RetVal make(int size);
74 inline RetVal target(int size, Tree& self) {
75 Tree* tree = &self;
76 const int height = self.height();
77 Tree* n1 = tree;
78 Tree* n2 = tree;
79 switch (height) {
80 case 3:
81 tree = tree->edge(0)->tree();
82 if (maybe()) return {};
83 n2 = tree;
84 case 2:
85 tree = tree->edge(0)->tree();
86 n1 = tree;
87 if (maybe()) return {};
88 case 1:
89 tree = tree->edge(0)->tree();
90 if (maybe()) return {};
91 case 0:
92 Rep* edge = tree->edge(0);
93 if (maybe()) return {};
94 int avail = getInt();
95 if (avail == 0) return {};
96 int delta = getInt();
97 RetVal span = {};
98 edge->length += delta;
99 switch (height) {
100 case 3:
101 n1->length += delta;
102 case 2:
103 n1->length += delta;
104 case 1:
105 n1->length += delta;
106 case 0:
107 n1->length += delta;
108 return span;
109 }
110 break;
111 }
112 return make(size);
113 }
114 )cpp";
115
116 std::string Cond = analyzeAndPrintExitCondition(Code);
117 for (unsigned I = 0; I < 10; ++I)
118 EXPECT_EQ(Cond, analyzeAndPrintExitCondition(Code));
119 }
120
TEST(DeterminismTest,ValueMergeOrder)121 TEST(DeterminismTest, ValueMergeOrder) {
122 // Artificial example whose final flow condition variable numbering depends
123 // on the order in which we merge a, b, and c.
124 const char *Code = R"cpp(
125 bool target(bool a, bool b, bool c) {
126 if (a)
127 b = c;
128 else
129 c = b;
130 return a && b && c;
131 }
132 )cpp";
133
134 std::string Cond = analyzeAndPrintExitCondition(Code);
135 for (unsigned I = 0; I < 10; ++I)
136 EXPECT_EQ(Cond, analyzeAndPrintExitCondition(Code));
137 }
138
139 } // namespace clang::dataflow
140