1 | //===- DenseAnalysis.cpp - Dense 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/DataFlow/DenseAnalysis.h" |
10 | #include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h" |
11 | #include "mlir/Analysis/DataFlowFramework.h" |
12 | #include "mlir/IR/Block.h" |
13 | #include "mlir/IR/OpDefinition.h" |
14 | #include "mlir/IR/Operation.h" |
15 | #include "mlir/IR/Region.h" |
16 | #include "mlir/Interfaces/CallInterfaces.h" |
17 | #include "mlir/Interfaces/ControlFlowInterfaces.h" |
18 | #include "mlir/Support/LLVM.h" |
19 | #include "llvm/ADT/STLExtras.h" |
20 | #include "llvm/Support/Casting.h" |
21 | #include <cassert> |
22 | #include <optional> |
23 | |
24 | using namespace mlir; |
25 | using namespace mlir::dataflow; |
26 | |
27 | //===----------------------------------------------------------------------===// |
28 | // AbstractDenseForwardDataFlowAnalysis |
29 | //===----------------------------------------------------------------------===// |
30 | |
31 | void AbstractDenseForwardDataFlowAnalysis::initializeEquivalentLatticeAnchor( |
32 | Operation *top) { |
33 | top->walk(callback: [&](Operation *op) { |
34 | if (isa<RegionBranchOpInterface, CallOpInterface>(Val: op)) |
35 | return; |
36 | buildOperationEquivalentLatticeAnchor(op); |
37 | }); |
38 | } |
39 | |
40 | LogicalResult AbstractDenseForwardDataFlowAnalysis::initialize(Operation *top) { |
41 | // Visit every operation and block. |
42 | if (failed(Result: processOperation(op: top))) |
43 | return failure(); |
44 | |
45 | for (Region ®ion : top->getRegions()) { |
46 | for (Block &block : region) { |
47 | visitBlock(block: &block); |
48 | for (Operation &op : block) |
49 | if (failed(Result: initialize(top: &op))) |
50 | return failure(); |
51 | } |
52 | } |
53 | return success(); |
54 | } |
55 | |
56 | LogicalResult AbstractDenseForwardDataFlowAnalysis::visit(ProgramPoint *point) { |
57 | if (!point->isBlockStart()) |
58 | return processOperation(op: point->getPrevOp()); |
59 | visitBlock(block: point->getBlock()); |
60 | return success(); |
61 | } |
62 | |
63 | void AbstractDenseForwardDataFlowAnalysis::visitCallOperation( |
64 | CallOpInterface call, const AbstractDenseLattice &before, |
65 | AbstractDenseLattice *after) { |
66 | // Allow for customizing the behavior of calls to external symbols, including |
67 | // when the analysis is explicitly marked as non-interprocedural. |
68 | auto callable = |
69 | dyn_cast_if_present<CallableOpInterface>(call.resolveCallable()); |
70 | if (!getSolverConfig().isInterprocedural() || |
71 | (callable && !callable.getCallableRegion())) { |
72 | return visitCallControlFlowTransfer( |
73 | call: call, action: CallControlFlowAction::ExternalCallee, before, after); |
74 | } |
75 | |
76 | const auto *predecessors = getOrCreateFor<PredecessorState>( |
77 | getProgramPointAfter(call.getOperation()), getProgramPointAfter(call)); |
78 | // Otherwise, if not all return sites are known, then conservatively assume we |
79 | // can't reason about the data-flow. |
80 | if (!predecessors->allPredecessorsKnown()) |
81 | return setToEntryState(after); |
82 | |
83 | for (Operation *predecessor : predecessors->getKnownPredecessors()) { |
84 | // Get the lattices at callee return: |
85 | // |
86 | // func.func @callee() { |
87 | // ... |
88 | // return // predecessor |
89 | // // latticeAtCalleeReturn |
90 | // } |
91 | // func.func @caller() { |
92 | // ... |
93 | // call @callee |
94 | // // latticeAfterCall |
95 | // ... |
96 | // } |
97 | AbstractDenseLattice *latticeAfterCall = after; |
98 | const AbstractDenseLattice *latticeAtCalleeReturn = |
99 | getLatticeFor(getProgramPointAfter(call.getOperation()), |
100 | getProgramPointAfter(predecessor)); |
101 | visitCallControlFlowTransfer(call, CallControlFlowAction::ExitCallee, |
102 | *latticeAtCalleeReturn, latticeAfterCall); |
103 | } |
104 | } |
105 | |
106 | LogicalResult |
107 | AbstractDenseForwardDataFlowAnalysis::processOperation(Operation *op) { |
108 | ProgramPoint *point = getProgramPointAfter(op); |
109 | // If the containing block is not executable, bail out. |
110 | if (op->getBlock() != nullptr && |
111 | !getOrCreateFor<Executable>(dependent: point, anchor: getProgramPointBefore(block: op->getBlock())) |
112 | ->isLive()) |
113 | return success(); |
114 | |
115 | // Get the dense lattice to update. |
116 | AbstractDenseLattice *after = getLattice(anchor: point); |
117 | |
118 | // Get the dense state before the execution of the op. |
119 | const AbstractDenseLattice *before = |
120 | getLatticeFor(dependent: point, anchor: getProgramPointBefore(op)); |
121 | |
122 | // If this op implements region control-flow, then control-flow dictates its |
123 | // transfer function. |
124 | if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) { |
125 | visitRegionBranchOperation(point, branch: branch, after); |
126 | return success(); |
127 | } |
128 | |
129 | // If this is a call operation, then join its lattices across known return |
130 | // sites. |
131 | if (auto call = dyn_cast<CallOpInterface>(op)) { |
132 | visitCallOperation(call: call, before: *before, after); |
133 | return success(); |
134 | } |
135 | |
136 | // Invoke the operation transfer function. |
137 | return visitOperationImpl(op, before: *before, after); |
138 | } |
139 | |
140 | void AbstractDenseForwardDataFlowAnalysis::visitBlock(Block *block) { |
141 | // If the block is not executable, bail out. |
142 | ProgramPoint *point = getProgramPointBefore(block); |
143 | if (!getOrCreateFor<Executable>(dependent: point, anchor: point)->isLive()) |
144 | return; |
145 | |
146 | // Get the dense lattice to update. |
147 | AbstractDenseLattice *after = getLattice(anchor: point); |
148 | |
149 | // The dense lattices of entry blocks are set by region control-flow or the |
150 | // callgraph. |
151 | if (block->isEntryBlock()) { |
152 | // Check if this block is the entry block of a callable region. |
153 | auto callable = dyn_cast<CallableOpInterface>(block->getParentOp()); |
154 | if (callable && callable.getCallableRegion() == block->getParent()) { |
155 | const auto *callsites = getOrCreateFor<PredecessorState>( |
156 | point, getProgramPointAfter(callable)); |
157 | // If not all callsites are known, conservatively mark all lattices as |
158 | // having reached their pessimistic fixpoints. Do the same if |
159 | // interprocedural analysis is not enabled. |
160 | if (!callsites->allPredecessorsKnown() || |
161 | !getSolverConfig().isInterprocedural()) |
162 | return setToEntryState(after); |
163 | for (Operation *callsite : callsites->getKnownPredecessors()) { |
164 | // Get the dense lattice before the callsite. |
165 | const AbstractDenseLattice *before; |
166 | before = getLatticeFor(point, getProgramPointBefore(callsite)); |
167 | |
168 | visitCallControlFlowTransfer(cast<CallOpInterface>(callsite), |
169 | CallControlFlowAction::EnterCallee, |
170 | *before, after); |
171 | } |
172 | return; |
173 | } |
174 | |
175 | // Check if we can reason about the control-flow. |
176 | if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp())) |
177 | return visitRegionBranchOperation(point, branch: branch, after); |
178 | |
179 | // Otherwise, we can't reason about the data-flow. |
180 | return setToEntryState(after); |
181 | } |
182 | |
183 | // Join the state with the state after the block's predecessors. |
184 | for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end(); |
185 | it != e; ++it) { |
186 | // Skip control edges that aren't executable. |
187 | Block *predecessor = *it; |
188 | if (!getOrCreateFor<Executable>( |
189 | dependent: point, anchor: getLatticeAnchor<CFGEdge>(args&: predecessor, args&: block)) |
190 | ->isLive()) |
191 | continue; |
192 | |
193 | // Merge in the state from the predecessor's terminator. |
194 | join(lhs: after, rhs: *getLatticeFor( |
195 | dependent: point, anchor: getProgramPointAfter(op: predecessor->getTerminator()))); |
196 | } |
197 | } |
198 | |
199 | void AbstractDenseForwardDataFlowAnalysis::visitRegionBranchOperation( |
200 | ProgramPoint *point, RegionBranchOpInterface branch, |
201 | AbstractDenseLattice *after) { |
202 | // Get the terminator predecessors. |
203 | const auto *predecessors = getOrCreateFor<PredecessorState>(dependent: point, anchor: point); |
204 | assert(predecessors->allPredecessorsKnown() && |
205 | "unexpected unresolved region successors" ); |
206 | |
207 | for (Operation *op : predecessors->getKnownPredecessors()) { |
208 | const AbstractDenseLattice *before; |
209 | // If the predecessor is the parent, get the state before the parent. |
210 | if (op == branch) { |
211 | before = getLatticeFor(dependent: point, anchor: getProgramPointBefore(op)); |
212 | // Otherwise, get the state after the terminator. |
213 | } else { |
214 | before = getLatticeFor(dependent: point, anchor: getProgramPointAfter(op)); |
215 | } |
216 | |
217 | // This function is called in two cases: |
218 | // 1. when visiting the block (point = block start); |
219 | // 2. when visiting the parent operation (point = iter after parent op). |
220 | // In both cases, we are looking for predecessor operations of the point, |
221 | // 1. predecessor may be the terminator of another block from another |
222 | // region (assuming that the block does belong to another region via an |
223 | // assertion) or the parent (when parent can transfer control to this |
224 | // region); |
225 | // 2. predecessor may be the terminator of a block that exits the |
226 | // region (when region transfers control to the parent) or the operation |
227 | // before the parent. |
228 | // In the latter case, just perform the join as it isn't the control flow |
229 | // affected by the region. |
230 | std::optional<unsigned> regionFrom = |
231 | op == branch ? std::optional<unsigned>() |
232 | : op->getBlock()->getParent()->getRegionNumber(); |
233 | if (point->isBlockStart()) { |
234 | unsigned regionTo = point->getBlock()->getParent()->getRegionNumber(); |
235 | visitRegionBranchControlFlowTransfer(branch: branch, regionFrom, regionTo, |
236 | before: *before, after); |
237 | } else { |
238 | assert(point->getPrevOp() == branch && |
239 | "expected to be visiting the branch itself" ); |
240 | // Only need to call the arc transfer when the predecessor is the region |
241 | // or the op itself, not the previous op. |
242 | if (op->getParentOp() == branch || op == branch) { |
243 | visitRegionBranchControlFlowTransfer( |
244 | branch: branch, regionFrom, /*regionTo=*/std::nullopt, before: *before, after); |
245 | } else { |
246 | join(lhs: after, rhs: *before); |
247 | } |
248 | } |
249 | } |
250 | } |
251 | |
252 | //===----------------------------------------------------------------------===// |
253 | // AbstractDenseBackwardDataFlowAnalysis |
254 | //===----------------------------------------------------------------------===// |
255 | |
256 | void AbstractDenseBackwardDataFlowAnalysis::initializeEquivalentLatticeAnchor( |
257 | Operation *top) { |
258 | top->walk(callback: [&](Operation *op) { |
259 | if (isa<RegionBranchOpInterface, CallOpInterface>(Val: op)) |
260 | return; |
261 | buildOperationEquivalentLatticeAnchor(op); |
262 | }); |
263 | } |
264 | |
265 | LogicalResult |
266 | AbstractDenseBackwardDataFlowAnalysis::initialize(Operation *top) { |
267 | // Visit every operation and block. |
268 | if (failed(Result: processOperation(op: top))) |
269 | return failure(); |
270 | |
271 | for (Region ®ion : top->getRegions()) { |
272 | for (Block &block : region) { |
273 | visitBlock(block: &block); |
274 | for (Operation &op : llvm::reverse(C&: block)) { |
275 | if (failed(Result: initialize(top: &op))) |
276 | return failure(); |
277 | } |
278 | } |
279 | } |
280 | return success(); |
281 | } |
282 | |
283 | LogicalResult |
284 | AbstractDenseBackwardDataFlowAnalysis::visit(ProgramPoint *point) { |
285 | if (!point->isBlockEnd()) |
286 | return processOperation(op: point->getNextOp()); |
287 | visitBlock(block: point->getBlock()); |
288 | return success(); |
289 | } |
290 | |
291 | void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation( |
292 | CallOpInterface call, const AbstractDenseLattice &after, |
293 | AbstractDenseLattice *before) { |
294 | // Find the callee. |
295 | Operation *callee = call.resolveCallableInTable(&symbolTable); |
296 | |
297 | auto callable = dyn_cast_or_null<CallableOpInterface>(callee); |
298 | // No region means the callee is only declared in this module. |
299 | // If that is the case or if the solver is not interprocedural, |
300 | // let the hook handle it. |
301 | if (!getSolverConfig().isInterprocedural() || |
302 | (callable && (!callable.getCallableRegion() || |
303 | callable.getCallableRegion()->empty()))) { |
304 | return visitCallControlFlowTransfer( |
305 | call: call, action: CallControlFlowAction::ExternalCallee, after, before); |
306 | } |
307 | |
308 | if (!callable) |
309 | return setToExitState(before); |
310 | |
311 | Region *region = callable.getCallableRegion(); |
312 | |
313 | // Call-level control flow specifies the data flow here. |
314 | // |
315 | // func.func @callee() { |
316 | // ^calleeEntryBlock: |
317 | // // latticeAtCalleeEntry |
318 | // ... |
319 | // } |
320 | // func.func @caller() { |
321 | // ... |
322 | // // latticeBeforeCall |
323 | // call @callee |
324 | // ... |
325 | // } |
326 | Block *calleeEntryBlock = ®ion->front(); |
327 | ProgramPoint *calleeEntry = getProgramPointBefore(block: calleeEntryBlock); |
328 | const AbstractDenseLattice &latticeAtCalleeEntry = |
329 | *getLatticeFor(dependent: getProgramPointBefore(call.getOperation()), anchor: calleeEntry); |
330 | AbstractDenseLattice *latticeBeforeCall = before; |
331 | visitCallControlFlowTransfer(call: call, action: CallControlFlowAction::EnterCallee, |
332 | after: latticeAtCalleeEntry, before: latticeBeforeCall); |
333 | } |
334 | |
335 | LogicalResult |
336 | AbstractDenseBackwardDataFlowAnalysis::processOperation(Operation *op) { |
337 | ProgramPoint *point = getProgramPointBefore(op); |
338 | // If the containing block is not executable, bail out. |
339 | if (op->getBlock() != nullptr && |
340 | !getOrCreateFor<Executable>(dependent: point, anchor: getProgramPointBefore(block: op->getBlock())) |
341 | ->isLive()) |
342 | return success(); |
343 | |
344 | // Get the dense lattice to update. |
345 | AbstractDenseLattice *before = getLattice(anchor: point); |
346 | |
347 | // Get the dense state after execution of this op. |
348 | const AbstractDenseLattice *after = |
349 | getLatticeFor(dependent: point, anchor: getProgramPointAfter(op)); |
350 | |
351 | // Special cases where control flow may dictate data flow. |
352 | if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) { |
353 | visitRegionBranchOperation(point, branch: branch, branchPoint: RegionBranchPoint::parent(), |
354 | before); |
355 | return success(); |
356 | } |
357 | if (auto call = dyn_cast<CallOpInterface>(op)) { |
358 | visitCallOperation(call: call, after: *after, before); |
359 | return success(); |
360 | } |
361 | |
362 | // Invoke the operation transfer function. |
363 | return visitOperationImpl(op, after: *after, before); |
364 | } |
365 | |
366 | void AbstractDenseBackwardDataFlowAnalysis::visitBlock(Block *block) { |
367 | ProgramPoint *point = getProgramPointAfter(block); |
368 | // If the block is not executable, bail out. |
369 | if (!getOrCreateFor<Executable>(dependent: point, anchor: getProgramPointBefore(block)) |
370 | ->isLive()) |
371 | return; |
372 | |
373 | AbstractDenseLattice *before = getLattice(anchor: point); |
374 | |
375 | // We need "exit" blocks, i.e. the blocks that may return control to the |
376 | // parent operation. |
377 | auto isExitBlock = [](Block *b) { |
378 | // Treat empty and terminator-less blocks as exit blocks. |
379 | if (b->empty() || !b->back().mightHaveTrait<OpTrait::IsTerminator>()) |
380 | return true; |
381 | |
382 | // There may be a weird case where a terminator may be transferring control |
383 | // either to the parent or to another block, so exit blocks and successors |
384 | // are not mutually exclusive. |
385 | return isa_and_nonnull<RegionBranchTerminatorOpInterface>( |
386 | Val: b->getTerminator()); |
387 | }; |
388 | if (isExitBlock(block)) { |
389 | // If this block is exiting from a callable, the successors of exiting from |
390 | // a callable are the successors of all call sites. And the call sites |
391 | // themselves are predecessors of the callable. |
392 | auto callable = dyn_cast<CallableOpInterface>(block->getParentOp()); |
393 | if (callable && callable.getCallableRegion() == block->getParent()) { |
394 | const auto *callsites = getOrCreateFor<PredecessorState>( |
395 | point, getProgramPointAfter(callable)); |
396 | // If not all call sites are known, conservative mark all lattices as |
397 | // having reached their pessimistic fix points. |
398 | if (!callsites->allPredecessorsKnown() || |
399 | !getSolverConfig().isInterprocedural()) { |
400 | return setToExitState(before); |
401 | } |
402 | |
403 | for (Operation *callsite : callsites->getKnownPredecessors()) { |
404 | const AbstractDenseLattice *after = |
405 | getLatticeFor(point, getProgramPointAfter(callsite)); |
406 | visitCallControlFlowTransfer(cast<CallOpInterface>(callsite), |
407 | CallControlFlowAction::ExitCallee, *after, |
408 | before); |
409 | } |
410 | return; |
411 | } |
412 | |
413 | // If this block is exiting from an operation with region-based control |
414 | // flow, propagate the lattice back along the control flow edge. |
415 | if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp())) { |
416 | visitRegionBranchOperation(point, branch: branch, branchPoint: block->getParent(), before); |
417 | return; |
418 | } |
419 | |
420 | // Cannot reason about successors of an exit block, set the pessimistic |
421 | // fixpoint. |
422 | return setToExitState(before); |
423 | } |
424 | |
425 | // Meet the state with the state before block's successors. |
426 | for (Block *successor : block->getSuccessors()) { |
427 | if (!getOrCreateFor<Executable>(dependent: point, |
428 | anchor: getLatticeAnchor<CFGEdge>(args&: block, args&: successor)) |
429 | ->isLive()) |
430 | continue; |
431 | |
432 | // Merge in the state from the successor: either the first operation, or the |
433 | // block itself when empty. |
434 | meet(lhs: before, rhs: *getLatticeFor(dependent: point, anchor: getProgramPointBefore(block: successor))); |
435 | } |
436 | } |
437 | |
438 | void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation( |
439 | ProgramPoint *point, RegionBranchOpInterface branch, |
440 | RegionBranchPoint branchPoint, AbstractDenseLattice *before) { |
441 | |
442 | // The successors of the operation may be either the first operation of the |
443 | // entry block of each possible successor region, or the next operation when |
444 | // the branch is a successor of itself. |
445 | SmallVector<RegionSuccessor> successors; |
446 | branch.getSuccessorRegions(branchPoint, successors); |
447 | for (const RegionSuccessor &successor : successors) { |
448 | const AbstractDenseLattice *after; |
449 | if (successor.isParent() || successor.getSuccessor()->empty()) { |
450 | after = getLatticeFor(dependent: point, anchor: getProgramPointAfter(branch)); |
451 | } else { |
452 | Region *successorRegion = successor.getSuccessor(); |
453 | assert(!successorRegion->empty() && "unexpected empty successor region" ); |
454 | Block *successorBlock = &successorRegion->front(); |
455 | |
456 | if (!getOrCreateFor<Executable>(dependent: point, |
457 | anchor: getProgramPointBefore(block: successorBlock)) |
458 | ->isLive()) |
459 | continue; |
460 | |
461 | after = getLatticeFor(dependent: point, anchor: getProgramPointBefore(block: successorBlock)); |
462 | } |
463 | |
464 | visitRegionBranchControlFlowTransfer(branch: branch, regionFrom: branchPoint, regionTo: successor, after: *after, |
465 | before); |
466 | } |
467 | } |
468 | |