1//===- TestDenseForwardDataFlowAnalysis.cpp -------------------------------===//
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// Implementation of tests passes exercising dense forward data flow 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/Interfaces/SideEffectInterfaces.h"
18#include "mlir/Pass/Pass.h"
19#include "mlir/Support/LLVM.h"
20#include "llvm/ADT/TypeSwitch.h"
21#include <optional>
22
23using namespace mlir;
24using namespace mlir::dataflow;
25using namespace mlir::dataflow::test;
26
27namespace {
28
29/// This lattice represents, for a given memory resource, the potential last
30/// operations that modified the resource.
31class LastModification : public AbstractDenseLattice, public AccessLatticeBase {
32public:
33 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(LastModification)
34
35 using AbstractDenseLattice::AbstractDenseLattice;
36
37 /// Join the last modifications.
38 ChangeResult join(const AbstractDenseLattice &lattice) override {
39 return AccessLatticeBase::merge(rhs: static_cast<AccessLatticeBase>(
40 static_cast<const LastModification &>(lattice)));
41 }
42
43 void print(raw_ostream &os) const override {
44 return AccessLatticeBase::print(os);
45 }
46};
47
48class LastModifiedAnalysis
49 : public DenseForwardDataFlowAnalysis<LastModification> {
50public:
51 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(LastModifiedAnalysis)
52
53 explicit LastModifiedAnalysis(DataFlowSolver &solver, bool assumeFuncWrites)
54 : DenseForwardDataFlowAnalysis(solver),
55 assumeFuncWrites(assumeFuncWrites) {}
56
57 /// Visit an operation. If the operation has no memory effects, then the state
58 /// is propagated with no change. If the operation allocates a resource, then
59 /// its reaching definitions is set to empty. If the operation writes to a
60 /// resource, then its reaching definition is set to the written value.
61 LogicalResult visitOperation(Operation *op, const LastModification &before,
62 LastModification *after) override;
63
64 void visitCallControlFlowTransfer(CallOpInterface call,
65 CallControlFlowAction action,
66 const LastModification &before,
67 LastModification *after) override;
68
69 void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch,
70 std::optional<unsigned> regionFrom,
71 std::optional<unsigned> regionTo,
72 const LastModification &before,
73 LastModification *after) override;
74
75 /// Visit an operation. If this analysis can confirm that lattice content
76 /// of lattice anchors around operation are necessarily identical, join
77 /// them into the same equivalent class.
78 void buildOperationEquivalentLatticeAnchor(Operation *op) override;
79
80 /// At an entry point, the last modifications of all memory resources are
81 /// unknown.
82 void setToEntryState(LastModification *lattice) override {
83 propagateIfChanged(state: lattice, changed: lattice->reset());
84 }
85
86private:
87 const bool assumeFuncWrites;
88};
89} // end anonymous namespace
90
91LogicalResult LastModifiedAnalysis::visitOperation(
92 Operation *op, const LastModification &before, LastModification *after) {
93 auto memory = dyn_cast<MemoryEffectOpInterface>(Val: op);
94 // If we can't reason about the memory effects, then conservatively assume we
95 // can't deduce anything about the last modifications.
96 if (!memory) {
97 setToEntryState(after);
98 return success();
99 }
100
101 SmallVector<MemoryEffects::EffectInstance> effects;
102 memory.getEffects(effects);
103
104 // First, check if all underlying values are already known. Otherwise, avoid
105 // propagating and stay in the "undefined" state to avoid incorrectly
106 // propagating values that may be overwritten later on as that could be
107 // problematic for convergence based on monotonicity of lattice updates.
108 SmallVector<Value> underlyingValues;
109 underlyingValues.reserve(N: effects.size());
110 for (const auto &effect : effects) {
111 Value value = effect.getValue();
112
113 // If we see an effect on anything other than a value, assume we can't
114 // deduce anything about the last modifications.
115 if (!value) {
116 setToEntryState(after);
117 return success();
118 }
119
120 // If we cannot find the underlying value, we shouldn't just propagate the
121 // effects through, return the pessimistic state.
122 std::optional<Value> underlyingValue =
123 UnderlyingValueAnalysis::getMostUnderlyingValue(
124 value, getUnderlyingValueFn: [&](Value value) {
125 return getOrCreateFor<UnderlyingValueLattice>(
126 dependent: getProgramPointAfter(op), anchor: value);
127 });
128
129 // If the underlying value is not yet known, don't propagate yet.
130 if (!underlyingValue)
131 return success();
132
133 underlyingValues.push_back(Elt: *underlyingValue);
134 }
135
136 // Update the state when all underlying values are known.
137 ChangeResult result = after->join(lattice: before);
138 for (const auto &[effect, value] : llvm::zip(t&: effects, u&: underlyingValues)) {
139 // If the underlying value is known to be unknown, set to fixpoint state.
140 if (!value) {
141 setToEntryState(after);
142 return success();
143 }
144
145 // Nothing to do for reads.
146 if (isa<MemoryEffects::Read>(Val: effect.getEffect()))
147 continue;
148
149 result |= after->set(value, op);
150 }
151 propagateIfChanged(state: after, changed: result);
152 return success();
153}
154
155void LastModifiedAnalysis::buildOperationEquivalentLatticeAnchor(
156 Operation *op) {
157 if (isMemoryEffectFree(op)) {
158 unionLatticeAnchors<LastModification>(anchor: getProgramPointBefore(op),
159 other: getProgramPointAfter(op));
160 }
161}
162
163void LastModifiedAnalysis::visitCallControlFlowTransfer(
164 CallOpInterface call, CallControlFlowAction action,
165 const LastModification &before, LastModification *after) {
166 if (action == CallControlFlowAction::ExternalCallee && assumeFuncWrites) {
167 SmallVector<Value> underlyingValues;
168 underlyingValues.reserve(N: call->getNumOperands());
169 for (Value operand : call.getArgOperands()) {
170 std::optional<Value> underlyingValue =
171 UnderlyingValueAnalysis::getMostUnderlyingValue(
172 value: operand, getUnderlyingValueFn: [&](Value value) {
173 return getOrCreateFor<UnderlyingValueLattice>(
174 dependent: getProgramPointAfter(op: call.getOperation()), anchor: value);
175 });
176 if (!underlyingValue)
177 return;
178 underlyingValues.push_back(Elt: *underlyingValue);
179 }
180
181 ChangeResult result = after->join(lattice: before);
182 for (Value operand : underlyingValues)
183 result |= after->set(value: operand, op: call);
184 return propagateIfChanged(state: after, changed: result);
185 }
186 auto testCallAndStore =
187 dyn_cast<::test::TestCallAndStoreOp>(call.getOperation());
188 if (testCallAndStore && ((action == CallControlFlowAction::EnterCallee &&
189 testCallAndStore.getStoreBeforeCall()) ||
190 (action == CallControlFlowAction::ExitCallee &&
191 !testCallAndStore.getStoreBeforeCall()))) {
192 (void)visitOperation(op: call, before, after);
193 return;
194 }
195 AbstractDenseForwardDataFlowAnalysis::visitCallControlFlowTransfer(
196 call, action, before, after);
197}
198
199void LastModifiedAnalysis::visitRegionBranchControlFlowTransfer(
200 RegionBranchOpInterface branch, std::optional<unsigned> regionFrom,
201 std::optional<unsigned> regionTo, const LastModification &before,
202 LastModification *after) {
203 auto defaultHandling = [&]() {
204 AbstractDenseForwardDataFlowAnalysis::visitRegionBranchControlFlowTransfer(
205 branch, regionFrom, regionTo, before, after);
206 };
207 TypeSwitch<Operation *>(branch.getOperation())
208 .Case<::test::TestStoreWithARegion, ::test::TestStoreWithALoopRegion>(
209 [=](auto storeWithRegion) {
210 if ((!regionTo && !storeWithRegion.getStoreBeforeRegion()) ||
211 (!regionFrom && storeWithRegion.getStoreBeforeRegion()))
212 (void)visitOperation(branch, before, after);
213 defaultHandling();
214 })
215 .Default([=](auto) { defaultHandling(); });
216}
217
218namespace {
219struct TestLastModifiedPass
220 : public PassWrapper<TestLastModifiedPass, OperationPass<>> {
221 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestLastModifiedPass)
222
223 TestLastModifiedPass() = default;
224 TestLastModifiedPass(const TestLastModifiedPass &other) : PassWrapper(other) {
225 interprocedural = other.interprocedural;
226 assumeFuncWrites = other.assumeFuncWrites;
227 }
228
229 StringRef getArgument() const override { return "test-last-modified"; }
230
231 Option<bool> interprocedural{
232 *this, "interprocedural", llvm::cl::init(Val: true),
233 llvm::cl::desc("perform interprocedural analysis")};
234 Option<bool> assumeFuncWrites{
235 *this, "assume-func-writes", llvm::cl::init(Val: false),
236 llvm::cl::desc(
237 "assume external functions have write effect on all arguments")};
238
239 void runOnOperation() override {
240 Operation *op = getOperation();
241
242 DataFlowSolver solver(DataFlowConfig().setInterprocedural(interprocedural));
243 loadBaselineAnalyses(solver);
244 solver.load<LastModifiedAnalysis>(args&: assumeFuncWrites);
245 solver.load<UnderlyingValueAnalysis>();
246 if (failed(Result: solver.initializeAndRun(top: op)))
247 return signalPassFailure();
248
249 raw_ostream &os = llvm::errs();
250
251 // Note that if the underlying value could not be computed or is unknown, we
252 // conservatively treat the result also unknown.
253 op->walk(callback: [&](Operation *op) {
254 auto tag = op->getDiscardableAttrOfType<StringAttr>(name: "tag");
255 if (!tag)
256 return;
257 os << "test_tag: " << tag.getValue() << ":\n";
258 const LastModification *lastMods =
259 solver.lookupState<LastModification>(anchor: solver.getProgramPointAfter(op));
260 if (!lastMods) {
261 // The lattice may not be computed for operations in unreachable code
262 // (e.g., private functions not called from anywhere in interprocedural
263 // analysis mode).
264 os << " - <not computed>\n";
265 return;
266 }
267 for (auto [index, operand] : llvm::enumerate(First: op->getOperands())) {
268 os << " operand #" << index << "\n";
269 std::optional<Value> underlyingValue =
270 UnderlyingValueAnalysis::getMostUnderlyingValue(
271 value: operand, getUnderlyingValueFn: [&](Value value) {
272 return solver.lookupState<UnderlyingValueLattice>(anchor: value);
273 });
274 if (!underlyingValue) {
275 os << " - <unknown>\n";
276 continue;
277 }
278 Value value = *underlyingValue;
279 assert(value && "expected an underlying value");
280 if (const AdjacentAccess *lastMod =
281 lastMods->getAdjacentAccess(value)) {
282 if (!lastMod->isKnown()) {
283 os << " - <unknown>\n";
284 } else {
285 for (Operation *lastModifier : lastMod->get()) {
286 if (auto tagName =
287 lastModifier->getDiscardableAttrOfType<StringAttr>(
288 name: "tag_name")) {
289 os << " - " << tagName.getValue() << "\n";
290 } else {
291 os << " - " << lastModifier->getName() << "\n";
292 }
293 }
294 }
295 } else {
296 os << " - <unknown>\n";
297 }
298 }
299 });
300 }
301};
302} // end anonymous namespace
303
304namespace mlir {
305namespace test {
306void registerTestLastModifiedPass() {
307 PassRegistration<TestLastModifiedPass>();
308}
309} // end namespace test
310} // end namespace mlir
311