[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

112–113

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

123–136

Let's also add tests for these two paths.

[ymandel]

address comments; move tests to proper locations

[ymandel]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

123–136

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.

117

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.

117

agreed. Added fixme.

[sgatev]

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

884 ↗

(On Diff #423693)

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);
 
     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. So, we need *some* value for the condition
+    // expression, even if just an atom.
+    if (Val == nullptr) {
+      Val = &Env.makeAtomicBoolValue();
+      QualType Type = Cond.getType();
+      assert(Type->isBooleanType() || Type->isReferenceType());
+      if (Type->isBooleanType()) {
+        auto &Loc = Env.createStorageLocation(Cond);
+        Env.setStorageLocation(Cond, Loc);
+        Env.setValue(Loc, *Val);
+      } else if (auto *CondVal = cast_or_null<ReferenceValue>(
+                     Env.getValue(Cond, SkipPast::None))) {
+        Env.setValue(CondVal->getPointeeLoc(), *Val);
+      } else {
+        QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType();
+        StorageLocation &PointeeLoc = Env.createStorageLocation(PointeeType);
+        Env.setValue(PointeeLoc, *Val);
+        auto *Loc = Env.getStorageLocation(Cond, SkipPast::None);
+        // `Cond` must have been processed already (and so must have an
+        // associated location) since it came from the predecessor block.
+        assert(Loc != nullptr);
+        Env.setValue(*Loc, Env.takeOwnership(
+                               std::make_unique<ReferenceValue>(PointeeLoc)));
+      }
+    }
 
     // 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);
   }

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
         EXPECT_FALSE(EnvThen.flowConditionImplies(BarValThen));
 
         auto &BarValElse =
             *cast<BoolValue>(EnvElse.getValue(*BarDecl, SkipPast::None));
         EXPECT_TRUE(EnvElse.flowConditionImplies(BarValElse));
       });
 }
 
+TEST_F(TransferTest, 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));
+      });
+}
+
+TEST_F(TransferTest, 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));
+      });
+}
+
 TEST_F(TransferTest, CorrelatedBranches) {
   std::string Code = R"(
     void target(bool B, bool C) {
       if (B) {
         return;
       }
       (void)0;
       /*[[p0]]*/