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   ConstantPropagationLattice transfer(const Stmt *S,
125                                       const 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 Element;
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       if (E->EvaluateAsInt(R, Context) && R.Val.isInt())
149         return ConstantPropagationLattice{
150             {{Var, R.Val.getInt().getExtValue()}}};
151       return ConstantPropagationLattice::top();
152     }
153 
154     if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
155       const auto *RHS = Nodes.getNodeAs<clang::Expr>(kRHS);
156       assert(RHS != nullptr);
157 
158       Expr::EvalResult R;
159       if (RHS->EvaluateAsInt(R, Context) && R.Val.isInt())
160         return ConstantPropagationLattice{
161             {{Var, R.Val.getInt().getExtValue()}}};
162       return ConstantPropagationLattice::top();
163     }
164 
165     // Any assignment involving the expression itself resets the variable to
166     // "unknown". A more advanced analysis could try to evaluate the compound
167     // assignment. For example, `x += 0` need not invalidate `x`.
168     if (Nodes.getNodeAs<clang::Expr>(kAssignment))
169       return ConstantPropagationLattice::top();
170 
171     llvm_unreachable("expected at least one bound identifier");
172   }
173 };
174 
175 using ::testing::Pair;
176 using ::testing::UnorderedElementsAre;
177 
178 MATCHER_P(HasConstantVal, v, "") {
179   return arg.Data.hasValue() && arg.Data->Value == v;
180 }
181 
182 MATCHER(IsUnknown, "") { return arg == arg.bottom(); }
183 MATCHER(Varies, "") { return arg == arg.top(); }
184 
185 MATCHER_P(HoldsCPLattice, m,
186           ((negation ? "doesn't hold" : "holds") +
187            llvm::StringRef(" a lattice element that ") +
188            ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
189               .str()) {
190   return ExplainMatchResult(m, arg.Lattice, result_listener);
191 }
192 
193 class ConstantPropagationTest : public ::testing::Test {
194 protected:
195   template <typename Matcher>
196   void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
197     test::checkDataflow<ConstantPropagationAnalysis>(
198         Code, "fun",
199         [](ASTContext &C, Environment &) {
200           return ConstantPropagationAnalysis(C);
201         },
202         [&Expectations](
203             llvm::ArrayRef<std::pair<
204                 std::string,
205                 DataflowAnalysisState<ConstantPropagationAnalysis::Lattice>>>
206                 Results,
207             ASTContext &) { EXPECT_THAT(Results, Expectations); },
208         {"-fsyntax-only", "-std=c++17"});
209   }
210 };
211 
212 TEST_F(ConstantPropagationTest, JustInit) {
213   std::string Code = R"(
214     void fun() {
215       int target = 1;
216       // [[p]]
217     }
218   )";
219   RunDataflow(
220       Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(1)))));
221 }
222 
223 // Verifies that the analysis tracks the last variable seen.
224 TEST_F(ConstantPropagationTest, TwoVariables) {
225   std::string Code = R"(
226     void fun() {
227       int target = 1;
228       // [[p1]]
229       int other = 2;
230       // [[p2]]
231       target = 3;
232       // [[p3]]
233     }
234   )";
235   RunDataflow(Code, UnorderedElementsAre(
236                         Pair("p1", HoldsCPLattice(HasConstantVal(1))),
237                         Pair("p2", HoldsCPLattice(HasConstantVal(2))),
238                         Pair("p3", HoldsCPLattice(HasConstantVal(3)))));
239 }
240 
241 TEST_F(ConstantPropagationTest, Assignment) {
242   std::string Code = R"(
243     void fun() {
244       int target = 1;
245       // [[p1]]
246       target = 2;
247       // [[p2]]
248     }
249   )";
250   RunDataflow(Code, UnorderedElementsAre(
251                         Pair("p1", HoldsCPLattice(HasConstantVal(1))),
252                         Pair("p2", HoldsCPLattice(HasConstantVal(2)))));
253 }
254 
255 TEST_F(ConstantPropagationTest, 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(Pair("p", HoldsCPLattice(Varies()))));
265 }
266 
267 TEST_F(ConstantPropagationTest, AssignmentBinOp) {
268   std::string Code = R"(
269     void fun() {
270       int target;
271       target = 2 + 3;
272       // [[p]]
273     }
274   )";
275   RunDataflow(
276       Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(5)))));
277 }
278 
279 TEST_F(ConstantPropagationTest, PlusAssignment) {
280   std::string Code = R"(
281     void fun() {
282       int target = 1;
283       // [[p1]]
284       target += 2;
285       // [[p2]]
286     }
287   )";
288   RunDataflow(
289       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))),
290                                  Pair("p2", HoldsCPLattice(Varies()))));
291 }
292 
293 TEST_F(ConstantPropagationTest, SameAssignmentInBranches) {
294   std::string Code = R"cc(
295     void fun(bool b) {
296       int target;
297       // [[p1]]
298       if (b) {
299         target = 2;
300         // [[pT]]
301       } else {
302         target = 2;
303         // [[pF]]
304       }
305       (void)0;
306       // [[p2]]
307     }
308   )cc";
309   RunDataflow(Code, UnorderedElementsAre(
310                         Pair("p1", HoldsCPLattice(IsUnknown())),
311                         Pair("pT", HoldsCPLattice(HasConstantVal(2))),
312                         Pair("pF", HoldsCPLattice(HasConstantVal(2))),
313                         Pair("p2", HoldsCPLattice(HasConstantVal(2)))));
314 }
315 
316 TEST_F(ConstantPropagationTest, SameAssignmentInBranch) {
317   std::string Code = R"cc(
318     void fun(bool b) {
319       int target = 1;
320       // [[p1]]
321       if (b) {
322         target = 1;
323       }
324       (void)0;
325       // [[p2]]
326     }
327   )cc";
328   RunDataflow(Code, UnorderedElementsAre(
329                         Pair("p1", HoldsCPLattice(HasConstantVal(1))),
330                         Pair("p2", HoldsCPLattice(HasConstantVal(1)))));
331 }
332 
333 TEST_F(ConstantPropagationTest, NewVarInBranch) {
334   std::string Code = R"cc(
335     void fun(bool b) {
336       if (b) {
337         int target;
338         // [[p1]]
339         target = 1;
340         // [[p2]]
341       } else {
342         int target;
343         // [[p3]]
344         target = 1;
345         // [[p4]]
346       }
347     }
348   )cc";
349   RunDataflow(Code, UnorderedElementsAre(
350                         Pair("p1", HoldsCPLattice(IsUnknown())),
351                         Pair("p2", HoldsCPLattice(HasConstantVal(1))),
352                         Pair("p3", HoldsCPLattice(IsUnknown())),
353                         Pair("p4", HoldsCPLattice(HasConstantVal(1)))));
354 }
355 
356 TEST_F(ConstantPropagationTest, DifferentAssignmentInBranches) {
357   std::string Code = R"cc(
358     void fun(bool b) {
359       int target;
360       // [[p1]]
361       if (b) {
362         target = 1;
363         // [[pT]]
364       } else {
365         target = 2;
366         // [[pF]]
367       }
368       (void)0;
369       // [[p2]]
370     }
371   )cc";
372   RunDataflow(
373       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(IsUnknown())),
374                                  Pair("pT", HoldsCPLattice(HasConstantVal(1))),
375                                  Pair("pF", HoldsCPLattice(HasConstantVal(2))),
376                                  Pair("p2", HoldsCPLattice(Varies()))));
377 }
378 
379 TEST_F(ConstantPropagationTest, DifferentAssignmentInBranch) {
380   std::string Code = R"cc(
381     void fun(bool b) {
382       int target = 1;
383       // [[p1]]
384       if (b) {
385         target = 3;
386       }
387       (void)0;
388       // [[p2]]
389     }
390   )cc";
391   RunDataflow(
392       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))),
393                                  Pair("p2", HoldsCPLattice(Varies()))));
394 }
395 
396 } // namespace
397 } // namespace dataflow
398 } // namespace clang
399