[clang][dataflow] Implement transferBranch

[martong]

Summary

This patch introduces transferBranch, which Applies the analysis
transfer function for a given edge from a CFG block of a conditional
statement.

RFC:
https://discourse.llvm.org/t/rfc-clang-dataflow-signanalysis-edgetransfer-branchtransfer/65220

[gribozavr2]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

127

Please use CRTP (a non-virtual function here), and you'll need SFINAE to detect the presence of the overload of branchTransfer in branchTransferTypeErased.

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

86

Please add a doc comment. Please add a parameter name for the condition, it is not obvious what it is.

Could you think of a more descriptive name for Branch? For example, if the second parameter is Cond, WDYT about CondValue?

86

WDYT about calling it transferBranch... instead of branchTransfer...?

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

78

Please add a comment to RetTy.

148

CondValue?

253

It would be nice to still call branchTransfer even when BuiltinTransferOpts == false. Please leave a TODO if you don't want to implement that.

clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp

586

This file is an amazing example of how to use the framework, but could you add a more direct unit test with a simpler lattice and analysis that exercises the new callback?

[dkrupp]

clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp

241

Isn't this SignLattice::top() instead?

This is an initialization expression, which we cannot evaluate to int, but the variable is initialized.

[martong]

Aligned with the RFC, I am going to dissect this patch into two patches:

1. This patch will remain a simple infrastructural change that introduces transferBranch. This could be useful for complex lattices (e.g integer value ranges) until we have an SMT solver in the core framework. I'll try to add a very simple unit test case instead of having SignAnalysis itself as a huge integration test case.
2. An independent patch for SignAnalysis implementation. I am going to rework it by using the boolean Value abstraction as suggested in the RFC.

[martong]

• Add comments
• Assumption -> ConditionValue
• Use CRTP
• branchTransfer -> transferBranch
• Make just one simple test case for transferBranch

[martong]

• Rebase to latest llvm/main

[martong]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

127

Ok, changed it to use CRTP.

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

86

Ok, added a doc comment and renamed to transferBranch.

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

148

Ok, changed to ConditionValue.

253

Ok, I've added a TODO.

clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp

241

I am moving the sign analysis out of this patch.

586

Ok. I've removed the sign analysis from this patch and added a very simple test file with a very simple lattice to check the effect of transferBranch.

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

60–66 ↗

