234 lines · cpp
1//===- LoanPropagation.cpp - Loan Propagation 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#include <cassert>9#include <memory>10 11#include "Dataflow.h"12#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"13#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h"14#include "clang/Analysis/Analyses/LifetimeSafety/Loans.h"15#include "clang/Analysis/Analyses/LifetimeSafety/Origins.h"16#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h"17#include "clang/Analysis/AnalysisDeclContext.h"18#include "clang/Analysis/CFG.h"19#include "clang/Basic/LLVM.h"20#include "llvm/ADT/BitVector.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/Support/TimeProfiler.h"23#include "llvm/Support/raw_ostream.h"24 25namespace clang::lifetimes::internal {26 27// Prepass to find persistent origins. An origin is persistent if it is28// referenced in more than one basic block.29static llvm::BitVector computePersistentOrigins(const FactManager &FactMgr,30 const CFG &C) {31 llvm::TimeTraceScope("ComputePersistentOrigins");32 unsigned NumOrigins = FactMgr.getOriginMgr().getNumOrigins();33 llvm::BitVector PersistentOrigins(NumOrigins);34 35 llvm::SmallVector<const CFGBlock *> OriginToFirstSeenBlock(NumOrigins,36 nullptr);37 for (const CFGBlock *B : C) {38 for (const Fact *F : FactMgr.getFacts(B)) {39 auto CheckOrigin = [&](OriginID OID) {40 if (PersistentOrigins.test(OID.Value))41 return;42 auto &FirstSeenBlock = OriginToFirstSeenBlock[OID.Value];43 if (FirstSeenBlock == nullptr)44 FirstSeenBlock = B;45 if (FirstSeenBlock != B) {46 // We saw this origin in more than one block.47 PersistentOrigins.set(OID.Value);48 }49 };50 51 switch (F->getKind()) {52 case Fact::Kind::Issue:53 CheckOrigin(F->getAs<IssueFact>()->getOriginID());54 break;55 case Fact::Kind::OriginFlow: {56 const auto *OF = F->getAs<OriginFlowFact>();57 CheckOrigin(OF->getDestOriginID());58 CheckOrigin(OF->getSrcOriginID());59 break;60 }61 case Fact::Kind::Use:62 CheckOrigin(F->getAs<UseFact>()->getUsedOrigin());63 break;64 case Fact::Kind::OriginEscapes:65 case Fact::Kind::Expire:66 case Fact::Kind::TestPoint:67 break;68 }69 }70 }71 return PersistentOrigins;72}73 74namespace {75 76/// Represents the dataflow lattice for loan propagation.77///78/// This lattice tracks which loans each origin may hold at a given program79/// point.The lattice has a finite height: An origin's loan set is bounded by80/// the total number of loans in the function.81struct Lattice {82 /// The map from an origin to the set of loans it contains.83 /// Origins that appear in multiple blocks. Participates in join operations.84 OriginLoanMap PersistentOrigins = OriginLoanMap(nullptr);85 /// Origins confined to a single block. Discarded at block boundaries.86 OriginLoanMap BlockLocalOrigins = OriginLoanMap(nullptr);87 88 explicit Lattice(const OriginLoanMap &Persistent,89 const OriginLoanMap &BlockLocal)90 : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {}91 Lattice() = default;92 93 bool operator==(const Lattice &Other) const {94 return PersistentOrigins == Other.PersistentOrigins &&95 BlockLocalOrigins == Other.BlockLocalOrigins;96 }97 bool operator!=(const Lattice &Other) const { return !(*this == Other); }98 99 void dump(llvm::raw_ostream &OS) const {100 OS << "LoanPropagationLattice State:\n";101 OS << " Persistent Origins:\n";102 if (PersistentOrigins.isEmpty())103 OS << " <empty>\n";104 for (const auto &Entry : PersistentOrigins) {105 if (Entry.second.isEmpty())106 OS << " Origin " << Entry.first << " contains no loans\n";107 for (const LoanID &LID : Entry.second)108 OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";109 }110 OS << " Block-Local Origins:\n";111 if (BlockLocalOrigins.isEmpty())112 OS << " <empty>\n";113 for (const auto &Entry : BlockLocalOrigins) {114 if (Entry.second.isEmpty())115 OS << " Origin " << Entry.first << " contains no loans\n";116 for (const LoanID &LID : Entry.second)117 OS << " Origin " << Entry.first << " contains Loan " << LID << "\n";118 }119 }120};121 122class AnalysisImpl123 : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Forward> {124public:125 AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,126 OriginLoanMap::Factory &OriginLoanMapFactory,127 LoanSet::Factory &LoanSetFactory)128 : DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),129 LoanSetFactory(LoanSetFactory),130 PersistentOrigins(computePersistentOrigins(F, C)) {}131 132 using Base::transfer;133 134 StringRef getAnalysisName() const { return "LoanPropagation"; }135 136 Lattice getInitialState() { return Lattice{}; }137 138 /// Merges two lattices by taking the union of loans for each origin.139 /// Only persistent origins are joined; block-local origins are discarded.140 Lattice join(Lattice A, Lattice B) {141 OriginLoanMap JoinedOrigins = utils::join(142 A.PersistentOrigins, B.PersistentOrigins, OriginLoanMapFactory,143 [&](const LoanSet *S1, const LoanSet *S2) {144 assert((S1 || S2) && "unexpectedly merging 2 empty sets");145 if (!S1)146 return *S2;147 if (!S2)148 return *S1;149 return utils::join(*S1, *S2, LoanSetFactory);150 },151 // Asymmetric join is a performance win. For origins present only on one152 // branch, the loan set can be carried over as-is.153 utils::JoinKind::Asymmetric);154 return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap());155 }156 157 /// A new loan is issued to the origin. Old loans are erased.158 Lattice transfer(Lattice In, const IssueFact &F) {159 OriginID OID = F.getOriginID();160 LoanID LID = F.getLoanID();161 LoanSet NewLoans = LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID);162 return setLoans(In, OID, NewLoans);163 }164 165 /// A flow from source to destination. If `KillDest` is true, this replaces166 /// the destination's loans with the source's. Otherwise, the source's loans167 /// are merged into the destination's.168 Lattice transfer(Lattice In, const OriginFlowFact &F) {169 OriginID DestOID = F.getDestOriginID();170 OriginID SrcOID = F.getSrcOriginID();171 172 LoanSet DestLoans =173 F.getKillDest() ? LoanSetFactory.getEmptySet() : getLoans(In, DestOID);174 LoanSet SrcLoans = getLoans(In, SrcOID);175 LoanSet MergedLoans = utils::join(DestLoans, SrcLoans, LoanSetFactory);176 177 return setLoans(In, DestOID, MergedLoans);178 }179 180 LoanSet getLoans(OriginID OID, ProgramPoint P) const {181 return getLoans(getState(P), OID);182 }183 184private:185 /// Returns true if the origin is persistent (referenced in multiple blocks).186 bool isPersistent(OriginID OID) const {187 return PersistentOrigins.test(OID.Value);188 }189 190 Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {191 if (isPersistent(OID))192 return Lattice(OriginLoanMapFactory.add(L.PersistentOrigins, OID, Loans),193 L.BlockLocalOrigins);194 return Lattice(L.PersistentOrigins,195 OriginLoanMapFactory.add(L.BlockLocalOrigins, OID, Loans));196 }197 198 LoanSet getLoans(Lattice L, OriginID OID) const {199 const OriginLoanMap *Map =200 isPersistent(OID) ? &L.PersistentOrigins : &L.BlockLocalOrigins;201 if (auto *Loans = Map->lookup(OID))202 return *Loans;203 return LoanSetFactory.getEmptySet();204 }205 206 OriginLoanMap::Factory &OriginLoanMapFactory;207 LoanSet::Factory &LoanSetFactory;208 /// Boolean vector indexed by origin ID. If true, the origin appears in209 /// multiple basic blocks and must participate in join operations. If false,210 /// the origin is block-local and can be discarded at block boundaries.211 llvm::BitVector PersistentOrigins;212};213} // namespace214 215class LoanPropagationAnalysis::Impl final : public AnalysisImpl {216 using AnalysisImpl::AnalysisImpl;217};218 219LoanPropagationAnalysis::LoanPropagationAnalysis(220 const CFG &C, AnalysisDeclContext &AC, FactManager &F,221 OriginLoanMap::Factory &OriginLoanMapFactory,222 LoanSet::Factory &LoanSetFactory)223 : PImpl(std::make_unique<Impl>(C, AC, F, OriginLoanMapFactory,224 LoanSetFactory)) {225 PImpl->run();226}227 228LoanPropagationAnalysis::~LoanPropagationAnalysis() = default;229 230LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const {231 return PImpl->getLoans(OID, P);232}233} // namespace clang::lifetimes::internal234