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-exception
6//
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 and
11// transfer functions, allowing derived classes to implement specific analyses
12// by defining their lattice, join, and transfer functions.
13//
14//===----------------------------------------------------------------------===//
15#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_DATAFLOW_H
16#define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_DATAFLOW_H
17
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 specific
32/// `Fact`. identified by a lifetime-related event (`Fact`).
33///
34/// A `ProgramPoint` has "after" semantics: it represents the location
35/// immediately after its corresponding `Fact`.
36using ProgramPoint = const Fact *;
37
38/// A generic, policy-based driver for dataflow analyses. It combines
39/// 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 single
47/// lifetime-relevant `Fact` transforms the lattice state. Only overloads
48/// for facts relevant to the analysis need to be implemented.
49///
50/// \tparam Derived The CRTP derived class that implements the specific
51/// 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 changes
55/// 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 has
72 /// 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(Block: B, State: 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(B: 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 have
111 // 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: &B).dump(llvm::dbgs());
141 }
142
143private:
144 /// Computes the state at one end of a block by applying all its facts
145 /// sequentially to a given state from the other end.
146 Lattice transferBlock(const CFGBlock *Block, Lattice State) {
147 auto Facts = FactMgr.getFacts(B: Block);
148 if constexpr (isForward()) {
149 for (const Fact *F : Facts) {
150 State = transferFact(In: State, F);
151 PointToState[F->getID().Value] = State;
152 }
153 } else {
154 for (const Fact *F : llvm::reverse(C&: Facts)) {
155 // In backward analysis, capture the state before applying the fact.
156 PointToState[F->getID().Value] = State;
157 State = transferFact(In: 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::internal
192#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_DATAFLOW_H
193