================ @@ -0,0 +1,201 @@ +//===- VirtualMethodFamilyAnalysis.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/ScalableStaticAnalysis/Analyses/VirtualMethodFamily/VirtualMethodFamily.h" +#include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h" +#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisRegistry.h" +#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/SummaryAnalysis.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/raw_ostream.h" +#include <cassert> +#include <map> +#include <optional> +#include <utility> + +using namespace clang::ssaf; + +namespace { + +struct MethodFamilyUnionFind { + EntityId find(EntityId E); + void unionSets(EntityId A, EntityId B); + + void seed(EntityId E, EntityId Owner) { Roots.try_emplace(E, E); } + void seed(EntityId Owner, const VirtualMethodSummary &S); + + auto keys() const { return llvm::make_first_range(Roots); } + +private: + llvm::DenseMap<EntityId, EntityId> Roots; +}; + +// Keeps track of what method declared the given parameter or return value. +struct Owners { + void recordOwner(EntityId Owner, const VirtualMethodSummary &S); + void recordOwner(EntityId E, EntityId Owner); + + EntityId getOwnerOf(EntityId Id) const { + assert(Owners.count(Id)); + return Owners.at(Id); + } + +private: + llvm::DenseMap<EntityId, EntityId> Owners; +}; + +class VirtualMethodFamilyAnalysis final + : public SummaryAnalysis<VirtualMethodFamilyAnalysisResult, + VirtualMethodSummary> { +public: + llvm::Error add(EntityId Id, const VirtualMethodSummary &Summary) override { + Data[Id] = &Summary; + return llvm::Error::success(); + } + + llvm::Error finalize() override; + +private: + /// Fill the \c Owners and \c Family maps. + void groupParamsAndReturnEntities(); + + /// Make the param and return IDs share a family. + void unionParamsAndReturnEntitiesInSummaries(const VirtualMethodSummary &LHS, + const VirtualMethodSummary &RHS); + + Owners Owners; + MethodFamilyUnionFind Family; + std::map<EntityId, const VirtualMethodSummary *> Data; +}; +} // namespace + +EntityId MethodFamilyUnionFind::find(EntityId E) { + auto It = Roots.find(E); + if (It == Roots.end()) { + Roots.try_emplace(E, E); // Self-rooted singleton. + return E; + } + if (It->second == E) + return E; + EntityId Root = find(It->second); + Roots.insert_or_assign(E, Root); // Path compression. + return Root; +} + +void MethodFamilyUnionFind::unionSets(EntityId A, EntityId B) { + EntityId RootA = find(A); + EntityId RootB = find(B); + if (RootA == RootB) + return; + + // Prefer the lexicographically-smaller rep for stable output across runs. + if (RootB < RootA) + std::swap(RootA, RootB); + + Roots.insert_or_assign(RootB, RootA); +} + +void MethodFamilyUnionFind::seed(EntityId Owner, ---------------- ziqingluo-90 wrote:
Why the parameter `Owner` is needed? The other `seed` function does not use it. The ownership relation and the belong-to-a-family relation are independent, right? The union-find algorithm computes the latter one. The algorithm doesn't have to involve `Owner`. https://github.com/llvm/llvm-project/pull/213317 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
