VirtualMethodFamilyAnalysis.cpp

Go to the documentation of this file.

//===- 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