[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

69 ↗

(On Diff #394568)

Should this be a const ref? Same below.

97 ↗

(On Diff #394568)

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

119 ↗

(On Diff #394568)

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

160 ↗

(On Diff #394568)

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

161 ↗

(On Diff #394568)

Should this be a const ref?

180 ↗

(On Diff #394568)

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

197 ↗

(On Diff #394568)

Is this necessary?

217 ↗

(On Diff #394568)

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

245 ↗

(On Diff #394568)

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?

342 ↗

(On Diff #394568)

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

99 ↗

(On Diff #394568)

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

97 ↗

(On Diff #394568)

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

99 ↗

(On Diff #394568)

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.

119 ↗

(On Diff #394568)

inlined the matcher too

180 ↗

(On Diff #394568)

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

217 ↗

(On Diff #394568)

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.

245 ↗

(On Diff #394568)

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

[sgatev]

clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp

145 ↗

(On Diff #394594)

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
+  ConstantPropagation.cpp
+  ConstantPropagationTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests
   PRIVATE
   clangAnalysis

clang/unittests/Analysis/FlowSensitive/ConstantPropagation.h

+//===--- 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 <cstdint>
+
+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<int64_t> Value;
+
+  static ConstantPropagationLattice bottom() { 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 || Other.Var == nullptr)
+      return LatticeJoinEffect::Unchanged;
+
+    if (Var == nullptr) {
+      *this = Other;
+      return Other.Var == nullptr ? LatticeJoinEffect::Unchanged
+                                  : LatticeJoinEffect::Changed;
+    }
+
+    Value = llvm::None;
+    return LatticeJoinEffect::Changed;
+  }
+};
+
+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 *Stmt,
+                                      ConstantPropagationLattice Element,
+                                      Environment &Environment);
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOW_SENSITIVE_CONSTANT_PROPAGATION_H_

clang/unittests/Analysis/FlowSensitive/ConstantPropagation.cpp

+#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().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<int64_t> transferInternal(llvm::Optional<int64_t> Value,
+                                                const BoundNodes &Nodes,
+                                                const ASTContext &Context) {
+  if (const auto *E = Nodes.getNodeAs<clang::Expr>(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<clang::DeclStmt>(kDeclStmt))
+    return llvm::None;
+
+  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 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<clang::Expr>(kAssignment))
+    return llvm::None;
+
+  llvm_unreachable("expected at least one bound identifier");
+}
+
+ConstantPropagationLattice
+ConstantPropagationAnalysis::transfer(const clang::Stmt *Stmt,
+                                      ConstantPropagationLattice Element,
+                                      Environment &Env) {
+  auto VarDeclMatcher =
+      declStmt(
+          hasSingleDecl(varDecl(hasType(isInteger()),
+                                optionally(hasInitializer(expr().bind(kInit))))
+                            .bind(kVar)))
+          .bind(kDeclStmt);
+  auto Results = match(Element.Var != nullptr ? dispatchMatcher(*Element.Var)
+                                              : VarDeclMatcher,
+                       *Stmt, getASTContext());
+  if (Results.empty())
+    return Element;
+
+  const auto *Var = Results[0].getNodeAs<clang::VarDecl>(kVar);
+  assert(Var != nullptr);
+
+  return ConstantPropagationLattice{
+      Var, transferInternal(Element.Value, Results[0], getASTContext())};
+}

clang/unittests/Analysis/FlowSensitive/ConstantPropagationTest.cpp

+#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 <memory>
+#include <ostream>
+#include <string>
+#include <utility>
+
+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,
+          ((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:
+  ConstantPropagationTest() = default;
+
+  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)))));
+}
+
+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()))));
+}
+
+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(Varies())),
+                        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(Varies())),
+                        Pair("p2", HoldsCPLattice(HasConstantVal(1))),
+                        Pair("p3", HoldsCPLattice(Varies())),
+                        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;
+      } 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

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);
 }