[clang][dataflow] Ensure well-formed flow conditions.

[ymandel]

Summary

Ensure that the expressions associated with terminators are associated with a
value. Otherwise, we can generate degenerate flow conditions, where both
branches share the same condition.

[sgatev]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

114–128

What does it mean for flow conditions to be mutually exclusive? Why is this a requirement?

125–138

Let's also add tests for these two paths.

[ymandel]

address comments; move tests to proper locations

[ymandel]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

125–138

Turns out this code was overkill -- the conditions are rvalues (even lvalues have an implicit cast inserted), so regardless of any pre-existing form, we should just replace it unconditionally with a simple boolean representation.

I've added a new test, though, for fields (vs the existing one for functions), which should exercise the path of Loc != nullptr, vs the function which (with current implementation) will exercise Loc == nullptr.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

110

I am still not convinced why would we ever need SkipPast, as the AST will always have the necessary LValueToRValue conversions when we need to look past references. But this is unrelated to this patch.

119

I think this get or create pattern is getting more and more widespread. At some point we might want a helper.

[ymandel]

add comments to tests.

[ymandel]

added fixme

[ymandel]

Thanks for the review!

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

110

Agreed. But, I tried to pull out the SkipPast and it crashed (hence the FIXME). I'll try to track down what's happening, but it may be related to our conflation of ReferenceValue for normal lvalues and reference-typed declarations. Regardless, we want to reconsider our treatment of the different value classes.

119

agreed. Added fixme.

[sgatev]

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

884

What does "abstract" mean here? Perhaps "arbitrary"?

[ymandel]

address comments

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/ErrorHandling.h"
 
 namespace clang {
 namespace dataflow {
 
 class StmtToEnvMapImpl : public StmtToEnvMap {
 public:
   StmtToEnvMapImpl(
       const ControlFlowContext &CFCtx,
public:
   }
 
 private:
   void extendFlowCondition(const Expr &Cond) {
     // The terminator sub-expression might not be evaluated.
     if (Env.getValue(Cond, SkipPast::None) == nullptr)
       transfer(StmtToEnv, Cond, Env);
 
+    // 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));
-    if (Val == nullptr)
-      return;
+    // 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);
+    }
 
     // The condition must be inverted for the successor that encompasses the
     // "else" branch, if such exists.
     if (BlockSuccIdx == 1)
       Val = &Env.makeNot(*Val);
 
     Env.addToFlowCondition(*Val);
   }
 
   const StmtToEnvMap &StmtToEnv;
   Environment &Env;
   int BlockSuccIdx;
 };
 
 /// Computes the input state for a given basic block by joining the output
 /// states of its predecessors.
 ///
 /// Requirements:
 ///

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

runDataflow(
         ASSERT_THAT(FooDecl, NotNull());
 
         const Environment &Env = Results[0].second.Env;
         auto *FooVal = cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
         EXPECT_TRUE(Env.flowConditionImplies(*FooVal));
       });
 }
 
+// Verifies that flow conditions are properly constructed even when the
+// condition is not meaningfully interpreted.
+//
+// Note: currently, abstract function calls are uninterpreted, so the test
+// exercises this case. If and when we change that, this test will not add to
+// coverage (although it may still test a valuable case).
+TEST_F(FlowConditionTest, OpaqueFlowConditionMergesToOpaqueBool) {
+  std::string Code = R"(
+    bool foo();
+
+    void target() {
+      bool Bar = true;
+      if (foo())
+        Bar = false;
+      (void)0;
+      /*[[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 *BarDecl = findValueDecl(ASTCtx, "Bar");
+        ASSERT_THAT(BarDecl, NotNull());
+
+        auto &BarVal =
+            *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::Reference));
+
+        EXPECT_FALSE(Env.flowConditionImplies(BarVal));
+      });
+}
+
+// Verifies that flow conditions are properly constructed even when the
+// condition is not meaningfully interpreted.
+//
+// Note: currently, fields with recursive type calls are uninterpreted (beneath
+// the first instance), so the test exercises this case. If and when we change
+// that, this test will not add to coverage (although it may still test a
+// valuable case).
+TEST_F(FlowConditionTest, OpaqueFieldFlowConditionMergesToOpaqueBool) {
+  std::string Code = R"(
+    struct Rec {
+      Rec* Next;
+    };
+
+    struct Foo {
+      Rec* X;
+    };
+
+    void target(Foo F) {
+      bool Bar = true;
+      if (F.X->Next)
+        Bar = false;
+      (void)0;
+      /*[[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 *BarDecl = findValueDecl(ASTCtx, "Bar");
+        ASSERT_THAT(BarDecl, NotNull());
+
+        auto &BarVal =
+            *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::Reference));
+
+        EXPECT_FALSE(Env.flowConditionImplies(BarVal));
+      });
+}
+
+// Verifies that flow conditions are properly constructed even when the
+// condition is not meaningfully interpreted. Adds to above by nesting the
+// interestnig case inside a normal branch. This protects against degenerate
+// solutions which only test for empty flow conditions, for example.
+TEST_F(FlowConditionTest, OpaqueFlowConditionInsideBranchMergesToOpaqueBool) {
+  std::string Code = R"(
+    bool foo();
+
+    void target(bool Cond) {
+      bool Bar = true;
+      if (Cond) {
+        if (foo())
+          Bar = false;
+        (void)0;
+        /*[[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 *BarDecl = findValueDecl(ASTCtx, "Bar");
+        ASSERT_THAT(BarDecl, NotNull());
+
+        auto &BarVal =
+            *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::Reference));
+
+        EXPECT_FALSE(Env.flowConditionImplies(BarVal));
+      });
+}
+
 } // namespace