aboutsummaryrefslogtreecommitdiff
path: root/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp')
-rw-r--r--clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp180
1 files changed, 0 insertions, 180 deletions
diff --git a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp b/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp
deleted file mode 100644
index cddb3f3c..0000000
--- a/clang/lib/Analysis/LifetimeSafety/LiveOrigins.cpp
+++ /dev/null
@@ -1,180 +0,0 @@
-//===- LiveOrigins.cpp - Live Origins Analysis -----------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h"
-#include "Dataflow.h"
-#include "llvm/Support/ErrorHandling.h"
-
-namespace clang::lifetimes::internal {
-namespace {
-
-/// The dataflow lattice for origin liveness analysis.
-/// It tracks which origins are live, why they're live (which UseFact),
-/// and the confidence level of that liveness.
-struct Lattice {
- LivenessMap LiveOrigins;
-
- Lattice() : LiveOrigins(nullptr) {};
-
- explicit Lattice(LivenessMap L) : LiveOrigins(L) {}
-
- bool operator==(const Lattice &Other) const {
- return LiveOrigins == Other.LiveOrigins;
- }
-
- bool operator!=(const Lattice &Other) const { return !(*this == Other); }
-
- void dump(llvm::raw_ostream &OS, const OriginManager &OM) const {
- if (LiveOrigins.isEmpty())
- OS << " <empty>\n";
- for (const auto &Entry : LiveOrigins) {
- OriginID OID = Entry.first;
- const LivenessInfo &Info = Entry.second;
- OS << " ";
- OM.dump(OID, OS);
- OS << " is ";
- switch (Info.Kind) {
- case LivenessKind::Must:
- OS << "definitely";
- break;
- case LivenessKind::Maybe:
- OS << "maybe";
- break;
- case LivenessKind::Dead:
- llvm_unreachable("liveness kind of live origins should not be dead.");
- }
- OS << " live at this point\n";
- }
- }
-};
-
-/// The analysis that tracks which origins are live, with granular information
-/// about the causing use fact and confidence level. This is a backward
-/// analysis.
-class AnalysisImpl
- : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward> {
-
-public:
- AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
- LivenessMap::Factory &SF)
- : DataflowAnalysis(C, AC, F), FactMgr(F), Factory(SF) {}
- using DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward>::transfer;
-
- StringRef getAnalysisName() const { return "LiveOrigins"; }
-
- Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); }
-
- /// 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 {
- LivenessMap Merged = L1.LiveOrigins;
- // Take the earliest UseFact to make the join hermetic and commutative.
- auto CombineUseFact = [](const UseFact &A,
- const UseFact &B) -> const UseFact * {
- return A.getUseExpr()->getExprLoc() < B.getUseExpr()->getExprLoc() ? &A
- : &B;
- };
- auto CombineLivenessKind = [](LivenessKind K1,
- LivenessKind K2) -> LivenessKind {
- assert(K1 != LivenessKind::Dead && "LivenessKind should not be dead.");
- assert(K2 != LivenessKind::Dead && "LivenessKind should not be dead.");
- // Only return "Must" if both paths are "Must", otherwise Maybe.
- if (K1 == LivenessKind::Must && K2 == LivenessKind::Must)
- return LivenessKind::Must;
- return LivenessKind::Maybe;
- };
- auto CombineLivenessInfo = [&](const LivenessInfo *L1,
- const LivenessInfo *L2) -> LivenessInfo {
- assert((L1 || L2) && "unexpectedly merging 2 empty sets");
- if (!L1)
- return LivenessInfo(L2->CausingUseFact, LivenessKind::Maybe);
- if (!L2)
- return LivenessInfo(L1->CausingUseFact, LivenessKind::Maybe);
- return LivenessInfo(
- CombineUseFact(*L1->CausingUseFact, *L2->CausingUseFact),
- CombineLivenessKind(L1->Kind, L2->Kind));
- };
- return Lattice(utils::join(
- L1.LiveOrigins, L2.LiveOrigins, Factory, CombineLivenessInfo,
- // A symmetric join is required here. If an origin is live on one
- // branch but not the other, its confidence must be demoted to `Maybe`.
- utils::JoinKind::Symmetric));
- }
-
- /// A read operation makes the origin live with definite confidence, as it
- /// 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) {
- OriginID OID = UF.getUsedOrigin(FactMgr.getOriginMgr());
- // Write kills liveness.
- if (UF.isWritten())
- return Lattice(Factory.remove(In.LiveOrigins, OID));
- // Read makes origin live with definite confidence (dominates this point).
- return Lattice(Factory.add(In.LiveOrigins, OID,
- LivenessInfo(&UF, LivenessKind::Must)));
- }
-
- /// 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()));
- }
-
- /// 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) {
- if (!OF.getKillDest())
- return In;
- return Lattice(Factory.remove(In.LiveOrigins, OF.getDestOriginID()));
- }
-
- LivenessMap getLiveOriginsAt(ProgramPoint P) const {
- return getState(P).LiveOrigins;
- }
-
- // Dump liveness values on all test points in the program.
- void dump(llvm::raw_ostream &OS,
- llvm::StringMap<ProgramPoint> TestPoints) const {
- llvm::dbgs() << "==========================================\n";
- llvm::dbgs() << getAnalysisName() << " results:\n";
- llvm::dbgs() << "==========================================\n";
- for (const auto &Entry : TestPoints) {
- OS << "TestPoint: " << Entry.getKey() << "\n";
- getState(Entry.getValue()).dump(OS, FactMgr.getOriginMgr());
- }
- }
-
-private:
- FactManager &FactMgr;
- LivenessMap::Factory &Factory;
-};
-} // namespace
-
-// PImpl wrapper implementation
-class LiveOriginsAnalysis::Impl : public AnalysisImpl {
- using AnalysisImpl::AnalysisImpl;
-};
-
-LiveOriginsAnalysis::LiveOriginsAnalysis(const CFG &C, AnalysisDeclContext &AC,
- FactManager &F,
- LivenessMap::Factory &SF)
- : PImpl(std::make_unique<Impl>(C, AC, F, SF)) {
- PImpl->run();
-}
-
-LiveOriginsAnalysis::~LiveOriginsAnalysis() = default;
-
-LivenessMap LiveOriginsAnalysis::getLiveOriginsAt(ProgramPoint P) const {
- return PImpl->getLiveOriginsAt(P);
-}
-
-void LiveOriginsAnalysis::dump(llvm::raw_ostream &OS,
- llvm::StringMap<ProgramPoint> TestPoints) const {
- PImpl->dump(OS, TestPoints);
-}
-} // namespace clang::lifetimes::internal