================
@@ -5,36 +5,114 @@
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
-#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
-#include "Dataflow.h"
+#include <cassert>
#include <memory>
+#include "Dataflow.h"
+#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"
+#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"
+#include "clang/Analysis/Analyses/LifetimeSafety/Loans.h"
+#include "clang/Analysis/Analyses/LifetimeSafety/Origins.h"
+#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/TimeProfiler.h"
+#include "llvm/Support/raw_ostream.h"
+
namespace clang::lifetimes::internal {
+
+// Prepass to find persistent origins. An origin is persistent if it is
+// referenced in more than one basic block.
+static llvm::BitVector computePersistentOrigins(const FactManager &FactMgr,
+ const CFG &C) {
+ llvm::TimeTraceScope("ComputePersistentOrigins");
+ unsigned NumOrigins = FactMgr.getOriginMgr().getNumOrigins();
+ llvm::BitVector PersistentOrigins(NumOrigins);
+
+ llvm::SmallVector<const CFGBlock *> OriginToFirstSeenBlock(NumOrigins,
+ nullptr);
+ for (const CFGBlock *B : C) {
+ for (const Fact *F : FactMgr.getFacts(B)) {
+ auto CheckOrigin = [&](OriginID OID) {
+ if (PersistentOrigins.test(OID.Value))
+ return;
+ auto &FirstSeenBlock = OriginToFirstSeenBlock[OID.Value];
+ if (FirstSeenBlock == nullptr)
+ FirstSeenBlock = B;
+ if (FirstSeenBlock != B) {
+ // We saw this origin in more than one block.
+ PersistentOrigins.set(OID.Value);
+ }
+ };
+
+ 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());
+ 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
/// point.The lattice has a finite height: An origin's loan set is bounded by
/// the total number of loans in the function.
-/// TODO(opt): To reduce the lattice size, propagate origins of declarations,
-/// 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);
-
- explicit Lattice(const OriginLoanMap &S) : Origins(S) {}
+ /// 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);
----------------
usx95 wrote:
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.
https://github.com/llvm/llvm-project/pull/165789
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
