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/// It may additionally override `Lattice transferAtBlockExit(Lattice);` to
51/// drop state that is not visible outside the block it was computed in.
52///
53/// \tparam Derived The CRTP derived class that implements the specific
54/// analysis.
55/// \tparam LatticeType The dataflow lattice used by the analysis.
56/// \tparam Dir The direction of the analysis (Forward or Backward).
57/// TODO: Maybe use the dataflow framework! The framework might need changes
58/// to support the current comparison done at block-entry.
59template <typename Derived, typename LatticeType, Direction Dir>
60class DataflowAnalysis {
61public:
62 using Lattice = LatticeType;
63 using Base = DataflowAnalysis<Derived, Lattice, Dir>;
64
65private:
66 const CFG &Cfg;
67 AnalysisDeclContext &AC;
68
69 /// The dataflow state before a basic block is processed.
70 llvm::DenseMap<const CFGBlock *, Lattice> InStates;
71 /// The dataflow state after a basic block is processed.
72 llvm::DenseMap<const CFGBlock *, Lattice> OutStates;
73 /// Dataflow state at each program point, indexed by Fact ID.
74 /// In a forward analysis, this is the state after the Fact at that point has
75 /// been applied, while in a backward analysis, it is the state before.
76 llvm::SmallVector<Lattice> PointToState;
77
78 static constexpr bool isForward() { return Dir == Direction::Forward; }
79
80protected:
81 FactManager &FactMgr;
82
83 explicit DataflowAnalysis(const CFG &Cfg, AnalysisDeclContext &AC,
84 FactManager &FactMgr)
85 : Cfg(Cfg), AC(AC), FactMgr(FactMgr) {}
86
87public:
88 void run() {
89 Derived &D = static_cast<Derived &>(*this);
90 llvm::TimeTraceScope Time(D.getAnalysisName());
91
92 PointToState.resize(FactMgr.getNumFacts());
93
94 using Worklist =
95 std::conditional_t<Dir == Direction::Forward, ForwardDataflowWorklist,
96 BackwardDataflowWorklist>;
97 Worklist W(Cfg, AC);
98
99 const CFGBlock *Start = isForward() ? &Cfg.getEntry() : &Cfg.getExit();
100 InStates[Start] = D.getInitialState();
101 W.enqueueBlock(Start);
102 drainWorklist(D, W);
103
104 // Walking predecessors from the exit only reaches blocks that can reach the
105 // exit, e.g., it misses the body of an infinite loop. Analyze those too.
106 // Their in-state is left unset rather than seeded, so that only the first
107 // block analyzed in each such cycle starts from the initial state.
108 if constexpr (!isForward()) {
109 for (const CFGBlock *B : Cfg)
110 if (!InStates.contains(B))
111 W.enqueueBlock(B);
112 drainWorklist(D, W);
113 }
114 }
115
116private:
117 template <typename WorklistT> void drainWorklist(Derived &D, WorklistT &W) {
118 while (const CFGBlock *B = W.dequeue()) {
119 std::optional<Lattice> StateIn = getInState(B);
120 Lattice StateOut =
121 transferBlock(Block: B, State: StateIn ? *StateIn : D.getInitialState());
122 OutStates[B] = StateOut;
123 for (const CFGBlock *AdjacentB : isForward() ? B->succs() : B->preds()) {
124 if (!AdjacentB)
125 continue;
126 std::optional<Lattice> OldInState = getInState(B: AdjacentB);
127 Lattice NewInState =
128 !OldInState ? StateOut : D.join(*OldInState, StateOut);
129 // Enqueue the adjacent block if its in-state has changed or if we have
130 // never seen it.
131 if (!OldInState || NewInState != *OldInState) {
132 InStates[AdjacentB] = NewInState;
133 W.enqueueBlock(AdjacentB);
134 }
135 }
136 }
137 }
138
139protected:
140 Lattice getState(ProgramPoint P) const {
141 return PointToState[P->getID().Value];
142 }
143
144 std::optional<Lattice> getInState(const CFGBlock *B) const {
145 auto It = InStates.find(B);
146 if (It == InStates.end())
147 return std::nullopt;
148 return It->second;
149 }
150
151 Lattice getOutState(const CFGBlock *B) const { return OutStates.lookup(B); }
152
153 void dump() const {
154 const Derived *D = static_cast<const Derived *>(this);
155 llvm::dbgs() << "==========================================\n";
156 llvm::dbgs() << D->getAnalysisName() << " results:\n";
157 llvm::dbgs() << "==========================================\n";
158 const CFGBlock &B = isForward() ? Cfg.getExit() : Cfg.getEntry();
159 getOutState(B: &B).dump(llvm::dbgs());
160 }
161
162private:
163 /// Computes the state at one end of a block by applying all its facts
164 /// sequentially to a given state from the other end.
165 Lattice transferBlock(const CFGBlock *Block, Lattice State) {
166 auto Facts = FactMgr.getFacts(B: Block);
167 if constexpr (isForward()) {
168 for (const Fact *F : Facts) {
169 State = transferFact(In: State, F);
170 PointToState[F->getID().Value] = State;
171 }
172 } else {
173 for (const Fact *F : llvm::reverse(C&: Facts)) {
174 // In backward analysis, capture the state before applying the fact.
175 PointToState[F->getID().Value] = State;
176 State = transferFact(In: State, F);
177 }
178 }
179 return static_cast<Derived *>(this)->transferAtBlockExit(State);
180 }
181
182 Lattice transferFact(Lattice In, const Fact *F) {
183 assert(F);
184 Derived *D = static_cast<Derived *>(this);
185 switch (F->getKind()) {
186 case Fact::Kind::Issue:
187 return D->transfer(In, *F->getAs<IssueFact>());
188 case Fact::Kind::Expire:
189 return D->transfer(In, *F->getAs<ExpireFact>());
190 case Fact::Kind::OriginFlow:
191 return D->transfer(In, *F->getAs<OriginFlowFact>());
192 case Fact::Kind::MovedOrigin:
193 return D->transfer(In, *F->getAs<MovedOriginFact>());
194 case Fact::Kind::OriginEscapes:
195 return D->transfer(In, *F->getAs<OriginEscapesFact>());
196 case Fact::Kind::Use:
197 return D->transfer(In, *F->getAs<UseFact>());
198 case Fact::Kind::TestPoint:
199 return D->transfer(In, *F->getAs<TestPointFact>());
200 case Fact::Kind::InvalidateOrigin:
201 return D->transfer(In, *F->getAs<InvalidateOriginFact>());
202 case Fact::Kind::KillOrigin:
203 return D->transfer(In, *F->getAs<KillOriginFact>());
204 }
205 llvm_unreachable("Unknown fact kind");
206 }
207
208public:
209 Lattice transferAtBlockExit(Lattice In) { return In; }
210
211 Lattice transfer(Lattice In, const IssueFact &) { return In; }
212 Lattice transfer(Lattice In, const ExpireFact &) { return In; }
213 Lattice transfer(Lattice In, const OriginFlowFact &) { return In; }
214 Lattice transfer(Lattice In, const MovedOriginFact &) { return In; }
215 Lattice transfer(Lattice In, const OriginEscapesFact &) { return In; }
216 Lattice transfer(Lattice In, const UseFact &) { return In; }
217 Lattice transfer(Lattice In, const TestPointFact &) { return In; }
218 Lattice transfer(Lattice In, const InvalidateOriginFact &) { return In; }
219 Lattice transfer(Lattice In, const KillOriginFact &) { return In; }
220};
221} // namespace clang::lifetimes::internal
222#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_DATAFLOW_H
223