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 `std::nullopt`, the lattice is either at top or bottom, based on
61 // `State`.
62 std::optional<int64_t> Value;
63
ValueLatticeclang::dataflow::__anon18d4833f0111::ValueLattice64 constexpr ValueLattice()
65 : State(ValueState::Undefined), Value(std::nullopt) {}
ValueLatticeclang::dataflow::__anon18d4833f0111::ValueLattice66 constexpr ValueLattice(int64_t V) : State(ValueState::Defined), Value(V) {}
ValueLatticeclang::dataflow::__anon18d4833f0111::ValueLattice67 constexpr ValueLattice(ValueState S) : State(S), Value(std::nullopt) {}
68
bottomclang::dataflow::__anon18d4833f0111::ValueLattice69 static constexpr ValueLattice bottom() {
70 return ValueLattice(ValueState::Undefined);
71 }
topclang::dataflow::__anon18d4833f0111::ValueLattice72 static constexpr ValueLattice top() {
73 return ValueLattice(ValueState::Defined);
74 }
75
operator ==(const ValueLattice & Lhs,const ValueLattice & Rhs)76 friend bool operator==(const ValueLattice &Lhs, const ValueLattice &Rhs) {
77 return Lhs.State == Rhs.State && Lhs.Value == Rhs.Value;
78 }
operator !=(const ValueLattice & Lhs,const ValueLattice & Rhs)79 friend bool operator!=(const ValueLattice &Lhs, const ValueLattice &Rhs) {
80 return !(Lhs == Rhs);
81 }
82
joinclang::dataflow::__anon18d4833f0111::ValueLattice83 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
operator <<(std::ostream & OS,const ValueLattice & L)97 std::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
109 using ConstantPropagationLattice = VarMapLattice<ValueLattice>;
110
111 constexpr char kDecl[] = "decl";
112 constexpr char kVar[] = "var";
113 constexpr char kInit[] = "init";
114 constexpr char kJustAssignment[] = "just-assignment";
115 constexpr char kAssignment[] = "assignment";
116 constexpr char kRHS[] = "rhs";
117
refToVar()118 auto refToVar() { return declRefExpr(to(varDecl().bind(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.
125 class ConstantPropagationAnalysis
126 : public DataflowAnalysis<ConstantPropagationAnalysis,
127 ConstantPropagationLattice> {
128 public:
ConstantPropagationAnalysis(ASTContext & Context)129 explicit ConstantPropagationAnalysis(ASTContext &Context)
130 : DataflowAnalysis<ConstantPropagationAnalysis,
131 ConstantPropagationLattice>(Context) {}
132
initialElement()133 static ConstantPropagationLattice initialElement() {
134 return ConstantPropagationLattice::bottom();
135 }
136
transfer(const CFGElement & E,ConstantPropagationLattice & Vars,Environment & Env)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 varDecl(decl().bind(kVar), hasType(isInteger()),
146 optionally(hasInitializer(expr().bind(kInit))))
147 .bind(kDecl))),
148 binaryOperator(hasOperatorName("="), hasLHS(refToVar()),
149 hasRHS(expr().bind(kRHS)))
150 .bind(kJustAssignment),
151 binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))
152 .bind(kAssignment)));
153
154 ASTContext &Context = getASTContext();
155 auto Results = match(matcher, *S, Context);
156 if (Results.empty())
157 return;
158 const BoundNodes &Nodes = Results[0];
159
160 const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
161 assert(Var != nullptr);
162
163 if (Nodes.getNodeAs<clang::VarDecl>(kDecl) != nullptr) {
164 if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
165 Expr::EvalResult R;
166 Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
167 ? ValueLattice(R.Val.getInt().getExtValue())
168 : ValueLattice::top();
169 } else {
170 // An unitialized variable holds *some* value, but we don't know what it
171 // is (it is implementation defined), so we set it to top.
172 Vars[Var] = ValueLattice::top();
173 }
174 } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
175 const auto *E = Nodes.getNodeAs<clang::Expr>(kRHS);
176 assert(E != nullptr);
177
178 Expr::EvalResult R;
179 Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
180 ? ValueLattice(R.Val.getInt().getExtValue())
181 : ValueLattice::top();
182 } else if (Nodes.getNodeAs<clang::Expr>(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
191 using ::clang::dataflow::test::AnalysisInputs;
192 using ::clang::dataflow::test::AnalysisOutputs;
193 using ::clang::dataflow::test::checkDataflow;
194 using ::llvm::IsStringMapEntry;
195 using ::testing::Pair;
196 using ::testing::UnorderedElementsAre;
197
198 MATCHER_P(Var, name,
199 (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +
200 name + "`")
201 .str()) {
202 return arg->getName() == name;
203 }
204
205 MATCHER_P(HasConstantVal, v, "") { return arg.Value && *arg.Value == v; }
206
207 MATCHER(Varies, "") { return arg == arg.top(); }
208
209 MATCHER_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
217 template <typename Matcher>
RunDataflow(llvm::StringRef Code,Matcher Expectations)218 void 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
TEST(MultiVarConstantPropagationTest,JustInit)236 TEST(MultiVarConstantPropagationTest, JustInit) {
237 std::string Code = R"(
238 void fun() {
239 int target = 1;
240 // [[p]]
241 }
242 )";
243 RunDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
244 "p", HoldsCPLattice(UnorderedElementsAre(
245 Pair(Var("target"), HasConstantVal(1)))))));
246 }
247
TEST(MultiVarConstantPropagationTest,Assignment)248 TEST(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 UnorderedElementsAre(
260 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(
261 Pair(Var("target"), HasConstantVal(1))))),
262 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
263 Var("target"), HasConstantVal(2)))))));
264 }
265
TEST(MultiVarConstantPropagationTest,AssignmentCall)266 TEST(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, UnorderedElementsAre(IsStringMapEntry(
276 "p", HoldsCPLattice(UnorderedElementsAre(
277 Pair(Var("target"), Varies()))))));
278 }
279
TEST(MultiVarConstantPropagationTest,AssignmentBinOp)280 TEST(MultiVarConstantPropagationTest, AssignmentBinOp) {
281 std::string Code = R"(
282 void fun() {
283 int target;
284 target = 2 + 3;
285 // [[p]]
286 }
287 )";
288 RunDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
289 "p", HoldsCPLattice(UnorderedElementsAre(
290 Pair(Var("target"), HasConstantVal(5)))))));
291 }
292
TEST(MultiVarConstantPropagationTest,PlusAssignment)293 TEST(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, UnorderedElementsAre(
304 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
305 Var("target"), HasConstantVal(1))))),
306 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(
307 Pair(Var("target"), Varies()))))));
308 }
309
TEST(MultiVarConstantPropagationTest,SameAssignmentInBranches)310 TEST(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 UnorderedElementsAre(
329 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(
330 Pair(Var("target"), Varies())))),
331 IsStringMapEntry("pT", HoldsCPLattice(UnorderedElementsAre(
332 Pair(Var("target"), HasConstantVal(2))))),
333 IsStringMapEntry("pF", HoldsCPLattice(UnorderedElementsAre(
334 Pair(Var("target"), HasConstantVal(2))))),
335 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
336 Var("target"), HasConstantVal(2)))))));
337 }
338
339 // Verifies that the analysis tracks multiple variables simultaneously.
TEST(MultiVarConstantPropagationTest,TwoVariables)340 TEST(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 UnorderedElementsAre(
354 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(
355 Pair(Var("target"), HasConstantVal(1))))),
356 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(
357 Pair(Var("target"), HasConstantVal(1)),
358 Pair(Var("other"), HasConstantVal(2))))),
359 IsStringMapEntry("p3", HoldsCPLattice(UnorderedElementsAre(
360 Pair(Var("target"), HasConstantVal(3)),
361 Pair(Var("other"), HasConstantVal(2)))))));
362 }
363
TEST(MultiVarConstantPropagationTest,TwoVariablesInBranches)364 TEST(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 UnorderedElementsAre(
384 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(
385 Pair(Var("target"), Varies()),
386 Pair(Var("other"), Varies())))),
387 IsStringMapEntry("pT", HoldsCPLattice(UnorderedElementsAre(
388 Pair(Var("target"), HasConstantVal(2)),
389 Pair(Var("other"), Varies())))),
390 IsStringMapEntry("pF", HoldsCPLattice(UnorderedElementsAre(
391 Pair(Var("other"), HasConstantVal(3)),
392 Pair(Var("target"), Varies())))),
393 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(
394 Pair(Var("target"), Varies()),
395 Pair(Var("other"), Varies()))))));
396 }
397
TEST(MultiVarConstantPropagationTest,SameAssignmentInBranch)398 TEST(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 UnorderedElementsAre(
413 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(
414 Pair(Var("target"), HasConstantVal(1))))),
415 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
416 Var("target"), HasConstantVal(1)))))));
417 }
418
TEST(MultiVarConstantPropagationTest,NewVarInBranch)419 TEST(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 UnorderedElementsAre(
438 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(
439 Pair(Var("target"), Varies())))),
440 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(
441 Pair(Var("target"), HasConstantVal(1))))),
442 IsStringMapEntry("p3", HoldsCPLattice(UnorderedElementsAre(
443 Pair(Var("target"), Varies())))),
444 IsStringMapEntry("p4", HoldsCPLattice(UnorderedElementsAre(Pair(
445 Var("target"), HasConstantVal(1)))))));
446 }
447
TEST(MultiVarConstantPropagationTest,DifferentAssignmentInBranches)448 TEST(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, UnorderedElementsAre(
466 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(
467 Pair(Var("target"), Varies())))),
468 IsStringMapEntry("pT", HoldsCPLattice(UnorderedElementsAre(Pair(
469 Var("target"), HasConstantVal(1))))),
470 IsStringMapEntry("pF", HoldsCPLattice(UnorderedElementsAre(Pair(
471 Var("target"), HasConstantVal(2))))),
472 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(
473 Pair(Var("target"), Varies()))))));
474 }
475
TEST(MultiVarConstantPropagationTest,DifferentAssignmentInBranch)476 TEST(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, UnorderedElementsAre(
490 IsStringMapEntry("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
491 Var("target"), HasConstantVal(1))))),
492 IsStringMapEntry("p2", HoldsCPLattice(UnorderedElementsAre(
493 Pair(Var("target"), Varies()))))));
494 }
495
496 } // namespace
497 } // namespace dataflow
498 } // namespace clang
499