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
24using namespace mlir;
25using namespace mlir::dataflow;
26
27//===----------------------------------------------------------------------===//
28// AbstractDenseForwardDataFlowAnalysis
29//===----------------------------------------------------------------------===//
30
31void 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
40LogicalResult AbstractDenseForwardDataFlowAnalysis::initialize(Operation *top) {
41 // Visit every operation and block.
42 if (failed(Result: processOperation(op: top)))
43 return failure();
44
45 for (Region &region : 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
56LogicalResult AbstractDenseForwardDataFlowAnalysis::visit(ProgramPoint *point) {
57 if (!point->isBlockStart())
58 return processOperation(op: point->getPrevOp());
59 visitBlock(block: point->getBlock());
60 return success();
61}
62
63void 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
106LogicalResult
107AbstractDenseForwardDataFlowAnalysis::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
140void 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
199void 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
256void 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
265LogicalResult
266AbstractDenseBackwardDataFlowAnalysis::initialize(Operation *top) {
267 // Visit every operation and block.
268 if (failed(Result: processOperation(op: top)))
269 return failure();
270
271 for (Region &region : 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
283LogicalResult
284AbstractDenseBackwardDataFlowAnalysis::visit(ProgramPoint *point) {
285 if (!point->isBlockEnd())
286 return processOperation(op: point->getNextOp());
287 visitBlock(block: point->getBlock());
288 return success();
289}
290
291void 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 = &region->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
335LogicalResult
336AbstractDenseBackwardDataFlowAnalysis::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
366void 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
438void 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

source code of mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp