[clang][dataflow] Add simplistic constant-propagation analysis.

[ymandel]

Summary

Adds a very simple constant-propagation analysis for demo and testing purposes.

Also, fixes two (small) bugs in the testing framework code.

[ymandel]

fix potential null pointer deref.

[ymandel]

Reworks analysis to use bottom, fixes two small bugs in testing framework.

[ymandel]

revised bottom representation and updated tests

[ymandel]

Coalesce all CP files into one test file.

[ymandel]

updated file header

[sgatev]

clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp

70

Should this be a const ref? Same below.

98

Why not put the definitions below also in the anonymous namespace?

120

What do you think about inlining this in ConstantPropagationAnalysis::transfer? We don't expect to call it from elsewhere, right?

161

Maybe call this S to disambiguate from the name of the type?

162

Should this be a const ref?

181

Maybe call this HasConstVal if you'd like to keep this short?

198

Is this necessary?

218

Capitalize - Code? Or maybe inline this in the function call? Same below.

246

Maybe add tests for assignment from a function call (e.g. int target = foo();) and assignment from an arithmetic expression (e.g. int target = 1 + 2;)? Both should result in IsUnknown() state, right?

343

Add internal checks, similar to those in SameAssignmentInBranches?

[xazax.hun]

This demo looks cool. While I know this is a demo, I think it misses some important features, namely invalidating the value when we take the address of a variable or pass it to a function by non-const reference.
I'm fine with not supporting those cases, but I'd love to see a comment about that. Just in case someone wants to use this analysis as a basis for something in production :)

clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp

100

Do we need an actual array? I think this would copy "var" into a global array. Alternatively, using static constexpr char* kVar= "var", we would just refer to the string in the read only memory. (Or maybe both would behave the same because compiler optimizations?)

[ymandel]

Responds to reviewer comments.

[ymandel]

clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp

98

LLVM style is to limit use of anonymous namespaces to class declarations (which have no parallel to static).

100

Good question. I prefer this style because the array form carries the bounds information with it, unlike the raw pointer form: https://godbolt.org/z/jEP9Wasrh But, I don't know of any meaningful performance implications. FWIW, this is the recommended form for our internal codebase.

120

inlined the matcher too

181

I'm fine with the current length. And, a little worried that "const" has its own meaning, which is separate from this one.

218

capitalized, but prefer to keep it separate for readability. Also, generally good practice since some compliers don't allow these kinds of strings inline in macro calls.

246

Actually, the eval engine is more powerful than you'd guess -- 1 + 2 evaluates statically. :)

[sgatev]

clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp

145

Move this above to replace the other call to getASTContext() or use getASTContext() everywhere?

[ymandel]

address review comments

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
+  SingleVarConstantPropagationTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests
   PRIVATE
   clangAnalysis

clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp

