li.zhe.hua updated this revision to Diff 451887.
li.zhe.hua marked an inline comment as done.
li.zhe.hua added a comment.
Add FIXME
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D131645/new/
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,15 @@
/// 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.
+///
+/// FIXME: Provide concrete guidance on how to write a good widen function,
+/// which can be tricky.
template <typename Derived, typename LatticeT>
class DataflowAnalysis : public TypeErasedDataflowAnalysis {
public:
@@ -85,6 +94,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 +115,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
