ymandel created this revision. ymandel added reviewers: xazax.hun, sgatev, gribozavr2. Herald added subscribers: martong, rnkovacs. Herald added a reviewer: NoQ. Herald added a project: All. ymandel requested review of this revision. Herald added a project: clang.
Defines `operator==` as an equivalence relation on the `Value` type. It standardizes several places in the code where we replicate the ~same equivalence comparison. NOTE: It may be better to define this as a named method, rather than overriding the operator, given that it is a (weak) equivalence relation rather than a (deep) equality relation. Repository: rG LLVM Github Monorepo https://reviews.llvm.org/D135964 Files: clang/include/clang/Analysis/FlowSensitive/Value.h clang/lib/Analysis/FlowSensitive/CMakeLists.txt clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp clang/lib/Analysis/FlowSensitive/Value.cpp clang/unittests/Analysis/FlowSensitive/CMakeLists.txt clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp clang/unittests/Analysis/FlowSensitive/ValueTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/ValueTest.cpp =================================================================== --- /dev/null +++ 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 <memory> + +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 Index: clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp =================================================================== --- clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp +++ 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<TopBoolValue>(Prop1) && - isa<TopBoolValue>(Prop2)); + assert(Prop1 != nullptr && Prop2 != nullptr); + return *Prop1 == *Prop2; } bool merge(QualType Type, const Value &Val1, const Environment &Env1, Index: clang/unittests/Analysis/FlowSensitive/CMakeLists.txt =================================================================== --- clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -19,6 +19,7 @@ TypeErasedDataflowAnalysisTest.cpp SolverTest.cpp UncheckedOptionalAccessModelTest.cpp + ValueTest.cpp ) clang_target_link_libraries(ClangAnalysisFlowSensitiveTests Index: clang/lib/Analysis/FlowSensitive/Value.cpp =================================================================== --- /dev/null +++ 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 <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 operator==(const Value &Val1, const Value &Val2) { + return &Val1 == &Val2 || (Val1.getKind() == Val2.getKind() && + (isa<TopBoolValue>(&Val1) || + areEquivalentIndirectionValues(Val1, Val2)) && + Val1.Properties == Val2.Properties); +} + +} // namespace dataflow +} // namespace clang Index: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp =================================================================== --- clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -49,28 +49,6 @@ 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 @@ -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<TopBoolValue>(Val) && isa<TopBoolValue>(It->second))) { + if (*Val == *It->second) { JoinedEnv.LocToVal.insert({Loc, Val}); continue; } Index: clang/lib/Analysis/FlowSensitive/CMakeLists.txt =================================================================== --- clang/lib/Analysis/FlowSensitive/CMakeLists.txt +++ clang/lib/Analysis/FlowSensitive/CMakeLists.txt @@ -4,6 +4,7 @@ DataflowEnvironment.cpp Transfer.cpp TypeErasedDataflowAnalysis.cpp + Value.cpp WatchedLiteralsSolver.cpp DebugSupport.cpp Index: clang/include/clang/Analysis/FlowSensitive/Value.h =================================================================== --- clang/include/clang/Analysis/FlowSensitive/Value.h +++ 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<Value *> Properties; }; +inline bool operator!=(const Value &Val1, const Value &Val2) { + return !(Val1 == Val2); +} + /// Models a boolean. class BoolValue : public Value { public:
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
