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/DebugLog.h"
21#include <cassert>
22#include <optional>
23
24using namespace mlir;
25using namespace mlir::dataflow;
26
27#define DEBUG_TYPE "dense-analysis"
28
29//===----------------------------------------------------------------------===//
30// AbstractDenseForwardDataFlowAnalysis
31//===----------------------------------------------------------------------===//
32
33void AbstractDenseForwardDataFlowAnalysis::initializeEquivalentLatticeAnchor(
34 Operation *top) {
35 LDBG() << "initializeEquivalentLatticeAnchor: "
36 << OpWithFlags(top, OpPrintingFlags().skipRegions());
37 top->walk(callback: [&](Operation *op) {
38 if (isa<RegionBranchOpInterface, CallOpInterface>(Val: op)) {
39 LDBG() << " Skipping "
40 << OpWithFlags(op, OpPrintingFlags().skipRegions())
41 << " (region branch or call)";
42 return;
43 }
44 LDBG() << " Building equivalent lattice anchor for "
45 << OpWithFlags(op, OpPrintingFlags().skipRegions());
46 buildOperationEquivalentLatticeAnchor(op);
47 });
48}
49
50LogicalResult AbstractDenseForwardDataFlowAnalysis::initialize(Operation *top) {
51 LDBG() << "initialize (forward): "
52 << OpWithFlags(top, OpPrintingFlags().skipRegions());
53 // Visit every operation and block.
54 if (failed(Result: processOperation(op: top))) {
55 LDBG() << " Failed to process top-level operation";
56 return failure();
57 }
58
59 for (Region &region : top->getRegions()) {
60 LDBG() << " Processing region with " << region.getBlocks().size()
61 << " blocks";
62 for (Block &block : region) {
63 LDBG() << " Processing block with " << block.getOperations().size()
64 << " operations";
65 visitBlock(block: &block);
66 for (Operation &op : block) {
67 LDBG() << " Initializing operation: "
68 << OpWithFlags(&op, OpPrintingFlags().skipRegions());
69 if (failed(Result: initialize(top: &op))) {
70 LDBG() << " Failed to initialize operation";
71 return failure();
72 }
73 }
74 }
75 }
76 LDBG() << " Forward initialization completed successfully";
77 return success();
78}
79
80LogicalResult AbstractDenseForwardDataFlowAnalysis::visit(ProgramPoint *point) {
81 LDBG() << "visit (forward): " << *point;
82 if (!point->isBlockStart()) {
83 LDBG() << " Processing operation: "
84 << OpWithFlags(point->getPrevOp(), OpPrintingFlags().skipRegions());
85 return processOperation(op: point->getPrevOp());
86 }
87 LDBG() << " Visiting block: " << point->getBlock();
88 visitBlock(block: point->getBlock());
89 return success();
90}
91
92void AbstractDenseForwardDataFlowAnalysis::visitCallOperation(
93 CallOpInterface call, const AbstractDenseLattice &before,
94 AbstractDenseLattice *after) {
95 LDBG() << "visitCallOperation (forward): "
96 << OpWithFlags(call.getOperation(), OpPrintingFlags().skipRegions());
97 LDBG() << " before state: " << before;
98 LDBG() << " after state: " << *after;
99
100 // Allow for customizing the behavior of calls to external symbols, including
101 // when the analysis is explicitly marked as non-interprocedural.
102 auto isExternalCallable = [&]() {
103 auto callable =
104 dyn_cast_if_present<CallableOpInterface>(Val: call.resolveCallable());
105 return callable && !callable.getCallableRegion();
106 };
107 if (!getSolverConfig().isInterprocedural() || isExternalCallable()) {
108 LDBG() << " Handling as external callee (non-interprocedural or external)";
109 return visitCallControlFlowTransfer(
110 call, action: CallControlFlowAction::ExternalCallee, before, after);
111 }
112
113 const auto *predecessors = getOrCreateFor<PredecessorState>(
114 dependent: getProgramPointAfter(op: call.getOperation()), anchor: getProgramPointAfter(op: call));
115 // Otherwise, if not all return sites are known, then conservatively assume we
116 // can't reason about the data-flow.
117 if (!predecessors->allPredecessorsKnown()) {
118 LDBG() << " Not all predecessors known, setting to entry state";
119 return setToEntryState(after);
120 }
121
122 LDBG() << " Processing " << predecessors->getKnownPredecessors().size()
123 << " known predecessors";
124 for (Operation *predecessor : predecessors->getKnownPredecessors()) {
125 LDBG() << " Processing predecessor: "
126 << OpWithFlags(predecessor, OpPrintingFlags().skipRegions());
127 // Get the lattices at callee return:
128 //
129 // func.func @callee() {
130 // ...
131 // return // predecessor
132 // // latticeAtCalleeReturn
133 // }
134 // func.func @caller() {
135 // ...
136 // call @callee
137 // // latticeAfterCall
138 // ...
139 // }
140 AbstractDenseLattice *latticeAfterCall = after;
141 const AbstractDenseLattice *latticeAtCalleeReturn =
142 getLatticeFor(dependent: getProgramPointAfter(op: call.getOperation()),
143 anchor: getProgramPointAfter(op: predecessor));
144 LDBG() << " Lattice at callee return: " << *latticeAtCalleeReturn;
145 visitCallControlFlowTransfer(call, action: CallControlFlowAction::ExitCallee,
146 before: *latticeAtCalleeReturn, after: latticeAfterCall);
147 }
148}
149
150LogicalResult
151AbstractDenseForwardDataFlowAnalysis::processOperation(Operation *op) {
152 LDBG() << "processOperation (forward): "
153 << OpWithFlags(op, OpPrintingFlags().skipRegions());
154 ProgramPoint *point = getProgramPointAfter(op);
155 // If the containing block is not executable, bail out.
156 if (op->getBlock() != nullptr &&
157 !getOrCreateFor<Executable>(dependent: point, anchor: getProgramPointBefore(block: op->getBlock()))
158 ->isLive()) {
159 LDBG() << " Block not executable, skipping operation";
160 return success();
161 }
162
163 // Get the dense lattice to update.
164 AbstractDenseLattice *after = getLattice(anchor: point);
165
166 // Get the dense state before the execution of the op.
167 const AbstractDenseLattice *before =
168 getLatticeFor(dependent: point, anchor: getProgramPointBefore(op));
169 LDBG() << " before state: " << *before;
170 LDBG() << " after state: " << *after;
171
172 // If this op implements region control-flow, then control-flow dictates its
173 // transfer function.
174 if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: op)) {
175 LDBG() << " Processing as region branch operation";
176 visitRegionBranchOperation(point, branch, after);
177 return success();
178 }
179
180 // If this is a call operation, then join its lattices across known return
181 // sites.
182 if (auto call = dyn_cast<CallOpInterface>(Val: op)) {
183 LDBG() << " Processing as call operation";
184 visitCallOperation(call, before: *before, after);
185 return success();
186 }
187
188 // Invoke the operation transfer function.
189 LDBG() << " Invoking operation transfer function";
190 return visitOperationImpl(op, before: *before, after);
191}
192
193void AbstractDenseForwardDataFlowAnalysis::visitBlock(Block *block) {
194 LDBG() << "visitBlock (forward): " << block;
195 // If the block is not executable, bail out.
196 ProgramPoint *point = getProgramPointBefore(block);
197 if (!getOrCreateFor<Executable>(dependent: point, anchor: point)->isLive()) {
198 LDBG() << " Block not executable, skipping";
199 return;
200 }
201
202 // Get the dense lattice to update.
203 AbstractDenseLattice *after = getLattice(anchor: point);
204 LDBG() << " Block lattice state: " << *after;
205
206 // The dense lattices of entry blocks are set by region control-flow or the
207 // callgraph.
208 if (block->isEntryBlock()) {
209 LDBG() << " Processing entry block";
210 // Check if this block is the entry block of a callable region.
211 auto callable = dyn_cast<CallableOpInterface>(Val: block->getParentOp());
212 if (callable && callable.getCallableRegion() == block->getParent()) {
213 LDBG() << " Entry block of callable region";
214 const auto *callsites = getOrCreateFor<PredecessorState>(
215 dependent: point, anchor: getProgramPointAfter(op: callable));
216 // If not all callsites are known, conservatively mark all lattices as
217 // having reached their pessimistic fixpoints. Do the same if
218 // interprocedural analysis is not enabled.
219 if (!callsites->allPredecessorsKnown() ||
220 !getSolverConfig().isInterprocedural()) {
221 LDBG() << " Not all callsites known or non-interprocedural, setting "
222 "to entry state";
223 return setToEntryState(after);
224 }
225 LDBG() << " Processing " << callsites->getKnownPredecessors().size()
226 << " known callsites";
227 for (Operation *callsite : callsites->getKnownPredecessors()) {
228 LDBG() << " Processing callsite: "
229 << OpWithFlags(callsite, OpPrintingFlags().skipRegions());
230 // Get the dense lattice before the callsite.
231 const AbstractDenseLattice *before;
232 before = getLatticeFor(dependent: point, anchor: getProgramPointBefore(op: callsite));
233 LDBG() << " Lattice before callsite: " << *before;
234
235 visitCallControlFlowTransfer(call: cast<CallOpInterface>(Val: callsite),
236 action: CallControlFlowAction::EnterCallee,
237 before: *before, after);
238 }
239 return;
240 }
241
242 // Check if we can reason about the control-flow.
243 if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: block->getParentOp())) {
244 LDBG() << " Entry block of region branch operation";
245 return visitRegionBranchOperation(point, branch, after);
246 }
247
248 // Otherwise, we can't reason about the data-flow.
249 LDBG() << " Cannot reason about data-flow, setting to entry state";
250 return setToEntryState(after);
251 }
252
253 // Join the state with the state after the block's predecessors.
254 LDBG() << " Joining state from "
255 << std::distance(first: block->pred_begin(), last: block->pred_end())
256 << " predecessors";
257 for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end();
258 it != e; ++it) {
259 // Skip control edges that aren't executable.
260 Block *predecessor = *it;
261 if (!getOrCreateFor<Executable>(
262 dependent: point, anchor: getLatticeAnchor<CFGEdge>(args&: predecessor, args&: block))
263 ->isLive()) {
264 LDBG() << " Skipping non-executable edge from " << predecessor;
265 continue;
266 }
267
268 LDBG() << " Joining state from predecessor " << predecessor;
269 const AbstractDenseLattice &before = *getLatticeFor(
270 dependent: point, anchor: getProgramPointAfter(op: predecessor->getTerminator()));
271 // Merge in the state from the predecessor's terminator.
272 visitBlockTransfer(block, point, predecessor, before, after);
273 }
274}
275
276void AbstractDenseForwardDataFlowAnalysis::visitRegionBranchOperation(
277 ProgramPoint *point, RegionBranchOpInterface branch,
278 AbstractDenseLattice *after) {
279 LDBG() << "visitRegionBranchOperation (forward): "
280 << OpWithFlags(branch.getOperation(), OpPrintingFlags().skipRegions());
281 LDBG() << " point: " << *point;
282 LDBG() << " after state: " << *after;
283
284 // Get the terminator predecessors.
285 const auto *predecessors = getOrCreateFor<PredecessorState>(dependent: point, anchor: point);
286 assert(predecessors->allPredecessorsKnown() &&
287 "unexpected unresolved region successors");
288
289 LDBG() << " Processing " << predecessors->getKnownPredecessors().size()
290 << " known predecessors";
291 for (Operation *op : predecessors->getKnownPredecessors()) {
292 LDBG() << " Processing predecessor: "
293 << OpWithFlags(op, OpPrintingFlags().skipRegions());
294 const AbstractDenseLattice *before;
295 // If the predecessor is the parent, get the state before the parent.
296 if (op == branch) {
297 LDBG() << " Predecessor is the branch itself, getting state before "
298 "parent";
299 before = getLatticeFor(dependent: point, anchor: getProgramPointBefore(op));
300 // Otherwise, get the state after the terminator.
301 } else {
302 LDBG()
303 << " Predecessor is terminator, getting state after terminator";
304 before = getLatticeFor(dependent: point, anchor: getProgramPointAfter(op));
305 }
306 LDBG() << " before state: " << *before;
307
308 // This function is called in two cases:
309 // 1. when visiting the block (point = block start);
310 // 2. when visiting the parent operation (point = iter after parent op).
311 // In both cases, we are looking for predecessor operations of the point,
312 // 1. predecessor may be the terminator of another block from another
313 // region (assuming that the block does belong to another region via an
314 // assertion) or the parent (when parent can transfer control to this
315 // region);
316 // 2. predecessor may be the terminator of a block that exits the
317 // region (when region transfers control to the parent) or the operation
318 // before the parent.
319 // In the latter case, just perform the join as it isn't the control flow
320 // affected by the region.
321 std::optional<unsigned> regionFrom =
322 op == branch ? std::optional<unsigned>()
323 : op->getBlock()->getParent()->getRegionNumber();
324 LDBG() << " regionFrom: "
325 << (regionFrom ? std::to_string(val: *regionFrom) : "parent");
326
327 if (point->isBlockStart()) {
328 unsigned regionTo = point->getBlock()->getParent()->getRegionNumber();
329 LDBG() << " Point is block start, regionTo: " << regionTo;
330 LDBG() << " Calling visitRegionBranchControlFlowTransfer with "
331 "regionFrom/regionTo";
332 visitRegionBranchControlFlowTransfer(branch, regionFrom, regionTo,
333 before: *before, after);
334 } else {
335 assert(point->getPrevOp() == branch &&
336 "expected to be visiting the branch itself");
337 LDBG() << " Point is not block start, checking if predecessor is "
338 "region or op itself";
339 // Only need to call the arc transfer when the predecessor is the region
340 // or the op itself, not the previous op.
341 if (op->getParentOp() == branch || op == branch) {
342 LDBG() << " Predecessor is region or op itself, calling "
343 "visitRegionBranchControlFlowTransfer";
344 visitRegionBranchControlFlowTransfer(
345 branch, regionFrom, /*regionTo=*/std::nullopt, before: *before, after);
346 } else {
347 LDBG()
348 << " Predecessor is not region or op itself, performing join";
349 join(lhs: after, rhs: *before);
350 }
351 }
352 }
353}
354
355//===----------------------------------------------------------------------===//
356// AbstractDenseBackwardDataFlowAnalysis
357//===----------------------------------------------------------------------===//
358
359void AbstractDenseBackwardDataFlowAnalysis::initializeEquivalentLatticeAnchor(
360 Operation *top) {
361 LDBG() << "initializeEquivalentLatticeAnchor (backward): "
362 << OpWithFlags(top, OpPrintingFlags().skipRegions());
363 top->walk(callback: [&](Operation *op) {
364 if (isa<RegionBranchOpInterface, CallOpInterface>(Val: op)) {
365 LDBG() << " Skipping "
366 << OpWithFlags(op, OpPrintingFlags().skipRegions())
367 << " (region branch or call)";
368 return;
369 }
370 LDBG() << " Building equivalent lattice anchor for "
371 << OpWithFlags(op, OpPrintingFlags().skipRegions());
372 buildOperationEquivalentLatticeAnchor(op);
373 });
374}
375
376LogicalResult
377AbstractDenseBackwardDataFlowAnalysis::initialize(Operation *top) {
378 LDBG() << "initialize (backward): "
379 << OpWithFlags(top, OpPrintingFlags().skipRegions());
380 // Visit every operation and block.
381 if (failed(Result: processOperation(op: top))) {
382 LDBG() << " Failed to process top-level operation";
383 return failure();
384 }
385
386 for (Region &region : top->getRegions()) {
387 LDBG() << " Processing region with " << region.getBlocks().size()
388 << " blocks";
389 for (Block &block : region) {
390 LDBG() << " Processing block with " << block.getOperations().size()
391 << " operations";
392 visitBlock(block: &block);
393 for (Operation &op : llvm::reverse(C&: block)) {
394 LDBG() << " Initializing operation (backward): "
395 << OpWithFlags(&op, OpPrintingFlags().skipRegions());
396 if (failed(Result: initialize(top: &op))) {
397 LDBG() << " Failed to initialize operation";
398 return failure();
399 }
400 }
401 }
402 }
403 LDBG() << " Backward initialization completed successfully";
404 return success();
405}
406
407LogicalResult
408AbstractDenseBackwardDataFlowAnalysis::visit(ProgramPoint *point) {
409 LDBG() << "visit (backward): " << *point;
410 if (!point->isBlockEnd()) {
411 LDBG() << " Processing operation: "
412 << OpWithFlags(point->getNextOp(), OpPrintingFlags().skipRegions());
413 return processOperation(op: point->getNextOp());
414 }
415 LDBG() << " Visiting block: " << point->getBlock();
416 visitBlock(block: point->getBlock());
417 return success();
418}
419
420void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation(
421 CallOpInterface call, const AbstractDenseLattice &after,
422 AbstractDenseLattice *before) {
423 LDBG() << "visitCallOperation (backward): "
424 << OpWithFlags(call.getOperation(), OpPrintingFlags().skipRegions());
425 LDBG() << " after state: " << after;
426 LDBG() << " before state: " << *before;
427
428 // If the solver is not interprocedural, let the hook handle it as an external
429 // callee.
430 if (!getSolverConfig().isInterprocedural()) {
431 LDBG() << " Non-interprocedural analysis, handling as external callee";
432 return visitCallControlFlowTransfer(
433 call, action: CallControlFlowAction::ExternalCallee, after, before);
434 }
435
436 // Find the callee.
437 Operation *callee = call.resolveCallableInTable(symbolTable: &symbolTable);
438 if (callee) {
439 LDBG() << " Resolved callee: "
440 << OpWithFlags(callee, OpPrintingFlags().skipRegions());
441 } else {
442 LDBG() << " Resolved callee: null";
443 }
444
445 auto callable = dyn_cast_or_null<CallableOpInterface>(Val: callee);
446 // No region means the callee is only declared in this module.
447 // If that is the case or if the solver is not interprocedural,
448 // let the hook handle it.
449 if (callable && (!callable.getCallableRegion() ||
450 callable.getCallableRegion()->empty())) {
451 LDBG() << " Callee has no region or empty region, handling as external "
452 "callee";
453 return visitCallControlFlowTransfer(
454 call, action: CallControlFlowAction::ExternalCallee, after, before);
455 }
456
457 if (!callable) {
458 LDBG() << " No callable found, setting to exit state";
459 return setToExitState(before);
460 }
461
462 Region *region = callable.getCallableRegion();
463 LDBG() << " Processing callable with region";
464
465 // Call-level control flow specifies the data flow here.
466 //
467 // func.func @callee() {
468 // ^calleeEntryBlock:
469 // // latticeAtCalleeEntry
470 // ...
471 // }
472 // func.func @caller() {
473 // ...
474 // // latticeBeforeCall
475 // call @callee
476 // ...
477 // }
478 Block *calleeEntryBlock = &region->front();
479 ProgramPoint *calleeEntry = getProgramPointBefore(block: calleeEntryBlock);
480 const AbstractDenseLattice &latticeAtCalleeEntry =
481 *getLatticeFor(dependent: getProgramPointBefore(op: call.getOperation()), anchor: calleeEntry);
482 LDBG() << " Lattice at callee entry: " << latticeAtCalleeEntry;
483 AbstractDenseLattice *latticeBeforeCall = before;
484 visitCallControlFlowTransfer(call, action: CallControlFlowAction::EnterCallee,
485 after: latticeAtCalleeEntry, before: latticeBeforeCall);
486}
487
488LogicalResult
489AbstractDenseBackwardDataFlowAnalysis::processOperation(Operation *op) {
490 LDBG() << "processOperation (backward): "
491 << OpWithFlags(op, OpPrintingFlags().skipRegions());
492 ProgramPoint *point = getProgramPointBefore(op);
493 // If the containing block is not executable, bail out.
494 if (op->getBlock() != nullptr &&
495 !getOrCreateFor<Executable>(dependent: point, anchor: getProgramPointBefore(block: op->getBlock()))
496 ->isLive()) {
497 LDBG() << " Block not executable, skipping operation";
498 return success();
499 }
500
501 // Get the dense lattice to update.
502 AbstractDenseLattice *before = getLattice(anchor: point);
503
504 // Get the dense state after execution of this op.
505 const AbstractDenseLattice *after =
506 getLatticeFor(dependent: point, anchor: getProgramPointAfter(op));
507 LDBG() << " before state: " << *before;
508 LDBG() << " after state: " << *after;
509
510 // Special cases where control flow may dictate data flow.
511 if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: op)) {
512 LDBG() << " Processing as region branch operation";
513 visitRegionBranchOperation(point, branch, branchPoint: RegionBranchPoint::parent(),
514 before);
515 return success();
516 }
517 if (auto call = dyn_cast<CallOpInterface>(Val: op)) {
518 LDBG() << " Processing as call operation";
519 visitCallOperation(call, after: *after, before);
520 return success();
521 }
522
523 // Invoke the operation transfer function.
524 LDBG() << " Invoking operation transfer function";
525 return visitOperationImpl(op, after: *after, before);
526}
527
528void AbstractDenseBackwardDataFlowAnalysis::visitBlock(Block *block) {
529 LDBG() << "visitBlock (backward): " << block;
530 ProgramPoint *point = getProgramPointAfter(block);
531 // If the block is not executable, bail out.
532 if (!getOrCreateFor<Executable>(dependent: point, anchor: getProgramPointBefore(block))
533 ->isLive()) {
534 LDBG() << " Block not executable, skipping";
535 return;
536 }
537
538 AbstractDenseLattice *before = getLattice(anchor: point);
539 LDBG() << " Block lattice state: " << *before;
540
541 // We need "exit" blocks, i.e. the blocks that may return control to the
542 // parent operation.
543 auto isExitBlock = [](Block *b) {
544 // Treat empty and terminator-less blocks as exit blocks.
545 if (b->empty() || !b->back().mightHaveTrait<OpTrait::IsTerminator>())
546 return true;
547
548 // There may be a weird case where a terminator may be transferring control
549 // either to the parent or to another block, so exit blocks and successors
550 // are not mutually exclusive.
551 return isa_and_nonnull<RegionBranchTerminatorOpInterface>(
552 Val: b->getTerminator());
553 };
554 if (isExitBlock(block)) {
555 LDBG() << " Processing exit block";
556 // If this block is exiting from a callable, the successors of exiting from
557 // a callable are the successors of all call sites. And the call sites
558 // themselves are predecessors of the callable.
559 auto callable = dyn_cast<CallableOpInterface>(Val: block->getParentOp());
560 if (callable && callable.getCallableRegion() == block->getParent()) {
561 LDBG() << " Exit block of callable region";
562 const auto *callsites = getOrCreateFor<PredecessorState>(
563 dependent: point, anchor: getProgramPointAfter(op: callable));
564 // If not all call sites are known, conservative mark all lattices as
565 // having reached their pessimistic fix points.
566 if (!callsites->allPredecessorsKnown() ||
567 !getSolverConfig().isInterprocedural()) {
568 LDBG() << " Not all callsites known or non-interprocedural, setting "
569 "to exit state";
570 return setToExitState(before);
571 }
572
573 LDBG() << " Processing " << callsites->getKnownPredecessors().size()
574 << " known callsites";
575 for (Operation *callsite : callsites->getKnownPredecessors()) {
576 LDBG() << " Processing callsite: "
577 << OpWithFlags(callsite, OpPrintingFlags().skipRegions());
578 const AbstractDenseLattice *after =
579 getLatticeFor(dependent: point, anchor: getProgramPointAfter(op: callsite));
580 LDBG() << " Lattice after callsite: " << *after;
581 visitCallControlFlowTransfer(call: cast<CallOpInterface>(Val: callsite),
582 action: CallControlFlowAction::ExitCallee, after: *after,
583 before);
584 }
585 return;
586 }
587
588 // If this block is exiting from an operation with region-based control
589 // flow, propagate the lattice back along the control flow edge.
590 if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: block->getParentOp())) {
591 LDBG() << " Exit block of region branch operation";
592 auto terminator =
593 cast<RegionBranchTerminatorOpInterface>(Val: block->getTerminator());
594 visitRegionBranchOperation(point, branch, branchPoint: terminator, before);
595 return;
596 }
597
598 // Cannot reason about successors of an exit block, set the pessimistic
599 // fixpoint.
600 LDBG() << " Cannot reason about successors, setting to exit state";
601 return setToExitState(before);
602 }
603
604 // Meet the state with the state before block's successors.
605 LDBG() << " Meeting state from " << block->getSuccessors().size()
606 << " successors";
607 for (Block *successor : block->getSuccessors()) {
608 if (!getOrCreateFor<Executable>(dependent: point,
609 anchor: getLatticeAnchor<CFGEdge>(args&: block, args&: successor))
610 ->isLive()) {
611 LDBG() << " Skipping non-executable edge to " << successor;
612 continue;
613 }
614
615 LDBG() << " Meeting state from successor " << successor;
616 // Merge in the state from the successor: either the first operation, or the
617 // block itself when empty.
618 visitBlockTransfer(block, point, successor,
619 after: *getLatticeFor(dependent: point, anchor: getProgramPointBefore(block: successor)),
620 before);
621 }
622}
623
624void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
625 ProgramPoint *point, RegionBranchOpInterface branch,
626 RegionBranchPoint branchPoint, AbstractDenseLattice *before) {
627 LDBG() << "visitRegionBranchOperation (backward): "
628 << OpWithFlags(branch.getOperation(), OpPrintingFlags().skipRegions());
629 LDBG() << " branchPoint: " << (branchPoint.isParent() ? "parent" : "region");
630 LDBG() << " before state: " << *before;
631
632 // The successors of the operation may be either the first operation of the
633 // entry block of each possible successor region, or the next operation when
634 // the branch is a successor of itself.
635 SmallVector<RegionSuccessor> successors;
636 branch.getSuccessorRegions(point: branchPoint, regions&: successors);
637 LDBG() << " Processing " << successors.size() << " successor regions";
638 for (const RegionSuccessor &successor : successors) {
639 const AbstractDenseLattice *after;
640 if (successor.isOperation()) {
641 LDBG() << " Successor is operation";
642 after = getLatticeFor(dependent: point,
643 anchor: getProgramPointAfter(op: successor.getSuccessorOp()));
644 } else if (successor.getSuccessor()->empty()) {
645 LDBG() << " Successor is empty region";
646 after = getLatticeFor(dependent: point, anchor: getProgramPointAfter(op: branch));
647 } else {
648 Region *successorRegion = successor.getSuccessor();
649 assert(!successorRegion->empty() && "unexpected empty successor region");
650 Block *successorBlock = &successorRegion->front();
651 LDBG() << " Successor region with "
652 << successorRegion->getBlocks().size() << " blocks";
653
654 if (!getOrCreateFor<Executable>(dependent: point,
655 anchor: getProgramPointBefore(block: successorBlock))
656 ->isLive()) {
657 LDBG() << " Successor block not executable, skipping";
658 continue;
659 }
660
661 after = getLatticeFor(dependent: point, anchor: getProgramPointBefore(block: successorBlock));
662 }
663 LDBG() << " After state: " << *after;
664
665 visitRegionBranchControlFlowTransfer(branch, regionFrom: branchPoint, regionTo: successor, after: *after,
666 before);
667 }
668}
669