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 | |
27 | using namespace mlir; |
28 | |
29 | //===----------------------------------------------------------------------===// |
30 | // GenericLatticeAnchor |
31 | //===----------------------------------------------------------------------===// |
32 | |
33 | GenericLatticeAnchor::~GenericLatticeAnchor() = default; |
34 | |
35 | //===----------------------------------------------------------------------===// |
36 | // AnalysisState |
37 | //===----------------------------------------------------------------------===// |
38 | |
39 | AnalysisState::~AnalysisState() = default; |
40 | |
41 | void 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 | |
54 | void AnalysisState::dump() const { print(os&: llvm::errs()); } |
55 | |
56 | //===----------------------------------------------------------------------===// |
57 | // ProgramPoint |
58 | //===----------------------------------------------------------------------===// |
59 | |
60 | void 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 | |
77 | void 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 | |
91 | Location 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 | |
107 | LogicalResult 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 | |
141 | void 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 | |
157 | DataFlowAnalysis::~DataFlowAnalysis() = default; |
158 | |
159 | DataFlowAnalysis::DataFlowAnalysis(DataFlowSolver &solver) : solver(solver) {} |
160 | |
161 | void DataFlowAnalysis::addDependency(AnalysisState *state, |
162 | ProgramPoint *point) { |
163 | state->addDependency(dependent: point, analysis: this); |
164 | } |
165 | |
166 | void DataFlowAnalysis::propagateIfChanged(AnalysisState *state, |
167 | ChangeResult changed) { |
168 | solver.propagateIfChanged(state, changed); |
169 | } |
170 | |