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/Value.h"
13#include "llvm/ADT/ScopeExit.h"
14#include "llvm/ADT/iterator.h"
15#include "llvm/Config/abi-breaking.h"
16#include "llvm/Support/Casting.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/raw_ostream.h"
19
20#define DEBUG_TYPE "dataflow"
21#if LLVM_ENABLE_ABI_BREAKING_CHECKS
22#define DATAFLOW_DEBUG(X) LLVM_DEBUG(X)
23#else
24#define DATAFLOW_DEBUG(X)
25#endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
26
27using namespace mlir;
28
29//===----------------------------------------------------------------------===//
30// GenericLatticeAnchor
31//===----------------------------------------------------------------------===//
32
33GenericLatticeAnchor::~GenericLatticeAnchor() = default;
34
35//===----------------------------------------------------------------------===//
36// AnalysisState
37//===----------------------------------------------------------------------===//
38
39AnalysisState::~AnalysisState() = default;
40
41void AnalysisState::addDependency(ProgramPoint *dependent,
42 DataFlowAnalysis *analysis) {
43 auto inserted = dependents.insert(X: {dependent, analysis});
44 (void)inserted;
45 DATAFLOW_DEBUG({
46 if (inserted) {
47 llvm::dbgs() << "Creating dependency between " << debugName << " of "
48 << anchor << "\nand " << debugName << " on " << dependent
49 << "\n";
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 return getPrevOp()->print(os, flags: OpPrintingFlags().skipRegions());
68 }
69 os << "<before operation>:";
70 return getNextOp()->print(os, flags: OpPrintingFlags().skipRegions());
71}
72
73//===----------------------------------------------------------------------===//
74// LatticeAnchor
75//===----------------------------------------------------------------------===//
76
77void LatticeAnchor::print(raw_ostream &os) const {
78 if (isNull()) {
79 os << "<NULL POINT>";
80 return;
81 }
82 if (auto *LatticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(Val: *this))
83 return LatticeAnchor->print(os);
84 if (auto value = llvm::dyn_cast<Value>(Val: *this)) {
85 return value.print(os, flags: OpPrintingFlags().skipRegions());
86 }
87
88 return llvm::cast<ProgramPoint *>(Val: *this)->print(os);
89}
90
91Location LatticeAnchor::getLoc() const {
92 if (auto *LatticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(Val: *this))
93 return LatticeAnchor->getLoc();
94 if (auto value = llvm::dyn_cast<Value>(Val: *this))
95 return value.getLoc();
96
97 ProgramPoint *pp = llvm::cast<ProgramPoint *>(Val: *this);
98 if (!pp->isBlockStart())
99 return pp->getPrevOp()->getLoc();
100 return pp->getBlock()->getParent()->getLoc();
101}
102
103//===----------------------------------------------------------------------===//
104// DataFlowSolver
105//===----------------------------------------------------------------------===//
106
107LogicalResult DataFlowSolver::initializeAndRun(Operation *top) {
108 // Enable enqueue to the worklist.
109 isRunning = true;
110 auto guard = llvm::make_scope_exit(F: [&]() { isRunning = false; });
111
112 // Initialize equivalent lattice anchors.
113 for (DataFlowAnalysis &analysis : llvm::make_pointee_range(Range&: childAnalyses)) {
114 analysis.initializeEquivalentLatticeAnchor(top);
115 }
116
117 // Initialize the analyses.
118 for (DataFlowAnalysis &analysis : llvm::make_pointee_range(Range&: childAnalyses)) {
119 DATAFLOW_DEBUG(llvm::dbgs()
120 << "Priming analysis: " << analysis.debugName << "\n");
121 if (failed(Result: analysis.initialize(top)))
122 return failure();
123 }
124
125 // Run the analysis until fixpoint.
126 // Iterate until all states are in some initialized state and the worklist
127 // is exhausted.
128 while (!worklist.empty()) {
129 auto [point, analysis] = worklist.front();
130 worklist.pop();
131
132 DATAFLOW_DEBUG(llvm::dbgs() << "Invoking '" << analysis->debugName
133 << "' on: " << point << "\n");
134 if (failed(Result: analysis->visit(point)))
135 return failure();
136 }
137
138 return success();
139}
140
141void DataFlowSolver::propagateIfChanged(AnalysisState *state,
142 ChangeResult changed) {
143 assert(isRunning &&
144 "DataFlowSolver is not running, should not use propagateIfChanged");
145 if (changed == ChangeResult::Change) {
146 DATAFLOW_DEBUG(llvm::dbgs() << "Propagating update to " << state->debugName
147 << " of " << state->anchor << "\n"
148 << "Value: " << *state << "\n");
149 state->onUpdate(solver: this);
150 }
151}
152
153//===----------------------------------------------------------------------===//
154// DataFlowAnalysis
155//===----------------------------------------------------------------------===//
156
157DataFlowAnalysis::~DataFlowAnalysis() = default;
158
159DataFlowAnalysis::DataFlowAnalysis(DataFlowSolver &solver) : solver(solver) {}
160
161void DataFlowAnalysis::addDependency(AnalysisState *state,
162 ProgramPoint *point) {
163 state->addDependency(dependent: point, analysis: this);
164}
165
166void DataFlowAnalysis::propagateIfChanged(AnalysisState *state,
167 ChangeResult changed) {
168 solver.propagateIfChanged(state, changed);
169}
170

source code of mlir/lib/Analysis/DataFlowFramework.cpp