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 @@ -77,6 +77,17 @@ llvm::StringMap 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: 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 (!areEquivalentValues(*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 (areEquivalentValues(*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,39 @@ +//===-- 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" + +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 areEquivalentValues(const Value &Val1, const Value &Val2) { + return &Val1 == &Val2 || (Val1.getKind() == Val2.getKind() && + (isa(&Val1) || + areEquivalentIndirectionValues(Val1, Val2))); +} + +} // 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 @@ -517,11 +517,10 @@ 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(Prop1) && - isa(Prop2)); + assert(Prop1 != nullptr && Prop2 != nullptr); + return areEquivalentValues(*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,85 @@ +//===- 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, 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)); + EXPECT_TRUE(areEquivalentValues(V2, V1)); +} + +TEST(ValueTest, AliasedPointersEquivalent) { + auto L = ScalarStorageLocation(QualType()); + PointerValue V1(L); + PointerValue V2(L); + EXPECT_TRUE(areEquivalentValues(V1, V2)); + EXPECT_TRUE(areEquivalentValues(V2, V1)); +} + +TEST(ValueTest, TopsEquivalent) { + TopBoolValue V1; + TopBoolValue V2; + EXPECT_TRUE(areEquivalentValues(V1, V2)); + 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)); + EXPECT_TRUE(areEquivalentValues(V2, V1)); +} + +TEST(ValueTest, DifferentKindsNotEquivalent) { + auto L = ScalarStorageLocation(QualType()); + ReferenceValue V1(L); + TopBoolValue V2; + EXPECT_FALSE(areEquivalentValues(V1, V2)); + 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)); + 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)); + EXPECT_FALSE(areEquivalentValues(V2, V1)); +} + +} // namespace