199 lines · cpp
1//===- LiveOrigins.cpp - Live Origins Analysis -----------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h"10#include "Dataflow.h"11#include "llvm/Support/ErrorHandling.h"12 13namespace clang::lifetimes::internal {14namespace {15 16/// The dataflow lattice for origin liveness analysis.17/// It tracks which origins are live, why they're live (which UseFact),18/// and the confidence level of that liveness.19struct Lattice {20 LivenessMap LiveOrigins;21 22 Lattice() : LiveOrigins(nullptr) {};23 24 explicit Lattice(LivenessMap L) : LiveOrigins(L) {}25 26 bool operator==(const Lattice &Other) const {27 return LiveOrigins == Other.LiveOrigins;28 }29 30 bool operator!=(const Lattice &Other) const { return !(*this == Other); }31 32 void dump(llvm::raw_ostream &OS, const OriginManager &OM) const {33 if (LiveOrigins.isEmpty())34 OS << " <empty>\n";35 for (const auto &Entry : LiveOrigins) {36 OriginID OID = Entry.first;37 const LivenessInfo &Info = Entry.second;38 OS << " ";39 OM.dump(OID, OS);40 OS << " is ";41 switch (Info.Kind) {42 case LivenessKind::Must:43 OS << "definitely";44 break;45 case LivenessKind::Maybe:46 OS << "maybe";47 break;48 case LivenessKind::Dead:49 llvm_unreachable("liveness kind of live origins should not be dead.");50 }51 OS << " live at this point\n";52 }53 }54};55 56static SourceLocation GetFactLoc(CausingFactType F) {57 if (const auto *UF = F.dyn_cast<const UseFact *>())58 return UF->getUseExpr()->getExprLoc();59 if (const auto *OEF = F.dyn_cast<const OriginEscapesFact *>())60 return OEF->getEscapeExpr()->getExprLoc();61 llvm_unreachable("unhandled causing fact in PointerUnion");62}63 64/// The analysis that tracks which origins are live, with granular information65/// about the causing use fact and confidence level. This is a backward66/// analysis.67class AnalysisImpl68 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward> {69 70public:71 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,72 LivenessMap::Factory &SF)73 : DataflowAnalysis(C, AC, F), FactMgr(F), Factory(SF) {}74 using DataflowAnalysis<AnalysisImpl, Lattice, Direction::Backward>::transfer;75 76 StringRef getAnalysisName() const { return "LiveOrigins"; }77 78 Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); }79 80 /// Merges two lattices by combining liveness information.81 /// When the same origin has different confidence levels, we take the lower82 /// one.83 Lattice join(Lattice L1, Lattice L2) const {84 LivenessMap Merged = L1.LiveOrigins;85 // Take the earliest Fact to make the join hermetic and commutative.86 auto CombineCausingFact = [](CausingFactType A,87 CausingFactType B) -> CausingFactType {88 if (!A)89 return B;90 if (!B)91 return A;92 return GetFactLoc(A) < GetFactLoc(B) ? A : B;93 };94 auto CombineLivenessKind = [](LivenessKind K1,95 LivenessKind K2) -> LivenessKind {96 assert(K1 != LivenessKind::Dead && "LivenessKind should not be dead.");97 assert(K2 != LivenessKind::Dead && "LivenessKind should not be dead.");98 // Only return "Must" if both paths are "Must", otherwise Maybe.99 if (K1 == LivenessKind::Must && K2 == LivenessKind::Must)100 return LivenessKind::Must;101 return LivenessKind::Maybe;102 };103 auto CombineLivenessInfo = [&](const LivenessInfo *L1,104 const LivenessInfo *L2) -> LivenessInfo {105 assert((L1 || L2) && "unexpectedly merging 2 empty sets");106 if (!L1)107 return LivenessInfo(L2->CausingFact, LivenessKind::Maybe);108 if (!L2)109 return LivenessInfo(L1->CausingFact, LivenessKind::Maybe);110 return LivenessInfo(CombineCausingFact(L1->CausingFact, L2->CausingFact),111 CombineLivenessKind(L1->Kind, L2->Kind));112 };113 return Lattice(utils::join(114 L1.LiveOrigins, L2.LiveOrigins, Factory, CombineLivenessInfo,115 // A symmetric join is required here. If an origin is live on one116 // branch but not the other, its confidence must be demoted to `Maybe`.117 utils::JoinKind::Symmetric));118 }119 120 /// A read operation makes the origin live with definite confidence, as it121 /// dominates this program point. A write operation kills the liveness of122 /// the origin since it overwrites the value.123 Lattice transfer(Lattice In, const UseFact &UF) {124 OriginID OID = UF.getUsedOrigin();125 // Write kills liveness.126 if (UF.isWritten())127 return Lattice(Factory.remove(In.LiveOrigins, OID));128 // Read makes origin live with definite confidence (dominates this point).129 return Lattice(Factory.add(In.LiveOrigins, OID,130 LivenessInfo(&UF, LivenessKind::Must)));131 }132 133 /// An escaping origin (e.g., via return) makes the origin live with definite134 /// confidence, as it dominates this program point.135 Lattice transfer(Lattice In, const OriginEscapesFact &OEF) {136 OriginID OID = OEF.getEscapedOriginID();137 return Lattice(Factory.add(In.LiveOrigins, OID,138 LivenessInfo(&OEF, LivenessKind::Must)));139 }140 141 /// Issuing a new loan to an origin kills its liveness.142 Lattice transfer(Lattice In, const IssueFact &IF) {143 return Lattice(Factory.remove(In.LiveOrigins, IF.getOriginID()));144 }145 146 /// An OriginFlow kills the liveness of the destination origin if `KillDest`147 /// is true. Otherwise, it propagates liveness from destination to source.148 Lattice transfer(Lattice In, const OriginFlowFact &OF) {149 if (!OF.getKillDest())150 return In;151 return Lattice(Factory.remove(In.LiveOrigins, OF.getDestOriginID()));152 }153 154 LivenessMap getLiveOriginsAt(ProgramPoint P) const {155 return getState(P).LiveOrigins;156 }157 158 // Dump liveness values on all test points in the program.159 void dump(llvm::raw_ostream &OS,160 llvm::StringMap<ProgramPoint> TestPoints) const {161 llvm::dbgs() << "==========================================\n";162 llvm::dbgs() << getAnalysisName() << " results:\n";163 llvm::dbgs() << "==========================================\n";164 for (const auto &Entry : TestPoints) {165 OS << "TestPoint: " << Entry.getKey() << "\n";166 getState(Entry.getValue()).dump(OS, FactMgr.getOriginMgr());167 }168 }169 170private:171 FactManager &FactMgr;172 LivenessMap::Factory &Factory;173};174} // namespace175 176// PImpl wrapper implementation177class LiveOriginsAnalysis::Impl : public AnalysisImpl {178 using AnalysisImpl::AnalysisImpl;179};180 181LiveOriginsAnalysis::LiveOriginsAnalysis(const CFG &C, AnalysisDeclContext &AC,182 FactManager &F,183 LivenessMap::Factory &SF)184 : PImpl(std::make_unique<Impl>(C, AC, F, SF)) {185 PImpl->run();186}187 188LiveOriginsAnalysis::~LiveOriginsAnalysis() = default;189 190LivenessMap LiveOriginsAnalysis::getLiveOriginsAt(ProgramPoint P) const {191 return PImpl->getLiveOriginsAt(P);192}193 194void LiveOriginsAnalysis::dump(llvm::raw_ostream &OS,195 llvm::StringMap<ProgramPoint> TestPoints) const {196 PImpl->dump(OS, TestPoints);197}198} // namespace clang::lifetimes::internal199