411 lines · cpp
1//===- unittests/Analysis/FlowSensitive/SingleVarConstantPropagation.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 only tracks one11// variable at a time -- the one with the most recent declaration encountered.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 "llvm/ADT/StringRef.h"27#include "llvm/ADT/Twine.h"28#include "llvm/Support/Error.h"29#include "llvm/Testing/ADT/StringMapEntry.h"30#include "llvm/Testing/Annotations/Annotations.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// A semi-lattice for dataflow analysis that tracks the value of a single47// integer variable. If it can be identified with a single (constant) value,48// then that value is stored.49struct ConstantPropagationLattice {50 // A null `Var` represents "top": either more than one value is possible or51 // more than one variable was encountered. Otherwise, `Data` indicates that52 // `Var` has the given `Value` at the program point with which this lattice53 // element is associated, for all paths through the program.54 struct VarValue {55 const VarDecl *Var;56 int64_t Value;57 58 friend bool operator==(VarValue Lhs, VarValue Rhs) {59 return Lhs.Var == Rhs.Var && Lhs.Value == Rhs.Value;60 }61 };62 // `std::nullopt` is "bottom".63 std::optional<VarValue> Data;64 65 static constexpr ConstantPropagationLattice bottom() {66 return {std::nullopt};67 }68 static constexpr ConstantPropagationLattice top() {69 return {VarValue{nullptr, 0}};70 }71 72 friend bool operator==(const ConstantPropagationLattice &Lhs,73 const ConstantPropagationLattice &Rhs) {74 return Lhs.Data == Rhs.Data;75 }76 77 LatticeJoinEffect join(const ConstantPropagationLattice &Other) {78 if (*this == Other || Other == bottom() || *this == top())79 return LatticeJoinEffect::Unchanged;80 81 if (*this == bottom()) {82 *this = Other;83 return LatticeJoinEffect::Changed;84 }85 86 *this = top();87 return LatticeJoinEffect::Changed;88 }89};90 91std::ostream &operator<<(std::ostream &OS,92 const ConstantPropagationLattice &L) {93 if (L == L.bottom())94 return OS << "None";95 if (L == L.top())96 return OS << "Any";97 return OS << L.Data->Var->getName().str() << " = " << L.Data->Value;98}99 100} // namespace101 102static constexpr char kVar[] = "var";103static constexpr char kInit[] = "init";104static constexpr char kJustAssignment[] = "just-assignment";105static constexpr char kAssignment[] = "assignment";106static constexpr char kRHS[] = "rhs";107 108static auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }109 110namespace {111// N.B. This analysis is deliberately simplistic, leaving out many important112// details needed for a real analysis in production. Most notably, the transfer113// function does not account for the variable's address possibly escaping, which114// would invalidate the analysis.115class ConstantPropagationAnalysis116 : public DataflowAnalysis<ConstantPropagationAnalysis,117 ConstantPropagationLattice> {118public:119 explicit ConstantPropagationAnalysis(ASTContext &Context)120 : DataflowAnalysis<ConstantPropagationAnalysis,121 ConstantPropagationLattice>(Context) {}122 123 static ConstantPropagationLattice initialElement() {124 return ConstantPropagationLattice::bottom();125 }126 127 void transfer(const CFGElement &E, ConstantPropagationLattice &Element,128 Environment &Env) {129 auto CS = E.getAs<CFGStmt>();130 if (!CS)131 return;132 auto S = CS->getStmt();133 auto matcher = stmt(134 anyOf(declStmt(hasSingleDecl(varDecl(hasType(isInteger()),135 hasInitializer(expr().bind(kInit)))136 .bind(kVar))),137 binaryOperator(hasOperatorName("="), hasLHS(refToVar()),138 hasRHS(expr().bind(kRHS)))139 .bind(kJustAssignment),140 binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))141 .bind(kAssignment)));142 143 ASTContext &Context = getASTContext();144 auto Results = match(matcher, *S, Context);145 if (Results.empty())146 return;147 const BoundNodes &Nodes = Results[0];148 149 const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);150 assert(Var != nullptr);151 152 if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {153 Expr::EvalResult R;154 Element =155 (E->EvaluateAsInt(R, Context) && R.Val.isInt())156 ? ConstantPropagationLattice{{{Var,157 R.Val.getInt().getExtValue()}}}158 : ConstantPropagationLattice::top();159 } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {160 const auto *RHS = Nodes.getNodeAs<clang::Expr>(kRHS);161 assert(RHS != nullptr);162 163 Expr::EvalResult R;164 Element =165 (RHS->EvaluateAsInt(R, Context) && R.Val.isInt())166 ? ConstantPropagationLattice{{{Var,167 R.Val.getInt().getExtValue()}}}168 : ConstantPropagationLattice::top();169 } else if (Nodes.getNodeAs<clang::Expr>(kAssignment))170 // Any assignment involving the expression itself resets the variable to171 // "unknown". A more advanced analysis could try to evaluate the compound172 // assignment. For example, `x += 0` need not invalidate `x`.173 Element = ConstantPropagationLattice::top();174 }175};176 177using ::clang::dataflow::test::AnalysisInputs;178using ::clang::dataflow::test::AnalysisOutputs;179using ::clang::dataflow::test::checkDataflow;180using ::llvm::IsStringMapEntry;181using ::testing::UnorderedElementsAre;182 183MATCHER_P(HasConstantVal, v, "") { return arg.Data && arg.Data->Value == v; }184 185MATCHER(IsUnknown, "") { return arg == arg.bottom(); }186MATCHER(Varies, "") { return arg == arg.top(); }187 188MATCHER_P(HoldsCPLattice, m,189 ((negation ? "doesn't hold" : "holds") +190 llvm::StringRef(" a lattice element that ") +191 ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))192 .str()) {193 return ExplainMatchResult(m, arg.Lattice, result_listener);194}195 196template <typename Matcher>197void RunDataflow(llvm::StringRef Code, Matcher Expectations) {198 ASSERT_THAT_ERROR(199 checkDataflow<ConstantPropagationAnalysis>(200 AnalysisInputs<ConstantPropagationAnalysis>(201 Code, hasName("fun"),202 [](ASTContext &C, Environment &) {203 return ConstantPropagationAnalysis(C);204 })205 .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),206 /*VerifyResults=*/207 [&Expectations](const llvm::StringMap<DataflowAnalysisState<208 ConstantPropagationAnalysis::Lattice>> &Results,209 const AnalysisOutputs &) {210 EXPECT_THAT(Results, Expectations);211 }),212 llvm::Succeeded());213}214 215TEST(ConstantPropagationTest, JustInit) {216 std::string Code = R"(217 void fun() {218 int target = 1;219 // [[p]]220 }221 )";222 RunDataflow(Code, UnorderedElementsAre(IsStringMapEntry(223 "p", HoldsCPLattice(HasConstantVal(1)))));224}225 226// Verifies that the analysis tracks the last variable seen.227TEST(ConstantPropagationTest, TwoVariables) {228 std::string Code = R"(229 void fun() {230 int target = 1;231 // [[p1]]232 int other = 2;233 // [[p2]]234 target = 3;235 // [[p3]]236 }237 )";238 RunDataflow(Code,239 UnorderedElementsAre(240 IsStringMapEntry("p1", HoldsCPLattice(HasConstantVal(1))),241 IsStringMapEntry("p2", HoldsCPLattice(HasConstantVal(2))),242 IsStringMapEntry("p3", HoldsCPLattice(HasConstantVal(3)))));243}244 245TEST(ConstantPropagationTest, Assignment) {246 std::string Code = R"(247 void fun() {248 int target = 1;249 // [[p1]]250 target = 2;251 // [[p2]]252 }253 )";254 RunDataflow(Code,255 UnorderedElementsAre(256 IsStringMapEntry("p1", HoldsCPLattice(HasConstantVal(1))),257 IsStringMapEntry("p2", HoldsCPLattice(HasConstantVal(2)))));258}259 260TEST(ConstantPropagationTest, 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 IsStringMapEntry("p", HoldsCPLattice(Varies()))));271}272 273TEST(ConstantPropagationTest, AssignmentBinOp) {274 std::string Code = R"(275 void fun() {276 int target;277 target = 2 + 3;278 // [[p]]279 }280 )";281 RunDataflow(Code, UnorderedElementsAre(IsStringMapEntry(282 "p", HoldsCPLattice(HasConstantVal(5)))));283}284 285TEST(ConstantPropagationTest, 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,295 UnorderedElementsAre(296 IsStringMapEntry("p1", HoldsCPLattice(HasConstantVal(1))),297 IsStringMapEntry("p2", HoldsCPLattice(Varies()))));298}299 300TEST(ConstantPropagationTest, SameAssignmentInBranches) {301 std::string Code = R"cc(302 void fun(bool b) {303 int target;304 // [[p1]]305 if (b) {306 target = 2;307 // [[pT]]308 } else {309 target = 2;310 // [[pF]]311 }312 (void)0;313 // [[p2]]314 }315 )cc";316 RunDataflow(Code,317 UnorderedElementsAre(318 IsStringMapEntry("p1", HoldsCPLattice(IsUnknown())),319 IsStringMapEntry("pT", HoldsCPLattice(HasConstantVal(2))),320 IsStringMapEntry("pF", HoldsCPLattice(HasConstantVal(2))),321 IsStringMapEntry("p2", HoldsCPLattice(HasConstantVal(2)))));322}323 324TEST(ConstantPropagationTest, SameAssignmentInBranch) {325 std::string Code = R"cc(326 void fun(bool b) {327 int target = 1;328 // [[p1]]329 if (b) {330 target = 1;331 }332 (void)0;333 // [[p2]]334 }335 )cc";336 RunDataflow(Code,337 UnorderedElementsAre(338 IsStringMapEntry("p1", HoldsCPLattice(HasConstantVal(1))),339 IsStringMapEntry("p2", HoldsCPLattice(HasConstantVal(1)))));340}341 342TEST(ConstantPropagationTest, NewVarInBranch) {343 std::string Code = R"cc(344 void fun(bool b) {345 if (b) {346 int target;347 // [[p1]]348 target = 1;349 // [[p2]]350 } else {351 int target;352 // [[p3]]353 target = 1;354 // [[p4]]355 }356 }357 )cc";358 RunDataflow(Code,359 UnorderedElementsAre(360 IsStringMapEntry("p1", HoldsCPLattice(IsUnknown())),361 IsStringMapEntry("p2", HoldsCPLattice(HasConstantVal(1))),362 IsStringMapEntry("p3", HoldsCPLattice(IsUnknown())),363 IsStringMapEntry("p4", HoldsCPLattice(HasConstantVal(1)))));364}365 366TEST(ConstantPropagationTest, DifferentAssignmentInBranches) {367 std::string Code = R"cc(368 void fun(bool b) {369 int target;370 // [[p1]]371 if (b) {372 target = 1;373 // [[pT]]374 } else {375 target = 2;376 // [[pF]]377 }378 (void)0;379 // [[p2]]380 }381 )cc";382 RunDataflow(Code,383 UnorderedElementsAre(384 IsStringMapEntry("p1", HoldsCPLattice(IsUnknown())),385 IsStringMapEntry("pT", HoldsCPLattice(HasConstantVal(1))),386 IsStringMapEntry("pF", HoldsCPLattice(HasConstantVal(2))),387 IsStringMapEntry("p2", HoldsCPLattice(Varies()))));388}389 390TEST(ConstantPropagationTest, DifferentAssignmentInBranch) {391 std::string Code = R"cc(392 void fun(bool b) {393 int target = 1;394 // [[p1]]395 if (b) {396 target = 3;397 }398 (void)0;399 // [[p2]]400 }401 )cc";402 RunDataflow(Code,403 UnorderedElementsAre(404 IsStringMapEntry("p1", HoldsCPLattice(HasConstantVal(1))),405 IsStringMapEntry("p2", HoldsCPLattice(Varies()))));406}407 408} // namespace409} // namespace dataflow410} // namespace clang411