LoanPropagation.cpp

Go to the documentation of this file.

//===- LoanPropagation.cpp - Loan Propagation 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 <algorithm>
#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/ImmutableList.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/raw_ostream.h"
 
namespace clang::lifetimes::internal {
 
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.
struct Lattice {
  /// The map from an origin to the set of loans it contains.
  /// 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);
 
  explicit Lattice(const OriginLoanMap &Persistent,
                   const OriginLoanMap &BlockLocal)
      : PersistentOrigins(Persistent), BlockLocalOrigins(BlockLocal) {}
  Lattice() = default;
 
  bool operator==(const Lattice &Other) const {
    return PersistentOrigins == Other.PersistentOrigins &&
           BlockLocalOrigins == Other.BlockLocalOrigins;
  }
  bool operator!=(const Lattice &Other) const { return !(*this == Other); }
 
  void dump(llvm::raw_ostream &OS) const {
    OS << "LoanPropagationLattice State:\n";
    OS << " Persistent Origins:\n";
    if (PersistentOrigins.isEmpty())
      OS << "  <empty>\n";
    for (const auto &Entry : PersistentOrigins) {
      if (Entry.second.isEmpty())
        OS << "  Origin " << Entry.first << " contains no loans\n";
      for (const LoanID &LID : Entry.second)
        OS << "  Origin " << Entry.first << " contains Loan " << LID << "\n";
    }
    OS << " Block-Local Origins:\n";
    if (BlockLocalOrigins.isEmpty())
      OS << "  <empty>\n";
    for (const auto &Entry : BlockLocalOrigins) {
      if (Entry.second.isEmpty())
        OS << "  Origin " << Entry.first << " contains no loans\n";
      for (const LoanID &LID : Entry.second)
        OS << "  Origin " << Entry.first << " contains Loan " << LID << "\n";
    }
  }
};
 
class AnalysisImpl
    : public DataflowAnalysis<AnalysisImpl, Lattice, Direction::Forward> {
public:
  AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
               OriginLoanMap::Factory &OriginLoanMapFactory,
               LoanSet::Factory &LoanSetFactory)
      : DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),
        LoanSetFactory(LoanSetFactory),
        PersistentOrigins(F.getPersistentOrigins()) {}
 
  using Base::transfer;
 
  StringRef getAnalysisName() const { return "LoanPropagation"; }
 
  Lattice getInitialState() { return Lattice{}; }
 
  /// Merges two lattices by taking the union of loans for each origin.
  Lattice join(Lattice A, Lattice B) {
    assert(A.BlockLocalOrigins.isEmpty() && B.BlockLocalOrigins.isEmpty() &&
           "block-local origins must not reach a block boundary");
    OriginLoanMap JoinedOrigins = utils::join(
        A.PersistentOrigins, B.PersistentOrigins, OriginLoanMapFactory,
        [&](const LoanSet *S1, const LoanSet *S2) {
          assert((S1 || S2) && "unexpectedly merging 2 empty sets");
          if (!S1)
            return *S2;
          if (!S2)
            return *S1;
          return utils::join(*S1, *S2, LoanSetFactory);
        },
        // Asymmetric join is a performance win. For origins present only on one
        // branch, the loan set can be carried over as-is.
        utils::JoinKind::Asymmetric);
    return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap());
  }
 
  /// Block-local origins are not referenced outside the block that computed
  /// them, so they are dropped here rather than propagated to adjacent blocks.
  /// Dropping them at the boundary (instead of in `join`) also covers edges
  /// where `join` is never called, such as blocks with a single predecessor.
  Lattice transferAtBlockExit(Lattice L) {
    return Lattice(L.PersistentOrigins, OriginLoanMapFactory.getEmptyMap());
  }
 
  /// A new loan is issued to the origin. Old loans are erased.
  Lattice transfer(Lattice In, const IssueFact &F) {
    OriginID OID = F.getOriginID();
    LoanID LID = F.getLoanID();
    LoanSet NewLoans = LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID);
    return setLoans(In, OID, NewLoans);
  }
 
  /// A flow from source to destination. If `KillDest` is true, this replaces
  /// the destination's loans with the source's. Otherwise, the source's loans
  /// are merged into the destination's.
  Lattice transfer(Lattice In, const OriginFlowFact &F) {
    OriginID DestOID = F.getDestOriginID();
    OriginID SrcOID = F.getSrcOriginID();
 
    LoanSet DestLoans =
        F.getKillDest() ? LoanSetFactory.getEmptySet() : getLoans(In, DestOID);
    LoanSet SrcLoans = getLoans(In, SrcOID);
    LoanSet MergedLoans = utils::join(DestLoans, SrcLoans, LoanSetFactory);
 
    return setLoans(In, DestOID, MergedLoans);
  }
 
  Lattice transfer(Lattice In, const KillOriginFact &F) {
    return setLoans(In, F.getKilledOrigin(), LoanSetFactory.getEmptySet());
  }
 
  Lattice transfer(Lattice In, const ExpireFact &F) {
    if (auto OID = F.getOriginID())
      return setLoans(In, *OID, LoanSetFactory.getEmptySet());
    return In;
  }
 
  LoanSet getLoans(OriginID OID, ProgramPoint P) const {
    return getLoans(getState(P), OID);
  }
 
  llvm::SmallVector<OriginID> buildOriginFlowChain(ProgramPoint StartPoint,
                                                   const OriginID StartOID,
                                                   const LoanID TargetLoan,
                                                   const CFG *Cfg) const {
    assert(getLoans(StartOID, StartPoint).contains(TargetLoan) &&
           "TargetLoan must be present in the StartOID at the StartPoint");
 
    // Locate the CFG block containing the StartPoint
    const CFGBlock *EndBlock = nullptr;
    size_t BlockID = FactMgr.getBlockID(StartPoint);
    for (const CFGBlock *Block : *Cfg)
      if (Block->getBlockID() == BlockID) {
        EndBlock = Block;
        break;
      }
 
    // Set up DFS traversal state
    // SearchState tracks which block we're in and which origin we're tracing
    // Each DFSNode maintains its own OriginFlowChain.
    using SearchState = std::pair<const CFGBlock *, OriginID>;
    struct DFSNode {
      SearchState CurrState;
      llvm::ImmutableList<OriginID> OriginFlowChain;
    };
 
    llvm::SmallVector<DFSNode> PendingStates;
    llvm::SmallSet<SearchState, 16> VistedStates;
    llvm::ImmutableList<OriginID>::Factory OriginFlowChainFactory;
    PendingStates.push_back(
        {{EndBlock, StartOID}, OriginFlowChainFactory.getEmptyList()});
 
    // DFS loop to trace loan backwards through CFG
    while (!PendingStates.empty()) {
      DFSNode CurrNode = PendingStates.pop_back_val();
      auto [CurrBlock, CurrOID] = CurrNode.CurrState;
 
      // Trace origins within the current block
      const auto [BuildResult, Complete] =
          buildOriginFlowChain(CurrBlock, CurrOID, TargetLoan);
      if (!BuildResult.empty()) {
        for (OriginID OID : BuildResult)
          CurrNode.OriginFlowChain =
              OriginFlowChainFactory.add(OID, CurrNode.OriginFlowChain);
        CurrOID = BuildResult.back();
      }
 
      // If we found the IssueFact, we're done
      if (Complete) {
        llvm::SmallVector<OriginID> Result(CurrNode.OriginFlowChain.begin(),
                                           CurrNode.OriginFlowChain.end());
        std::reverse(Result.begin(), Result.end());
        return Result;
      }
 
      // Only explore predecessor blocks where the target loan is present in the
      // current origin.
      for (const CFGBlock *PredBlock : CurrBlock->preds()) {
        SearchState NextState = {PredBlock, CurrOID};
        if (getLoans(getOutState(PredBlock), CurrOID).contains(TargetLoan) &&
            VistedStates.insert(NextState).second)
          PendingStates.push_back({NextState, CurrNode.OriginFlowChain});
      }
    }
 
    llvm_unreachable("Could not reconstruct origin flow. Search finished "
                     "without reaching IssueFact");
  }
 
  llvm::SmallVector<OriginID> buildOriginFlowChain(const UseFact *UF,
                                                   const LoanID TargetLoan,
                                                   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);
 
    return {};
  }
 
