1//===- DataFlowFramework.cpp - A generic framework for data-flow analysis -===//
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#include "mlir/Analysis/DataFlowFramework.h"
10#include "mlir/IR/Location.h"
11#include "mlir/IR/Operation.h"
12#include "mlir/IR/SymbolTable.h"
13#include "mlir/IR/Value.h"
14#include "llvm/ADT/ScopeExit.h"
15#include "llvm/ADT/iterator.h"
16#include "llvm/Config/abi-breaking.h"
17#include "llvm/Support/Casting.h"
18#include "llvm/Support/DebugLog.h"
19#include "llvm/Support/raw_ostream.h"
20
21#define DEBUG_TYPE "dataflow"
22#if LLVM_ENABLE_ABI_BREAKING_CHECKS
23#define DATAFLOW_DEBUG(X) X
24#else
25#define DATAFLOW_DEBUG(X)
26#endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
27
28using namespace mlir;
29
30//===----------------------------------------------------------------------===//
31// GenericLatticeAnchor
32//===----------------------------------------------------------------------===//
33
34GenericLatticeAnchor::~GenericLatticeAnchor() = default;
35
36//===----------------------------------------------------------------------===//
37// AnalysisState
38//===----------------------------------------------------------------------===//
39
40AnalysisState::~AnalysisState() = default;
41
42void AnalysisState::addDependency(ProgramPoint *dependent,
43 DataFlowAnalysis *analysis) {
44 auto inserted = dependents.insert(X: {dependent, analysis});
45 (void)inserted;
46 DATAFLOW_DEBUG({
47 if (inserted) {
48 LDBG() << "Creating dependency between " << debugName << " of " << anchor
49 << "\nand " << debugName << " on " << *dependent;
50 }
51 });
52}
53
54void AnalysisState::dump() const { print(os&: llvm::errs()); }
55
56//===----------------------------------------------------------------------===//
57// ProgramPoint
58//===----------------------------------------------------------------------===//
59
60void ProgramPoint::print(raw_ostream &os) const {
61 if (isNull()) {
62 os << "<NULL POINT>";
63 return;
64 }
65 if (!isBlockStart()) {
66 os << "<after operation>:"
67 << OpWithFlags(getPrevOp(), OpPrintingFlags().skipRegions());
68 return;
69 }
70 if (!isBlockEnd()) {
71 os << "<before operation>:"
72 << OpWithFlags(getNextOp(), OpPrintingFlags().skipRegions());
73 return;
74 }
75 os << "<beginning of empty block>";
76}
77
78//===----------------------------------------------------------------------===//
79// LatticeAnchor
80//===----------------------------------------------------------------------===//
81
82void LatticeAnchor::print(raw_ostream &os) const {
83 if (isNull()) {
84 os << "<NULL POINT>";
85 return;
86 }
87 if (auto *latticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(Val: *this))
88 return latticeAnchor->print(os);
89 if (auto value = llvm::dyn_cast<Value>(Val: *this)) {
90 return value.print(os, flags: OpPrintingFlags().skipRegions());
91 }
92
93 return llvm::cast<ProgramPoint *>(Val: *this)->print(os);
94}
95
96Location LatticeAnchor::getLoc() const {
97 if (auto *latticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(Val: *this))
98 return latticeAnchor->getLoc();
99 if (auto value = llvm::dyn_cast<Value>(Val: *this))
100 return value.getLoc();
101
102 ProgramPoint *pp = llvm::cast<ProgramPoint *>(Val: *this);
103 if (!pp->isBlockStart())
104 return pp->getPrevOp()->getLoc();
105 return pp->getBlock()->getParent()->getLoc();
106}
107
108//===----------------------------------------------------------------------===//
109// DataFlowSolver
110//===----------------------------------------------------------------------===//
111
112LogicalResult DataFlowSolver::initializeAndRun(
113 Operation *top,
114 llvm::function_ref<bool(DataFlowAnalysis &)> analysisFilter) {
115 // Enable enqueue to the worklist.
116 isRunning = true;
117 llvm::scope_exit guard([&]() { isRunning = false; });
118
119 bool isInterprocedural = config.isInterprocedural();
120 llvm::scope_exit restoreInterprocedural(
121 [&]() { config.setInterprocedural(isInterprocedural); });
122 if (isInterprocedural && !top->hasTrait<OpTrait::SymbolTable>())
123 config.setInterprocedural(false);
124
125 auto shouldInitialize = [&](DataFlowAnalysis &analysis) {
126 return !analysisFilter || analysisFilter(analysis);
127 };
128
129 // Initialize equivalent lattice anchors.
130 for (DataFlowAnalysis &analysis : llvm::make_pointee_range(Range&: childAnalyses)) {
131 if (!shouldInitialize(analysis))
132 continue;
133 analysis.initializeEquivalentLatticeAnchor(top);
134 }
135
136 // Initialize the analyses.
137 for (DataFlowAnalysis &analysis : llvm::make_pointee_range(Range&: childAnalyses)) {
138 if (!shouldInitialize(analysis))
139 continue;
140 DATAFLOW_DEBUG(LDBG() << "Priming analysis: " << analysis.debugName);
141 if (failed(Result: analysis.initialize(top)))
142 return failure();
143 }
144
145 // Run the analysis until fixpoint.
146 // Iterate until all states are in some initialized state and the worklist
147 // is exhausted.
148 while (!worklist.empty()) {
149 auto [point, analysis] = dequeue();
150
151 DATAFLOW_DEBUG(LDBG() << "Invoking '" << analysis->debugName
152 << "' on: " << *point);
153 if (failed(Result: analysis->visit(point)))
154 return failure();
155 }
156
157 return success();
158}
159
160void DataFlowSolver::propagateIfChanged(AnalysisState *state,
161 ChangeResult changed) {
162 assert(isRunning &&
163 "DataFlowSolver is not running, should not use propagateIfChanged");
164 if (changed == ChangeResult::Change) {
165 DATAFLOW_DEBUG(LDBG() << "Propagating update to " << state->debugName
166 << " of " << state->anchor << "\n"
167 << "Value: " << *state);
168 state->onUpdate(solver: this);
169 }
170}
171
172//===----------------------------------------------------------------------===//
173// DataFlowAnalysis
174//===----------------------------------------------------------------------===//
175
176DataFlowAnalysis::~DataFlowAnalysis() = default;
177
178DataFlowAnalysis::DataFlowAnalysis(DataFlowSolver &solver) : solver(solver) {}
179
180void DataFlowAnalysis::addDependency(AnalysisState *state,
181 ProgramPoint *point) {
182 state->addDependency(dependent: point, analysis: this);
183}
184
185void DataFlowAnalysis::propagateIfChanged(AnalysisState *state,
186 ChangeResult changed) {
187 solver.propagateIfChanged(state, changed);
188}
189