[LifetimeSafety] Optimize loan propagation by separating persistent and block-local origins #165789
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Contributor
Author
This stack of pull requests is managed by Graphite. Learn more about stacking. |
usx95
changed the title
llvmbot
added
clang
Member
|
@llvm/pr-subscribers-clang-temporal-safety Author: Utkarsh Saxena (usx95) ChangesSummaryOptimizes the lifetime analysis loan propagation by preventing block-local origins from participating in expensive join operations at block boundaries. ProblemThe lifetime analysis currently performs join operations on all origins at every block boundary. However, many origins are block-local: they exist only to propagate loans between persistent origins across temporary declarations within a single block. Including them in joins is unnecessary and expensive. SolutionThis PR classifies origins into two categories:
Implementation
Benefits
Fixes #165780 Full diff: https://github.com/llvm/llvm-project/pull/165789.diff 2 Files Affected:
diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
index 387097e705f94..3ee48facfeb57 100644
--- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
+++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
@@ -7,10 +7,60 @@
//===----------------------------------------------------------------------===//
#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
#include "Dataflow.h"
+#include "llvm/Support/TimeProfiler.h"
#include <memory>
namespace clang::lifetimes::internal {
+
+// Pre-pass to find persistent origins. An origin is persistent if it is
+// referenced in more than one basic block.
+static llvm::DenseSet<OriginID> computePersistentOrigins(FactManager &FactMgr,
+ const CFG &C) {
+ llvm::TimeTraceScope("ComputePersistentOrigins");
+ llvm::DenseSet<OriginID> PersistentOrigins;
+
+ llvm::DenseMap<OriginID, const CFGBlock *> OriginToBlock;
+ for (const CFGBlock *B : C) {
+ for (const Fact *F : FactMgr.getFacts(B)) {
+ auto CheckOrigin = [&](OriginID OID) {
+ if (PersistentOrigins.count(OID))
+ return;
+ auto It = OriginToBlock.find(OID);
+ if (It == OriginToBlock.end()) {
+ OriginToBlock[OID] = B;
+ } else if (It->second != B) {
+ // We saw this origin in more than one block.
+ PersistentOrigins.insert(OID);
+ }
+ };
+
+ switch (F->getKind()) {
+ case Fact::Kind::Issue:
+ CheckOrigin(F->getAs<IssueFact>()->getOriginID());
+ break;
+ case Fact::Kind::OriginFlow: {
+ const auto *OF = F->getAs<OriginFlowFact>();
+ CheckOrigin(OF->getDestOriginID());
+ CheckOrigin(OF->getSrcOriginID());
+ break;
+ }
+ case Fact::Kind::ReturnOfOrigin:
+ CheckOrigin(F->getAs<ReturnOfOriginFact>()->getReturnedOriginID());
+ break;
+ case Fact::Kind::Use:
+ CheckOrigin(F->getAs<UseFact>()->getUsedOrigin(FactMgr.getOriginMgr()));
+ break;
+ case Fact::Kind::Expire:
+ case Fact::Kind::TestPoint:
+ break;
+ }
+ }
+ }
+ return PersistentOrigins;
+}
+
namespace {
+
/// Represents the dataflow lattice for loan propagation.
///
/// This lattice tracks which loans each origin may hold at a given program
@@ -20,21 +70,35 @@ namespace {
/// not expressions, because expressions are not visible across blocks.
struct Lattice {
/// The map from an origin to the set of loans it contains.
- OriginLoanMap Origins = OriginLoanMap(nullptr);
+ OriginLoanMap PersistentOrigins = OriginLoanMap(nullptr);
+ OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr);
- explicit Lattice(const OriginLoanMap &S) : Origins(S) {}
+ explicit Lattice(const OriginLoanMap &Persistent,
+ const OriginLoanMap &BlockLocal)
+ : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {}
Lattice() = default;
bool operator==(const Lattice &Other) const {
- return Origins == Other.Origins;
+ return PersistentOrigins == Other.PersistentOrigins &&
+ BlockLocalOrigins == Other.BlockLocalOrigins;
}
bool operator!=(const Lattice &Other) const { return !(*this == Other); }
void dump(llvm::raw_ostream &OS) const {
OS << "LoanPropagationLattice State:\n";
- if (Origins.isEmpty())
+ OS << " Persistent Origins:\n";
+ if (PersistentOrigins.isEmpty())
OS << " <empty>\n";
- for (const auto &Entry : Origins) {
+ for (const auto &Entry : PersistentOrigins) {
+ if (Entry.second.isEmpty())
+ OS << " Origin " << Entry.first << " contains no loans\n";
+ for (const LoanID &LID : Entry.second)
+ OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
+ }
+ OS << " Block-Local Origins:\n";
+ if (BlockLocalOrigins.isEmpty())
+ OS << " <empty>\n";
+ for (const auto &Entry : BlockLocalOrigins) {
if (Entry.second.isEmpty())
OS << " Origin " << Entry.first << " contains no loans\n";
for (const LoanID &LID : Entry.second)
@@ -50,7 +114,8 @@ class AnalysisImpl
OriginLoanMap::Factory &OriginLoanMapFactory,
LoanSet::Factory &LoanSetFactory)
: DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),
- LoanSetFactory(LoanSetFactory) {}
+ LoanSetFactory(LoanSetFactory),
+ PersistentOrigins(computePersistentOrigins(F, C)) {}
using Base::transfer;
@@ -59,10 +124,9 @@ class AnalysisImpl
Lattice getInitialState() { return Lattice{}; }
/// Merges two lattices by taking the union of loans for each origin.
- // TODO(opt): Keep the state small by removing origins which become dead.
Lattice join(Lattice A, Lattice B) {
OriginLoanMap JoinedOrigins = utils::join(
- A.Origins, B.Origins, OriginLoanMapFactory,
+ A.PersistentOrigins, B.PersistentOrigins, OriginLoanMapFactory,
[&](const LoanSet *S1, const LoanSet *S2) {
assert((S1 || S2) && "unexpectedly merging 2 empty sets");
if (!S1)
@@ -74,16 +138,15 @@ class AnalysisImpl
// Asymmetric join is a performance win. For origins present only on one
// branch, the loan set can be carried over as-is.
utils::JoinKind::Asymmetric);
- return Lattice(JoinedOrigins);
+ return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap());
}
/// A new loan is issued to the origin. Old loans are erased.
Lattice transfer(Lattice In, const IssueFact &F) {
OriginID OID = F.getOriginID();
LoanID LID = F.getLoanID();
- return Lattice(OriginLoanMapFactory.add(
- In.Origins, OID,
- LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID)));
+ LoanSet NewLoans = LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID);
+ return setLoans(In, OID, NewLoans);
}
/// A flow from source to destination. If `KillDest` is true, this replaces
@@ -98,7 +161,7 @@ class AnalysisImpl
LoanSet SrcLoans = getLoans(In, SrcOID);
LoanSet MergedLoans = utils::join(DestLoans, SrcLoans, LoanSetFactory);
- return Lattice(OriginLoanMapFactory.add(In.Origins, DestOID, MergedLoans));
+ return setLoans(In, DestOID, MergedLoans);
}
LoanSet getLoans(OriginID OID, ProgramPoint P) const {
@@ -106,14 +169,30 @@ class AnalysisImpl
}
private:
+ bool isPersistent(OriginID OID) const {
+ return PersistentOrigins.contains(OID);
+ }
+
+ Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {
+ if (isPersistent(OID)) {
+ return Lattice(OriginLoanMapFactory.add(L.PersistentOrigins, OID, Loans),
+ L.BlockLocalOrigins);
+ }
+ return Lattice(L.PersistentOrigins,
+ OriginLoanMapFactory.add(L.BlockLocalOrigins, OID, Loans));
+ }
+
LoanSet getLoans(Lattice L, OriginID OID) const {
- if (auto *Loans = L.Origins.lookup(OID))
+ const OriginLoanMap *Map =
+ isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins;
+ if (auto *Loans = Map->lookup(OID))
return *Loans;
return LoanSetFactory.getEmptySet();
}
OriginLoanMap::Factory &OriginLoanMapFactory;
LoanSet::Factory &LoanSetFactory;
+ llvm::DenseSet<OriginID> PersistentOrigins;
};
} // namespace
diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
index 0c051847f4d47..40205b9a8fd19 100644
--- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
+++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
@@ -543,7 +543,6 @@ TEST_F(LifetimeAnalysisTest, PointersInACycle) {
EXPECT_THAT(Origin("p1"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
EXPECT_THAT(Origin("p2"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
EXPECT_THAT(Origin("p3"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
- EXPECT_THAT(Origin("temp"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
}
TEST_F(LifetimeAnalysisTest, PointersAndExpirationInACycle) {
|
Member
|
@llvm/pr-subscribers-clang-analysis Author: Utkarsh Saxena (usx95) ChangesSummaryOptimizes the lifetime analysis loan propagation by preventing block-local origins from participating in expensive join operations at block boundaries. ProblemThe lifetime analysis currently performs join operations on all origins at every block boundary. However, many origins are block-local: they exist only to propagate loans between persistent origins across temporary declarations within a single block. Including them in joins is unnecessary and expensive. SolutionThis PR classifies origins into two categories:
Implementation
Benefits
Fixes #165780 Full diff: https://github.com/llvm/llvm-project/pull/165789.diff 2 Files Affected:
diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
index 387097e705f94..3ee48facfeb57 100644
--- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
+++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
@@ -7,10 +7,60 @@
//===----------------------------------------------------------------------===//
#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
#include "Dataflow.h"
+#include "llvm/Support/TimeProfiler.h"
#include <memory>
namespace clang::lifetimes::internal {
+
+// Pre-pass to find persistent origins. An origin is persistent if it is
+// referenced in more than one basic block.
+static llvm::DenseSet<OriginID> computePersistentOrigins(FactManager &FactMgr,
+ const CFG &C) {
+ llvm::TimeTraceScope("ComputePersistentOrigins");
+ llvm::DenseSet<OriginID> PersistentOrigins;
+
+ llvm::DenseMap<OriginID, const CFGBlock *> OriginToBlock;
+ for (const CFGBlock *B : C) {
+ for (const Fact *F : FactMgr.getFacts(B)) {
+ auto CheckOrigin = [&](OriginID OID) {
+ if (PersistentOrigins.count(OID))
+ return;
+ auto It = OriginToBlock.find(OID);
+ if (It == OriginToBlock.end()) {
+ OriginToBlock[OID] = B;
+ } else if (It->second != B) {
+ // We saw this origin in more than one block.
+ PersistentOrigins.insert(OID);
+ }
+ };
+
+ switch (F->getKind()) {
+ case Fact::Kind::Issue:
+ CheckOrigin(F->getAs<IssueFact>()->getOriginID());
+ break;
+ case Fact::Kind::OriginFlow: {
+ const auto *OF = F->getAs<OriginFlowFact>();
+ CheckOrigin(OF->getDestOriginID());
+ CheckOrigin(OF->getSrcOriginID());
+ break;
+ }
+ case Fact::Kind::ReturnOfOrigin:
+ CheckOrigin(F->getAs<ReturnOfOriginFact>()->getReturnedOriginID());
+ break;
+ case Fact::Kind::Use:
+ CheckOrigin(F->getAs<UseFact>()->getUsedOrigin(FactMgr.getOriginMgr()));
+ break;
+ case Fact::Kind::Expire:
+ case Fact::Kind::TestPoint:
+ break;
+ }
+ }
+ }
+ return PersistentOrigins;
+}
+
namespace {
+
/// Represents the dataflow lattice for loan propagation.
///
/// This lattice tracks which loans each origin may hold at a given program
@@ -20,21 +70,35 @@ namespace {
/// not expressions, because expressions are not visible across blocks.
struct Lattice {
/// The map from an origin to the set of loans it contains.
- OriginLoanMap Origins = OriginLoanMap(nullptr);
+ OriginLoanMap PersistentOrigins = OriginLoanMap(nullptr);
+ OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr);
- explicit Lattice(const OriginLoanMap &S) : Origins(S) {}
+ explicit Lattice(const OriginLoanMap &Persistent,
+ const OriginLoanMap &BlockLocal)
+ : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {}
Lattice() = default;
bool operator==(const Lattice &Other) const {
- return Origins == Other.Origins;
+ return PersistentOrigins == Other.PersistentOrigins &&
+ BlockLocalOrigins == Other.BlockLocalOrigins;
}
bool operator!=(const Lattice &Other) const { return !(*this == Other); }
void dump(llvm::raw_ostream &OS) const {
OS << "LoanPropagationLattice State:\n";
- if (Origins.isEmpty())
+ OS << " Persistent Origins:\n";
+ if (PersistentOrigins.isEmpty())
OS << " <empty>\n";
- for (const auto &Entry : Origins) {
+ for (const auto &Entry : PersistentOrigins) {
+ if (Entry.second.isEmpty())
+ OS << " Origin " << Entry.first << " contains no loans\n";
+ for (const LoanID &LID : Entry.second)
+ OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
+ }
+ OS << " Block-Local Origins:\n";
+ if (BlockLocalOrigins.isEmpty())
+ OS << " <empty>\n";
+ for (const auto &Entry : BlockLocalOrigins) {
if (Entry.second.isEmpty())
OS << " Origin " << Entry.first << " contains no loans\n";
for (const LoanID &LID : Entry.second)
@@ -50,7 +114,8 @@ class AnalysisImpl
OriginLoanMap::Factory &OriginLoanMapFactory,
LoanSet::Factory &LoanSetFactory)
: DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),
- LoanSetFactory(LoanSetFactory) {}
+ LoanSetFactory(LoanSetFactory),
+ PersistentOrigins(computePersistentOrigins(F, C)) {}
using Base::transfer;
@@ -59,10 +124,9 @@ class AnalysisImpl
Lattice getInitialState() { return Lattice{}; }
/// Merges two lattices by taking the union of loans for each origin.
- // TODO(opt): Keep the state small by removing origins which become dead.
Lattice join(Lattice A, Lattice B) {
OriginLoanMap JoinedOrigins = utils::join(
- A.Origins, B.Origins, OriginLoanMapFactory,
+ A.PersistentOrigins, B.PersistentOrigins, OriginLoanMapFactory,
[&](const LoanSet *S1, const LoanSet *S2) {
assert((S1 || S2) && "unexpectedly merging 2 empty sets");
if (!S1)
@@ -74,16 +138,15 @@ class AnalysisImpl
// Asymmetric join is a performance win. For origins present only on one
// branch, the loan set can be carried over as-is.
utils::JoinKind::Asymmetric);
- return Lattice(JoinedOrigins);
+ return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap());
}
/// A new loan is issued to the origin. Old loans are erased.
Lattice transfer(Lattice In, const IssueFact &F) {
OriginID OID = F.getOriginID();
LoanID LID = F.getLoanID();
- return Lattice(OriginLoanMapFactory.add(
- In.Origins, OID,
- LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID)));
+ LoanSet NewLoans = LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID);
+ return setLoans(In, OID, NewLoans);
}
/// A flow from source to destination. If `KillDest` is true, this replaces
@@ -98,7 +161,7 @@ class AnalysisImpl
LoanSet SrcLoans = getLoans(In, SrcOID);
LoanSet MergedLoans = utils::join(DestLoans, SrcLoans, LoanSetFactory);
- return Lattice(OriginLoanMapFactory.add(In.Origins, DestOID, MergedLoans));
+ return setLoans(In, DestOID, MergedLoans);
}
LoanSet getLoans(OriginID OID, ProgramPoint P) const {
@@ -106,14 +169,30 @@ class AnalysisImpl
}
private:
+ bool isPersistent(OriginID OID) const {
+ return PersistentOrigins.contains(OID);
+ }
+
+ Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {
+ if (isPersistent(OID)) {
+ return Lattice(OriginLoanMapFactory.add(L.PersistentOrigins, OID, Loans),
+ L.BlockLocalOrigins);
+ }
+ return Lattice(L.PersistentOrigins,
+ OriginLoanMapFactory.add(L.BlockLocalOrigins, OID, Loans));
+ }
+
LoanSet getLoans(Lattice L, OriginID OID) const {
- if (auto *Loans = L.Origins.lookup(OID))
+ const OriginLoanMap *Map =
+ isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins;
+ if (auto *Loans = Map->lookup(OID))
return *Loans;
return LoanSetFactory.getEmptySet();
}
OriginLoanMap::Factory &OriginLoanMapFactory;
LoanSet::Factory &LoanSetFactory;
+ llvm::DenseSet<OriginID> PersistentOrigins;
};
} // namespace
diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
index 0c051847f4d47..40205b9a8fd19 100644
--- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
+++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
@@ -543,7 +543,6 @@ TEST_F(LifetimeAnalysisTest, PointersInACycle) {
EXPECT_THAT(Origin("p1"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
EXPECT_THAT(Origin("p2"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
EXPECT_THAT(Origin("p3"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
- EXPECT_THAT(Origin("temp"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
}
TEST_F(LifetimeAnalysisTest, PointersAndExpirationInACycle) {
|
Member
|
@llvm/pr-subscribers-clang Author: Utkarsh Saxena (usx95) ChangesSummaryOptimizes the lifetime analysis loan propagation by preventing block-local origins from participating in expensive join operations at block boundaries. ProblemThe lifetime analysis currently performs join operations on all origins at every block boundary. However, many origins are block-local: they exist only to propagate loans between persistent origins across temporary declarations within a single block. Including them in joins is unnecessary and expensive. SolutionThis PR classifies origins into two categories:
Implementation
Benefits
Fixes #165780 Full diff: https://github.com/llvm/llvm-project/pull/165789.diff 2 Files Affected:
diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
index 387097e705f94..3ee48facfeb57 100644
--- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
+++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp
@@ -7,10 +7,60 @@
//===----------------------------------------------------------------------===//
#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
#include "Dataflow.h"
+#include "llvm/Support/TimeProfiler.h"
#include <memory>
namespace clang::lifetimes::internal {
+
+// Pre-pass to find persistent origins. An origin is persistent if it is
+// referenced in more than one basic block.
+static llvm::DenseSet<OriginID> computePersistentOrigins(FactManager &FactMgr,
+ const CFG &C) {
+ llvm::TimeTraceScope("ComputePersistentOrigins");
+ llvm::DenseSet<OriginID> PersistentOrigins;
+
+ llvm::DenseMap<OriginID, const CFGBlock *> OriginToBlock;
+ for (const CFGBlock *B : C) {
+ for (const Fact *F : FactMgr.getFacts(B)) {
+ auto CheckOrigin = [&](OriginID OID) {
+ if (PersistentOrigins.count(OID))
+ return;
+ auto It = OriginToBlock.find(OID);
+ if (It == OriginToBlock.end()) {
+ OriginToBlock[OID] = B;
+ } else if (It->second != B) {
+ // We saw this origin in more than one block.
+ PersistentOrigins.insert(OID);
+ }
+ };
+
+ switch (F->getKind()) {
+ case Fact::Kind::Issue:
+ CheckOrigin(F->getAs<IssueFact>()->getOriginID());
+ break;
+ case Fact::Kind::OriginFlow: {
+ const auto *OF = F->getAs<OriginFlowFact>();
+ CheckOrigin(OF->getDestOriginID());
+ CheckOrigin(OF->getSrcOriginID());
+ break;
+ }
+ case Fact::Kind::ReturnOfOrigin:
+ CheckOrigin(F->getAs<ReturnOfOriginFact>()->getReturnedOriginID());
+ break;
+ case Fact::Kind::Use:
+ CheckOrigin(F->getAs<UseFact>()->getUsedOrigin(FactMgr.getOriginMgr()));
+ break;
+ case Fact::Kind::Expire:
+ case Fact::Kind::TestPoint:
+ break;
+ }
+ }
+ }
+ return PersistentOrigins;
+}
+
namespace {
+
/// Represents the dataflow lattice for loan propagation.
///
/// This lattice tracks which loans each origin may hold at a given program
@@ -20,21 +70,35 @@ namespace {
/// not expressions, because expressions are not visible across blocks.
struct Lattice {
/// The map from an origin to the set of loans it contains.
- OriginLoanMap Origins = OriginLoanMap(nullptr);
+ OriginLoanMap PersistentOrigins = OriginLoanMap(nullptr);
+ OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr);
- explicit Lattice(const OriginLoanMap &S) : Origins(S) {}
+ explicit Lattice(const OriginLoanMap &Persistent,
+ const OriginLoanMap &BlockLocal)
+ : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {}
Lattice() = default;
bool operator==(const Lattice &Other) const {
- return Origins == Other.Origins;
+ return PersistentOrigins == Other.PersistentOrigins &&
+ BlockLocalOrigins == Other.BlockLocalOrigins;
}
bool operator!=(const Lattice &Other) const { return !(*this == Other); }
void dump(llvm::raw_ostream &OS) const {
OS << "LoanPropagationLattice State:\n";
- if (Origins.isEmpty())
+ OS << " Persistent Origins:\n";
+ if (PersistentOrigins.isEmpty())
OS << " <empty>\n";
- for (const auto &Entry : Origins) {
+ for (const auto &Entry : PersistentOrigins) {
+ if (Entry.second.isEmpty())
+ OS << " Origin " << Entry.first << " contains no loans\n";
+ for (const LoanID &LID : Entry.second)
+ OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";
+ }
+ OS << " Block-Local Origins:\n";
+ if (BlockLocalOrigins.isEmpty())
+ OS << " <empty>\n";
+ for (const auto &Entry : BlockLocalOrigins) {
if (Entry.second.isEmpty())
OS << " Origin " << Entry.first << " contains no loans\n";
for (const LoanID &LID : Entry.second)
@@ -50,7 +114,8 @@ class AnalysisImpl
OriginLoanMap::Factory &OriginLoanMapFactory,
LoanSet::Factory &LoanSetFactory)
: DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),
- LoanSetFactory(LoanSetFactory) {}
+ LoanSetFactory(LoanSetFactory),
+ PersistentOrigins(computePersistentOrigins(F, C)) {}
using Base::transfer;
@@ -59,10 +124,9 @@ class AnalysisImpl
Lattice getInitialState() { return Lattice{}; }
/// Merges two lattices by taking the union of loans for each origin.
- // TODO(opt): Keep the state small by removing origins which become dead.
Lattice join(Lattice A, Lattice B) {
OriginLoanMap JoinedOrigins = utils::join(
- A.Origins, B.Origins, OriginLoanMapFactory,
+ A.PersistentOrigins, B.PersistentOrigins, OriginLoanMapFactory,
[&](const LoanSet *S1, const LoanSet *S2) {
assert((S1 || S2) && "unexpectedly merging 2 empty sets");
if (!S1)
@@ -74,16 +138,15 @@ class AnalysisImpl
// Asymmetric join is a performance win. For origins present only on one
// branch, the loan set can be carried over as-is.
utils::JoinKind::Asymmetric);
- return Lattice(JoinedOrigins);
+ return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap());
}
/// A new loan is issued to the origin. Old loans are erased.
Lattice transfer(Lattice In, const IssueFact &F) {
OriginID OID = F.getOriginID();
LoanID LID = F.getLoanID();
- return Lattice(OriginLoanMapFactory.add(
- In.Origins, OID,
- LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID)));
+ LoanSet NewLoans = LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID);
+ return setLoans(In, OID, NewLoans);
}
/// A flow from source to destination. If `KillDest` is true, this replaces
@@ -98,7 +161,7 @@ class AnalysisImpl
LoanSet SrcLoans = getLoans(In, SrcOID);
LoanSet MergedLoans = utils::join(DestLoans, SrcLoans, LoanSetFactory);
- return Lattice(OriginLoanMapFactory.add(In.Origins, DestOID, MergedLoans));
+ return setLoans(In, DestOID, MergedLoans);
}
LoanSet getLoans(OriginID OID, ProgramPoint P) const {
@@ -106,14 +169,30 @@ class AnalysisImpl
}
private:
+ bool isPersistent(OriginID OID) const {
+ return PersistentOrigins.contains(OID);
+ }
+
+ Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {
+ if (isPersistent(OID)) {
+ return Lattice(OriginLoanMapFactory.add(L.PersistentOrigins, OID, Loans),
+ L.BlockLocalOrigins);
+ }
+ return Lattice(L.PersistentOrigins,
+ OriginLoanMapFactory.add(L.BlockLocalOrigins, OID, Loans));
+ }
+
LoanSet getLoans(Lattice L, OriginID OID) const {
- if (auto *Loans = L.Origins.lookup(OID))
+ const OriginLoanMap *Map =
+ isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins;
+ if (auto *Loans = Map->lookup(OID))
return *Loans;
return LoanSetFactory.getEmptySet();
}
OriginLoanMap::Factory &OriginLoanMapFactory;
LoanSet::Factory &LoanSetFactory;
+ llvm::DenseSet<OriginID> PersistentOrigins;
};
} // namespace
diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
index 0c051847f4d47..40205b9a8fd19 100644
--- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
+++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
@@ -543,7 +543,6 @@ TEST_F(LifetimeAnalysisTest, PointersInACycle) {
EXPECT_THAT(Origin("p1"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
EXPECT_THAT(Origin("p2"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
EXPECT_THAT(Origin("p3"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
- EXPECT_THAT(Origin("temp"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
}
TEST_F(LifetimeAnalysisTest, PointersAndExpirationInACycle) {
|
usx95
force-pushed
the
users/usx95/10-30-persistent-origin-optimisation
branch
from
e18f21c to
8e7fde9
Compare
usx95
force-pushed
the
users/usx95/10-30-persistent-origin-optimisation
branch
from
8e7fde9 to
11055e3
Compare
Xazax-hun
reviewed
Oct 31, 2025
Xazax-hun
reviewed
Oct 31, 2025
usx95
force-pushed
the
users/usx95/10-30-persistent-origin-optimisation
branch
from
a0f216f to
3db9f2d
Compare
usx95
added a commit
to usx95/llvm-project
that referenced
this pull request
Oct 31, 2025
Xazax-hun
approved these changes
Oct 31, 2025
Collaborator
Xazax-hun
left a comment
Xazax-hun
left a comment
There was a problem hiding this comment.
This looks great, thanks!
usx95
force-pushed
the
users/usx95/10-30-persistent-origin-optimisation
branch
from
3db9f2d to
33c0c70
Compare
usx95
added a commit
to usx95/llvm-project
that referenced
this pull request
Nov 1, 2025
mrcvtl
reviewed
Nov 4, 2025
mrcvtl
reviewed
Nov 4, 2025
Contributor
mrcvtl
left a comment
mrcvtl
left a comment
There was a problem hiding this comment.
Really nice! I left a comment while I was taking a look at the changes.
usx95
force-pushed
the
users/usx95/10-30-persistent-origin-optimisation
branch
from
33c0c70 to
0bbc422
Compare
usx95
changed the title
ymand
approved these changes
Nov 5, 2025
Collaborator
ymand
left a comment
ymand
left a comment
There was a problem hiding this comment.
asked about 2 possible changes, but fine going in as is. Thanks!
| auto CheckOrigin = [&](OriginID OID) { | ||
| if (PersistentOrigins.test(OID.Value)) | ||
| return; | ||
| auto &FirstSeenBlock = OriginToFirstSeenBlock[OID.Value]; |
Collaborator
There was a problem hiding this comment.
nit: could you instead just count the occurences of each origin and then, after visiting all blocks in C, any origin with count > 1 are persistent?
Contributor
Author
There was a problem hiding this comment.
Not really. The origin flow facts would be of the form: $1 = $2, $2 = $3, ... and $2 is still a block-local origin.
| /// Origins that appear in multiple blocks. Participates in join operations. | ||
| OriginLoanMap PersistentOrigins = OriginLoanMap(nullptr); | ||
| /// Origins confined to a single block. Discarded at block boundaries. | ||
| OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr); |
Collaborator
There was a problem hiding this comment.
Have you considered, instead of this eager tracking of persistant and local separately, just clearing all local originals from the single map before the join? Then, the logic/complexity is limited to that one site.
Collaborator
There was a problem hiding this comment.
In case this change is made let's redo the benchmarks. Not sure how efficient removing items is from our persistent maps.
Contributor
Author
There was a problem hiding this comment.
Yes it is possible to do so. There are some benefits of doing so: we can delete more than just block-local origins, we can delete all origins which are dead (using the liveness analysis).
But I would prefer not to do "deletions" though as they are both expensive (logarithmic) + create a lot of holes in the buffer backing the trees and make it quite sparse (the number of deleted origins would be much higher than the persistent origins).
So I feel the current approach is both simple and efficient in time and memory layout.
Contributor
Author
usx95
force-pushed
the
users/usx95/10-30-persistent-origin-optimisation
branch
from
0bbc422 to
667242a
Compare
github-project-automation
bot
moved this from In Progress
to Done
in Lifetime Safety in Clang
usx95
added a commit
that referenced
this pull request
Nov 7, 2025
Fixes test failure introduced by a typo in #165789
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/144/builds/39567 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/190/builds/30485 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/27/builds/18592 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/3/builds/24519 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/10/builds/16861 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/65/builds/25139 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/46/builds/25977 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/140/builds/33678 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/154/builds/23718 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/174/builds/27108 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/11/builds/27534 Here is the relevant piece of the build log for the reference |
llvm-sync bot
pushed a commit
to arm/arm-toolchain
that referenced
this pull request
Nov 7, 2025
Fixes test failure introduced by a typo in llvm/llvm-project#165789
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/55/builds/19715 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/85/builds/15388 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/164/builds/15348 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/87/builds/4026 Here is the relevant piece of the build log for the reference |
Collaborator
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/132/builds/3341 Here is the relevant piece of the build log for the reference |
vinay-deshmukh
pushed a commit
to vinay-deshmukh/llvm-project
that referenced
this pull request
Nov 8, 2025
…nd block-local origins (llvm#165789) ## Summary Optimizes the lifetime analysis loan propagation by preventing block-local origins from participating in expensive join operations at block boundaries. ## Problem The lifetime analysis currently performs join operations on all origins at every block boundary. However, many origins are block-local: they exist only to propagate loans between persistent origins across temporary declarations and expressions within a single block. Including them in joins is unnecessary and expensive. ## Solution This PR classifies origins into two categories: - **Persistent origins**: referenced in multiple basic blocks, must participate in joins - **Block-local origins**: confined to a single block, can be discarded at block boundaries ### Implementation 1. **Pre-pass** (`computePersistentOrigins`): Analyzes all facts in the CFG to identify which origins appear in multiple blocks 2. **Split lattice**: Maintains two separate `OriginLoanMap`s: - `PersistentOrigins`: participates in join operations - `BlockLocalOrigins`: used during block execution, discarded at boundaries 3. **Optimized join**: Only merges persistent origins; block-local map is reset to empty ### Benefits - Significantly reduces join complexity, especially in functions with many temporary locals - Performance scales with the ratio of temporary to persistent origins - Correctness preserved: block-local loan propagation still works within blocks Fixes: llvm#165780 Fixes: llvm#164625. It brings down regression from **150% to 2%**. ---
vinay-deshmukh
pushed a commit
to vinay-deshmukh/llvm-project
that referenced
this pull request
Nov 8, 2025
Fixes test failure introduced by a typo in llvm#165789
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Summary
Optimizes the lifetime analysis loan propagation by preventing block-local origins from participating in expensive join operations at block boundaries.
Problem
The lifetime analysis currently performs join operations on all origins at every block boundary. However, many origins are block-local: they exist only to propagate loans between persistent origins across temporary declarations and expressions within a single block. Including them in joins is unnecessary and expensive.
Solution
This PR classifies origins into two categories:
Implementation
computePersistentOrigins): Analyzes all facts in the CFG to identify which origins appear in multiple blocksOriginLoanMaps:PersistentOrigins: participates in join operationsBlockLocalOrigins: used during block execution, discarded at boundariesBenefits
Fixes: #165780
Fixes: #164625. It brings down regression from 150% to 2%.