blob: d9851ba274ffdb95df72220e44b29857cdb62e29 [file] [edit]
//===- 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/ArrayRef.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);
auto keys() const { return llvm::make_first_range(Roots); }
private:
llvm::DenseMap<EntityId, EntityId> Roots;
};
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 Family map.
void groupParamsAndReturnEntities();
/// Make the param and return IDs share a family.
void unionParamsAndReturnEntitiesInSummaries(const VirtualMethodSummary &LHS,
const VirtualMethodSummary &RHS);
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 VirtualMethodFamilyAnalysis::unionParamsAndReturnEntitiesInSummaries(
const VirtualMethodSummary &LHS, const VirtualMethodSummary &RHS) {
assert(LHS.ParamEntities.size() == RHS.ParamEntities.size());
assert(LHS.ReturnEntity.has_value() == RHS.ReturnEntity.has_value());
using llvm::zip_equal;
for (auto [LParam, RParam] : zip_equal(LHS.ParamEntities, RHS.ParamEntities))
Family.unionSets(LParam, RParam);
if (LHS.ReturnEntity.has_value())
Family.unionSets(*LHS.ReturnEntity, *RHS.ReturnEntity);
}
void VirtualMethodFamilyAnalysis::groupParamsAndReturnEntities() {
for (const VirtualMethodSummary *CurrSum : llvm::make_second_range(Data)) {
for (EntityId OverriddenMethodId : CurrSum->OverriddenMethods) {
auto BaseSumIt = Data.find(OverriddenMethodId);
assert(BaseSumIt != Data.end());
const VirtualMethodSummary &BaseSum = *BaseSumIt->second;
unionParamsAndReturnEntitiesInSummaries(*CurrSum, BaseSum);
}
}
}
llvm::Error VirtualMethodFamilyAnalysis::finalize() {
groupParamsAndReturnEntities();
auto &R = getResult();
for (EntityId E : Family.keys())
R.RetAndParamData.insert({E, Family.find(E)});
return llvm::Error::success();
}
static AnalysisRegistry::Add<VirtualMethodFamilyAnalysis>
RegisterAnalysis("Override-family equivalence classes for virtual methods");
//===----------------------------------------------------------------------===//
// Printing
//===----------------------------------------------------------------------===//
static void printEntityIds(llvm::raw_ostream &OS,
llvm::ArrayRef<EntityId> Ids) {
OS << "[";
llvm::interleaveComma(Ids, OS, [&](EntityId Id) { OS << Id; });
OS << "]";
}
namespace clang::ssaf {
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
const VirtualMethodSummary &S) {
OS << "VirtualMethodSummary { params=";
printEntityIds(OS, S.ParamEntities);
OS << ", return=";
if (S.ReturnEntity)
OS << *S.ReturnEntity;
else
OS << "<none>";
OS << ", overridden=";
printEntityIds(OS, S.OverriddenMethods);
return OS << " }";
}
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
const VirtualMethodFamilyAnalysisResult &R) {
OS << "VirtualMethodFamilyAnalysisResult with " << R.RetAndParamData.size()
<< " entries ";
if (R.RetAndParamData.empty())
return OS << "{}";
// DenseMap iteration order depends on hashing, so sort for stable output.
using Entry = std::pair<EntityId, EntityId>;
llvm::SmallVector<Entry> Entries(R.RetAndParamData.begin(),
R.RetAndParamData.end());
llvm::sort(Entries,
[](const Entry &L, const Entry &R) { return L.first < R.first; });
OS << "{\n";
for (const auto &[Id, FamilyId] : Entries)
OS << " " << Id << " -> " << FamilyId << "\n";
return OS << "}";
}
// NOLINTNEXTLINE(misc-use-internal-linkage)
volatile int VirtualMethodFamilyAnalysisAnchorSource = 0;
} // namespace clang::ssaf