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/FlowSensitive/DataflowAnalysis.h"
23 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
24 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
25 #include "clang/Analysis/FlowSensitive/MapLattice.h"
26 #include "clang/Tooling/Tooling.h"
27 #include "llvm/ADT/None.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/ADT/StringRef.h"
30 #include "llvm/ADT/Twine.h"
31 #include "llvm/Support/Error.h"
32 #include "llvm/Testing/Support/Annotations.h"
33 #include "llvm/Testing/Support/Error.h"
34 #include "gmock/gmock.h"
35 #include "gtest/gtest.h"
36 #include <cstdint>
37 #include <memory>
38 #include <ostream>
39 #include <string>
40 #include <utility>
41
42 namespace clang {
43 namespace dataflow {
44 namespace {
45 using namespace ast_matchers;
46
47 // Models the value of an expression at a program point, for all paths through
48 // the program.
49 struct ValueLattice {
50 // FIXME: change the internal representation to use a `std::variant`, once
51 // clang admits C++17 constructs.
52 enum class ValueState : bool {
53 Undefined,
54 Defined,
55 };
56 // `State` determines the meaning of the lattice when `Value` is `None`:
57 // * `Undefined` -> bottom,
58 // * `Defined` -> top.
59 ValueState State;
60
61 // When `None`, the lattice is either at top or bottom, based on `State`.
62 llvm::Optional<int64_t> Value;
63
ValueLatticeclang::dataflow::__anonfcb2a35c0111::ValueLattice64 constexpr ValueLattice() : State(ValueState::Undefined), Value(llvm::None) {}
ValueLatticeclang::dataflow::__anonfcb2a35c0111::ValueLattice65 constexpr ValueLattice(int64_t V) : State(ValueState::Defined), Value(V) {}
ValueLatticeclang::dataflow::__anonfcb2a35c0111::ValueLattice66 constexpr ValueLattice(ValueState S) : State(S), Value(llvm::None) {}
67
bottomclang::dataflow::__anonfcb2a35c0111::ValueLattice68 static constexpr ValueLattice bottom() {
69 return ValueLattice(ValueState::Undefined);
70 }
topclang::dataflow::__anonfcb2a35c0111::ValueLattice71 static constexpr ValueLattice top() {
72 return ValueLattice(ValueState::Defined);
73 }
74
operator ==(const ValueLattice & Lhs,const ValueLattice & Rhs)75 friend bool operator==(const ValueLattice &Lhs, const ValueLattice &Rhs) {
76 return Lhs.State == Rhs.State && Lhs.Value == Rhs.Value;
77 }
operator !=(const ValueLattice & Lhs,const ValueLattice & Rhs)78 friend bool operator!=(const ValueLattice &Lhs, const ValueLattice &Rhs) {
79 return !(Lhs == Rhs);
80 }
81
joinclang::dataflow::__anonfcb2a35c0111::ValueLattice82 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
operator <<(std::ostream & OS,const ValueLattice & L)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
refToVar()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:
ConstantPropagationAnalysis(ASTContext & Context)128 explicit ConstantPropagationAnalysis(ASTContext &Context)
129 : DataflowAnalysis<ConstantPropagationAnalysis,
130 ConstantPropagationLattice>(Context) {}
131
initialElement()132 static ConstantPropagationLattice initialElement() {
133 return ConstantPropagationLattice::bottom();
134 }
135
transfer(const Stmt * S,ConstantPropagationLattice & Vars,Environment & Env)136 void transfer(const Stmt *S, ConstantPropagationLattice &Vars,
137 Environment &Env) {
138 auto matcher =
139 stmt(anyOf(declStmt(hasSingleDecl(
140 varDecl(decl().bind(kVar), hasType(isInteger()),
141 optionally(hasInitializer(expr().bind(kInit))))
142 .bind(kDecl))),
143 binaryOperator(hasOperatorName("="), hasLHS(refToVar()),
144 hasRHS(expr().bind(kRHS)))
145 .bind(kJustAssignment),
146 binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))
147 .bind(kAssignment)));
148
149 ASTContext &Context = getASTContext();
150 auto Results = match(matcher, *S, Context);
151 if (Results.empty())
152 return;
153 const BoundNodes &Nodes = Results[0];
154
155 const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
156 assert(Var != nullptr);
157
158 if (Nodes.getNodeAs<clang::VarDecl>(kDecl) != nullptr) {
159 if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
160 Expr::EvalResult R;
161 Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
162 ? ValueLattice(R.Val.getInt().getExtValue())
163 : ValueLattice::top();
164 } else {
165 // An unitialized variable holds *some* value, but we don't know what it
166 // is (it is implementation defined), so we set it to top.
167 Vars[Var] = ValueLattice::top();
168 }
169 } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
170 const auto *E = Nodes.getNodeAs<clang::Expr>(kRHS);
171 assert(E != nullptr);
172
173 Expr::EvalResult R;
174 Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
175 ? ValueLattice(R.Val.getInt().getExtValue())
176 : ValueLattice::top();
177 } else if (Nodes.getNodeAs<clang::Expr>(kAssignment)) {
178 // Any assignment involving the expression itself resets the variable to
179 // "unknown". A more advanced analysis could try to evaluate the compound
180 // assignment. For example, `x += 0` need not invalidate `x`.
181 Vars[Var] = ValueLattice::top();
182 }
183 }
184 };
185
186 using ::testing::IsEmpty;
187 using ::testing::Pair;
188 using ::testing::UnorderedElementsAre;
189
190 MATCHER_P(Var, name,
191 (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +
192 name + "`")
193 .str()) {
194 return arg->getName() == name;
195 }
196
197 MATCHER_P(HasConstantVal, v, "") { return arg.Value && *arg.Value == v; }
198
199 MATCHER(Varies, "") { return arg == arg.top(); }
200
201 MATCHER_P(HoldsCPLattice, m,
202 ((negation ? "doesn't hold" : "holds") +
203 llvm::StringRef(" a lattice element that ") +
204 ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
205 .str()) {
206 return ExplainMatchResult(m, arg.Lattice, result_listener);
207 }
208
209 template <typename Matcher>
RunDataflow(llvm::StringRef Code,Matcher Expectations)210 void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
211 ASSERT_THAT_ERROR(
212 test::checkDataflow<ConstantPropagationAnalysis>(
213 Code, "fun",
214 [](ASTContext &C, Environment &) {
215 return ConstantPropagationAnalysis(C);
216 },
217 [&Expectations](
218 llvm::ArrayRef<std::pair<
219 std::string,
220 DataflowAnalysisState<ConstantPropagationAnalysis::Lattice>>>
221 Results,
222 ASTContext &) { EXPECT_THAT(Results, Expectations); },
223 {"-fsyntax-only", "-std=c++17"}),
224 llvm::Succeeded());
225 }
226
TEST(MultiVarConstantPropagationTest,JustInit)227 TEST(MultiVarConstantPropagationTest, JustInit) {
228 std::string Code = R"(
229 void fun() {
230 int target = 1;
231 // [[p]]
232 }
233 )";
234 RunDataflow(Code, UnorderedElementsAre(
235 Pair("p", HoldsCPLattice(UnorderedElementsAre(Pair(
236 Var("target"), HasConstantVal(1)))))));
237 }
238
TEST(MultiVarConstantPropagationTest,Assignment)239 TEST(MultiVarConstantPropagationTest, Assignment) {
240 std::string Code = R"(
241 void fun() {
242 int target = 1;
243 // [[p1]]
244 target = 2;
245 // [[p2]]
246 }
247 )";
248 RunDataflow(Code, UnorderedElementsAre(
249 Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
250 Var("target"), HasConstantVal(1))))),
251 Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
252 Var("target"), HasConstantVal(2)))))));
253 }
254
TEST(MultiVarConstantPropagationTest,AssignmentCall)255 TEST(MultiVarConstantPropagationTest, AssignmentCall) {
256 std::string Code = R"(
257 int g();
258 void fun() {
259 int target;
260 target = g();
261 // [[p]]
262 }
263 )";
264 RunDataflow(Code, UnorderedElementsAre(
265 Pair("p", HoldsCPLattice(UnorderedElementsAre(
266 Pair(Var("target"), Varies()))))));
267 }
268
TEST(MultiVarConstantPropagationTest,AssignmentBinOp)269 TEST(MultiVarConstantPropagationTest, AssignmentBinOp) {
270 std::string Code = R"(
271 void fun() {
272 int target;
273 target = 2 + 3;
274 // [[p]]
275 }
276 )";
277 RunDataflow(Code, UnorderedElementsAre(
278 Pair("p", HoldsCPLattice(UnorderedElementsAre(Pair(
279 Var("target"), HasConstantVal(5)))))));
280 }
281
TEST(MultiVarConstantPropagationTest,PlusAssignment)282 TEST(MultiVarConstantPropagationTest, PlusAssignment) {
283 std::string Code = R"(
284 void fun() {
285 int target = 1;
286 // [[p1]]
287 target += 2;
288 // [[p2]]
289 }
290 )";
291 RunDataflow(Code, UnorderedElementsAre(
292 Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
293 Var("target"), HasConstantVal(1))))),
294 Pair("p2", HoldsCPLattice(UnorderedElementsAre(
295 Pair(Var("target"), Varies()))))));
296 }
297
TEST(MultiVarConstantPropagationTest,SameAssignmentInBranches)298 TEST(MultiVarConstantPropagationTest, SameAssignmentInBranches) {
299 std::string Code = R"cc(
300 void fun(bool b) {
301 int target;
302 // [[p1]]
303 if (b) {
304 target = 2;
305 // [[pT]]
306 } else {
307 target = 2;
308 // [[pF]]
309 }
310 (void)0;
311 // [[p2]]
312 }
313 )cc";
314 RunDataflow(Code,
315 UnorderedElementsAre(
316 Pair("p1", HoldsCPLattice(UnorderedElementsAre(
317 Pair(Var("target"), Varies())))),
318 Pair("pT", HoldsCPLattice(UnorderedElementsAre(
319 Pair(Var("target"), HasConstantVal(2))))),
320 Pair("pF", HoldsCPLattice(UnorderedElementsAre(
321 Pair(Var("target"), HasConstantVal(2))))),
322 Pair("p2", HoldsCPLattice(UnorderedElementsAre(
323 Pair(Var("target"), HasConstantVal(2)))))));
324 }
325
326 // Verifies that the analysis tracks multiple variables simultaneously.
TEST(MultiVarConstantPropagationTest,TwoVariables)327 TEST(MultiVarConstantPropagationTest, TwoVariables) {
328 std::string Code = R"(
329 void fun() {
330 int target = 1;
331 // [[p1]]
332 int other = 2;
333 // [[p2]]
334 target = 3;
335 // [[p3]]
336 }
337 )";
338 RunDataflow(Code,
339 UnorderedElementsAre(
340 Pair("p1", HoldsCPLattice(UnorderedElementsAre(
341 Pair(Var("target"), HasConstantVal(1))))),
342 Pair("p2", HoldsCPLattice(UnorderedElementsAre(
343 Pair(Var("target"), HasConstantVal(1)),
344 Pair(Var("other"), HasConstantVal(2))))),
345 Pair("p3", HoldsCPLattice(UnorderedElementsAre(
346 Pair(Var("target"), HasConstantVal(3)),
347 Pair(Var("other"), HasConstantVal(2)))))));
348 }
349
TEST(MultiVarConstantPropagationTest,TwoVariablesInBranches)350 TEST(MultiVarConstantPropagationTest, TwoVariablesInBranches) {
351 std::string Code = R"cc(
352 void fun(bool b) {
353 int target;
354 int other;
355 // [[p1]]
356 if (b) {
357 target = 2;
358 // [[pT]]
359 } else {
360 other = 3;
361 // [[pF]]
362 }
363 (void)0;
364 // [[p2]]
365 }
366 )cc";
367 RunDataflow(Code, UnorderedElementsAre(
368 Pair("p1", HoldsCPLattice(UnorderedElementsAre(
369 Pair(Var("target"), Varies()),
370 Pair(Var("other"), Varies())))),
371 Pair("pT", HoldsCPLattice(UnorderedElementsAre(
372 Pair(Var("target"), HasConstantVal(2)),
373 Pair(Var("other"), Varies())))),
374 Pair("pF", HoldsCPLattice(UnorderedElementsAre(
375 Pair(Var("other"), HasConstantVal(3)),
376 Pair(Var("target"), Varies())))),
377 Pair("p2", HoldsCPLattice(UnorderedElementsAre(
378 Pair(Var("target"), Varies()),
379 Pair(Var("other"), Varies()))))));
380 }
381
TEST(MultiVarConstantPropagationTest,SameAssignmentInBranch)382 TEST(MultiVarConstantPropagationTest, SameAssignmentInBranch) {
383 std::string Code = R"cc(
384 void fun(bool b) {
385 int target = 1;
386 // [[p1]]
387 if (b) {
388 target = 1;
389 }
390 (void)0;
391 // [[p2]]
392 }
393 )cc";
394 RunDataflow(Code, UnorderedElementsAre(
395 Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
396 Var("target"), HasConstantVal(1))))),
397 Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
398 Var("target"), HasConstantVal(1)))))));
399 }
400
TEST(MultiVarConstantPropagationTest,NewVarInBranch)401 TEST(MultiVarConstantPropagationTest, NewVarInBranch) {
402 std::string Code = R"cc(
403 void fun(bool b) {
404 if (b) {
405 int target;
406 // [[p1]]
407 target = 1;
408 // [[p2]]
409 } else {
410 int target;
411 // [[p3]]
412 target = 1;
413 // [[p4]]
414 }
415 }
416 )cc";
417 RunDataflow(Code, UnorderedElementsAre(
418 Pair("p1", HoldsCPLattice(UnorderedElementsAre(
419 Pair(Var("target"), Varies())))),
420 Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
421 Var("target"), HasConstantVal(1))))),
422 Pair("p3", HoldsCPLattice(UnorderedElementsAre(
423 Pair(Var("target"), Varies())))),
424 Pair("p4", HoldsCPLattice(UnorderedElementsAre(Pair(
425 Var("target"), HasConstantVal(1)))))));
426 }
427
TEST(MultiVarConstantPropagationTest,DifferentAssignmentInBranches)428 TEST(MultiVarConstantPropagationTest, DifferentAssignmentInBranches) {
429 std::string Code = R"cc(
430 void fun(bool b) {
431 int target;
432 // [[p1]]
433 if (b) {
434 target = 1;
435 // [[pT]]
436 } else {
437 target = 2;
438 // [[pF]]
439 }
440 (void)0;
441 // [[p2]]
442 }
443 )cc";
444 RunDataflow(Code, UnorderedElementsAre(
445 Pair("p1", HoldsCPLattice(UnorderedElementsAre(
446 Pair(Var("target"), Varies())))),
447 Pair("pT", HoldsCPLattice(UnorderedElementsAre(Pair(
448 Var("target"), HasConstantVal(1))))),
449 Pair("pF", HoldsCPLattice(UnorderedElementsAre(Pair(
450 Var("target"), HasConstantVal(2))))),
451 Pair("p2", HoldsCPLattice(UnorderedElementsAre(
452 Pair(Var("target"), Varies()))))));
453 }
454
TEST(MultiVarConstantPropagationTest,DifferentAssignmentInBranch)455 TEST(MultiVarConstantPropagationTest, DifferentAssignmentInBranch) {
456 std::string Code = R"cc(
457 void fun(bool b) {
458 int target = 1;
459 // [[p1]]
460 if (b) {
461 target = 3;
462 }
463 (void)0;
464 // [[p2]]
465 }
466 )cc";
467 RunDataflow(Code, UnorderedElementsAre(
468 Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
469 Var("target"), HasConstantVal(1))))),
470 Pair("p2", HoldsCPLattice(UnorderedElementsAre(
471 Pair(Var("target"), Varies()))))));
472 }
473
474 } // namespace
475 } // namespace dataflow
476 } // namespace clang
477