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