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