193 lines · c
1//===- Dataflow.h - Generic Dataflow Analysis Framework --------*- 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// This file defines a generic, policy-based driver for dataflow analyses.10// It provides a flexible framework that combines the dataflow runner and11// transfer functions, allowing derived classes to implement specific analyses12// by defining their lattice, join, and transfer functions.13//14//===----------------------------------------------------------------------===//15#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_DATAFLOW_H16#define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_DATAFLOW_H17 18#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"19#include "clang/Analysis/AnalysisDeclContext.h"20#include "clang/Analysis/CFG.h"21#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"22#include "llvm/Support/Debug.h"23#include "llvm/Support/ErrorHandling.h"24#include "llvm/Support/TimeProfiler.h"25#include <optional>26 27namespace clang::lifetimes::internal {28 29enum class Direction { Forward, Backward };30 31/// A `ProgramPoint` identifies a location in the CFG by pointing to a specific32/// `Fact`. identified by a lifetime-related event (`Fact`).33///34/// A `ProgramPoint` has "after" semantics: it represents the location35/// immediately after its corresponding `Fact`.36using ProgramPoint = const Fact *;37 38/// A generic, policy-based driver for dataflow analyses. It combines39/// the dataflow runner and the transferer logic into a single class hierarchy.40///41/// The derived class is expected to provide:42/// - A `Lattice` type.43/// - `StringRef getAnalysisName() const`44/// - `Lattice getInitialState();` The initial state of the analysis.45/// - `Lattice join(Lattice, Lattice);` Merges states from multiple CFG paths.46/// - `Lattice transfer(Lattice, const FactType&);` Defines how a single47/// lifetime-relevant `Fact` transforms the lattice state. Only overloads48/// for facts relevant to the analysis need to be implemented.49///50/// \tparam Derived The CRTP derived class that implements the specific51/// analysis.52/// \tparam LatticeType The dataflow lattice used by the analysis.53/// \tparam Dir The direction of the analysis (Forward or Backward).54/// TODO: Maybe use the dataflow framework! The framework might need changes55/// to support the current comparison done at block-entry.56template <typename Derived, typename LatticeType, Direction Dir>57class DataflowAnalysis {58public:59 using Lattice = LatticeType;60 using Base = DataflowAnalysis<Derived, Lattice, Dir>;61 62private:63 const CFG &Cfg;64 AnalysisDeclContext &AC;65 66 /// The dataflow state before a basic block is processed.67 llvm::DenseMap<const CFGBlock *, Lattice> InStates;68 /// The dataflow state after a basic block is processed.69 llvm::DenseMap<const CFGBlock *, Lattice> OutStates;70 /// Dataflow state at each program point, indexed by Fact ID.71 /// In a forward analysis, this is the state after the Fact at that point has72 /// been applied, while in a backward analysis, it is the state before.73 llvm::SmallVector<Lattice> PointToState;74 75 static constexpr bool isForward() { return Dir == Direction::Forward; }76 77protected:78 FactManager &FactMgr;79 80 explicit DataflowAnalysis(const CFG &Cfg, AnalysisDeclContext &AC,81 FactManager &FactMgr)82 : Cfg(Cfg), AC(AC), FactMgr(FactMgr) {}83 84public:85 void run() {86 Derived &D = static_cast<Derived &>(*this);87 llvm::TimeTraceScope Time(D.getAnalysisName());88 89 PointToState.resize(FactMgr.getNumFacts());90 91 using Worklist =92 std::conditional_t<Dir == Direction::Forward, ForwardDataflowWorklist,93 BackwardDataflowWorklist>;94 Worklist W(Cfg, AC);95 96 const CFGBlock *Start = isForward() ? &Cfg.getEntry() : &Cfg.getExit();97 InStates[Start] = D.getInitialState();98 W.enqueueBlock(Start);99 100 while (const CFGBlock *B = W.dequeue()) {101 Lattice StateIn = *getInState(B);102 Lattice StateOut = transferBlock(B, StateIn);103 OutStates[B] = StateOut;104 for (const CFGBlock *AdjacentB : isForward() ? B->succs() : B->preds()) {105 if (!AdjacentB)106 continue;107 std::optional<Lattice> OldInState = getInState(AdjacentB);108 Lattice NewInState =109 !OldInState ? StateOut : D.join(*OldInState, StateOut);110 // Enqueue the adjacent block if its in-state has changed or if we have111 // never seen it.112 if (!OldInState || NewInState != *OldInState) {113 InStates[AdjacentB] = NewInState;114 W.enqueueBlock(AdjacentB);115 }116 }117 }118 }119 120protected:121 Lattice getState(ProgramPoint P) const {122 return PointToState[P->getID().Value];123 }124 125 std::optional<Lattice> getInState(const CFGBlock *B) const {126 auto It = InStates.find(B);127 if (It == InStates.end())128 return std::nullopt;129 return It->second;130 }131 132 Lattice getOutState(const CFGBlock *B) const { return OutStates.lookup(B); }133 134 void dump() const {135 const Derived *D = static_cast<const Derived *>(this);136 llvm::dbgs() << "==========================================\n";137 llvm::dbgs() << D->getAnalysisName() << " results:\n";138 llvm::dbgs() << "==========================================\n";139 const CFGBlock &B = isForward() ? Cfg.getExit() : Cfg.getEntry();140 getOutState(&B).dump(llvm::dbgs());141 }142 143private:144 /// Computes the state at one end of a block by applying all its facts145 /// sequentially to a given state from the other end.146 Lattice transferBlock(const CFGBlock *Block, Lattice State) {147 auto Facts = FactMgr.getFacts(Block);148 if constexpr (isForward()) {149 for (const Fact *F : Facts) {150 State = transferFact(State, F);151 PointToState[F->getID().Value] = State;152 }153 } else {154 for (const Fact *F : llvm::reverse(Facts)) {155 // In backward analysis, capture the state before applying the fact.156 PointToState[F->getID().Value] = State;157 State = transferFact(State, F);158 }159 }160 return State;161 }162 163 Lattice transferFact(Lattice In, const Fact *F) {164 assert(F);165 Derived *D = static_cast<Derived *>(this);166 switch (F->getKind()) {167 case Fact::Kind::Issue:168 return D->transfer(In, *F->getAs<IssueFact>());169 case Fact::Kind::Expire:170 return D->transfer(In, *F->getAs<ExpireFact>());171 case Fact::Kind::OriginFlow:172 return D->transfer(In, *F->getAs<OriginFlowFact>());173 case Fact::Kind::OriginEscapes:174 return D->transfer(In, *F->getAs<OriginEscapesFact>());175 case Fact::Kind::Use:176 return D->transfer(In, *F->getAs<UseFact>());177 case Fact::Kind::TestPoint:178 return D->transfer(In, *F->getAs<TestPointFact>());179 }180 llvm_unreachable("Unknown fact kind");181 }182 183public:184 Lattice transfer(Lattice In, const IssueFact &) { return In; }185 Lattice transfer(Lattice In, const ExpireFact &) { return In; }186 Lattice transfer(Lattice In, const OriginFlowFact &) { return In; }187 Lattice transfer(Lattice In, const OriginEscapesFact &) { return In; }188 Lattice transfer(Lattice In, const UseFact &) { return In; }189 Lattice transfer(Lattice In, const TestPointFact &) { return In; }190};191} // namespace clang::lifetimes::internal192#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_DATAFLOW_H193