diff --git a/clang/include/clang/Analysis/FlowSensitive/Value.h b/clang/include/clang/Analysis/FlowSensitive/Value.h --- a/clang/include/clang/Analysis/FlowSensitive/Value.h +++ b/clang/include/clang/Analysis/FlowSensitive/Value.h @@ -72,11 +72,24 @@ Properties.insert_or_assign(Name, &Val); } + /// Computes structural equality for these subclasses: + /// * ReferenceValue, PointerValue -- pointee locations are equal. Does not + /// compute deep equality of `Value` at said location. + /// * TopBoolValue -- both are `TopBoolValue`s. + /// + /// Obeys reflexivity, symmetry and transitivity, including comparison of + /// `Properties`. + friend bool operator==(const Value &Val1, const Value &Val2); + private: Kind ValKind; llvm::StringMap Properties; }; +inline bool operator!=(const Value &Val1, const Value &Val2) { + return !(Val1 == Val2); +} + /// Models a boolean. class BoolValue : public Value { public: diff --git a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt --- a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt @@ -4,6 +4,7 @@ DataflowEnvironment.cpp Transfer.cpp TypeErasedDataflowAnalysis.cpp + Value.cpp WatchedLiteralsSolver.cpp DebugSupport.cpp diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -49,28 +49,6 @@ return Result; } -static bool areEquivalentIndirectionValues(Value *Val1, Value *Val2) { - if (auto *IndVal1 = dyn_cast(Val1)) { - auto *IndVal2 = cast(Val2); - return &IndVal1->getReferentLoc() == &IndVal2->getReferentLoc(); - } - if (auto *IndVal1 = dyn_cast(Val1)) { - auto *IndVal2 = cast(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(Val1) && isa(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 @@ -93,11 +71,6 @@ 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)) @@ -321,7 +294,9 @@ continue; assert(It->second != nullptr); - if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model)) + if (*Val != *It->second && + !Model.compareEquivalent(Loc->getType(), *Val, *this, *It->second, + Other)) return false; } @@ -372,8 +347,7 @@ continue; assert(It->second != nullptr); - if (Val == It->second || - (isa(Val) && isa(It->second))) { + if (*Val == *It->second) { JoinedEnv.LocToVal.insert({Loc, Val}); continue; } diff --git a/clang/lib/Analysis/FlowSensitive/Value.cpp b/clang/lib/Analysis/FlowSensitive/Value.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/Analysis/FlowSensitive/Value.cpp @@ -0,0 +1,41 @@ +//===-- 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 + +namespace clang { +namespace dataflow { + +static bool areEquivalentIndirectionValues(const Value &Val1, + const Value &Val2) { + if (auto *IndVal1 = dyn_cast(&Val1)) { + auto *IndVal2 = cast(&Val2); + return &IndVal1->getReferentLoc() == &IndVal2->getReferentLoc(); + } + if (auto *IndVal1 = dyn_cast(&Val1)) { + auto *IndVal2 = cast(&Val2); + return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc(); + } + return false; +} + +bool operator==(const Value &Val1, const Value &Val2) { + return &Val1 == &Val2 || (Val1.getKind() == Val2.getKind() && + (isa(&Val1) || + areEquivalentIndirectionValues(Val1, Val2)) && + Val1.Properties == Val2.Properties); +} + +} // namespace dataflow +} // namespace clang diff --git a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt --- a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -19,6 +19,7 @@ TypeErasedDataflowAnalysisTest.cpp SolverTest.cpp UncheckedOptionalAccessModelTest.cpp + ValueTest.cpp ) clang_target_link_libraries(ClangAnalysisFlowSensitiveTests diff --git a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp @@ -519,9 +519,8 @@ auto *Prop1 = Val1.getProperty("has_value"); auto *Prop2 = Val2.getProperty("has_value"); - return Prop1 == Prop2 || - (Prop1 != nullptr && Prop2 != nullptr && isa(Prop1) && - isa(Prop2)); + assert(Prop1 != nullptr && Prop2 != nullptr); + return *Prop1 == *Prop2; } bool merge(QualType Type, const Value &Val1, const Environment &Env1, diff --git a/clang/unittests/Analysis/FlowSensitive/ValueTest.cpp b/clang/unittests/Analysis/FlowSensitive/ValueTest.cpp new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/ValueTest.cpp @@ -0,0 +1,62 @@ +//===- 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 + +namespace { + +using namespace clang; +using namespace dataflow; + +TEST(ValueTest, EqReflexive) { + StructValue V; + EXPECT_EQ(V, V); +} + +TEST(ValueTest, AliasedReferencesEqual) { + auto L = ScalarStorageLocation(QualType()); + ReferenceValue V1(L); + ReferenceValue V2(L); + EXPECT_EQ(V1, V2); +} + +TEST(ValueTest, AliasedPointersEqual) { + auto L = ScalarStorageLocation(QualType()); + PointerValue V1(L); + PointerValue V2(L); + EXPECT_EQ(V1, V2); +} + +TEST(ValueTest, TopsEqual) { + TopBoolValue V1; + TopBoolValue V2; + EXPECT_EQ(V1, V2); +} + +TEST(ValueTest, DifferentKindsUnequal) { + auto L = ScalarStorageLocation(QualType()); + ReferenceValue V1(L); + TopBoolValue V2; + EXPECT_NE(V1, V2); +} + +TEST(ValueTest, TopsWithDifferentPropsUnequal) { + TopBoolValue Prop1; + TopBoolValue Prop2; + TopBoolValue V1; + TopBoolValue V2; + V1.setProperty("foo", Prop1); + V2.setProperty("bar", Prop2); + EXPECT_NE(V1, V2); +} + +} // namespace