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