1 //===- unittests/Analysis/FlowSensitive/SingelVarConstantPropagation.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/FlowSensitive/DataflowAnalysis.h"
23 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
24 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
25 #include "clang/Tooling/Tooling.h"
26 #include "llvm/ADT/None.h"
27 #include "llvm/ADT/Optional.h"
28 #include "llvm/ADT/StringRef.h"
29 #include "llvm/ADT/Twine.h"
30 #include "llvm/Support/Error.h"
31 #include "llvm/Testing/Support/Annotations.h"
32 #include "gmock/gmock.h"
33 #include "gtest/gtest.h"
34 #include <cstdint>
35 #include <memory>
36 #include <ostream>
37 #include <string>
38 #include <utility>
39 
40 namespace clang {
41 namespace dataflow {
42 namespace {
43 using namespace ast_matchers;
44 
45 // A semi-lattice for dataflow analysis that tracks the value of a single
46 // integer variable. If it can be identified with a single (constant) value,
47 // then that value is stored.
48 struct ConstantPropagationLattice {
49   // A null `Var` represents "top": either more than one value is possible or
50   // more than one variable was encountered. Otherwise, `Data` indicates that
51   // `Var` has the given `Value` at the program point with which this lattice
52   // element is associated, for all paths through the program.
53   struct VarValue {
54     const VarDecl *Var;
55     int64_t Value;
56 
57     friend bool operator==(VarValue Lhs, VarValue Rhs) {
58       return Lhs.Var == Rhs.Var && Lhs.Value == Rhs.Value;
59     }
60   };
61   // `None` is "bottom".
62   llvm::Optional<VarValue> Data;
63 
64   static constexpr ConstantPropagationLattice bottom() { return {llvm::None}; }
65   static constexpr ConstantPropagationLattice top() {
66     return {VarValue{nullptr, 0}};
67   }
68 
69   friend bool operator==(const ConstantPropagationLattice &Lhs,
70                          const ConstantPropagationLattice &Rhs) {
71     return Lhs.Data == Rhs.Data;
72   }
73 
74   LatticeJoinEffect join(const ConstantPropagationLattice &Other) {
75     if (*this == Other || Other == bottom() || *this == top())
76       return LatticeJoinEffect::Unchanged;
77 
78     if (*this == bottom()) {
79       *this = Other;
80       return LatticeJoinEffect::Changed;
81     }
82 
83     *this = top();
84     return LatticeJoinEffect::Changed;
85   }
86 };
87 
88 std::ostream &operator<<(std::ostream &OS,
89                          const ConstantPropagationLattice &L) {
90   if (L == L.bottom())
91     return OS << "None";
92   if (L == L.top())
93     return OS << "Any";
94   return OS << L.Data->Var->getName().str() << " = " << L.Data->Value;
95 }
96 
97 } // namespace
98 
99 static constexpr char kVar[] = "var";
100 static constexpr char kInit[] = "init";
101 static constexpr char kJustAssignment[] = "just-assignment";
102 static constexpr char kAssignment[] = "assignment";
103 static constexpr char kRHS[] = "rhs";
104 
105 static auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }
106 
107 namespace {
108 // N.B. This analysis is deliberately simplistic, leaving out many important
109 // details needed for a real analysis in production. Most notably, the transfer
110 // function does not account for the variable's address possibly escaping, which
111 // would invalidate the analysis.
112 class ConstantPropagationAnalysis
113     : public DataflowAnalysis<ConstantPropagationAnalysis,
114                               ConstantPropagationLattice> {
115 public:
116   explicit ConstantPropagationAnalysis(ASTContext &Context)
117       : DataflowAnalysis<ConstantPropagationAnalysis,
118                          ConstantPropagationLattice>(Context) {}
119 
120   static ConstantPropagationLattice initialElement() {
121     return ConstantPropagationLattice::bottom();
122   }
123 
124   void transfer(const Stmt *S, ConstantPropagationLattice &Element,
125                 Environment &Env) {
126     auto matcher = stmt(
127         anyOf(declStmt(hasSingleDecl(varDecl(hasType(isInteger()),
128                                              hasInitializer(expr().bind(kInit)))
129                                          .bind(kVar))),
130               binaryOperator(hasOperatorName("="), hasLHS(refToVar()),
131                              hasRHS(expr().bind(kRHS)))
132                   .bind(kJustAssignment),
133               binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))
134                   .bind(kAssignment)));
135 
136     ASTContext &Context = getASTContext();
137     auto Results = match(matcher, *S, Context);
138     if (Results.empty())
139       return;
140     const BoundNodes &Nodes = Results[0];
141 
142     const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
143     assert(Var != nullptr);
144 
145     if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
146       Expr::EvalResult R;
147       Element =
148           (E->EvaluateAsInt(R, Context) && R.Val.isInt())
149               ? ConstantPropagationLattice{{{Var,
150                                              R.Val.getInt().getExtValue()}}}
151               : ConstantPropagationLattice::top();
152     } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
153       const auto *RHS = Nodes.getNodeAs<clang::Expr>(kRHS);
154       assert(RHS != nullptr);
155 
156       Expr::EvalResult R;
157       Element =
158           (RHS->EvaluateAsInt(R, Context) && R.Val.isInt())
159               ? ConstantPropagationLattice{{{Var,
160                                              R.Val.getInt().getExtValue()}}}
161               : ConstantPropagationLattice::top();
162     } else if (Nodes.getNodeAs<clang::Expr>(kAssignment))
163       // Any assignment involving the expression itself resets the variable to
164       // "unknown". A more advanced analysis could try to evaluate the compound
165       // assignment. For example, `x += 0` need not invalidate `x`.
166       Element = ConstantPropagationLattice::top();
167   }
168 };
169 
170 using ::testing::Pair;
171 using ::testing::UnorderedElementsAre;
172 
173 MATCHER_P(HasConstantVal, v, "") {
174   return arg.Data.hasValue() && arg.Data->Value == v;
175 }
176 
177 MATCHER(IsUnknown, "") { return arg == arg.bottom(); }
178 MATCHER(Varies, "") { return arg == arg.top(); }
179 
180 MATCHER_P(HoldsCPLattice, m,
181           ((negation ? "doesn't hold" : "holds") +
182            llvm::StringRef(" a lattice element that ") +
183            ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
184               .str()) {
185   return ExplainMatchResult(m, arg.Lattice, result_listener);
186 }
187 
188 class ConstantPropagationTest : public ::testing::Test {
189 protected:
190   template <typename Matcher>
191   void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
192     test::checkDataflow<ConstantPropagationAnalysis>(
193         Code, "fun",
194         [](ASTContext &C, Environment &) {
195           return ConstantPropagationAnalysis(C);
196         },
197         [&Expectations](
198             llvm::ArrayRef<std::pair<
199                 std::string,
200                 DataflowAnalysisState<ConstantPropagationAnalysis::Lattice>>>
201                 Results,
202             ASTContext &) { EXPECT_THAT(Results, Expectations); },
203         {"-fsyntax-only", "-std=c++17"});
204   }
205 };
206 
207 TEST_F(ConstantPropagationTest, JustInit) {
208   std::string Code = R"(
209     void fun() {
210       int target = 1;
211       // [[p]]
212     }
213   )";
214   RunDataflow(
215       Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(1)))));
216 }
217 
218 // Verifies that the analysis tracks the last variable seen.
219 TEST_F(ConstantPropagationTest, TwoVariables) {
220   std::string Code = R"(
221     void fun() {
222       int target = 1;
223       // [[p1]]
224       int other = 2;
225       // [[p2]]
226       target = 3;
227       // [[p3]]
228     }
229   )";
230   RunDataflow(Code, UnorderedElementsAre(
231                         Pair("p1", HoldsCPLattice(HasConstantVal(1))),
232                         Pair("p2", HoldsCPLattice(HasConstantVal(2))),
233                         Pair("p3", HoldsCPLattice(HasConstantVal(3)))));
234 }
235 
236 TEST_F(ConstantPropagationTest, Assignment) {
237   std::string Code = R"(
238     void fun() {
239       int target = 1;
240       // [[p1]]
241       target = 2;
242       // [[p2]]
243     }
244   )";
245   RunDataflow(Code, UnorderedElementsAre(
246                         Pair("p1", HoldsCPLattice(HasConstantVal(1))),
247                         Pair("p2", HoldsCPLattice(HasConstantVal(2)))));
248 }
249 
250 TEST_F(ConstantPropagationTest, AssignmentCall) {
251   std::string Code = R"(
252     int g();
253     void fun() {
254       int target;
255       target = g();
256       // [[p]]
257     }
258   )";
259   RunDataflow(Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(Varies()))));
260 }
261 
262 TEST_F(ConstantPropagationTest, AssignmentBinOp) {
263   std::string Code = R"(
264     void fun() {
265       int target;
266       target = 2 + 3;
267       // [[p]]
268     }
269   )";
270   RunDataflow(
271       Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(5)))));
272 }
273 
274 TEST_F(ConstantPropagationTest, PlusAssignment) {
275   std::string Code = R"(
276     void fun() {
277       int target = 1;
278       // [[p1]]
279       target += 2;
280       // [[p2]]
281     }
282   )";
283   RunDataflow(
284       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))),
285                                  Pair("p2", HoldsCPLattice(Varies()))));
286 }
287 
288 TEST_F(ConstantPropagationTest, SameAssignmentInBranches) {
289   std::string Code = R"cc(
290     void fun(bool b) {
291       int target;
292       // [[p1]]
293       if (b) {
294         target = 2;
295         // [[pT]]
296       } else {
297         target = 2;
298         // [[pF]]
299       }
300       (void)0;
301       // [[p2]]
302     }
303   )cc";
304   RunDataflow(Code, UnorderedElementsAre(
305                         Pair("p1", HoldsCPLattice(IsUnknown())),
306                         Pair("pT", HoldsCPLattice(HasConstantVal(2))),
307                         Pair("pF", HoldsCPLattice(HasConstantVal(2))),
308                         Pair("p2", HoldsCPLattice(HasConstantVal(2)))));
309 }
310 
311 TEST_F(ConstantPropagationTest, SameAssignmentInBranch) {
312   std::string Code = R"cc(
313     void fun(bool b) {
314       int target = 1;
315       // [[p1]]
316       if (b) {
317         target = 1;
318       }
319       (void)0;
320       // [[p2]]
321     }
322   )cc";
323   RunDataflow(Code, UnorderedElementsAre(
324                         Pair("p1", HoldsCPLattice(HasConstantVal(1))),
325                         Pair("p2", HoldsCPLattice(HasConstantVal(1)))));
326 }
327 
328 TEST_F(ConstantPropagationTest, NewVarInBranch) {
329   std::string Code = R"cc(
330     void fun(bool b) {
331       if (b) {
332         int target;
333         // [[p1]]
334         target = 1;
335         // [[p2]]
336       } else {
337         int target;
338         // [[p3]]
339         target = 1;
340         // [[p4]]
341       }
342     }
343   )cc";
344   RunDataflow(Code, UnorderedElementsAre(
345                         Pair("p1", HoldsCPLattice(IsUnknown())),
346                         Pair("p2", HoldsCPLattice(HasConstantVal(1))),
347                         Pair("p3", HoldsCPLattice(IsUnknown())),
348                         Pair("p4", HoldsCPLattice(HasConstantVal(1)))));
349 }
350 
351 TEST_F(ConstantPropagationTest, DifferentAssignmentInBranches) {
352   std::string Code = R"cc(
353     void fun(bool b) {
354       int target;
355       // [[p1]]
356       if (b) {
357         target = 1;
358         // [[pT]]
359       } else {
360         target = 2;
361         // [[pF]]
362       }
363       (void)0;
364       // [[p2]]
365     }
366   )cc";
367   RunDataflow(
368       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(IsUnknown())),
369                                  Pair("pT", HoldsCPLattice(HasConstantVal(1))),
370                                  Pair("pF", HoldsCPLattice(HasConstantVal(2))),
371                                  Pair("p2", HoldsCPLattice(Varies()))));
372 }
373 
374 TEST_F(ConstantPropagationTest, DifferentAssignmentInBranch) {
375   std::string Code = R"cc(
376     void fun(bool b) {
377       int target = 1;
378       // [[p1]]
379       if (b) {
380         target = 3;
381       }
382       (void)0;
383       // [[p2]]
384     }
385   )cc";
386   RunDataflow(
387       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))),
388                                  Pair("p2", HoldsCPLattice(Varies()))));
389 }
390 
391 } // namespace
392 } // namespace dataflow
393 } // namespace clang
394