[clang][dataflow] Add support for nested composite bool expressions

[sgatev]

Summary

This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

516

Could you elaborate on when would this happen? I'd expect the traversal to always visit the predecessor basic blocks first and within a basic block always visit subexpressions first. So I'd be quite surprised if there is a subexpression we did not visit.

[sgatev]

Address reviewers' comments.

[sgatev]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

516

From what I've seen, logic operators influence the structure of the CFG through additional basic blocks and terminators, but their sub-expression operators are not added directly in the basic blocks.

For example:

void test(bool a, bool b, bool c) {
    bool d = a && (b || c);
}

results in:

void test(bool a, bool b, bool c)
 [B5 (ENTRY)]
   Succs (1): B4

 [B1]
   1: [B4.2] && ([B3.2] || [B2.2])
   2: bool d = a && (b || c);
   Preds (3): B2 B3 B4
   Succs (1): B0

 [B2]
   1: c
   2: [B2.1] (ImplicitCastExpr, LValueToRValue, _Bool)
   Preds (1): B3
   Succs (1): B1

 [B3]
   1: b
   2: [B3.1] (ImplicitCastExpr, LValueToRValue, _Bool)
   T: [B3.2] || ...
   Preds (1): B4
   Succs (2): B1 B2

 [B4]
   1: a
   2: [B4.1] (ImplicitCastExpr, LValueToRValue, _Bool)
   T: [B4.2] && ...
   Preds (1): B5
   Succs (2): B3 B1

 [B0 (EXIT)]
   Preds (1): B1

So, when we evaluate a && (b || c) in B1, the sub-expression b || c has not been evaluated yet. I updated the comment in the code to make that more clear.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

516

I understand the structure of the CFG and also understand that certain subexpressions are in different basic blocks. But I still don't understand why would b || c be not evaluated when we evaluate a && (b || c).

The operator && in your example is evaluated in B1. The operator || is evaluated in B3. B3 is a predecessor of B1, so if we process the CFG in reverse-post order, we should visit B3 before B1.

I am pretty sure if the traversal is well-written we should have the || evaluated before we visit B1.

I suspect that something different might be going on. Is it possible that you want to evaluate the && in B4?

Note that && is a terminator there because of the short-circuiting. So at that point we should NOT ask for the value of ||.

[sgatev]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

516

The operator || is evaluated in B3.

I don't think that's the case. Similar to your observation about && being a terminator in B4, I believe that || is a terminator in B3.

I interpret B3 as the "a is true" branch. It still doesn't contain information about b and c which might be subject to short-circuiting.

Does that make sense?

[xazax.hun]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

516

