1 //===- unittests/Analysis/FlowSensitive/SingleVarConstantPropagation.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 // This file defines a simplistic version of Constant Propagation as an example
10 // of a forward, monotonic dataflow analysis. The analysis only tracks one
11 // variable at a time -- the one with the most recent declaration encountered.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "TestingSupport.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/Decl.h"
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/Stmt.h"
20 #include "clang/ASTMatchers/ASTMatchFinder.h"
21 #include "clang/ASTMatchers/ASTMatchers.h"
22 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
23 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
24 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
25 #include "clang/Tooling/Tooling.h"
26 #include "llvm/ADT/None.h"
27 #include "llvm/ADT/Optional.h"
28 #include "llvm/ADT/StringRef.h"
29 #include "llvm/ADT/Twine.h"
30 #include "llvm/Support/Error.h"
31 #include "llvm/Testing/Support/Annotations.h"
32 #include "llvm/Testing/Support/Error.h"
33 #include "gmock/gmock.h"
34 #include "gtest/gtest.h"
35 #include <cstdint>
36 #include <memory>
37 #include <ostream>
38 #include <string>
39 #include <utility>
40
41 namespace clang {
42 namespace dataflow {
43 namespace {
44 using namespace ast_matchers;
45
46 // A semi-lattice for dataflow analysis that tracks the value of a single
47 // integer variable. If it can be identified with a single (constant) value,
48 // then that value is stored.
49 struct ConstantPropagationLattice {
50 // A null `Var` represents "top": either more than one value is possible or
51 // more than one variable was encountered. Otherwise, `Data` indicates that
52 // `Var` has the given `Value` at the program point with which this lattice
53 // element is associated, for all paths through the program.
54 struct VarValue {
55 const VarDecl *Var;
56 int64_t Value;
57
operator ==clang::dataflow::__anon41be10130111::ConstantPropagationLattice58 friend bool operator==(VarValue Lhs, VarValue Rhs) {
59 return Lhs.Var == Rhs.Var && Lhs.Value == Rhs.Value;
60 }
61 };
62 // `None` is "bottom".
63 llvm::Optional<VarValue> Data;
64
bottomclang::dataflow::__anon41be10130111::ConstantPropagationLattice65 static constexpr ConstantPropagationLattice bottom() { return {llvm::None}; }
topclang::dataflow::__anon41be10130111::ConstantPropagationLattice66 static constexpr ConstantPropagationLattice top() {
67 return {VarValue{nullptr, 0}};
68 }
69
operator ==(const ConstantPropagationLattice & Lhs,const ConstantPropagationLattice & Rhs)70 friend bool operator==(const ConstantPropagationLattice &Lhs,
71 const ConstantPropagationLattice &Rhs) {
72 return Lhs.Data == Rhs.Data;
73 }
74
joinclang::dataflow::__anon41be10130111::ConstantPropagationLattice75 LatticeJoinEffect join(const ConstantPropagationLattice &Other) {
76 if (*this == Other || Other == bottom() || *this == top())
77 return LatticeJoinEffect::Unchanged;
78
79 if (*this == bottom()) {
80 *this = Other;
81 return LatticeJoinEffect::Changed;
82 }
83
84 *this = top();
85 return LatticeJoinEffect::Changed;
86 }
87 };
88
operator <<(std::ostream & OS,const ConstantPropagationLattice & L)89 std::ostream &operator<<(std::ostream &OS,
90 const ConstantPropagationLattice &L) {
91 if (L == L.bottom())
92 return OS << "None";
93 if (L == L.top())
94 return OS << "Any";
95 return OS << L.Data->Var->getName().str() << " = " << L.Data->Value;
96 }
97
98 } // namespace
99
100 static constexpr char kVar[] = "var";
101 static constexpr char kInit[] = "init";
102 static constexpr char kJustAssignment[] = "just-assignment";
103 static constexpr char kAssignment[] = "assignment";
104 static constexpr char kRHS[] = "rhs";
105
refToVar()106 static auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }
107
108 namespace {
109 // N.B. This analysis is deliberately simplistic, leaving out many important
110 // details needed for a real analysis in production. Most notably, the transfer
111 // function does not account for the variable's address possibly escaping, which
112 // would invalidate the analysis.
113 class ConstantPropagationAnalysis
114 : public DataflowAnalysis<ConstantPropagationAnalysis,
115 ConstantPropagationLattice> {
116 public:
ConstantPropagationAnalysis(ASTContext & Context)117 explicit ConstantPropagationAnalysis(ASTContext &Context)
118 : DataflowAnalysis<ConstantPropagationAnalysis,
119 ConstantPropagationLattice>(Context) {}
120
initialElement()121 static ConstantPropagationLattice initialElement() {
122 return ConstantPropagationLattice::bottom();
123 }
124
transfer(const Stmt * S,ConstantPropagationLattice & Element,Environment & Env)125 void transfer(const Stmt *S, ConstantPropagationLattice &Element,
126 Environment &Env) {
127 auto matcher = stmt(
128 anyOf(declStmt(hasSingleDecl(varDecl(hasType(isInteger()),
129 hasInitializer(expr().bind(kInit)))
130 .bind(kVar))),
131 binaryOperator(hasOperatorName("="), hasLHS(refToVar()),
132 hasRHS(expr().bind(kRHS)))
133 .bind(kJustAssignment),
134 binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))
135 .bind(kAssignment)));
136
137 ASTContext &Context = getASTContext();
138 auto Results = match(matcher, *S, Context);
139 if (Results.empty())
140 return;
141 const BoundNodes &Nodes = Results[0];
142
143 const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
144 assert(Var != nullptr);
145
146 if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
147 Expr::EvalResult R;
148 Element =
149 (E->EvaluateAsInt(R, Context) && R.Val.isInt())
150 ? ConstantPropagationLattice{{{Var,
151 R.Val.getInt().getExtValue()}}}
152 : ConstantPropagationLattice::top();
153 } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
154 const auto *RHS = Nodes.getNodeAs<clang::Expr>(kRHS);
155 assert(RHS != nullptr);
156
157 Expr::EvalResult R;
158 Element =
159 (RHS->EvaluateAsInt(R, Context) && R.Val.isInt())
160 ? ConstantPropagationLattice{{{Var,
161 R.Val.getInt().getExtValue()}}}
162 : ConstantPropagationLattice::top();
163 } else if (Nodes.getNodeAs<clang::Expr>(kAssignment))
164 // Any assignment involving the expression itself resets the variable to
165 // "unknown". A more advanced analysis could try to evaluate the compound
166 // assignment. For example, `x += 0` need not invalidate `x`.
167 Element = ConstantPropagationLattice::top();
168 }
169 };
170
171 using ::testing::Pair;
172 using ::testing::UnorderedElementsAre;
173
174 MATCHER_P(HasConstantVal, v, "") { return arg.Data && arg.Data->Value == v; }
175
176 MATCHER(IsUnknown, "") { return arg == arg.bottom(); }
177 MATCHER(Varies, "") { return arg == arg.top(); }
178
179 MATCHER_P(HoldsCPLattice, m,
180 ((negation ? "doesn't hold" : "holds") +
181 llvm::StringRef(" a lattice element that ") +
182 ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
183 .str()) {
184 return ExplainMatchResult(m, arg.Lattice, result_listener);
185 }
186
187 template <typename Matcher>
RunDataflow(llvm::StringRef Code,Matcher Expectations)188 void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
189 ASSERT_THAT_ERROR(
190 test::checkDataflow<ConstantPropagationAnalysis>(
191 Code, "fun",
192 [](ASTContext &C, Environment &) {
193 return ConstantPropagationAnalysis(C);
194 },
195 [&Expectations](
196 llvm::ArrayRef<std::pair<
197 std::string, DataflowAnalysisState<
198 ConstantPropagationAnalysis::Lattice>>>
199 Results,
200 ASTContext &) { EXPECT_THAT(Results, Expectations); },
201 {"-fsyntax-only", "-std=c++17"}),
202 llvm::Succeeded());
203 }
204
TEST(ConstantPropagationTest,JustInit)205 TEST(ConstantPropagationTest, JustInit) {
206 std::string Code = R"(
207 void fun() {
208 int target = 1;
209 // [[p]]
210 }
211 )";
212 RunDataflow(
213 Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(1)))));
214 }
215
216 // Verifies that the analysis tracks the last variable seen.
TEST(ConstantPropagationTest,TwoVariables)217 TEST(ConstantPropagationTest, TwoVariables) {
218 std::string Code = R"(
219 void fun() {
220 int target = 1;
221 // [[p1]]
222 int other = 2;
223 // [[p2]]
224 target = 3;
225 // [[p3]]
226 }
227 )";
228 RunDataflow(Code, UnorderedElementsAre(
229 Pair("p1", HoldsCPLattice(HasConstantVal(1))),
230 Pair("p2", HoldsCPLattice(HasConstantVal(2))),
231 Pair("p3", HoldsCPLattice(HasConstantVal(3)))));
232 }
233
TEST(ConstantPropagationTest,Assignment)234 TEST(ConstantPropagationTest, Assignment) {
235 std::string Code = R"(
236 void fun() {
237 int target = 1;
238 // [[p1]]
239 target = 2;
240 // [[p2]]
241 }
242 )";
243 RunDataflow(Code, UnorderedElementsAre(
244 Pair("p1", HoldsCPLattice(HasConstantVal(1))),
245 Pair("p2", HoldsCPLattice(HasConstantVal(2)))));
246 }
247
TEST(ConstantPropagationTest,AssignmentCall)248 TEST(ConstantPropagationTest, AssignmentCall) {
249 std::string Code = R"(
250 int g();
251 void fun() {
252 int target;
253 target = g();
254 // [[p]]
255 }
256 )";
257 RunDataflow(Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(Varies()))));
258 }
259
TEST(ConstantPropagationTest,AssignmentBinOp)260 TEST(ConstantPropagationTest, AssignmentBinOp) {
261 std::string Code = R"(
262 void fun() {
263 int target;
264 target = 2 + 3;
265 // [[p]]
266 }
267 )";
268 RunDataflow(
269 Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(5)))));
270 }
271
TEST(ConstantPropagationTest,PlusAssignment)272 TEST(ConstantPropagationTest, PlusAssignment) {
273 std::string Code = R"(
274 void fun() {
275 int target = 1;
276 // [[p1]]
277 target += 2;
278 // [[p2]]
279 }
280 )";
281 RunDataflow(
282 Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))),
283 Pair("p2", HoldsCPLattice(Varies()))));
284 }
285
TEST(ConstantPropagationTest,SameAssignmentInBranches)286 TEST(ConstantPropagationTest, SameAssignmentInBranches) {
287 std::string Code = R"cc(
288 void fun(bool b) {
289 int target;
290 // [[p1]]
291 if (b) {
292 target = 2;
293 // [[pT]]
294 } else {
295 target = 2;
296 // [[pF]]
297 }
298 (void)0;
299 // [[p2]]
300 }
301 )cc";
302 RunDataflow(Code, UnorderedElementsAre(
303 Pair("p1", HoldsCPLattice(IsUnknown())),
304 Pair("pT", HoldsCPLattice(HasConstantVal(2))),
305 Pair("pF", HoldsCPLattice(HasConstantVal(2))),
306 Pair("p2", HoldsCPLattice(HasConstantVal(2)))));
307 }
308
TEST(ConstantPropagationTest,SameAssignmentInBranch)309 TEST(ConstantPropagationTest, SameAssignmentInBranch) {
310 std::string Code = R"cc(
311 void fun(bool b) {
312 int target = 1;
313 // [[p1]]
314 if (b) {
315 target = 1;
316 }
317 (void)0;
318 // [[p2]]
319 }
320 )cc";
321 RunDataflow(Code, UnorderedElementsAre(
322 Pair("p1", HoldsCPLattice(HasConstantVal(1))),
323 Pair("p2", HoldsCPLattice(HasConstantVal(1)))));
324 }
325
TEST(ConstantPropagationTest,NewVarInBranch)326 TEST(ConstantPropagationTest, NewVarInBranch) {
327 std::string Code = R"cc(
328 void fun(bool b) {
329 if (b) {
330 int target;
331 // [[p1]]
332 target = 1;
333 // [[p2]]
334 } else {
335 int target;
336 // [[p3]]
337 target = 1;
338 // [[p4]]
339 }
340 }
341 )cc";
342 RunDataflow(Code, UnorderedElementsAre(
343 Pair("p1", HoldsCPLattice(IsUnknown())),
344 Pair("p2", HoldsCPLattice(HasConstantVal(1))),
345 Pair("p3", HoldsCPLattice(IsUnknown())),
346 Pair("p4", HoldsCPLattice(HasConstantVal(1)))));
347 }
348
TEST(ConstantPropagationTest,DifferentAssignmentInBranches)349 TEST(ConstantPropagationTest, DifferentAssignmentInBranches) {
350 std::string Code = R"cc(
351 void fun(bool b) {
352 int target;
353 // [[p1]]
354 if (b) {
355 target = 1;
356 // [[pT]]
357 } else {
358 target = 2;
359 // [[pF]]
360 }
361 (void)0;
362 // [[p2]]
363 }
364 )cc";
365 RunDataflow(
366 Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(IsUnknown())),
367 Pair("pT", HoldsCPLattice(HasConstantVal(1))),
368 Pair("pF", HoldsCPLattice(HasConstantVal(2))),
369 Pair("p2", HoldsCPLattice(Varies()))));
370 }
371
TEST(ConstantPropagationTest,DifferentAssignmentInBranch)372 TEST(ConstantPropagationTest, DifferentAssignmentInBranch) {
373 std::string Code = R"cc(
374 void fun(bool b) {
375 int target = 1;
376 // [[p1]]
377 if (b) {
378 target = 3;
379 }
380 (void)0;
381 // [[p2]]
382 }
383 )cc";
384 RunDataflow(
385 Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))),
386 Pair("p2", HoldsCPLattice(Varies()))));
387 }
388
389 } // namespace
390 } // namespace dataflow
391 } // namespace clang
392