Debian Codegraph @

llvm-project/clang/unittests/Analysis/FlowSensitive/MultiVarConstantPropagationTest.cpp

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