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

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