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