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 tracks all
11 //  variables in the scope, but lacks escape analysis.
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/Analysis/FlowSensitive/MapLattice.h"
26 #include "clang/Tooling/Tooling.h"
27 #include "llvm/ADT/None.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/ADT/StringRef.h"
30 #include "llvm/ADT/Twine.h"
31 #include "llvm/Support/Error.h"
32 #include "llvm/Testing/Support/Annotations.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 // Models the value of an expression at a program point, for all paths through
47 // the program.
48 struct ValueLattice {
49   // FIXME: change the internal representation to use a `std::variant`, once
50   // clang admits C++17 constructs.
51   enum class ValueState : bool {
52     Undefined,
53     Defined,
54   };
55   // `State` determines the meaning of the lattice when `Value` is `None`:
56   //  * `Undefined` -> bottom,
57   //  * `Defined` -> top.
58   ValueState State;
59 
60   // When `None`, the lattice is either at top or bottom, based on `State`.
61   llvm::Optional<int64_t> Value;
62 
63   constexpr ValueLattice() : State(ValueState::Undefined), Value(llvm::None) {}
64   constexpr ValueLattice(int64_t V) : State(ValueState::Defined), Value(V) {}
65   constexpr ValueLattice(ValueState S) : State(S), Value(llvm::None) {}
66 
67   static constexpr ValueLattice bottom() {
68     return ValueLattice(ValueState::Undefined);
69   }
70   static constexpr ValueLattice top() {
71     return ValueLattice(ValueState::Defined);
72   }
73 
74   friend bool operator==(const ValueLattice &Lhs, const ValueLattice &Rhs) {
75     return Lhs.State == Rhs.State && Lhs.Value == Rhs.Value;
76   }
77   friend bool operator!=(const ValueLattice &Lhs, const ValueLattice &Rhs) {
78     return !(Lhs == Rhs);
79   }
80 
81   LatticeJoinEffect join(const ValueLattice &Other) {
82     if (*this == Other || Other == bottom() || *this == top())
83       return LatticeJoinEffect::Unchanged;
84 
85     if (*this == bottom()) {
86       *this = Other;
87       return LatticeJoinEffect::Changed;
88     }
89 
90     *this = top();
91     return LatticeJoinEffect::Changed;
92   }
93 };
94 
95 std::ostream &operator<<(std::ostream &OS, const ValueLattice &L) {
96   if (L.Value.hasValue())
97     return OS << *L.Value;
98   switch (L.State) {
99   case ValueLattice::ValueState::Undefined:
100     return OS << "None";
101   case ValueLattice::ValueState::Defined:
102     return OS << "Any";
103   }
104 }
105 
106 using ConstantPropagationLattice = VarMapLattice<ValueLattice>;
107 
108 constexpr char kDecl[] = "decl";
109 constexpr char kVar[] = "var";
110 constexpr char kInit[] = "init";
111 constexpr char kJustAssignment[] = "just-assignment";
112 constexpr char kAssignment[] = "assignment";
113 constexpr char kRHS[] = "rhs";
114 
115 auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }
116 
117 // N.B. This analysis is deliberately simplistic, leaving out many important
118 // details needed for a real analysis. Most notably, the transfer function does
119 // not account for the variable's address possibly escaping, which would
120 // invalidate the analysis. It also could be optimized to drop out-of-scope
121 // variables from the map.
122 class ConstantPropagationAnalysis
123     : public DataflowAnalysis<ConstantPropagationAnalysis,
124                               ConstantPropagationLattice> {
125 public:
126   explicit ConstantPropagationAnalysis(ASTContext &Context)
127       : DataflowAnalysis<ConstantPropagationAnalysis,
128                          ConstantPropagationLattice>(Context) {}
129 
130   static ConstantPropagationLattice initialElement() {
131     return ConstantPropagationLattice::bottom();
132   }
133 
134   ConstantPropagationLattice
135   transfer(const Stmt *S, ConstantPropagationLattice Vars, Environment &Env) {
136     auto matcher =
137         stmt(anyOf(declStmt(hasSingleDecl(
138                        varDecl(decl().bind(kVar), hasType(isInteger()),
139                                optionally(hasInitializer(expr().bind(kInit))))
140                            .bind(kDecl))),
141                    binaryOperator(hasOperatorName("="), hasLHS(refToVar()),
142                                   hasRHS(expr().bind(kRHS)))
143                        .bind(kJustAssignment),
144                    binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))
145                        .bind(kAssignment)));
146 
147     ASTContext &Context = getASTContext();
148     auto Results = match(matcher, *S, Context);
149     if (Results.empty())
150       return Vars;
151     const BoundNodes &Nodes = Results[0];
152 
153     const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
154     assert(Var != nullptr);
155 
156     if (Nodes.getNodeAs<clang::VarDecl>(kDecl) != nullptr) {
157       if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
158         Expr::EvalResult R;
159         Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
160                         ? ValueLattice(R.Val.getInt().getExtValue())
161                         : ValueLattice::top();
162       } else {
163         // An unitialized variable holds *some* value, but we don't know what it
164         // is (it is implementation defined), so we set it to top.
165         Vars[Var] = ValueLattice::top();
166       }
167       return Vars;
168     }
169 
170     if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
171       const auto *E = Nodes.getNodeAs<clang::Expr>(kRHS);
172       assert(E != nullptr);
173 
174       Expr::EvalResult R;
175       Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
176                       ? ValueLattice(R.Val.getInt().getExtValue())
177                       : ValueLattice::top();
178       return Vars;
179     }
180 
181     // Any assignment involving the expression itself resets the variable to
182     // "unknown". A more advanced analysis could try to evaluate the compound
183     // assignment. For example, `x += 0` need not invalidate `x`.
184     if (Nodes.getNodeAs<clang::Expr>(kAssignment)) {
185       Vars[Var] = ValueLattice::top();
186       return Vars;
187     }
188 
189     llvm_unreachable("expected at least one bound identifier");
190   }
191 };
192 
193 using ::testing::IsEmpty;
194 using ::testing::Pair;
195 using ::testing::UnorderedElementsAre;
196 
197 MATCHER_P(Var, name,
198           (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +
199            name + "`")
200               .str()) {
201   return arg->getName() == name;
202 }
203 
204 MATCHER_P(HasConstantVal, v, "") {
205   return arg.Value.hasValue() && *arg.Value == v;
206 }
207 
208 MATCHER(Varies, "") { return arg == arg.top(); }
209 
210 MATCHER_P(HoldsCPLattice, m,
211           ((negation ? "doesn't hold" : "holds") +
212            llvm::StringRef(" a lattice element that ") +
213            ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
214               .str()) {
215   return ExplainMatchResult(m, arg.Lattice, result_listener);
216 }
217 
218 class MultiVarConstantPropagationTest : public ::testing::Test {
219 protected:
220   template <typename Matcher>
221   void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
222     test::checkDataflow<ConstantPropagationAnalysis>(
223         Code, "fun",
224         [](ASTContext &C, Environment &) {
225           return ConstantPropagationAnalysis(C);
226         },
227         [&Expectations](
228             llvm::ArrayRef<std::pair<
229                 std::string,
230                 DataflowAnalysisState<ConstantPropagationAnalysis::Lattice>>>
231                 Results,
232             ASTContext &) { EXPECT_THAT(Results, Expectations); },
233         {"-fsyntax-only", "-std=c++17"});
234   }
235 };
236 
237 TEST_F(MultiVarConstantPropagationTest, JustInit) {
238   std::string Code = R"(
239     void fun() {
240       int target = 1;
241       // [[p]]
242     }
243   )";
244   RunDataflow(Code, UnorderedElementsAre(
245                         Pair("p", HoldsCPLattice(UnorderedElementsAre(Pair(
246                                       Var("target"), HasConstantVal(1)))))));
247 }
248 
249 TEST_F(MultiVarConstantPropagationTest, Assignment) {
250   std::string Code = R"(
251     void fun() {
252       int target = 1;
253       // [[p1]]
254       target = 2;
255       // [[p2]]
256     }
257   )";
258   RunDataflow(Code, UnorderedElementsAre(
259                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
260                                        Var("target"), HasConstantVal(1))))),
261                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
262                                        Var("target"), HasConstantVal(2)))))));
263 }
264 
265 TEST_F(MultiVarConstantPropagationTest, AssignmentCall) {
266   std::string Code = R"(
267     int g();
268     void fun() {
269       int target;
270       target = g();
271       // [[p]]
272     }
273   )";
274   RunDataflow(Code, UnorderedElementsAre(
275                         Pair("p", HoldsCPLattice(UnorderedElementsAre(
276                                       Pair(Var("target"), Varies()))))));
277 }
278 
279 TEST_F(MultiVarConstantPropagationTest, AssignmentBinOp) {
280   std::string Code = R"(
281     void fun() {
282       int target;
283       target = 2 + 3;
284       // [[p]]
285     }
286   )";
287   RunDataflow(Code, UnorderedElementsAre(
288                         Pair("p", HoldsCPLattice(UnorderedElementsAre(Pair(
289                                       Var("target"), HasConstantVal(5)))))));
290 }
291 
292 TEST_F(MultiVarConstantPropagationTest, PlusAssignment) {
293   std::string Code = R"(
294     void fun() {
295       int target = 1;
296       // [[p1]]
297       target += 2;
298       // [[p2]]
299     }
300   )";
301   RunDataflow(Code, UnorderedElementsAre(
302                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
303                                        Var("target"), HasConstantVal(1))))),
304                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(
305                                        Pair(Var("target"), Varies()))))));
306 }
307 
308 TEST_F(MultiVarConstantPropagationTest, SameAssignmentInBranches) {
309   std::string Code = R"cc(
310     void fun(bool b) {
311       int target;
312       // [[p1]]
313       if (b) {
314         target = 2;
315         // [[pT]]
316       } else {
317         target = 2;
318         // [[pF]]
319       }
320       (void)0;
321       // [[p2]]
322     }
323   )cc";
324   RunDataflow(Code,
325               UnorderedElementsAre(
326                   Pair("p1", HoldsCPLattice(UnorderedElementsAre(
327                                  Pair(Var("target"), Varies())))),
328                   Pair("pT", HoldsCPLattice(UnorderedElementsAre(
329                                  Pair(Var("target"), HasConstantVal(2))))),
330                   Pair("pF", HoldsCPLattice(UnorderedElementsAre(
331                                  Pair(Var("target"), HasConstantVal(2))))),
332                   Pair("p2", HoldsCPLattice(UnorderedElementsAre(
333                                  Pair(Var("target"), HasConstantVal(2)))))));
334 }
335 
336 // Verifies that the analysis tracks multiple variables simultaneously.
337 TEST_F(MultiVarConstantPropagationTest, TwoVariables) {
338   std::string Code = R"(
339     void fun() {
340       int target = 1;
341       // [[p1]]
342       int other = 2;
343       // [[p2]]
344       target = 3;
345       // [[p3]]
346     }
347   )";
348   RunDataflow(Code,
349               UnorderedElementsAre(
350                   Pair("p1", HoldsCPLattice(UnorderedElementsAre(
351                                  Pair(Var("target"), HasConstantVal(1))))),
352                   Pair("p2", HoldsCPLattice(UnorderedElementsAre(
353                                  Pair(Var("target"), HasConstantVal(1)),
354                                  Pair(Var("other"), HasConstantVal(2))))),
355                   Pair("p3", HoldsCPLattice(UnorderedElementsAre(
356                                  Pair(Var("target"), HasConstantVal(3)),
357                                  Pair(Var("other"), HasConstantVal(2)))))));
358 }
359 
360 TEST_F(MultiVarConstantPropagationTest, TwoVariablesInBranches) {
361   std::string Code = R"cc(
362     void fun(bool b) {
363       int target;
364       int other;
365       // [[p1]]
366       if (b) {
367         target = 2;
368         // [[pT]]
369       } else {
370         other = 3;
371         // [[pF]]
372       }
373       (void)0;
374       // [[p2]]
375     }
376   )cc";
377   RunDataflow(Code, UnorderedElementsAre(
378                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(
379                                        Pair(Var("target"), Varies()),
380                                        Pair(Var("other"), Varies())))),
381                         Pair("pT", HoldsCPLattice(UnorderedElementsAre(
382                                        Pair(Var("target"), HasConstantVal(2)),
383                                        Pair(Var("other"), Varies())))),
384                         Pair("pF", HoldsCPLattice(UnorderedElementsAre(
385                                        Pair(Var("other"), HasConstantVal(3)),
386                                        Pair(Var("target"), Varies())))),
387                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(
388                                        Pair(Var("target"), Varies()),
389                                        Pair(Var("other"), Varies()))))));
390 }
391 
392 TEST_F(MultiVarConstantPropagationTest, SameAssignmentInBranch) {
393   std::string Code = R"cc(
394     void fun(bool b) {
395       int target = 1;
396       // [[p1]]
397       if (b) {
398         target = 1;
399       }
400       (void)0;
401       // [[p2]]
402     }
403   )cc";
404   RunDataflow(Code, UnorderedElementsAre(
405                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
406                                        Var("target"), HasConstantVal(1))))),
407                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
408                                        Var("target"), HasConstantVal(1)))))));
409 }
410 
411 TEST_F(MultiVarConstantPropagationTest, NewVarInBranch) {
412   std::string Code = R"cc(
413     void fun(bool b) {
414       if (b) {
415         int target;
416         // [[p1]]
417         target = 1;
418         // [[p2]]
419       } else {
420         int target;
421         // [[p3]]
422         target = 1;
423         // [[p4]]
424       }
425     }
426   )cc";
427   RunDataflow(Code, UnorderedElementsAre(
428                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(
429                                        Pair(Var("target"), Varies())))),
430                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
431                                        Var("target"), HasConstantVal(1))))),
432                         Pair("p3", HoldsCPLattice(UnorderedElementsAre(
433                                        Pair(Var("target"), Varies())))),
434                         Pair("p4", HoldsCPLattice(UnorderedElementsAre(Pair(
435                                        Var("target"), HasConstantVal(1)))))));
436 }
437 
438 TEST_F(MultiVarConstantPropagationTest, DifferentAssignmentInBranches) {
439   std::string Code = R"cc(
440     void fun(bool b) {
441       int target;
442       // [[p1]]
443       if (b) {
444         target = 1;
445         // [[pT]]
446       } else {
447         target = 2;
448         // [[pF]]
449       }
450       (void)0;
451       // [[p2]]
452     }
453   )cc";
454   RunDataflow(Code, UnorderedElementsAre(
455                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(
456                                        Pair(Var("target"), Varies())))),
457                         Pair("pT", HoldsCPLattice(UnorderedElementsAre(Pair(
458                                        Var("target"), HasConstantVal(1))))),
459                         Pair("pF", HoldsCPLattice(UnorderedElementsAre(Pair(
460                                        Var("target"), HasConstantVal(2))))),
461                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(
462                                        Pair(Var("target"), Varies()))))));
463 }
464 
465 TEST_F(MultiVarConstantPropagationTest, DifferentAssignmentInBranch) {
466   std::string Code = R"cc(
467     void fun(bool b) {
468       int target = 1;
469       // [[p1]]
470       if (b) {
471         target = 3;
472       }
473       (void)0;
474       // [[p2]]
475     }
476   )cc";
477   RunDataflow(Code, UnorderedElementsAre(
478                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
479                                        Var("target"), HasConstantVal(1))))),
480                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(
481                                        Pair(Var("target"), Varies()))))));
482 }
483 
484 } // namespace
485 } // namespace dataflow
486 } // namespace clang
487