diff --git a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt --- a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -4,6 +4,8 @@ ) add_clang_unittest(ClangAnalysisFlowSensitiveTests + ConstantPropagation.cpp + ConstantPropagationTest.cpp TestingSupport.cpp TestingSupportTest.cpp TypeErasedDataflowAnalysisTest.cpp diff --git a/clang/unittests/Analysis/FlowSensitive/ConstantPropagation.h b/clang/unittests/Analysis/FlowSensitive/ConstantPropagation.h new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/ConstantPropagation.h @@ -0,0 +1,85 @@ +//===--- TestingSupport.h - Testing utils for dataflow analyses -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines a simplist version of Constant Propagation as an example of +// a forward, monotonic dataflow analysis. The analysis only tracks one variable +// at a time -- the one with the most recent declaration encountered. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_CONSTANT_PROPAGATION_H_ +#define LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_CONSTANT_PROPAGATION_H_ + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include + +namespace clang { +namespace dataflow { + +// Lattice for data flow analysis that tracks the value of a single integer +// variable. If it can be identified with a single (constant) value, then that +// value is stored. Otherwise, "unknown" if many values are possible. +struct ConstantPropagationLattice { + const VarDecl *Var; + // `None` indicates more than one value is possible. If `Value` is populated, + // it indicates that `Var` has the given value at program point with which + // this lattice element is associated, for all paths through the program. + llvm::Optional Value; + + // `top` is not required by the framework, but it tends to be useful in + // practice. + static ConstantPropagationLattice top() { return {nullptr, llvm::None}; } + + friend bool operator==(ConstantPropagationLattice Element1, + ConstantPropagationLattice Element2) { + return Element1.Var == Element2.Var && Element1.Value == Element2.Value; + } + + friend bool operator!=(ConstantPropagationLattice Element1, + ConstantPropagationLattice Element2) { + return !(Element1 == Element2); + } + + LatticeJoinEffect join(ConstantPropagationLattice Other) { + if (*this == Other) + return LatticeJoinEffect::Unchanged; + + LatticeJoinEffect Result = *this == top() ? LatticeJoinEffect::Unchanged + : LatticeJoinEffect::Changed; + *this = top(); + return Result; + } +}; + +class ConstantPropagationAnalysis + : public DataflowAnalysis { +public: + explicit ConstantPropagationAnalysis(ASTContext &Context) + : DataflowAnalysis(Context) {} + + static ConstantPropagationLattice initialElement() { + return {nullptr, llvm::None}; + } + + ConstantPropagationLattice transfer(const Stmt *Stmt, + ConstantPropagationLattice Element, + Environment &Environment); +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_CONSTANT_PROPAGATION_H_ diff --git a/clang/unittests/Analysis/FlowSensitive/ConstantPropagation.cpp b/clang/unittests/Analysis/FlowSensitive/ConstantPropagation.cpp new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/ConstantPropagation.cpp @@ -0,0 +1,92 @@ +#include "ConstantPropagation.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" +#include "clang/AST/Stmt.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" + +using namespace ::clang; +using namespace ::dataflow; +using namespace ::clang::ast_matchers; + +static constexpr char kVar[] = "var"; +static constexpr char kInit[] = "init"; +static constexpr char kJustAssignment[] = "just-assignment"; +static constexpr char kAssignment[] = "assignment"; +static constexpr char kDeclStmt[] = "decl-stmt"; +static constexpr char kRHS[] = "rhs"; + +static auto refToVar(const VarDecl &Var) { + return declRefExpr(to(varDecl(equalsNode(&Var)).bind(kVar))); +} + +// Plain (not compound) assignment: "=". +static auto assignmentExpr(const VarDecl &Var) { + return binaryOperator(hasOperatorName("="), hasLHS(refToVar(Var)), + hasRHS(expr().bind(kRHS))); +} + +static auto anyAssignmentExpr(const VarDecl &Var) { + return binaryOperator(isAssignmentOperator(), hasLHS(refToVar(Var))); +} + +static auto dispatchMatcher(const VarDecl &Var) { + return stmt(anyOf(declStmt(hasSingleDecl(varDecl(hasType(isInteger()), + optionally(hasInitializer( + expr().bind(kInit)))) + .bind(kVar))) + .bind(kDeclStmt), + assignmentExpr(Var).bind(kJustAssignment), + anyAssignmentExpr(Var).bind(kAssignment))); +} + +static llvm::Optional transferInternal(llvm::Optional Value, + const BoundNodes &Nodes, + const ASTContext &Context) { + if (const auto *E = Nodes.getNodeAs(kInit)) { + Expr::EvalResult R; + if (E->EvaluateAsInt(R, Context) && R.Val.isInt()) + return R.Val.getInt().getExtValue(); + return llvm::None; + } + + // A declaration, but without the initializer (because `kInit` is unbound). + if (Nodes.getNodeAs(kDeclStmt)) { + return llvm::None; + } + + if (Nodes.getNodeAs(kJustAssignment)) { + const auto *RHS = Nodes.getNodeAs(kRHS); + assert(RHS != nullptr); + + Expr::EvalResult R; + if (RHS->EvaluateAsInt(R, Context) && R.Val.isInt()) + return R.Val.getInt().getExtValue(); + return llvm::None; + } + + // Any assignment involving the expression itself resets the variable to + // "unknown". A more advanced analysis could try to evaluate the compound + // assignment. For example, `x += 0` need not invalidate `x`. + if (const auto *E = Nodes.getNodeAs(kAssignment)) { + return llvm::None; + } + + return Value; +} + +ConstantPropagationLattice +ConstantPropagationAnalysis::transfer(const clang::Stmt *Stmt, + ConstantPropagationLattice Element, + Environment &Env) { + auto Results = match(dispatchMatcher(*Element.Var), *Stmt, getASTContext()); + if (Results.empty()) + return Element; + + const auto *Var = Results[0].getNodeAs(kVar); + assert(Var != nullptr); + + return ConstantPropagationLattice{ + Var, transferInternal(Element.Value, Results[0], getASTContext())}; +} diff --git a/clang/unittests/Analysis/FlowSensitive/ConstantPropagationTest.cpp b/clang/unittests/Analysis/FlowSensitive/ConstantPropagationTest.cpp new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/ConstantPropagationTest.cpp @@ -0,0 +1,201 @@ +#include "ConstantPropagation.h" +#include "TestingSupport.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/Twine.h" +#include "llvm/Support/Error.h" +#include "llvm/Testing/Support/Annotations.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include +#include +#include +#include + +namespace clang { +namespace dataflow { + +std::ostream &operator<<(std::ostream &OS, + const ConstantPropagationLattice &L) { + std::string Name = L.Var != nullptr ? L.Var->getName().str() : "NOVAR"; + OS << Name << " = "; + if (L.Value) + return OS << *L.Value; + return OS << "NONE"; +} + +namespace { +using ::testing::Pair; +using ::testing::UnorderedElementsAre; + +MATCHER_P(HasConstantVal, v, "") { return arg.Value && *arg.Value == v; } + +MATCHER(Varies, "") { return !arg.Value; } + +MATCHER_P(HoldsCPLattice, m, + (llvm::StringRef(negation ? "doesn't hold" : "holds") + + " a lattice element that " + + ::testing::DescribeMatcher(m, negation)) + .str()) { + return ExplainMatchResult(m, arg.Lattice, result_listener); +} + +class ConstantPropagationTest : public ::testing::Test { +protected: + ConstantPropagationTest() = default; + + template + void RunDataflow(llvm::StringRef Code, Matcher Expectations) { + test::checkDataflow( + Code, "fun", + [](ASTContext &C, Environment &) { + return ConstantPropagationAnalysis(C); + }, + [&Expectations]( + llvm::ArrayRef>> + Results, + ASTContext &) { EXPECT_THAT(Results, Expectations); }, + {"-fsyntax-only", "-std=c++17"}); + } +}; + +TEST_F(ConstantPropagationTest, JustInit) { + std::string code = R"( + void fun() { + int target = 1; + // [[p]] + } + )"; + RunDataflow( + code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(1))))); +} + +TEST_F(ConstantPropagationTest, Assignment) { + std::string code = R"( + void fun() { + int target = 1; + // [[p1]] + target = 2; + // [[p2]] + } + )"; + RunDataflow(code, UnorderedElementsAre( + Pair("p1", HoldsCPLattice(HasConstantVal(1))), + Pair("p2", HoldsCPLattice(HasConstantVal(2))))); +} + +TEST_F(ConstantPropagationTest, PlusAssignment) { + std::string code = R"( + void fun() { + int target = 1; + // [[p1]] + target += 2; + // [[p2]] + } + )"; + RunDataflow( + code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))), + Pair("p2", HoldsCPLattice(Varies())))); +} + +// TODO: fix bug in annotation sourcing! or file it at least +// TEST_F(ConstantPropagationTest, SameAssignmentInBranches) { +// std::string code = R"cc( +// void fun(bool b) { +// int target; +// // [[p1]] +// if (b) { +// target = 2; +// } else { +// target = 2; +// } +// // [[p2]] +// } +// )cc"; +// RunDataflow(code, UnorderedElementsAre( +// Pair("p1", HoldsCPLattice(Varies())), +// Pair("p2", HoldsCPLattice(HasConstantVal(2))))); +// } + +TEST_F(ConstantPropagationTest, SameAssignmentInBranches) { + std::string code = R"cc( + void fun(bool b) { + int target = 1; + // [[p1]] + if (b) { + target = 2; + } else { + target = 2; + } + (void)0; + // [[p2]] + } + )cc"; + RunDataflow(code, UnorderedElementsAre( + Pair("p1", HoldsCPLattice(Varies())), + Pair("p2", HoldsCPLattice(HasConstantVal(2))))); +} + +TEST_F(ConstantPropagationTest, SameAssignmentInBranch) { + std::string code = R"cc( + void fun(bool b) { + int target = 1; + // [[p1]] + if (b) { + target = 1; + } + (void)0; + // [[p2]] + } + )cc"; + RunDataflow(code, UnorderedElementsAre( + Pair("p1", HoldsCPLattice(HasConstantVal(1))), + Pair("p2", HoldsCPLattice(HasConstantVal(1))))); +} + +TEST_F(ConstantPropagationTest, DifferentAssignmentInBranches) { + std::string code = R"cc( + void fun(bool b) { + int target; + // [[p1]] + if (b) { + target = 1; + } else { + target = 2; + } + (void)0; + // [[p2]] + } + )cc"; + RunDataflow(code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(Varies())), + Pair("p2", HoldsCPLattice(Varies())))); +} + +TEST_F(ConstantPropagationTest, DifferentAssignmentInBranch) { + std::string code = R"cc( + void fun(bool b) { + int target = 1; + // [[p1]] + if (b) { + target = 3; + } + (void)0; + // [[p2]] + } + )cc"; + RunDataflow( + code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(HasConstantVal(1))), + Pair("p2", HoldsCPLattice(Varies())))); +} + +} // namespace +} // namespace dataflow +} // namespace clang diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h --- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h @@ -1,4 +1,4 @@ -//===--- DataflowValues.h - Data structure for dataflow values --*- C++ -*-===// +//===--- TestingSupport.h - Testing utils for dataflow analyses -*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,9 +6,7 @@ // //===----------------------------------------------------------------------===// // -// This file defines a skeleton data structure for encapsulating the dataflow -// values for a CFG. Typically this is subclassed to provide methods for -// computing these values from a CFG. +// This file defines utilities to simplify testing of dataflow analyses. // //===----------------------------------------------------------------------===//