1//===- unittests/Analysis/FlowSensitive/MultiVarConstantPropagation.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 tracks all
11// variables in the scope, but lacks escape analysis.
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 "clang/Analysis/FlowSensitive/MapLattice.h"
27#include "llvm/ADT/StringRef.h"
28#include "llvm/ADT/Twine.h"
29#include "llvm/Support/Error.h"
30#include "llvm/Testing/ADT/StringMapEntry.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// Models the value of an expression at a program point, for all paths through
47// the program.
48struct ValueLattice {
49 // FIXME: change the internal representation to use a `std::variant`, once
50 // clang admits C++17 constructs.
51 enum class ValueState : bool {
52 Undefined,
53 Defined,
54 };
55 // `State` determines the meaning of the lattice when `Value` is `None`:
56 // * `Undefined` -> bottom,
57 // * `Defined` -> top.
58 ValueState State;
59
60 // When `std::nullopt`, the lattice is either at top or bottom, based on
61 // `State`.
62 std::optional<int64_t> Value;
63
64 constexpr ValueLattice()
65 : State(ValueState::Undefined), Value(std::nullopt) {}
66 constexpr ValueLattice(int64_t V) : State(ValueState::Defined), Value(V) {}
67 constexpr ValueLattice(ValueState S) : State(S), Value(std::nullopt) {}
68
69 static constexpr ValueLattice bottom() {
70 return ValueLattice(ValueState::Undefined);
71 }
72 static constexpr ValueLattice top() {
73 return ValueLattice(ValueState::Defined);
74 }
75
76 friend bool operator==(const ValueLattice &Lhs, const ValueLattice &Rhs) {
77 return Lhs.State == Rhs.State && Lhs.Value == Rhs.Value;
78 }
79 friend bool operator!=(const ValueLattice &Lhs, const ValueLattice &Rhs) {
80 return !(Lhs == Rhs);
81 }
82
83 LatticeJoinEffect join(const ValueLattice &Other) {
84 if (*this == Other || Other == bottom() || *this == top())
85 return LatticeJoinEffect::Unchanged;
86
87 if (*this == bottom()) {
88 *this = Other;
89 return LatticeJoinEffect::Changed;
90 }
91
92 *this = top();
93 return LatticeJoinEffect::Changed;
94 }
95};
96
97std::ostream &operator<<(std::ostream &OS, const ValueLattice &L) {
98 if (L.Value)
99 return OS << *L.Value;
100 switch (L.State) {
101 case ValueLattice::ValueState::Undefined:
102 return OS << "None";
103 case ValueLattice::ValueState::Defined:
104 return OS << "Any";
105 }
106 llvm_unreachable("unknown ValueState!");
107}
108
109using ConstantPropagationLattice = VarMapLattice<ValueLattice>;
110
111constexpr char kDecl[] = "decl";
112constexpr char kVar[] = "var";
113constexpr char kInit[] = "init";
114constexpr char kJustAssignment[] = "just-assignment";
115constexpr char kAssignment[] = "assignment";
116constexpr char kRHS[] = "rhs";
117
118auto refToVar() { return declRefExpr(to(InnerMatcher: varDecl().bind(ID: kVar))); }
119
120// N.B. This analysis is deliberately simplistic, leaving out many important
121// details needed for a real analysis. Most notably, the transfer function does
122// not account for the variable's address possibly escaping, which would
123// invalidate the analysis. It also could be optimized to drop out-of-scope
124// variables from the map.
125class ConstantPropagationAnalysis
126 : public DataflowAnalysis<ConstantPropagationAnalysis,
127 ConstantPropagationLattice> {
128public:
129 explicit ConstantPropagationAnalysis(ASTContext &Context)
130 : DataflowAnalysis<ConstantPropagationAnalysis,
131 ConstantPropagationLattice>(Context) {}
132
133 static ConstantPropagationLattice initialElement() {
134 return ConstantPropagationLattice::bottom();
135 }
136
137 void transfer(const CFGElement &E, ConstantPropagationLattice &Vars,
138 Environment &Env) {
139 auto CS = E.getAs<CFGStmt>();
140 if (!CS)
141 return;
142 auto S = CS->getStmt();
143 auto matcher =
144 stmt(anyOf(declStmt(hasSingleDecl(
145 InnerMatcher: varDecl(decl().bind(ID: kVar), hasType(InnerMatcher: isInteger()),
146 optionally(hasInitializer(InnerMatcher: expr().bind(ID: kInit))))
147 .bind(ID: kDecl))),
148 binaryOperator(hasOperatorName(Name: "="), hasLHS(InnerMatcher: refToVar()),
149 hasRHS(InnerMatcher: expr().bind(ID: kRHS)))
150 .bind(ID: kJustAssignment),
151 binaryOperator(isAssignmentOperator(), hasLHS(InnerMatcher: refToVar()))
152 .bind(ID: kAssignment)));
153
154 ASTContext &Context = getASTContext();
155 auto Results = match(Matcher: matcher, Node: *S, Context);
156 if (Results.empty())
157 return;
158 const BoundNodes &Nodes = Results[0];
159
160 const auto *Var = Nodes.getNodeAs<clang::VarDecl>(ID: kVar);
161 assert(Var != nullptr);
162
163 if (Nodes.getNodeAs<clang::VarDecl>(ID: kDecl) != nullptr) {
164 if (const auto *E = Nodes.getNodeAs<clang::Expr>(ID: kInit)) {
165 Expr::EvalResult R;
166 Vars[Var] = (E->EvaluateAsInt(Result&: R, Ctx: Context) && R.Val.isInt())
167 ? ValueLattice(R.Val.getInt().getExtValue())
168 : ValueLattice::top();
169 } else {
170 // An uninitialized variable holds *some* value, but we don't know what
171 // it is (it is implementation defined), so we set it to top.
172 Vars[Var] = ValueLattice::top();
173 }
174 } else if (Nodes.getNodeAs<clang::Expr>(ID: kJustAssignment)) {
175 const auto *E = Nodes.getNodeAs<clang::Expr>(ID: kRHS);
176 assert(E != nullptr);
177
178 Expr::EvalResult R;
179 Vars[Var] = (E->EvaluateAsInt(Result&: R, Ctx: Context) && R.Val.isInt())
180 ? ValueLattice(R.Val.getInt().getExtValue())
181 : ValueLattice::top();
182 } else if (Nodes.getNodeAs<clang::Expr>(ID: kAssignment)) {
183 // Any assignment involving the expression itself resets the variable to
184 // "unknown". A more advanced analysis could try to evaluate the compound
185 // assignment. For example, `x += 0` need not invalidate `x`.
186 Vars[Var] = ValueLattice::top();
187 }
188 }
189};
190
191using ::clang::dataflow::test::AnalysisInputs;
192using ::clang::dataflow::test::AnalysisOutputs;
193using ::clang::dataflow::test::checkDataflow;
194using ::llvm::IsStringMapEntry;
195using ::testing::Pair;
196using ::testing::UnorderedElementsAre;
197
198MATCHER_P(Var, name,
199 (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +
200 name + "`")
201 .str()) {
202 return arg->getName() == name;
203}
204
205MATCHER_P(HasConstantVal, v, "") { return arg.Value && *arg.Value == v; }
206
207MATCHER(Varies, "") { return arg == arg.top(); }
208
209MATCHER_P(HoldsCPLattice, m,
210 ((negation ? "doesn't hold" : "holds") +
211 llvm::StringRef(" a lattice element that ") +
212 ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
213 .str()) {
214 return ExplainMatchResult(m, arg.Lattice, result_listener);
215}
216
217template <typename Matcher>
218void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
219 ASSERT_THAT_ERROR(
220 checkDataflow<ConstantPropagationAnalysis>(
221 AnalysisInputs<ConstantPropagationAnalysis>(
222 Code, hasName("fun"),
223 [](ASTContext &C, Environment &) {
224 return ConstantPropagationAnalysis(C);
225 })
226 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
227 /*VerifyResults=*/
228 [&Expectations](const llvm::StringMap<DataflowAnalysisState<
229 ConstantPropagationAnalysis::Lattice>> &Results,
230 const AnalysisOutputs &) {
231 EXPECT_THAT(Results, Expectations);
232 }),
233 llvm::Succeeded());
234}
235
236TEST(MultiVarConstantPropagationTest, JustInit) {
237 std::string Code = R"(
238 void fun() {
239 int target = 1;
240 // [[p]]
241 }
242 )";
243 RunDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
244 KM: "p", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
245 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1)))))));
246}
247
248TEST(MultiVarConstantPropagationTest, Assignment) {
249 std::string Code = R"(
250 void fun() {
251 int target = 1;
252 // [[p1]]
253 target = 2;
254 // [[p2]]
255 }
256 )";
257 RunDataflow(
258 Code,
259 Expectations: UnorderedElementsAre(
260 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
261 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1))))),
262 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(matchers: Pair(
263 first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 2)))))));
264}
265
266TEST(MultiVarConstantPropagationTest, AssignmentCall) {
267 std::string Code = R"(
268 int g();
269 void fun() {
270 int target;
271 target = g();
272 // [[p]]
273 }
274 )";
275 RunDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
276 KM: "p", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
277 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies()))))));
278}
279
280TEST(MultiVarConstantPropagationTest, AssignmentBinOp) {
281 std::string Code = R"(
282 void fun() {
283 int target;
284 target = 2 + 3;
285 // [[p]]
286 }
287 )";
288 RunDataflow(Code, Expectations: UnorderedElementsAre(matchers: IsStringMapEntry(
289 KM: "p", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
290 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 5)))))));
291}
292
293TEST(MultiVarConstantPropagationTest, PlusAssignment) {
294 std::string Code = R"(
295 void fun() {
296 int target = 1;
297 // [[p1]]
298 target += 2;
299 // [[p2]]
300 }
301 )";
302 RunDataflow(
303 Code, Expectations: UnorderedElementsAre(
304 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(matchers: Pair(
305 first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1))))),
306 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
307 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies()))))));
308}
309
310TEST(MultiVarConstantPropagationTest, SameAssignmentInBranches) {
311 std::string Code = R"cc(
312 void fun(bool b) {
313 int target;
314 // [[p1]]
315 if (b) {
316 target = 2;
317 // [[pT]]
318 } else {
319 target = 2;
320 // [[pF]]
321 }
322 (void)0;
323 // [[p2]]
324 }
325 )cc";
326 RunDataflow(
327 Code,
328 Expectations: UnorderedElementsAre(
329 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
330 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies())))),
331 matchers: IsStringMapEntry(KM: "pT", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
332 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 2))))),
333 matchers: IsStringMapEntry(KM: "pF", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
334 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 2))))),
335 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(matchers: Pair(
336 first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 2)))))));
337}
338
339// Verifies that the analysis tracks multiple variables simultaneously.
340TEST(MultiVarConstantPropagationTest, TwoVariables) {
341 std::string Code = R"(
342 void fun() {
343 int target = 1;
344 // [[p1]]
345 int other = 2;
346 // [[p2]]
347 target = 3;
348 // [[p3]]
349 }
350 )";
351 RunDataflow(
352 Code,
353 Expectations: UnorderedElementsAre(
354 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
355 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1))))),
356 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
357 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1)),
358 matchers: Pair(first_matcher: Var(gmock_p0: "other"), second_matcher: HasConstantVal(gmock_p0: 2))))),
359 matchers: IsStringMapEntry(KM: "p3", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
360 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 3)),
361 matchers: Pair(first_matcher: Var(gmock_p0: "other"), second_matcher: HasConstantVal(gmock_p0: 2)))))));
362}
363
364TEST(MultiVarConstantPropagationTest, TwoVariablesInBranches) {
365 std::string Code = R"cc(
366 void fun(bool b) {
367 int target;
368 int other;
369 // [[p1]]
370 if (b) {
371 target = 2;
372 // [[pT]]
373 } else {
374 other = 3;
375 // [[pF]]
376 }
377 (void)0;
378 // [[p2]]
379 }
380 )cc";
381 RunDataflow(
382 Code,
383 Expectations: UnorderedElementsAre(
384 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
385 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies()),
386 matchers: Pair(first_matcher: Var(gmock_p0: "other"), second_matcher: Varies())))),
387 matchers: IsStringMapEntry(KM: "pT", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
388 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 2)),
389 matchers: Pair(first_matcher: Var(gmock_p0: "other"), second_matcher: Varies())))),
390 matchers: IsStringMapEntry(KM: "pF", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
391 matchers: Pair(first_matcher: Var(gmock_p0: "other"), second_matcher: HasConstantVal(gmock_p0: 3)),
392 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies())))),
393 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
394 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies()),
395 matchers: Pair(first_matcher: Var(gmock_p0: "other"), second_matcher: Varies()))))));
396}
397
398TEST(MultiVarConstantPropagationTest, SameAssignmentInBranch) {
399 std::string Code = R"cc(
400 void fun(bool b) {
401 int target = 1;
402 // [[p1]]
403 if (b) {
404 target = 1;
405 }
406 (void)0;
407 // [[p2]]
408 }
409 )cc";
410 RunDataflow(
411 Code,
412 Expectations: UnorderedElementsAre(
413 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
414 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1))))),
415 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(matchers: Pair(
416 first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1)))))));
417}
418
419TEST(MultiVarConstantPropagationTest, NewVarInBranch) {
420 std::string Code = R"cc(
421 void fun(bool b) {
422 if (b) {
423 int target;
424 // [[p1]]
425 target = 1;
426 // [[p2]]
427 } else {
428 int target;
429 // [[p3]]
430 target = 1;
431 // [[p4]]
432 }
433 }
434 )cc";
435 RunDataflow(
436 Code,
437 Expectations: UnorderedElementsAre(
438 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
439 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies())))),
440 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
441 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1))))),
442 matchers: IsStringMapEntry(KM: "p3", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
443 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies())))),
444 matchers: IsStringMapEntry(KM: "p4", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(matchers: Pair(
445 first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1)))))));
446}
447
448TEST(MultiVarConstantPropagationTest, DifferentAssignmentInBranches) {
449 std::string Code = R"cc(
450 void fun(bool b) {
451 int target;
452 // [[p1]]
453 if (b) {
454 target = 1;
455 // [[pT]]
456 } else {
457 target = 2;
458 // [[pF]]
459 }
460 (void)0;
461 // [[p2]]
462 }
463 )cc";
464 RunDataflow(
465 Code, Expectations: UnorderedElementsAre(
466 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
467 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies())))),
468 matchers: IsStringMapEntry(KM: "pT", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(matchers: Pair(
469 first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1))))),
470 matchers: IsStringMapEntry(KM: "pF", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(matchers: Pair(
471 first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 2))))),
472 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
473 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies()))))));
474}
475
476TEST(MultiVarConstantPropagationTest, DifferentAssignmentInBranch) {
477 std::string Code = R"cc(
478 void fun(bool b) {
479 int target = 1;
480 // [[p1]]
481 if (b) {
482 target = 3;
483 }
484 (void)0;
485 // [[p2]]
486 }
487 )cc";
488 RunDataflow(
489 Code, Expectations: UnorderedElementsAre(
490 matchers: IsStringMapEntry(KM: "p1", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(matchers: Pair(
491 first_matcher: Var(gmock_p0: "target"), second_matcher: HasConstantVal(gmock_p0: 1))))),
492 matchers: IsStringMapEntry(KM: "p2", VM: HoldsCPLattice(gmock_p0: UnorderedElementsAre(
493 matchers: Pair(first_matcher: Var(gmock_p0: "target"), second_matcher: Varies()))))));
494}
495
496} // namespace
497} // namespace dataflow
498} // namespace clang
499

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