[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

83–84

Please add a comment to RetTy.

153

CondValue?

258

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

153

Ok, changed to ConditionValue.

258

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

61–67

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

83–85

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.

262

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

263

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

29

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 {

32

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

87–89

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

121

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

124

EXPECT_THAT...

[martong]

clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp

10–12

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

83–85

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

165

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

165

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

static int blockIndexInPredecessor(const CFGBlock &Pred,
                                    const CFGBlock &Block) {
   auto BlockPos = llvm::find_if(
       Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
         return Succ && Succ->getBlockID() == Block.getBlockID();
       });
   return BlockPos - Pred.succ_begin();
 }
 
+// The return type of the visit functions in TerminatorVisitor. The first
+// element represents the terminator expression (that is the conditional
+// expression in case of a path split in the CFG). The second element
+// represents whether the condition was true or false.
+using TerminatorVisitorRetTy = std::pair<const Expr *, bool>;
+
 /// Extends the flow condition of an environment based on a terminator
 /// statement.
-class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> {
+class TerminatorVisitor
+    : public ConstStmtVisitor<TerminatorVisitor, TerminatorVisitorRetTy> {
 public:
-  TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
+  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) {
+  TerminatorVisitorRetTy VisitIfStmt(const IfStmt *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
-    extendFlowCondition(*Cond);
+    return extendFlowCondition(*Cond);
   }
 
-  void VisitWhileStmt(const WhileStmt *S) {
+  TerminatorVisitorRetTy VisitWhileStmt(const WhileStmt *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
-    extendFlowCondition(*Cond);
+    return extendFlowCondition(*Cond);
   }
 
-  void VisitDoStmt(const DoStmt *S) {
+  TerminatorVisitorRetTy VisitDoStmt(const DoStmt *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
-    extendFlowCondition(*Cond);
+    return extendFlowCondition(*Cond);
   }
 
-  void VisitForStmt(const ForStmt *S) {
+  TerminatorVisitorRetTy VisitForStmt(const ForStmt *S) {
     auto *Cond = S->getCond();
     if (Cond != nullptr)
-      extendFlowCondition(*Cond);
+      return extendFlowCondition(*Cond);
+    return {nullptr, false};
   }
 
-  void VisitBinaryOperator(const BinaryOperator *S) {
+  TerminatorVisitorRetTy 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) {
+  TerminatorVisitorRetTy
+  VisitConditionalOperator(const ConditionalOperator *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
-    extendFlowCondition(*Cond);
+    return extendFlowCondition(*Cond);
   }
 
 private:
-  void extendFlowCondition(const Expr &Cond) {
+  TerminatorVisitorRetTy 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 != nullptr)
+          // FIXME: 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

add_clang_unittest(ClangAnalysisFlowSensitiveTests
   MapLatticeTest.cpp
   MatchSwitchTest.cpp
   MultiVarConstantPropagationTest.cpp
   SignAnalysisTest.cpp
   SingleVarConstantPropagationTest.cpp
   SolverTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
+  TransferBranchTest.cpp
   TransferTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
   UncheckedOptionalAccessModelTest.cpp
   ValueTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests
   PRIVATE

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 test for the transferBranch function of the
+//  TypeErasedDataflowAnalysis.
+//
+//===----------------------------------------------------------------------===//
+
+#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::dataflow::test {
+namespace {
+
+using namespace ast_matchers;
+
+struct TestLattice {
+  llvm::Optional<bool> Branch;
+  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.Branch == Rhs.Branch;
+  }
+};
+
+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.Branch = Branch;
+  }
+};
+
+using ::testing::UnorderedElementsAre;
+
+template <typename Matcher>
+void runDataflow(llvm::StringRef Code, Matcher VerifyResults,
+                 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),
+      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,
+         const AnalysisOutputs &) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q"));
+
+        const TestLattice &LP = getLatticeAtAnnotation(Results, "p");
+        EXPECT_THAT(LP.Branch, Optional(true));
+
+        const TestLattice &LQ = getLatticeAtAnnotation(Results, "q");
+        EXPECT_THAT(LQ.Branch, Optional(false));
+      },
+      LangStandard::lang_cxx17);
+}
+
+} // namespace
+} // namespace clang::dataflow::test