https://github.com/ymand created
https://github.com/llvm/llvm-project/pull/120967
This PR has 2 related goals:
*Remove dependency on `llvm::Any`*. For some platforms, use of `llvm::Any`
forces users to explicitly define internal details related to `Any`. Aside from
aesthetics, this places an obscure requirement on lattice implementers. We
prefer to use LLVM's (explicit) RTTI framework instead.
*Introduce virtual interface for lattices*. Currently, we implicitly define the
interface for lattices, because the interface to analyses is fully captured in
templates. This PR moves to an explicit, virtual interface.
We combine these two changes in a single PR because they are closely related: we
use the new lattice interface as the basis of an open type hierarchy that embeds
RTTI for safe interfacing with the dataflow engine.
>From 43385b7341ef6d3bd5f689670ca407f6e5f91949 Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum <yitzh...@google.com>
Date: Mon, 23 Dec 2024 13:42:21 +0000
Subject: [PATCH] Introduce virtual interface for lattices and remove
dependency on `llvm::Any`.
This PR has 2 related goals:
*Remove dependency on `llvm::Any`*. For some platforms, use of `llvm::Any`
forces users to explicitly define internal details related to `Any`. Aside from
aesthetics, this places an obscure requirement on lattice implementers. We
prefer to use LLVM's (explicit) RTTI framework instead.
*Introduce virtual interface for lattices*. Currently, we implicitly define the
interface for lattices, because the interface to analyses is fully captured in
templates. This PR moves to an explicit, virtual interface.
We combine these two changes in a single PR because they are closely related: we
use the new lattice interface as the basis of an open type hierarchy that embeds
RTTI for safe interfacing with the dataflow engine.
---
.../CachedConstAccessorsLattice.h | 20 ++-
.../Analysis/FlowSensitive/DataflowAnalysis.h | 151 +-----------------
.../Analysis/FlowSensitive/DataflowLattice.h | 38 +++++
.../clang/Analysis/FlowSensitive/Logger.h | 4 +-
.../clang/Analysis/FlowSensitive/MapLattice.h | 26 ++-
.../Models/UncheckedOptionalAccessModel.h | 24 ++-
.../Analysis/FlowSensitive/NoopAnalysis.h | 20 +--
.../Analysis/FlowSensitive/NoopLattice.h | 29 ++--
.../TypeErasedDataflowAnalysis.h | 144 +++++++++--------
clang/lib/Analysis/FlowSensitive/Arena.cpp | 4 +-
.../lib/Analysis/FlowSensitive/HTMLLogger.cpp | 3 +-
clang/lib/Analysis/FlowSensitive/Logger.cpp | 4 +-
.../Models/UncheckedOptionalAccessModel.cpp | 9 +-
clang/lib/Analysis/FlowSensitive/Transfer.cpp | 1 +
.../TypeErasedDataflowAnalysis.cpp | 56 +++----
.../FlowSensitive/ChromiumCheckModelTest.cpp | 15 +-
.../Analysis/FlowSensitive/LoggerTest.cpp | 50 ++++--
.../Analysis/FlowSensitive/MapLatticeTest.cpp | 40 +++--
.../MultiVarConstantPropagationTest.cpp | 52 +++---
.../FlowSensitive/SignAnalysisTest.cpp | 14 +-
.../SingleVarConstantPropagationTest.cpp | 52 +++---
.../Analysis/FlowSensitive/TestingSupport.h | 8 +-
.../FlowSensitive/TransferBranchTest.cpp | 33 ++--
.../TypeErasedDataflowAnalysisTest.cpp | 116 ++++++++++----
24 files changed, 475 insertions(+), 438 deletions(-)
diff --git
a/clang/include/clang/Analysis/FlowSensitive/CachedConstAccessorsLattice.h
b/clang/include/clang/Analysis/FlowSensitive/CachedConstAccessorsLattice.h
index 48c5287367739a..8dd9cd546be160 100644
--- a/clang/include/clang/Analysis/FlowSensitive/CachedConstAccessorsLattice.h
+++ b/clang/include/clang/Analysis/FlowSensitive/CachedConstAccessorsLattice.h
@@ -20,6 +20,7 @@
#include "clang/Analysis/FlowSensitive/Value.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLFunctionalExtras.h"
+#include "llvm/Support/ExtensibleRTTI.h"
namespace clang {
namespace dataflow {
@@ -88,7 +89,15 @@ template <typename Base> class CachedConstAccessorsLattice :
public Base {
return Base::operator==(Other);
}
- LatticeJoinEffect join(const CachedConstAccessorsLattice &Other);
+ std::unique_ptr<DataflowLattice> clone() override {
+ return std::make_unique<CachedConstAccessorsLattice>(*this);
+ }
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const CachedConstAccessorsLattice>(Other);
+ }
+
+ LatticeEffect join(const DataflowLattice &Other) override;
private:
// Maps a record storage location and const method to the value to return
@@ -146,22 +155,23 @@ joinConstMethodMap(
template <typename Base>
LatticeEffect CachedConstAccessorsLattice<Base>::join(
- const CachedConstAccessorsLattice<Base> &Other) {
-
+ const DataflowLattice &Other) {
LatticeEffect Effect = Base::join(Other);
+ const auto &OtherL = llvm::cast<const
CachedConstAccessorsLattice<Base>>(Other);
+
// For simplicity, we only retain values that are identical, but not ones
that
// are non-identical but equivalent. This is likely to be sufficient in
// practice, and it reduces implementation complexity considerably.
ConstMethodReturnValues =
clang::dataflow::internal::joinConstMethodMap<dataflow::Value>(
- ConstMethodReturnValues, Other.ConstMethodReturnValues, Effect);
+ ConstMethodReturnValues, OtherL.ConstMethodReturnValues, Effect);
ConstMethodReturnStorageLocations =
clang::dataflow::internal::joinConstMethodMap<dataflow::StorageLocation>(
ConstMethodReturnStorageLocations,
- Other.ConstMethodReturnStorageLocations, Effect);
+ OtherL.ConstMethodReturnStorageLocations, Effect);
return Effect;
}
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
index e6efde091871fc..494a2d5cd1e8a7 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
@@ -16,7 +16,6 @@
#include <iterator>
#include <optional>
-#include <type_traits>
#include <utility>
#include <vector>
@@ -37,138 +36,6 @@
namespace clang {
namespace dataflow {
-/// Base class template for dataflow analyses built on a single lattice type.
-///
-/// Requirements:
-///
-/// `Derived` must be derived from a specialization of this class template and
-/// must provide the following public members:
-/// * `LatticeT initialElement()` - returns a lattice element that models the
-/// initial state of a basic block;
-/// * `void transfer(const CFGElement &, LatticeT &, Environment &)` -
applies
-/// the analysis transfer function for a given CFG element and lattice
-/// element.
-///
-/// `Derived` can optionally provide the following members:
-/// * `void transferBranch(bool Branch, const Stmt *Stmt, TypeErasedLattice
&E,
-/// Environment &Env)` - applies the analysis transfer
-/// function for a given edge from a CFG block of a conditional statement.
-///
-/// `Derived` can optionally override the virtual functions in the
-/// `Environment::ValueModel` interface (which is an indirect base class of
-/// this class).
-///
-/// `LatticeT` is a bounded join-semilattice that is used by `Derived` and
must
-/// provide the following public members:
-/// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
-/// argument by computing their least upper bound, modifies the object if
-/// necessary, and returns an effect indicating whether any changes were
-/// made to it;
-/// FIXME: make it `static LatticeT join(const LatticeT&, const LatticeT&)`
-/// * `bool operator==(const LatticeT &) const` - returns true if and only if
-/// the object is equal to the argument.
-///
-/// `LatticeT` can optionally provide the following members:
-/// * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the
-/// lattice element with an approximation that can reach a fixed point more
-/// quickly than iterated application of the transfer function alone. The
-/// previous value is provided to inform the choice of widened value. The
-/// function must also serve as a comparison operation, by indicating
whether
-/// the widened value is equivalent to the previous value with the returned
-/// `LatticeJoinEffect`.
-template <typename Derived, typename LatticeT>
-class DataflowAnalysis : public TypeErasedDataflowAnalysis {
-public:
- /// Bounded join-semilattice that is used in the analysis.
- using Lattice = LatticeT;
-
- explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
-
- explicit DataflowAnalysis(ASTContext &Context,
- DataflowAnalysisOptions Options)
- : TypeErasedDataflowAnalysis(Options), Context(Context) {}
-
- ASTContext &getASTContext() final { return Context; }
-
- TypeErasedLattice typeErasedInitialElement() final {
- return {static_cast<Derived *>(this)->initialElement()};
- }
-
- TypeErasedLattice joinTypeErased(const TypeErasedLattice &E1,
- const TypeErasedLattice &E2) final {
- // FIXME: change the signature of join() to avoid copying here.
- Lattice L1 = llvm::any_cast<const Lattice &>(E1.Value);
- const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
- L1.join(L2);
- return {std::move(L1)};
- }
-
- LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current,
- const TypeErasedLattice &Previous) final {
- Lattice &C = llvm::any_cast<Lattice &>(Current.Value);
- const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value);
- return widenInternal(Rank0{}, C, P);
- }
-
- bool isEqualTypeErased(const TypeErasedLattice &E1,
- const TypeErasedLattice &E2) final {
- const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
- const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
- return L1 == L2;
- }
-
- void transferTypeErased(const CFGElement &Element, TypeErasedLattice &E,
- Environment &Env) final {
- Lattice &L = llvm::any_cast<Lattice &>(E.Value);
- static_cast<Derived *>(this)->transfer(Element, L, Env);
- }
-
- void transferBranchTypeErased(bool Branch, const Stmt *Stmt,
- TypeErasedLattice &E, Environment &Env) final {
- transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch,
Stmt,
- E, Env);
- }
-
-private:
- // These `Rank` structs are used for template metaprogramming to choose
- // between overloads.
- struct Rank1 {};
- struct Rank0 : Rank1 {};
-
- // The first-choice implementation: use `widen` when it is available.
- template <typename T>
- static auto widenInternal(Rank0, T &Current, const T &Prev)
- -> decltype(Current.widen(Prev)) {
- return Current.widen(Prev);
- }
-
- // The second-choice implementation: `widen` is unavailable. Widening is
- // merged with equality checking, so when widening is unimplemented, we
- // default to equality checking.
- static LatticeJoinEffect widenInternal(Rank1, const Lattice &Current,
- const Lattice &Prev) {
- return Prev == Current ? LatticeJoinEffect::Unchanged
- : LatticeJoinEffect::Changed;
- }
-
- // The first-choice implementation: `transferBranch` is implemented.
- template <typename Analysis>
- static auto transferBranchInternal(Rank0, Analysis &A, bool Branch,
- const Stmt *Stmt, TypeErasedLattice &L,
- Environment &Env)
- -> std::void_t<decltype(A.transferBranch(
- Branch, Stmt, std::declval<LatticeT &>(), Env))> {
- A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env);
- }
-
- // The second-choice implementation: `transferBranch` is unimplemented.
No-op.
- template <typename Analysis>
- static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *,
- TypeErasedLattice &, Environment &) {}
-
- ASTContext &Context;
-};
-
// Model of the program at a given program point.
template <typename LatticeT> struct DataflowAnalysisState {
// Model of a program property.
@@ -241,7 +108,7 @@ runDataflowAnalysis(const AdornedCFG &ACFG, AnalysisT
&Analysis,
[&PostAnalysisCallbacks](const CFGElement &Element,
const TypeErasedDataflowAnalysisState &State)
{
auto *Lattice =
- llvm::any_cast<typename
AnalysisT::Lattice>(&State.Lattice.Value);
+ llvm::cast<typename AnalysisT::Lattice>(State.Lattice.get());
// FIXME: we should not be copying the environment here!
// Ultimately the `CFGEltCallback` only gets a const reference
anyway.
PostAnalysisCallbacks.Before(
@@ -253,13 +120,13 @@ runDataflowAnalysis(const AdornedCFG &ACFG, AnalysisT
&Analysis,
TypeErasedCallbacks.After =
[&PostAnalysisCallbacks](const CFGElement &Element,
const TypeErasedDataflowAnalysisState &State)
{
- auto *Lattice =
- llvm::any_cast<typename
AnalysisT::Lattice>(&State.Lattice.Value);
+ auto &Lattice =
+ llvm::cast<typename AnalysisT::Lattice>(*State.Lattice);
// FIXME: we should not be copying the environment here!
// Ultimately the `CFGEltCallback` only gets a const reference
anyway.
PostAnalysisCallbacks.After(
Element, DataflowAnalysisState<typename AnalysisT::Lattice>{
- *Lattice, State.Env.fork()});
+ Lattice, State.Env.fork()});
};
}
@@ -278,8 +145,8 @@ runDataflowAnalysis(const AdornedCFG &ACFG, AnalysisT
&Analysis,
return llvm::transformOptional(
std::move(OptState), [](TypeErasedDataflowAnalysisState &&State) {
return DataflowAnalysisState<typename AnalysisT::Lattice>{
- llvm::any_cast<typename AnalysisT::Lattice>(
- std::move(State.Lattice.Value)),
+ llvm::cast<typename AnalysisT::Lattice>(
+ std::move(*State.Lattice)),
std::move(State.Env)};
});
});
@@ -341,8 +208,7 @@ diagnoseFunction(const FunctionDecl &FuncDecl, ASTContext
&ASTCtx,
auto EltDiagnostics = Diagnoser.Before(
Elt, ASTCtx,
TransferStateForDiagnostics<typename AnalysisT::Lattice>(
- llvm::any_cast<const typename AnalysisT::Lattice &>(
- State.Lattice.Value),
+ llvm::cast<typename AnalysisT::Lattice>(*State.Lattice),
State.Env));
llvm::move(EltDiagnostics, std::back_inserter(Diagnostics));
};
@@ -355,8 +221,7 @@ diagnoseFunction(const FunctionDecl &FuncDecl, ASTContext
&ASTCtx,
auto EltDiagnostics = Diagnoser.After(
Elt, ASTCtx,
TransferStateForDiagnostics<typename AnalysisT::Lattice>(
- llvm::any_cast<const typename AnalysisT::Lattice &>(
- State.Lattice.Value),
+ llvm::cast<typename AnalysisT::Lattice>(*State.Lattice),
State.Env));
llvm::move(EltDiagnostics, std::back_inserter(Diagnostics));
};
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h
index b262732804ed69..f773c0bf9fefe5 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h
@@ -14,6 +14,10 @@
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/ExtensibleRTTI.h"
+#include <memory>
+
namespace clang {
namespace dataflow {
@@ -25,6 +29,40 @@ enum class LatticeEffect {
// DEPRECATED. Use `LatticeEffect`.
using LatticeJoinEffect = LatticeEffect;
+class DataflowLattice
+ : public llvm::RTTIExtends<DataflowLattice, llvm::RTTIRoot> {
+public:
+ inline static char ID = 0;
+ DataflowLattice() = default;
+
+ /// Joins two type-erased lattice elements by computing their least upper
+ /// bound.
+ virtual LatticeEffect join(const DataflowLattice &) = 0;
+
+ virtual std::unique_ptr<DataflowLattice> clone() = 0;
+
+ /// Chooses a lattice element that approximates the current element at a
+ /// program point, given the previous element at that point. Places the
+ /// widened result in the current element (`Current`). Widening is optional
--
+ /// it is only needed to either accelerate convergence (for lattices with
+ /// non-trivial height) or guarantee convergence (for lattices with infinite
+ /// height).
+ ///
+ /// Returns an indication of whether any changes were made to `Current` in
+ /// order to widen. This saves a separate call to `isEqualTypeErased` after
+ /// the widening.
+ virtual LatticeEffect widen(const DataflowLattice &Previous) {
+ return isEqual(Previous) ? LatticeEffect::Unchanged
+ : LatticeEffect::Changed;
+ }
+
+ /// Returns true if and only if the two given type-erased lattice elements
are
+ /// equal.
+ virtual bool isEqual(const DataflowLattice &) const = 0;
+};
+
+using DataflowLatticePtr = std::unique_ptr<DataflowLattice>;
+
} // namespace dataflow
} // namespace clang
diff --git a/clang/include/clang/Analysis/FlowSensitive/Logger.h
b/clang/include/clang/Analysis/FlowSensitive/Logger.h
index f2e64810d00506..34d5865f6bb244 100644
--- a/clang/include/clang/Analysis/FlowSensitive/Logger.h
+++ b/clang/include/clang/Analysis/FlowSensitive/Logger.h
@@ -16,7 +16,7 @@
namespace clang::dataflow {
// Forward declarations so we can use Logger anywhere in the framework.
class AdornedCFG;
-class TypeErasedDataflowAnalysis;
+class DataflowAnalysis;
struct TypeErasedDataflowAnalysisState;
/// A logger is notified as the analysis progresses.
@@ -40,7 +40,7 @@ class Logger {
/// Called by the framework as we start analyzing a new function or
statement.
/// Forms a pair with endAnalysis().
- virtual void beginAnalysis(const AdornedCFG &, TypeErasedDataflowAnalysis &)
{
+ virtual void beginAnalysis(const AdornedCFG &, DataflowAnalysis &) {
}
virtual void endAnalysis() {}
diff --git a/clang/include/clang/Analysis/FlowSensitive/MapLattice.h
b/clang/include/clang/Analysis/FlowSensitive/MapLattice.h
index b2d147e4ae444b..0321d55b9863eb 100644
--- a/clang/include/clang/Analysis/FlowSensitive/MapLattice.h
+++ b/clang/include/clang/Analysis/FlowSensitive/MapLattice.h
@@ -36,11 +36,15 @@ namespace dataflow {
///
/// Requirements on `ElementLattice`:
/// * Provides standard declarations of a bounded semi-lattice.
-template <typename Key, typename ElementLattice> class MapLattice {
+template <typename Key, typename ElementLattice>
+class MapLattice : public llvm::RTTIExtends<MapLattice<Key, ElementLattice>,
+ DataflowLattice> {
using Container = llvm::DenseMap<Key, ElementLattice>;
Container C;
public:
+ inline static char ID = 0;
+
using key_type = Key;
using mapped_type = ElementLattice;
using value_type = typename Container::value_type;
@@ -89,18 +93,28 @@ template <typename Key, typename ElementLattice> class
MapLattice {
mapped_type &operator[](const key_type &K) { return C[K]; }
+
+ DataflowLatticePtr clone() override {
+ return std::make_unique<MapLattice>(*this);
+ }
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const MapLattice>(Other);
+ }
+
/// If an entry exists in one map but not the other, the missing entry is
/// treated as implicitly mapping to `bottom`. So, the joined map contains
the
/// entry as it was in the source map.
- LatticeJoinEffect join(const MapLattice &Other) {
- LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged;
+ LatticeEffect join(const DataflowLattice &L) override {
+ const auto &Other = llvm::cast<MapLattice>(L);
+ LatticeEffect Effect = LatticeEffect::Unchanged;
for (const auto &O : Other.C) {
auto It = C.find(O.first);
if (It == C.end()) {
C.insert(O);
- Effect = LatticeJoinEffect::Changed;
- } else if (It->second.join(O.second) == LatticeJoinEffect::Changed)
- Effect = LatticeJoinEffect::Changed;
+ Effect = LatticeEffect::Changed;
+ } else if (It->second.join(O.second) == LatticeEffect::Changed)
+ Effect = LatticeEffect::Changed;
}
return Effect;
}
diff --git
a/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h
b/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h
index 713494178b97bd..654c76efec823b 100644
---
a/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h
+++
b/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h
@@ -23,6 +23,8 @@
#include "clang/Analysis/FlowSensitive/NoopLattice.h"
#include "clang/Basic/SourceLocation.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/ExtensibleRTTI.h"
+#include <memory>
namespace clang {
namespace dataflow {
@@ -48,28 +50,34 @@ struct UncheckedOptionalAccessModelOptions {
bool IgnoreSmartPointerDereference = false;
};
-using UncheckedOptionalAccessLattice =
CachedConstAccessorsLattice<NoopLattice>;
+struct UncheckedOptionalAccessLattice
+ : public llvm::RTTIExtends<UncheckedOptionalAccessLattice,
+ CachedConstAccessorsLattice<NoopLattice>> {
+ inline static char ID = 0;
+};
/// Dataflow analysis that models whether optionals hold values or not.
///
/// Models the `std::optional`, `absl::optional`, and `base::Optional` types.
class UncheckedOptionalAccessModel
- : public DataflowAnalysis<UncheckedOptionalAccessModel,
- UncheckedOptionalAccessLattice> {
+ : public DataflowAnalysis {
public:
+ using Lattice = UncheckedOptionalAccessLattice;
+
UncheckedOptionalAccessModel(ASTContext &Ctx, dataflow::Environment &Env);
/// Returns a matcher for the optional classes covered by this model.
static ast_matchers::DeclarationMatcher optionalClassDecl();
- static UncheckedOptionalAccessLattice initialElement() { return {}; }
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>();
+ }
- void transfer(const CFGElement &Elt, UncheckedOptionalAccessLattice &L,
- Environment &Env);
+ void transfer(const CFGElement &Elt, DataflowLattice &L,
+ Environment &Env) override;
private:
- CFGMatchSwitch<TransferState<UncheckedOptionalAccessLattice>>
- TransferMatchSwitch;
+ CFGMatchSwitch<TransferState<Lattice>> TransferMatchSwitch;
};
class UncheckedOptionalAccessDiagnoser {
diff --git a/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h
b/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h
index 393f68300cb80c..a5efb001358514 100644
--- a/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h
+++ b/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h
@@ -13,26 +13,26 @@
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H
-#include "clang/AST/ASTContext.h"
#include "clang/Analysis/CFG.h"
-#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/NoopLattice.h"
+#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
+#include <memory>
namespace clang {
namespace dataflow {
-class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
+class NoopAnalysis : public DataflowAnalysis {
public:
- NoopAnalysis(ASTContext &Context)
- : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
+ using DataflowAnalysis::DataflowAnalysis;
+ using Lattice = NoopLattice;
- NoopAnalysis(ASTContext &Context, DataflowAnalysisOptions Options)
- : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context, Options) {}
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<NoopLattice>();
+ }
- static NoopLattice initialElement() { return {}; }
-
- void transfer(const CFGElement &E, NoopLattice &L, Environment &Env) {}
+ void transfer(const CFGElement &E, DataflowLattice &L,
+ Environment &Env) override {}
};
} // namespace dataflow
diff --git a/clang/include/clang/Analysis/FlowSensitive/NoopLattice.h
b/clang/include/clang/Analysis/FlowSensitive/NoopLattice.h
index 96c695473b67a1..e5201d6910ecbf 100644
--- a/clang/include/clang/Analysis/FlowSensitive/NoopLattice.h
+++ b/clang/include/clang/Analysis/FlowSensitive/NoopLattice.h
@@ -14,8 +14,7 @@
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOP_LATTICE_H
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
-#include "clang/Support/Compiler.h"
-#include "llvm/ADT/Any.h"
+#include <memory>
#include <ostream>
namespace clang {
@@ -24,13 +23,24 @@ namespace dataflow {
/// Trivial lattice for dataflow analysis with exactly one element.
///
/// Useful for analyses that only need the Environment and nothing more.
-class NoopLattice {
+class NoopLattice : public llvm::RTTIExtends<NoopLattice, DataflowLattice> {
public:
- bool operator==(const NoopLattice &Other) const { return true; }
+ inline static char ID = 0;
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return llvm::isa<NoopLattice>(Other);
+ }
+
+ std::unique_ptr<DataflowLattice> clone() override {
+ return std::make_unique<NoopLattice>();
+ }
- LatticeJoinEffect join(const NoopLattice &Other) {
+ LatticeEffect join(const DataflowLattice &Other) override {
+ assert(llvm::isa<NoopLattice>(Other));
return LatticeJoinEffect::Unchanged;
}
+
+ bool operator==(const NoopLattice &Other) const { return true; }
};
inline std::ostream &operator<<(std::ostream &OS, const NoopLattice &) {
@@ -40,13 +50,4 @@ inline std::ostream &operator<<(std::ostream &OS, const
NoopLattice &) {
} // namespace dataflow
} // namespace clang
-namespace llvm {
-// This needs to be exported for ClangAnalysisFlowSensitiveTests so any_cast
-// uses the correct address of Any::TypeId from the clang shared library
instead
-// of creating one in the test executable. when building with
-// CLANG_LINK_CLANG_DYLIB
-extern template struct CLANG_TEMPLATE_ABI
- Any::TypeId<clang::dataflow::NoopLattice>;
-} // namespace llvm
-
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOP_LATTICE_H
diff --git
a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
index 512453e2be67ad..dbad9d334e2696 100644
--- a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
+++ b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
@@ -25,7 +25,6 @@
#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
-#include "llvm/ADT/Any.h"
#include "llvm/Support/Error.h"
namespace clang {
@@ -40,95 +39,100 @@ struct DataflowAnalysisOptions {
DataflowAnalysisContext::Options{};
};
-/// Type-erased lattice element container.
+/// Base class template for dataflow analyses built on a single lattice type.
///
/// Requirements:
///
-/// The type of the object stored in the container must be a bounded
-/// join-semilattice.
-struct TypeErasedLattice {
- llvm::Any Value;
-};
+/// `Derived` must be derived from a specialization of this class template and
+/// must provide the following public members:
+/// * `LatticeT initialElement()` - returns a lattice element that models the
+/// initial state of a basic block;
+/// * `void transfer(const CFGElement &, LatticeT &, Environment &)` -
applies
+/// the analysis transfer function for a given CFG element and lattice
+/// element.
+///
+/// `Derived` can optionally provide the following members:
+/// * `void transferBranch(bool Branch, const Stmt *Stmt, TypeErasedLattice
&E,
+/// Environment &Env)` - applies the analysis transfer
+/// function for a given edge from a CFG block of a conditional statement.
+///
+/// `Derived` can optionally override the virtual functions in the
+/// `Environment::ValueModel` interface (which is an indirect base class of
+/// this class).
+///
+/// `LatticeT` is a bounded join-semilattice that is used by `Derived` and
must
+/// provide the following public members:
+/// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
+/// argument by computing their least upper bound, modifies the object if
+/// necessary, and returns an effect indicating whether any changes were
+/// made to it;
+/// FIXME: make it `static LatticeT join(const LatticeT&, const LatticeT&)`
+/// * `bool operator==(const LatticeT &) const` - returns true if and only if
+/// the object is equal to the argument.
+///
+/// `LatticeT` can optionally provide the following members:
+/// * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the
+/// lattice element with an approximation that can reach a fixed point more
+/// quickly than iterated application of the transfer function alone. The
+/// previous value is provided to inform the choice of widened value. The
+/// function must also serve as a comparison operation, by indicating
whether
+/// the widened value is equivalent to the previous value with the returned
+/// `LatticeJoinEffect`.
/// Type-erased base class for dataflow analyses built on a single lattice
type.
-class TypeErasedDataflowAnalysis : public Environment::ValueModel {
+class DataflowAnalysis : public Environment::ValueModel {
+ ASTContext &Context;
DataflowAnalysisOptions Options;
public:
- TypeErasedDataflowAnalysis() : Options({}) {}
-
- TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options)
- : Options(Options) {}
-
- virtual ~TypeErasedDataflowAnalysis() {}
-
- /// Returns the `ASTContext` that is used by the analysis.
- virtual ASTContext &getASTContext() = 0;
-
- /// Returns a type-erased lattice element that models the initial state of a
- /// basic block.
- virtual TypeErasedLattice typeErasedInitialElement() = 0;
-
- /// Joins two type-erased lattice elements by computing their least upper
- /// bound. Places the join result in the left element and returns an effect
- /// indicating whether any changes were made to it.
- virtual TypeErasedLattice joinTypeErased(const TypeErasedLattice &,
- const TypeErasedLattice &) = 0;
-
- /// Chooses a lattice element that approximates the current element at a
- /// program point, given the previous element at that point. Places the
- /// widened result in the current element (`Current`). Widening is optional
--
- /// it is only needed to either accelerate convergence (for lattices with
- /// non-trivial height) or guarantee convergence (for lattices with infinite
- /// height).
- ///
- /// Returns an indication of whether any changes were made to `Current` in
- /// order to widen. This saves a separate call to `isEqualTypeErased` after
- /// the widening.
- virtual LatticeJoinEffect
- widenTypeErased(TypeErasedLattice &Current,
- const TypeErasedLattice &Previous) = 0;
-
- /// Returns true if and only if the two given type-erased lattice elements
are
- /// equal.
- virtual bool isEqualTypeErased(const TypeErasedLattice &,
- const TypeErasedLattice &) = 0;
-
- /// Applies the analysis transfer function for a given control flow graph
- /// element and type-erased lattice element.
- virtual void transferTypeErased(const CFGElement &, TypeErasedLattice &,
- Environment &) = 0;
-
- /// Applies the analysis transfer function for a given edge from a CFG block
- /// of a conditional statement.
- /// @param Stmt The condition which is responsible for the split in the CFG.
- /// @param Branch True if the edge goes to the basic block where the
- /// condition is true.
- // FIXME: Change `Stmt` argument to a reference.
- virtual void transferBranchTypeErased(bool Branch, const Stmt *,
- TypeErasedLattice &, Environment &) =
0;
-
- /// If the built-in model is enabled, returns the options to be passed to
- /// them. Otherwise returns empty.
- const std::optional<DataflowAnalysisContext::Options> &
- builtinOptions() const {
- return Options.BuiltinOpts;
+ explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
+
+ explicit DataflowAnalysis(ASTContext &Context, DataflowAnalysisOptions
Options)
+ : Context(Context), Options(Options) {}
+
+ /// Returns the `ASTContext` that is used by the analysis.
+ ASTContext &getASTContext() { return Context; }
+
+ /// Returns a lattice element that models the initial state of a
+ /// basic block.
+ virtual DataflowLatticePtr initialElement() = 0;
+
+ /// Applies the analysis transfer function for a given control flow graph
+ /// element and type-erased lattice element. The derived type of Lattice will
+ /// always match the type of the lattice returned by `initialElement`.
+ virtual void transfer(const CFGElement &, DataflowLattice &Lattice,
+ Environment &) = 0;
+
+ /// Applies the analysis transfer function for a given edge from a CFG block
+ /// of a conditional statement. This method is optional and so the default
+ /// implementation is a no-op.
+ /// @param Stmt The condition which is responsible for the split in the CFG.
+ /// @param Branch True if the edge goes to the basic block where the
+ /// condition is true.
+ virtual void transferBranch(bool Branch, const Stmt &Stmt, DataflowLattice &,
+ Environment &) {};
+
+ /// If the built-in model is enabled, returns the options to be passed to
+ /// them. Otherwise returns empty.
+ const std::optional<DataflowAnalysisContext::Options> &builtinOptions() const
{
+ return Options.BuiltinOpts;
}
};
/// Type-erased model of the program at a given program point.
struct TypeErasedDataflowAnalysisState {
/// Type-erased model of a program property.
- TypeErasedLattice Lattice;
+ std::unique_ptr<DataflowLattice> Lattice;
/// Model of the state of the program (store and heap).
Environment Env;
- TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
+ TypeErasedDataflowAnalysisState(std::unique_ptr<DataflowLattice> Lattice,
+ Environment Env)
: Lattice(std::move(Lattice)), Env(std::move(Env)) {}
TypeErasedDataflowAnalysisState fork() const {
- return TypeErasedDataflowAnalysisState(Lattice, Env.fork());
+ return TypeErasedDataflowAnalysisState(Lattice->clone(), Env.fork());
}
};
@@ -159,7 +163,7 @@ struct CFGEltCallbacksTypeErased {
/// from converging.
llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>>
runTypeErasedDataflowAnalysis(
- const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,
+ const AdornedCFG &ACFG, DataflowAnalysis &Analysis,
const Environment &InitEnv,
const CFGEltCallbacksTypeErased &PostAnalysisCallbacks,
std::int32_t MaxBlockVisits);
diff --git a/clang/lib/Analysis/FlowSensitive/Arena.cpp
b/clang/lib/Analysis/FlowSensitive/Arena.cpp
index 7542a137c735e0..59d0fb2aa4208d 100644
--- a/clang/lib/Analysis/FlowSensitive/Arena.cpp
+++ b/clang/lib/Analysis/FlowSensitive/Arena.cpp
@@ -180,7 +180,7 @@ class FormulaParseError : public
llvm::ErrorInfo<FormulaParseError> {
unsigned Offset;
public:
- static char ID;
+ inline static char ID;
FormulaParseError(llvm::StringRef Formula, unsigned Offset)
: Formula(Formula), Offset(Offset) {}
@@ -195,8 +195,6 @@ class FormulaParseError : public
llvm::ErrorInfo<FormulaParseError> {
}
};
-char FormulaParseError::ID = 0;
-
} // namespace
llvm::Expected<const Formula &> Arena::parseFormula(llvm::StringRef In) {
diff --git a/clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp
b/clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp
index 557df218837941..ecec08be5febe5 100644
--- a/clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp
+++ b/clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp
@@ -175,8 +175,7 @@ class HTMLLogger : public Logger {
public:
explicit HTMLLogger(StreamFactory Streams) : Streams(std::move(Streams)) {}
- void beginAnalysis(const AdornedCFG &ACFG,
- TypeErasedDataflowAnalysis &A) override {
+ void beginAnalysis(const AdornedCFG &ACFG, DataflowAnalysis &A) override {
OS = Streams();
this->ACFG = &ACFG;
*OS << llvm::StringRef(HTMLLogger_html).split("<?INJECT?>").first;
diff --git a/clang/lib/Analysis/FlowSensitive/Logger.cpp
b/clang/lib/Analysis/FlowSensitive/Logger.cpp
index 8f40768171c94e..a2afe43e5a9b88 100644
--- a/clang/lib/Analysis/FlowSensitive/Logger.cpp
+++ b/clang/lib/Analysis/FlowSensitive/Logger.cpp
@@ -28,13 +28,13 @@ struct TextualLogger final : Logger {
unsigned CurrentElementIndex;
bool ShowColors;
llvm::DenseMap<const CFGBlock *, unsigned> VisitCount;
- TypeErasedDataflowAnalysis *CurrentAnalysis;
+ DataflowAnalysis *CurrentAnalysis;
TextualLogger(llvm::raw_ostream &OS)
: OS(OS), ShowColors(llvm::WithColor::defaultAutoDetectFunction()(OS)) {}
virtual void beginAnalysis(const AdornedCFG &ACFG,
- TypeErasedDataflowAnalysis &Analysis) override {
+ DataflowAnalysis &Analysis) override {
{
llvm::WithColor Header(OS, llvm::raw_ostream::Colors::RED,
/*Bold=*/true);
OS << "=== Beginning data flow analysis ===\n";
diff --git
a/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp
b/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp
index da5dda063344f9..7c1372f434fa9a 100644
--- a/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp
+++ b/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp
@@ -1102,9 +1102,7 @@ UncheckedOptionalAccessModel::optionalClassDecl() {
UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx,
Environment &Env)
- : DataflowAnalysis<UncheckedOptionalAccessModel,
- UncheckedOptionalAccessLattice>(Ctx),
- TransferMatchSwitch(buildTransferMatchSwitch()) {
+ : DataflowAnalysis(Ctx), TransferMatchSwitch(buildTransferMatchSwitch()) {
Env.getDataflowAnalysisContext().setSyntheticFieldCallback(
[&Ctx](QualType Ty) -> llvm::StringMap<QualType> {
const CXXRecordDecl *Optional =
@@ -1117,9 +1115,10 @@
UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx,
}
void UncheckedOptionalAccessModel::transfer(const CFGElement &Elt,
- UncheckedOptionalAccessLattice &L,
+ DataflowLattice &L,
Environment &Env) {
- LatticeTransferState State(L, Env);
+ LatticeTransferState State(llvm::cast<UncheckedOptionalAccessLattice>(L),
+ Env);
TransferMatchSwitch(Elt, getASTContext(), State);
}
diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp
b/clang/lib/Analysis/FlowSensitive/Transfer.cpp
index 9c54eb16d22246..6c00640768e532 100644
--- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp
+++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp
@@ -22,6 +22,7 @@
#include "clang/AST/StmtVisitor.h"
#include "clang/Analysis/FlowSensitive/ASTOps.h"
#include "clang/Analysis/FlowSensitive/AdornedCFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
index 32b3886439495f..98c2acec9ff295 100644
--- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -26,11 +26,10 @@
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
-#include "clang/Analysis/FlowSensitive/RecordOps.h"
+#include "clang/Analysis/FlowSensitive/Logger.h"
#include "clang/Analysis/FlowSensitive/Transfer.h"
#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
#include "clang/Analysis/FlowSensitive/Value.h"
-#include "clang/Support/Compiler.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Debug.h"
@@ -38,27 +37,13 @@
#define DEBUG_TYPE "clang-dataflow"
-namespace clang {
-namespace dataflow {
-class NoopLattice;
-}
-} // namespace clang
-
-namespace llvm {
-// This needs to be exported for ClangAnalysisFlowSensitiveTests so any_cast
-// uses the correct address of Any::TypeId from the clang shared library
instead
-// of creating one in the test executable. when building with
-// CLANG_LINK_CLANG_DYLIB
-template struct CLANG_EXPORT_TEMPLATE
Any::TypeId<clang::dataflow::NoopLattice>;
-} // namespace llvm
-
namespace clang {
namespace dataflow {
/// Returns the index of `Block` in the successors of `Pred`.
static int blockIndexInPredecessor(const CFGBlock &Pred,
const CFGBlock &Block) {
- auto BlockPos = llvm::find_if(
+ const auto *BlockPos = llvm::find_if(
Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
return Succ && Succ->getBlockID() == Block.getBlockID();
});
@@ -102,7 +87,7 @@ class TerminatorVisitor
/// Holds data structures required for running dataflow analysis.
struct AnalysisContext {
- AnalysisContext(const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,
+ AnalysisContext(const AdornedCFG &ACFG, DataflowAnalysis &Analysis,
const Environment &InitEnv,
llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>>
BlockStates)
@@ -116,7 +101,7 @@ struct AnalysisContext {
/// Contains the CFG being analyzed.
const AdornedCFG &ACFG;
/// The analysis to be run.
- TypeErasedDataflowAnalysis &Analysis;
+ DataflowAnalysis &Analysis;
/// Initial state to start the analysis.
const Environment &InitEnv;
Logger &Log;
@@ -179,7 +164,9 @@ class JoinedStateBuilder {
TypeErasedDataflowAnalysisState
join(const TypeErasedDataflowAnalysisState &L,
const TypeErasedDataflowAnalysisState &R) {
- return {AC.Analysis.joinTypeErased(L.Lattice, R.Lattice),
+ auto L2 = L.Lattice->clone();
+ L2->join(*R.Lattice);
+ return {std::move(L2),
Environment::join(L.Env, R.Env, AC.Analysis, JoinBehavior)};
}
@@ -200,14 +187,15 @@ class JoinedStateBuilder {
// FIXME: Consider passing `Block` to Analysis.typeErasedInitialElement
// to enable building analyses like computation of dominators that
// initialize the state of each basic block differently.
- return {AC.Analysis.typeErasedInitialElement(), AC.InitEnv.fork()};
+ return {AC.Analysis.initialElement(), AC.InitEnv.fork()};
if (All.size() == 1)
// Join the environment with itself so that we discard expression state
if
// desired.
// FIXME: We could consider writing special-case code for this that only
// does the discarding, but it's not clear if this is worth it.
- return {All[0]->Lattice, Environment::join(All[0]->Env, All[0]->Env,
- AC.Analysis, JoinBehavior)};
+ return {All[0]->Lattice->clone(),
+ Environment::join(All[0]->Env, All[0]->Env, AC.Analysis,
+ JoinBehavior)};
auto Result = join(*All[0], *All[1]);
for (unsigned I = 2; I < All.size(); ++I)
@@ -317,8 +305,7 @@ computeBlockInputState(const CFGBlock &Block,
AnalysisContext &AC) {
BranchVal ? CondVal : &Copy.Env.makeNot(*CondVal);
Copy.Env.assume(AssertedVal->formula());
}
- AC.Analysis.transferBranchTypeErased(BranchVal, Cond, Copy.Lattice,
- Copy.Env);
+ AC.Analysis.transferBranch(BranchVal, *Cond, *Copy.Lattice, Copy.Env);
Builder.addOwned(std::move(Copy));
}
return std::move(Builder).take();
@@ -449,7 +436,7 @@ transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC,
}
// User-provided analysis
- AC.Analysis.transferTypeErased(Element, State.Lattice, State.Env);
+ AC.Analysis.transfer(Element, *State.Lattice, State.Env);
if (PostAnalysisCallbacks.After) {
PostAnalysisCallbacks.After(Element, State);
@@ -487,7 +474,7 @@ transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC,
llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>>
runTypeErasedDataflowAnalysis(
- const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,
+ const AdornedCFG &ACFG, DataflowAnalysis &Analysis,
const Environment &InitEnv,
const CFGEltCallbacksTypeErased &PostAnalysisCallbacks,
std::int32_t MaxBlockVisits) {
@@ -510,7 +497,7 @@ runTypeErasedDataflowAnalysis(
// The entry basic block doesn't contain statements so it can be skipped.
const CFGBlock &Entry = CFG.getEntry();
- BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
+ BlockStates[Entry.getBlockID()] = {Analysis.initialElement(),
StartingEnv.fork()};
Worklist.enqueueSuccessors(&Entry);
@@ -539,19 +526,18 @@ runTypeErasedDataflowAnalysis(
OldBlockState->Env.dump();
});
if (isBackedgeNode(*Block)) {
- LatticeJoinEffect Effect1 = Analysis.widenTypeErased(
- NewBlockState.Lattice, OldBlockState->Lattice);
- LatticeJoinEffect Effect2 =
+ LatticeEffect Effect1 =
+ NewBlockState.Lattice->widen(*OldBlockState->Lattice);
+ LatticeEffect Effect2 =
NewBlockState.Env.widen(OldBlockState->Env, Analysis);
- if (Effect1 == LatticeJoinEffect::Unchanged &&
- Effect2 == LatticeJoinEffect::Unchanged) {
+ if (Effect1 == LatticeEffect::Unchanged &&
+ Effect2 == LatticeEffect::Unchanged) {
// The state of `Block` didn't change from widening so there's no
need
// to revisit its successors.
AC.Log.blockConverged();
continue;
}
- } else if (Analysis.isEqualTypeErased(OldBlockState->Lattice,
- NewBlockState.Lattice) &&
+ } else if (OldBlockState->Lattice->isEqual(*NewBlockState.Lattice) &&
OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis))
{
// The state of `Block` didn't change after transfer so there's no need
// to revisit its successors.
diff --git a/clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp
b/clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp
index a2762046665a2c..532ab4716bd761 100644
--- a/clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/ChromiumCheckModelTest.cpp
@@ -108,16 +108,19 @@ std::string ReplacePattern(std::string S, const
std::string &Pattern,
return S;
}
-template <typename Model>
-class ModelAdaptorAnalysis
- : public DataflowAnalysis<ModelAdaptorAnalysis<Model>, NoopLattice> {
+template <typename Model> class ModelAdaptorAnalysis : public DataflowAnalysis
{
public:
+ using Lattice = NoopLattice;
+
explicit ModelAdaptorAnalysis(ASTContext &Context)
- : DataflowAnalysis<ModelAdaptorAnalysis, NoopLattice>(Context) {}
+ : DataflowAnalysis(Context) {}
- static NoopLattice initialElement() { return NoopLattice(); }
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>();
+ }
- void transfer(const CFGElement &E, NoopLattice &, Environment &Env) {
+ void transfer(const CFGElement &E, DataflowLattice &,
+ Environment &Env) override {
M.transfer(E, Env);
}
diff --git a/clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
b/clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
index 88630119ba8a1a..c9cf006d0ff814 100644
--- a/clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
@@ -1,8 +1,9 @@
#include "TestingSupport.h"
#include "clang/ASTMatchers/ASTMatchers.h"
-#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
+#include "llvm/Support/ExtensibleRTTI.h"
#include "llvm/Testing/Support/Error.h"
#include "gtest/gtest.h"
@@ -10,43 +11,59 @@ namespace clang::dataflow::test {
namespace {
using testing::HasSubstr;
-struct TestLattice {
+struct TestLattice : public llvm::RTTIExtends<TestLattice, DataflowLattice> {
+ inline static char ID = 0;
+
int Elements = 0;
int Branches = 0;
int Joins = 0;
- LatticeJoinEffect join(const TestLattice &Other) {
+ DataflowLatticePtr clone() override {
+ return std::make_unique<TestLattice>(*this);
+ }
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const TestLattice>(Other);
+ }
+
+ LatticeEffect join(const DataflowLattice &L) override {
+ const auto &Other = llvm::cast<const TestLattice>(L);
if (Joins < 3) {
++Joins;
Elements += Other.Elements;
Branches += Other.Branches;
- return LatticeJoinEffect::Changed;
+ return LatticeEffect::Changed;
}
- return LatticeJoinEffect::Unchanged;
+ return LatticeEffect::Unchanged;
}
- friend bool operator==(const TestLattice &LHS, const TestLattice &RHS) {
- return std::tie(LHS.Elements, LHS.Branches, LHS.Joins) ==
+
+ bool operator==(const TestLattice &RHS) const {
+ return std::tie(Elements, Branches, Joins) ==
std::tie(RHS.Elements, RHS.Branches, RHS.Joins);
}
};
-class TestAnalysis : public DataflowAnalysis<TestAnalysis, TestLattice> {
+class TestAnalysis : public DataflowAnalysis {
public:
+ using Lattice = TestLattice;
using DataflowAnalysis::DataflowAnalysis;
- static TestLattice initialElement() { return TestLattice{}; }
- void transfer(const CFGElement &, TestLattice &L, Environment &E) {
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>();
+ }
+ void transfer(const CFGElement &, DataflowLattice &L,
+ Environment &E) override {
E.getDataflowAnalysisContext().getOptions().Log->log(
[](llvm::raw_ostream &OS) { OS << "transfer()"; });
- ++L.Elements;
+ ++llvm::cast<Lattice>(L).Elements;
}
- void transferBranch(bool Branch, const Stmt *S, TestLattice &L,
- Environment &E) {
+ void transferBranch(bool Branch, const Stmt &, DataflowLattice &L,
+ Environment &E) override {
E.getDataflowAnalysisContext().getOptions().Log->log(
[&](llvm::raw_ostream &OS) {
OS << "transferBranch(" << Branch << ")";
});
- ++L.Branches;
+ ++llvm::cast<Lattice>(L).Branches;
}
};
@@ -57,8 +74,7 @@ class TestLogger : public Logger {
private:
llvm::raw_string_ostream OS;
- void beginAnalysis(const AdornedCFG &,
- TypeErasedDataflowAnalysis &) override {
+ void beginAnalysis(const AdornedCFG &, DataflowAnalysis &) override {
logText("beginAnalysis()");
}
void endAnalysis() override { logText("\nendAnalysis()"); }
@@ -76,7 +92,7 @@ class TestLogger : public Logger {
OS << "enterElement(" << llvm::StringRef(S).trim() << ")\n";
}
void recordState(TypeErasedDataflowAnalysisState &S) override {
- const TestLattice &L = llvm::any_cast<TestLattice>(S.Lattice.Value);
+ const TestLattice &L = llvm::cast<TestLattice>(*S.Lattice);
OS << "recordState(Elements=" << L.Elements << ", Branches=" << L.Branches
<< ", Joins=" << L.Joins << ")\n";
}
diff --git a/clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp
b/clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp
index f6fe81e0dfc5f6..e03d611443daaa 100644
--- a/clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp
@@ -1,6 +1,7 @@
#include "clang/Analysis/FlowSensitive/MapLattice.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "llvm/Support/Error.h"
+#include "llvm/Support/ExtensibleRTTI.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include <ostream>
@@ -10,7 +11,7 @@ using namespace dataflow;
namespace {
// A simple lattice for basic tests.
-class BooleanLattice {
+class BooleanLattice : public DataflowLattice {
public:
BooleanLattice() : Value(false) {}
explicit BooleanLattice(bool B) : Value(B) {}
@@ -19,7 +20,16 @@ class BooleanLattice {
static BooleanLattice top() { return BooleanLattice(true); }
- LatticeJoinEffect join(BooleanLattice Other) {
+ DataflowLatticePtr clone() override {
+ return std::make_unique<BooleanLattice>(*this);
+ }
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const BooleanLattice>(Other);
+ }
+
+ LatticeEffect join(const DataflowLattice &L) override {
+ const auto &Other = llvm::cast<BooleanLattice>(L);
auto Prev = Value;
Value = Value || Other.Value;
return Prev == Value ? LatticeJoinEffect::Unchanged
@@ -44,6 +54,8 @@ class BooleanLattice {
private:
bool Value;
};
+
+using BoolMapLattice = MapLattice<int, BooleanLattice>;
} // namespace
static constexpr int Key1 = 0;
@@ -55,7 +67,7 @@ using ::testing::Pair;
using ::testing::UnorderedElementsAre;
TEST(MapLatticeTest, InsertWorks) {
- MapLattice<int, BooleanLattice> Lattice;
+ BoolMapLattice Lattice;
EXPECT_THAT(Lattice.insert({Key1, BooleanLattice(false)}), Pair(_, true));
EXPECT_THAT(Lattice.insert({Key2, BooleanLattice(false)}), Pair(_, true));
@@ -68,10 +80,10 @@ TEST(MapLatticeTest, InsertWorks) {
}
TEST(MapLatticeTest, ComparisonWorks) {
- MapLattice<int, BooleanLattice> Lattice1;
+ BoolMapLattice Lattice1;
Lattice1.insert({Key1, BooleanLattice(true)});
Lattice1.insert({Key2, BooleanLattice(false)});
- MapLattice<int, BooleanLattice> Lattice2 = Lattice1;
+ BoolMapLattice Lattice2 = Lattice1;
EXPECT_EQ(Lattice1, Lattice2);
Lattice2.find(Key2)->second = BooleanLattice(true);
@@ -79,11 +91,11 @@ TEST(MapLatticeTest, ComparisonWorks) {
}
TEST(MapLatticeTest, JoinChange) {
- MapLattice<int, BooleanLattice> Lattice1;
+ BoolMapLattice Lattice1;
Lattice1.insert({Key1, BooleanLattice(false)});
Lattice1.insert({Key2, BooleanLattice(false)});
- MapLattice<int, BooleanLattice> Lattice2;
+ BoolMapLattice Lattice2;
Lattice2.insert({Key1, BooleanLattice(true)});
Lattice2.insert({Key2, BooleanLattice(true)});
@@ -97,7 +109,7 @@ TEST(MapLatticeTest, JoinChange) {
}
TEST(MapLatticeTest, JoinEqNoChange) {
- MapLattice<int, BooleanLattice> Lattice;
+ BoolMapLattice Lattice;
Lattice.insert({Key1, BooleanLattice(false)});
Lattice.insert({Key2, BooleanLattice(false)});
@@ -107,11 +119,11 @@ TEST(MapLatticeTest, JoinEqNoChange) {
}
TEST(MapLatticeTest, JoinLtNoChange) {
- MapLattice<int, BooleanLattice> Lattice1;
+ BoolMapLattice Lattice1;
Lattice1.insert({Key1, BooleanLattice(false)});
Lattice1.insert({Key2, BooleanLattice(false)});
- MapLattice<int, BooleanLattice> Lattice2;
+ BoolMapLattice Lattice2;
Lattice2.insert({Key1, BooleanLattice(true)});
Lattice2.insert({Key2, BooleanLattice(true)});
@@ -128,9 +140,9 @@ TEST(MapLatticeTest, JoinLtNoChange) {
}
TEST(MapLatticeTest, JoinDifferentDomainsProducesUnion) {
- MapLattice<int, BooleanLattice> Lattice1;
+ BoolMapLattice Lattice1;
Lattice1.insert({Key1, BooleanLattice(true)});
- MapLattice<int, BooleanLattice> Lattice2;
+ BoolMapLattice Lattice2;
Lattice2.insert({Key2, BooleanLattice(true)});
ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
@@ -139,7 +151,7 @@ TEST(MapLatticeTest, JoinDifferentDomainsProducesUnion) {
}
TEST(MapLatticeTest, FindWorks) {
- MapLattice<int, BooleanLattice> Lattice;
+ BoolMapLattice Lattice;
Lattice.insert({Key1, BooleanLattice(true)});
Lattice.insert({Key2, BooleanLattice(false)});
@@ -153,7 +165,7 @@ TEST(MapLatticeTest, FindWorks) {
}
TEST(MapLatticeTest, ContainsWorks) {
- MapLattice<int, BooleanLattice> Lattice;
+ BoolMapLattice Lattice;
Lattice.insert({Key1, BooleanLattice(true)});
EXPECT_TRUE(Lattice.contains(Key1));
EXPECT_FALSE(Lattice.contains(Key2));
diff --git
a/clang/unittests/Analysis/FlowSensitive/MultiVarConstantPropagationTest.cpp
b/clang/unittests/Analysis/FlowSensitive/MultiVarConstantPropagationTest.cpp
index ed95887a45f1a3..a7f2e4900b438c 100644
--- a/clang/unittests/Analysis/FlowSensitive/MultiVarConstantPropagationTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/MultiVarConstantPropagationTest.cpp
@@ -45,7 +45,9 @@ using namespace ast_matchers;
// Models the value of an expression at a program point, for all paths through
// the program.
-struct ValueLattice {
+struct ValueLattice : public llvm::RTTIExtends<ValueLattice, DataflowLattice> {
+ inline static char ID = 0;
+
// FIXME: change the internal representation to use a `std::variant`, once
// clang admits C++17 constructs.
enum class ValueState : bool {
@@ -61,15 +63,14 @@ struct ValueLattice {
// `State`.
std::optional<int64_t> Value;
- constexpr ValueLattice()
- : State(ValueState::Undefined), Value(std::nullopt) {}
- constexpr ValueLattice(int64_t V) : State(ValueState::Defined), Value(V) {}
- constexpr ValueLattice(ValueState S) : State(S), Value(std::nullopt) {}
+ ValueLattice() : State(ValueState::Undefined), Value(std::nullopt) {}
+ explicit ValueLattice(int64_t V) : State(ValueState::Defined), Value(V) {}
+ explicit ValueLattice(ValueState S) : State(S), Value(std::nullopt) {}
- static constexpr ValueLattice bottom() {
+ static ValueLattice bottom() {
return ValueLattice(ValueState::Undefined);
}
- static constexpr ValueLattice top() {
+ static ValueLattice top() {
return ValueLattice(ValueState::Defined);
}
@@ -80,17 +81,26 @@ struct ValueLattice {
return !(Lhs == Rhs);
}
- LatticeJoinEffect join(const ValueLattice &Other) {
+ DataflowLatticePtr clone() override {
+ return std::make_unique<ValueLattice>(*this);
+ }
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const ValueLattice>(Other);
+ }
+
+ LatticeEffect join(const DataflowLattice &L) override {
+ const auto &Other = llvm::cast<ValueLattice>(L);
if (*this == Other || Other == bottom() || *this == top())
- return LatticeJoinEffect::Unchanged;
+ return LatticeEffect::Unchanged;
if (*this == bottom()) {
*this = Other;
- return LatticeJoinEffect::Changed;
+ return LatticeEffect::Changed;
}
*this = top();
- return LatticeJoinEffect::Changed;
+ return LatticeEffect::Changed;
}
};
@@ -122,24 +132,24 @@ auto refToVar() { return
declRefExpr(to(varDecl().bind(kVar))); }
// not account for the variable's address possibly escaping, which would
// invalidate the analysis. It also could be optimized to drop out-of-scope
// variables from the map.
-class ConstantPropagationAnalysis
- : public DataflowAnalysis<ConstantPropagationAnalysis,
- ConstantPropagationLattice> {
+class ConstantPropagationAnalysis : public DataflowAnalysis {
public:
+ using Lattice = ConstantPropagationLattice;
+
explicit ConstantPropagationAnalysis(ASTContext &Context)
- : DataflowAnalysis<ConstantPropagationAnalysis,
- ConstantPropagationLattice>(Context) {}
+ : DataflowAnalysis(Context) {}
- static ConstantPropagationLattice initialElement() {
- return ConstantPropagationLattice::bottom();
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>(ConstantPropagationLattice::bottom());
}
- void transfer(const CFGElement &E, ConstantPropagationLattice &Vars,
- Environment &Env) {
+ void transfer(const CFGElement &E, DataflowLattice &L,
+ Environment &Env) override {
+ auto &Vars = llvm::cast<ConstantPropagationLattice>(L);
auto CS = E.getAs<CFGStmt>();
if (!CS)
return;
- auto S = CS->getStmt();
+ auto *S = CS->getStmt();
auto matcher =
stmt(anyOf(declStmt(hasSingleDecl(
varDecl(decl().bind(kVar), hasType(isInteger()),
diff --git a/clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp
b/clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp
index b8fc528dbdce07..9e2166d6bc0edb 100644
--- a/clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp
@@ -351,17 +351,19 @@ auto buildTransferMatchSwitch() {
.Build();
}
-class SignPropagationAnalysis
- : public DataflowAnalysis<SignPropagationAnalysis, NoopLattice> {
+class SignPropagationAnalysis : public DataflowAnalysis {
public:
+ using Lattice = NoopLattice;
+
SignPropagationAnalysis(ASTContext &Context)
- : DataflowAnalysis<SignPropagationAnalysis, NoopLattice>(Context),
+ : DataflowAnalysis(Context),
TransferMatchSwitch(buildTransferMatchSwitch()) {}
- static NoopLattice initialElement() { return {}; }
+ std::unique_ptr<DataflowLattice> initialElement() override { return {}; }
- void transfer(const CFGElement &Elt, NoopLattice &L, Environment &Env) {
- LatticeTransferState State(L, Env);
+ void transfer(const CFGElement &Elt, DataflowLattice &L,
+ Environment &Env) override {
+ LatticeTransferState State(llvm::cast<NoopLattice>(L), Env);
TransferMatchSwitch(Elt, getASTContext(), State);
}
void join(QualType Type, const Value &Val1, const Environment &Env1,
diff --git
a/clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp
b/clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp
index b76ce4fa426427..9670cfa344b5b5 100644
---
a/clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp
+++
b/clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp
@@ -46,7 +46,10 @@ using namespace ast_matchers;
// A semi-lattice for dataflow analysis that tracks the value of a single
// integer variable. If it can be identified with a single (constant) value,
// then that value is stored.
-struct ConstantPropagationLattice {
+struct ConstantPropagationLattice
+ : public llvm::RTTIExtends<ConstantPropagationLattice, DataflowLattice> {
+ inline static char ID = 0;
+
// A null `Var` represents "top": either more than one value is possible or
// more than one variable was encountered. Otherwise, `Data` indicates that
// `Var` has the given `Value` at the program point with which this lattice
@@ -62,11 +65,14 @@ struct ConstantPropagationLattice {
// `std::nullopt` is "bottom".
std::optional<VarValue> Data;
- static constexpr ConstantPropagationLattice bottom() {
- return {std::nullopt};
+ explicit ConstantPropagationLattice(std::optional<VarValue> Data)
+ : Data(std::move(Data)) {}
+
+ static ConstantPropagationLattice bottom() {
+ return ConstantPropagationLattice{std::nullopt};
}
- static constexpr ConstantPropagationLattice top() {
- return {VarValue{nullptr, 0}};
+ static ConstantPropagationLattice top() {
+ return ConstantPropagationLattice{VarValue{nullptr, 0}};
}
friend bool operator==(const ConstantPropagationLattice &Lhs,
@@ -74,17 +80,26 @@ struct ConstantPropagationLattice {
return Lhs.Data == Rhs.Data;
}
- LatticeJoinEffect join(const ConstantPropagationLattice &Other) {
+ DataflowLatticePtr clone() override {
+ return std::make_unique<ConstantPropagationLattice>(*this);
+ }
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const ConstantPropagationLattice>(Other);
+ }
+
+ LatticeEffect join(const DataflowLattice &L) override {
+ const auto &Other = llvm::cast<ConstantPropagationLattice>(L);
if (*this == Other || Other == bottom() || *this == top())
- return LatticeJoinEffect::Unchanged;
+ return LatticeEffect::Unchanged;
if (*this == bottom()) {
*this = Other;
- return LatticeJoinEffect::Changed;
+ return LatticeEffect::Changed;
}
*this = top();
- return LatticeJoinEffect::Changed;
+ return LatticeEffect::Changed;
}
};
@@ -112,24 +127,23 @@ namespace {
// details needed for a real analysis in production. Most notably, the transfer
// function does not account for the variable's address possibly escaping,
which
// would invalidate the analysis.
-class ConstantPropagationAnalysis
- : public DataflowAnalysis<ConstantPropagationAnalysis,
- ConstantPropagationLattice> {
+class ConstantPropagationAnalysis : public DataflowAnalysis {
public:
+ using Lattice = ConstantPropagationLattice;
explicit ConstantPropagationAnalysis(ASTContext &Context)
- : DataflowAnalysis<ConstantPropagationAnalysis,
- ConstantPropagationLattice>(Context) {}
+ : DataflowAnalysis(Context) {}
- static ConstantPropagationLattice initialElement() {
- return ConstantPropagationLattice::bottom();
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>(ConstantPropagationLattice::bottom());
}
- void transfer(const CFGElement &E, ConstantPropagationLattice &Element,
- Environment &Env) {
+ void transfer(const CFGElement &E, DataflowLattice &L,
+ Environment &Env) override {
+ auto &Element = llvm::cast<ConstantPropagationLattice>(L);
auto CS = E.getAs<CFGStmt>();
if (!CS)
return;
- auto S = CS->getStmt();
+ auto *S = CS->getStmt();
auto matcher = stmt(
anyOf(declStmt(hasSingleDecl(varDecl(hasType(isInteger()),
hasInitializer(expr().bind(kInit)))
diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h
b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h
index 2ba84373531c6d..13482f2aad075f 100644
--- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h
+++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h
@@ -102,7 +102,7 @@ struct AnalysisOutputs {
/// function and is analyzed.
const AdornedCFG &ACFG;
/// The analysis to be run.
- TypeErasedDataflowAnalysis &Analysis;
+ DataflowAnalysis &Analysis;
/// Initial state to start the analysis.
const Environment &InitEnv;
// Stores the state of a CFG block if it has been evaluated by the analysis.
@@ -254,8 +254,7 @@ checkDataflow(AnalysisInputs<AnalysisT> AI,
AI.Callbacks.Before(
Context, Element,
TransferStateForDiagnostics<typename AnalysisT::Lattice>(
- llvm::any_cast<const typename AnalysisT::Lattice &>(
- State.Lattice.Value),
+ llvm::cast<const typename AnalysisT::Lattice>(State.Lattice),
State.Env));
};
}
@@ -266,8 +265,7 @@ checkDataflow(AnalysisInputs<AnalysisT> AI,
AI.Callbacks.After(
Context, Element,
TransferStateForDiagnostics<typename AnalysisT::Lattice>(
- llvm::any_cast<const typename AnalysisT::Lattice &>(
- State.Lattice.Value),
+ llvm::cast<const typename AnalysisT::Lattice>(State.Lattice),
State.Env));
};
}
diff --git a/clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp
b/clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp
index ef78131dd72a3a..651541923fb658 100644
--- a/clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp
@@ -25,12 +25,22 @@ namespace {
using namespace ast_matchers;
-struct TestLattice {
+struct TestLattice : public llvm::RTTIExtends<TestLattice, DataflowLattice> {
+ inline static char ID = 0;
+
std::optional<bool> Branch;
static TestLattice bottom() { return {}; }
+ DataflowLatticePtr clone() override {
+ return std::make_unique<TestLattice>(*this);
+ }
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const TestLattice>(Other);
+ }
+
// Does not matter for this test, but we must provide some definition of
join.
- LatticeJoinEffect join(const TestLattice &Other) {
+ LatticeJoinEffect join(const DataflowLattice &) override {
return LatticeJoinEffect::Unchanged;
}
friend bool operator==(const TestLattice &Lhs, const TestLattice &Rhs) {
@@ -38,16 +48,19 @@ struct TestLattice {
}
};
-class TestPropagationAnalysis
- : public DataflowAnalysis<TestPropagationAnalysis, TestLattice> {
+class TestPropagationAnalysis : public DataflowAnalysis {
public:
+ using Lattice = TestLattice;
+
explicit TestPropagationAnalysis(ASTContext &Context)
- : DataflowAnalysis<TestPropagationAnalysis, TestLattice>(Context) {}
- static TestLattice initialElement() { return TestLattice::bottom(); }
- void transfer(const CFGElement &, TestLattice &, Environment &) {}
- void transferBranch(bool Branch, const Stmt *S, TestLattice &L,
- Environment &Env) {
- L.Branch = Branch;
+ : DataflowAnalysis(Context) {}
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>(TestLattice::bottom());
+ }
+ void transfer(const CFGElement &, DataflowLattice &, Environment &) override
{}
+ void transferBranch(bool Branch, const Stmt &S, DataflowLattice &L,
+ Environment &Env) override {
+ llvm::cast<Lattice>(L).Branch = Branch;
}
};
diff --git
a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
index 8717d9753d161b..ce0af893a8fee3 100644
--- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -20,6 +20,7 @@
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "clang/Analysis/FlowSensitive/DebugSupport.h"
#include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
+#include "clang/Analysis/FlowSensitive/NoopLattice.h"
#include "clang/Analysis/FlowSensitive/Value.h"
#include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
#include "clang/Tooling/Tooling.h"
@@ -28,6 +29,7 @@
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Error.h"
+#include "llvm/Support/ExtensibleRTTI.h"
#include "llvm/Testing/ADT/StringMapEntry.h"
#include "llvm/Testing/Support/Error.h"
#include "gmock/gmock.h"
@@ -407,34 +409,50 @@ TEST_F(DiscardExprStateTest,
CallWithParenExprTreatedCorrectly) {
EXPECT_NE(CallExpectState.Env.getValue(FnToPtrDecay), nullptr);
}
-struct NonConvergingLattice {
+struct NonConvergingLattice
+ : public llvm::RTTIExtends<NonConvergingLattice, DataflowLattice> {
+ inline static char ID = 0;
int State;
+ explicit NonConvergingLattice(int S) : State(S) {}
+
bool operator==(const NonConvergingLattice &Other) const {
return State == Other.State;
}
- LatticeJoinEffect join(const NonConvergingLattice &Other) {
- if (Other.State == 0)
+ LatticeEffect join(const DataflowLattice &Other) override {
+ const auto &L = llvm::cast<const NonConvergingLattice>(Other);
+ if (L.State == 0)
return LatticeJoinEffect::Unchanged;
- State += Other.State;
+ State += L.State;
return LatticeJoinEffect::Changed;
}
+
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const NonConvergingLattice>(Other);
+ }
+
+ std::unique_ptr<DataflowLattice> clone() override {
+ return std::make_unique<NonConvergingLattice>(*this);
+ }
};
-class NonConvergingAnalysis
- : public DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice> {
+class NonConvergingAnalysis : public DataflowAnalysis {
public:
+ using Lattice = NonConvergingLattice;
+
explicit NonConvergingAnalysis(ASTContext &Context)
- : DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice>(
- Context,
- // Don't apply builtin transfer function.
- DataflowAnalysisOptions{std::nullopt}) {}
+ : DataflowAnalysis(Context,
+ // Don't apply builtin transfer function.
+ DataflowAnalysisOptions{std::nullopt}) {}
- static NonConvergingLattice initialElement() { return {0}; }
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>(0);
+ }
- void transfer(const CFGElement &, NonConvergingLattice &E, Environment &) {
- ++E.State;
+ void transfer(const CFGElement &, DataflowLattice &L,
+ Environment &) override {
+ ++llvm::cast<NonConvergingLattice>(L).State;
}
};
@@ -481,7 +499,9 @@ TEST_F(DataflowAnalysisTest, JoinBoolLValues) {
llvm::Succeeded());
}
-struct FunctionCallLattice {
+struct FunctionCallLattice
+ : public llvm::RTTIExtends<FunctionCallLattice, DataflowLattice> {
+ inline static char ID = 0;
using FunctionSet = llvm::SmallSet<std::string, 8>;
FunctionSet CalledFunctions;
@@ -489,7 +509,8 @@ struct FunctionCallLattice {
return CalledFunctions == Other.CalledFunctions;
}
- LatticeJoinEffect join(const FunctionCallLattice &Other) {
+ LatticeEffect join(const DataflowLattice &L) override {
+ const auto &Other = llvm::cast<const FunctionCallLattice>(L);
if (Other.CalledFunctions.empty())
return LatticeJoinEffect::Unchanged;
const size_t size_before = CalledFunctions.size();
@@ -498,6 +519,13 @@ struct FunctionCallLattice {
return CalledFunctions.size() == size_before ? LatticeJoinEffect::Unchanged
: LatticeJoinEffect::Changed;
}
+
+ std::unique_ptr<DataflowLattice> clone() override {
+ return std::make_unique<FunctionCallLattice>(*this);
+ }
+ bool isEqual(const DataflowLattice &Other) const override {
+ return *this == llvm::cast<const FunctionCallLattice>(Other);
+ }
};
std::ostream &operator<<(std::ostream &OS, const FunctionCallLattice &L) {
@@ -507,22 +535,27 @@ std::ostream &operator<<(std::ostream &OS, const
FunctionCallLattice &L) {
return OS << "{" << S << "}";
}
-class FunctionCallAnalysis
- : public DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice> {
+class FunctionCallAnalysis : public DataflowAnalysis {
public:
+ using Lattice = FunctionCallLattice;
+
explicit FunctionCallAnalysis(ASTContext &Context)
- : DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice>(Context) {}
+ : DataflowAnalysis(Context) {}
- static FunctionCallLattice initialElement() { return {}; }
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>();
+ }
- void transfer(const CFGElement &Elt, FunctionCallLattice &E, Environment &) {
+ void transfer(const CFGElement &Elt, DataflowLattice &L,
+ Environment &) override {
+ auto &FCL = llvm::cast<FunctionCallLattice>(L);
auto CS = Elt.getAs<CFGStmt>();
if (!CS)
return;
const auto *S = CS->getStmt();
if (auto *C = dyn_cast<CallExpr>(S)) {
if (auto *F = dyn_cast<FunctionDecl>(C->getCalleeDecl())) {
- E.CalledFunctions.insert(F->getNameInfo().getAsString());
+ FCL.CalledFunctions.insert(F->getNameInfo().getAsString());
}
}
}
@@ -696,10 +729,12 @@ TEST_F(NoreturnDestructorTest,
ConditionalOperatorNestedBranchReturns) {
// Models an analysis that uses flow conditions.
class SpecialBoolAnalysis final
- : public DataflowAnalysis<SpecialBoolAnalysis, NoopLattice> {
+ : public DataflowAnalysis {
public:
+ using Lattice = NoopLattice;
+
explicit SpecialBoolAnalysis(ASTContext &Context, Environment &Env)
- : DataflowAnalysis<SpecialBoolAnalysis, NoopLattice>(Context) {
+ : DataflowAnalysis(Context) {
Env.getDataflowAnalysisContext().setSyntheticFieldCallback(
[](QualType Ty) -> llvm::StringMap<QualType> {
RecordDecl *RD = Ty->getAsRecordDecl();
@@ -710,9 +745,12 @@ class SpecialBoolAnalysis final
});
}
- static NoopLattice initialElement() { return {}; }
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>();
+ }
- void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
+ void transfer(const CFGElement &Elt, DataflowLattice &,
+ Environment &Env) override {
auto CS = Elt.getAs<CFGStmt>();
if (!CS)
return;
@@ -807,15 +845,19 @@ TEST_F(JoinFlowConditionsTest,
JoinDistinctButProvablyEquivalentValues) {
});
}
-class NullPointerAnalysis final
- : public DataflowAnalysis<NullPointerAnalysis, NoopLattice> {
+class NullPointerAnalysis final : public DataflowAnalysis {
public:
+ using Lattice = NoopLattice;
+
explicit NullPointerAnalysis(ASTContext &Context)
- : DataflowAnalysis<NullPointerAnalysis, NoopLattice>(Context) {}
+ : DataflowAnalysis(Context) {}
- static NoopLattice initialElement() { return {}; }
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>();
+ }
- void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
+ void transfer(const CFGElement &Elt, DataflowLattice &,
+ Environment &Env) override {
auto CS = Elt.getAs<CFGStmt>();
if (!CS)
return;
@@ -1520,14 +1562,18 @@ TEST_F(FlowConditionTest, PointerToBoolImplicitCast) {
});
}
-class TopAnalysis final : public DataflowAnalysis<TopAnalysis, NoopLattice> {
+class TopAnalysis final : public DataflowAnalysis {
public:
- explicit TopAnalysis(ASTContext &Context)
- : DataflowAnalysis<TopAnalysis, NoopLattice>(Context) {}
+ using Lattice = NoopLattice;
- static NoopLattice initialElement() { return {}; }
+ explicit TopAnalysis(ASTContext &Context) : DataflowAnalysis(Context) {}
+
+ std::unique_ptr<DataflowLattice> initialElement() override {
+ return std::make_unique<Lattice>();
+ }
- void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
+ void transfer(const CFGElement &Elt, DataflowLattice &,
+ Environment &Env) override {
auto CS = Elt.getAs<CFGStmt>();
if (!CS)
return;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
