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 "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, "") {
175   return arg.Data.hasValue() && arg.Data->Value == v;
176 }
177 
178 MATCHER(IsUnknown, "") { return arg == arg.bottom(); }
179 MATCHER(Varies, "") { return arg == arg.top(); }
180 
181 MATCHER_P(HoldsCPLattice, m,
182           ((negation ? "doesn't hold" : "holds") +
183            llvm::StringRef(" a lattice element that ") +
184            ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
185               .str()) {
186   return ExplainMatchResult(m, arg.Lattice, result_listener);
187 }
188 
189 class ConstantPropagationTest : public ::testing::Test {
190 protected:
191   template <typename Matcher>
192   void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
193     ASSERT_THAT_ERROR(
194         test::checkDataflow<ConstantPropagationAnalysis>(
195             Code, "fun",
196             [](ASTContext &C, Environment &) {
197               return ConstantPropagationAnalysis(C);
198             },
199             [&Expectations](
200                 llvm::ArrayRef<std::pair<
201                     std::string, DataflowAnalysisState<
202                                      ConstantPropagationAnalysis::Lattice>>>
203                     Results,
204                 ASTContext &) { EXPECT_THAT(Results, Expectations); },
205             {"-fsyntax-only", "-std=c++17"}),
206         llvm::Succeeded());
207   }
208 };
209 
210 TEST_F(ConstantPropagationTest, JustInit) {
211   std::string Code = R"(
212     void fun() {
213       int target = 1;
214       // [[p]]
215     }
216   )";
217   RunDataflow(
218       Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(1)))));
219 }
220 
221 // Verifies that the analysis tracks the last variable seen.
222 TEST_F(ConstantPropagationTest, TwoVariables) {
223   std::string Code = R"(
224     void fun() {
225       int target = 1;
226       // [[p1]]
227       int other = 2;
228       // [[p2]]
229       target = 3;
230       // [[p3]]
231     }
232   )";
233   RunDataflow(Code, UnorderedElementsAre(
234                         Pair("p1", HoldsCPLattice(HasConstantVal(1))),
235                         Pair("p2", HoldsCPLattice(HasConstantVal(2))),
236                         Pair("p3", HoldsCPLattice(HasConstantVal(3)))));
237 }
238 
239 TEST_F(ConstantPropagationTest, 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(HasConstantVal(1))),
250                         Pair("p2", HoldsCPLattice(HasConstantVal(2)))));
251 }
252 
253 TEST_F(ConstantPropagationTest, AssignmentCall) {
254   std::string Code = R"(
255     int g();
256     void fun() {
257       int target;
258       target = g();
259       // [[p]]
260     }
261   )";
262   RunDataflow(Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(Varies()))));
263 }
264 
265 TEST_F(ConstantPropagationTest, AssignmentBinOp) {
266   std::string Code = R"(
267     void fun() {
268       int target;
269       target = 2 + 3;
270       // [[p]]
271     }
272   )";
273   RunDataflow(
274       Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(5)))));
275 }
276 
277 TEST_F(ConstantPropagationTest, PlusAssignment) {
278   std::string Code = R"(
279     void fun() {
280       int target = 1;
281       // [[p1]]
282       target += 2;
283       // [[p2]]
284     }
285   )";
286   RunDataflow(
287       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))),
288                                  Pair("p2", HoldsCPLattice(Varies()))));
289 }
290 
291 TEST_F(ConstantPropagationTest, SameAssignmentInBranches) {
292   std::string Code = R"cc(
293     void fun(bool b) {
294       int target;
295       // [[p1]]
296       if (b) {
297         target = 2;
298         // [[pT]]
299       } else {
300         target = 2;
301         // [[pF]]
302       }
303       (void)0;
304       // [[p2]]
305     }
306   )cc";
307   RunDataflow(Code, UnorderedElementsAre(
308                         Pair("p1", HoldsCPLattice(IsUnknown())),
309                         Pair("pT", HoldsCPLattice(HasConstantVal(2))),
310                         Pair("pF", HoldsCPLattice(HasConstantVal(2))),
311                         Pair("p2", HoldsCPLattice(HasConstantVal(2)))));
312 }
313 
314 TEST_F(ConstantPropagationTest, SameAssignmentInBranch) {
315   std::string Code = R"cc(
316     void fun(bool b) {
317       int target = 1;
318       // [[p1]]
319       if (b) {
320         target = 1;
321       }
322       (void)0;
323       // [[p2]]
324     }
325   )cc";
326   RunDataflow(Code, UnorderedElementsAre(
327                         Pair("p1", HoldsCPLattice(HasConstantVal(1))),
328                         Pair("p2", HoldsCPLattice(HasConstantVal(1)))));
329 }
330 
331 TEST_F(ConstantPropagationTest, NewVarInBranch) {
332   std::string Code = R"cc(
333     void fun(bool b) {
334       if (b) {
335         int target;
336         // [[p1]]
337         target = 1;
338         // [[p2]]
339       } else {
340         int target;
341         // [[p3]]
342         target = 1;
343         // [[p4]]
344       }
345     }
346   )cc";
347   RunDataflow(Code, UnorderedElementsAre(
348                         Pair("p1", HoldsCPLattice(IsUnknown())),
349                         Pair("p2", HoldsCPLattice(HasConstantVal(1))),
350                         Pair("p3", HoldsCPLattice(IsUnknown())),
351                         Pair("p4", HoldsCPLattice(HasConstantVal(1)))));
352 }
353 
354 TEST_F(ConstantPropagationTest, DifferentAssignmentInBranches) {
355   std::string Code = R"cc(
356     void fun(bool b) {
357       int target;
358       // [[p1]]
359       if (b) {
360         target = 1;
361         // [[pT]]
362       } else {
363         target = 2;
364         // [[pF]]
365       }
366       (void)0;
367       // [[p2]]
368     }
369   )cc";
370   RunDataflow(
371       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(IsUnknown())),
372                                  Pair("pT", HoldsCPLattice(HasConstantVal(1))),
373                                  Pair("pF", HoldsCPLattice(HasConstantVal(2))),
374                                  Pair("p2", HoldsCPLattice(Varies()))));
375 }
376 
377 TEST_F(ConstantPropagationTest, DifferentAssignmentInBranch) {
378   std::string Code = R"cc(
379     void fun(bool b) {
380       int target = 1;
381       // [[p1]]
382       if (b) {
383         target = 3;
384       }
385       (void)0;
386       // [[p2]]
387     }
388   )cc";
389   RunDataflow(
390       Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))),
391                                  Pair("p2", HoldsCPLattice(Varies()))));
392 }
393 
394 } // namespace
395 } // namespace dataflow
396 } // namespace clang
397