clang/unittests/Analysis/FlowSensitive/MultiVarConstantPropagationTest.cpp

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