[clang][dataflow] Add equivalence relation for `Value` type.

[ymandel]

Summary

Defines an equivalence relation on the Value type to standardize several
places in the code where we replicate the ~same equivalence comparison.

[ymandel]

Reviewers: I'm inclined towards a method vs overloaded operator. Please let me know.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/Value.cpp

38

I started to wonder, is it always the case that we want properties to be part of the identity for values? Especially when we have multiple checks collaborating in the same fixed-point iteration, the properties added by one check might not be interesting for the others, and influencing what values are considered equal is a way to "leak" this information between checks.

Feel free to leave it as is for now, I just wanted to make sure we think about this at some point in the future :)

[xazax.hun]

In D135964#3858706, @ymandel wrote:

Reviewers: I'm inclined towards a method vs overloaded operator. Please let me know.

I don't have a strong preference. But in case we come up with multiple kinds of equalities (see my comment about the properties) methods might work better.

[ymandel]

switched to function, instead of operator.

[ymandel]

In D135964#3858783, @xazax.hun wrote:

In D135964#3858706, @ymandel wrote:

Reviewers: I'm inclined towards a method vs overloaded operator. Please let me know.

I don't have a strong preference. But in case we come up with multiple kinds of equalities (see my comment about the properties) methods might work better.

Agreed. I switched to a free function. I think operator== just implies too much.

clang/lib/Analysis/FlowSensitive/Value.cpp

38

Good point. This only occurred to me once I was writing it as an operator==. But, we don't do this in the current code and I think its premature. I've taken it out and updated the comment to reflect. We will need to consider this for the future.

[sgatev]

clang/lib/Analysis/FlowSensitive/Value.cpp

15

This seems unnecessary.

clang/unittests/Analysis/FlowSensitive/ValueTest.cpp

30

I suggest dropping the symmetry comment.

[ymandel]

address comments

clang/include/clang/Analysis/FlowSensitive/Value.h

void setProperty(llvm::StringRef Name, Value &Val) {
     Properties.insert_or_assign(Name, &Val);
   }
 
 private:
   Kind ValKind;
   llvm::StringMap<Value *> Properties;
 };
 
+/// An equivalence relation for values. It obeys reflexivity, symmetry and
+/// transitivity. It does *not* include comparison of `Properties`.
+///
+/// Computes equivalence for these subclasses:
+/// * ReferenceValue, PointerValue -- pointee locations are equal. Does not
+///   compute deep equality of `Value` at said location.
+/// * TopBoolValue -- both are `TopBoolValue`s.
+///
+/// Otherwise, falls back to pointer equality.
+bool areEquivalentValues(const Value &Val1, const Value &Val2);
+
 /// Models a boolean.
 class BoolValue : public Value {
 public:
   explicit BoolValue(Kind ValueKind) : Value(ValueKind) {}
 
   static bool classof(const Value *Val) {
     return Val->getKind() == Kind::TopBool ||
            Val->getKind() == Kind::AtomicBool ||

clang/lib/Analysis/FlowSensitive/CMakeLists.txt

 add_clang_library(clangAnalysisFlowSensitive
   ControlFlowContext.cpp
   DataflowAnalysisContext.cpp
   DataflowEnvironment.cpp
   Transfer.cpp
   TypeErasedDataflowAnalysis.cpp
+  Value.cpp
   WatchedLiteralsSolver.cpp
   DebugSupport.cpp
 
   LINK_LIBS
   clangAnalysis
   clangAST
   clangBasic
   )
 
 add_subdirectory(Models)

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
   for (auto &Entry : Map1) {
     auto It = Map2.find(Entry.first);
     if (It != Map2.end() && Entry.second == It->second)
       Result.insert({Entry.first, Entry.second});
   }
   return Result;
 }
 
-static bool areEquivalentIndirectionValues(Value *Val1, Value *Val2) {
-  if (auto *IndVal1 = dyn_cast<ReferenceValue>(Val1)) {
-    auto *IndVal2 = cast<ReferenceValue>(Val2);
-    return &IndVal1->getReferentLoc() == &IndVal2->getReferentLoc();
-  }
-  if (auto *IndVal1 = dyn_cast<PointerValue>(Val1)) {
-    auto *IndVal2 = cast<PointerValue>(Val2);
-    return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
-  }
-  return false;
-}
-
-/// Returns true if and only if `Val1` is equivalent to `Val2`.
-static bool equivalentValues(QualType Type, Value *Val1,
-                             const Environment &Env1, Value *Val2,
-                             const Environment &Env2,
-                             Environment::ValueModel &Model) {
-  return Val1 == Val2 || (isa<TopBoolValue>(Val1) && isa<TopBoolValue>(Val2)) ||
-         areEquivalentIndirectionValues(Val1, Val2) ||
-         Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2);
-}
-
 /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
 /// respectively, of the same type `Type`. Merging generally produces a single
 /// value that (soundly) approximates the two inputs, although the actual
 /// 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 (auto *Expr1 = dyn_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: add unit tests that cover this statement.
