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
41namespace clang {
42namespace dataflow {
43namespace {
44using 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.
49struct 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
58 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
65 static constexpr ConstantPropagationLattice bottom() {
66 return {.Data: std::nullopt};
67 }
68 static constexpr ConstantPropagationLattice top() {
69 return {.Data: VarValue{.Var: nullptr, .Value: 0}};
70 }
71
72 friend bool operator==(const ConstantPropagationLattice &Lhs,
73 const ConstantPropagationLattice &Rhs) {
74 return Lhs.Data == Rhs.Data;
75 }
76
77 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
91std::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
102static constexpr char kVar[] = "var";
103static constexpr char kInit[] = "init";
104static constexpr char kJustAssignment[] = "just-assignment";
105static constexpr char kAssignment[] = "assignment";
106static constexpr char kRHS[] = "rhs";
107
108static auto refToVar() { return declRefExpr(to(InnerMatcher: varDecl().bind(ID: kVar))); }
109
110namespace {
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.
115class ConstantPropagationAnalysis
116 : public DataflowAnalysis<ConstantPropagationAnalysis,
117 ConstantPropagationLattice> {
118public:
119 explicit ConstantPropagationAnalysis(ASTContext &Context)
120 : DataflowAnalysis<ConstantPropagationAnalysis,
121 ConstantPropagationLattice>(Context) {}
122
123 static ConstantPropagationLattice initialElement() {
124 return ConstantPropagationLattice::bottom();
125 }
126
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(InnerMatcher: varDecl(hasType(InnerMatcher: isInteger()),
135 hasInitializer(InnerMatcher: expr().bind(ID: kInit)))
136 .bind(ID: kVar))),
137 binaryOperator(hasOperatorName(Name: "="), hasLHS(InnerMatcher: refToVar()),
138 hasRHS(InnerMatcher: expr().bind(ID: kRHS)))
139 .bind(ID: kJustAssignment),
140 binaryOperator(isAssignmentOperator(), hasLHS(InnerMatcher: refToVar()))
141 .bind(ID: kAssignment)));
142
143 ASTContext &Context = getASTContext();
144 auto Results = match(Matcher: matcher, Node: *S, Context);
145 if (Results.empty())
146 return;
147 const BoundNodes &Nodes = Results[0];
148
149 const auto *Var = Nodes.getNodeAs<clang::VarDecl>(ID: kVar);
150 assert(Var != nullptr);
151
152 if (const auto *E = Nodes.getNodeAs<clang::Expr>(ID: kInit)) {
153 Expr::EvalResult R;
154 Element =
155 (E->EvaluateAsInt(Result&: R, Ctx: Context) && R.Val.isInt())
156 ? ConstantPropagationLattice{.Data: {{.Var: Var,
157 .Value: R.Val.getInt().getExtValue()}}}
158 : ConstantPropagationLattice::top();
159 } else if (Nodes.getNodeAs<clang::Expr>(ID: kJustAssignment)) {
160 const auto *RHS = Nodes.getNodeAs<clang::Expr>(ID: kRHS);
161 assert(RHS != nullptr);
162
163 Expr::EvalResult R;
164 Element =
165 (RHS->EvaluateAsInt(Result&: R, Ctx: Context) && R.Val.isInt())
166 ? ConstantPropagationLattice{.Data: {{.Var: Var,
167 .Value: R.Val.getInt().getExtValue()}}}
168 : ConstantPropagationLattice::top();
169 } else if (Nodes.getNodeAs<clang::Expr>(ID: 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
177using ::clang::dataflow::test::AnalysisInputs;
178using ::clang::dataflow::test::AnalysisOutputs;
179using ::clang::dataflow::test::checkDataflow;
180using ::llvm::IsStringMapEntry;
181using ::testing::UnorderedElementsAre;
182
183MATCHER_P(HasConstantVal, v, "") { return arg.Data && arg.Data->Value == v; }
184
185MATCHER(IsUnknown, "") { return arg == arg.bottom(); }
186MATCHER(Varies, "") { return arg == arg.top(); }
187
188MATCHER_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
196template <typename Matcher>
197void 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
215TEST(ConstantPropagationTest, JustInit) {
216 std::string Code = R"(
217 void fun() {
218 int target = 1;
219 // [[p]]
220 }
221 )";
222 RunDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
223 KM: "p", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1)))));
224}
225
226// Verifies that the analysis tracks the last variable seen.
227TEST(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 Expectations: UnorderedElementsAre(
240 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1))),
241 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 2))),
242 matchers: IsStringMapEntry(KM: "p3", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 3)))));
243}
244
245TEST(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 Expectations: UnorderedElementsAre(
256 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1))),
257 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 2)))));
258}
259
260TEST(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, Expectations: UnorderedElementsAre(
270 matchers: IsStringMapEntry(KM: "p", VM: HoldsCPLattice(gmock_p0: Varies()))));
271}
272
273TEST(ConstantPropagationTest, AssignmentBinOp) {
274 std::string Code = R"(
275 void fun() {
276 int target;
277 target = 2 + 3;
278 // [[p]]
279 }
280 )";
281 RunDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
282 KM: "p", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 5)))));
283}
284
285TEST(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 Expectations: UnorderedElementsAre(
296 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1))),
297 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: Varies()))));
298}
299
300TEST(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 Expectations: UnorderedElementsAre(
318 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: IsUnknown())),
319 matchers: IsStringMapEntry(KM: "pT", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 2))),
320 matchers: IsStringMapEntry(KM: "pF", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 2))),
321 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 2)))));
322}
323
324TEST(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 Expectations: UnorderedElementsAre(
338 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1))),
339 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1)))));
340}
341
342TEST(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 Expectations: UnorderedElementsAre(
360 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: IsUnknown())),
361 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1))),
362 matchers: IsStringMapEntry(KM: "p3", VM: HoldsCPLattice(gmock_p0: IsUnknown())),
363 matchers: IsStringMapEntry(KM: "p4", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1)))));
364}
365
366TEST(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 Expectations: UnorderedElementsAre(
384 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: IsUnknown())),
385 matchers: IsStringMapEntry(KM: "pT", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1))),
386 matchers: IsStringMapEntry(KM: "pF", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 2))),
387 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: Varies()))));
388}
389
390TEST(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 Expectations: UnorderedElementsAre(
404 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: HasConstantVal(gmock_p0: 1))),
405 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: Varies()))));
406}
407
408} // namespace
409} // namespace dataflow
410} // namespace clang
411

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