+//===- unittests/Analysis/FlowSensitive/SingelVarConstantPropagation.cpp --===//
+//
+// 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 simplistic 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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestingSupport.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"
+#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/None.h"
+#include "llvm/ADT/Optional.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 <cstdint>
+#include <memory>
+#include <ostream>
+#include <string>
+#include <utility>
+
+namespace clang {
+namespace dataflow {
+namespace {
+using namespace ast_matchers;
+
+// A semi-lattice for dataflow 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.
+struct ConstantPropagationLattice {
+  // A null `Var` represents "top": either more than one value is possible or
+  // more than one variable was encountered. Otherwise, `Data` indicates that
+  // `Var` has the given `Value` at the program point with which this lattice
+  // element is associated, for all paths through the program.
+  struct VarValue {
+    const VarDecl *Var;
+    int64_t Value;
+
+    friend bool operator==(VarValue Lhs, VarValue Rhs) {
+      return Lhs.Var == Rhs.Var && Lhs.Value == Rhs.Value;
+    }
+  };
+  // `None` is "bottom".
+  llvm::Optional<VarValue> Data;
+
+  static constexpr ConstantPropagationLattice bottom() { return {llvm::None}; }
+  static constexpr ConstantPropagationLattice top() {
+    return {VarValue{nullptr, 0}};
+  }
+
+  friend bool operator==(const ConstantPropagationLattice &Lhs,
+                         const ConstantPropagationLattice &Rhs) {
+    return Lhs.Data == Rhs.Data;
+  }
+
+  LatticeJoinEffect join(const ConstantPropagationLattice &Other) {
+    if (*this == Other || Other == bottom() || *this == top())
+      return LatticeJoinEffect::Unchanged;
+
+    if (*this == bottom()) {
+      *this = Other;
+      return LatticeJoinEffect::Changed;
+    }
+
+    *this = top();
+    return LatticeJoinEffect::Changed;
+  }
+};
+
+std::ostream &operator<<(std::ostream &OS,
+                         const ConstantPropagationLattice &L) {
+  if (L == L.bottom())
+    return OS << "None";
+  if (L == L.top())
+    return OS << "Any";
+  return OS << L.Data->Var->getName().str() << " = " << L.Data->Value;
+}
+
+} // namespace
+
+static constexpr char kVar[] = "var";
+static constexpr char kInit[] = "init";
+static constexpr char kJustAssignment[] = "just-assignment";
+static constexpr char kAssignment[] = "assignment";
+static constexpr char kRHS[] = "rhs";
+
+static auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }
+
+namespace {
+// N.B. This analysis is deliberately simplistic, leaving out many important
+// details needed for a real analysis in production. Most notably, the transfer
+// function does not account for the variable's address possibly escaping, which
+// would invalidate the analysis.
+class ConstantPropagationAnalysis
+    : public DataflowAnalysis<ConstantPropagationAnalysis,
+                              ConstantPropagationLattice> {
+public:
+  explicit ConstantPropagationAnalysis(ASTContext &Context)
+      : DataflowAnalysis<ConstantPropagationAnalysis,
+                         ConstantPropagationLattice>(Context) {}
+
+  static ConstantPropagationLattice initialElement() {
+    return ConstantPropagationLattice::bottom();
+  }
+
+  ConstantPropagationLattice transfer(const Stmt *S,
+                                      const ConstantPropagationLattice &Element,
+                                      Environment &Env) {
+    auto matcher = stmt(
+        anyOf(declStmt(hasSingleDecl(varDecl(hasType(isInteger()),
+                                             hasInitializer(expr().bind(kInit)))
+                                         .bind(kVar))),
+              binaryOperator(hasOperatorName("="), hasLHS(refToVar()),
+                             hasRHS(expr().bind(kRHS)))
+                  .bind(kJustAssignment),
+              binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))
+                  .bind(kAssignment)));
+
+    auto Results = match(matcher, *S, getASTContext());
+    if (Results.empty())
+      return Element;
+
+    const auto *Var = Results[0].getNodeAs<clang::VarDecl>(kVar);
+    assert(Var != nullptr);
+
+    const BoundNodes &Nodes = Results[0];
+    const ASTContext &Context = getASTContext();
+
+    if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
+      Expr::EvalResult R;
+      if (E->EvaluateAsInt(R, Context) && R.Val.isInt())
+        return ConstantPropagationLattice{
+            {{Var, R.Val.getInt().getExtValue()}}};
+      return ConstantPropagationLattice::top();
+    }
+
+    if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
+      const auto *RHS = Nodes.getNodeAs<clang::Expr>(kRHS);
+      assert(RHS != nullptr);
+
+      Expr::EvalResult R;
+      if (RHS->EvaluateAsInt(R, Context) && R.Val.isInt())
+        return ConstantPropagationLattice{
+            {{Var, R.Val.getInt().getExtValue()}}};
+      return ConstantPropagationLattice::top();
+    }
+
+    // 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<clang::Expr>(kAssignment))
+      return ConstantPropagationLattice::top();
+
+    llvm_unreachable("expected at least one bound identifier");
+  }
+};
+
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+MATCHER_P(HasConstantVal, v, "") {
+  return arg.Data.hasValue() && arg.Data->Value == v;
+}
+
+MATCHER(IsUnknown, "") { return arg == arg.bottom(); }
+MATCHER(Varies, "") { return arg == arg.top(); }
+
+MATCHER_P(HoldsCPLattice, m,
+          ((negation ? "doesn't hold" : "holds") +
+           llvm::StringRef(" a lattice element that ") +
+           ::testing::DescribeMatcher<ConstantPropagationLattice>(m, negation))
+              .str()) {
+  return ExplainMatchResult(m, arg.Lattice, result_listener);
+}
+
+class ConstantPropagationTest : public ::testing::Test {
+protected:
+  template <typename Matcher>
+  void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
+    test::checkDataflow<ConstantPropagationAnalysis>(
+        Code, "fun",
+        [](ASTContext &C, Environment &) {
+          return ConstantPropagationAnalysis(C);
+        },
+        [&Expectations](
+            llvm::ArrayRef<std::pair<
+                std::string,
+                DataflowAnalysisState<ConstantPropagationAnalysis::Lattice>>>
+                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)))));
+}
+
+// Verifies that the analysis tracks the last variable seen.
+TEST_F(ConstantPropagationTest, TwoVariables) {
+  std::string Code = R"(
+    void fun() {
+      int target = 1;
+      // [[p1]]
+      int other = 2;
+      // [[p2]]
+      target = 3;
+      // [[p3]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p1", HoldsCPLattice(HasConstantVal(1))),
+                        Pair("p2", HoldsCPLattice(HasConstantVal(2))),
+                        Pair("p3", HoldsCPLattice(HasConstantVal(3)))));
+}
+
+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, AssignmentCall) {
+  std::string Code = R"(
+    int g();
+    void fun() {
+      int target;
+      target = g();
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(Varies()))));
+}
+
+TEST_F(ConstantPropagationTest, AssignmentBinOp) {
+  std::string Code = R"(
+    void fun() {
+      int target;
+      target = 2 + 3;
+      // [[p]]
+    }
+  )";
+  RunDataflow(
+      Code, UnorderedElementsAre(Pair("p", HoldsCPLattice(HasConstantVal(5)))));
+}
+
+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()))));
+}
+
+TEST_F(ConstantPropagationTest, SameAssignmentInBranches) {
+  std::string Code = R"cc(
+    void fun(bool b) {
+      int target;
+      // [[p1]]
+      if (b) {
+        target = 2;
+        // [[pT]]
+      } else {
+        target = 2;
+        // [[pF]]
+      }
+      (void)0;
+      // [[p2]]
+    }
+  )cc";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p1", HoldsCPLattice(IsUnknown())),
+                        Pair("pT", HoldsCPLattice(HasConstantVal(2))),
+                        Pair("pF", HoldsCPLattice(HasConstantVal(2))),
+                        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, NewVarInBranch) {
+  std::string Code = R"cc(
+    void fun(bool b) {
+      if (b) {
+        int target;
+        // [[p1]]
+        target = 1;
+        // [[p2]]
+      } else {
+        int target;
+        // [[p3]]
+        target = 1;
+        // [[p4]]
+      }
+    }
+  )cc";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p1", HoldsCPLattice(IsUnknown())),
+                        Pair("p2", HoldsCPLattice(HasConstantVal(1))),
+                        Pair("p3", HoldsCPLattice(IsUnknown())),
+                        Pair("p4", HoldsCPLattice(HasConstantVal(1)))));
+}
+
+TEST_F(ConstantPropagationTest, DifferentAssignmentInBranches) {
+  std::string Code = R"cc(
+    void fun(bool b) {
+      int target;
+      // [[p1]]
+      if (b) {
+        target = 1;
+        // [[pT]]
+      } else {
+        target = 2;
+        // [[pF]]
+      }
+      (void)0;
+      // [[p2]]
+    }
+  )cc";
+  RunDataflow(
+      Code, UnorderedElementsAre(Pair("p1", HoldsCPLattice(IsUnknown())),
+                                 Pair("pT", HoldsCPLattice(HasConstantVal(1))),
+                                 Pair("pF", HoldsCPLattice(HasConstantVal(2))),
+                                 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

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

-//===--- 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.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// 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.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_
 #define LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_TESTING_SUPPORT_H_
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
std::function<void(
             std::string, DataflowAnalysisState<typename AnalysisT::Lattice>>>,
         ASTContext &)>
         Expectations,
     ArrayRef<std::string> Args,
     const tooling::FileContentMappings &VirtualMappedFiles = {}) {
   using StateT = DataflowAnalysisState<typename AnalysisT::Lattice>;
 
   llvm::Annotations AnnotatedCode(Code);
-  auto Unit = tooling::buildASTFromCodeWithArgs(
-      AnnotatedCode.code(), {"-fsyntax-only", "-std=c++17"});
+  auto Unit = tooling::buildASTFromCodeWithArgs(AnnotatedCode.code(), Args);
   auto &Context = Unit->getASTContext();
 
   if (Context.getDiagnostics().getClient()->getNumErrors() != 0) {
     FAIL() << "Source file has syntax or type errors, they were printed to "
               "the test log";
   }
 
   std::pair<const FunctionDecl *, std::unique_ptr<CFG>> CFGResult =
transferBlock(
         BlockStates, *Block, Env, Analysis,
         [&Results, &Annotations](const clang::CFGStmt &Stmt,
                                  const TypeErasedDataflowAnalysisState &State) {
           auto It = Annotations.find(Stmt.getStmt());
           if (It == Annotations.end())
             return;
           if (auto *Lattice = llvm::any_cast<typename AnalysisT::Lattice>(
                   &State.Lattice.Value)) {
-            Results.emplace_back(
-                It->second, StateT{std::move(*Lattice), std::move(State.Env)});
+            Results.emplace_back(It->second, StateT{*Lattice, State.Env});
           } else {
             FAIL() << "Could not cast lattice element to expected type.";
           }
         });
   }
   Expectations(Results, Context);
 }