https://github.com/usx95 created https://github.com/llvm/llvm-project/pull/211225
None >From 4598148afbeda2a02a1a01b16cecd77385973405 Mon Sep 17 00:00:00 2001 From: Utkarsh Saxena <[email protected]> Date: Wed, 22 Jul 2026 08:53:48 +0000 Subject: [PATCH] multiple-compile-time-improv --- .../Analysis/Analyses/LifetimeSafety/Facts.h | 18 ++ .../Analyses/LifetimeSafety/LiveOrigins.h | 2 +- .../Analyses/LifetimeSafety/LoanPropagation.h | 5 +- .../Analyses/LifetimeSafety/MovedLoans.h | 2 +- .../Analysis/Analyses/LifetimeSafety/Utils.h | 48 +++-- clang/lib/Analysis/LifetimeSafety/Checker.cpp | 194 +++++++++++++----- clang/lib/Analysis/LifetimeSafety/Dataflow.h | 100 ++++++--- clang/lib/Analysis/LifetimeSafety/Facts.cpp | 6 +- .../Analysis/LifetimeSafety/LiveOrigins.cpp | 71 ++++--- .../LifetimeSafety/LoanPropagation.cpp | 113 +++++++--- .../Analysis/LifetimeSafety/MovedLoans.cpp | 46 +++-- .../unittests/Analysis/LifetimeSafetyTest.cpp | 10 +- llvm/include/llvm/ADT/ImmutableSet.h | 11 +- 13 files changed, 448 insertions(+), 178 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h index 94db2a7f311ae..6c3b7ceaca8ba 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h @@ -366,6 +366,22 @@ class FactManager { void *Mem = FactAllocator.Allocate<FactType>(); FactType *Res = new (Mem) FactType(std::forward<Args>(args)...); Res->setID(NextFactID++); + + if constexpr (std::is_same_v<FactType, OriginEscapesFact> || + std::is_same_v<FactType, ReturnEscapeFact> || + std::is_same_v<FactType, GlobalEscapeFact> || + std::is_same_v<FactType, FieldEscapeFact> || + std::is_same_v<FactType, InvalidateOriginFact> || + std::is_same_v<FactType, TestPointFact>) { + NeedsDataflow = true; + } else if constexpr (std::is_same_v<FactType, IssueFact>) { + const Loan *L = getLoanMgr().getLoan(Res->getLoanID()); + if (L && !L->getAccessPath().getAsPlaceholderThis() && + !L->getAccessPath().getAsPlaceholderParam()) { + NeedsDataflow = true; + } + } + return Res; } @@ -387,6 +403,8 @@ class FactManager { llvm::ArrayRef<const Fact *> getBlockContaining(ProgramPoint P) const; size_t getBlockID(ProgramPoint P) const; + bool NeedsDataflow = false; + unsigned getNumFacts() const { return NextFactID.Value; } LoanManager &getLoanMgr() { return LoanMgr; } diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h index 8f998fa83fbf5..7a60676898b55 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h @@ -83,7 +83,7 @@ class LiveOriginsAnalysis { /// Returns the set of origins that are live at a specific program point, /// along with the the details of the liveness. - LivenessMap getLiveOriginsAt(ProgramPoint P) const; + const LivenessMap &getLiveOriginsAt(ProgramPoint P) const; // Dump liveness values on all test points in the program. void dump(llvm::raw_ostream &OS, diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h index e13442facd82d..74ed131cf8ec7 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h @@ -35,7 +35,10 @@ class LoanPropagationAnalysis { LoanSet::Factory &LoanSetFactory); ~LoanPropagationAnalysis(); - LoanSet getLoans(OriginID OID, ProgramPoint P) const; + const LoanSet *getLoans(OriginID OID, ProgramPoint P) const; + + using LoanMatchCallback = llvm::function_ref<void(OriginID, const LoanSet &)>; + void forEachOriginWithLoansAt(ProgramPoint P, LoanMatchCallback CB) const; /// Builds the chain of origins through which a loan has propagated. /// diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h index 133aa02fa9a45..a2bd414cf20ad 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h @@ -35,7 +35,7 @@ class MovedLoansAnalysis { MovedLoansMap::Factory &MovedLoansMapFactory); ~MovedLoansAnalysis(); - MovedLoansMap getMovedLoans(ProgramPoint P) const; + const MovedLoansMap &getMovedLoans(ProgramPoint P) const; private: class Impl; diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h index 62eec670c54a2..0ac028ff015b3 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h @@ -46,8 +46,17 @@ using MapTy = llvm::ImmutableMap<KeyT, ValT, llvm::ImutKeyValueInfo<KeyT, ValT>, /// Computes the union of two ImmutableSets. template <typename T> -SetTy<T> join(SetTy<T> A, SetTy<T> B, typename SetTy<T>::Factory &F) { - return F.unionSets(A, B); +SetTy<T> join(const SetTy<T> &A_ref, const SetTy<T> &B_ref, typename SetTy<T>::Factory &F) { + if (A_ref.getRootWithoutRetain() == B_ref.getRootWithoutRetain()) + return A_ref; + SetTy<T> A = A_ref; + SetTy<T> B = B_ref; + SetTy<T> Result = F.unionSets(A, B); + if (Result.getRootWithoutRetain() == A_ref.getRootWithoutRetain()) + return A_ref; + if (Result.getRootWithoutRetain() == B_ref.getRootWithoutRetain()) + return B_ref; + return Result; } /// Describes the strategy for joining two `ImmutableMap` instances, primarily @@ -72,30 +81,43 @@ enum class JoinKind { /// JoinValues is commutative with a left identity, which holds for the /// lifetime lattices. template <typename KeyT, typename ValT, typename Joiner> -MapTy<KeyT, ValT> join(MapTy<KeyT, ValT> A, MapTy<KeyT, ValT> B, +MapTy<KeyT, ValT> join(const MapTy<KeyT, ValT> &A_ref, const MapTy<KeyT, ValT> &B_ref, typename MapTy<KeyT, ValT>::Factory &F, Joiner JoinValues, JoinKind Kind) { - if (A.getRootWithoutRetain() == B.getRootWithoutRetain()) - return A; - // Drive the merge with the taller map so the shorter one is the one split. - if (A.getHeight() < B.getHeight()) + if (A_ref.getRootWithoutRetain() == B_ref.getRootWithoutRetain()) + return A_ref; + + MapTy<KeyT, ValT> A = A_ref; + MapTy<KeyT, ValT> B = B_ref; + + bool Swapped = false; + if (A.getHeight() < B.getHeight()) { std::swap(A, B); + Swapped = true; + } using ValueTy = typename MapTy<KeyT, ValT>::value_type; - auto Combine = [&JoinValues](const ValueTy *AElem, + auto Combine = [&JoinValues, Swapped](const ValueTy *AElem, const ValueTy *BElem) -> std::pair<KeyT, ValT> { + const ValueTy *OrigA = Swapped ? BElem : AElem; + const ValueTy *OrigB = Swapped ? AElem : BElem; const KeyT &Key = AElem ? AElem->first : BElem->first; return std::pair<KeyT, ValT>(Key, - JoinValues(AElem ? &AElem->second : nullptr, - BElem ? &BElem->second : nullptr)); + JoinValues(OrigA ? &OrigA->second : nullptr, + OrigB ? &OrigB->second : nullptr)); }; // Asymmetric keeps keys unique to either map as-is (valid because JoinValues // has a left identity); symmetric passes unmatched keys through JoinValues. // The lifetime joins are idempotent lattice joins, so pointer-identical // subtrees (common once one state is derived from the other) can be shared. - return F.mergeWith(A, B, Combine, - /*KeepUnmatched=*/Kind == JoinKind::Asymmetric, - /*SkipShared=*/true); + MapTy<KeyT, ValT> Result = F.mergeWith(A, B, Combine, + /*KeepUnmatched=*/Kind == JoinKind::Asymmetric, + /*SkipShared=*/true); + if (Result.getRootWithoutRetain() == A_ref.getRootWithoutRetain()) + return A_ref; + if (Result.getRootWithoutRetain() == B_ref.getRootWithoutRetain()) + return B_ref; + return Result; } } // namespace clang::lifetimes::internal::utils diff --git a/clang/lib/Analysis/LifetimeSafety/Checker.cpp b/clang/lib/Analysis/LifetimeSafety/Checker.cpp index 53e5077131147..678c32c9844f1 100644 --- a/clang/lib/Analysis/LifetimeSafety/Checker.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Checker.cpp @@ -56,7 +56,19 @@ using AnnotationTarget = using EscapingTarget = LifetimeSafetySemaHelper::EscapingTarget; class LifetimeChecker { -private: + struct PathKey { + const void *RootVal; + unsigned Kind; + bool operator<(const PathKey &Other) const { + if (RootVal != Other.RootVal) + return RootVal < Other.RootVal; + return Kind < Other.Kind; + } + bool operator==(const PathKey &Other) const { + return RootVal == Other.RootVal && Kind == Other.Kind; + } + }; + std::vector<std::pair<PathKey, llvm::SmallVector<LoanID, 2>>> LoansByPath; llvm::DenseMap<LoanID, PendingWarning> FinalWarningsMap; llvm::DenseMap<AnnotationTarget, EscapingTarget> AnnotationWarningsMap; llvm::DenseMap<const ParmVarDecl *, EscapingTarget> NoescapeWarningsMap; @@ -95,6 +107,39 @@ class LifetimeChecker { LiveOrigins(LiveOrigins), FactMgr(FM), SemaHelper(SemaHelper), AST(ADC.getASTContext()), Cfg(ADC.getCFG()), FD(ADC.getDecl()), LSOpts(LSOpts) { + for (const Loan *Loan : FactMgr.getLoanMgr().getLoans()) { + const AccessPath &Path = Loan->getAccessPath(); + const void *RootVal = nullptr; + switch (Path.getKind()) { + case AccessPath::Kind::ValueDecl: + RootVal = Path.getAsValueDecl(); + break; + case AccessPath::Kind::MaterializeTemporary: + RootVal = Path.getAsMaterializeTemporaryExpr(); + break; + case AccessPath::Kind::PlaceholderParam: + RootVal = Path.getAsPlaceholderParam(); + break; + case AccessPath::Kind::PlaceholderThis: + RootVal = Path.getAsPlaceholderThis(); + break; + case AccessPath::Kind::NewAllocation: + RootVal = Path.getAsNewAllocation(); + break; + } + PathKey Key = {RootVal, static_cast<unsigned>(Path.getKind())}; + auto It = std::lower_bound(LoansByPath.begin(), LoansByPath.end(), Key, + [](const auto &X, const PathKey &K) { + return X.first < K; + }); + if (It != LoansByPath.end() && It->first == Key) { + It->second.push_back(Loan->getID()); + } else { + llvm::SmallVector<LoanID, 2> Vec; + Vec.push_back(Loan->getID()); + LoansByPath.insert(It, {Key, std::move(Vec)}); + } + } for (const CFGBlock *B : *ADC.getAnalysis<PostOrderCFGView>()) for (const Fact *F : FactMgr.getFacts(B)) if (const auto *EF = F->getAs<ExpireFact>()) @@ -121,7 +166,9 @@ class LifetimeChecker { /// [[clang::noescape]]. void checkAnnotations(const OriginEscapesFact *OEF) { OriginID EscapedOID = OEF->getEscapedOriginID(); - LoanSet EscapedLoans = LoanPropagation.getLoans(EscapedOID, OEF); + const LoanSet *EscapedLoans = LoanPropagation.getLoans(EscapedOID, OEF); + if (!EscapedLoans) + return; auto CheckParam = [&](const ParmVarDecl *PVD, bool IsMoved) { // NoEscape param should not escape. if (PVD->hasAttr<NoEscapeAttr>()) { @@ -164,7 +211,7 @@ class LifetimeChecker { } }; auto MovedAtEscape = MovedLoans.getMovedLoans(OEF); - for (LoanID LID : EscapedLoans) { + for (LoanID LID : *EscapedLoans) { const Loan *L = FactMgr.getLoanMgr().getLoan(LID); const AccessPath &AP = L->getAccessPath(); if (const auto *PVD = AP.getAsPlaceholderParam()) @@ -174,6 +221,36 @@ class LifetimeChecker { } } + /// Returns the corresponding loan IDs for an AccessPath using the precomputed map. + llvm::ArrayRef<LoanID> getLoansForPath(const AccessPath &Path) const { + const void *RootVal = nullptr; + switch (Path.getKind()) { + case AccessPath::Kind::ValueDecl: + RootVal = Path.getAsValueDecl(); + break; + case AccessPath::Kind::MaterializeTemporary: + RootVal = Path.getAsMaterializeTemporaryExpr(); + break; + case AccessPath::Kind::PlaceholderParam: + RootVal = Path.getAsPlaceholderParam(); + break; + case AccessPath::Kind::PlaceholderThis: + RootVal = Path.getAsPlaceholderThis(); + break; + case AccessPath::Kind::NewAllocation: + RootVal = Path.getAsNewAllocation(); + break; + } + PathKey Key = {RootVal, static_cast<unsigned>(Path.getKind())}; + auto It = std::lower_bound(LoansByPath.begin(), LoansByPath.end(), Key, + [](const auto &X, const PathKey &K) { + return X.first < K; + }); + if (It != LoansByPath.end() && It->first == Key) + return It->second; + return {}; + } + /// Checks for use-after-free & use-after-return errors when an access path /// expires (e.g., a variable goes out of scope). /// @@ -182,29 +259,32 @@ class LifetimeChecker { /// hold that are prefixed by the expired path. void checkExpiry(const ExpireFact *EF) { const AccessPath &ExpiredPath = EF->getAccessPath(); - LivenessMap Origins = LiveOrigins.getLiveOriginsAt(EF); - for (auto &[OID, LiveInfo] : Origins) { - LoanSet HeldLoans = LoanPropagation.getLoans(OID, EF); - for (LoanID HeldLoanID : HeldLoans) { - const Loan *HeldLoan = FactMgr.getLoanMgr().getLoan(HeldLoanID); - if (ExpiredPath != HeldLoan->getAccessPath()) - continue; - // HeldLoan is expired because its AccessPath is expired. - PendingWarning &CurWarning = FinalWarningsMap[HeldLoan->getID()]; - const Expr *MovedExpr = nullptr; - if (auto *ME = MovedLoans.getMovedLoans(EF).lookup(HeldLoanID)) - MovedExpr = *ME; - // Skip if we already have a dominating causing fact. - if (CurWarning.CausingFactDominatesExpiry) - continue; - if (causingFactDominatesExpiry(LiveInfo.Kind)) - CurWarning.CausingFactDominatesExpiry = true; - CurWarning.CausingFact = LiveInfo.CausingFact; - CurWarning.ExpiryLoc = EF->getExpiryLoc(); - CurWarning.MovedExpr = MovedExpr; - CurWarning.InvalidatedByExpr = nullptr; - } - } + + llvm::ArrayRef<LoanID> ExpiredLoanIDs = getLoansForPath(ExpiredPath); + if (ExpiredLoanIDs.empty()) + return; + + const LivenessMap &Origins = LiveOrigins.getLiveOriginsAt(EF); + + auto CheckLoans = [&](OriginID OID, const LoanSet &HeldLoans) { + for (LoanID HeldLoanID : ExpiredLoanIDs) { + if (!HeldLoans.contains(HeldLoanID)) continue; + const LivenessInfo *LiveInfo = Origins.lookup(OID); + if (!LiveInfo) continue; + + const Loan *HeldLoan = FactMgr.getLoanMgr().getLoan(HeldLoanID); + PendingWarning &CurWarning = FinalWarningsMap[HeldLoan->getID()]; + if (CurWarning.CausingFactDominatesExpiry) continue; + if (causingFactDominatesExpiry(LiveInfo->Kind)) + CurWarning.CausingFactDominatesExpiry = true; + CurWarning.CausingFact = LiveInfo->CausingFact; + CurWarning.ExpiryLoc = EF->getExpiryLoc(); + CurWarning.MovedExpr = MovedLoans.getMovedLoans(EF).lookup(HeldLoanID) ? *MovedLoans.getMovedLoans(EF).lookup(HeldLoanID) : nullptr; + CurWarning.InvalidatedByExpr = nullptr; + } + }; + + LoanPropagation.forEachOriginWithLoansAt(EF, CheckLoans); } /// Checks for use-after-invalidation errors when a container is modified. @@ -215,35 +295,47 @@ class LifetimeChecker { void checkInvalidation(const InvalidateOriginFact *IOF) { OriginID InvalidatedOrigin = IOF->getInvalidatedOrigin(); /// Get loans directly pointing to the invalidated container - LoanSet DirectlyInvalidatedLoans = + const LoanSet *DirectlyInvalidatedLoans = LoanPropagation.getLoans(InvalidatedOrigin, IOF); - auto IsInvalidated = [&](const Loan *L) { - for (LoanID InvalidID : DirectlyInvalidatedLoans) { - const Loan *InvalidL = FactMgr.getLoanMgr().getLoan(InvalidID); - if (InvalidL->getAccessPath() == L->getAccessPath()) - return true; + if (!DirectlyInvalidatedLoans || DirectlyInvalidatedLoans->isEmpty()) + return; + + llvm::SmallVector<LoanID, 4> InvalidatedLoanIDs; + for (const Loan *L : FactMgr.getLoanMgr().getLoans()) { + for (LoanID InvalidID : *DirectlyInvalidatedLoans) { + if (FactMgr.getLoanMgr().getLoan(InvalidID)->getAccessPath() == L->getAccessPath()) { + InvalidatedLoanIDs.push_back(L->getID()); + break; + } } - return false; - }; + } + if (InvalidatedLoanIDs.empty()) + return; + // For each live origin, check if it holds an invalidated loan and report. - LivenessMap Origins = LiveOrigins.getLiveOriginsAt(IOF); - for (auto &[OID, LiveInfo] : Origins) { - LoanSet HeldLoans = LoanPropagation.getLoans(OID, IOF); - for (LoanID LiveLoanID : HeldLoans) - if (IsInvalidated(FactMgr.getLoanMgr().getLoan(LiveLoanID))) { - bool CurDomination = causingFactDominatesExpiry(LiveInfo.Kind); - bool LastDomination = - FinalWarningsMap.lookup(LiveLoanID).CausingFactDominatesExpiry; - if (!LastDomination) { - FinalWarningsMap[LiveLoanID] = { - /*ExpiryLoc=*/{}, - /*CausingFact=*/LiveInfo.CausingFact, - /*MovedExpr=*/nullptr, - /*InvalidatedByExpr=*/IOF->getInvalidationExpr(), - /*CausingFactDominatesExpiry=*/CurDomination}; - } + const LivenessMap &Origins = LiveOrigins.getLiveOriginsAt(IOF); + + auto CheckLoans = [&](OriginID OID, const LoanSet &HeldLoans) { + for (LoanID LiveLoanID : InvalidatedLoanIDs) { + if (!HeldLoans.contains(LiveLoanID)) continue; + const LivenessInfo *LiveInfo = Origins.lookup(OID); + if (!LiveInfo) continue; + + bool CurDomination = causingFactDominatesExpiry(LiveInfo->Kind); + bool LastDomination = + FinalWarningsMap.lookup(LiveLoanID).CausingFactDominatesExpiry; + if (!LastDomination) { + FinalWarningsMap[LiveLoanID] = { + /*ExpiryLoc=*/{}, + /*CausingFact=*/LiveInfo->CausingFact, + /*MovedExpr=*/nullptr, + /*InvalidatedByExpr=*/IOF->getInvalidationExpr(), + /*CausingFactDominatesExpiry=*/CurDomination}; + } } - } + }; + + LoanPropagation.forEachOriginWithLoansAt(IOF, CheckLoans); } void issuePendingWarnings() { diff --git a/clang/lib/Analysis/LifetimeSafety/Dataflow.h b/clang/lib/Analysis/LifetimeSafety/Dataflow.h index fc3049c8bec84..4f4d01db36533 100644 --- a/clang/lib/Analysis/LifetimeSafety/Dataflow.h +++ b/clang/lib/Analysis/LifetimeSafety/Dataflow.h @@ -64,13 +64,14 @@ class DataflowAnalysis { AnalysisDeclContext &AC; /// The dataflow state before a basic block is processed. - llvm::DenseMap<const CFGBlock *, Lattice> InStates; + llvm::SmallVector<std::optional<Lattice>> InStates; /// The dataflow state after a basic block is processed. - llvm::DenseMap<const CFGBlock *, Lattice> OutStates; + llvm::SmallVector<std::optional<Lattice>> OutStates; /// Dataflow state at each program point, indexed by Fact ID. /// In a forward analysis, this is the state after the Fact at that point has /// been applied, while in a backward analysis, it is the state before. llvm::SmallVector<Lattice> PointToState; + llvm::BitVector PointInitialized; static constexpr bool isForward() { return Dir == Direction::Forward; } @@ -86,7 +87,15 @@ class DataflowAnalysis { Derived &D = static_cast<Derived &>(*this); llvm::TimeTraceScope Time(D.getAnalysisName()); - PointToState.resize(FactMgr.getNumFacts()); + PointToState.resize(FactMgr.getNumFacts(), D.getInitialState()); + PointInitialized.resize(FactMgr.getNumFacts()); + InStates.resize(Cfg.getNumBlockIDs()); + OutStates.resize(Cfg.getNumBlockIDs()); + + if (FactMgr.getLoanMgr().getLoans().empty() || !FactMgr.NeedsDataflow) { + PointInitialized.set(); + return; + } using Worklist = std::conditional_t<Dir == Direction::Forward, ForwardDataflowWorklist, @@ -94,23 +103,31 @@ class DataflowAnalysis { Worklist W(Cfg, AC); const CFGBlock *Start = isForward() ? &Cfg.getEntry() : &Cfg.getExit(); - InStates[Start] = D.getInitialState(); + InStates[Start->getBlockID()] = D.getInitialState(); W.enqueueBlock(Start); while (const CFGBlock *B = W.dequeue()) { Lattice StateIn = *getInState(B); - Lattice StateOut = transferBlock(B, StateIn); - OutStates[B] = StateOut; + std::optional<Lattice> StateOut = transferBlock(B, std::move(StateIn)); + // If none of the facts inside the block changed state, and the final state + // is unchanged, transferBlock returns std::nullopt. We don't need to propagate. + if (!StateOut) + continue; + + const std::optional<Lattice> &OldOutState = getOutState(B); + if (OldOutState && *OldOutState == *StateOut) + continue; + OutStates[B->getBlockID()] = *StateOut; for (const CFGBlock *AdjacentB : isForward() ? B->succs() : B->preds()) { if (!AdjacentB) continue; - std::optional<Lattice> OldInState = getInState(AdjacentB); + const std::optional<Lattice> &OldInState = getInState(AdjacentB); Lattice NewInState = - !OldInState ? StateOut : D.join(*OldInState, StateOut); + !OldInState ? *StateOut : D.join(*OldInState, *StateOut); // Enqueue the adjacent block if its in-state has changed or if we have // never seen it. if (!OldInState || NewInState != *OldInState) { - InStates[AdjacentB] = NewInState; + InStates[AdjacentB->getBlockID()] = std::move(NewInState); W.enqueueBlock(AdjacentB); } } @@ -118,43 +135,62 @@ class DataflowAnalysis { } protected: - Lattice getState(ProgramPoint P) const { + const Lattice &getState(ProgramPoint P) const { + assert(PointInitialized.test(P->getID().Value) && "Queried uninitialized state!"); return PointToState[P->getID().Value]; } - std::optional<Lattice> getInState(const CFGBlock *B) const { - auto It = InStates.find(B); - if (It == InStates.end()) - return std::nullopt; - return It->second; + const std::optional<Lattice> &getInState(const CFGBlock *B) const { + if (B->getBlockID() >= InStates.size()) { + static const std::optional<Lattice> Empty; + return Empty; + } + return InStates[B->getBlockID()]; } - Lattice getOutState(const CFGBlock *B) const { return OutStates.lookup(B); } - + const std::optional<Lattice> &getOutState(const CFGBlock *B) const { + if (B->getBlockID() >= OutStates.size()) { + static const std::optional<Lattice> Empty; + return Empty; + } + return OutStates[B->getBlockID()]; + } void dump() const { const Derived *D = static_cast<const Derived *>(this); llvm::dbgs() << "==========================================\n"; llvm::dbgs() << D->getAnalysisName() << " results:\n"; llvm::dbgs() << "==========================================\n"; const CFGBlock &B = isForward() ? Cfg.getExit() : Cfg.getEntry(); - getOutState(&B).dump(llvm::dbgs()); + if (auto Out = getOutState(&B)) { + Out->dump(llvm::dbgs()); + } else { + llvm::dbgs() << "No state for block\n"; + } } private: /// Computes the state at one end of a block by applying all its facts /// sequentially to a given state from the other end. - Lattice transferBlock(const CFGBlock *Block, Lattice State) { + std::optional<Lattice> transferBlock(const CFGBlock *Block, Lattice State) { auto Facts = FactMgr.getFacts(Block); if constexpr (isForward()) { for (const Fact *F : Facts) { - State = transferFact(State, F); - PointToState[F->getID().Value] = State; + State = transferFact(std::move(State), F); + unsigned ID = F->getID().Value; + if (PointInitialized.test(ID) && PointToState[ID] == State) + return std::nullopt; // Converged early + PointToState[ID] = State; + PointInitialized.set(ID); } } else { for (const Fact *F : llvm::reverse(Facts)) { // In backward analysis, capture the state before applying the fact. - PointToState[F->getID().Value] = State; - State = transferFact(State, F); + unsigned ID = F->getID().Value; + if (PointInitialized.test(ID) && PointToState[ID] == State) + return std::nullopt; // Converged early + PointToState[ID] = State; + PointInitialized.set(ID); + State = transferFact(std::move(State), F); } } return State; @@ -165,23 +201,23 @@ class DataflowAnalysis { Derived *D = static_cast<Derived *>(this); switch (F->getKind()) { case Fact::Kind::Issue: - return D->transfer(In, *F->getAs<IssueFact>()); + return D->transfer(std::move(In), *F->getAs<IssueFact>()); case Fact::Kind::Expire: - return D->transfer(In, *F->getAs<ExpireFact>()); + return D->transfer(std::move(In), *F->getAs<ExpireFact>()); case Fact::Kind::OriginFlow: - return D->transfer(In, *F->getAs<OriginFlowFact>()); + return D->transfer(std::move(In), *F->getAs<OriginFlowFact>()); case Fact::Kind::MovedOrigin: - return D->transfer(In, *F->getAs<MovedOriginFact>()); + return D->transfer(std::move(In), *F->getAs<MovedOriginFact>()); case Fact::Kind::OriginEscapes: - return D->transfer(In, *F->getAs<OriginEscapesFact>()); + return D->transfer(std::move(In), *F->getAs<OriginEscapesFact>()); case Fact::Kind::Use: - return D->transfer(In, *F->getAs<UseFact>()); + return D->transfer(std::move(In), *F->getAs<UseFact>()); case Fact::Kind::TestPoint: - return D->transfer(In, *F->getAs<TestPointFact>()); + return D->transfer(std::move(In), *F->getAs<TestPointFact>()); case Fact::Kind::InvalidateOrigin: - return D->transfer(In, *F->getAs<InvalidateOriginFact>()); + return D->transfer(std::move(In), *F->getAs<InvalidateOriginFact>()); case Fact::Kind::KillOrigin: - return D->transfer(In, *F->getAs<KillOriginFact>()); + return D->transfer(std::move(In), *F->getAs<KillOriginFact>()); } llvm_unreachable("Unknown fact kind"); } diff --git a/clang/lib/Analysis/LifetimeSafety/Facts.cpp b/clang/lib/Analysis/LifetimeSafety/Facts.cpp index ec2d42e10206a..3e573d5888b6f 100644 --- a/clang/lib/Analysis/LifetimeSafety/Facts.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Facts.cpp @@ -47,12 +47,12 @@ void OriginFlowFact::dump(llvm::raw_ostream &OS, const LoanManager &LM, OS << "\tDest: "; OM.dump(getDestOriginID(), OS); if (LPA) { - LoanSet DestinationLoans = LPA->getLoans(getDestOriginID(), this); - if (DestinationLoans.isEmpty()) + const LoanSet *DestinationLoans = LPA->getLoans(getDestOriginID(), this); + if (!DestinationLoans || DestinationLoans->isEmpty()) OS << " has no loans"; else { OS << " has loans to { "; - for (LoanID LID : DestinationLoans) { + for (LoanID LID : *DestinationLoans) { LM.getLoan(LID)->getAccessPath().dump(OS); OS << " "; } diff --git a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp index 69b903c813555..05da33a838194 100644 --- a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp @@ -22,10 +22,11 @@ struct Lattice { Lattice() : LiveOrigins(nullptr) {}; - explicit Lattice(LivenessMap L) : LiveOrigins(L) {} + explicit Lattice(LivenessMap L) : LiveOrigins(std::move(L)) {} bool operator==(const Lattice &Other) const { - return LiveOrigins == Other.LiveOrigins; + return LiveOrigins.getRootWithoutRetain() == + Other.LiveOrigins.getRootWithoutRetain(); } bool operator!=(const Lattice &Other) const { return !(*this == Other); } @@ -87,7 +88,7 @@ class AnalysisImpl /// Merges two lattices by combining liveness information. /// When the same origin has different confidence levels, we take the lower /// one. - Lattice join(Lattice L1, Lattice L2) const { + Lattice join(const Lattice &L1, const Lattice &L2) const { LivenessMap Merged = L1.LiveOrigins; // Take the earliest Fact to make the join hermetic and commutative. auto CombineCausingFact = [](CausingFactType A, @@ -96,6 +97,8 @@ class AnalysisImpl return B; if (!B) return A; + if (A == B) + return A; return GetFactLoc(A) < GetFactLoc(B) ? A : B; }; auto CombineLivenessKind = [](LivenessKind K1, @@ -114,6 +117,8 @@ class AnalysisImpl return LivenessInfo(L2->CausingFact, LivenessKind::Maybe); if (!L2) return LivenessInfo(L1->CausingFact, LivenessKind::Maybe); + if (*L1 == *L2) + return *L1; return LivenessInfo(CombineCausingFact(L1->CausingFact, L2->CausingFact), CombineLivenessKind(L1->Kind, L2->Kind)); }; @@ -128,66 +133,84 @@ class AnalysisImpl /// dominates this program point. A write operation kills the liveness of /// the origin since it overwrites the value. Lattice transfer(Lattice In, const UseFact &UF) { - Lattice Out = In; for (const OriginList *Cur = UF.getUsedOrigins(); Cur; Cur = Cur->peelOuterOrigin()) { OriginID OID = Cur->getOuterOriginID(); // Write kills liveness. if (UF.isWritten()) { - Out = Lattice(Factory.remove(Out.LiveOrigins, OID)); + if (In.LiveOrigins.lookup(OID)) + In = Lattice(Factory.remove(std::move(In.LiveOrigins), OID)); } else { // Read makes origin live with definite confidence (dominates this // point). - Out = Lattice(Factory.add(Out.LiveOrigins, OID, - LivenessInfo(&UF, LivenessKind::Must))); + LivenessInfo NewInfo(&UF, LivenessKind::Must); + if (const LivenessInfo *Existing = In.LiveOrigins.lookup(OID)) { + if (Existing->Kind == NewInfo.Kind) + continue; + } + In = Lattice(Factory.add(std::move(In.LiveOrigins), OID, NewInfo)); } } - return Out; + return In; } /// An escaping origin (e.g., via return) makes the origin live with definite /// confidence, as it dominates this program point. Lattice transfer(Lattice In, const OriginEscapesFact &OEF) { OriginID OID = OEF.getEscapedOriginID(); - return Lattice(Factory.add(In.LiveOrigins, OID, - LivenessInfo(&OEF, LivenessKind::Must))); + LivenessInfo NewInfo(&OEF, LivenessKind::Must); + if (const LivenessInfo *Existing = In.LiveOrigins.lookup(OID)) { + if (Existing->Kind == NewInfo.Kind) + return In; + } + return Lattice(Factory.add(std::move(In.LiveOrigins), OID, NewInfo)); } /// Issuing a new loan to an origin kills its liveness. Lattice transfer(Lattice In, const IssueFact &IF) { - return Lattice(Factory.remove(In.LiveOrigins, IF.getOriginID())); + if (In.LiveOrigins.lookup(IF.getOriginID())) + return Lattice(Factory.remove(std::move(In.LiveOrigins), IF.getOriginID())); + return In; } /// An OriginFlow kills the liveness of the destination origin if `KillDest` /// is true. Otherwise, it propagates liveness from destination to source. Lattice transfer(Lattice In, const OriginFlowFact &OF) { - Lattice Out = In; OriginID Dest = OF.getDestOriginID(); OriginID Src = OF.getSrcOriginID(); // If the destination of the flow is live, the source of the flow must also // be marked live before this point as its value will flow into the // destination. - if (In.LiveOrigins.contains(Dest)) { - const LivenessInfo *DestInfo = In.LiveOrigins.lookup(Dest); - assert(DestInfo); - Out = Lattice(Factory.add(Out.LiveOrigins, Src, *DestInfo)); + bool DestLive = false; + if (const LivenessInfo *DestInfo = In.LiveOrigins.lookup(Dest)) { + DestLive = true; + if (const LivenessInfo *ExistingSrc = In.LiveOrigins.lookup(Src)) { + if (ExistingSrc->Kind != DestInfo->Kind) + In = Lattice(Factory.add(std::move(In.LiveOrigins), Src, *DestInfo)); + } else { + In = Lattice(Factory.add(std::move(In.LiveOrigins), Src, *DestInfo)); + } } - if (OF.getKillDest()) - Out = Lattice(Factory.remove(Out.LiveOrigins, Dest)); - return Out; + if (OF.getKillDest() && DestLive) + In = Lattice(Factory.remove(std::move(In.LiveOrigins), Dest)); + return In; } Lattice transfer(Lattice In, const KillOriginFact &F) { - return Lattice(Factory.remove(In.LiveOrigins, F.getKilledOrigin())); + if (In.LiveOrigins.lookup(F.getKilledOrigin())) + return Lattice(Factory.remove(std::move(In.LiveOrigins), F.getKilledOrigin())); + return In; } Lattice transfer(Lattice In, const ExpireFact &F) { - if (auto OID = F.getOriginID()) - return Lattice(Factory.remove(In.LiveOrigins, *OID)); + if (auto OID = F.getOriginID()) { + if (In.LiveOrigins.lookup(*OID)) + return Lattice(Factory.remove(std::move(In.LiveOrigins), *OID)); + } return In; } - LivenessMap getLiveOriginsAt(ProgramPoint P) const { + const LivenessMap &getLiveOriginsAt(ProgramPoint P) const { return getState(P).LiveOrigins; } @@ -223,7 +246,7 @@ LiveOriginsAnalysis::LiveOriginsAnalysis(const CFG &C, AnalysisDeclContext &AC, LiveOriginsAnalysis::~LiveOriginsAnalysis() = default; -LivenessMap LiveOriginsAnalysis::getLiveOriginsAt(ProgramPoint P) const { +const LivenessMap &LiveOriginsAnalysis::getLiveOriginsAt(ProgramPoint P) const { return PImpl->getLiveOriginsAt(P); } diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp index 078892bd48c10..d90a6f04399cb 100644 --- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp @@ -97,14 +97,16 @@ struct Lattice { /// Origins confined to a single block. Discarded at block boundaries. OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr); - explicit Lattice(const OriginLoanMap &Persistent, - const OriginLoanMap &BlockLocal) - : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {} + explicit Lattice(OriginLoanMap Persistent, OriginLoanMap BlockLocal) + : PersistentOrigins(std::move(Persistent)), + BlockLocalOrigins(std::move(BlockLocal)) {} Lattice() = default; bool operator==(const Lattice &Other) const { - return PersistentOrigins == Other.PersistentOrigins && - BlockLocalOrigins == Other.BlockLocalOrigins; + return PersistentOrigins.getRootWithoutRetain() == + Other.PersistentOrigins.getRootWithoutRetain() && + BlockLocalOrigins.getRootWithoutRetain() == + Other.BlockLocalOrigins.getRootWithoutRetain(); } bool operator!=(const Lattice &Other) const { return !(*this == Other); } @@ -149,7 +151,7 @@ class AnalysisImpl /// Merges two lattices by taking the union of loans for each origin. /// Only persistent origins are joined; block-local origins are discarded. - Lattice join(Lattice A, Lattice B) { + Lattice join(const Lattice &A, const Lattice &B) { OriginLoanMap JoinedOrigins = utils::join( A.PersistentOrigins, B.PersistentOrigins, OriginLoanMapFactory, [&](const LoanSet *S1, const LoanSet *S2) { @@ -170,8 +172,13 @@ class AnalysisImpl Lattice transfer(Lattice In, const IssueFact &F) { OriginID OID = F.getOriginID(); LoanID LID = F.getLoanID(); + const LoanSet *Existing = isPersistent(OID) + ? In.PersistentOrigins.lookup(OID) + : In.BlockLocalOrigins.lookup(OID); + if (Existing && Existing->isSingleton() && Existing->contains(LID)) + return In; LoanSet NewLoans = LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID); - return setLoans(In, OID, NewLoans); + return setLoans(std::move(In), OID, NewLoans, Existing); } /// A flow from source to destination. If `KillDest` is true, this replaces @@ -181,33 +188,57 @@ class AnalysisImpl OriginID DestOID = F.getDestOriginID(); OriginID SrcOID = F.getSrcOriginID(); + const LoanSet *Existing = isPersistent(DestOID) + ? In.PersistentOrigins.lookup(DestOID) + : In.BlockLocalOrigins.lookup(DestOID); + LoanSet DestLoans = - F.getKillDest() ? LoanSetFactory.getEmptySet() : getLoans(In, DestOID); - LoanSet SrcLoans = getLoans(In, SrcOID); - LoanSet MergedLoans = utils::join(DestLoans, SrcLoans, LoanSetFactory); + Existing ? (F.getKillDest() ? LoanSetFactory.getEmptySet() : *Existing) + : LoanSetFactory.getEmptySet(); + + const LoanSet *SrcLoans = getLoans(In, SrcOID); + LoanSet MergedLoans = SrcLoans ? utils::join(DestLoans, *SrcLoans, LoanSetFactory) : DestLoans; - return setLoans(In, DestOID, MergedLoans); + return setLoans(std::move(In), DestOID, MergedLoans, Existing); } Lattice transfer(Lattice In, const KillOriginFact &F) { - return setLoans(In, F.getKilledOrigin(), LoanSetFactory.getEmptySet()); + OriginID OID = F.getKilledOrigin(); + const LoanSet *Existing = isPersistent(OID) + ? In.PersistentOrigins.lookup(OID) + : In.BlockLocalOrigins.lookup(OID); + return setLoans(std::move(In), OID, LoanSetFactory.getEmptySet(), Existing); } Lattice transfer(Lattice In, const ExpireFact &F) { - if (auto OID = F.getOriginID()) - return setLoans(In, *OID, LoanSetFactory.getEmptySet()); + if (auto OID = F.getOriginID()) { + const LoanSet *Existing = isPersistent(*OID) + ? In.PersistentOrigins.lookup(*OID) + : In.BlockLocalOrigins.lookup(*OID); + return setLoans(std::move(In), *OID, LoanSetFactory.getEmptySet(), Existing); + } return In; } - LoanSet getLoans(OriginID OID, ProgramPoint P) const { + const LoanSet *getLoans(OriginID OID, ProgramPoint P) const { return getLoans(getState(P), OID); } + void forEachOriginWithLoansAt(ProgramPoint P, + clang::lifetimes::internal::LoanPropagationAnalysis::LoanMatchCallback CB) const { + const auto &PState = getState(P); + for (const auto &[OID, Loans] : PState.PersistentOrigins) + CB(OID, Loans); + for (const auto &[OID, Loans] : PState.BlockLocalOrigins) + CB(OID, Loans); + } + llvm::SmallVector<OriginID> buildOriginFlowChain(ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan, const CFG *Cfg) const { - assert(getLoans(StartOID, StartPoint).contains(TargetLoan) && + const LoanSet *StartLoans = getLoans(StartOID, StartPoint); + assert(StartLoans && StartLoans->contains(TargetLoan) && "TargetLoan must be present in the StartOID at the StartPoint"); // Locate the CFG block containing the StartPoint @@ -253,8 +284,14 @@ class AnalysisImpl // current origin. for (const CFGBlock *PredBlock : CurrBlock->preds()) { SearchState NextState = {PredBlock, CurrOID}; - if (getLoans(getOutState(PredBlock), CurrOID).contains(TargetLoan) && - VistedStates.insert(NextState).second) + auto Out = getOutState(PredBlock); + if (Out) { + if (const LoanSet *OutLoans = getLoans(*Out, CurrOID)) { + if (OutLoans->contains(TargetLoan) && + VistedStates.insert(NextState).second) + PendingStates.push_back({NextState, CurrNode.OriginFlowChain}); + } + } PendingStates.push_back({NextState, CurrNode.OriginFlowChain}); } } @@ -268,9 +305,10 @@ class AnalysisImpl const CFG *Cfg) const { for (const OriginList *Cur = UF->getUsedOrigins(); Cur; Cur = Cur->peelOuterOrigin()) - if (getLoans(Cur->getOuterOriginID(), UF).contains(TargetLoan)) - return buildOriginFlowChain(UF, Cur->getOuterOriginID(), TargetLoan, - Cfg); + if (const LoanSet *Loans = getLoans(Cur->getOuterOriginID(), UF)) + if (Loans->contains(TargetLoan)) + return buildOriginFlowChain(UF, Cur->getOuterOriginID(), TargetLoan, + Cfg); return {}; } @@ -281,20 +319,30 @@ class AnalysisImpl return PersistentOrigins.test(OID.Value); } - Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) { + Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans, const LoanSet *Existing) { + if (Existing && *Existing == Loans) + return L; + + if (Loans.isEmpty()) { + if (!Existing) + return L; + if (isPersistent(OID)) + return Lattice(OriginLoanMapFactory.remove(L.PersistentOrigins, OID), + std::move(L.BlockLocalOrigins)); + return Lattice(std::move(L.PersistentOrigins), + OriginLoanMapFactory.remove(L.BlockLocalOrigins, OID)); + } if (isPersistent(OID)) return Lattice(OriginLoanMapFactory.add(L.PersistentOrigins, OID, Loans), - L.BlockLocalOrigins); - return Lattice(L.PersistentOrigins, + std::move(L.BlockLocalOrigins)); + return Lattice(std::move(L.PersistentOrigins), OriginLoanMapFactory.add(L.BlockLocalOrigins, OID, Loans)); } - LoanSet getLoans(Lattice L, OriginID OID) const { + const LoanSet *getLoans(const Lattice &L, OriginID OID) const { const OriginLoanMap *Map = isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins; - if (auto *Loans = Map->lookup(OID)) - return *Loans; - return LoanSetFactory.getEmptySet(); + return Map->lookup(OID); } /// Builds the chain of origins through which a loan has propagated. @@ -321,7 +369,8 @@ class AnalysisImpl continue; const OriginID SrcOriginID = OFF->getSrcOriginID(); - if (!getLoans(SrcOriginID, OFF).contains(TargetLoan)) + const LoanSet *Loans = getLoans(SrcOriginID, OFF); + if (!Loans || !Loans->contains(TargetLoan)) continue; OriginFlowChain.push_back(SrcOriginID); @@ -355,10 +404,14 @@ LoanPropagationAnalysis::LoanPropagationAnalysis( LoanPropagationAnalysis::~LoanPropagationAnalysis() = default; -LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const { +const LoanSet *LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const { return PImpl->getLoans(OID, P); } +void LoanPropagationAnalysis::forEachOriginWithLoansAt(ProgramPoint P, LoanPropagationAnalysis::LoanMatchCallback CB) const { + PImpl->forEachOriginWithLoansAt(P, CB); +} + llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain( ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan, const CFG *Cfg) const { diff --git a/clang/lib/Analysis/LifetimeSafety/MovedLoans.cpp b/clang/lib/Analysis/LifetimeSafety/MovedLoans.cpp index 138704821024a..83b60d6d227be 100644 --- a/clang/lib/Analysis/LifetimeSafety/MovedLoans.cpp +++ b/clang/lib/Analysis/LifetimeSafety/MovedLoans.cpp @@ -25,12 +25,13 @@ namespace { struct Lattice { MovedLoansMap MovedLoans = MovedLoansMap(nullptr); - explicit Lattice(MovedLoansMap MovedLoans) : MovedLoans(MovedLoans) {} + explicit Lattice(MovedLoansMap MovedLoans) : MovedLoans(std::move(MovedLoans)) {} Lattice() = default; bool operator==(const Lattice &Other) const { - return MovedLoans == Other.MovedLoans; + return MovedLoans.getRootWithoutRetain() == + Other.MovedLoans.getRootWithoutRetain(); } bool operator!=(const Lattice &Other) const { return !(*this == Other); } }; @@ -55,7 +56,7 @@ class AnalysisImpl /// Merges moved loan state from different control flow paths. When a loan /// is moved on multiple paths, picks the lexically earliest move expression. - Lattice join(Lattice A, Lattice B) { + Lattice join(const Lattice &A, const Lattice &B) { MovedLoansMap MovedLoans = utils::join( A.MovedLoans, B.MovedLoans, MovedLoansMapFactory, [](const Expr *const *MoveA, const Expr *const *MoveB) -> const Expr * { @@ -64,6 +65,8 @@ class AnalysisImpl return *MoveB; if (!MoveB) return *MoveA; + if (*MoveA == *MoveB) + return *MoveA; return (*MoveA)->getExprLoc() < (*MoveB)->getExprLoc() ? *MoveA : *MoveB; }, @@ -74,28 +77,39 @@ class AnalysisImpl /// Marks all live loans sharing the same access path as the moved origin as /// potentially moved. Lattice transfer(Lattice In, const MovedOriginFact &F) { - MovedLoansMap MovedLoans = In.MovedLoans; OriginID MovedOrigin = F.getMovedOrigin(); - LoanSet ImmediatelyMovedLoans = LoanPropagation.getLoans(MovedOrigin, &F); + const LoanSet *ImmediatelyMovedLoans = LoanPropagation.getLoans(MovedOrigin, &F); + if (!ImmediatelyMovedLoans || ImmediatelyMovedLoans->isEmpty()) + return In; + auto IsInvalidated = [&](const AccessPath &Path) { - for (LoanID LID : ImmediatelyMovedLoans) { + for (LoanID LID : *ImmediatelyMovedLoans) { const Loan *MovedLoan = LoanMgr.getLoan(LID); if (MovedLoan->getAccessPath() == Path) return true; } return false; }; - for (auto [O, _] : LiveOrigins.getLiveOriginsAt(&F)) - for (LoanID LiveLoan : LoanPropagation.getLoans(O, &F)) { - const Loan *LiveLoanPtr = LoanMgr.getLoan(LiveLoan); - if (IsInvalidated(LiveLoanPtr->getAccessPath())) - MovedLoans = - MovedLoansMapFactory.add(MovedLoans, LiveLoan, F.getMoveExpr()); - } - return Lattice(MovedLoans); + const auto &Origins = LiveOrigins.getLiveOriginsAt(&F); + + auto CheckLoans = [&](OriginID O, const LoanSet &Loans) { + if (!Origins.lookup(O)) return; + for (LoanID LiveLoan : Loans) { + const Loan *LiveLoanPtr = LoanMgr.getLoan(LiveLoan); + if (IsInvalidated(LiveLoanPtr->getAccessPath())) { + if (const Expr *const *Existing = In.MovedLoans.lookup(LiveLoan)) + if (*Existing == F.getMoveExpr()) + continue; + In = Lattice(MovedLoansMapFactory.add(std::move(In.MovedLoans), LiveLoan, F.getMoveExpr())); + } + } + }; + + LoanPropagation.forEachOriginWithLoansAt(&F, CheckLoans); + return In; } - MovedLoansMap getMovedLoans(ProgramPoint P) { return getState(P).MovedLoans; } + const MovedLoansMap &getMovedLoans(ProgramPoint P) { return getState(P).MovedLoans; } private: const LoanPropagationAnalysis &LoanPropagation; @@ -121,7 +135,7 @@ MovedLoansAnalysis::MovedLoansAnalysis( MovedLoansAnalysis::~MovedLoansAnalysis() = default; -MovedLoansMap MovedLoansAnalysis::getMovedLoans(ProgramPoint P) const { +const MovedLoansMap &MovedLoansAnalysis::getMovedLoans(ProgramPoint P) const { return PImpl->getMovedLoans(P); } } // namespace clang::lifetimes::internal diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 57cf7068affae..cb0512fbc6996 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -156,8 +156,9 @@ class LifetimeTestHelper { LoanSet Result = F.getEmptySet(); for (const auto &[OID, LI] : LiveOriginsMap) { - LoanSet Loans = LoanPropagation.getLoans(OID, P); - Result = clang::lifetimes::internal::utils::join(Result, Loans, F); + const LoanSet *Loans = LoanPropagation.getLoans(OID, P); + if (Loans && !Loans->isEmpty()) + Result = clang::lifetimes::internal::utils::join(Result, *Loans, F); } if (Result.isEmpty()) @@ -183,7 +184,10 @@ class LifetimeTestHelper { ProgramPoint PP = Runner.getProgramPoint(Annotation); if (!PP) return std::nullopt; - return Analysis.getLoanPropagation().getLoans(OID, PP); + const LoanSet *Loans = Analysis.getLoanPropagation().getLoans(OID, PP); + if (Loans && !Loans->isEmpty()) + return *Loans; + return std::nullopt; } std::optional<std::vector<std::pair<OriginID, LivenessKind>>> diff --git a/llvm/include/llvm/ADT/ImmutableSet.h b/llvm/include/llvm/ADT/ImmutableSet.h index 23d66caafce33..8e6aad758c93e 100644 --- a/llvm/include/llvm/ADT/ImmutableSet.h +++ b/llvm/include/llvm/ADT/ImmutableSet.h @@ -647,8 +647,10 @@ class ImutAVLFactory TreeTy *L = transformTree(getLeft(T), Combine, FromB); TreeTy *R = transformTree(getRight(T), Combine, FromB); const value_type &E = getValue(T); - return createNode(L, FromB ? Combine(nullptr, &E) : Combine(&E, nullptr), - R); + value_type NewE = FromB ? Combine(nullptr, &E) : Combine(&E, nullptr); + if (L == getLeft(T) && R == getRight(T) && T->isElementEqual(NewE)) + return T; + return createNode(L, NewE, R); } /// Merges \p A and \p B by recursing over \p A's structure and splitting \p B @@ -691,7 +693,10 @@ class ImutAVLFactory return A; return joinTrees(NewL, AElem, NewR); } - return joinTrees(NewL, Combine(&AElem, nullptr), NewR); + auto NewE = Combine(&AElem, nullptr); + if (NewL == getLeft(A) && NewR == getRight(A) && A->isElementEqual(NewE)) + return A; + return joinTrees(NewL, NewE, NewR); } // Key present in both: combine the two elements. Preserve sharing when the // combined value is unchanged and neither subtree moved, so that a join _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