Oh, I see now! Sorry, I somehow assumed Visit is recursive. But you only visit the top level operator not the whole subexpression. Yeah, I understand now, thanks! This looks good to me.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

 }
 
 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
 public:
   TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env)
       : StmtToEnv(StmtToEnv), Env(Env) {}
 
   void VisitBinaryOperator(const BinaryOperator *S) {
-    switch (S->getOpcode()) {
-    case BO_Assign: {
-      // The CFG does not contain `ParenExpr` as top-level statements in basic
-      // blocks, however sub-expressions can still be of that type.
-      assert(S->getLHS() != nullptr);
-      const Expr *LHS = S->getLHS()->IgnoreParens();
-
-      assert(LHS != nullptr);
-      auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
-      if (LHSLoc == nullptr)
-        break;
 
-      // The CFG does not contain `ParenExpr` as top-level statements in basic
-      // blocks, however sub-expressions can still be of that type.
-      assert(S->getRHS() != nullptr);
-      const Expr *RHS = S->getRHS()->IgnoreParens();
-
-      assert(RHS != nullptr);
-      Value *RHSVal = Env.getValue(*RHS, SkipPast::Reference);
+
+    switch (S->getOpcode()) {
+    case BO_Assign: {
+      auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
+      if (LHSLoc == nullptr)
+        break;
+
+      auto *RHSVal = Env.getValue(*RHS, SkipPast::Reference);
       if (RHSVal == nullptr)
         break;
 
       // Assign a value to the storage location of the left-hand side.
       Env.setValue(*LHSLoc, *RHSVal);
 
       // Assign a storage location for the whole expression.
       Env.setStorageLocation(*S, *LHSLoc);
       break;
     }
     case BO_LAnd:
     case BO_LOr: {
-      const Expr *LHS = S->getLHS();
-      assert(LHS != nullptr);
-
-      const Expr *RHS = S->getRHS();
-      assert(RHS != nullptr);
-
-      BoolValue *LHSVal =
-          dyn_cast_or_null<BoolValue>(Env.getValue(*LHS, SkipPast::Reference));
-
-      // `RHS` and `S` might be part of different basic blocks. We need to
-      // access their values from the corresponding environments.
-      BoolValue *RHSVal = nullptr;
-      const Environment *RHSEnv = StmtToEnv.getEnvironment(*RHS);
-      if (RHSEnv != nullptr)
-        RHSVal = dyn_cast_or_null<BoolValue>(
-            RHSEnv->getValue(*RHS, SkipPast::Reference));
-
-      // Create fresh values for unknown boolean expressions.
-      // FIXME: Consider providing a `GetOrCreateFresh` util in case this style
-      // is expected to be common or make sure that all expressions are assigned
-      // values and drop this.
-      if (LHSVal == nullptr)
-        LHSVal = &Env.takeOwnership(std::make_unique<AtomicBoolValue>());
-      if (RHSVal == nullptr)
-        RHSVal = &Env.takeOwnership(std::make_unique<AtomicBoolValue>());
+      BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
+      BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
 
       auto &Loc = Env.createStorageLocation(*S);
       Env.setStorageLocation(*S, Loc);
       if (S->getOpcode() == BO_LAnd)
-        Env.setValue(Loc, Env.makeAnd(*LHSVal, *RHSVal));
+        Env.setValue(Loc, Env.makeAnd(LHSVal, RHSVal));
       else
-        Env.setValue(Loc, Env.makeOr(*LHSVal, *RHSVal));
+        Env.setValue(Loc, Env.makeOr(LHSVal, RHSVal));
       break;
     }
     default:
       // FIXME: Add support for BO_EQ, BO_NE.
       break;
     }
   }
 
public:
 
   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
     auto &Loc = Env.createStorageLocation(*S);
     Env.setStorageLocation(*S, Loc);
     Env.setValue(Loc, Env.getBoolLiteralValue(S->getValue()));
   }
 
 private:
+  BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
+    // `SubExpr` and its parent logic operator might be part of different basic
+    // blocks. We try to access the value that is assigned to `SubExpr` in the
+    // corresponding environment.
+    if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) {
+      if (auto *Val = dyn_cast_or_null<BoolValue>(
+              SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
+        return *Val;
+    }
+
+    // Sub-expressions that are logic operators are not added in basic blocks
+    // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
+    // operator, it isn't evaluated and assigned a value yet. In that case, we
+    // need to first visit `SubExpr` and then try to get the value that gets
+    // assigned to it.
+    Visit(&SubExpr);
+    if (auto *Val = dyn_cast_or_null<BoolValue>(
+            Env.getValue(SubExpr, SkipPast::Reference)))
+      return *Val;
+
+    // If the value of `SubExpr` is still unknown, we create a fresh symbolic
+    // boolean value for it.
+    return Env.makeAtomicBoolValue();
+  }
+
   const StmtToEnvMap &StmtToEnv;
   Environment &Env;
 };
 
 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
   assert(!isa<ParenExpr>(&S));
   TransferVisitor(StmtToEnv, Env).Visit(&S);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                     Env.getValue(*BarDecl, SkipPast::None));
                 ASSERT_THAT(BarVal, NotNull());
 
                 EXPECT_EQ(FooVal, &Env.getBoolLiteralValue(true));
                 EXPECT_EQ(BarVal, &Env.getBoolLiteralValue(false));
               });
 }
 
