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

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