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   ConstantPropagationLattice
136   transfer(const Stmt *S, ConstantPropagationLattice Vars, 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 Vars;
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       return Vars;
169     }
170 
171     if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
172       const auto *E = Nodes.getNodeAs<clang::Expr>(kRHS);
173       assert(E != nullptr);
174 
175       Expr::EvalResult R;
176       Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
177                       ? ValueLattice(R.Val.getInt().getExtValue())
178                       : ValueLattice::top();
179       return Vars;
180     }
181 
182     // Any assignment involving the expression itself resets the variable to
183     // "unknown". A more advanced analysis could try to evaluate the compound
184     // assignment. For example, `x += 0` need not invalidate `x`.
185     if (Nodes.getNodeAs<clang::Expr>(kAssignment)) {
186       Vars[Var] = ValueLattice::top();
187       return Vars;
188     }
189 
190     llvm_unreachable("expected at least one bound identifier");
191   }
192 };
193 
194 using ::testing::IsEmpty;
195 using ::testing::Pair;
196 using ::testing::UnorderedElementsAre;
197 
198 MATCHER_P(Var, name,
199           (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +
200            name + "`")
201               .str()) {
202   return arg->getName() == name;
203 }
204 
205 MATCHER_P(HasConstantVal, v, "") {
206   return arg.Value.hasValue() && *arg.Value == v;
207 }
208 
209 MATCHER(Varies, "") { return arg == arg.top(); }
210 
211 MATCHER_P(HoldsCPLattice, m,
212           ((negation ? "doesn't hold" : "holds") +
213            llvm::StringRef(" a lattice element that ") +
214            ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
215               .str()) {
216   return ExplainMatchResult(m, arg.Lattice, result_listener);
217 }
218 
219 class MultiVarConstantPropagationTest : public ::testing::Test {
220 protected:
221   template <typename Matcher>
222   void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
223     test::checkDataflow<ConstantPropagationAnalysis>(
224         Code, "fun",
225         [](ASTContext &C, Environment &) {
226           return ConstantPropagationAnalysis(C);
227         },
228         [&Expectations](
229             llvm::ArrayRef<std::pair<
230                 std::string,
231                 DataflowAnalysisState<ConstantPropagationAnalysis::Lattice>>>
232                 Results,
233             ASTContext &) { EXPECT_THAT(Results, Expectations); },
234         {"-fsyntax-only", "-std=c++17"});
235   }
236 };
237 
238 TEST_F(MultiVarConstantPropagationTest, JustInit) {
239   std::string Code = R"(
240     void fun() {
241       int target = 1;
242       // [[p]]
243     }
244   )";
245   RunDataflow(Code, UnorderedElementsAre(
246                         Pair("p", HoldsCPLattice(UnorderedElementsAre(Pair(
247                                       Var("target"), HasConstantVal(1)))))));
248 }
249 
250 TEST_F(MultiVarConstantPropagationTest, Assignment) {
251   std::string Code = R"(
252     void fun() {
253       int target = 1;
254       // [[p1]]
255       target = 2;
256       // [[p2]]
257     }
258   )";
259   RunDataflow(Code, UnorderedElementsAre(
260                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
261                                        Var("target"), HasConstantVal(1))))),
262                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
263                                        Var("target"), HasConstantVal(2)))))));
264 }
265 
266 TEST_F(MultiVarConstantPropagationTest, AssignmentCall) {
267   std::string Code = R"(
268     int g();
269     void fun() {
270       int target;
271       target = g();
272       // [[p]]
273     }
274   )";
275   RunDataflow(Code, UnorderedElementsAre(
276                         Pair("p", HoldsCPLattice(UnorderedElementsAre(
277                                       Pair(Var("target"), Varies()))))));
278 }
279 
280 TEST_F(MultiVarConstantPropagationTest, AssignmentBinOp) {
281   std::string Code = R"(
282     void fun() {
283       int target;
284       target = 2 + 3;
285       // [[p]]
286     }
287   )";
288   RunDataflow(Code, UnorderedElementsAre(
289                         Pair("p", HoldsCPLattice(UnorderedElementsAre(Pair(
290                                       Var("target"), HasConstantVal(5)))))));
291 }
292 
293 TEST_F(MultiVarConstantPropagationTest, PlusAssignment) {
294   std::string Code = R"(
295     void fun() {
296       int target = 1;
297       // [[p1]]
298       target += 2;
299       // [[p2]]
300     }
301   )";
302   RunDataflow(Code, UnorderedElementsAre(
303                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
304                                        Var("target"), HasConstantVal(1))))),
305                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(
306                                        Pair(Var("target"), Varies()))))));
307 }
308 
309 TEST_F(MultiVarConstantPropagationTest, SameAssignmentInBranches) {
310   std::string Code = R"cc(
311     void fun(bool b) {
312       int target;
313       // [[p1]]
314       if (b) {
315         target = 2;
316         // [[pT]]
317       } else {
318         target = 2;
319         // [[pF]]
320       }
321       (void)0;
322       // [[p2]]
323     }
324   )cc";
325   RunDataflow(Code,
326               UnorderedElementsAre(
327                   Pair("p1", HoldsCPLattice(UnorderedElementsAre(
328                                  Pair(Var("target"), Varies())))),
329                   Pair("pT", HoldsCPLattice(UnorderedElementsAre(
330                                  Pair(Var("target"), HasConstantVal(2))))),
331                   Pair("pF", HoldsCPLattice(UnorderedElementsAre(
332                                  Pair(Var("target"), HasConstantVal(2))))),
333                   Pair("p2", HoldsCPLattice(UnorderedElementsAre(
334                                  Pair(Var("target"), HasConstantVal(2)))))));
335 }
336 
337 // Verifies that the analysis tracks multiple variables simultaneously.
338 TEST_F(MultiVarConstantPropagationTest, TwoVariables) {
339   std::string Code = R"(
340     void fun() {
341       int target = 1;
342       // [[p1]]
343       int other = 2;
344       // [[p2]]
345       target = 3;
346       // [[p3]]
347     }
348   )";
349   RunDataflow(Code,
350               UnorderedElementsAre(
351                   Pair("p1", HoldsCPLattice(UnorderedElementsAre(
352                                  Pair(Var("target"), HasConstantVal(1))))),
353                   Pair("p2", HoldsCPLattice(UnorderedElementsAre(
354                                  Pair(Var("target"), HasConstantVal(1)),
355                                  Pair(Var("other"), HasConstantVal(2))))),
356                   Pair("p3", HoldsCPLattice(UnorderedElementsAre(
357                                  Pair(Var("target"), HasConstantVal(3)),
358                                  Pair(Var("other"), HasConstantVal(2)))))));
359 }
360 
361 TEST_F(MultiVarConstantPropagationTest, TwoVariablesInBranches) {
362   std::string Code = R"cc(
363     void fun(bool b) {
364       int target;
365       int other;
366       // [[p1]]
367       if (b) {
368         target = 2;
369         // [[pT]]
370       } else {
371         other = 3;
372         // [[pF]]
373       }
374       (void)0;
375       // [[p2]]
376     }
377   )cc";
378   RunDataflow(Code, UnorderedElementsAre(
379                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(
380                                        Pair(Var("target"), Varies()),
381                                        Pair(Var("other"), Varies())))),
382                         Pair("pT", HoldsCPLattice(UnorderedElementsAre(
383                                        Pair(Var("target"), HasConstantVal(2)),
384                                        Pair(Var("other"), Varies())))),
385                         Pair("pF", HoldsCPLattice(UnorderedElementsAre(
386                                        Pair(Var("other"), HasConstantVal(3)),
387                                        Pair(Var("target"), Varies())))),
388                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(
389                                        Pair(Var("target"), Varies()),
390                                        Pair(Var("other"), Varies()))))));
391 }
392 
393 TEST_F(MultiVarConstantPropagationTest, SameAssignmentInBranch) {
394   std::string Code = R"cc(
395     void fun(bool b) {
396       int target = 1;
397       // [[p1]]
398       if (b) {
399         target = 1;
400       }
401       (void)0;
402       // [[p2]]
403     }
404   )cc";
405   RunDataflow(Code, UnorderedElementsAre(
406                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
407                                        Var("target"), HasConstantVal(1))))),
408                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
409                                        Var("target"), HasConstantVal(1)))))));
410 }
411 
412 TEST_F(MultiVarConstantPropagationTest, NewVarInBranch) {
413   std::string Code = R"cc(
414     void fun(bool b) {
415       if (b) {
416         int target;
417         // [[p1]]
418         target = 1;
419         // [[p2]]
420       } else {
421         int target;
422         // [[p3]]
423         target = 1;
424         // [[p4]]
425       }
426     }
427   )cc";
428   RunDataflow(Code, UnorderedElementsAre(
429                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(
430                                        Pair(Var("target"), Varies())))),
431                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(Pair(
432                                        Var("target"), HasConstantVal(1))))),
433                         Pair("p3", HoldsCPLattice(UnorderedElementsAre(
434                                        Pair(Var("target"), Varies())))),
435                         Pair("p4", HoldsCPLattice(UnorderedElementsAre(Pair(
436                                        Var("target"), HasConstantVal(1)))))));
437 }
438 
439 TEST_F(MultiVarConstantPropagationTest, DifferentAssignmentInBranches) {
440   std::string Code = R"cc(
441     void fun(bool b) {
442       int target;
443       // [[p1]]
444       if (b) {
445         target = 1;
446         // [[pT]]
447       } else {
448         target = 2;
449         // [[pF]]
450       }
451       (void)0;
452       // [[p2]]
453     }
454   )cc";
455   RunDataflow(Code, UnorderedElementsAre(
456                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(
457                                        Pair(Var("target"), Varies())))),
458                         Pair("pT", HoldsCPLattice(UnorderedElementsAre(Pair(
459                                        Var("target"), HasConstantVal(1))))),
460                         Pair("pF", HoldsCPLattice(UnorderedElementsAre(Pair(
461                                        Var("target"), HasConstantVal(2))))),
462                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(
463                                        Pair(Var("target"), Varies()))))));
464 }
465 
466 TEST_F(MultiVarConstantPropagationTest, DifferentAssignmentInBranch) {
467   std::string Code = R"cc(
468     void fun(bool b) {
469       int target = 1;
470       // [[p1]]
471       if (b) {
472         target = 3;
473       }
474       (void)0;
475       // [[p2]]
476     }
477   )cc";
478   RunDataflow(Code, UnorderedElementsAre(
479                         Pair("p1", HoldsCPLattice(UnorderedElementsAre(Pair(
480                                        Var("target"), HasConstantVal(1))))),
481                         Pair("p2", HoldsCPLattice(UnorderedElementsAre(
482                                        Pair(Var("target"), Varies()))))));
483 }
484 
485 } // namespace
486 } // namespace dataflow
487 } // namespace clang
488