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