1//===- TestDataFlowFramework.cpp - Test data-flow analysis framework ------===//
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/Dialect/Func/IR/FuncOps.h"
11#include "mlir/IR/Builders.h"
12#include "mlir/Pass/Pass.h"
13#include "llvm/ADT/DenseMap.h"
14#include <optional>
15
16using namespace mlir;
17
18namespace {
19constexpr char kTagAttrName[] = "tag";
20constexpr char kFooAttrName[] = "foo";
21constexpr char kFooStateAttrName[] = "foo_state";
22constexpr char kBarStateAttrName[] = "bar_state";
23
24/// This analysis state represents an integer that is OR'd with other states.
25class FooState : public AnalysisState {
26public:
27 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(FooState)
28
29 using AnalysisState::AnalysisState;
30
31 /// Returns true if the state is uninitialized.
32 bool isUninitialized() const { return !state; }
33
34 /// Print the integer value or "none" if uninitialized.
35 void print(raw_ostream &os) const override {
36 if (state)
37 os << *state;
38 else
39 os << "none";
40 }
41
42 /// Join the state with another. If either is uninitialized, take the
43 /// initialized value. Otherwise, OR the integer values.
44 ChangeResult join(const FooState &rhs) {
45 if (rhs.isUninitialized())
46 return ChangeResult::NoChange;
47 return join(value: *rhs.state);
48 }
49 ChangeResult join(uint64_t value) {
50 if (isUninitialized()) {
51 state = value;
52 return ChangeResult::Change;
53 }
54 uint64_t before = *state;
55 state = before | value;
56 return before == *state ? ChangeResult::NoChange : ChangeResult::Change;
57 }
58
59 /// Set the value of the state directly.
60 ChangeResult set(const FooState &rhs) {
61 if (state == rhs.state)
62 return ChangeResult::NoChange;
63 state = rhs.state;
64 return ChangeResult::Change;
65 }
66
67 /// Returns the integer value of the state.
68 uint64_t getValue() const { return *state; }
69
70private:
71 /// An optional integer value.
72 std::optional<uint64_t> state;
73};
74
75/// This analysis computes `FooState` across operations and control-flow edges.
76/// If an op specifies a `foo` integer attribute, the contained value is OR'd
77/// with the value before the operation.
78class FooAnalysis : public DataFlowAnalysis {
79public:
80 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(FooAnalysis)
81
82 using DataFlowAnalysis::DataFlowAnalysis;
83
84 static bool classof(const DataFlowAnalysis *a) {
85 return a->getTypeID() == TypeID::get<FooAnalysis>();
86 }
87
88 LogicalResult initialize(Operation *top) override;
89 LogicalResult visit(ProgramPoint *point) override;
90
91 unsigned lookupVisits(const Block *block) const;
92
93private:
94 void visitBlock(Block *block);
95 void visitOperation(Operation *op);
96
97 DenseMap<const Block *, unsigned> blockVisits; // including initial visit
98};
99
100/// This analysis state stores whether all previously observed `FooState`
101/// values at tagged program points along the CFG leading to the current point
102/// have not been positive multiples of 5. Once the state becomes false at some
103/// point, all later points reachable from it also remain false.
104class BarState : public AnalysisState {
105public:
106 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(BarState)
107
108 using AnalysisState::AnalysisState;
109
110 bool isUninitialized() const { return !state; }
111
112 void print(raw_ostream &os) const override {
113 if (!state) {
114 os << "none";
115 return;
116 }
117 os << (*state ? "true" : "false");
118 }
119
120 ChangeResult join(const BarState &rhs) {
121 if (rhs.isUninitialized())
122 return ChangeResult::NoChange;
123 return join(value: rhs.getValue());
124 }
125
126 ChangeResult join(bool value) {
127 if (isUninitialized()) {
128 state = value;
129 return ChangeResult::Change;
130 }
131 bool newValue = *state && value;
132 if (newValue == *state)
133 return ChangeResult::NoChange;
134 state = newValue;
135 return ChangeResult::Change;
136 }
137
138 bool getValue() const { return *state; }
139
140private:
141 std::optional<bool> state;
142};
143
144/// This analysis is intended to be loaded after `FooAnalysis` has converged.
145/// It records whether every observed `FooState` on or before a given tagged
146/// program point has not been a positive multiple of 5. Because the state only
147/// ever transitions from true to false, observing a transient positive
148/// divisible-by-5 `FooState` before `FooAnalysis` converges can permanently
149/// poison the result.
150class BarAnalysis : public DataFlowAnalysis {
151public:
152 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(BarAnalysis)
153
154 using DataFlowAnalysis::DataFlowAnalysis;
155
156 static bool classof(const DataFlowAnalysis *a) {
157 return a->getTypeID() == TypeID::get<BarAnalysis>();
158 }
159
160 LogicalResult initialize(Operation *top) override;
161 LogicalResult visit(ProgramPoint *point) override;
162
163private:
164 void visitBlock(Block *block);
165 void visitOperation(Operation *op);
166};
167
168struct TestFooAnalysisPass
169 : public PassWrapper<TestFooAnalysisPass, OperationPass<func::FuncOp>> {
170 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestFooAnalysisPass)
171
172 StringRef getArgument() const override { return "test-foo-analysis"; }
173
174 void runOnOperation() override;
175};
176
177struct TestStagedAnalysesPass
178 : public PassWrapper<TestStagedAnalysesPass, OperationPass<func::FuncOp>> {
179 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestStagedAnalysesPass)
180
181 StringRef getArgument() const override { return "test-staged-analyses"; }
182
183 void runOnOperation() override;
184};
185} // namespace
186
187LogicalResult FooAnalysis::initialize(Operation *top) {
188 if (top->getNumRegions() != 1)
189 return top->emitError(message: "expected a single region top-level op");
190
191 if (top->getRegion(index: 0).getBlocks().empty())
192 return top->emitError(message: "expected at least one block in the region");
193
194 // Initialize the top-level state.
195 (void)getOrCreate<FooState>(anchor: getProgramPointBefore(block: &top->getRegion(index: 0).front()))
196 ->join(value: 0);
197
198 // Visit all nested blocks and operations.
199 for (Block &block : top->getRegion(index: 0)) {
200 visitBlock(block: &block);
201 for (Operation &op : block) {
202 if (op.getNumRegions())
203 return op.emitError(message: "unexpected op with regions");
204 visitOperation(op: &op);
205 }
206 }
207 return success();
208}
209
210LogicalResult FooAnalysis::visit(ProgramPoint *point) {
211 if (!point->isBlockStart())
212 visitOperation(op: point->getPrevOp());
213 else
214 visitBlock(block: point->getBlock());
215 return success();
216}
217
218unsigned FooAnalysis::lookupVisits(const Block *const block) const {
219 return blockVisits.lookup(Val: block);
220}
221
222void FooAnalysis::visitBlock(Block *block) {
223 ++blockVisits[block];
224 if (block->isEntryBlock()) {
225 // This is the initial state. Let the framework default-initialize it.
226 return;
227 }
228 ProgramPoint *point = getProgramPointBefore(block);
229 FooState *state = getOrCreate<FooState>(anchor: point);
230 ChangeResult result = ChangeResult::NoChange;
231 for (Block *pred : block->getPredecessors()) {
232 // Join the state at the terminators of all predecessors.
233 const FooState *predState = getOrCreateFor<FooState>(
234 dependent: point, anchor: getProgramPointAfter(op: pred->getTerminator()));
235 result |= state->join(rhs: *predState);
236 }
237 propagateIfChanged(state, changed: result);
238}
239
240void FooAnalysis::visitOperation(Operation *op) {
241 ProgramPoint *point = getProgramPointAfter(op);
242 FooState *state = getOrCreate<FooState>(anchor: point);
243 ChangeResult result = ChangeResult::NoChange;
244
245 // Copy the state across the operation.
246 const FooState *prevState;
247 prevState = getOrCreateFor<FooState>(dependent: point, anchor: getProgramPointBefore(op));
248 result |= state->set(*prevState);
249
250 // Modify the state with the attribute, if specified.
251 if (auto attr = op->getDiscardableAttrOfType<IntegerAttr>(name: kFooAttrName)) {
252 uint64_t value = attr.getType().isUnsignedInteger()
253 ? attr.getUInt()
254 : static_cast<uint64_t>(attr.getInt());
255 result |= state->join(value);
256 }
257 propagateIfChanged(state, changed: result);
258}
259
260LogicalResult BarAnalysis::initialize(Operation *top) {
261 if (top->getNumRegions() != 1)
262 return top->emitError(message: "expected a single region top-level op");
263
264 if (top->getRegion(index: 0).getBlocks().empty())
265 return top->emitError(message: "expected at least one block in the region");
266
267 // Seed the entry state to true before observing any `FooState`.
268 (void)getOrCreate<BarState>(anchor: getProgramPointBefore(block: &top->getRegion(index: 0).front()))
269 ->join(value: true);
270
271 for (Block &block : top->getRegion(index: 0)) {
272 visitBlock(block: &block);
273 for (Operation &op : block) {
274 if (op.getNumRegions())
275 return op.emitError(message: "unexpected op with regions");
276 visitOperation(op: &op);
277 }
278 }
279 return success();
280}
281
282LogicalResult BarAnalysis::visit(ProgramPoint *point) {
283 if (!point->isBlockStart())
284 visitOperation(op: point->getPrevOp());
285 else
286 visitBlock(block: point->getBlock());
287 return success();
288}
289
290void BarAnalysis::visitBlock(Block *block) {
291 if (block->isEntryBlock())
292 return;
293
294 ProgramPoint *point = getProgramPointBefore(block);
295 BarState *state = getOrCreate<BarState>(anchor: point);
296 ChangeResult result = ChangeResult::NoChange;
297 for (Block *pred : block->getPredecessors()) {
298 const BarState *predState = getOrCreateFor<BarState>(
299 dependent: point, anchor: getProgramPointAfter(op: pred->getTerminator()));
300 result |= state->join(rhs: *predState);
301 }
302 propagateIfChanged(state, changed: result);
303}
304
305void BarAnalysis::visitOperation(Operation *op) {
306 ProgramPoint *point = getProgramPointAfter(op);
307 BarState *state = getOrCreate<BarState>(anchor: point);
308 ChangeResult result = ChangeResult::NoChange;
309
310 const BarState *prevState =
311 getOrCreateFor<BarState>(dependent: point, anchor: getProgramPointBefore(op));
312 result |= state->join(rhs: *prevState);
313
314 if (op->hasDiscardableAttr(name: kTagAttrName)) {
315 const FooState *fooState = getOrCreateFor<FooState>(dependent: point, anchor: point);
316 if (fooState->isUninitialized())
317 return;
318 const auto value = fooState->getValue();
319 result |= state->join(value: value > 0 && value % 5 != 0);
320 }
321 propagateIfChanged(state, changed: result);
322}
323
324void TestFooAnalysisPass::runOnOperation() {
325 func::FuncOp func = getOperation();
326 DataFlowSolver solver;
327 auto &analysis = *solver.load<FooAnalysis>();
328 if (failed(Result: solver.initializeAndRun(top: func)))
329 return signalPassFailure();
330
331 raw_ostream &os = llvm::errs();
332 os << "function: @" << func.getSymName() << "\n";
333
334 func.walk(callback: [&](Operation *op) {
335 auto tag = op->getDiscardableAttrOfType<StringAttr>(name: kTagAttrName);
336 if (!tag)
337 return;
338 if (auto *const block = op->getBlock(); &block->front() == op)
339 os << tag.getValue() << " block visits -> "
340 << analysis.lookupVisits(block) << "\n";
341 const FooState *state =
342 solver.lookupState<FooState>(anchor: solver.getProgramPointAfter(op));
343 assert(state && !state->isUninitialized());
344 os << tag.getValue() << " -> " << state->getValue() << "\n";
345 });
346}
347
348void TestStagedAnalysesPass::runOnOperation() {
349 func::FuncOp func = getOperation();
350 Builder builder(func.getContext());
351
352 DataFlowSolver solver;
353 solver.load<FooAnalysis>();
354 if (failed(Result: solver.initializeAndRun(top: func)))
355 return signalPassFailure();
356 solver.load<BarAnalysis>();
357 if (failed(Result: solver.initializeAndRun(top: func, analysisFilter: llvm::IsaPred<BarAnalysis>)))
358 return signalPassFailure();
359
360 func.walk(callback: [&](Operation *op) {
361 if (!op->hasDiscardableAttr(name: kTagAttrName))
362 return;
363
364 ProgramPoint *point = solver.getProgramPointAfter(op);
365 const FooState *fooState = solver.lookupState<FooState>(anchor: point);
366 const BarState *barState = solver.lookupState<BarState>(anchor: point);
367 assert(fooState && !fooState->isUninitialized());
368 assert(barState && !barState->isUninitialized());
369
370 op->setDiscardableAttr(name: kFooStateAttrName,
371 value: builder.getI64IntegerAttr(value: fooState->getValue()));
372 op->setDiscardableAttr(name: kBarStateAttrName,
373 value: builder.getBoolAttr(value: barState->getValue()));
374 });
375}
376
377namespace mlir {
378namespace test {
379void registerTestFooAnalysisPass() { PassRegistration<TestFooAnalysisPass>(); }
380void registerTestStagedAnalysesPass() {
381 PassRegistration<TestStagedAnalysesPass>();
382}
383} // namespace test
384} // namespace mlir
385