[clang][dataflow] Fix bug in joining bool values.

[ymandel]

Summary

Currently, the code assumes that all boolean-typed values are an instance of
BoolValue (or its subclasses). Yet, lvalues violate this assumption. This
patch drops the assumption and strengthens the check to confirm the shape of
both values being joined.

The patch also notes as FIXMES a number of problems discovered fixing this bug.

[gribozavr2]

LGTM!

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 /// meaning depends on `Model`.
 static Value *mergeDistinctValues(QualType Type, Value &Val1,
                                   const Environment &Env1, Value &Val2,
                                   const Environment &Env2,
                                   Environment &MergedEnv,
                                   Environment::ValueModel &Model) {
   // Join distinct boolean values preserving information about the constraints
   // in the respective path conditions.
-  if (Type->isBooleanType()) {
-    // FIXME: The type check above is a workaround and should be unnecessary.
-    // However, right now we can end up with BoolValue's in integer-typed
-    // variables due to our incorrect handling of boolean-to-integer casts (we
-    // just propagate the BoolValue to the result of the cast). For example:
+  if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) {
+    // FIXME: Checking both values should be unnecessary, since they should have
+    // a consistent shape.  However, right now we can end up with BoolValue's in
+    // integer-typed variables due to our incorrect handling of
+    // boolean-to-integer casts (we just propagate the BoolValue to the result
+    // of the cast). So, a join can encounter an integer in one branch but a
+    // bool in the other.
+    // For example:
+    // ```
     // std::optional<bool> o;
-    //
-    //
     // int x;
-    // if (o.has_value()) {
+    // if (o.has_value())
     //   x = o.value();
-    // }
+    // ```
     auto *Expr1 = cast<BoolValue>(&Val1);
     auto *Expr2 = cast<BoolValue>(&Val2);
     auto &MergedVal = MergedEnv.makeAtomicBoolValue();
     MergedEnv.addToFlowCondition(MergedEnv.makeOr(
         MergedEnv.makeAnd(Env1.getFlowConditionToken(),
                           MergedEnv.makeIff(MergedVal, *Expr1)),
         MergedEnv.makeAnd(Env2.getFlowConditionToken(),
                           MergedEnv.makeIff(MergedVal, *Expr2))));
     return &MergedVal;
   }
 
   // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
   // returns false to avoid storing unneeded values in `DACtx`.
+  // FIXME: Creating the value based on the type alone creates misshapen values
+  // for lvalues, since the type does not reflect the need for `ReferenceValue`.
   if (Value *MergedVal = MergedEnv.createValue(Type))
     if (Model.merge(Type, Val1, Env1, Val2, Env2, *MergedVal, MergedEnv))
       return MergedVal;
 
   return nullptr;
 }
 
 // When widening does not change `Current`, return value will equal `&Prev`.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

return unpackBinaryBoolValue<BiconditionalValue>(Env, V,
                                                      &Environment::makeIff);
   }
   llvm_unreachable("All reachable cases in switch return");
 }
 
 // Unpacks the value (if any) associated with `E` and updates `E` to the new
 // value, if any unpacking occured.
 static Value *maybeUnpackLValueExpr(const Expr &E, Environment &Env) {
+  // FIXME: this is too flexible: it _allows_ a reference, while it should
+  // _require_ one, since lvalues should always be wrapped in `ReferenceValue`.
   auto *Loc = Env.getStorageLocation(E, SkipPast::Reference);
   if (Loc == nullptr)
     return nullptr;
   auto *Val = Env.getValue(*Loc);
 
   auto *B = dyn_cast_or_null<BoolValue>(Val);
   if (B == nullptr)
     return Val;

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

std::string Code = R"(
     }
   )";
   auto Res = runAnalysis<NonConvergingAnalysis>(
       Code, [](ASTContext &C) { return NonConvergingAnalysis(C); });
   EXPECT_EQ(llvm::toString(Res.takeError()),
             "maximum number of iterations reached");
 }
 
+// Regression test for joins of bool-typed lvalue expressions. The first loop
+// results in two passes through the code that follows. Each pass results in a
+// different `ReferenceValue` for the pointee of `v`. Then, the second loop
+// causes a join at the loop head where the two environments map expresssion
+// `*v` to different `ReferenceValue`s.
+//
+// An earlier version crashed for this condition (for boolean-typed lvalues), so
+// this test only verifies that the analysis runs successfully, without
+// examining any details of the results.
+TEST(DataflowAnalysisTest, JoinBoolLValues) {
+  std::string Code = R"(
+    void target() {
+      for (int x = 1; x; x = 0)
+        (void)x;
+      bool *v;
+      if (*v)
+        for (int x = 1; x; x = 0)
+          (void)x;
+    }
+  )";
+  ASSERT_THAT_ERROR(
+      runAnalysis<NoopAnalysis>(Code,
+                                [](ASTContext &C) {
+                                  auto EnableBuiltIns = DataflowAnalysisOptions{
+                                      DataflowAnalysisContext::Options{}};
+                                  return NoopAnalysis(C, EnableBuiltIns);
+                                })
+          .takeError(),
+      llvm::Succeeded());
+}
+
 struct FunctionCallLattice {
   using FunctionSet = llvm::SmallSet<std::string, 8>;
   FunctionSet CalledFunctions;
 
   bool operator==(const FunctionCallLattice &Other) const {
     return CalledFunctions == Other.CalledFunctions;
   }