-  if (areEquivalentIndirectionValues(Val1, Val2)) {
-    return Val1;
-  }
-
   // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
   // returns false to avoid storing unneeded values in `DACtx`.
   if (Value *MergedVal = MergedEnv.createValue(Type))
     if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv))
       return MergedVal;
 
   return nullptr;
 }
for (auto &Entry : LocToVal) {
     Value *Val = Entry.second;
     assert(Val != nullptr);
 
     auto It = Other.LocToVal.find(Loc);
     if (It == Other.LocToVal.end())
       continue;
     assert(It->second != nullptr);
 
-    if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model))
+    if (!areEquivalentValues(*Val, *It->second) &&
+        !Model.compareEquivalent(Loc->getType(), *Val, *this, *It->second,
+                                 Other))
       return false;
   }
 
   return true;
 }
 
 LatticeJoinEffect Environment::join(const Environment &Other,
                                     Environment::ValueModel &Model) {
for (auto &Entry : LocToVal) {
     Value *Val = Entry.second;
     assert(Val != nullptr);
 
     auto It = Other.LocToVal.find(Loc);
     if (It == Other.LocToVal.end())
       continue;
     assert(It->second != nullptr);
 
-    if (Val == It->second ||
-        (isa<TopBoolValue>(Val) && isa<TopBoolValue>(It->second))) {
+    if (areEquivalentValues(*Val, *It->second)) {
       JoinedEnv.LocToVal.insert({Loc, Val});
       continue;
     }
 
     if (Value *MergedVal = mergeDistinctValues(
             Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model))
       JoinedEnv.LocToVal.insert({Loc, MergedVal});
   }

clang/lib/Analysis/FlowSensitive/Value.cpp

+//===-- Value.cpp -----------------------------------------------*- C++ -*-===//
+//
+// 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 support functions for the `Value` type.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/FlowSensitive/Value.h"
+#include "llvm/Support/Casting.h"
+#include <cassert>
+
+namespace clang {
+namespace dataflow {
+
+static bool areEquivalentIndirectionValues(const Value &Val1,
+                                           const Value &Val2) {
+  if (auto *IndVal1 = dyn_cast<ReferenceValue>(&Val1)) {
+    auto *IndVal2 = cast<ReferenceValue>(&Val2);
+    return &IndVal1->getReferentLoc() == &IndVal2->getReferentLoc();
+  }
+  if (auto *IndVal1 = dyn_cast<PointerValue>(&Val1)) {
+    auto *IndVal2 = cast<PointerValue>(&Val2);
+    return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
+  }
+  return false;
+}
+
+bool areEquivalentValues(const Value &Val1, const Value &Val2) {
+  return &Val1 == &Val2 || (Val1.getKind() == Val2.getKind() &&
+                            (isa<TopBoolValue>(&Val1) ||
+                             areEquivalentIndirectionValues(Val1, Val2)));
+}
+
+} // namespace dataflow
+} // namespace clang

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

add_clang_unittest(ClangAnalysisFlowSensitiveTests
   MultiVarConstantPropagationTest.cpp
   SingleVarConstantPropagationTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
   TransferTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
   SolverTest.cpp
   UncheckedOptionalAccessModelTest.cpp
+  ValueTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests
   PRIVATE
   clangAnalysis
   clangAnalysisFlowSensitive
   clangAnalysisFlowSensitiveModels
   clangAST

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

public:
   bool compareEquivalent(QualType Type, const Value &Val1,
                          const Environment &Env1, const Value &Val2,
                          const Environment &Env2) override {
     // Nothing to say about a value that does not model an `OptionalInt`.
     if (!Type->isRecordType() ||
         Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
       return false;
 
-    auto *Prop1  = Val1.getProperty("has_value");
+    auto *Prop1 = Val1.getProperty("has_value");
     auto *Prop2 = Val2.getProperty("has_value");
-    return Prop1 == Prop2 ||
-           (Prop1 != nullptr && Prop2 != nullptr && isa<TopBoolValue>(Prop1) &&
-            isa<TopBoolValue>(Prop2));
+    assert(Prop1 != nullptr && Prop2 != nullptr);
+    return areEquivalentValues(*Prop1, *Prop2);
   }
 
   bool merge(QualType Type, const Value &Val1, const Environment &Env1,
              const Value &Val2, const Environment &Env2, Value &MergedVal,
              Environment &MergedEnv) override {
     // Nothing to say about a value that does not model an `OptionalInt`.
     if (!Type->isRecordType() ||
         Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")

clang/unittests/Analysis/FlowSensitive/ValueTest.cpp

+//===- unittests/Analysis/FlowSensitive/ValueTest.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/FlowSensitive/Value.h"
+#include "clang/Analysis/FlowSensitive/StorageLocation.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <memory>
+
+namespace {
+
+using namespace clang;
+using namespace dataflow;
+
+TEST(ValueTest, EquivalenceReflexive) {
+  StructValue V;
+  EXPECT_TRUE(areEquivalentValues(V, V));
+}
+
+TEST(ValueTest, AliasedReferencesEquivalent) {
+  auto L = ScalarStorageLocation(QualType());
+  ReferenceValue V1(L);
+  ReferenceValue V2(L);
+  EXPECT_TRUE(areEquivalentValues(V1, V2));
+  // Symmetry.
+  EXPECT_TRUE(areEquivalentValues(V2, V1));
+}
+
+TEST(ValueTest, AliasedPointersEquivalent) {
+  auto L = ScalarStorageLocation(QualType());
+  PointerValue V1(L);
+  PointerValue V2(L);
+  EXPECT_TRUE(areEquivalentValues(V1, V2));
+  // Symmetry.
+  EXPECT_TRUE(areEquivalentValues(V2, V1));
+}
+
+TEST(ValueTest, TopsEquivalent) {
+  TopBoolValue V1;
+  TopBoolValue V2;
+  EXPECT_TRUE(areEquivalentValues(V1, V2));
+  // Symmetry.
+  EXPECT_TRUE(areEquivalentValues(V2, V1));
+}
+
+TEST(ValueTest, EquivalentValuesWithDifferentPropsEquivalent) {
+  TopBoolValue Prop1;
+  TopBoolValue Prop2;
+  TopBoolValue V1;
+  TopBoolValue V2;
+  V1.setProperty("foo", Prop1);
+  V2.setProperty("bar", Prop2);
+  EXPECT_TRUE(areEquivalentValues(V1, V2));
+  // Symmetry.
+  EXPECT_TRUE(areEquivalentValues(V2, V1));
+}
+
+TEST(ValueTest, DifferentKindsNotEquivalent) {
+  auto L = ScalarStorageLocation(QualType());
+  ReferenceValue V1(L);
+  TopBoolValue V2;
+  EXPECT_FALSE(areEquivalentValues(V1, V2));
+  // Symmetry.
+  EXPECT_FALSE(areEquivalentValues(V2, V1));
+}
+
+TEST(ValueTest, NotAliasedReferencesNotEquivalent) {
+  auto L1 = ScalarStorageLocation(QualType());
+  ReferenceValue V1(L1);
+  auto L2 = ScalarStorageLocation(QualType());
+  ReferenceValue V2(L2);
+  EXPECT_FALSE(areEquivalentValues(V1, V2));
+  // Symmetry.
+  EXPECT_FALSE(areEquivalentValues(V2, V1));
+}
+
+TEST(ValueTest, NotAliasedPointersNotEquivalent) {
+  auto L1 = ScalarStorageLocation(QualType());
+  PointerValue V1(L1);
+  auto L2 = ScalarStorageLocation(QualType());
+  PointerValue V2(L2);
+  EXPECT_FALSE(areEquivalentValues(V1, V2));
+  // Symmetry.
+  EXPECT_FALSE(areEquivalentValues(V2, V1));
+}
+
+} // namespace