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