li.zhe.hua created this revision.
Herald added subscribers: martong, xazax.hun.
Herald added a reviewer: NoQ.
Herald added a project: All.
li.zhe.hua requested review of this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
In order to better support convergence in a sound way, we allow users
to provide a widen operator for their lattice type. This can be
implemented for lattices of infinite (or sufficiently large) height in
order to reach convergence in loops.
If not provided, this defaults to the existing `join` operation that
is required to be defined. This is a sound default, as `join` would be
at least more precise than a theoretical `widen`.
Tracking bug: #56931
Depends on D131644 <https://reviews.llvm.org/D131644>
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D131645
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -48,6 +48,7 @@
using ::testing::IsNull;
using ::testing::NotNull;
using ::testing::Pair;
+using ::testing::Ref;
using ::testing::Test;
using ::testing::UnorderedElementsAre;
@@ -86,6 +87,99 @@
EXPECT_TRUE(BlockStates[1].has_value());
}
+struct HasWidenLattice {
+ HasWidenLattice() {
+ ON_CALL(*this, join).WillByDefault([](const HasWidenLattice &) {
+ return LatticeJoinEffect::Unchanged;
+ });
+ }
+ // Mock objects are not copyable by default. Since this is a monostate,
+ // delegate to the default ctor.
+ HasWidenLattice(const HasWidenLattice &) : HasWidenLattice() {}
+ HasWidenLattice &operator=(const HasWidenLattice &) { return *this; }
+
+ MOCK_METHOD(LatticeJoinEffect, join, (const HasWidenLattice &));
+ MOCK_METHOD(void, widen, (const HasWidenLattice &));
+
+ friend bool operator==(const HasWidenLattice &, const HasWidenLattice &) {
+ return true;
+ }
+};
+
+class HasWidenAnalysis
+ : public DataflowAnalysis<HasWidenAnalysis, HasWidenLattice> {
+public:
+ static HasWidenLattice initialElement() { return {}; }
+ using DataflowAnalysis::DataflowAnalysis;
+ void transfer(const Stmt *, HasWidenLattice &, Environment &) {}
+};
+
+TEST(DataflowAnalysisTest, WidenPrefersWidenWhenProvided) {
+ std::unique_ptr<ASTUnit> AST =
+ tooling::buildASTFromCodeWithArgs("int x = 0;", {"-std=c++11"});
+ HasWidenAnalysis Analysis(AST->getASTContext(),
+ /*ApplyBuiltinTransfer=*/false);
+
+ TypeErasedLattice A = {HasWidenLattice()};
+ TypeErasedLattice B = {HasWidenLattice()};
+ HasWidenLattice &LA = *llvm::any_cast<HasWidenLattice>(&A.Value);
+ HasWidenLattice &LB = *llvm::any_cast<HasWidenLattice>(&B.Value);
+
+ // Expect only `LA.widen(LB)` is called, and nothing else.
+ EXPECT_CALL(LA, widen).Times(0);
+ EXPECT_CALL(LB, widen).Times(0);
+ EXPECT_CALL(LA, join).Times(0);
+ EXPECT_CALL(LB, join).Times(0);
+ EXPECT_CALL(LA, widen(Ref(LB))).Times(1);
+
+ Analysis.widenTypeErased(A, B);
+}
+
+struct OnlyJoinLattice {
+ OnlyJoinLattice() {
+ ON_CALL(*this, join).WillByDefault([](const OnlyJoinLattice &) {
+ return LatticeJoinEffect::Unchanged;
+ });
+ }
+ // Mock objects are not copyable by default. Since this is a monostate,
+ // delegate to the default ctor.
+ OnlyJoinLattice(const OnlyJoinLattice &) : OnlyJoinLattice() {}
+ OnlyJoinLattice &operator=(const OnlyJoinLattice &) { return *this; }
+
+ MOCK_METHOD(LatticeJoinEffect, join, (const OnlyJoinLattice &));
+
+ friend bool operator==(const OnlyJoinLattice &, const OnlyJoinLattice &) {
+ return true;
+ }
+};
+
+class OnlyJoinAnalysis
+ : public DataflowAnalysis<OnlyJoinAnalysis, OnlyJoinLattice> {
+public:
+ static OnlyJoinLattice initialElement() { return {}; }
+ using DataflowAnalysis::DataflowAnalysis;
+ void transfer(const Stmt *, OnlyJoinLattice &, Environment &) {}
+};
+
+TEST(DataflowAnalysisTest, WidenFallsBackToJoin) {
+ std::unique_ptr<ASTUnit> AST =
+ tooling::buildASTFromCodeWithArgs("int x = 0;", {"-std=c++11"});
+ OnlyJoinAnalysis Analysis(AST->getASTContext(),
+ /*ApplyBuiltinTransfer=*/false);
+
+ TypeErasedLattice A = {OnlyJoinLattice()};
+ TypeErasedLattice B = {OnlyJoinLattice()};
+ OnlyJoinLattice &LA = *llvm::any_cast<OnlyJoinLattice>(&A.Value);
+ OnlyJoinLattice &LB = *llvm::any_cast<OnlyJoinLattice>(&B.Value);
+
+ // Expect only `LA.join(LB)` is called, and nothing else.
+ EXPECT_CALL(LA, join).Times(0);
+ EXPECT_CALL(LB, join).Times(0);
+ EXPECT_CALL(LA, join(Ref(LB))).Times(1);
+
+ Analysis.widenTypeErased(A, B);
+}
+
struct NonConvergingLattice {
int State;
Index: clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
+++ clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
@@ -77,6 +77,10 @@
virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &,
const TypeErasedLattice &) = 0;
+ /// Relaxes the constraints in `A` to subsume the state in `B`.
+ virtual void widenTypeErased(TypeErasedLattice &A,
+ const TypeErasedLattice &B) = 0;
+
/// Returns true if and only if the two given type-erased lattice elements are
/// equal.
virtual bool isEqualTypeErased(const TypeErasedLattice &,
Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
@@ -55,6 +55,12 @@
/// made to it;
/// * `bool operator==(const LatticeT &) const` - returns true if and only if
/// the object is equal to the argument.
+///
+/// `LatticeT` may also optionally provide the following members:
+/// * `void widen(const LatticeT &)` - relaxes the object to subsume the
+/// argument, computing an upper bound. Widen is called during loops, where
+/// a join operation may prevent convergence for a lattice of infinite
+/// height. If `widen` is not provided, `join` is used by default.
template <typename Derived, typename LatticeT>
class DataflowAnalysis : public TypeErasedDataflowAnalysis {
public:
@@ -85,6 +91,13 @@
return L1.join(L2);
}
+ void widenTypeErased(TypeErasedLattice &E1,
+ const TypeErasedLattice &E2) final {
+ Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
+ const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
+ widenInternal(Rank0{}, L1, L2);
+ }
+
bool isEqualTypeErased(const TypeErasedLattice &E1,
const TypeErasedLattice &E2) final {
const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
@@ -99,6 +112,27 @@
}
private:
+ struct Rank1 {};
+ struct Rank0 : Rank1 {};
+
+ // We first try to use the widen operator if the lattice defines it, and fall
+ // back to using join if not.
+ //
+ // Widen (relative to join) trades precision for convergence in loops. A
+ // lattice with a reasonable, finite height may prefer to continue using the
+ // join operation.
+ template <typename T>
+ static auto widenInternal(Rank0, T &L1, const T &L2)
+ -> llvm::detail::void_t<decltype(L1.widen(L2))> {
+ L1.widen(L2);
+ }
+
+ template <typename T>
+ static auto widenInternal(Rank1, T &L1, const T &L2)
+ -> llvm::detail::void_t<decltype(L1.join(L2))> {
+ L1.join(L2);
+ }
+
ASTContext &Context;
};
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