private:
  /// Returns true if the origin is persistent (referenced in multiple blocks).
  bool isPersistent(OriginID OID) const {
    return PersistentOrigins.test(OID.Value);
  }
 
  Lattice setLoans(Lattice L, OriginID OID, LoanSet Loans) {
    if (isPersistent(OID))
      return Lattice(OriginLoanMapFactory.add(L.PersistentOrigins, OID, Loans),
                     L.BlockLocalOrigins);
    return Lattice(L.PersistentOrigins,
                   OriginLoanMapFactory.add(L.BlockLocalOrigins, OID, Loans));
  }
 
  LoanSet getLoans(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();
  }
 
  /// Builds the chain of origins through which a loan has propagated.
  ///
  /// This procedure operates strictly within a single Block. Starting from the
  /// last fact of the Block, it traces backwards through OriginFlowFacts to
  /// identify the sequence of origins through which the loan flowed.
  ///
  /// Returns (chain, true) if the target loan origin is found during the
  /// traversal, otherwise returns (chain, false).
  std::pair<llvm::SmallVector<OriginID>, bool>
  buildOriginFlowChain(const CFGBlock *Block, const OriginID StartOID,
                       const LoanID TargetLoan) const {
    OriginID CurrOID = StartOID;
    llvm::SmallVector<OriginID> OriginFlowChain;
 
    for (const Fact *F : llvm::reverse(FactMgr.getFacts(Block))) {
      if (const auto *IF = F->getAs<IssueFact>())
        if (IF->getLoanID() == TargetLoan && IF->getOriginID() == CurrOID)
          return {OriginFlowChain, true};
 
      const auto *OFF = F->getAs<OriginFlowFact>();
      if (!OFF || OFF->getDestOriginID() != CurrOID)
        continue;
 
      const OriginID SrcOriginID = OFF->getSrcOriginID();
      if (!getLoans(SrcOriginID, OFF).contains(TargetLoan))
        continue;
 
      OriginFlowChain.push_back(SrcOriginID);
      CurrOID = SrcOriginID;
    }
 
    return {OriginFlowChain, false};
  }
 
  OriginLoanMap::Factory &OriginLoanMapFactory;
  LoanSet::Factory &LoanSetFactory;
  /// Origins referenced from more than one basic block; see
  /// `FactManager::getPersistentOrigins`.
  const llvm::BitVector &PersistentOrigins;
};
} // namespace
 
class LoanPropagationAnalysis::Impl final : public AnalysisImpl {
  using AnalysisImpl::AnalysisImpl;
};
 
LoanPropagationAnalysis::LoanPropagationAnalysis(
    const CFG &C, AnalysisDeclContext &AC, FactManager &F,
    OriginLoanMap::Factory &OriginLoanMapFactory,
    LoanSet::Factory &LoanSetFactory)
    : PImpl(std::make_unique<Impl>(C, AC, F, OriginLoanMapFactory,
                                   LoanSetFactory)) {
  PImpl->run();
}
 
LoanPropagationAnalysis::~LoanPropagationAnalysis() = default;
 
LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const {
  return PImpl->getLoans(OID, P);
}
 
llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain(
    ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan,
    const CFG *Cfg) const {
  return PImpl->buildOriginFlowChain(StartPoint, StartOID, TargetLoan, Cfg);
}
 
llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain(
    const UseFact *UF, const LoanID TargetLoan, const CFG *Cfg) const {
  return PImpl->buildOriginFlowChain(UF, TargetLoan, Cfg);
}
} // namespace clang::lifetimes::internal