https://github.com/aviralg created https://github.com/llvm/llvm-project/pull/186813
This change Introduces the analysis execution layer of the Scalable Static Analysis Framework. This layer bridges the LUSummary (entity summaries from the linker phase) to WPASuite (the collection of whole-program analysis results). It introduces the following classes: - `AnalysisResult` — base class for all per-analysis results. - `AnalysisBase` — minimal common base with a private kind tag used by the driver for dispatch - `SummaryAnalysis<ResultT, EntitySummaryT>` — processes per-entity EntitySummary objects from LUSummary. - `DerivedAnalysis<ResultT, DepResultTs...>` — consumes previously produced AnalysisResult objects. - `AnalysisRegistry` — unified `llvm::Registry` backed registry to register analyses. - `WPASuite` — Container bundling `EntityIdTable` and all `AnalysisResult` objects from a driver run. - `AnalysisDriver` — executes analyses topologically, feeding results of child analyses to parent analyses. >From 397d5649770f59907fb910c6be127d322b9fdd6a Mon Sep 17 00:00:00 2001 From: Aviral Goel <[email protected]> Date: Sat, 14 Mar 2026 09:23:07 -0700 Subject: [PATCH] Analysis Tree --- .../Core/Analysis/AnalysisBase.h | 55 +++ .../Core/Analysis/AnalysisDriver.h | 91 ++++ .../Core/Analysis/AnalysisRegistry.h | 95 +++++ .../Core/Analysis/AnalysisResult.h | 30 ++ .../Core/Analysis/DerivedAnalysis.h | 133 ++++++ .../Core/Analysis/SummaryAnalysis.h | 132 ++++++ .../Core/Analysis/WPASuite.h | 92 +++++ .../Core/EntityLinker/LUSummary.h | 1 + .../Core/Model/AnalysisName.h | 49 +++ .../Core/Model/AnalysisTraits.h | 33 ++ .../Core/Support/FormatProviders.h | 8 + .../Core/Analysis/AnalysisDriver.cpp | 196 +++++++++ .../Core/Analysis/AnalysisRegistry.cpp | 37 ++ .../Core/CMakeLists.txt | 3 + .../Core/Model/AnalysisName.cpp | 16 + .../Analysis/AnalysisDriverTest.cpp | 390 ++++++++++++++++++ .../CMakeLists.txt | 1 + 17 files changed, 1362 insertions(+) create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisBase.h create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.h create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisResult.h create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/DerivedAnalysis.h create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/SummaryAnalysis.h create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/WPASuite.h create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h create mode 100644 clang/include/clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisTraits.h create mode 100644 clang/lib/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.cpp create mode 100644 clang/lib/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.cpp create mode 100644 clang/lib/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.cpp create mode 100644 clang/unittests/ScalableStaticAnalysisFramework/Analysis/AnalysisDriverTest.cpp diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisBase.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisBase.h new file mode 100644 index 0000000000000..478a6fa85d4a8 --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisBase.h @@ -0,0 +1,55 @@ +//===- AnalysisBase.h -----------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Minimal common base for SummaryAnalysisBase and DerivedAnalysisBase. +// Carries the identity (analysisName()) and dependency list +// (dependencyNames()) shared by every analysis regardless of kind. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISBASE_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISBASE_H + +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h" +#include <vector> + +namespace clang::ssaf { + +class AnalysisDriver; +class SummaryAnalysisBase; +class DerivedAnalysisBase; + +/// Minimal common base for both analysis kinds. +/// +/// Not subclassed directly — use SummaryAnalysis<...> or +/// DerivedAnalysis<...> instead. +class AnalysisBase { + friend class AnalysisDriver; + friend class SummaryAnalysisBase; + friend class DerivedAnalysisBase; + + enum class Kind { Summary, Derived }; + Kind TheKind; + +protected: + explicit AnalysisBase(Kind K) : TheKind(K) {} + +public: + virtual ~AnalysisBase() = default; + + /// Name of this analysis. Equal to ResultT::analysisName() in both typed + /// intermediates. + virtual AnalysisName analysisName() const = 0; + + /// AnalysisNames of all AnalysisResult dependencies. + virtual const std::vector<AnalysisName> &dependencyNames() const = 0; +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISBASE_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.h new file mode 100644 index 0000000000000..1cc5c18d348b9 --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.h @@ -0,0 +1,91 @@ +//===- AnalysisDriver.h ---------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Central orchestrator for whole-program analysis. Takes ownership of an +// LUSummary, drives all registered analyses in topological dependency order, +// and returns a WPASuite. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISDRIVER_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISDRIVER_H + +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/WPASuite.h" +#include "clang/ScalableStaticAnalysisFramework/Core/EntityLinker/LUSummary.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/Support/Error.h" +#include <memory> +#include <vector> + +namespace clang::ssaf { + +/// Orchestrates whole-program analysis over an LUSummary. +/// +/// Three run() patterns are supported: +/// - run() && — all registered analyses; silently skips any whose +/// entity data is absent or whose dependency was skipped. +/// Requires an rvalue driver because this exhausts the +/// LUSummary. +/// - run(names) — named subset plus transitive dependencies; returns +/// Expected and fails if any listed name has no +/// registered analysis or missing entity data. +/// - run<ResultTs..> — type-safe variant of run(names). +class AnalysisDriver final { +public: + explicit AnalysisDriver(std::unique_ptr<LUSummary> LU); + + /// Runs all registered analyses in topological dependency order. + /// Silently skips analyses with absent entity data or skipped dependencies. + /// + /// Requires an rvalue driver (std::move(Driver).run()) because this + /// exhausts all remaining LUSummary data. + [[nodiscard]] llvm::Expected<WPASuite> run() &&; + + /// Runs only the named analyses (plus their transitive dependencies). + /// + /// Returns an error if any listed AnalysisName has no registered analysis + /// or if a required SummaryAnalysis has no matching entity data in the + /// LUSummary. The EntityIdTable is copied (not moved) so the driver remains + /// usable for subsequent calls. + [[nodiscard]] llvm::Expected<WPASuite> + run(llvm::ArrayRef<AnalysisName> Names); + + /// Type-safe variant of run(names). Derives names from + /// ResultTs::analysisName(). + template <typename... ResultTs> [[nodiscard]] llvm::Expected<WPASuite> run() { + return run({ResultTs::analysisName()...}); + } + +private: + std::unique_ptr<LUSummary> LU; + + /// Instantiates all analyses reachable from \p Roots (plus transitive + /// dependencies) and returns them in topological order via a single DFS. + /// Reports an error on unregistered names or cycles. + static llvm::Expected<std::vector<std::unique_ptr<AnalysisBase>>> + sortTopologically(llvm::ArrayRef<AnalysisName> Roots); + + /// Executes a topologically-sorted analysis list and returns a WPASuite. + /// \p IdTable is moved into the returned WPASuite. + llvm::Expected<WPASuite> + execute(EntityIdTable IdTable, + std::vector<std::unique_ptr<AnalysisBase>> Sorted); + + llvm::Error + executeSummaryAnalysis(std::unique_ptr<SummaryAnalysisBase> Summary, + WPASuite &Suite); + + llvm::Error + executeDerivedAnalysis(std::unique_ptr<DerivedAnalysisBase> Derived, + WPASuite &Suite); +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISDRIVER_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h new file mode 100644 index 0000000000000..e4faba62c070e --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h @@ -0,0 +1,95 @@ +//===- AnalysisRegistry.h -------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Unified registry for both SummaryAnalysis and DerivedAnalysis subclasses. +// +// To register an analysis, add a static Add<AnalysisT> in its translation +// unit: +// +// static AnalysisRegistry::Add<MyAnalysis> +// Registered("One-line description of MyAnalysis"); +// +// The registry entry name is derived automatically from +// MyAnalysis::analysisName(), so name-mismatch bugs are impossible. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISREGISTRY_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISREGISTRY_H + +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/DerivedAnalysis.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/SummaryAnalysis.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Support/ErrorBuilder.h" +#include "llvm/Support/Registry.h" +#include <memory> +#include <optional> +#include <string> +#include <vector> + +namespace clang::ssaf { + +/// Unified registry for SummaryAnalysis and DerivedAnalysis implementations. +/// +/// Internally uses a single llvm::Registry<AnalysisBase>. The correct kind +/// is carried by the AnalysisBase::TheKind tag set in each subclass +/// constructor. +class AnalysisRegistry { + using RegistryT = llvm::Registry<AnalysisBase>; + + AnalysisRegistry() = delete; + +public: + /// Registers AnalysisT with the unified registry. + /// + /// The registry entry name is derived automatically from + /// AnalysisT::ResultType::analysisName(), so name-mismatch bugs are + /// impossible. + /// + /// Add objects must be declared static at namespace scope. + template <typename AnalysisT> struct Add { + static_assert(std::is_base_of_v<SummaryAnalysisBase, AnalysisT> || + std::is_base_of_v<DerivedAnalysisBase, AnalysisT>, + "AnalysisT must derive from SummaryAnalysis<...> or " + "DerivedAnalysis<...>"); + + explicit Add(llvm::StringRef Desc) + : Name(AnalysisT::ResultType::analysisName().str().str()), + Node(Name, Desc) { + if (contains(Name)) { + ErrorBuilder::fatal("duplicate analysis registration for '{0}'", Name); + } + analysisNames.push_back(AnalysisT::ResultType::analysisName()); + } + + Add(const Add &) = delete; + Add &operator=(const Add &) = delete; + + private: + std::string Name; + RegistryT::Add<AnalysisT> Node; + }; + + /// Returns true if an analysis is registered under \p Name. + static bool contains(llvm::StringRef Name); + + /// Returns the names of all registered analyses. + static const std::vector<AnalysisName> &names(); + + /// Instantiates the analysis registered under \p Name, or returns + /// std::nullopt if no such analysis is registered. + static std::optional<std::unique_ptr<AnalysisBase>> + instantiate(llvm::StringRef Name); + +private: + static std::vector<AnalysisName> analysisNames; +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISREGISTRY_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisResult.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisResult.h new file mode 100644 index 0000000000000..87d781cff30a8 --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisResult.h @@ -0,0 +1,30 @@ +//===- AnalysisResult.h ---------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Base class for all whole-program analysis results produced by AnalysisDriver. +// Replaces SummaryData. Concrete subclasses carry a static analysisName(). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISRESULT_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISRESULT_H + +namespace clang::ssaf { + +/// Base class for whole-program analysis results. +/// +/// Concrete subclasses must provide: +/// static AnalysisName analysisName(); +class AnalysisResult { +public: + virtual ~AnalysisResult() = default; +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_ANALYSISRESULT_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/DerivedAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/DerivedAnalysis.h new file mode 100644 index 0000000000000..7b5695dab7c72 --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/DerivedAnalysis.h @@ -0,0 +1,133 @@ +//===- DerivedAnalysis.h --------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Defines DerivedAnalysisBase (type-erased base known to AnalysisDriver) and +// the typed intermediate DerivedAnalysis<ResultT, DepResultTs...> that +// concrete analyses inherit from. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_DERIVEDANALYSIS_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_DERIVEDANALYSIS_H + +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisBase.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisResult.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisTraits.h" +#include "llvm/Support/Error.h" +#include <map> +#include <memory> +#include <vector> + +namespace clang::ssaf { + +class AnalysisDriver; + +/// Type-erased base for derived analyses. Known to AnalysisDriver. +/// +/// Not subclassed directly — use DerivedAnalysis<ResultT, DepResultTs...>. +/// A derived analysis consumes previously produced AnalysisResult objects +/// and computes a new one via an initialize/step/finalize lifecycle. +class DerivedAnalysisBase : public AnalysisBase { + friend class AnalysisDriver; + +protected: + DerivedAnalysisBase() : AnalysisBase(AnalysisBase::Kind::Derived) {} + +private: + /// Called once with the dependency results before the step() loop. + /// + /// \param DepResults Immutable results of all declared dependencies, keyed + /// by AnalysisName. Guaranteed to contain every name + /// returned by dependencyNames(). + virtual llvm::Error initialize( + const std::map<AnalysisName, const AnalysisResult *> &DepResults) = 0; + + /// Performs one pass. Returns true if another pass is needed; false when + /// converged. + virtual llvm::Expected<bool> step() = 0; + + /// Called after the step() loop converges. Default is a no-op. + virtual llvm::Error finalize() { return llvm::Error::success(); } + + /// Transfers ownership of the computed result. Called once after finalize(). + virtual std::unique_ptr<AnalysisResult> result() && = 0; +}; + +/// Typed intermediate that concrete derived analyses inherit from. +/// +/// Concrete analyses must implement: +/// llvm::Error initialize(const DepResultTs &...) override; +/// llvm::Expected<bool> step() override; +/// and may override finalize(). +/// +/// Dependencies are fixed for the lifetime of the analysis — initialize() +/// binds them once, step() is called until it returns false, and +/// finalize() post-processes after convergence. +template <typename ResultT, typename... DepResultTs> +class DerivedAnalysis : public DerivedAnalysisBase { + static_assert(std::is_base_of_v<AnalysisResult, ResultT>, + "ResultT must derive from AnalysisResult"); + static_assert(HasAnalysisName<ResultT>::value, + "ResultT must have a static analysisName() method"); + static_assert((std::is_base_of_v<AnalysisResult, DepResultTs> && ...), + "Every DepResultT must derive from AnalysisResult"); + static_assert((HasAnalysisName<DepResultTs>::value && ...), + "Every DepResultT must have a static analysisName() method"); + + std::unique_ptr<ResultT> Result; + +public: + DerivedAnalysis() : Result(std::make_unique<ResultT>()) {} + + using ResultType = ResultT; + + /// Used by AnalysisRegistry::Add to derive the registry entry name. + AnalysisName analysisName() const final { return ResultT::analysisName(); } + + const std::vector<AnalysisName> &dependencyNames() const final { + static const std::vector<AnalysisName> Names = { + DepResultTs::analysisName()...}; + return Names; + } + + /// Called once with the fixed dependency results before the step() loop. + virtual llvm::Error initialize(const DepResultTs &...) = 0; + + /// Performs one step. Returns true if another step is needed; false when + /// converged. Single-step analyses always return false. + virtual llvm::Expected<bool> step() = 0; + + /// Called after the step() loop converges. Override for post-processing. + virtual llvm::Error finalize() { return llvm::Error::success(); } + +protected: + /// Read-only access to the result being built. + const ResultT &result() const & { return *Result; } + + /// Mutable access to the result being built. + ResultT &result() & { return *Result; } + +private: + /// Seals the type-erased base overload, downcasts, and dispatches to the + /// typed initialize(). + llvm::Error + initialize(const std::map<AnalysisName, const AnalysisResult *> &Map) final { + return initialize(*static_cast<const DepResultTs *>( + Map.at(DepResultTs::analysisName()))...); + } + + /// Type-erased result extraction for the driver. + std::unique_ptr<AnalysisResult> result() && final { + return std::move(Result); + } +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_DERIVEDANALYSIS_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/SummaryAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/SummaryAnalysis.h new file mode 100644 index 0000000000000..3a53ec147db4f --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/SummaryAnalysis.h @@ -0,0 +1,132 @@ +//===- SummaryAnalysis.h --------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Defines SummaryAnalysisBase (type-erased base known to AnalysisDriver) and +// the typed intermediate SummaryAnalysis<ResultT, EntitySummaryT> that +// concrete analyses inherit from. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_SUMMARYANALYSIS_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_SUMMARYANALYSIS_H + +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisBase.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisResult.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisTraits.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityId.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/SummaryName.h" +#include "clang/ScalableStaticAnalysisFramework/Core/TUSummary/EntitySummary.h" +#include "llvm/Support/Error.h" +#include <memory> + +namespace clang::ssaf { + +class AnalysisDriver; + +/// Type-erased base for summary analyses. Known to AnalysisDriver. +/// +/// Not subclassed directly — use SummaryAnalysis<ResultT, EntitySummaryT>. +/// A summary analysis processes per-entity EntitySummary objects from the +/// LUSummary one at a time, accumulating whole-program data into an +/// AnalysisResult. +class SummaryAnalysisBase : public AnalysisBase { + friend class AnalysisDriver; + +protected: + SummaryAnalysisBase() : AnalysisBase(AnalysisBase::Kind::Summary) {} + +public: + /// SummaryName of the EntitySummary type this analysis consumes. + /// Used by the driver to route entities from the LUSummary. + virtual SummaryName summaryName() const = 0; + +private: + /// Called once before any add() calls. Default is a no-op. + virtual llvm::Error initialize() { return llvm::Error::success(); } + + /// Called once per matching entity. The driver retains ownership of the + /// summary; multiple SummaryAnalysis instances may receive the same entity. + virtual llvm::Error add(EntityId Id, const EntitySummary &Summary) = 0; + + /// Called after all entities have been processed. Default is a no-op. + virtual llvm::Error finalize() { return llvm::Error::success(); } + + /// Transfers ownership of the built result. Called once after finalize(). + /// The rvalue ref-qualifier enforces single use. + virtual std::unique_ptr<AnalysisResult> result() && = 0; +}; + +/// Typed intermediate that concrete summary analyses inherit from. +/// +/// Concrete analyses must implement: +/// llvm::Error add(EntityId Id, const EntitySummaryT &Summary) override; +/// and may override initialize() and finalize(). +/// +/// The result being built is accessible via result() const & (read-only) and +/// result() & (mutable) within the analysis implementation. +template <typename ResultT, typename EntitySummaryT> +class SummaryAnalysis : public SummaryAnalysisBase { + static_assert(std::is_base_of_v<AnalysisResult, ResultT>, + "ResultT must derive from AnalysisResult"); + static_assert(HasAnalysisName<ResultT>::value, + "ResultT must have a static analysisName() method"); + static_assert(std::is_base_of_v<EntitySummary, EntitySummaryT>, + "EntitySummaryT must derive from EntitySummary"); + + std::unique_ptr<ResultT> Result; + +public: + SummaryAnalysis() : Result(std::make_unique<ResultT>()) {} + + using ResultType = ResultT; + + /// Used by AnalysisRegistry::Add to derive the registry entry name. + AnalysisName analysisName() const final { return ResultT::analysisName(); } + + SummaryName summaryName() const final { + return EntitySummaryT::summaryName(); + } + + const std::vector<AnalysisName> &dependencyNames() const final { + static const std::vector<AnalysisName> Empty; + return Empty; + } + + /// Called once before the first add() call. Override for initialization. + virtual llvm::Error initialize() override { return llvm::Error::success(); } + + /// Called once per matching entity. Implement to accumulate data. + virtual llvm::Error add(EntityId Id, const EntitySummaryT &Summary) = 0; + + /// Called after all entities have been processed. Override for + /// post-processing. + virtual llvm::Error finalize() override { return llvm::Error::success(); } + +protected: + /// Read-only access to the result being built. + const ResultT &result() const & { return *Result; } + + /// Mutable access to the result being built. + ResultT &result() & { return *Result; } + +private: + /// Seals the type-erased base overload, downcasts, and dispatches to the + /// typed add(). + llvm::Error add(EntityId Id, const EntitySummary &Summary) final { + return add(Id, static_cast<const EntitySummaryT &>(Summary)); + } + + /// Type-erased result extraction for the driver. + std::unique_ptr<AnalysisResult> result() && final { + return std::move(Result); + } +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_SUMMARYANALYSIS_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/WPASuite.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/WPASuite.h new file mode 100644 index 0000000000000..040f8ea79c0ec --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Analysis/WPASuite.h @@ -0,0 +1,92 @@ +//===- WPASuite.h ---------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// The value returned by AnalysisDriver::run(). Bundles the EntityIdTable +// (moved from the LUSummary) with the analysis results keyed by AnalysisName. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_WPASUITE_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_WPASUITE_H + +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisResult.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisTraits.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityIdTable.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Support/ErrorBuilder.h" +#include "llvm/Support/Error.h" +#include <map> +#include <memory> + +namespace clang::ssaf { + +class AnalysisDriver; + +/// Bundles the EntityIdTable (moved from the LUSummary) and the analysis +/// results produced by one AnalysisDriver::run() call, keyed by AnalysisName. +/// +/// This is the natural unit of persistence: entity names and analysis results +/// are self-contained in one object. +class WPASuite { + friend class AnalysisDriver; + + EntityIdTable IdTable; + std::map<AnalysisName, std::unique_ptr<AnalysisResult>> Data; + + WPASuite() = default; + +public: + /// Returns the EntityIdTable that maps EntityId values to their symbolic + /// names. Moved from the LUSummary during AnalysisDriver::run(). + const EntityIdTable &idTable() const { return IdTable; } + + /// Returns true if a result for \p ResultT is present. + template <typename ResultT> [[nodiscard]] bool contains() const { + static_assert(std::is_base_of_v<AnalysisResult, ResultT>, + "ResultT must derive from AnalysisResult"); + static_assert(HasAnalysisName<ResultT>::value, + "ResultT must have a static analysisName() method"); + + return contains(ResultT::analysisName()); + } + + /// Returns true if a result for \p Name is present. + [[nodiscard]] bool contains(AnalysisName Name) const { + return Data.find(Name) != Data.end(); + } + + /// Returns a reference to the result for \p ResultT, or an error if absent. + template <typename ResultT> [[nodiscard]] llvm::Expected<ResultT &> get() { + static_assert(std::is_base_of_v<AnalysisResult, ResultT>, + "ResultT must derive from AnalysisResult"); + static_assert(HasAnalysisName<ResultT>::value, + "ResultT must have a static analysisName() method"); + + auto Result = get(ResultT::analysisName()); + if (!Result) { + return Result.takeError(); + } + return static_cast<ResultT &>(*Result); + } + + /// Returns a reference to the result for \p Name, or an error if absent. + [[nodiscard]] llvm::Expected<AnalysisResult &> get(AnalysisName Name) { + auto It = Data.find(Name); + if (It == Data.end()) { + return ErrorBuilder::create(std::errc::invalid_argument, + "no result for analysis '{0}' in WPASuite", + Name.str()) + .build(); + } + return *It->second; + } +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_ANALYSIS_WPASUITE_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/EntityLinker/LUSummary.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/EntityLinker/LUSummary.h index 552fff04a4c01..44e7504009bee 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Core/EntityLinker/LUSummary.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/EntityLinker/LUSummary.h @@ -34,6 +34,7 @@ class LUSummary { friend class LUSummaryConsumer; friend class SerializationFormat; friend class TestFixture; + friend class AnalysisDriver; NestedBuildNamespace LUNamespace; diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h new file mode 100644 index 0000000000000..167d8a8b0485e --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h @@ -0,0 +1,49 @@ +//===- AnalysisName.h -----------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Strong typedef identifying a whole-program analysis and its result type. +// Distinct from SummaryName, which identifies per-entity EntitySummary types. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_MODEL_ANALYSISNAME_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_MODEL_ANALYSISNAME_H + +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/raw_ostream.h" +#include <string> + +namespace clang::ssaf { + +/// Uniquely identifies a whole-program analysis and the AnalysisResult it +/// produces. Used as the key in WPASuite and AnalysisRegistry. +/// +/// Distinct from SummaryName, which is used by EntitySummary types for routing +/// through the LUSummary. +class AnalysisName { +public: + explicit AnalysisName(std::string Name) : Name(std::move(Name)) {} + + bool operator==(const AnalysisName &Other) const { + return Name == Other.Name; + } + bool operator!=(const AnalysisName &Other) const { return !(*this == Other); } + bool operator<(const AnalysisName &Other) const { return Name < Other.Name; } + + /// Explicit conversion to the underlying string representation. + llvm::StringRef str() const { return Name; } + +private: + std::string Name; +}; + +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const AnalysisName &AN); + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_MODEL_ANALYSISNAME_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisTraits.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisTraits.h new file mode 100644 index 0000000000000..888f4a8e6be4a --- /dev/null +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisTraits.h @@ -0,0 +1,33 @@ +//===- AnalysisTraits.h ---------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Type traits for AnalysisResult subclasses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_MODEL_ANALYSISTRAITS_H +#define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_MODEL_ANALYSISTRAITS_H + +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h" +#include <type_traits> + +namespace clang::ssaf { + +/// Type trait that checks whether \p T has a static \c analysisName() method +/// returning \c AnalysisName. Used to enforce the convention on AnalysisResult +/// subclasses and analysis classes at instantiation time. +template <typename T, typename = void> +struct HasAnalysisName : std::false_type {}; + +template <typename T> +struct HasAnalysisName<T, std::void_t<decltype(T::analysisName())>> + : std::is_same<decltype(T::analysisName()), AnalysisName> {}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_MODEL_ANALYSISTRAITS_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Support/FormatProviders.h b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Support/FormatProviders.h index d49fd6cb4a1dc..f50d17d7f035a 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Core/Support/FormatProviders.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Core/Support/FormatProviders.h @@ -14,6 +14,7 @@ #ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_SUPPORT_FORMATPROVIDERS_H #define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_CORE_SUPPORT_FORMATPROVIDERS_H +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h" #include "clang/ScalableStaticAnalysisFramework/Core/Model/BuildNamespace.h" #include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityId.h" #include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityLinkage.h" @@ -24,6 +25,13 @@ namespace llvm { +template <> struct format_provider<clang::ssaf::AnalysisName> { + static void format(const clang::ssaf::AnalysisName &Val, raw_ostream &OS, + StringRef Style) { + OS << Val; + } +}; + template <> struct format_provider<clang::ssaf::EntityId> { static void format(const clang::ssaf::EntityId &Val, raw_ostream &OS, StringRef Style) { diff --git a/clang/lib/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.cpp b/clang/lib/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.cpp new file mode 100644 index 0000000000000..64b496142cd47 --- /dev/null +++ b/clang/lib/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.cpp @@ -0,0 +1,196 @@ +//===- AnalysisDriver.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/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/DerivedAnalysis.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/SummaryAnalysis.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Support/ErrorBuilder.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/ErrorHandling.h" +#include <map> +#include <vector> + +using namespace clang; +using namespace ssaf; + +AnalysisDriver::AnalysisDriver(std::unique_ptr<LUSummary> LU) + : LU(std::move(LU)) {} + +llvm::Expected<std::vector<std::unique_ptr<AnalysisBase>>> +AnalysisDriver::sortTopologically(llvm::ArrayRef<AnalysisName> Roots) { + struct Visitor { + enum class State { Unvisited, Visiting, Visited }; + + std::map<AnalysisName, State> Marks; + std::map<AnalysisName, std::unique_ptr<AnalysisBase>> Analyses; + std::vector<std::unique_ptr<AnalysisBase>> Result; + + State getState(const AnalysisName &Name) { + auto MarkIt = Marks.find(Name); + return MarkIt != Marks.end() ? MarkIt->second : State::Unvisited; + } + + void setState(const AnalysisName &Name, State S) { Marks[Name] = S; } + + llvm::Error visit(const AnalysisName &Name) { + State S = getState(Name); + + if (S == State::Visited) { + return llvm::Error::success(); + } + + if (S == State::Visiting) { + return ErrorBuilder::create(std::errc::invalid_argument, + "cycle detected involving analysis '{0}'", + Name) + .build(); + } + + if (S == State::Unvisited) { + setState(Name, State::Visiting); + + auto V = AnalysisRegistry::instantiate(Name.str()); + if (!V) { + return ErrorBuilder::create(std::errc::invalid_argument, + "no analysis registered for '{0}'", Name) + .build(); + } + + const auto &Deps = (*V)->dependencyNames(); + Analyses[Name] = std::move(*V); + + for (const auto &Dep : Deps) { + if (auto Err = visit(Dep)) { + return Err; + } + } + + setState(Name, State::Visited); + Result.push_back(std::move(Analyses[Name])); + Analyses.erase(Name); + return llvm::Error::success(); + } + llvm_unreachable("unhandled State"); + } + }; + + Visitor V; + for (const auto &Root : Roots) { + if (auto Err = V.visit(Root)) { + return std::move(Err); + } + } + return std::move(V.Result); +} + +llvm::Error AnalysisDriver::executeSummaryAnalysis( + std::unique_ptr<SummaryAnalysisBase> Summary, WPASuite &Suite) { + SummaryName SN = Summary->summaryName(); + auto DataIt = LU->Data.find(SN); + if (DataIt == LU->Data.end()) { + return ErrorBuilder::create(std::errc::invalid_argument, + "no data for analysis '{0}' in LUSummary", + Summary->analysisName().str()) + .build(); + } + + if (auto Err = Summary->initialize()) { + return Err; + } + + for (auto &[Id, EntitySummary] : DataIt->second) { + if (auto Err = Summary->add(Id, *EntitySummary)) { + return Err; + } + } + + if (auto Err = Summary->finalize()) { + return Err; + } + + Suite.Data.emplace(Summary->analysisName(), std::move(*Summary).result()); + + return llvm::Error::success(); +} + +llvm::Error AnalysisDriver::executeDerivedAnalysis( + std::unique_ptr<DerivedAnalysisBase> Derived, WPASuite &Suite) { + std::map<AnalysisName, const AnalysisResult *> DepMap; + + for (const auto &DepName : Derived->dependencyNames()) { + auto It = Suite.Data.find(DepName); + if (It == Suite.Data.end()) { + ErrorBuilder::fatal("missing dependency '{0}' for analysis '{1}': " + "dependency graph is not topologically sorted", + DepName.str(), Derived->analysisName().str()); + } + DepMap[DepName] = It->second.get(); + } + + if (auto Err = Derived->initialize(DepMap)) { + return Err; + } + + while (true) { + auto StepOrErr = Derived->step(); + if (!StepOrErr) { + return StepOrErr.takeError(); + } + if (!*StepOrErr) { + break; + } + } + + if (auto Err = Derived->finalize()) { + return Err; + } + + Suite.Data.emplace(Derived->analysisName(), std::move(*Derived).result()); + + return llvm::Error::success(); +} + +llvm::Expected<WPASuite> +AnalysisDriver::execute(EntityIdTable IdTable, + std::vector<std::unique_ptr<AnalysisBase>> Sorted) { + WPASuite Suite; + Suite.IdTable = std::move(IdTable); + + for (auto &V : Sorted) { + if (V->TheKind == AnalysisBase::Kind::Summary) { + auto SA = std::unique_ptr<SummaryAnalysisBase>( + static_cast<SummaryAnalysisBase *>(V.release())); + if (auto Err = executeSummaryAnalysis(std::move(SA), Suite)) { + return std::move(Err); + } + } else { + auto DA = std::unique_ptr<DerivedAnalysisBase>( + static_cast<DerivedAnalysisBase *>(V.release())); + if (auto Err = executeDerivedAnalysis(std::move(DA), Suite)) { + return std::move(Err); + } + } + } + + return Suite; +} + +llvm::Expected<WPASuite> AnalysisDriver::run() && { + return run(AnalysisRegistry::names()); +} + +llvm::Expected<WPASuite> +AnalysisDriver::run(llvm::ArrayRef<AnalysisName> Names) { + auto ExpectedSorted = sortTopologically(Names); + if (!ExpectedSorted) { + return ExpectedSorted.takeError(); + } + + return execute(LU->IdTable, std::move(*ExpectedSorted)); +} diff --git a/clang/lib/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.cpp b/clang/lib/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.cpp new file mode 100644 index 0000000000000..aac05fdb08453 --- /dev/null +++ b/clang/lib/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.cpp @@ -0,0 +1,37 @@ +//===- AnalysisRegistry.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/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h" +#include "llvm/ADT/STLExtras.h" + +using namespace clang; +using namespace ssaf; + +using RegistryT = llvm::Registry<AnalysisBase>; + +LLVM_INSTANTIATE_REGISTRY(RegistryT) + +std::vector<AnalysisName> AnalysisRegistry::analysisNames; + +bool AnalysisRegistry::contains(llvm::StringRef Name) { + return llvm::is_contained(analysisNames, AnalysisName(std::string(Name))); +} + +const std::vector<AnalysisName> &AnalysisRegistry::names() { + return analysisNames; +} + +std::optional<std::unique_ptr<AnalysisBase>> +AnalysisRegistry::instantiate(llvm::StringRef Name) { + for (const auto &Entry : RegistryT::entries()) { + if (Entry.getName() == Name) { + return std::unique_ptr<AnalysisBase>(Entry.instantiate()); + } + } + return std::nullopt; +} diff --git a/clang/lib/ScalableStaticAnalysisFramework/Core/CMakeLists.txt b/clang/lib/ScalableStaticAnalysisFramework/Core/CMakeLists.txt index 190b9fe400a64..9e9786dae5a07 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Core/CMakeLists.txt +++ b/clang/lib/ScalableStaticAnalysisFramework/Core/CMakeLists.txt @@ -4,7 +4,10 @@ set(LLVM_LINK_COMPONENTS add_clang_library(clangScalableStaticAnalysisFrameworkCore ASTEntityMapping.cpp + Analysis/AnalysisDriver.cpp + Analysis/AnalysisRegistry.cpp EntityLinker/EntityLinker.cpp + Model/AnalysisName.cpp Model/BuildNamespace.cpp Model/EntityId.cpp Model/EntityIdTable.cpp diff --git a/clang/lib/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.cpp b/clang/lib/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.cpp new file mode 100644 index 0000000000000..95e0c02f9a92f --- /dev/null +++ b/clang/lib/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.cpp @@ -0,0 +1,16 @@ +//===- AnalysisName.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/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h" + +using namespace clang::ssaf; + +llvm::raw_ostream &clang::ssaf::operator<<(llvm::raw_ostream &OS, + const AnalysisName &AN) { + return OS << "AnalysisName(" << AN.str() << ")"; +} diff --git a/clang/unittests/ScalableStaticAnalysisFramework/Analysis/AnalysisDriverTest.cpp b/clang/unittests/ScalableStaticAnalysisFramework/Analysis/AnalysisDriverTest.cpp new file mode 100644 index 0000000000000..436e0da580910 --- /dev/null +++ b/clang/unittests/ScalableStaticAnalysisFramework/Analysis/AnalysisDriverTest.cpp @@ -0,0 +1,390 @@ +//===- AnalysisDriverTest.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/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.h" +#include "../TestFixture.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisResult.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/SummaryAnalysis.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/WPASuite.h" +#include "clang/ScalableStaticAnalysisFramework/Core/EntityLinker/LUSummary.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/AnalysisName.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/BuildNamespace.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityId.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityLinkage.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityName.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/SummaryName.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Testing/Support/Error.h" +#include "gtest/gtest.h" +#include <memory> +#include <utility> +#include <vector> + +using namespace clang; +using namespace ssaf; + +namespace { + +// --------------------------------------------------------------------------- +// Instance counter +// --------------------------------------------------------------------------- + +static int NextSummaryInstanceId = 0; + +// --------------------------------------------------------------------------- +// Entity summaries +// --------------------------------------------------------------------------- + +class Analysis1EntitySummary final : public EntitySummary { +public: + int InstanceId = NextSummaryInstanceId++; + static SummaryName summaryName() { return SummaryName("Analysis1"); } + SummaryName getSummaryName() const override { + return SummaryName("Analysis1"); + } +}; + +class Analysis2EntitySummary final : public EntitySummary { +public: + int InstanceId = NextSummaryInstanceId++; + static SummaryName summaryName() { return SummaryName("Analysis2"); } + SummaryName getSummaryName() const override { + return SummaryName("Analysis2"); + } +}; + +class Analysis3EntitySummary final : public EntitySummary { +public: + int InstanceId = NextSummaryInstanceId++; + static SummaryName summaryName() { return SummaryName("Analysis3"); } + SummaryName getSummaryName() const override { + return SummaryName("Analysis3"); + } +}; + +class Analysis4EntitySummary final : public EntitySummary { +public: + int InstanceId = NextSummaryInstanceId++; + static SummaryName summaryName() { return SummaryName("Analysis4"); } + SummaryName getSummaryName() const override { + return SummaryName("Analysis4"); + } +}; + +// --------------------------------------------------------------------------- +// Results +// --------------------------------------------------------------------------- + +class Analysis1Result final : public AnalysisResult { +public: + static AnalysisName analysisName() { return AnalysisName("Analysis1"); } + std::vector<std::pair<EntityId, int>> Entries; + bool WasFinalized = false; +}; + +class Analysis2Result final : public AnalysisResult { +public: + static AnalysisName analysisName() { return AnalysisName("Analysis2"); } + std::vector<std::pair<EntityId, int>> Entries; + bool WasFinalized = false; +}; + +// No analysis or registration for Analysis3. Data for Analysis3 is inserted +// into the LUSummary to verify the driver silently skips it. +class Analysis3Result final : public AnalysisResult { +public: + static AnalysisName analysisName() { return AnalysisName("Analysis3"); } +}; + +// Analysis4 has a registered analysis but no data is inserted into the +// LUSummary, so it is skipped and get() returns nullptr. +class Analysis4Result final : public AnalysisResult { +public: + static AnalysisName analysisName() { return AnalysisName("Analysis4"); } + std::vector<std::pair<EntityId, int>> Entries; + bool WasFinalized = false; +}; + +// --------------------------------------------------------------------------- +// Analysis destruction flags (reset in SetUp) +// --------------------------------------------------------------------------- + +static bool Analysis1WasDestroyed = false; +static bool Analysis2WasDestroyed = false; +static bool Analysis4WasDestroyed = false; + +// --------------------------------------------------------------------------- +// Analyses +// --------------------------------------------------------------------------- + +class Analysis1 final + : public SummaryAnalysis<Analysis1Result, Analysis1EntitySummary> { +public: + ~Analysis1() { Analysis1WasDestroyed = true; } + + llvm::Error add(EntityId Id, const Analysis1EntitySummary &S) override { + result().Entries.push_back({Id, S.InstanceId}); + return llvm::Error::success(); + } + + llvm::Error finalize() override { + result().WasFinalized = true; + return llvm::Error::success(); + } +}; + +static AnalysisRegistry::Add<Analysis1> RegAnalysis1("Analysis for Analysis1"); + +class Analysis2 final + : public SummaryAnalysis<Analysis2Result, Analysis2EntitySummary> { +public: + ~Analysis2() { Analysis2WasDestroyed = true; } + + llvm::Error add(EntityId Id, const Analysis2EntitySummary &S) override { + result().Entries.push_back({Id, S.InstanceId}); + return llvm::Error::success(); + } + + llvm::Error finalize() override { + result().WasFinalized = true; + return llvm::Error::success(); + } +}; + +static AnalysisRegistry::Add<Analysis2> RegAnalysis2("Analysis for Analysis2"); + +class Analysis4 final + : public SummaryAnalysis<Analysis4Result, Analysis4EntitySummary> { +public: + ~Analysis4() { Analysis4WasDestroyed = true; } + + llvm::Error add(EntityId Id, const Analysis4EntitySummary &S) override { + result().Entries.push_back({Id, S.InstanceId}); + return llvm::Error::success(); + } + + llvm::Error finalize() override { + result().WasFinalized = true; + return llvm::Error::success(); + } +}; + +static AnalysisRegistry::Add<Analysis4> RegAnalysis4("Analysis for Analysis4"); + +// --------------------------------------------------------------------------- +// Fixture +// --------------------------------------------------------------------------- + +class AnalysisDriverTest : public TestFixture { +protected: + static constexpr EntityLinkage ExternalLinkage = + EntityLinkage(EntityLinkageType::External); + + void SetUp() override { + NextSummaryInstanceId = 0; + Analysis1WasDestroyed = false; + Analysis2WasDestroyed = false; + Analysis4WasDestroyed = false; + } + + std::unique_ptr<LUSummary> makeLUSummary() { + NestedBuildNamespace NS( + {BuildNamespace(BuildNamespaceKind::LinkUnit, "TestLU")}); + return std::make_unique<LUSummary>(std::move(NS)); + } + + EntityId addEntity(LUSummary &LU, llvm::StringRef USR) { + NestedBuildNamespace NS( + {BuildNamespace(BuildNamespaceKind::LinkUnit, "TestLU")}); + EntityName Name(USR.str(), "", NS); + EntityId Id = getIdTable(LU).getId(Name); + getLinkageTable(LU).insert({Id, ExternalLinkage}); + return Id; + } + + static bool hasEntry(const std::vector<std::pair<EntityId, int>> &Entries, + EntityId Id, int InstanceId) { + return llvm::is_contained(Entries, std::make_pair(Id, InstanceId)); + } + + template <typename SummaryT> + int insertSummary(LUSummary &LU, llvm::StringRef SN, EntityId Id) { + auto S = std::make_unique<SummaryT>(); + int InstanceId = S->InstanceId; + getData(LU)[SummaryName(SN.str())][Id] = std::move(S); + return InstanceId; + } +}; + +// --------------------------------------------------------------------------- +// Tests +// --------------------------------------------------------------------------- + +TEST(AnalysisRegistryTest, AnalysisIsRegistered) { + EXPECT_FALSE(AnalysisRegistry::contains("AnalysisNonExisting")); + EXPECT_TRUE(AnalysisRegistry::contains("Analysis1")); + EXPECT_TRUE(AnalysisRegistry::contains("Analysis2")); + EXPECT_TRUE(AnalysisRegistry::contains("Analysis4")); +} + +TEST(AnalysisRegistryTest, AnalysisCanBeInstantiated) { + EXPECT_FALSE( + AnalysisRegistry::instantiate("AnalysisNonExisting").has_value()); + EXPECT_TRUE(AnalysisRegistry::instantiate("Analysis1").has_value()); + EXPECT_TRUE(AnalysisRegistry::instantiate("Analysis2").has_value()); + EXPECT_TRUE(AnalysisRegistry::instantiate("Analysis4").has_value()); +} + +// run() — processes all registered analyses present in the LUSummary. +// Silently skips data whose analysis is unregistered (Analysis3). +TEST_F(AnalysisDriverTest, RunAll) { + auto LU = makeLUSummary(); + const auto E1 = addEntity(*LU, "Entity1"); + const auto E2 = addEntity(*LU, "Entity2"); + const auto E3 = addEntity(*LU, "Entity3"); + const auto E4 = addEntity(*LU, "Entity4"); + + int s1a = insertSummary<Analysis1EntitySummary>(*LU, "Analysis1", E1); + int s1b = insertSummary<Analysis1EntitySummary>(*LU, "Analysis1", E2); + int s2a = insertSummary<Analysis2EntitySummary>(*LU, "Analysis2", E2); + int s2b = insertSummary<Analysis2EntitySummary>(*LU, "Analysis2", E3); + int s4a = insertSummary<Analysis4EntitySummary>(*LU, "Analysis4", E4); + + // No registered analysis — Analysis3 data silently skipped. + (void)insertSummary<Analysis3EntitySummary>(*LU, "Analysis3", E1); + + AnalysisDriver Driver(std::move(LU)); + auto WPAOrErr = std::move(Driver).run(); + ASSERT_THAT_EXPECTED(WPAOrErr, llvm::Succeeded()); + + { + auto R1OrErr = WPAOrErr->get<Analysis1Result>(); + ASSERT_THAT_EXPECTED(R1OrErr, llvm::Succeeded()); + EXPECT_EQ(R1OrErr->Entries.size(), 2u); + EXPECT_TRUE(hasEntry(R1OrErr->Entries, E1, s1a)); + EXPECT_TRUE(hasEntry(R1OrErr->Entries, E2, s1b)); + EXPECT_TRUE(R1OrErr->WasFinalized); + EXPECT_TRUE(Analysis1WasDestroyed); + } + + { + auto R2OrErr = WPAOrErr->get<Analysis2Result>(); + ASSERT_THAT_EXPECTED(R2OrErr, llvm::Succeeded()); + EXPECT_EQ(R2OrErr->Entries.size(), 2u); + EXPECT_TRUE(hasEntry(R2OrErr->Entries, E2, s2a)); + EXPECT_TRUE(hasEntry(R2OrErr->Entries, E3, s2b)); + EXPECT_TRUE(R2OrErr->WasFinalized); + EXPECT_TRUE(Analysis2WasDestroyed); + } + + { + auto R4OrErr = WPAOrErr->get<Analysis4Result>(); + ASSERT_THAT_EXPECTED(R4OrErr, llvm::Succeeded()); + EXPECT_EQ(R4OrErr->Entries.size(), 1u); + EXPECT_TRUE(hasEntry(R4OrErr->Entries, E4, s4a)); + EXPECT_TRUE(R4OrErr->WasFinalized); + EXPECT_TRUE(Analysis4WasDestroyed); + } + + // Unregistered analysis — not present in WPA. + EXPECT_THAT_EXPECTED(WPAOrErr->get<Analysis3Result>(), llvm::Failed()); +} + +// run(names) — processes only the analyses for the given names. +TEST_F(AnalysisDriverTest, RunByName) { + auto LU = makeLUSummary(); + const auto E1 = addEntity(*LU, "Entity1"); + const auto E2 = addEntity(*LU, "Entity2"); + + int s1a = insertSummary<Analysis1EntitySummary>(*LU, "Analysis1", E1); + insertSummary<Analysis2EntitySummary>(*LU, "Analysis2", E2); + + AnalysisDriver Driver(std::move(LU)); + auto WPAOrErr = Driver.run({AnalysisName("Analysis1")}); + ASSERT_THAT_EXPECTED(WPAOrErr, llvm::Succeeded()); + + // Analysis1 was requested and has data — present. + auto R1OrErr = WPAOrErr->get<Analysis1Result>(); + ASSERT_THAT_EXPECTED(R1OrErr, llvm::Succeeded()); + EXPECT_EQ(R1OrErr->Entries.size(), 1u); + EXPECT_TRUE(hasEntry(R1OrErr->Entries, E1, s1a)); + EXPECT_TRUE(R1OrErr->WasFinalized); + + // Analysis2 was not requested — not present even though data exists. + EXPECT_THAT_EXPECTED(WPAOrErr->get<Analysis2Result>(), llvm::Failed()); +} + +// run(names) — error when a requested name has no data in LUSummary. +TEST_F(AnalysisDriverTest, RunByNameErrorMissingData) { + auto LU = makeLUSummary(); + AnalysisDriver Driver(std::move(LU)); + + EXPECT_THAT_EXPECTED(Driver.run({AnalysisName("Analysis1")}), llvm::Failed()); +} + +// run(names) — error when a requested name has no registered analysis. +TEST_F(AnalysisDriverTest, RunByNameErrorMissingAnalysis) { + auto LU = makeLUSummary(); + const auto E1 = addEntity(*LU, "Entity1"); + insertSummary<Analysis3EntitySummary>(*LU, "Analysis3", E1); + + AnalysisDriver Driver(std::move(LU)); + + // Analysis3 has data but no registered analysis. + EXPECT_THAT_EXPECTED(Driver.run({AnalysisName("Analysis3")}), llvm::Failed()); +} + +// run<ResultTs...>() — type-safe subset. +TEST_F(AnalysisDriverTest, RunByType) { + auto LU = makeLUSummary(); + const auto E1 = addEntity(*LU, "Entity1"); + const auto E2 = addEntity(*LU, "Entity2"); + + int s1a = insertSummary<Analysis1EntitySummary>(*LU, "Analysis1", E1); + insertSummary<Analysis2EntitySummary>(*LU, "Analysis2", E2); + + AnalysisDriver Driver(std::move(LU)); + auto WPAOrErr = Driver.run<Analysis1Result>(); + ASSERT_THAT_EXPECTED(WPAOrErr, llvm::Succeeded()); + + // Analysis1 was requested — present. + auto R1OrErr = WPAOrErr->get<Analysis1Result>(); + ASSERT_THAT_EXPECTED(R1OrErr, llvm::Succeeded()); + EXPECT_EQ(R1OrErr->Entries.size(), 1u); + EXPECT_TRUE(hasEntry(R1OrErr->Entries, E1, s1a)); + EXPECT_TRUE(R1OrErr->WasFinalized); + + // Analysis2 was not requested — not present even though data exists. + EXPECT_THAT_EXPECTED(WPAOrErr->get<Analysis2Result>(), llvm::Failed()); +} + +// run<ResultTs...>() — error when a requested type has no data in LUSummary. +TEST_F(AnalysisDriverTest, RunByTypeErrorMissingData) { + auto LU = makeLUSummary(); + AnalysisDriver Driver(std::move(LU)); + + EXPECT_THAT_EXPECTED(Driver.run<Analysis1Result>(), llvm::Failed()); +} + +// contains() — present entries return true; absent entries return false. +TEST_F(AnalysisDriverTest, Contains) { + auto LU = makeLUSummary(); + const auto E1 = addEntity(*LU, "Entity1"); + insertSummary<Analysis1EntitySummary>(*LU, "Analysis1", E1); + insertSummary<Analysis4EntitySummary>(*LU, "Analysis4", E1); + + AnalysisDriver Driver(std::move(LU)); + auto WPAOrErr = std::move(Driver).run(); + ASSERT_THAT_EXPECTED(WPAOrErr, llvm::Succeeded()); + + EXPECT_TRUE(WPAOrErr->contains<Analysis1Result>()); + EXPECT_FALSE(WPAOrErr->contains<Analysis2Result>()); +} + +} // namespace diff --git a/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt b/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt index 7652ebb390f86..2fec611718475 100644 --- a/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt +++ b/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt @@ -1,5 +1,6 @@ add_distinct_clang_unittest(ClangScalableAnalysisTests Analyses/UnsafeBufferUsage/UnsafeBufferUsageTest.cpp + Analysis/AnalysisDriverTest.cpp ASTEntityMappingTest.cpp BuildNamespaceTest.cpp EntityIdTableTest.cpp _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