(On Diff #469636)

This is unused (a leftover). I am going remove this matcher.

[ymandel]

Overall, looks quite good.

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

89–90

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

78–81

please lift this out and define it as a struct. then, refer to it by name on line 76. that will improve the readability of the code and provide a way to document explicitly the role of the two fields.

257

I generally prefer explicit comparison but it's particularly important here, given that Cond sounds like it could be a boolean.

258

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

28 ↗

(On Diff #469636)

feels odd to mix and match namespace handling here. I think that if you want to go with namespace clang... that's fine but then do the same for test. In fact, since we're now in C++17, maybe:

namespace clang::dataflow::test {
namespace {

31 ↗

(On Diff #469636)

bool? i understand that you don't want to use bool directly, but still seems like the better base type here.

86–88 ↗

(On Diff #469636)

Can your test below use AnalysisOutputs directly, and thereby avoid this conversion lambda?

120 ↗

(On Diff #469636)

Please be explicit about the optional, since this is an important detail of the test. Same below.

123 ↗

(On Diff #469636)

EXPECT_THAT...

[martong]

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

9–11 ↗

(On Diff #469636)

I should update this comment as well.

[xazax.hun]

With the rest of the comments addressed it looks good to me.

[martong]

Thanks for the assiduous review @ymandel !

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

78–81

Ok, I hoisted this to be TerminatorVisitorRetTy.

[martong]

• Address ymandel's comments

[ymandel]

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

73 ↗

(On Diff #470748)

nit: maybe just rename the parameter to VerifyResults (and then no need for the comment)?

[martong]

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

73 ↗

(On Diff #470748)

Good idea, I've renamed it within the commit.

[martong]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

160

Actually, this member is not used, I am not sure why was this added. Anyway, I am removing this in a follow up commit.

[martong]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

160

https://github.com/llvm/llvm-project/commit/5bd142ca265d8243ecebb63ffed0c7afd3abf440

[aaron.ballman]

FWIW, it looks like this change broke the AIX bot: https://lab.llvm.org/buildbot/#/builders/214/builds/3932

[martong]

In D133698#3886329, @aaron.ballman wrote:

FWIW, it looks like this change broke the AIX bot: https://lab.llvm.org/buildbot/#/builders/214/builds/3932

Yes, I've received many build bot failures complaining about the unused private field. I hope that I've fixed that in
https://github.com/llvm/llvm-project/commit/5bd142ca265d8243ecebb63ffed0c7afd3abf440

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

void transferTypeErased(const CFGElement *Element, TypeErasedLattice &E,
     // `CFGElement`.
     if constexpr (HasTransferFor<Derived, LatticeT, Stmt>::value) {
       if (auto Stmt = Element->getAs<CFGStmt>()) {
         static_cast<Derived *>(this)->transfer(Stmt->getStmt(), L, Env);
       }
     }
   }
 
+  // Default implementation is a Noop.
+  virtual void branchTransfer(bool Branch, const Stmt *S, Lattice &L,
+                              Environment &Env) {}
+
+  void branchTransferTypeErased(bool Branch, const Stmt *Stmt,
+                                TypeErasedLattice &E, Environment &Env) final {
+    Lattice &L = llvm::any_cast<Lattice &>(E.Value);
+    branchTransfer(Branch, Stmt, L, Env);
+  }
+
 private:
   ASTContext &Context;
 };
 
 // Model of the program at a given program point.
 template <typename LatticeT> struct DataflowAnalysisState {
   // Model of a program property.
   LatticeT Lattice;

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

public:
   /// equal.
   virtual bool isEqualTypeErased(const TypeErasedLattice &,
                                  const TypeErasedLattice &) = 0;
 
   /// Applies the analysis transfer function for a given control flow graph
   /// element and type-erased lattice element.
   virtual void transferTypeErased(const CFGElement *, TypeErasedLattice &,
                                   Environment &) = 0;
+  virtual void branchTransferTypeErased(bool Branch, const Stmt *,
+                                        TypeErasedLattice &, Environment &) = 0;
 
   /// If the built-in transfer functions (which model the heap and stack in the
   /// `Environment`) are to be applied, returns the options to be passed to
   /// them. Otherwise returns empty.
   llvm::Optional<TransferOptions> builtinTransferOptions() const {
     return Options.BuiltinTransferOpts;
   }
 };
 
 /// Type-erased model of the program at a given program point.
 struct TypeErasedDataflowAnalysisState {

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

auto BlockPos = llvm::find_if(
       Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
         return Succ && Succ->getBlockID() == Block.getBlockID();
       });
   return BlockPos - Pred.succ_begin();
 }
 
 /// Extends the flow condition of an environment based on a terminator
 /// statement.
-class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> {
+class TerminatorVisitor
+    : public ConstStmtVisitor<TerminatorVisitor,
+                              std::pair<const Expr *, bool>> {
 public:
-  TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
+  using RetTy = std::pair<const Expr *, bool>;
+  TerminatorVisitor(TypeErasedDataflowAnalysis &Analysis,
+                    const StmtToEnvMap &StmtToEnv, Environment &Env,
                     int BlockSuccIdx, TransferOptions TransferOpts)
-      : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx),
-        TransferOpts(TransferOpts) {}
+      : Analysis(Analysis), StmtToEnv(StmtToEnv), Env(Env),
+        BlockSuccIdx(BlockSuccIdx), TransferOpts(TransferOpts) {}
 
-  void VisitIfStmt(const IfStmt *S) {
+  RetTy VisitIfStmt(const IfStmt *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
-    extendFlowCondition(*Cond);
+    return extendFlowCondition(*Cond);
   }
 
-  void VisitWhileStmt(const WhileStmt *S) {
+  RetTy VisitWhileStmt(const WhileStmt *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
-    extendFlowCondition(*Cond);
+    return extendFlowCondition(*Cond);
   }
 
-  void VisitDoStmt(const DoStmt *S) {
+  RetTy VisitDoStmt(const DoStmt *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
-    extendFlowCondition(*Cond);
+    return extendFlowCondition(*Cond);
   }
 
-  void VisitForStmt(const ForStmt *S) {
+  RetTy VisitForStmt(const ForStmt *S) {
     auto *Cond = S->getCond();
     if (Cond != nullptr)
-      extendFlowCondition(*Cond);
+      return extendFlowCondition(*Cond);
+    return {nullptr, false};
   }
 
-  void VisitBinaryOperator(const BinaryOperator *S) {
+  RetTy VisitBinaryOperator(const BinaryOperator *S) {
     assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
     auto *LHS = S->getLHS();
     assert(LHS != nullptr);
-    extendFlowCondition(*LHS);
+    return extendFlowCondition(*LHS);
   }
 
-  void VisitConditionalOperator(const ConditionalOperator *S) {
+  RetTy VisitConditionalOperator(const ConditionalOperator *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
-    extendFlowCondition(*Cond);
+    return extendFlowCondition(*Cond);
   }
 
 private:
-  void extendFlowCondition(const Expr &Cond) {
+  RetTy extendFlowCondition(const Expr &Cond) {
     // The terminator sub-expression might not be evaluated.
     if (Env.getStorageLocation(Cond, SkipPast::None) == nullptr)
       transfer(StmtToEnv, Cond, Env, TransferOpts);
 
     // FIXME: The flow condition must be an r-value, so `SkipPast::None` should
     // suffice.
     auto *Val =
         cast_or_null<BoolValue>(Env.getValue(Cond, SkipPast::Reference));
     // Value merging depends on flow conditions from different environments
     // being mutually exclusive -- that is, they cannot both be true in their
     // entirety (even if they may share some clauses). So, we need *some* value
     // for the condition expression, even if just an atom.
     if (Val == nullptr) {
       // FIXME: Consider introducing a helper for this get-or-create pattern.
       auto *Loc = Env.getStorageLocation(Cond, SkipPast::None);
       if (Loc == nullptr) {
         Loc = &Env.createStorageLocation(Cond);
         Env.setStorageLocation(Cond, *Loc);
       }
       Val = &Env.makeAtomicBoolValue();
       Env.setValue(*Loc, *Val);
     }
 
+    bool Assumption = true;
     // The condition must be inverted for the successor that encompasses the
     // "else" branch, if such exists.
-    if (BlockSuccIdx == 1)
+    if (BlockSuccIdx == 1) {
       Val = &Env.makeNot(*Val);
+      Assumption = false;
+    }
 
     Env.addToFlowCondition(*Val);
+    return {&Cond, Assumption};
   }
 
+  TypeErasedDataflowAnalysis &Analysis;
   const StmtToEnvMap &StmtToEnv;
   Environment &Env;
   int BlockSuccIdx;
   TransferOptions TransferOpts;
 };
 
 /// Holds data structures required for running dataflow analysis.
 struct AnalysisContext {
const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
         AC.BlockStates[Pred->getBlockID()];
     if (!MaybePredState)
       continue;
 
     TypeErasedDataflowAnalysisState PredState = MaybePredState.value();
     if (BuiltinTransferOpts) {
       if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
         const StmtToEnvMapImpl StmtToEnv(AC.CFCtx, AC.BlockStates);
-        TerminatorVisitor(StmtToEnv, PredState.Env,
+        auto [Cond, Assumption] =
+            TerminatorVisitor(Analysis, StmtToEnv, PredState.Env,
                               blockIndexInPredecessor(*Pred, Block),
                               *BuiltinTransferOpts)
                 .Visit(PredTerminatorStmt);
+        if (Cond)
+          Analysis.branchTransferTypeErased(Assumption, Cond, PredState.Lattice,
+                                            PredState.Env);
       }
     }
 
     if (MaybeState) {
       Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
       MaybeState->Env.join(PredState.Env, Analysis);
     } else {
       MaybeState = std::move(PredState);

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
   CFGMatchSwitchTest.cpp
   ChromiumCheckModelTest.cpp
   DataflowAnalysisContextTest.cpp
   DataflowEnvironmentTest.cpp
   DebugSupportTest.cpp
   MapLatticeTest.cpp
   MatchSwitchTest.cpp
   MultiVarConstantPropagationTest.cpp
+  SignAnalysisTest.cpp
   SingleVarConstantPropagationTest.cpp
+  SolverTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
   TransferTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
-  SolverTest.cpp
   UncheckedOptionalAccessModelTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests
   PRIVATE
   clangAnalysis
   clangAnalysisFlowSensitive
   clangAnalysisFlowSensitiveModels

clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp

+//===- unittests/Analysis/FlowSensitive/SignAnalysisTest.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 Sign Analysis as an example
+//  of a forward, monotonic dataflow analysis. The analysis tracks all
+//  variables in the scope, but lacks escape analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#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/Analysis/FlowSensitive/MapLattice.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 "llvm/Testing/Support/Error.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;
+
+// Models the signedness of a variable, for all paths through
+// the program.
+struct SignLattice {
+  enum class SignState : int {
+    Bottom,
+    Negative,
+    Zero,
+    Positive,
+    Top,
+  };
+  SignState State;
+
+  constexpr SignLattice() : State(SignState::Bottom) {}
+  constexpr SignLattice(int64_t V)
+      : State(V == 0 ? SignState::Zero
+                     : (V < 0 ? SignState::Negative : SignState::Positive)) {}
+  constexpr SignLattice(SignState S) : State(S) {}
+
+  static constexpr SignLattice bottom() {
+    return SignLattice(SignState::Bottom);
+  }
+  static constexpr SignLattice negative() {
+    return SignLattice(SignState::Negative);
+  }
+  static constexpr SignLattice zero() { return SignLattice(SignState::Zero); }
+  static constexpr SignLattice positive() {
+    return SignLattice(SignState::Positive);
+  }
+  static constexpr SignLattice top() { return SignLattice(SignState::Top); }
+
+  friend bool operator==(const SignLattice &Lhs, const SignLattice &Rhs) {
+    return Lhs.State == Rhs.State;
+  }
+  friend bool operator!=(const SignLattice &Lhs, const SignLattice &Rhs) {
+    return !(Lhs == Rhs);
+  }
+
+  LatticeJoinEffect join(const SignLattice &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 SignLattice &L) {
+  switch (L.State) {
+  case SignLattice::SignState::Bottom:
+    return OS << "Bottom";
+  case SignLattice::SignState::Negative:
+    return OS << "Negative";
+  case SignLattice::SignState::Zero:
+    return OS << "Zero";
+  case SignLattice::SignState::Positive:
+    return OS << "Positive";
+  case SignLattice::SignState::Top:
+    return OS << "Top";
+  }
+  llvm_unreachable("unknown SignState!");
+}
+
+using SignPropagationLattice = VarMapLattice<SignLattice>;
+
+constexpr char kDecl[] = "decl";
+constexpr char kVar[] = "var";
+constexpr char kRHSVar[] = "rhsvar";
+constexpr char kInit[] = "init";
+constexpr char kJustAssignment[] = "just-assignment";
+constexpr char kAssignment[] = "assignment";
+constexpr char kComparison[] = "comparison";
+constexpr char kRHS[] = "rhs";
+
+auto refToVar(StringRef V) { return declRefExpr(to(varDecl().bind(V))); }
+
+// N.B. This analysis is deliberately simplistic, leaving out many important
+// details needed for a real analysis. Most notably, the transfer function does
+// not account for the variable's address possibly escaping, which would
+// invalidate the analysis. It also could be optimized to drop out-of-scope
+// variables from the map.
+class SignPropagationAnalysis
+    : public DataflowAnalysis<SignPropagationAnalysis, SignPropagationLattice> {
+public:
+  explicit SignPropagationAnalysis(ASTContext &Context)
+      : DataflowAnalysis<SignPropagationAnalysis, SignPropagationLattice>(
+            Context) {}
+
+  static SignPropagationLattice initialElement() {
+    return SignPropagationLattice::bottom();
+  }
+
+  void branchTransfer(bool Branch, const Stmt *S, SignPropagationLattice &Vars,
+                      Environment &Env) {
+    auto matcher = binaryOperator(isComparisonOperator(),
+                                  hasLHS(hasDescendant(refToVar(kVar))),
+                                  hasRHS(expr().bind(kRHS)))
+                       .bind(kComparison);
+    ASTContext &Context = getASTContext();
+    auto Results = match(matcher, *S, Context);
+    if (Results.empty())
+      return;
+    const BoundNodes &Nodes = Results[0];
+
+    const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
+    assert(Var != nullptr);
+    if (const auto *BinOp =
+            Nodes.getNodeAs<clang::BinaryOperator>(kComparison)) {
+      const auto *RHS = Nodes.getNodeAs<clang::Expr>(kRHS);
+      assert(RHS != nullptr);
+
+      Expr::EvalResult R;
+      if (!(RHS->EvaluateAsInt(R, Context) && R.Val.isInt()))
+        return;
+      auto V = SignLattice(R.Val.getInt().getExtValue());
+      auto OpCode =
+          Branch ? BinOp->getOpcode()
+                 : BinaryOperator::negateComparisonOp(BinOp->getOpcode());
+      switch (OpCode) {
+      case BO_LT:
+        if (V == SignLattice::positive()) {
+          Vars[Var] = SignLattice::top();
+        } else {
+          // Var is less than 0 or a negative number.
+          Vars[Var] = SignLattice::negative();
+        }
+        break;
+      case BO_LE:
+        // Var is less than or equal to a negative number.
+        if (V == SignLattice::negative()) {
+          Vars[Var] = SignLattice::negative();
+        } else {
+          // Var is less than or equal to 0 or a positive number.
+          Vars[Var] = SignLattice::top();
+        }
+        break;
+      case BO_GT:
+        if (V == SignLattice::negative()) {
+          Vars[Var] = SignLattice::top();
+        } else {
+          // Var is greater than 0 or a positive number.
+          Vars[Var] = SignLattice::positive();
+        }
+        break;
+      case BO_GE:
+        // Var is greater than or equal to a positive number.
+        if (V == SignLattice::positive()) {
+          Vars[Var] = SignLattice::positive();
+        } else {
+          // Var is greater than or equal to 0 or a negative number.
+          Vars[Var] = SignLattice::top();
+        }
+        break;
+      case BO_EQ:
+        Vars[Var] = V;
+        break;
+      case BO_NE: // Noop.
+        break;
+      default:
+        llvm_unreachable("not implemented");
+      }
+    }
+  }
+
+  void transfer(const Stmt *S, SignPropagationLattice &Vars, Environment &Env) {
+    auto matcher = stmt(
+        anyOf(declStmt(hasSingleDecl(
+                  varDecl(decl().bind(kVar), hasType(isInteger()),
+                          optionally(hasInitializer(expr().bind(kInit))))
+                      .bind(kDecl))),
+              binaryOperator(hasOperatorName("="), hasLHS(refToVar(kVar)),
+                             hasRHS(hasDescendant(refToVar(kRHSVar))))
+                  .bind(kJustAssignment),
+              binaryOperator(isAssignmentOperator(), hasLHS(refToVar(kVar)))
+                  .bind(kAssignment)));
+
+    ASTContext &Context = getASTContext();
+    auto Results = match(matcher, *S, Context);
+    if (Results.empty())
+      return;
+    const BoundNodes &Nodes = Results[0];
+
+    const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
+    assert(Var != nullptr);
+
+    if (Nodes.getNodeAs<clang::VarDecl>(kDecl) != nullptr) {
+      if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
+        Expr::EvalResult R;
+        Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
+                        ? SignLattice(R.Val.getInt().getExtValue())
+                        : SignLattice::bottom();
+      } else {
+        // An unitialized variable holds *some* value, but we don't know what it
+        // is (it is implementation defined), so we set it to top.
+        Vars[Var] = SignLattice::top();
+      }
+      // Assign one variable to another.
+    } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
+      const auto *RHSVar = Nodes.getNodeAs<clang::VarDecl>(kRHSVar);
+      assert(RHSVar);
+      auto It = Vars.find(RHSVar);
+      if (It != Vars.end())
+        Vars[Var] = It->second;
+      else
+        Vars[Var] = SignLattice::top();
+      // Assign a constant to a variable.
+    } else if (const auto *BinOp =
+                   Nodes.getNodeAs<clang::BinaryOperator>(kAssignment)) {
+      const auto *RHS = BinOp->getRHS();
+      Expr::EvalResult R;
+      // Not a constant.
+      if (!(RHS->EvaluateAsInt(R, Context) && R.Val.isInt())) {
+        Vars[Var] = SignLattice::top();
+        return;
+      }
+      Vars[Var] = SignLattice(R.Val.getInt().getExtValue());
+    }
+  }
+};
+
+using ::testing::IsEmpty;
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+MATCHER_P(Var, name,
+          (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +
+           name + "`")
+              .str()) {
+  assert(isa<VarDecl>(arg));
+  return arg->getName() == name;
+}
+
+MATCHER(Bottom, "") { return arg == arg.bottom(); }
+MATCHER(Negative, "") { return arg == arg.negative(); }
+MATCHER(Zero, "") { return arg == arg.zero(); }
+MATCHER(Positive, "") { return arg == arg.positive(); }
+MATCHER(Top, "") { return arg == arg.top(); }
+
+MATCHER_P(HoldsSignLattice, m,
+          ((negation ? "doesn't hold" : "holds") +
+           llvm::StringRef(" a lattice element that ") +
+           ::testing::DescribeMatcher<SignPropagationLattice>(m, negation))
+              .str()) {
+  return ExplainMatchResult(m, arg.Lattice, result_listener);
+}
+
+template <typename Matcher>
+void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
+  ASSERT_THAT_ERROR(
+      test::checkDataflow<SignPropagationAnalysis>(
+          Code, "fun",
+          [](ASTContext &C, Environment &) {
+            return SignPropagationAnalysis(C);
+          },
+          [&Expectations](
+              llvm::ArrayRef<std::pair<
+                  std::string,
+                  DataflowAnalysisState<SignPropagationAnalysis::Lattice>>>
+                  Results,
+              ASTContext &) { EXPECT_THAT(Results, Expectations); },
+          {"-fsyntax-only", "-std=c++17"}),
+      llvm::Succeeded());
+}
+
+TEST(SignAnalysisTest, Init) {
+  std::string Code = R"(
+    void fun() {
+      int neg = -1;
+      int zero = 0;
+      int pos = 1;
+      int uninited;
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("neg"), Negative()),
+                                      Pair(Var("zero"), Zero()),
+                                      Pair(Var("pos"), Positive()),
+                                      Pair(Var("uninited"), Top()))))));
+}
+
+TEST(SignAnalysisTest, Assignment) {
+  std::string Code = R"(
+    void fun() {
+      int neg, zero, pos;
+      neg = -1;
+      zero = 0;
+      pos = 1;
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("neg"), Negative()),
+                                      Pair(Var("zero"), Zero()),
+                                      Pair(Var("pos"), Positive()))))));
+}
+
+TEST(SignAnalysisTest, InitToBottom) {
+  std::string Code = R"(
+    int foo();
+    void fun() {
+      int a = foo();
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Bottom()))))));
+}
+
+TEST(SignAnalysisTest, AssignmentAfterBottom) {
+  std::string Code = R"(
+    int foo();
+    void fun(bool b) {
+      int a = foo();
+      a = -1;
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative()))))));
+}
+
+TEST(SignAnalysisTest, GreaterThan) {
+  std::string Code = R"(
+    int foo();
+    void fun() {
+      int a = foo();
+      if (a > 0) {
+        (void)0;
+        // [[p]]
+      }
+      if (a > -1) {
+        (void)0;
+        // [[q]]
+      }
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Positive())))),
+                        Pair("q", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, GreaterThanIfElse) {
+  std::string Code = R"(
+    void fun(int a) {
+      if (a > 0) {
+        (void)1;
+        // [[p]]
+      } else {
+        (void)0;
+        // [[q]]
+      }
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Positive())))),
+                        Pair("q", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, LessThan) {
+  std::string Code = R"(
+    int foo();
+    void fun() {
+      int a = foo();
+      if (a < 0) {
+        (void)0;
+        // [[p]]
+      }
+      if (a < 1) {
+        (void)0;
+        // [[q]]
+      }
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative())))),
+                        Pair("q", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, LessThanIfElse) {
+  std::string Code = R"(
+    void fun(int a) {
+      if (a < 0) {
+        (void)1;
+        // [[p]]
+      } else {
+        (void)0;
+        // [[q]]
+      }
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative())))),
+                        Pair("q", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, Equality) {
+  std::string Code = R"(
+    int foo();
+    void fun() {
+      int a = foo();
+      if (a == -1) {
+        (void)0;
+        // [[n]]
+      }
+      if (a == 0) {
+        (void)0;
+        // [[z]]
+      }
+      if (a == 1) {
+        (void)0;
+        // [[p]]
+      }
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("n", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative())))),
+                        Pair("z", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Zero())))),
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Positive()))))));
+}
+
+TEST(SignAnalysisTest, SymbolicAssignment) {
+  std::string Code = R"(
+    int foo();
+    void fun() {
+      int a = foo();
+      int b = foo();
+      if (a < 0) {
+        b = a;
+        (void)0;
+        // [[p]]
+      }
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative()),
+                                      Pair(Var("b"), Negative()))))));
+}
+
+TEST(SignAnalysisTest, JoinToTop) {
+  std::string Code = R"(
+    int foo();
+    void fun(bool b) {
+      int a = foo();
+      if (b) {
+        a = -1;
+        (void)0;
+        // [[p]]
+      } else {
+        a = 1;
+        (void)0;
+        // [[q]]
+      }
+      (void)0;
+      // [[r]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative())))),
+                        Pair("q", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Positive())))),
+                        Pair("r", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, JoinToNeg) {
+  std::string Code = R"(
+    int foo();
+    void fun() {
+      int a = foo();
+      if (a < 1) {
+        a = -1;
+        (void)0;
+        // [[p]]
+      } else {
+        a = -1;
+        (void)0;
+        // [[q]]
+      }
+      (void)0;
+      // [[r]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative())))),
+                        Pair("q", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative())))),
+                        Pair("r", HoldsSignLattice(UnorderedElementsAre(
+                                      Pair(Var("a"), Negative()))))));
+}
+
+TEST(SignAnalysisTest, NestedIfs) {
+  std::string Code = R"(
+    int foo();
+    void fun() {
+      int a = foo();
+      if (a >= 0) {
+        (void)0;
+        // [[p]]
+        if (a == 0) {
+          (void)0;
+          // [[q]]
+        }
+      }
+      (void)0;
+      // [[r]]
+    }
+  )";
+  RunDataflow(
+      Code,
+      UnorderedElementsAre(
+          Pair("p",
+               HoldsSignLattice(UnorderedElementsAre(Pair(Var("a"), Top())))),
+          Pair("q",
+               HoldsSignLattice(UnorderedElementsAre(Pair(Var("a"), Zero())))),
+          Pair("r",
+               HoldsSignLattice(UnorderedElementsAre(Pair(Var("a"), Top()))))));
+}
+
+} // namespace
+} // namespace dataflow
+} // namespace clang

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

if (!Stmt)
       return;
     auto It = StmtToAnnotations.find(Stmt->getStmt());
     if (It == StmtToAnnotations.end())
       return;
     auto *Lattice =
         llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
     auto [_, InsertSuccess] =
         AnnotationStates.insert({It->second, StateT{*Lattice, State.Env}});
+    (void)_;
     (void)InsertSuccess;
     assert(InsertSuccess);
   };
   return checkDataflow<AnalysisT>(
       std::move(AI)
           .withSetupTest(std::move(SetupTest))
           .withPostVisitCFG(std::move(PostVisitCFG)),
       [&VerifyResults, &AnnotationStates](const AnalysisOutputs &AO) {