1//===- TestDenseBackwardDataFlowAnalysis.cpp - Test pass ------------------===//
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// Test pass for backward dense dataflow analysis.
10//
11//===----------------------------------------------------------------------===//
12
13#include "TestDenseDataFlowAnalysis.h"
14#include "TestOpsInterfaces.h"
15#include "mlir/Analysis/DataFlow/DenseAnalysis.h"
16#include "mlir/Analysis/DataFlow/Utils.h"
17#include "mlir/Analysis/DataFlowFramework.h"
18#include "mlir/IR/Builders.h"
19#include "mlir/IR/SymbolTable.h"
20#include "mlir/Interfaces/CallInterfaces.h"
21#include "mlir/Interfaces/ControlFlowInterfaces.h"
22#include "mlir/Interfaces/SideEffectInterfaces.h"
23#include "mlir/Pass/Pass.h"
24#include "mlir/Support/TypeID.h"
25#include "llvm/Support/DebugLog.h"
26#include "llvm/Support/raw_ostream.h"
27
28using namespace mlir;
29using namespace mlir::dataflow;
30using namespace mlir::dataflow::test;
31
32#define DEBUG_TYPE "test-next-access"
33
34namespace {
35
36class NextAccess : public AbstractDenseLattice, public AccessLatticeBase {
37public:
38 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(NextAccess)
39
40 using dataflow::AbstractDenseLattice::AbstractDenseLattice;
41
42 ChangeResult meet(const AbstractDenseLattice &lattice) override {
43 return AccessLatticeBase::merge(rhs: static_cast<AccessLatticeBase>(
44 static_cast<const NextAccess &>(lattice)));
45 }
46
47 void print(raw_ostream &os) const override {
48 return AccessLatticeBase::print(os);
49 }
50};
51
52class NextAccessAnalysis : public DenseBackwardDataFlowAnalysis<NextAccess> {
53public:
54 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(NextAccessAnalysis)
55
56 NextAccessAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable,
57 bool assumeFuncReads = false)
58 : DenseBackwardDataFlowAnalysis(solver, symbolTable),
59 assumeFuncReads(assumeFuncReads) {}
60
61 LogicalResult visitOperation(Operation *op, const NextAccess &after,
62 NextAccess *before) override;
63
64 void visitCallControlFlowTransfer(CallOpInterface call,
65 CallControlFlowAction action,
66 const NextAccess &after,
67 NextAccess *before) override;
68
69 void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch,
70 RegionBranchPoint regionFrom,
71 RegionSuccessor regionTo,
72 const NextAccess &after,
73 NextAccess *before) override;
74
75 // TODO: this isn't ideal for the analysis. When there is no next access, it
76 // means "we don't know what the next access is" rather than "there is no next
77 // access". But it's unclear how to differentiate the two cases...
78 void setToExitState(NextAccess *lattice) override {
79 LDBG() << "setToExitState: setting lattice to unknown state";
80 propagateIfChanged(state: lattice, changed: lattice->setKnownToUnknown());
81 }
82
83 /// Visit an operation. If this analysis can confirm that lattice content
84 /// of lattice anchors around operation are necessarily identical, join
85 /// them into the same equivalent class.
86 void buildOperationEquivalentLatticeAnchor(Operation *op) override;
87
88 const bool assumeFuncReads;
89};
90} // namespace
91
92LogicalResult NextAccessAnalysis::visitOperation(Operation *op,
93 const NextAccess &after,
94 NextAccess *before) {
95 LDBG() << "visitOperation: "
96 << OpWithFlags(op, OpPrintingFlags().skipRegions());
97 LDBG() << " after state: " << after;
98 LDBG() << " before state: " << *before;
99
100 auto memory = dyn_cast<MemoryEffectOpInterface>(Val: op);
101 // If we can't reason about the memory effects, conservatively assume we can't
102 // say anything about the next access.
103 if (!memory) {
104 LDBG() << " No memory effect interface, setting to exit state";
105 setToExitState(before);
106 return success();
107 }
108
109 SmallVector<MemoryEffects::EffectInstance> effects;
110 memory.getEffects(effects);
111 LDBG() << " Found " << effects.size() << " memory effects";
112
113 // First, check if all underlying values are already known. Otherwise, avoid
114 // propagating and stay in the "undefined" state to avoid incorrectly
115 // propagating values that may be overwritten later on as that could be
116 // problematic for convergence based on monotonicity of lattice updates.
117 SmallVector<Value> underlyingValues;
118 underlyingValues.reserve(N: effects.size());
119 for (const MemoryEffects::EffectInstance &effect : effects) {
120 Value value = effect.getValue();
121
122 // Effects with unspecified value are treated conservatively and we cannot
123 // assume anything about the next access.
124 if (!value) {
125 LDBG() << " Effect has unspecified value, setting to exit state";
126 setToExitState(before);
127 return success();
128 }
129
130 // If cannot find the most underlying value, we cannot assume anything about
131 // the next accesses.
132 std::optional<Value> underlyingValue =
133 UnderlyingValueAnalysis::getMostUnderlyingValue(
134 value, getUnderlyingValueFn: [&](Value value) {
135 return getOrCreateFor<UnderlyingValueLattice>(
136 dependent: getProgramPointBefore(op), anchor: value);
137 });
138
139 // If the underlying value is not known yet, don't propagate.
140 if (!underlyingValue) {
141 LDBG() << " Underlying value not known for " << value
142 << ", skipping propagation";
143 return success();
144 }
145
146 LDBG() << " Found underlying value " << *underlyingValue << " for "
147 << value;
148 underlyingValues.push_back(Elt: *underlyingValue);
149 }
150
151 // Update the state if all underlying values are known.
152 LDBG() << " All underlying values known, updating state";
153 ChangeResult result = before->meet(lattice: after);
154 for (const auto &[effect, value] : llvm::zip(t&: effects, u&: underlyingValues)) {
155 // If the underlying value is known to be unknown, set to fixpoint.
156 if (!value) {
157 LDBG() << " Underlying value is unknown, setting to exit state";
158 setToExitState(before);
159 return success();
160 }
161
162 LDBG() << " Setting next access for value " << value << " to operation "
163 << OpWithFlags(op, OpPrintingFlags().skipRegions());
164 result |= before->set(value, op);
165 }
166 LDBG() << " Final result: "
167 << (result == ChangeResult::Change ? "changed" : "no change");
168 propagateIfChanged(state: before, changed: result);
169 return success();
170}
171
172void NextAccessAnalysis::buildOperationEquivalentLatticeAnchor(Operation *op) {
173 LDBG() << "buildOperationEquivalentLatticeAnchor: "
174 << OpWithFlags(op, OpPrintingFlags().skipRegions());
175 if (isMemoryEffectFree(op)) {
176 LDBG() << " Operation is memory effect free, unioning lattice anchors";
177 unionLatticeAnchors<NextAccess>(anchor: getProgramPointBefore(op),
178 other: getProgramPointAfter(op));
179 } else {
180 LDBG() << " Operation has memory effects, not unioning lattice anchors";
181 }
182}
183
184void NextAccessAnalysis::visitCallControlFlowTransfer(
185 CallOpInterface call, CallControlFlowAction action, const NextAccess &after,
186 NextAccess *before) {
187 LDBG() << "visitCallControlFlowTransfer: "
188 << OpWithFlags(call.getOperation(), OpPrintingFlags().skipRegions());
189 LDBG() << " action: "
190 << (action == CallControlFlowAction::ExternalCallee ? "ExternalCallee"
191 : action == CallControlFlowAction::EnterCallee ? "EnterCallee"
192 : "ExitCallee");
193 LDBG() << " assumeFuncReads: " << assumeFuncReads;
194
195 if (action == CallControlFlowAction::ExternalCallee && assumeFuncReads) {
196 LDBG() << " Handling external callee with assumed function reads";
197 SmallVector<Value> underlyingValues;
198 underlyingValues.reserve(N: call->getNumOperands());
199 for (Value operand : call.getArgOperands()) {
200 std::optional<Value> underlyingValue =
201 UnderlyingValueAnalysis::getMostUnderlyingValue(
202 value: operand, getUnderlyingValueFn: [&](Value value) {
203 return getOrCreateFor<UnderlyingValueLattice>(
204 dependent: getProgramPointBefore(op: call.getOperation()), anchor: value);
205 });
206 if (!underlyingValue) {
207 LDBG() << " Underlying value not known for operand " << operand
208 << ", returning";
209 return;
210 }
211 LDBG() << " Found underlying value " << *underlyingValue
212 << " for operand " << operand;
213 underlyingValues.push_back(Elt: *underlyingValue);
214 }
215
216 LDBG() << " Setting next access for " << underlyingValues.size()
217 << " operands";
218 ChangeResult result = before->meet(lattice: after);
219 for (Value operand : underlyingValues) {
220 LDBG() << " Setting next access for operand " << operand << " to call "
221 << call;
222 result |= before->set(value: operand, op: call);
223 }
224 LDBG() << " Call control flow result: "
225 << (result == ChangeResult::Change ? "changed" : "no change");
226 return propagateIfChanged(state: before, changed: result);
227 }
228 auto testCallAndStore =
229 dyn_cast<::test::TestCallAndStoreOp>(call.getOperation());
230 if (testCallAndStore && ((action == CallControlFlowAction::EnterCallee &&
231 testCallAndStore.getStoreBeforeCall()) ||
232 (action == CallControlFlowAction::ExitCallee &&
233 !testCallAndStore.getStoreBeforeCall()))) {
234 LDBG() << " Handling TestCallAndStoreOp with special logic";
235 (void)visitOperation(op: call, after, before);
236 } else {
237 LDBG() << " Using default call control flow transfer logic";
238 AbstractDenseBackwardDataFlowAnalysis::visitCallControlFlowTransfer(
239 call, action, after, before);
240 }
241}
242
243void NextAccessAnalysis::visitRegionBranchControlFlowTransfer(
244 RegionBranchOpInterface branch, RegionBranchPoint regionFrom,
245 RegionSuccessor regionTo, const NextAccess &after, NextAccess *before) {
246 LDBG() << "visitRegionBranchControlFlowTransfer: "
247 << OpWithFlags(branch.getOperation(), OpPrintingFlags().skipRegions());
248 LDBG() << " regionFrom: " << (regionFrom.isParent() ? "parent" : "region");
249 LDBG() << " regionTo: " << (regionTo.isOperation() ? "operation" : "region");
250
251 auto testStoreWithARegion =
252 dyn_cast<::test::TestStoreWithARegion>(branch.getOperation());
253
254 if (testStoreWithARegion && ((regionTo.isOperation() &&
255 !testStoreWithARegion.getStoreBeforeRegion()) ||
256 (regionFrom.isParent() &&
257 testStoreWithARegion.getStoreBeforeRegion()))) {
258 LDBG() << " Handling TestStoreWithARegion with special logic";
259 (void)visitOperation(op: branch, after: static_cast<const NextAccess &>(after),
260 before: static_cast<NextAccess *>(before));
261 } else {
262 LDBG() << " Using default region branch control flow transfer logic";
263 propagateIfChanged(state: before, changed: before->meet(lattice: after));
264 }
265}
266
267namespace {
268struct TestNextAccessPass
269 : public PassWrapper<TestNextAccessPass, OperationPass<>> {
270 TestNextAccessPass() = default;
271 TestNextAccessPass(const TestNextAccessPass &other) : PassWrapper(other) {
272 interprocedural = other.interprocedural;
273 assumeFuncReads = other.assumeFuncReads;
274 }
275
276 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestNextAccessPass)
277
278 StringRef getArgument() const override { return "test-next-access"; }
279
280 Option<bool> interprocedural{
281 *this, "interprocedural", llvm::cl::init(Val: true),
282 llvm::cl::desc("perform interprocedural analysis")};
283 Option<bool> assumeFuncReads{
284 *this, "assume-func-reads", llvm::cl::init(Val: false),
285 llvm::cl::desc(
286 "assume external functions have read effect on all arguments")};
287
288 static constexpr llvm::StringLiteral kTagAttrName = "name";
289 static constexpr llvm::StringLiteral kNextAccessAttrName = "next_access";
290 static constexpr llvm::StringLiteral kAtEntryPointAttrName =
291 "next_at_entry_point";
292
293 static Attribute makeNextAccessAttribute(Operation *op,
294 const DataFlowSolver &solver,
295 const NextAccess *nextAccess) {
296 if (!nextAccess)
297 return StringAttr::get(context: op->getContext(), bytes: "not computed");
298
299 // Note that if the underlying value could not be computed or is unknown, we
300 // conservatively treat the result also unknown.
301 SmallVector<Attribute> attrs;
302 for (Value operand : op->getOperands()) {
303 std::optional<Value> underlyingValue =
304 UnderlyingValueAnalysis::getMostUnderlyingValue(
305 value: operand, getUnderlyingValueFn: [&](Value value) {
306 return solver.lookupState<UnderlyingValueLattice>(anchor: value);
307 });
308 if (!underlyingValue) {
309 attrs.push_back(Elt: StringAttr::get(context: op->getContext(), bytes: "unknown"));
310 continue;
311 }
312 Value value = *underlyingValue;
313 const AdjacentAccess *nextAcc = nextAccess->getAdjacentAccess(value);
314 if (!nextAcc || !nextAcc->isKnown()) {
315 attrs.push_back(Elt: StringAttr::get(context: op->getContext(), bytes: "unknown"));
316 continue;
317 }
318
319 SmallVector<Attribute> innerAttrs;
320 innerAttrs.reserve(N: nextAcc->get().size());
321 for (Operation *nextAccOp : nextAcc->get()) {
322 if (auto nextAccTag =
323 nextAccOp->getDiscardableAttrOfType<StringAttr>(name: kTagAttrName)) {
324 innerAttrs.push_back(Elt: nextAccTag);
325 continue;
326 }
327 std::string repr;
328 llvm::raw_string_ostream os(repr);
329 nextAccOp->print(os);
330 innerAttrs.push_back(Elt: StringAttr::get(context: op->getContext(), bytes: os.str()));
331 }
332 attrs.push_back(Elt: ArrayAttr::get(context: op->getContext(), value: innerAttrs));
333 }
334 return ArrayAttr::get(context: op->getContext(), value: attrs);
335 }
336
337 void runOnOperation() override {
338 Operation *op = getOperation();
339 LDBG() << "runOnOperation: Starting test-next-access pass on "
340 << OpWithFlags(op, OpPrintingFlags().skipRegions());
341 LDBG() << " interprocedural: " << interprocedural;
342 LDBG() << " assumeFuncReads: " << assumeFuncReads;
343
344 SymbolTableCollection symbolTable;
345
346 auto config = DataFlowConfig().setInterprocedural(interprocedural);
347 DataFlowSolver solver(config);
348 loadBaselineAnalyses(solver);
349 solver.load<NextAccessAnalysis>(args&: symbolTable, args&: assumeFuncReads);
350 solver.load<UnderlyingValueAnalysis>();
351 LDBG() << " Initializing and running dataflow solver";
352 if (failed(Result: solver.initializeAndRun(top: op))) {
353 emitError(loc: op->getLoc(), message: "dataflow solver failed");
354 return signalPassFailure();
355 }
356 LDBG() << " Dataflow solver completed successfully";
357 LDBG() << " Walking operations to set next access attributes";
358 op->walk(callback: [&](Operation *op) {
359 auto tag = op->getDiscardableAttrOfType<StringAttr>(name: kTagAttrName);
360 if (!tag)
361 return;
362
363 LDBG() << " Processing tagged operation: "
364 << OpWithFlags(op, OpPrintingFlags().skipRegions());
365 const NextAccess *nextAccess =
366 solver.lookupState<NextAccess>(anchor: solver.getProgramPointAfter(op));
367 op->setDiscardableAttr(name: kNextAccessAttrName,
368 value: makeNextAccessAttribute(op, solver, nextAccess));
369
370 auto iface = dyn_cast<RegionBranchOpInterface>(Val: op);
371 if (!iface)
372 return;
373
374 SmallVector<Attribute> entryPointNextAccess;
375 SmallVector<RegionSuccessor> regionSuccessors;
376 iface.getSuccessorRegions(point: RegionBranchPoint::parent(), regions&: regionSuccessors);
377 for (const RegionSuccessor &successor : regionSuccessors) {
378 if (successor.isOperation() || successor.getSuccessor()->empty())
379 continue;
380 Block &successorBlock = successor.getSuccessor()->front();
381 ProgramPoint *successorPoint =
382 solver.getProgramPointBefore(block: &successorBlock);
383 entryPointNextAccess.push_back(Elt: makeNextAccessAttribute(
384 op, solver, nextAccess: solver.lookupState<NextAccess>(anchor: successorPoint)));
385 }
386 op->setDiscardableAttr(
387 name: kAtEntryPointAttrName,
388 value: ArrayAttr::get(context: op->getContext(), value: entryPointNextAccess));
389 });
390 }
391};
392} // namespace
393
394namespace mlir::test {
395void registerTestNextAccessPass() { PassRegistration<TestNextAccessPass>(); }
396} // namespace mlir::test
397