499 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines a simplistic version of Constant Propagation as an example10// of a forward, monotonic dataflow analysis. The analysis tracks all11// 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 41namespace clang {42namespace dataflow {43namespace {44using namespace ast_matchers;45 46// Models the value of an expression at a program point, for all paths through47// the program.48struct ValueLattice {49 // FIXME: change the internal representation to use a `std::variant`, once50 // 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 on61 // `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 97std::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 109using ConstantPropagationLattice = VarMapLattice<ValueLattice>;110 111constexpr char kDecl[] = "decl";112constexpr char kVar[] = "var";113constexpr char kInit[] = "init";114constexpr char kJustAssignment[] = "just-assignment";115constexpr char kAssignment[] = "assignment";116constexpr char kRHS[] = "rhs";117 118auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }119 120// N.B. This analysis is deliberately simplistic, leaving out many important121// details needed for a real analysis. Most notably, the transfer function does122// not account for the variable's address possibly escaping, which would123// invalidate the analysis. It also could be optimized to drop out-of-scope124// variables from the map.125class ConstantPropagationAnalysis126 : public DataflowAnalysis<ConstantPropagationAnalysis,127 ConstantPropagationLattice> {128public: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 uninitialized variable holds *some* value, but we don't know what171 // it 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 to184 // "unknown". A more advanced analysis could try to evaluate the compound185 // assignment. For example, `x += 0` need not invalidate `x`.186 Vars[Var] = ValueLattice::top();187 }188 }189};190 191using ::clang::dataflow::test::AnalysisInputs;192using ::clang::dataflow::test::AnalysisOutputs;193using ::clang::dataflow::test::checkDataflow;194using ::llvm::IsStringMapEntry;195using ::testing::Pair;196using ::testing::UnorderedElementsAre;197 198MATCHER_P(Var, name,199 (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +200 name + "`")201 .str()) {202 return arg->getName() == name;203}204 205MATCHER_P(HasConstantVal, v, "") { return arg.Value && *arg.Value == v; }206 207MATCHER(Varies, "") { return arg == arg.top(); }208 209MATCHER_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 217template <typename Matcher>218void 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 236TEST(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 248TEST(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 266TEST(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 280TEST(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 293TEST(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 310TEST(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.340TEST(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 364TEST(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 398TEST(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 419TEST(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 448TEST(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 476TEST(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} // namespace497} // namespace dataflow498} // namespace clang499