[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

115

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–81

Please add a comment to RetTy.

149

CondValue?

254

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 ↗

(On Diff #459451)

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 ↗

(On Diff #459451)

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

115

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

149

Ok, changed to ConditionValue.

254

Ok, I've added a TODO.

clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp

241 ↗

(On Diff #459451)

I am moving the sign analysis out of this patch.

586 ↗

(On Diff #459451)

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

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

[ymandel]

Overall, looks quite good.

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

87–88

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

78–79

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.

258

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

259

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

28

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

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

86–88

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

120

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

123

EXPECT_THAT...

[martong]

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

9–11

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–79

Ok, I hoisted this to be TerminatorVisitorRetTy.

[martong]

• Address ymandel's comments

[ymandel]

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

74

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

[martong]

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

74

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

[martong]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

161

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

161

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

 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 namespace dataflow {
 
+template <typename AnalysisT, typename LatticeT, typename = std::void_t<>>
+struct HasTransferBranchFor : std::false_type {};
+
+template <typename AnalysisT, typename LatticeT>
+struct HasTransferBranchFor<
+    AnalysisT, LatticeT,
+    std::void_t<decltype(std::declval<AnalysisT>().transferBranch(
+        std::declval<bool>(), std::declval<const Stmt *>(),
+        std::declval<LatticeT &>(), std::declval<Environment &>()))>>
+    : std::true_type {};
 /// Base class template for dataflow analyses built on a single lattice type.
 ///
 /// Requirements:
 ///
 ///  `Derived` must be derived from a specialization of this class template and
 ///  must provide the following public members:
 ///   * `LatticeT initialElement()` - returns a lattice element that models the
 ///     initial state of a basic block;
public:
   }
 
   void transferTypeErased(const CFGElement *Element, TypeErasedLattice &E,
                           Environment &Env) final {
     Lattice &L = llvm::any_cast<Lattice &>(E.Value);
     static_cast<Derived *>(this)->transfer(Element, L, Env);
   }
 
+  void transferBranchTypeErased(bool Branch, const Stmt *Stmt,
+                                TypeErasedLattice &E, Environment &Env) final {
+    if constexpr (HasTransferBranchFor<Derived, LatticeT>::value) {
+      Lattice &L = llvm::any_cast<Lattice &>(E.Value);
+      static_cast<Derived *>(this)->transferBranch(Branch, Stmt, L, Env);
+    }
+    // Silence unused parameter warnings.
+    (void)Branch;
+    (void)Stmt;
+  }
+
 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;
 
+  /// Applies the analysis transfer function for a given edge from a
+  /// CFG block of a conditional statement.
+  /// @param Stmt The condition which is responsible for the split in the CFG.
+  /// @param Branch True if the edge goes to the basic block where the
+  /// condition is true.
+  virtual void transferBranchTypeErased(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;
   }
 };
 

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,
+  // The return type of the visit functions.
+  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 ConditionValue = 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);
+      ConditionValue = false;
+    }
 
     Env.addToFlowCondition(*Val);
+    return {&Cond, ConditionValue};
   }
 
+  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, CondValue] =
+            TerminatorVisitor(Analysis, StmtToEnv, PredState.Env,
                               blockIndexInPredecessor(*Pred, Block),
                               *BuiltinTransferOpts)
                 .Visit(PredTerminatorStmt);
+        if (Cond)
+          // TODO Call transferBranchTypeErased even if BuiltinTransferOpts are
+          // not set.
+          Analysis.transferBranchTypeErased(CondValue, 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
+  TransferBranchTest.cpp
   SingleVarConstantPropagationTest.cpp
+  SolverTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
   TransferTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
-  SolverTest.cpp
   UncheckedOptionalAccessModelTest.cpp
   ValueTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests
   PRIVATE
   clangAnalysis
   clangAnalysisFlowSensitive

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) {

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.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/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Testing/Support/Annotations.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace dataflow {
+namespace {
+using namespace ast_matchers;
+using namespace test;
+
+struct TestLattice {
+  enum class Branch : int { True, False };
+  llvm::Optional<Branch> TheBranch;
+  static TestLattice bottom() { return {}; }
+
+  // Does not matter for this test, but we must provide some definition of join.
+  LatticeJoinEffect join(const TestLattice &Other) {
+    return LatticeJoinEffect::Unchanged;
+  }
+  friend bool operator==(const TestLattice &Lhs, const TestLattice &Rhs) {
+    return Lhs.TheBranch == Rhs.TheBranch;
+  }
+};
+
+class TestPropagationAnalysis
+    : public DataflowAnalysis<TestPropagationAnalysis, TestLattice> {
+public:
+  explicit TestPropagationAnalysis(ASTContext &Context)
+      : DataflowAnalysis<TestPropagationAnalysis, TestLattice>(Context) {}
+  static TestLattice initialElement() { return TestLattice::bottom(); }
+  void transfer(const CFGElement *, TestLattice &, Environment &) {}
+  void transferBranch(bool Branch, const Stmt *S, TestLattice &L,
+                      Environment &Env) {
+    L.TheBranch =
+        Branch ? TestLattice::Branch::True : TestLattice::Branch::False;
+  }
+};
+
+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;
+}
+
+template <typename Matcher>
+void runDataflow(llvm::StringRef Code, Matcher Match,
+                 LangStandard::Kind Std = LangStandard::lang_cxx17,
+                 llvm::StringRef TargetFun = "fun") {
+  using ast_matchers::hasName;
+  ASSERT_THAT_ERROR(
+      checkDataflow<TestPropagationAnalysis>(
+          AnalysisInputs<TestPropagationAnalysis>(
+              Code, hasName(TargetFun),
+              [](ASTContext &C, Environment &) {
+                return TestPropagationAnalysis(C);
+              })
+              .withASTBuildArgs(
+                  {"-fsyntax-only", "-fno-delayed-template-parsing",
+                   "-std=" +
+                       std::string(LangStandard::getLangStandardForKind(Std)
+                                       .getName())}),
+          /*VerifyResults=*/
+          [&Match](const llvm::StringMap<DataflowAnalysisState<TestLattice>>
+                       &Results,
+                   const AnalysisOutputs &AO) { Match(Results, AO.ASTCtx); }),
+      llvm::Succeeded());
+}
+
+template <typename LatticeT>
+const LatticeT &getLatticeAtAnnotation(
+    const llvm::StringMap<DataflowAnalysisState<LatticeT>> &AnnotationStates,
+    llvm::StringRef Annotation) {
+  auto It = AnnotationStates.find(Annotation);
+  assert(It != AnnotationStates.end());
+  return It->getValue().Lattice;
+}
+
+TEST(TransferBranchTest, IfElse) {
+  std::string Code = R"(
+    void fun(int a) {
+      if (a > 0) {
+        (void)1;
+        // [[p]]
+      } else {
+        (void)0;
+        // [[q]]
+      }
+    }
+  )";
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<TestLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q"));
+
+        const TestLattice &LP = getLatticeAtAnnotation(Results, "p");
+        EXPECT_TRUE(LP.TheBranch == TestLattice::Branch::True);
+
+        const TestLattice &LQ = getLatticeAtAnnotation(Results, "q");
+        EXPECT_TRUE(LQ.TheBranch == TestLattice::Branch::False);
+      },
+      LangStandard::lang_cxx17);
+}
+
+} // namespace
+} // namespace dataflow
+} // namespace clang