-TEST_F(TransferTest, AssignFromBoolConjunction) {
+TEST_F(TransferTest, AssignFromCompositeBoolExpression) {
+  {
     std::string Code = R"(
-    void target(bool Foo, bool Bar) {
-      bool Baz = (Foo) && (Bar);
+    void target(bool Foo, bool Bar, bool Qux) {
+      bool Baz = (Foo) && (Bar || Qux);
       // [[p]]
     }
   )";
     runDataflow(
         Code, [](llvm::ArrayRef<
                      std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                      Results,
                  ASTContext &ASTCtx) {
           ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
           const Environment &Env = Results[0].second.Env;
 
           const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
           ASSERT_THAT(FooDecl, NotNull());
 
-        const auto *FooVal =
-            dyn_cast_or_null<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+          const auto *FooVal = dyn_cast_or_null<BoolValue>(
+              Env.getValue(*FooDecl, SkipPast::None));
           ASSERT_THAT(FooVal, NotNull());
 
           const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
           ASSERT_THAT(BarDecl, NotNull());
 
-        const auto *BarVal =
-            dyn_cast_or_null<BoolValue>(Env.getValue(*BarDecl, SkipPast::None));
+          const auto *BarVal = dyn_cast_or_null<BoolValue>(
+              Env.getValue(*BarDecl, SkipPast::None));
           ASSERT_THAT(BarVal, NotNull());
 
+          const ValueDecl *QuxDecl = findValueDecl(ASTCtx, "Qux");
+          ASSERT_THAT(QuxDecl, NotNull());
+
+          const auto *QuxVal = dyn_cast_or_null<BoolValue>(
+              Env.getValue(*QuxDecl, SkipPast::None));
+          ASSERT_THAT(QuxVal, NotNull());
+
           const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
           ASSERT_THAT(BazDecl, NotNull());
 
           const auto *BazVal = dyn_cast_or_null<ConjunctionValue>(
               Env.getValue(*BazDecl, SkipPast::None));
           ASSERT_THAT(BazVal, NotNull());
-
           EXPECT_EQ(&BazVal->getLeftSubValue(), FooVal);
-        EXPECT_EQ(&BazVal->getRightSubValue(), BarVal);
+
+          const auto *BazRightSubValVal =
+              cast<DisjunctionValue>(&BazVal->getRightSubValue());
+          EXPECT_EQ(&BazRightSubValVal->getLeftSubValue(), BarVal);
+          EXPECT_EQ(&BazRightSubValVal->getRightSubValue(), QuxVal);
         });
   }
 
-TEST_F(TransferTest, AssignFromBoolDisjunction) {
+  {
     std::string Code = R"(
-    void target(bool Foo, bool Bar) {
-      bool Baz = (Foo) || (Bar);
+    void target(bool Foo, bool Bar, bool Qux) {
+      bool Baz = (Foo && Qux) || (Bar);
       // [[p]]
     }
   )";
     runDataflow(
         Code, [](llvm::ArrayRef<
                      std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                      Results,
                  ASTContext &ASTCtx) {
           ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
           const Environment &Env = Results[0].second.Env;
 
           const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
           ASSERT_THAT(FooDecl, NotNull());
 
-        const auto *FooVal =
-            dyn_cast_or_null<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+          const auto *FooVal = dyn_cast_or_null<BoolValue>(
+              Env.getValue(*FooDecl, SkipPast::None));
           ASSERT_THAT(FooVal, NotNull());
 
           const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
           ASSERT_THAT(BarDecl, NotNull());
 
-        const auto *BarVal =
-            dyn_cast_or_null<BoolValue>(Env.getValue(*BarDecl, SkipPast::None));
+          const auto *BarVal = dyn_cast_or_null<BoolValue>(
+              Env.getValue(*BarDecl, SkipPast::None));
           ASSERT_THAT(BarVal, NotNull());
 
+          const ValueDecl *QuxDecl = findValueDecl(ASTCtx, "Qux");
+          ASSERT_THAT(QuxDecl, NotNull());
+
+          const auto *QuxVal = dyn_cast_or_null<BoolValue>(
+              Env.getValue(*QuxDecl, SkipPast::None));
+          ASSERT_THAT(QuxVal, NotNull());
+
           const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
           ASSERT_THAT(BazDecl, NotNull());
 
           const auto *BazVal = dyn_cast_or_null<DisjunctionValue>(
               Env.getValue(*BazDecl, SkipPast::None));
           ASSERT_THAT(BazVal, NotNull());
 
-        EXPECT_EQ(&BazVal->getLeftSubValue(), FooVal);
+          const auto *BazLeftSubValVal =
+              cast<ConjunctionValue>(&BazVal->getLeftSubValue());
+          EXPECT_EQ(&BazLeftSubValVal->getLeftSubValue(), FooVal);
+          EXPECT_EQ(&BazLeftSubValVal->getRightSubValue(), QuxVal);
+
           EXPECT_EQ(&BazVal->getRightSubValue(), BarVal);
         });
   }
+}
 
 TEST_F(TransferTest, AssignFromBoolNegation) {
   std::string Code = R"(
     void target() {
       bool Foo = true;
       bool Bar = !(Foo);
       // [[p]]
     }